Deriving and Analyzing Learning Algorithms

很难判断哪种学习算法最适合特定情况。 许多在线学习算法的偏差可以用假设空间上的“距离函数”编码，并且（对于简单的问题）可以使用摊销分析来提供相对性能保证（类似于k服务器问题的竞争比）。 这些保证可以用来指示何时一个偏差比另一个更合适，允许智能选择学习algorithm.This项目探讨了假设上的距离函数和凸优化中使用的Bregman分歧之间的联系。 通过调整为Bregman分歧开发的工具，研究人员将改进和推广性能保证。 这将导致更准确地预测各种学习算法在更广泛的问题上的表现。 此外，改进的理解将使新的学习算法的推导适合于特定情况。

It can be difficult to tell which learning algorithm is best for a particular situation. The bias of many on-line learning algorithms can be encoded with a "distance function" on the hypothesis space, and (for simple problems) an amortized analysis can be used to provide relative performance guarantees (analogous to the competitive ratios for k-server problems). These guarantees can be used to indicate when one bias is more appropriate than another, allowing an intelligent choice of learning algorithm.This project explores the connection between the distance functions over hypotheses and the Bregman divergences used in convex optimization. By adapting the tools developed for Bregman divergences, the investigators will improve and generalize the performance guarantees. This will result in more accurate predictions of how well the various learning algorithms will perform on a wider variety of problems. Furthermore, the improved understanding will enable the derivation of new learning algorithms tailored to specific situations.