Shuffle SGD is Always Better than SGD: Improved Analysis of SGD with Arbitrary Data Orders
Preprint
Abstract
Stochastic Gradient Descent (SGD) algorithms are widely used in optimizing neural networks, with Random Reshuffling (RR) and Single Shuffle (SS) being popular choices for cycling through random or single permutations of the training data. However, the convergence properties of these algorithms in the non-convex case are not fully understood. Existing results suggest that, in realistic training scenarios where the number of epochs is smaller than the training set size, RR may perform worse than SGD. In this paper, we analyze a general SGD algorithm that allows for arbitrary data orderings and show improved convergence rates for non-convex functions. Specifically, our analysis reveals that SGD with random and single shuffling is always faster or at least as good as classical SGD with replacement, regardless of the number of iterations. Overall, our study highlights the benefits of using SGD with random/single shuffling and provides new insights into its convergence properties for non-convex optimization.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- First-order and Stochastic Optimization Methods for Machine Learning2020
- Perturbed Iterate Analysis for Asynchronous Stochastic OptimizationSIAM Journal on Optimization, 2017
- Parallel stochastic gradient algorithms for large-scale matrix completionMathematical Programming Computation, 2013
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic ProgrammingSIAM Journal on Optimization, 2013
- Ergodic mirror descent2011
- An optimal method for stochastic composite optimizationMathematical Programming, 2011
- Pegasos: primal estimated sub-gradient solver for SVMMathematical Programming, 2010
- A Randomized Incremental Subgradient Method for Distributed Optimization in Networked SystemsSIAM Journal on Optimization, 2010
- A class of unconstrained minimization methods for neural network trainingOptimization Methods and Software, 1994
- An Adaptive Associative Memory PrincipleIEEE Transactions on Computers, 1974