Without-Replacement Sampling for Stochastic Gradient Methods

Ohad ShamirNeurIPS 2016 · OpenReview

Introduction

In the landscape of machine learning and convex optimization, Stochastic Gradient Descent (SGD) is the foundational engine powering most model training. However, a persistent gap exists between how SGD is analyzed in theory and how it is deployed in practice. The mathematical "gold standard" for analyzing SGD assumes that at every step, data points are sampled with replacement (independently and uniformly at random). In contrast, real-world implementations almost universally sample without replacement—typically by randomly shuffling the dataset and processing it sequentially.

This paper bridges this fundamental gap, providing rigorous convergence guarantees for without-replacement sampling, particularly in the highly relevant "few-pass" regime.

The Theory-Practice Gap

Practitioners prefer without-replacement sampling for several compelling reasons:

  1. Hardware Efficiency: Sequential memory access is significantly faster and easier to implement than true random sampling.
  2. Empirical Performance: It often converges faster in practice.

Despite these advantages, theoretical justification has historically lagged. Because without-replacement sampling breaks the assumption of independent and identically distributed (i.i.d.) draws, standard convergence proofs fail. Previous theoretical attempts either required an infinite number of passes over the data or demonstrated that without-replacement sampling could perform exponentially worse in specific adversarial scenarios. This paper addresses the mystery of why without-replacement sampling performs so well during the crucial first few passes over a dataset.

A Novel Theoretical Framework

To establish these guarantees, the author combines techniques from three distinct areas of machine learning theory:

  • Adversarial Online Learning: Utilizing the concept of "regret" to measure how much better an algorithm could have performed had it seen the entire data sequence in advance.
  • Transductive Learning Theory: Employing Transductive Rademacher Complexity to quantify how well a random subset (the "prefix" of a shuffled dataset) represents the entire dataset.
  • Stochastic Variance Reduced Gradient (SVRG): Extending the analysis to fast stochastic methods to show they maintain linear convergence without needing continuous reshuffling.

The core technical innovation is a novel lemma that decomposes the suboptimality of without-replacement SGD into two parts: the algorithm's regret and the transductive complexity of the function class. Specifically, it relates the expected difference between the two sampling methods to the difference between the average loss on a prefix of a random permutation versus the remaining suffix.

Key Results and Parity Guarantees

Because this is a theoretical paper, the results are mathematically derived for general convex optimization problems rather than benchmarked on specific empirical datasets. The findings establish that without-replacement sampling is theoretically at least as good as standard SGD:

  • Convex Lipschitz Functions: The method attains an $O(1/\sqrt{T})$ suboptimality bound after $T$ iterations, perfectly matching the standard i.i.d. rate.
  • Strongly Convex & Smooth Functions: It achieves $O(1/\lambda T)$ suboptimality, again matching the standard with-replacement rate up to constant factors.

The Single-Shuffle Advantage in SVRG

For SVRG applied to regularized least squares, the paper proves a remarkable property: the data only needs to be shuffled once at the very beginning. Provided the problem is reasonably well-conditioned (i.e., the condition number is smaller than the dataset size), the algorithm achieves an $\epsilon$-accurate solution in $O(\log(1/\epsilon))$ epochs using only sequential passes, without ever needing to reshuffle between epochs.

Advancing Distributed Optimization

Previous analyses of distributed SVRG required communicating large amounts of data to simulate i.i.d. sampling—a bottleneck known as the distributed "Birthday Paradox." This paper demonstrates that by utilizing without-replacement sampling, individual machines can simply iterate over their local data partitions. This extends the regime where distributed SVRG is communication-efficient from $\lambda = \Omega(1/\sqrt{m})$ to $\lambda = \Omega(1/m)$, marking a significant improvement for large-scale distributed training.

Limitations and Future Directions

While this work provides a crucial theoretical foundation, it leaves a few open questions:

  • "Not Worse" vs. "Better": The proofs primarily establish that without-replacement sampling is not significantly worse than with-replacement sampling. They do not yet fully capture the theoretical reasons for the empirical superiority (faster convergence) often observed in practice.
  • Scope of SVRG Results: The strongest results regarding SVRG and distributed optimization are currently restricted to regularized least squares problems. While the author conjectures these hold for other smooth, strongly convex losses (like logistic regression), formal proofs remain for future work.
  • Logarithmic Factors: Some of the derived bounds contain logarithmic dependencies on the dimension ($d$) or the number of iterations ($T$). These may be artifacts of the proof techniques rather than fundamental mathematical limits.

Ultimately, this paper takes a major step toward aligning the mathematical theory of stochastic optimization with the realities of modern machine learning practice.

Summary updated

Abstract

Stochastic gradient methods for machine learning and optimization problems are usually analyzed assuming data points are sampled <em>with</em> replacement. In contrast, sampling <em>without</em> replacement is far less understood, yet in practice it is very common, often easier to implement, and usually performs better. In this paper, we provide competitive convergence guarantees for without-replacement sampling under several scenarios, focusing on the natural regime of few passes over the data. Moreover, we describe a useful application of these results in the context of distributed optimization with randomly-partitioned data, yielding a nearly-optimal algorithm for regularized least squares (in terms of both communication complexity and runtime complexity) under broad parameter regimes. Our proof techniques combine ideas from stochastic optimization, adversarial online learning and transductive learning theory, and can potentially be applied to other stochastic optimization and learning problems.
BibTeX
@inproceedings{shamir2016without,
  author = {Ohad Shamir},
  title = {{Without-Replacement Sampling for Stochastic Gradient Methods}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=r1NQbwZu-B},
}
Figure