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

Kwangjun Ahn, Chulhee Yun, Suvrit Sra

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.

Introduction: The Theory-Practice Gap in SGD

In modern machine learning, Stochastic Gradient Descent (SGD) is the standard optimization method. However, a significant gap exists between theoretical analysis and practical implementation. While most textbooks analyze SGD using independent and identically distributed (i.i.d.) sampling (with replacement), practitioners almost exclusively use shuffling (sampling without replacement).

Shuffling is empirically faster, but theoretically challenging. Because data points are not replaced, the samples within an epoch are dependent, making the "shuffling gradient" a biased estimate of the true gradient. This paper by Ahn, Yun, and Sra provides a theoretical breakthrough, establishing optimal convergence rates for shuffling SGD under realistic conditions.

Overcoming Theoretical Hurdles

Previous attempts to prove the superiority of shuffling SGD (specifically the $O(1/K^2)$ rate, where $K$ is the number of epochs) suffered from two major limitations:

  1. Component Convexity: Prior work often assumed every individual data point's loss function ($f_i$) was convex. This is rarely the case in deep learning.
  2. Large Epoch Requirements: Many results only held if the number of epochs $K$ was extremely large (e.g., $K \ge \kappa^2$, where $\kappa$ is the condition number), which is impractical for many real-world training schedules.

The authors address these issues using a combination of advanced mathematical tools:

  • Hoeffding-Serfling Inequality: A vector-valued version is used to bound the noise from without-replacement sampling, showing that aggregate epoch updates approximate the full gradient even without individual component convexity.
  • Varying Step Sizes: By employing a specific schedule of decreasing step sizes, the authors remove the "burn-in" period or large epoch requirement.
  • Refined Convergence Analysis: A new variant of Chung’s Lemma was developed to handle the simultaneous scaling of $n$ (data points) and $K$ (epochs).

Convergence Results

The paper establishes minimax optimal convergence rates for both RandomShuffle and SingleShuffle. A key insight is that for smooth strongly convex costs, shuffling only once at the start (SingleShuffle) is theoretically as powerful as shuffling every epoch (RandomShuffle).

Table 1: Comparison of convergence rates for RandomShuffle across different function classes and assumptions.

As shown in Table 1, the authors achieve several "tight" bounds that match known lower bounds (LB):

  • PŁ and Strongly Convex Functions: The rate is improved to $\tilde{O}(\frac{1}{nK^2})$, with the epoch requirement reduced from $K \gtrsim \kappa^2$ to $K \gtrsim \kappa$.
  • Quadratic Functions: The rate matches the best-known lower bounds at $\tilde{O}(\frac{1}{(nK)^2} + \frac{1}{nK^3})$.
  • Removing Log Factors: By assuming component convexity and using varying step sizes, the authors achieve the exact $O(1/nK^2)$ rate for any $K \ge 1$, closing the poly-log gap.

Limitations and Future Work

While this work significantly advances the theory of shuffling SGD, some open questions remain. The analysis relies on the assumption that iterates stay within a bounded set (Assumption 1). Additionally, while the PŁ condition covers some non-convex landscapes, the technique for removing the epoch requirement still relies on individual component convexity. Extending these "no-requirement" results to fully non-convex components remains a challenge 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