mlsanityData to 14 Oct 2026

On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms

arXiv 2206.05869 ↗First posted 13 Jun 2022cs.LG math.OCcited by 2

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent (SGD) algorithm is the method of choice in many machine learning tasks thanks to its scalability and efficiency in dealing with large-scale problems. In this paper, we focus on the shuffling version of SGD which matches the mainstream practical heuristics. We show the convergence to a global solution of shuffling SGD for a class of non-convex functions under over-parameterized settings. Our analysis employs more relaxed non-convex assumptions than previous literature. Nevertheless, we maintain the desired computational complexity as shuffling SGD has achieved in the general convex setting.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 43 of its 65 references that are in the map. First posted on arXiv 13 Jun 2022.

Builds on

43 of 65 references.

References · 43

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  4. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  6. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  7. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  8. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
  9. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
  10. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  11. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  12. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
31 more
  1. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  2. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  3. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  4. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
  5. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  6. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 121
  7. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  8. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 95
  9. 2013Multi-digit Number Recognition from Street View Imagery using Deep Convolutional Neural Networkscited by 84
  10. 2014Convolutional Neural Networks at Constrained Time Costcited by 81
  11. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 79
  12. 2016Gradient Descent Learns Linear Dynamical Systemscited by 79
  13. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  14. 2018Random Shuffling Beats SGD after Finite Epochscited by 67
  15. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
  16. 2019How Good is SGD with Random Shuffling?cited by 64
  17. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
  18. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  19. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  20. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  21. 2019The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descentcited by 46
  22. 2019SGD Converges to Global Minimum in Deep Learning via Star-convex Pathcited by 39
  23. 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
  24. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  25. 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
  26. 2019Fast and Furious Convergence: Stochastic Second Order Methods under Interpolationcited by 18
  27. 2022Nesterov Accelerated Shuffling Gradient Method for Convex Optimizationcited by 10
  28. 2015Optimizing Star-Convex Functionscited by 9
  29. 2020On The Convergence of First Order Methods for Quasar-Convex Optimizationcited by 8
  30. 2021Random-reshuffled SARAH does not need a full gradient computationscited by 7
  31. 2022Finite-Sum Optimization: A New Perspective for Convergence to a Global Solutioncited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 1.

2 papers.

  1. 2026Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimizationcited by 2
  2. 2024Shuffling Momentum Gradient Algorithm for Convex Optimizationcited by 1