Best of three worlds? Bias and extrapolation in constant-step size stochastic approximation

Abstract:  Stochastic approximation is a class of iterative procedures that include, among others, stochastic gradient descent and temporal difference (TD) learning for reinforcement learning. In this talk, we consider linear stochastic approximation (LSA) with a constant stepsize and Markovian noise. We show that the iterate has a limit distribution and converges to it geometrically in Wasserstein distance. Furthermore, we provide a precise characterization of the asymptotic bias of the limit: it admits a Taylor-like, infinite series expansion with respect to the stepsize. Moreover, the bias is proportional to the mixing time of the Markovian noise and hence vanishes when the noise is in fact i.i.d.

The results above suggest the following algorithmic paradigm for LSA, which combines three ingredients: (1) use a constant stepsize for fast convergence of the optimization error, (2) use Polyak-Ruppert averaging to reduce the variance, and (3) use Richardson-Romberg extrapolation to correct the bias. In particular, our infinite series expansion implies that extrapolation with m stepsizes eliminates the m-1 leading terms in the bias expansion, resulting in an exponentially smaller bias.

Bio:  Qiaomin Xie is an assistant professor in the Department of Industrial and Systems Engineering (ISyE) at the University of Wisconsin-Madison. She was previously a visiting assistant professor at the School of Operations Research and Information Engineering at Cornell University. Prior to that, she was a postdoctoral researcher with LIDS at MIT. Qiaomin received her Ph.D. degree in Electrical and Computing Engineering from the University of Illinois Urbana Champaign in 2016. Her research interests lie in the fields of reinforcement learning, applied probability and stochastic networks, with applications to computer and communication networks. She is the recipient of JP Morgan Faculty Research Award (2021), Google Systems Research Award (2020) and UIUC CSL Ph.D. Thesis Award (2017)

***Event will take place in a hybrid format. The location for in-person attendance will be room 1690 Beyster Building.   Attendance will also be available via Zoom.

Join Zoom Meeting: https://umich.zoom.us/j/91414297851

Meeting ID: 914 1429 7851

Passcode: XXXXXX (Will be sent via e-mail to attendees)

Zoom Passcode information is also available upon request to Michele Feldkamp ([email protected]) or Sher Nickrand([email protected]).