Research map / Optimization / Nonconvex and smooth optimization
Adapting to Mixing Time in Stochastic Optimization with Markovian Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an MLMC gradient estimator with AdaGrad instead of relying on prior mixing-time knowledge | Convex stochastic optimization with Markovian data · Convex stochastic optimization with Markovian data | convergence rate: \calig{O}(\taumix/\sqrt{T}) -> \Ocaltilde(\sqrt{\taumix/T}) | Helped |
| Use MAG for TD learning with linear function approximation | TD learning · TD learning with linear function approximation | convergence rate: \calig{O}\brac{\frac{G^2\taumix}{(1-\gamma)\sqrt{T}}} -> \tilde{\mathcal{O}}\brac{\frac{GR\sqrt{\taumix}}{(1-\gamma)\sqr | Helped |
| Use MLMC gradient estimation rather than standard stochastic gradients (ablation) | Synthetic linear regression with Markovian data · Synthetic linear regression with Markovian data | suboptimality | Helped |
| Use a non-adaptive learning rate instead of AdaGrad with the MLMC estimator (ablation) | MAG · Synthetic linear regression with Markovian data | suboptimality | Hurt |
| Use MAG in the small mixing-time regime | Synthetic linear regression with Markovian data · Synthetic linear regression with small mixing time | suboptimality | Hurt |
| Use MAG in the large mixing-time regime | Synthetic linear regression with Markovian data · Synthetic linear regression with large mixing time | suboptimality | Helped |
Closest papers by meaning
- On Markov Chain Gradient Descent (NeurIPS 2018 · similarity 0.91)
- High-probability Convergence of Gradient Methods under Markovian Stochasticity (NeurIPS 2026 · similarity 0.90)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.90)
- Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching (ICML 2025 · similarity 0.88)
- Stochastic Optimization with Arbitrary Recurrent Data Sampling (ICML 2024 · similarity 0.88)
- Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.