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.***