Stochastic Approximation: How to do it Instance-Optimally?

3/16/23 | 4:15pm | E25-111

 

 

 

 

Martin Wainwright

Cecil H. Green Professor
MIT

Abstract: Stochastic approximation (SA) methods, dating back to the seminal work of Robbins-Monro (1951), are used to solve fixed point equations based on noisy observations. They are a computational workhorse in statistics, machine learning, and operations research. Classical results provide instance dependent asymptotic guarantees, but do not distinguish between methods at the finite-sample level. Other more recent work provides non-asymptotic guarantees, but fails to guarantee asymptotic optimality. In this talk, we describe a two-time-scale SA procedure (ROOT-SA) that is easy to implement, and simultaneously instance-optimal in both asymptotic and non-asymptotic senses. We illustrate this general procedure with applications to reinforcement learning.

Based on joint work with Wenlong Mou, Koulik Khamaru, Peter Bartlett, Michael Jordan (UC Berkeley).

Bio: Martin Wainwright is currently the Cecil H. Green Professor at MIT, affiliated with LIDS, IDSS and SDSC. He received a Bachelor’s degree in Mathematics from University of Waterloo, Canada, and a Ph.D. degree in EECS from Massachusetts Institute of Technology (MIT). His research interests include high-dimensional statistics, stochastic control and reinforcement learning, causal inference, and information-theoretic methods in statistics. He was a Section Lecturer at the International Congress of Mathematicians in 2014, received the COPSS Presidents’ Award (2014) from the Joint Statistical Societies; and the Medallion Award and Lectureship (2013), and the David Blackwell Award (2017) from the Institute of Mathematical Statistics.

Event Time:
2023 – 16:15