mlsanityData to 7 Oct 2026

First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities

arXiv 2305.15938 ↗First posted 25 May 2023math.OC cs.LG stat.MLcited by 14

Not on the map. Why?

Abstract (arXiv)

This paper delves into stochastic optimization problems that involve Markovian noise. We present a unified approach for the theoretical analysis of first-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time of the underlying noise sequence, we use the randomized batching scheme, which is based on the multilevel Monte Carlo method. Moreover, our technique allows us to eliminate the limiting assumptions of previous research on Markov noise, such as the need for a bounded domain and uniformly bounded stochastic gradients. Our extension to variational inequalities under Markovian noise is original. Additionally, we provide lower bounds that match the oracle complexity of our method in the case of strongly convex optimization problems.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 47 of its 106 references that are in the map. First posted on arXiv 25 May 2023.

Builds on

47 of 106 references.

References · 47

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  5. 2017Training GANs with Optimismcited by 217
  6. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  7. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  8. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  9. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  10. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 142
  11. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  12. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
35 more
  1. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  2. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  3. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 81
  4. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  5. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  6. 2018On Markov Chain Gradient Descentcited by 63
  7. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  8. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  9. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  10. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  11. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  12. 2018On the insufficiency of existing momentum schemes for Stochastic Optimizationcited by 46
  13. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46
  14. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  15. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  16. 2019Revisiting Stochastic Extragradientcited by 35
  17. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  18. 2017Extragradient method with variance reduction for stochastic variational inequalitiescited by 33
  19. 2021Stochastic Extragradient: General Analysis and Improved Ratescited by 31
  20. 2018Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimizationcited by 30
  21. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 24
  22. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 22
  23. 2021Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Constructioncited by 22
  24. 2014Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variantscited by 19
  25. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 18
  26. 2019A Universally Optimal Multistage Accelerated Stochastic Gradient Methodcited by 17
  27. 2020Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learningcited by 15
  28. 2020Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithmscited by 14
  29. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  30. 2019Training GANs with Centripetal Accelerationcited by 13
  31. 2019Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functionscited by 12
  32. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  33. 2020Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Conditioncited by 7
  34. 2023Rosenthal-type inequalities for linear statistics of Markov chainscited by 5
  35. 2017Incremental constraint projection methods for monotone stochastic variational inequalitiescited by 3

Built on by

Cited by year (2026 to 7 Oct)

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

14 papers.

Sort:

  1. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  2. 2025Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithmcited by 8
  3. 2024Queuing dynamics of asynchronous Federated Learningcited by 6
  4. 2024Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workerscited by 5
  5. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 4
  6. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  7. 2023Markov Chain Mirror Descent On Data Federationcited by 1
  8. 2024Debiasing Federated Learning with Correlated Client Participationcited by 1
  9. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  10. 2026Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterizationcited by 1
  11. 2024Stochastic optimization with arbitrary recurrent data samplingcited by 0
  12. 2026Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticitycited by 0
2 more
  1. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0
  2. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0