RI: Small: Random Perturbation Methods in Sequential Learning

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

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.