mlsanityData to 7 Oct 2026

On Convergence of Incremental Gradient for Non-Convex Smooth Functions

arXiv 2305.19259 ↗First posted 30 May 2023cs.LG math.OC stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

In machine learning and neural network optimization, algorithms like incremental gradient, and shuffle SGD are popular due to minimizing the number of cache misses and good practical convergence behavior. However, their optimization properties in theory, especially for non-convex smooth functions, remain incompletely explored. This paper delves into the convergence properties of SGD algorithms with arbitrary data ordering, within a broad framework for non-convex smooth functions. Our findings show enhanced convergence guarantees for incremental gradient and single shuffle SGD. Particularly if n is the training set size, we improve n times the optimization term of convergence guarantee to reach accuracy varepsilon from O(n / varepsilon) to O(1 / varepsilon).

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 31 of its 59 references that are in the map. First posted on arXiv 30 May 2023.

Builds on

31 of 59 references.

References · 31

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  5. 2014Convex Optimization: Algorithms and Complexitycited by 569
  6. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  7. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  8. 2020On the Convergence of SGD with Biased Gradientscited by 79
  9. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
  10. 2015Perturbed Iterate Analysis for Asynchronous Stochastic Optimizationcited by 67
  11. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  12. 2019How Good is SGD with Random Shuffling?cited by 63
19 more
  1. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 59
  2. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
  3. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  4. 2020Closing the convergence gap of SGD without replacementcited by 56
  5. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 44
  6. 2019Semi-Cyclic Stochastic Gradient Descentcited by 40
  7. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 37
  8. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  9. 2021Proximal and Federated Random Reshufflingcited by 33
  10. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  11. 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 26
  12. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
  13. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 21
  14. 2022GraB: Finding Provably Better Data Permutations than Random Reshufflingcited by 18
  15. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  16. 2021Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problemscited by 16
  17. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 15
  18. 2021Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?cited by 8
  19. 2023Coordinating Distributed Example Orders for Provably Accelerated Trainingcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 2.

7 papers.

  1. 2025Variance Reduction Methods Do Not Need to Compute Full Gradients: Improved Efficiency through Shufflingcited by 2
  2. 2025Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weightingcited by 0
  3. 2025Shuffling Heuristic in Variational Inequalities: Establishing New Convergence Guaranteescited by 0
  4. 2025On the Limits of Momentum in Decentralized and Federated Optimizationcited by 0
  5. 2025First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptionscited by 0
  6. 2026A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithmscited by 0
  7. 2026Robustifying Asynchronous SGD via Soft Throttlingcited by 0