Stochastic Approximation

Ask about this topic

Overview

Stochastic approximation studies how repeated updates based on noisy samples can find solutions to optimization, root-finding, and fixed-point problems, including those in reinforcement learning. Common approaches include Polyak–Ruppert averaging, two-time-scale updates, variance reduction, and Lyapunov or Poisson-equation analyses to control noise and dependence. Current work develops finite-time convergence and uncertainty guarantees for settings such as Markovian data, heavy-tailed noise, and asynchronous updates. A central challenge is to obtain sharp, reliable rates without restrictive assumptions on smoothness, stability, or noise.

Latest papers

CardsList

76 papers13 papers in the last four weeks, level with the four weeks before. 0.1% of all new papers.

  1. Stochastic Tracking of Drifting Affine Fixed Points

    Oct 19, 2026Sajad KhodadadianStochastic ApproximationNon-Stationary RL

    Grado Department of Industrial and Systems Engineering, Virginia Tech

  2. A Nonlinear Time-Series Theory for Constant-step SGD with Momentum

    Oct 12, 2026Younghun Lee, Jake Zummo, Wei Biao WuStochastic Gradient DescentStochastic Optimization Convergence

    Department of Statistics, University of Chicago

  3. Limit Theory for Online Expectile Estimation under Short and Long Range Dependence

    Oct 12, 2026Younghun Lee, Jake Zummo, Wei Biao WuLong-Range Dependency ModelingStochastic Approximation

    Department of Statistics, University of Chicago

  4. Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Always

    Oct 8, 2026Safwan Labbi, Paul Mangold, Eric MoulinesFederated LearningHeterogeneous Federated Learning

    CMAP, CNRS, École Polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France · Mohamed bin Zayed University of Artificial Intelligence, UAE · LRE EPITA, 94270 Le Kremlin-Bicêtre, France

  5. Stationary Bias and Extrapolation in Nonlinear Two-Timescale Stochastic Approximation

    Oct 7, 2026A. Ch. Madhusudanarao, Rahul SinghRichardson ExtrapolationStochastic Approximation

    Department of Computer Science and Automation Indian Institute of Science, Bengaluru, India · Laboratoire de Recherche de l’EPITA, Paris, France

  6. What a Reporting Convention Hides: A Matched-Budget Audit of Quantum Natural Gradient with an Exactly Computed Metric

    Oct 7, 2026Lu Wei, Yufeng Wang, Haibin LingQuantum Machine LearningVariational Quantum Algorithms

    Stony Brook University · Westlake University

  7. Moment-Accurate Gaussian Mixtures for Constant-Step Stochastic Approximation

    Oct 4, 2026Xiaoli Li, Wei Biao WuGaussian Mixture ModelsStochastic Approximation

    University of Chicago

  8. Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD

    Sep 30, 2026Junghoon SeoStochastic ApproximationStochastic Gradient Descent

    PIT IN Corp., South Korea

  9. Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data

    Sep 30, 2026Yang PengAsynchronous RLStochastic Approximation

    Yau Mathematical Sciences Center, Tsinghua University

  10. Probe-Space Preconditioning for Fast and Stable Zero-Order Training

    Sep 29, 2026Francois Chaubard, Mykel J. Kochenderfer, Chris RéZeroth-Order OptimizationMemory-Efficient Fine-Tuning

    Stanford University, Stanford, CA, USA.

  11. Second-Moment Stochastic Approximation Methods

    Sep 29, 2026Tao Jiang, Lin XiaoStochastic ApproximationMuon Optimizer

    Fundamental AI Research (FAIR), Meta Superintelligence Labs

  12. Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding

    Sep 28, 2026TaeHo Yoon, Nicolas LoizouStochastic Approximation

    Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science, Johns Hopkins University

  13. Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise

    Sep 28, 2026Rahul Singh, Vivek S. Borkar, Eric MoulinesLast-Iterate ConvergenceStochastic Approximation

    Laboratoire de Recherche de l’EPITA, Paris, France · Indian Institute of Technology Bombay · Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, United Arab Emirates

  14. A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning

    Sep 24, 2026Ids van der Werf, Sergio Rozada, Antonio G. MarquesStochastic ApproximationTemporal-Difference Learning

    Delft University of Technology, Dep. Microelectronics, Delft, The Netherlands

  15. Distributed Stochastic Approximation Algorithms and Heavy-Tailed Age of Information

    Sep 23, 2026Adrian Redder, Arunselvan Ramaswamy, Holger KarlStochastic ApproximationAge of Information

    Dept. of Electrical Engineering and Information Technology, Paderborn University, Germany · Dept. of Industrial Engineering and Operations Research, Indian Institute of Technology Bombay, India · Hasso-Plattner Institute (HPI), Digital Engineering Faculty, University of Potsdam, Germany

  16. Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity

    Sep 22, 2026Tong Yang, Tao Jiang, Yuejie Chi +2Last-Iterate ConvergenceStochastic Approximation

    Department of Electrical and Computer Engineering, Carnegie Mellon University · Fundamental AI Research (FAIR), Meta Superintelligence Labs · Department of Statistics and Data Science, Yale University +1

  17. Polyak-Type Extragradient Methods for Monotone Root-Finding Problems

    Sep 22, 2026TaeHo Yoon, Sayantan Choudhury, Ezra Greenberg +1Stochastic ApproximationExtragradient Methods

    Department of Applied Mathematics & Statistics Mathematical Institute for Data Science (MINDS) Johns Hopkins University

  18. Locally Private Inference for Riemannian Stochastic Optimization

    Sep 18, 2026Xiaotian Chang, Yangdi Jiang, Qirui HuRiemannian OptimizationConfidence Region Estimation

    School of Physical and Mathematical Sciences, Nanyang Technological University · School of Statistics and Data Science, Shanghai University of Finance and Economics.

  19. The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes

    Sep 17, 2026Djamel Rassem Lamouri, Dorian Baudry, Nicolas GastStochastic ApproximationTwo-Timescale Stochastic Approximation

    Univ. Grenoble Alpes, CNRS, Inria Grenoble INP, LIG, 38000 Grenoble France

  20. Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

    Sep 14, 2026Jun-Hyun Kim, Ahmet AlacaogluLast-Iterate ConvergenceStochastic Approximation

    University of British Columbia, Vancouver. · Department of Mathematics, University of British Columbia, Vancouver.

  21. Steady-State Convergence of Stochastic Approximation

    Sep 14, 2026Yixuan Zhang, Qiaomin XieStochastic ApproximationQ-Learning

    Department of Industrial & Systems Engineering, University of Wisconsin–Madison

  22. Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizes

    Sep 14, 2026Xingguo Chen, Zhaohui Wu, Jinguo Ye +5Temporal-Difference LearningStochastic Approximation

    Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, Nanjing University of Posts & Telecommunications, Nanjing 210023, China · Nanjing University, 163 Xianlin Avenue, Nanjing 210023, China · Microsoft Corporation, One Microsoft Way, Redmond, WA 98052, USA +1

  23. Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints

    Sep 12, 2026Kang Liu, Mengxiao Chen, Siqi Xiong +1Primal-Dual OptimizationStochastic Optimization Convergence

    School of Future Technology, Xi’an Jiaotong University, Xi’an, China · School of Automation Science and Engineering, Xi’an Jiaotong University, Xi’an, China · Department of Rehabilitation Sciences, The Hong Kong Polytechnic University, Hong Kong SAR, China

  24. Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

    Sep 11, 2026Xinchen Du, Elizaveta Rebrova, Michał Dereziński +1Stochastic ApproximationSecond-Order Optimization

    School of Industrial and Systems Engineering, Georgia Institute of Technology · Department of Operations Research and Financial Engineering, Princeton University

  25. Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

    Sep 8, 2026Jelena Diakonikolas, Cristóbal Guzmán, David Martínez-RubioOracle ComplexityStochastic Approximation

    Department of Computer Sciences, University of Wisconsin-Madison · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile · IMDEA Software Institute, Madrid, Spain

  26. Convergence rates for the RMSprop optimizer with full control of the hyperparameters

    Aug 31, 2026Steffen Dereich, Arnulf JentzenStochastic ApproximationStochastic Optimization Convergence

  27. A Finite-Sample Analysis of Quantile Temporal-Difference Learning

    Aug 27, 2026Zijie Cheng, Xiang Li, Yang Peng +1Distributional RLStochastic Approximation

    School of Mathematical Sciences, Peking University · Perelman School of Medicine, University of Pennsylvania · Yau Mathematical Sciences Center, Tsinghua University

  28. SAUSS: Stochastic Approximation with Unbiased Simulated Scores for Limited Dependent Variable Models

    Aug 26, 2026Sokbae Lee, Yuan Liao, Myung Hwan Seo +1Stochastic ApproximationDiscrete Choice Modeling

    Department of Economics, Columbia University, New York, NY 10027, USA. · Department of Economics, University of Iowa, Iowa City, IA 52242, USA. · Department of Economics, The Hong Kong University of Science and Technology, Hong Kong. +1

  29. Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

    Aug 23, 2026Shengbo WangQ-LearningFunction Approximation in RL

    Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

  30. A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps

    Aug 16, 2026Ege C. Kaya, Arda Fazla, M. Berk Sahin +1Stochastic ApproximationLast-Iterate Convergence

    Elmore Family School of Electrical and Computer Engineering Purdue University West Lafayette, IN 47907, USA