mlsanityData to 7 Oct 2026

Adapting to Mixing Time in Stochastic Optimization with Markovian Data

arXiv 2202.04428 ↗First posted 9 Feb 2022cs.LG stat.MLcited by 35

Not on the map. Why?

Abstract (arXiv)

We consider stochastic optimization problems where data is drawn from a Markov chain. Existing methods for this setting crucially rely on knowing the mixing time of the chain, which in real-world applications is usually unknown. We propose the first optimization method that does not require the knowledge of the mixing time, yet obtains the optimal asymptotic convergence rate when applied to convex problems. We further show that our approach can be extended to: (i) finding stationary points in non-convex optimization with Markovian data, and (ii) obtaining better dependence on the mixing time in temporal difference (TD) learning; in both cases, our method is completely oblivious to the mixing time. Our method relies on a novel combination of multi-level Monte Carlo (MLMC) gradient estimation together with an adaptive learning method.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). Builds on 20 of its 45 references that are in the map. First posted on arXiv 9 Feb 2022.

Builds on

20 of 45 references.

References · 20

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  4. 2017A General and Adaptive Robust Loss Functioncited by 236
  5. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  6. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  7. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  8. 2020Large-Scale Methods for Distributionally Robust Optimizationcited by 179
  9. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  10. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  11. 2018On Markov Chain Gradient Descentcited by 63
  12. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
8 more
  1. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  2. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  3. 2017Online to Offline Conversions, Universality and Adaptive Minibatch Sizescited by 39
  4. 2017Mixing time estimation in reversible Markov chains from a single sample pathcited by 26
  5. 2021Stochastic Bias-Reduced Gradient Methodscited by 25
  6. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 24
  7. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  8. 2021Streaming Linear System Identification with Reverse Experience Replaycited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 9; 2024: 10; 2025: 6; 2026: 8.

35 papers.

Sort:

  1. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  2. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  3. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  4. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  5. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  6. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approachcited by 14
  7. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPscited by 11
  8. 2023Streaming PCA for Markovian Datacited by 9
  9. 2024Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithmcited by 9
  10. 2022Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datacited by 7
  11. 2022Constrained Stochastic Nonconvex Optimization with State-dependent Markov Datacited by 6
  12. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oraclescited by 6
23 more
  1. 2023Rosenthal-type inequalities for linear statistics of Markov chainscited by 5
  2. 2024Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workerscited by 5
  3. 2024Non-asymptotic Analysis of Biased Adaptive Stochastic Approximationcited by 4
  4. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  5. 2024The Entrapment Problem in Random Walk Decentralized Learningcited by 4
  6. 2024Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oraclescited by 4
  7. 2025A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averagingcited by 4
  8. 2025Scalable Decentralized Learning with Teleportationcited by 3
  9. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2
  10. 2026Process-Tensor Tomography of SGD: Measuring Non-Markovian Memory via Back-Flow of Distinguishabilitycited by 2
  11. 2023Markov Chain Mirror Descent On Data Federationcited by 1
  12. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  13. 2026Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffercited by 1
  14. 2023Confidence-Controlled Exploration: Efficient Sparse-Reward Policy Learning for Robot Navigationcited by 0
  15. 2024Markov Chain Gradient Descent in Hilbert Spacescited by 0
  16. 2025Gradient Descent Algorithm in Hilbert Spaces under Stationary Markov Chains with φ- and β-Mixingcited by 0
  17. 2025Online Regularized Learning Algorithms in RKHS with β- and φ-Mixing Sequencescited by 0
  18. 2026Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticitycited by 0
  19. 2026A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithmscited by 0
  20. 2026Decentralized Learning via Random Walk with Jumpscited by 0
  21. 2026Robust Asynchronous Q-Learning under Reward and State Corruption via Batchingcited by 0
  22. 2026Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimizationcited by 0
  23. 2026Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPscited by 0