Stochastic Learning under Random Reshuffling with Constant Step-sizes

Abstract

In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate of the learning process under diminishing step-sizes. This work focuses on the constant step-size case and strongly convex loss function. In this case, convergence is guaranteed to a small neighborhood of the optimizer albeit at a linear rate. The analysis establishes analytically that random reshuffling outperforms uniform sampling by showing explicitly that iterates approach a smaller neighborhood of size $O({\mu }^2)$ around the minimizer rather than $O(\mu )$. Furthermore, we derive an analytical expression for the steady-state mean-square-error performance of the algorithm, which helps clarify in greater detail the differences between sampling with and without replacement. We also explain the periodic behavior that is observed in random reshuffling implementations.

References in corpus (8)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Speeding Up Distributed Machine Learning Using Codes
• Why Random Reshuffling Beats Stochastic Gradient Descent
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Convergence Rate of Incremental Gradient and Newton Methods
• Variance-Reduced Stochastic Learning under Random Reshuffling
• A note on the non-commutative arithmetic-geometric mean inequality

Cited by in corpus (14)

• Supervised Learning Under Distributed Features
• Random Reshuffling: Simple Analysis with Vast Improvements
• On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• 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
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Random-reshuffled SARAH does not need a full gradient computations
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• On the Saturation Phenomenon of Stochastic Gradient Descent for Linear Inverse Problems
• Painless step size adaptation for SGD