mlsanityData to 7 Oct 2026

Nesterov Accelerated Shuffling Gradient Method for Convex Optimization

arXiv 2202.03525 ↗First posted 7 Feb 2022math.OC cs.LG stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose Nesterov Accelerated Shuffling Gradient (NASG), a new algorithm for the convex finite-sum minimization problems. Our method integrates the traditional Nesterov's acceleration momentum with different shuffling sampling schemes. We show that our algorithm has an improved rate of O(1/T) using unified shuffling schemes, where T is the number of epochs. This rate is better than that of any other shuffling gradient methods in convex regime. Our convergence analysis does not require an assumption on bounded domain or a bounded gradient condition. For randomized shuffling schemes, we improve the convergence bound further. When employing some initial condition, we show that our method converges faster near the small neighborhood of the solution. Numerical simulations demonstrate the efficiency of our algorithm.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 24 of its 57 references that are in the map. First posted on arXiv 7 Feb 2022.

Builds on

24 of 57 references.

References · 24

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  6. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  7. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  8. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  9. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  10. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  11. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 94
  12. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
12 more
  1. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  2. 2019How Good is SGD with Random Shuffling?cited by 63
  3. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 59
  4. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
  5. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  6. 2020Closing the convergence gap of SGD without replacementcited by 56
  7. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  8. 2021Proximal and Federated Random Reshufflingcited by 33
  9. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  10. 2016On the Influence of Momentum Acceleration on Online Learningcited by 23
  11. 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
  12. 2018Accelerating SGD with momentum for over-parameterized learningcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 3; 2025: 2; 2026: 1.

10 papers.

  1. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 21
  2. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  3. 2023Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Boundscited by 6
  4. 2023High Probability Guarantees for Random Reshufflingcited by 5
  5. 2022On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithmscited by 2
  6. 2024Shuffling Momentum Gradient Algorithm for Convex Optimizationcited by 1
  7. 2025Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Boundscited by 1
  8. 2026Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimizationcited by 1
  9. 2024Adaptive Gradient Regularization: A Faster and Generalizable Optimization Technique for Deep Neural Networkscited by 0
  10. 2025Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weightingcited by 0