Why Random Reshuffling Beats Stochastic Gradient Descent

Abstract

We analyze the convergence rate of the random reshuffling (RR) method, which is a randomized first-order incremental algorithm for minimizing a finite sum of convex component functions. RR proceeds in cycles, picking a uniformly random order (permutation) and processing the component functions one at a time according to this order, i.e., at each cycle, each component function is sampled without replacement from the collection. Though RR has been numerically observed to outperform its with-replacement counterpart stochastic gradient descent (SGD), characterization of its convergence rate has been a long standing open question. In this paper, we answer this question by showing that when the component functions are quadratics or smooth and the sum function is strongly convex, RR with iterate averaging and a diminishing stepsize ${\alpha }_k=\Theta (1/k^s)$ for $s\in (1/2,1)$ converges at rate $\Theta (1/k^{2s})$ with probability one in the suboptimality of the objective value, thus improving upon the $\Omega (1/k)$ rate of SGD. Our analysis draws on the theory of Polyak-Ruppert averaging and relies on decoupling the dependent cycle gradient error into an independent term over cycles and another term dominated by ${\alpha }_k^2$. This allows us to apply law of large numbers to an appropriately weighted version of the cycle gradient errors, where the weights depend on the stepsize. We also provide high probability convergence rate estimates that shows decay rate of different terms and allows us to propose a modification of RR with convergence rate $\mathcal{O}(\frac{1}{k^2})$.

References in corpus (8)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
• Stop Wasting My Gradients: Practical SVRG
• Convergence Rate of Incremental Gradient and Newton Methods
• A note on the non-commutative arithmetic-geometric mean inequality

Cited by in corpus (47)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Speeding Up Distributed Machine Learning Using Codes
• Differentially Private Model Publishing for Deep Learning
• Review: Deep Learning in Electron Microscopy
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• FairBatch: Batch Selection for Model Fairness
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• A Unified Convergence Analysis for Shuffling-Type Gradient Methods
• Incremental Methods for Weakly Convex Optimization
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Variance-Reduced Stochastic Learning under Random Reshuffling
• SGD without Replacement: Sharper Rates for General Smooth Convex Functions
• Random Shuffling Beats SGD after Finite Epochs
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Effective Model Sparsification by Scheduled Grow-and-Prune Methods
• How Good is SGD with Random Shuffling?
• Incremental Without Replacement Sampling in Nonconvex Optimization
• Membership Inference Attacks Against Object Detection Models
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Convergence of Online Adaptive and Recurrent Optimization Algorithms
• Decentralized Differentially Private Without-Replacement Stochastic Gradient Descent
• Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models
• Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
• Reducing Runtime by Recycling Samples
• Graph Drawing by Stochastic Gradient Descent
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• E2-Train: Training State-of-the-art CNNs with Over 80% Energy Savings
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Debiasing Stochastic Gradient Descent to handle missing values
• On Tight Convergence Rates of Without-replacement SGD
• Convergence of Random Reshuffling Under The Kurdyka-Łojasiewicz Inequality
• Permutation-Based SGD: Is Random Optimal?
• Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization
• Anti-Correlated Noise in Epoch-Based Stochastic Gradient Descent: Implications for Weight Variances in Flat Directions
• Sequenced-Replacement Sampling for Deep Learning
• Parallel Momentum Methods Under Biased Gradient Estimations
• Multifunction Cognitive Radar Task Scheduling Using Monte Carlo Tree Search and Policy Networks
• Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems
• Optimal Rates for Random Order Online Optimization
• Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity