Georgia Institute of Technology College of Sciences

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.