Random Reshuffling: Simple Analysis with Vast Improvements

Abstract

Random Reshuffling (RR) is an algorithm for minimizing finite-sum functions that utilizes iterative gradient descent steps in conjunction with data reshuffling. Often contrasted with its sibling Stochastic Gradient Descent (SGD), RR is usually faster in practice and enjoys significant popularity in convex and non-convex optimization. The convergence rate of RR has attracted substantial attention recently and, for strongly convex and smooth functions, it was shown to converge faster than SGD if 1) the stepsize is small, 2) the gradients are bounded, and 3) the number of epochs is large. We remove these 3 assumptions, improve the dependence on the condition number from ${\kappa }^2$ to $\kappa$ (resp. from $\kappa$ to $\sqrt{\kappa }$) and, in addition, show that RR has a different type of variance. We argue through theory and experiments that the new variance type gives an additional justification of the superior performance of RR. To go beyond strong convexity, we present several results for non-strongly convex and non-convex objectives. We show that in all cases, our theory improves upon existing literature. Finally, we prove fast convergence of the Shuffle-Once (SO) algorithm, which shuffles the data only once, at the beginning of the optimization process. Our theory for strongly-convex objectives tightly matches the known lower bounds for both RR and SO and substantiates the common practical heuristic of shuffling once or only a few times. As a byproduct of our analysis, we also get new results for the Incremental Gradient algorithm (IG), which does not shuffle the data at all.

arXiv commentv3 updates: Theorem 4 includes a new result for Polyak-Lojasiewicz functions. NeurIPS 2020. 35 pages, 2 figures, 2 tables, 3 algorithms

References in corpus (14)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Optimization for deep learning: theory and algorithms
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Better Theory for SGD in the Nonconvex World
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• Incremental Methods for Weakly Convex Optimization
• Adaptive Gradient Descent without Descent
• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• SGD with shuffling: optimal rates without component convexity and large epoch requirements
• Recht-Ré Noncommutative Arithmetic-Geometric Mean Conjecture is False
• On Tight Convergence Rates of Without-replacement SGD

Cited by in corpus (15)

• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• On The Impact of Machine Learning Randomness on Group Fairness
• SGD with shuffling: optimal rates without component convexity and large epoch requirements
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Proximal and Federated Random Reshuffling
• Incremental Without Replacement Sampling in Nonconvex Optimization
• SMG: A Shuffling Gradient-Based Method with Momentum
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?
• Parallel and Distributed algorithms for ML problems
• Permutation-Based SGD: Is Random Optimal?
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Random-reshuffled SARAH does not need a full gradient computations
• Convergence of Random Reshuffling Under The Kurdyka-Łojasiewicz Inequality