Research map / Optimization / Nonconvex and smooth optimization
Stochastic Gradient Descent under Markovian Sampling Schemes
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 MC-SAG variance reduction with time-adaptive stepsizes instead of MC-SGD | Markov-chain sampled smooth non-convex optimization · Finite-state Markov sampling | minimum expected squared gradient norm convergence rate: MC-SGD: \Tilde\mathcal O\left(\frac{\Delta L\tau_{\rm mix}}{T}+\frac{\sqrt{L\Delta\bar\sigma^2\tau_{\rm mix}}+\bar\sigma | Helped |
| Use MC-SAG rather than the compared gossip-based decentralized methods | Decentralized optimization · Communication complexity | communications to reach an ε-stationary point: \varepsilon^{-1}\tau_{\rm hit} versus \varepsilon^{-1}|\mathcal{E}|\tau_{\rm mix} and \varepsilon^{-1}n\tau_{\rm mix}^2 | Helped |
| Use all sampled gradients along the Markov-chain trajectory instead of waiting for mixing before each update | Variance-reduced decentralized optimization · Cases where τ_hit = o(n τ_mix) | convergence rate: \tau_{\rm hit}/T versus n\tau_{\rm mix}/T | Helped |
| Add local gradient noise | MC-SGD · Markov sampling with local noise | expected squared distance to optimum: \Tilde\mathcal O\left(\frac{L}{\mu^3T}\big(\sigma_{\rm local}^2+\tau_{\rm mix}\big(\frac{1}{4}\big)\sigma_\star^2 \big)\ | No clear effect |
| Assume interpolation so every local gradient vanishes at the shared optimum | MC-SGD · Strongly convex Markov sampling | expected squared distance to optimum: 2(1-\gamma\mu)^T\NRM{\xx_0-\xx^\star}^2 | Helped |
Closest papers by meaning
- On Markov Chain Gradient Descent (NeurIPS 2018 · similarity 0.93)
- High-probability Convergence of Gradient Methods under Markovian Stochasticity (NeurIPS 2026 · similarity 0.93)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.92)
- Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks (ICLR 2024 · similarity 0.91)
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.89)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
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.