Efficient Optimal Strategies for Prediction Games

In game-theoretic formulations of prediction problems, a strategy makes a decision, observes an outcome and pays a loss. The aim is to minimize the regret, which is the amount by which the total loss incurred exceeds the total loss of the best decision in hindsight. This talk will focus on the minimax optimal strategy, which exactly minimizes the regret, in two settings: mean estimation (where decisions and outcomes lie in a subset of a Hilbert space, and loss is squared distance), and linear regression (where the aim is to predict real-valued labels almost as well as the best linear function). For the game-theoretic formulations of these classical statistical problems, we obtain the minimax optimal strategies, and show that they can be efficiently computed. These optimal strategies can be viewed as regularized statistical estimators, where the regularization emerges as the optimal approach to hedging against an uncertain future.

Joint work with Yasin Abbasi-Yadkori, Wouter Koolen, Alan Malek, Eiji Takimoto, Manfred Warmuth.

Short Bio:

Peter Bartlett is a professor in the Computer Science Division and Department of Statistics and Associate Director of the Simons Institute for the Theory of Computing at the University of California at Berkeley. His research interests include machine learning and statistical learning theory. He is the co-author, with Martin Anthony, of the book Neural Network Learning: Theoretical Foundations. He has served as an associate editor of the journals Bernoulli, the Journal of Artificial Intelligence Research, the Journal of Machine Learning Research, the IEEE Transactions on Information Theory, Machine Learning, Mathematics of Control Signals and Systems, and Mathematics of Operations Research, and as program committee co-chair for COLT and NIPS. He was awarded the Malcolm McIntosh Prize for Physical Scientist of the Year in Australia in 2001, and was chosen as an Institute of Mathematical Statistics Medallion Lecturer in 2008, and an IMS Fellow and Australian Laureate Fellow in 2011. He was elected to the Australian Academy of Science in 2015.