RI: Small: Random Perturbation Methods in Sequential Learning

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

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.