RI: Small: Random Perturbation Methods in Sequential Learning

无论是婴儿还是机器都不是从白板开始学习的。就像婴儿来到这个世界时，大脑结构使她易于学习运动和语言技能一样，机器必须被赋予足够的优先结构来帮助它学习。这种先验结构在机器学习领域被称为归纳偏差。归纳偏差可以有多种形式，这就是为什么有许多不同种类的机器学习算法。例如，可以告诉机器类似的输入应该产生类似的输出，或者它应该更喜欢更简单的模型而不是复杂的模型。最近，出现了一类利用随机性将归纳偏差注入机器学习算法的方法。然而，研究人员并没有完全了解这些方法的威力和局限性。例如，注入随机性和偏爱更简单的模型之间有什么关系？这个项目研究了在设计机器学习算法时随机性的力量等基本问题。该项目开发的算法可以应用于许多有实际意义的问题，包括发现廉价的可再生能源。根据潜在的顺序学习问题，该项目的技术目标分为三类：在线学习、强盗问题和强化学习。在在线学习中，该项目考察了扰动的普遍性。也就是说，基于扰动的算法是否足够强大，能够在任何在线凸优化问题中实现最优性能保证？这项工作还旨在发现通用的基于扰动的在线学习算法，一旦问题可在线学习，就能成功地学习该问题。在强盗问题中，随机扰动被用来设计算法，该算法对观察到的奖励中的非平稳性和腐败具有鲁棒性。在强化学习中，基于随机扰动的探索策略的设计既便于计算，又具有样本效率。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Neither babies nor machines begin learning from a blank slate. Just like a baby comes into the world with brain structures that predispose her to learn motor and language skills, a machine has to be given enough prior structure to help it learn. This prior structure is called inductive bias in the field of machine learning. Inductive bias can take many forms, which is why there are many different sorts of machine learning algorithms. For example, the machine could be told that similar inputs should produce similar outputs, or that it should prefer simpler models over complex ones. Recently a class of methods has emerged that uses randomness to inject inductive bias into machine learning algorithms. However, researchers do not fully understand the power and limitations of these methods. For example, what is the relationship between injecting randomness and having a preference for simpler models? This project studies such fundamental questions about the power of randomness in designing machine learning algorithms. The algorithms developed in this project can be applied to many problems of practical interest including the discovery of cheap renewable energy sources.The technical goals of this project are divided into three categories according to the underlying sequential learning problem: online learning, bandit problems, and reinforcement learning. In online learning, the project examines the universality of perturbations. That is, are perturbation-based algorithms powerful enough to realize optimal performance guarantees in any online convex optimization problem? This work also aims to discover universal perturbation-based online learning algorithms that succeed in learning a problem as soon as the problem is online learnable. In bandit problems, random perturbations are used to design algorithms that are robust to non-stationarity and corruptions in the observed rewards. In reinforcement learning, exploration strategies based on random perturbations are designed that are both computationally tractable and sample efficient.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.