Amortized Analysis for On-Line Learning Algorithms

这个项目的重点是最近在计算学习理论社区中开发的一组新的算法。这类算法对其参数进行乘法更新，而不是标准梯度下降方法通常采用的加性更新。新家族的算法与梯度下降家族的算法有着根本不同的行为。当输入维数较大且最佳参数设置为“稀疏”（只有少数非零参数）时，新的算法家族特别有用。在许多简单的设置中，当最佳参数设置仅使用几个参数时，新系列已证明损失界限仅在参数总数中呈对数增长，而标准算法很容易被强制具有与相同目标的输入变量数量成比例的损失。这表明，在输入维度较大的情况下（例如在信息检索中），或者在原始输入上将少量输入扩展为大量非线性基函数的情况下，新的算法家族可能特别有效。本研究的目标是扩展新算法族，量化新算法族与现有算法族之间的质的差异，并证明新算法族的实际重要性

The focus of this project is a new family of algorithms that has been recently developed within the Computational Learning Theory community. Algorithms in this family do multiplicative updates to their parameters instead of the usual additive updates characteristic of the standard gradient descent methods. The algorithms from the new family have radically different behavior from the algorithms of the gradient descent family. The new family of algorithms is particularly useful when the input dimension is large and the best parameter setting is ``sparse'' -- having only a few non-zero parameters. In many simple settings, the new family has proven loss bounds that grow only logarithmically in the total number of parameters when the best parameter setting uses only a few parameters, whereas the standard algorithms can easily be forced to have loss proportional to the number of input variables for the same targets. This indicates that the new family of algorithms is likely to be particularly effective in settings where the input dimension is large (such as in Information Retrieval) or where a small number of inputs are expanded to a large number of non-linear basis functions over the original inputs. The goals of the research are to extend the new family of algorithms, quantify the qualitative differences between the new family and existing algorithms, and to demonstrate the practical importance of the new family.***