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 (4)

• 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
• Stop Wasting My Gradients: Practical SVRG
• Convergence Rate of Incremental Gradient and Newton Methods

Cited by in corpus (46)

• 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
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling
• On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning
• Variance-Reduced Stochastic Learning under Random Reshuffling
• SGD without Replacement: Sharper Rates for General Smooth Convex Functions
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Random Shuffling Beats SGD after Finite Epochs
• 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
• Dimension-Free Iteration Complexity of Finite Sum Optimization Problems
• Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models
• Decentralized Differentially Private Without-Replacement Stochastic Gradient Descent
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Reducing Runtime by Recycling Samples
• Convergence of Online Adaptive and Recurrent Optimization Algorithms
• Permutation-Based SGD: Is Random Optimal?
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Convergence of Random Reshuffling Under The Kurdyka-Łojasiewicz Inequality
• Debiasing Stochastic Gradient Descent to handle missing values
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• Graph Drawing by Stochastic Gradient Descent
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• On Tight Convergence Rates of Without-replacement SGD
• E2-Train: Training State-of-the-art CNNs with Over 80% Energy Savings
• Optimal Rates for Random Order Online Optimization
• Anti-Correlated Noise in Epoch-Based Stochastic Gradient Descent: Implications for Weight Variances in Flat Directions
• Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization
• Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity
• Sequenced-Replacement Sampling for Deep Learning
• Parallel Momentum Methods Under Biased Gradient Estimations
• Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems
• Multifunction Cognitive Radar Task Scheduling Using Monte Carlo Tree Search and Policy Networks