# Optimal variance-reduced stochastic approximation in Banach spaces

arXiv: https://arxiv.org/abs/2201.08518 · HTML: https://mlsanity.com/paper/2201.08518/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 81 references that are in the map.
- First posted on arXiv 21 Jan 2022.

## Builds on (most cited first, 28 of 28)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis](https://mlsanity.com/paper/2003.07337/) (2020)
- [Averaging Stochastic Gradient Descent on Riemannian Manifolds](https://mlsanity.com/paper/1802.09128/) (2018)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model](https://mlsanity.com/paper/1806.01492/) (2018)
- [Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning](https://mlsanity.com/paper/2106.14352/) (2021)
- [Competing with the Empirical Risk Minimizer in a Single Pass](https://mlsanity.com/paper/1412.6606/) (2014)
- [Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes](https://mlsanity.com/paper/2002.00874/) (2020)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators](https://mlsanity.com/paper/2106.12729/) (2021)
- [Inexact SARAH Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1811.10105/) (2018)
- [ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm](https://mlsanity.com/paper/2008.12690/) (2020)
- [Probabilistic Contraction Analysis of Iterated Random Operators](https://mlsanity.com/paper/1804.01195/) (2018)

## Built on by (most cited first, 17 of 17)

- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning](https://mlsanity.com/paper/2509.26442/) (2025)
- [Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise](https://mlsanity.com/paper/2605.20999/) (2026)
- [Limit Theorems for Stochastic Gradient Descent with Infinite Variance](https://mlsanity.com/paper/2410.16340/) (2024)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [Q-Measure-Learning for Continuous State RL: Efficient Implementation and Convergence](https://mlsanity.com/paper/2603.03523/) (2026)
- [Statistical Inference for Stochastic Gradient Descent: Beyond Finite Variance](https://mlsanity.com/paper/2605.26000/) (2026)
- [Instance-optimal stochastic convex optimization: Can we improve upon sample-average and robust stochastic approximation?](https://mlsanity.com/paper/2603.25657/) (2026)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity](https://mlsanity.com/paper/2408.06544/) (2024)
- [To bootstrap or to rollout? An optimal and adaptive interpolation](https://mlsanity.com/paper/2411.09731/) (2024)
- [Q-Learning with Stable Infinite-Dimensional Linear Function Approximation](https://mlsanity.com/paper/2608.22636/) (2026)

## Abstract (arXiv)

We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. Focusing on a stochastic query model that provides noisy evaluations of the operator, we analyze a variance-reduced stochastic approximation scheme, and establish non-asymptotic bounds for both the operator defect and the estimation error, measured in an arbitrary semi-norm. In contrast to worst-case guarantees, our bounds are instance-dependent, and achieve the local asymptotic minimax risk non-asymptotically. For linear operators, contractivity can be relaxed to multi-step contractivity, so that the theory can be applied to problems like average reward policy evaluation problem in reinforcement learning. We illustrate the theory via applications to stochastic shortest path problems, two-player zero-sum Markov games, as well as policy evaluation and Q-learning for tabular Markov decision processes.