Optimal variance-reduced stochastic approximation in Banach spaces

Applied and Computational Mathematics Seminar
Monday, November 21, 2022 - 2:00pm for 1 hour (actually 50 minutes)
Skiles 005 and https://gatech.zoom.us/j/98355006347
Wenlong Mou – UC Berkeley – wmou@eecs.berkeley.edu
Molei Tao

Please Note: Speaker will give the talk in person

Estimating the fixed-point of a contractive operator from empirical data is a fundamental computational and statistical task. In many practical applications including dynamic programming, the relevant norm is not induced by an inner product structure, which hinders existing techniques for analysis. In this talk, I will present recent advances in stochastic approximation methods for fixed-point equations in Banach spaces. Among other results, we discuss a novel variance-reduced stochastic approximation scheme, and establish its non-asymptotic error bounds. In contrast to worst-case guarantees, our bounds are instance-dependent, and achieve the optimal covariance structure in central limit theorems non-asymptotically.
Joint works with Koulik Khamaru, Martin Wainwright, Peter Bartlett, and Michael Jordan.