mlsanityData to 7 Oct 2026

Non-asymptotic Analysis of Biased Stochastic Approximation Scheme

arXiv 1902.00629 ↗First posted 2 Feb 2019stat.ML cs.LG math.OCcited by 45

Not on the map. Why?

Abstract (arXiv)

Stochastic approximation (SA) is a key method used in statistical learning. Recently, its non-asymptotic convergence analysis has been considered in many papers. However, most of the prior analyses are made under restrictive assumptions such as unbiased gradient estimates and convex objective function, which significantly limit their applications to sophisticated tasks such as online and reinforcement learning. These restrictions are all essentially relaxed in this work. In particular, we analyze a general SA scheme to minimize a non-convex, smooth objective function. We consider update procedure whose drift term depends on a state-dependent Markov chain and the mean field is not necessarily of gradient type, covering approximate second-order method and allowing asymptotic bias for the one-step updates. We illustrate these settings with the online EM algorithm and the policy-gradient method for average reward maximization in reinforcement learning.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 6; 2022: 9; 2023: 8; 2024: 12; 2025: 1; 2026: 8.

45 papers.

Sort:

By area:

  1. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 29
  2. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 28
  3. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 27
  4. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 19
  5. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  6. 2022BR-SNIS: Bias Reduced Self-Normalized Importance Samplingcited by 12
  7. 2021Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noisecited by 10
  8. 2023Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learningcited by 10
  9. 2023Zero-Regret Performative Prediction Under Inequality Constraintscited by 10
  10. 2021A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functionscited by 9
  11. 2021Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functionscited by 9
  12. 2022When Do Curricula Work in Federated Learning?cited by 9
33 more
  1. 2022Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datacited by 7
  2. 2023Online covariance estimation for stochastic gradient descent under Markovian samplingcited by 7
  3. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  4. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  5. 2022Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradientscited by 6
  6. 2022Constrained Stochastic Nonconvex Optimization with State-dependent Markov Datacited by 6
  7. 2021Online Estimation and Optimization of Utility-Based Shortfall Riskcited by 5
  8. 2022Data Sampling Affects the Complexity of Online SGD over Dependent Datacited by 5
  9. 2024Stochastic Approximation with Biased MCMC for Expectation Maximizationcited by 5
  10. 2023State and parameter learning with PaRIS particle Gibbscited by 4
  11. 2023Online Variational Sequential Monte Carlocited by 4
  12. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 4
  13. 2024Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oraclescited by 4
  14. 2024Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applicationscited by 4
  15. 2023Convergence Analysis of Stochastic Gradient Descent with MCMC Estimatorscited by 3
  16. 2022Learning from time-dependent streaming data with online stochastic algorithmscited by 2
  17. 2024Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walkscited by 2
  18. 2024Stochastic Gradient Descent with Adaptive Datacited by 2
  19. 2022Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitationcited by 1
  20. 2024EMC2: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergencecited by 1
  21. 2024Recursive Learning of Asymptotic Variational Objectivescited by 1
  22. 2026Efficient Stochastic Optimisation via Sequential Monte Carlocited by 1
  23. 2026Efficient Online Variational Estimation via Monte Carlo Samplingcited by 1
  24. 2026Natural Hypergradient Descent: Algorithm Design, Convergence Analysis, and Parallel Implementationcited by 1
  25. 2026Optimal low-rank stochastic gradient estimation for LLM trainingcited by 1
  26. 2023Towards frugal unsupervised detection of subtle abnormalities in medical imagingcited by 0
  27. 2024Stochastic optimization with arbitrary recurrent data samplingcited by 0
  28. 2024Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsizecited by 0
  29. 2025Latent Guided Sampling for Combinatorial Optimizationcited by 0
  30. 2026Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Expertscited by 0
  31. 2026Fast Model Selection and Stable Optimization for Softmax-Gated Multinomial-Logistic Mixture of Experts Modelscited by 0
  32. 2026UB-SMoE: Universally Balanced Sparse Mixture-of-Experts for Resource-adaptive Federated Fine-tuning of Foundation Modelscited by 0
  33. 2026Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimizationcited by 0