Research map / Optimization / Nonconvex and smooth optimization
First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
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 randomized batch sizes with accelerated SGD | Smooth strongly convex minimization with Markovian noise · Strongly convex minimization | oracle complexity: RASGD: $\mathcal{\tilde O} \left( \tau \left[ (1 + \delta^2) \sqrt{\frac{L}{\mu}} \log \frac{\norm{x^0 - x^*}^2}{\vareps | Helped |
| Use randomized batching in non-convex SGD | Smooth non-convex minimization with Markovian noise · Non-convex minimization | oracle complexity: $\mathcal{\tilde O} \left( \tau \cdot \left[\frac{(1 + \delta^2) L (f(x^0) - f^*)}{\varepsilon^2}+ \frac{L(f(x^0) - f^*) | Helped |
| Use randomized ExtraGradient under Markovian noise | Variational inequalities · Monotone variational inequalities | oracle complexity: $\mathcal{\tilde O} \left( \tau \left[ \frac{LD^2}{\varepsilon} + \frac{\sigma^2D^2+\Delta^2D^4}{\varepsilon^2}\right] \ | Helped |
| Include randomized batching to reduce gradient-estimate bias | RASGD and randomized ExtraGradient · Markovian-noise optimization and variational inequalities | oracle complexity dependence on mixing time: bias scaling as $M^{-2}$; expected oracle calls $\mathcal{O}(B\log_2(M))$ | Helped |
Closest papers by meaning
- 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.91)
- High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise (ICML 2024 · similarity 0.90)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.90)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
- Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching (ICML 2025 · 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.