Abstract
Stochastic gradient descent without replacement sampling is widely used in practice for model training. However, the vast majority of SGD analyses assumes data is sampled with replacement, and when the function minimized is strongly convex, an $\mathcal{O}\left(\frac{1}{T}\right)$ rate can be established when SGD is run for $T$ iterations. A recent line of breakthrough works on SGD without replacement (SGDo) established an $\mathcal{O}\left(\frac{n}{T^2}\right)$ convergence rate when the function minimized is strongly convex and is a sum of $n$ smooth functions, and an $\mathcal{O}\left(\frac{1}{T^2}+\frac{n^3}{T^3} ight)$ rate for sums of quadratics. On the other hand, the tightest known lower bound postulates an $\Omega\left(\frac{1}{T^2}+\frac{n^2}{T^3} ight)$ rate, leaving open the possibility of better SGDo convergence rates in the general case. In this paper, we close this gap and show that SGD without replacement achieves a rate of $\mathcal{O}\left(\frac{1}{T^2}+\frac{n^2}{T^3} ight)$ when the sum of the functions is a quadratic, and offer a new lower bound of $\Omega\left(\frac{n}{T^2} ight)$ for strongly convex functions that are sums of smooth functions.
Introduction
Stochastic Gradient Descent without replacement (SGDo), often referred to as Random Reshuffling, is the default algorithm for training machine learning models. Despite its empirical success, theoretical analysis has historically lagged behind, often relying on the simpler "with replacement" assumption to ensure unbiased gradient estimators. Recent research has shown that SGDo can actually outperform standard SGD, but significant gaps remained between the best-known upper and lower convergence bounds.
The Convergence Gap
Prior to this work, a discrepancy existed in the convergence rates for two primary classes of functions:
- Quadratics: The upper bound was $\mathcal{O}(1/T^2 + n^3/T^3)$, while the lower bound was $\Omega(1/T^2 + n^2/T^3)$.
- General Smooth, Strongly Convex Functions: The upper bound was $\mathcal{O}(n/T^2)$, but the lower bound was only $\Omega(1/T^2 + n^2/T^3)$.
This paper resolves these inconsistencies, providing tight bounds for both scenarios.
Methodology
The authors employed two distinct strategies to close these gaps. To tighten the upper bound for quadratics, they utilized iterate coupling. This technique avoids complex distance metrics by directly bounding the divergence of iterates when two data points in an epoch's permutation are swapped. This approach leverages the constant-Hessian property of quadratics to simplify the analysis of without-replacement sampling.
To raise the lower bound for general smooth functions, the authors constructed a worst-case 1D piecewise quadratic function. While smooth and strongly convex, this function is not globally quadratic. Through combinatorial probability, they demonstrated that the linear components of this function cause iterates to drift away from the optimum during an epoch, fundamentally limiting the convergence speed to $\Omega(n/T^2)$.
Key Results
The primary contribution of this work is the establishment of optimal convergence rates:
- Optimal Rate for Quadratics: An upper bound of $\tilde{\mathcal{O}}(1/T^2 + n^2/T^3)$ was proven, matching the existing lower bound.
- Optimal Rate for General Smooth Functions: A new lower bound of $\Omega(n/T^2)$ was established, matching the existing upper bound.
These results clarify that the optimal speed of SGDo is fundamentally tied to the function class: quadratics allow for faster convergence ($\approx n^2/T^3$) compared to general smooth functions ($\approx n/T^2$).
Conclusion
This paper successfully closes the convergence gap for SGD without replacement by providing tight upper and lower bounds. These findings suggest that the function class dictates the theoretical speed limit of Random Reshuffling. Future work may focus on optimizing the dependence on the condition number and extending the theory to explain the success of infrequent reshuffling in deep learning practice.
Summary updated