SGD with shuffling: optimal rates without component convexity and large epoch requirements

Kwangjun Ahn, Chulhee Yun, Suvrit Sra

Introduction

In machine learning, optimization almost always involves solving "finite-sum" problems, where the goal is to minimize an average loss over $n$ data points. Standard Stochastic Gradient Descent (SGD) theoretically picks a random data point with replacement at every step. However, in practice, this is rarely done. Instead, practitioners use RandomShuffle (shuffling the dataset at the start of every epoch) or SingleShuffle (shuffling once at the very beginning).

While shuffling empirically outperforms standard SGD, it is notoriously difficult to analyze mathematically. Because samples within an epoch depend on previously drawn samples, the gradients become "biased." Previous theoretical frameworks attempting to explain shuffling's superiority suffered from two major limitations:

  1. The Convexity Crutch: They assumed every individual component function ($f_i$) was convex—a rarity in deep learning.
  2. The "Wait Forever" Requirement: They suggested shuffling only outperforms standard SGD after a massive number of epochs (often proportional to the square of the condition number, $\kappa^2$).

This paper provides a tight theoretical foundation proving why without-replacement SGD is mathematically superior, establishing optimal convergence rates that match lower bounds and demonstrating that these benefits kick in much earlier than previously thought.

Methodological Innovations

To bridge the gap between theory and practice, the authors introduce several novel mathematical strategies:

  • Hoeffding-Serfling Concentration: To handle the bias introduced by sampling without replacement, the authors utilize a vector-valued version of the Hoeffding-Serfling inequality. This bounds the "noise" of shuffled gradients without requiring individual functions to be convex.
  • Varying Step Sizes: By moving away from the standard constant step size analysis and introducing a specific schedule of varying step sizes, the authors completely remove the "large epoch" requirement for certain function classes.
  • Matrix Analysis for Quadratics: The authors perform a fine-grained analysis of the expectation of random permutations to prove tight bounds for quadratic functions without assuming individual convexity. This cleverly bypasses the "matrix AM-GM inequality," a famous conjecture recently proven false.
  • Modified Chung’s Lemma: A new version of a classical technical tool (Chung’s Lemma) was developed to handle convergence rates dependent on both the number of data points ($n$) and the number of epochs ($K$).

Key Insights and Convergence Results

The core insight of this work is that component convexity isn't mandatory. The global property of the total loss function (such as being "gradient dominated" or satisfying the Polyak-Łojasiewicz (PŁ) condition) matters far more than the properties of individual data points. Optimal shuffling rates are achievable even if individual $f_i$ components are highly non-convex.

Furthermore, the paper reinforces the theoretical speedup of shuffling: while standard SGD converges at a rate of $O(1/nK)$, shuffling-based methods converge at $O(1/nK^2)$ (ignoring log factors). As the number of epochs ($K$) increases, shuffling becomes significantly faster.

Convergence rates for RandomShuffle compared to prior work

By refining the analysis, the authors achieved several state-of-the-art bounds:

  • For PŁ Functions (Non-convex but well-behaved): They achieved a rate of $O(\frac{\log^3(nK)}{nK^2})$ requiring only that the number of epochs $K$ is at least proportional to the condition number $\kappa$ ($K \gtrsim \kappa$). This is a massive improvement over previous requirements of $K \gtrsim \kappa^2$.
  • For Strongly Convex Functions: Assuming individual components are convex and using varying step sizes, they achieved a rate of $O(\frac{1}{nK^2})$ for any $K \ge 1$. This effectively closes the poly-logarithmic gap between upper and lower bounds found in previous literature and proves that shuffling helps from the very first epoch.
  • Quadratic Functions: They proved a tight bound of $O(\frac{1}{(nK)^2} + \frac{1}{nK^3})$ without requiring individual components to be convex, perfectly matching known lower bounds.

Limitations and Future Work

While this paper makes significant theoretical strides, a few open challenges remain:

  • The Hessian Gap: A small gap persists between the best-known lower and upper bounds for functions with a "Lipschitz Hessian" (where curvature doesn't change too abruptly).
  • Varying Step Sizes vs. Convexity: Although the "large epoch" requirement was removed for strongly convex functions, the proof still relies on individual component functions being convex. Removing this epoch requirement for non-convex components remains an open problem.
  • Beyond Last-Iterate: Some results apply to the "best iterate" found during training rather than the final one. Proving these bounds strictly for the last iterate across all cases is a target for future research.

Summary updated

Abstract

We study without-replacement SGD for solving finite-sum optimization problems. Specifically, depending on how the indices of the finite-sum are shuffled, we consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) algorithms. First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors. Notably, our analysis is general enough to cover gradient dominated nonconvex costs, and does not rely on the convexity of individual component functions unlike existing optimal convergence results. Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.
BibTeX
@inproceedings{ahn2020sgd,
  author = {Kwangjun Ahn and Chulhee Yun and Suvrit Sra},
  title = {{SGD with shuffling: optimal rates without component convexity and large epoch requirements}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=blYSQCnfztH},
}
Figure