Amortized Analysis for On-Line Learning Algorithms

在线学习算法的摊销分析

• 批准号: 9700201
• 负责人: Manfred Warmuth
• 金额: $ 23万
• 依托单位: University of California-Santa Cruz
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-01 至 2000-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9700201&HistoricalAwards=false
• 关键词: Amortized; Analysis; 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.***

该项目的重点是最近在计算学习理论社区中开发的新算法系列。该家族中的算法对其参数进行乘法更新，而不是标准梯度下降方法的常规添加剂更新。来自新家族的算法与梯度血统家族的算法有根本不同的行为。当输入维度较大并且最佳参数设置为``Sparse''时，新算法的新算法特别有用 - 只有几个非零参数。在许多简单的设置中，新家庭已证明损失范围仅在最佳参数设置使用几个参数时仅在参数总数中增长，而标准算法可以轻松地被迫与输入数量成比例的损失相比相同目标的变量。这表明新算法家族在输入维度较大（例如信息检索中）或将少量输入扩展到大量非线性基础函数的环境中可能特别有效。原始输入。该研究的目标是扩展新的算法家庭，量化新家庭和现有算法之间的质量差异，并证明新家庭的实际重要性。***