# Ordering for Non-Replacement SGD

arXiv: https://arxiv.org/abs/2306.15848 · HTML: https://mlsanity.com/paper/2306.15848/

## Key facts

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

## Builds on (most cited first, 30 of 40)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Energy and Policy Considerations for Deep Learning in NLP](https://mlsanity.com/paper/1906.02243/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Variance Reduction in SGD by Distributed Importance Sampling](https://mlsanity.com/paper/1511.06481/) (2015)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent](https://mlsanity.com/paper/1802.01737/) (2018)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization](https://mlsanity.com/paper/1907.04371/) (2019)
- [On the Ineffectiveness of Variance Reduced Optimization for Deep Learning](https://mlsanity.com/paper/1812.04529/) (2018)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey](https://mlsanity.com/paper/1507.01030/) (2015)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [The importance of better models in stochastic optimization](https://mlsanity.com/paper/1903.08619/) (2019)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [Choosing the Sample with Lowest Loss makes SGD Robust](https://mlsanity.com/paper/2001.03316/) (2020)

## 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.