mlsanityData to 7 Oct 2026

A Universally Optimal Multistage Accelerated Stochastic Gradient Method

arXiv 1901.08022 ↗First posted 23 Jan 2019math.OC cs.LG stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

We study the problem of minimizing a strongly convex, smooth function when we have noisy estimates of its gradient. We propose a novel multistage accelerated algorithm that is universally optimal in the sense that it achieves the optimal rate both in the deterministic and stochastic case and operates without knowledge of noise characteristics. The algorithm consists of stages that use a stochastic version of Nesterov's method with a specific restart and parameters selected to achieve the fastest reduction in the bias-variance terms in the convergence rate bounds.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 4; 2023: 4; 2024: 4; 2025: 2.

17 papers.

Sort:

  1. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  2. 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
  3. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  4. 2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learningcited by 10
  5. 2023Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noisecited by 9
  6. 2024An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothnesscited by 9
  7. 2024On the Performance Analysis of Momentum Method: A Frequency Domain Perspectivecited by 8
  8. 2023Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descentcited by 6
  9. 2022Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelizationcited by 4
  10. 2022Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methodscited by 3
  11. 2025On the Effectiveness of the z-Transform Method in Quadratic Optimizationcited by 2
  12. 2022Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysiscited by 1
5 more
  1. 2022Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithmscited by 1
  2. 2025Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Boundscited by 1
  3. 2023Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence and Experimentscited by 0
  4. 2024(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentumcited by 0
  5. 2024New logarithmic step size for stochastic gradient descentcited by 0