Random Shuffling Beats SGD after Finite Epochs

Abstract

A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-replacement version. We present the first (to our knowledge) non-asymptotic solution to this problem, which shows that after a "reasonable" number of epochs RandomShuffle indeed converges faster than SGD. Specifically, we prove that under strong convexity and second-order smoothness, the sequence generated by RandomShuffle converges to the optimal solution at the rate O(1/T^2 + n^3/T^3), where n is the number of components in the objective, and T is the total number of iterations. This result shows that after a reasonable number of epochs RandomShuffle is strictly better than SGD (which converges as O(1/T)). The key step toward showing this better dependence on T is the introduction of n into the bound; and as our analysis will show, in general a dependence on n is unavoidable without further changes to the algorithm. We show that for sparse data RandomShuffle has the rate O(1/T^2), again strictly better than SGD. Furthermore, we discuss extensions to nonconvex gradient dominated functions, as well as non-strongly convex settings.

References in corpus (9)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• Why Random Reshuffling Beats Stochastic Gradient Descent
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version

Cited by in corpus (3)

• Incremental Methods for Weakly Convex Optimization
• How Good is SGD with Random Shuffling?
• Adaptive Gradient Methods Can Be Provably Faster than SGD after Finite Epochs