mlsanityData to 7 Oct 2026

Ordering for Non-Replacement SGD

arXiv 2306.15848 ↗First posted 28 Jun 2023cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

One approach for reducing run time and improving efficiency of machine learning is to reduce the convergence rate of the optimization algorithm used. Shuffling is an algorithm technique that is widely used in machine learning, but it only started to gain attention theoretically in recent years. With different convergence rates developed for random shuffling and incremental gradient descent, we seek to find an ordering that can improve the convergence rates for the non-replacement form of the algorithm. Based on existing bounds of the distance between the optimal and current iterate, we derive an upper bound that is dependent on the gradients at the beginning of the epoch. Through analysis of the bound, we are able to develop optimal orderings for constant and decreasing step sizes for strongly convex and convex functions. We further test and verify our results through experiments on synthesis and real data sets. In addition, we are able to combine the ordering with mini-batch and further apply it to more complex neural networks, which show promising results.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 40 of its 117 references that are in the map. First posted on arXiv 28 Jun 2023.

Builds on

40 of 117 references.

References · 40

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  3. 2016Layer Normalizationcited by 5,579
  4. 2019Energy and Policy Considerations for Deep Learning in NLPcited by 1,242
  5. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  6. 2018Not All Samples Are Created Equal: Deep Learning with Importance Samplingcited by 323
  7. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  8. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  9. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  10. 2014Lazier Than Lazy Greedycited by 97
  11. 2015Variance Reduction in SGD by Distributed Importance Samplingcited by 79
  12. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
28 more
  1. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
  2. 2018Bayesian Coreset Construction via Greedy Iterative Geodesic Ascentcited by 68
  3. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  4. 2019How Good is SGD with Random Shuffling?cited by 63
  5. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
  6. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  7. 2020Closing the convergence gap of SGD without replacementcited by 56
  8. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  9. 2019Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimizationcited by 51
  10. 2018On the Ineffectiveness of Variance Reduced Optimization for Deep Learningcited by 48
  11. 2015Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Samplingcited by 46
  12. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 44
  13. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  14. 2017Training Gaussian Mixture Models at Scale via Coresetscited by 38
  15. 2013Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regressioncited by 32
  16. 2019The importance of better models in stochastic optimizationcited by 32
  17. 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 26
  18. 2020Choosing the Sample with Lowest Loss makes SGD Robustcited by 26
  19. 2015On the Convergence Rate of Incremental Aggregated Gradient Algorithmscited by 21
  20. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  21. 2017Safe Adaptive Importance Samplingcited by 19
  22. 2021Permutation-Based SGD: Is Random Optimal?cited by 16
  23. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 15
  24. 2013Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methodscited by 9
  25. 2016Exploiting the Structure: Stochastic Gradient Methods Using Raw Clusterscited by 6
  26. 2014A globally convergent incremental Newton methodcited by 5
  27. 2016Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimizationcited by 4
  28. 2013MLI: An API for Distributed Machine Learningcited by 3

Built on by

Not cited yet.