Closing the convergence gap of SGD without replacement

By Shashank Rajput, Anant Gupta, Dimitris Papailiopoulos. 2020

75 citations recorded by the source corpus.

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}\right)$ 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}\right)$ 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}\right)$ when the sum of the functions is a quadratic, and offer a new lower bound of $\Omega\left(\frac{n}{T^2}\right)$ for strongly convex functions that are sums of smooth functions.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Permutation-Based SGD: Is Random Optimal? (2021, methodology): “The next theorem shows that FlipFlop improves the convergence rate of Random Reshuffle: Theorem 5.”
A Unified Convergence Analysis for Shuffling-Type Gradient Methods (2020, background): “Another Ω(nT−2) shaper lower bound is recently established in (Rajput et al., 2020) when n > O(T ).”
SGD with shuffling: optimal rates without component convexity and large epoch requirements (2020, methodology): “3 For example, the tight rates on strongly convex F [11] and quadratic F [14] are obtained using coupling arguments showing that each iterate of RANDOMSHUFFLE makes progress on par with SGD, which crucially exploits the convexity of individual fi’s.”
Random Reshuffling: Simple Analysis with Vast Improvements (2020, result): “Our result for SO tightly matches the lower bound of Safran and Shamir (2020). We prove similar results in the more general setting when each fi is convex and f is strongly convex (see Theorem 2), but in this case we are forced to use smaller stepsizes.”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, methodology): “On the other hand, using Lemma 12 of [21] one can show that when choosing the order randomly, Eσ(2) ? ≥ nσ 2 256 .”