# Adapting to Mixing Time in Stochastic Optimization with Markovian Data

arXiv: https://arxiv.org/abs/2202.04428 · HTML: https://mlsanity.com/paper/2202.04428/

## Key facts

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

## Builds on (most cited first, 20 of 20)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [A General and Adaptive Robust Loss Function](https://mlsanity.com/paper/1701.03077/) (2017)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/1808.05671/) (2018)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Streaming Linear System Identification with Reverse Experience Replay](https://mlsanity.com/paper/2103.05896/) (2021)

## Built on by (most cited first, 30 of 36)

- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes](https://mlsanity.com/paper/2309.01922/) (2023)
- [Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability](https://mlsanity.com/paper/2310.14286/) (2023)
- [Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic](https://mlsanity.com/paper/2301.12083/) (2023)
- [A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach](https://mlsanity.com/paper/2407.18878/) (2024)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs](https://mlsanity.com/paper/2404.02108/) (2024)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm](https://mlsanity.com/paper/2402.02042/) (2024)
- [Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data](https://mlsanity.com/paper/2203.15797/) (2022)
- [Constrained Stochastic Nonconvex Optimization with State-dependent Markov Data](https://mlsanity.com/paper/2206.11346/) (2022)
- [Rosenthal-type inequalities for linear statistics of Markov chains](https://mlsanity.com/paper/2303.05838/) (2023)
- [Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles](https://mlsanity.com/paper/2403.11925/) (2024)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers](https://mlsanity.com/paper/2402.02951/) (2024)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [The Entrapment Problem in Random Walk Decentralized Learning](https://mlsanity.com/paper/2407.20611/) (2024)
- [A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging](https://mlsanity.com/paper/2505.21796/) (2025)
- [Scalable Decentralized Learning with Teleportation](https://mlsanity.com/paper/2501.15259/) (2025)
- [Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis](https://mlsanity.com/paper/2503.17454/) (2025)
- [Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffer](https://mlsanity.com/paper/2601.01502/) (2026)
- [Process-Tensor Tomography of SGD: Measuring Non-Markovian Memory via Back-Flow of Distinguishability](https://mlsanity.com/paper/2601.16563/) (2026)
- [Markov Chain Mirror Descent On Data Federation](https://mlsanity.com/paper/2309.14775/) (2023)
- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)
- [Confidence-Controlled Exploration: Efficient Sparse-Reward Policy Learning for Robot Navigation](https://mlsanity.com/paper/2306.06192/) (2023)
- [Markov Chain Gradient Descent in Hilbert Spaces](https://mlsanity.com/paper/2410.08361/) (2024)
- [Gradient Descent Algorithm in Hilbert Spaces under Stationary Markov Chains with φ- and β-Mixing](https://mlsanity.com/paper/2502.03551/) (2025)
- [Online Regularized Learning Algorithms in RKHS with β- and φ-Mixing Sequences](https://mlsanity.com/paper/2507.05929/) (2025)
- [Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity](https://mlsanity.com/paper/2601.01160/) (2026)

## 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.