Abstract

A large class of optimization and machine learning algorithms, especially those in reinforcement learning, are based on stochastic approximation (SA). In this talk, we consider SA of operators that are contractive under arbitrary norms. Recent research has established finite sample convergence guarantees for SA algorithms by bounding the mean-square error. This work focuses on obtaining stronger guarantees on the tail of errors, enabling us to provide PAC-style guarantees for the algorithms. We first consider SA with additive noise, which arises in supervised learning applications, and obtain strong sub-Gaussian tail bounds that are valid for all time. Next, we consider SA with multiplicative noise, which occurs in reinforcement learning, and derive Weibull tail bounds. The tail decay rate is faster than polynomial but could be slower than exponential. Additionally, we present an impossibility result showing that our Weibull tail bounds are generally tight. Key ideas in the proof involve the use of exponential Lyapunov functions to construct supermartingales, the application of Ville's maximal inequality, and a novel bootstrapping argument to handle the potential unboundedness of the iterates.

Bio

Zaiwei Chen is currently an Assistant Professor at the School of Industrial Engineering at Purdue University. Prior to this, he was a CMI Postdoctoral Fellow at Caltech in the Computing and Mathematical Sciences Department. He holds a Ph.D. in Machine Learning, as well as an M.S. in Mathematics and an M.S. in Operations Research, all from Georgia Tech.