mlsanityData to 7 Oct 2026

Optimal variance-reduced stochastic approximation in Banach spaces

arXiv 2201.08518 ↗First posted 21 Jan 2022math.ST cs.LG math.OCcited by 14

Not on the map. Why?

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.

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

Builds on

28 of 81 references.

References · 28

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  3. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  4. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  5. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  6. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  7. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  8. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  9. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  10. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  11. 2016Statistical Inference for Model Parameters in Stochastic Gradient Descentcited by 71
  12. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
16 more
  1. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  2. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  3. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  4. 2018Averaging Stochastic Gradient Descent on Riemannian Manifoldscited by 39
  5. 2016Asymptotic Optimality in Stochastic Optimizationcited by 38
  6. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  7. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  8. 2020Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learningcited by 22
  9. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21
  10. 2014Competing with the Empirical Risk Minimizer in a Single Passcited by 20
  11. 2020Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopescited by 19
  12. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  13. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  14. 2018Inexact SARAH Algorithm for Stochastic Optimizationcited by 12
  15. 2020ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithmcited by 6
  16. 2018Probabilistic Contraction Analysis of Iterated Random Operatorscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 2; 2024: 6; 2025: 1; 2026: 3.

14 papers.

Sort:

  1. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  2. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  3. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 11
  4. 2024Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noisecited by 10
  5. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  6. 2022Stabilizing Q-learning with Linear Architectures for Provably Efficient Learningcited by 5
  7. 2025Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learningcited by 5
  8. 2024Limit Theorems for Stochastic Gradient Descent with Infinite Variancecited by 3
  9. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  10. 2026Q-Measure-Learning for Continuous State RL: Efficient Implementation and Convergencecited by 1
  11. 2026Statistical Inference for Stochastic Gradient Descent: Beyond Finite Variancecited by 1
  12. 2024Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsizecited by 0
2 more
  1. 2024Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexitycited by 0
  2. 2024To bootstrap or to rollout? An optimal and adaptive interpolationcited by 0