Beyond the Single Pass Assumption in Stochastic Gradient Descent

50 concepts37 papers1 proposal

To analyze Stochastic Gradient Descent (SGD), machine learning theory traditionally relies on a powerful simplifying assumption: the single-pass (or online) regime. In this setting, the optimization algorithm streams through an infinite supply of data, encountering each sample exactly once.

Why is this assumption so popular? It preserves a crucial mathematical property: statistical independence. If every sample is fresh, the current state of the model's weights is completely independent of the next data point. This allows researchers to model gradient steps as unbiased estimators of the true population gradient, making convergence proofs elegant and tractable.

However, as noted in Generalization Properties and Implicit Regularization for Multiple Passes SGM and Optimal Learning for Multi-pass Stochastic Gradient Methods by Junhong Lin et al., this creates a massive chasm between theory and practice. In real-world deep learning, datasets are finite. We do not stream fresh data infinitely; instead, we cycle through a fixed dataset for dozens or hundreds of epochs.

Why Data Reuse Breaks Traditional Theory

When an algorithm transitions from a single pass to multiple passes, the mathematical machinery of online learning breaks down. The moment the optimizer completes its first epoch and begins a second, independence is lost. The model's weights have already been influenced by every single data point in the training set.

This loss of independence introduces severe temporal correlations, a challenge highlighted in From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks by Luca Arnaboldi et al. and Learning Dynamics in Linear VAE: Posterior Collapse Threshold, Superfluous Latent Space Pitfalls, and Speedup with KL Annealing by Yuma Ichikawa et al. Instead of acting as independent random variables, the recycled data points interact with a model state that already "remembers" them.

As Elizabeth Collins–Woodfin demonstrates in High-dimensional limit of one-pass SGD on least squares, the very nature of stochastic noise changes. In a single pass, noise behaves like true external variance; in multiple passes, it becomes highly correlated, altering the optimization trajectory in ways that standard high-dimensional analysis fails to capture. To bypass these analytical hurdles, theoretical frameworks like the one proposed in Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles by Kevin Scaman et al. often restrict their oracles to single-use data.

The Superpowers of Multi-Pass Training

If data reuse introduces such chaotic dependencies, why do practitioners do it? It turns out that multiple passes do not merely compensate for slow convergence; they fundamentally alter what a model can learn.

Implicit Regularization via Epoch Counting

In least-squares learning, running multiple passes over a dataset can actually serve as an implicit regularizer. In Optimal Learning for Multi-pass Stochastic Gradient Methods, Junhong Lin et al. demonstrated that the number of passes acts analogously to a regularization parameter (like the penalty in Ridge Regression). When paired with early stopping, multi-pass SGD achieves minimax optimal statistical accuracy without requiring explicit $L_2$ penalties.

Bypassing Information-Theoretic Limits

Perhaps the most striking benefit of multi-pass training is its ability to learn complex features that are completely invisible to single-pass algorithms. In high-dimensional settings, certain target functions possess a high "leap exponent"—meaning they require an impractical number of samples to learn via standard one-pass feature learning.

However, the authors of The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents (Yatin Dandi et al.) and Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions (Luca Arnaboldi et al.) showed that reusing data batches breaks this curse. By repeatedly exposing the network to the same samples, the optimization process can extract refined geometric information, allowing two-layer neural networks to learn hard multi-index functions with significantly fewer samples than single-pass methods would require.

Pushing Past the Single-Pass Error Floor

When datasets are small relative to a model's capacity, single-pass optimization quickly hits a performance plateau. In Improved Scaling Laws in Linear Regression via Data Reuse, Licong Lin et al. proved that multi-pass SGD, combined with a geometrically decaying step size, can surpass the theoretical error floor of single-pass training. Iterating over the same data effectively makes old samples act as "fresh" information up to a certain computational threshold, optimizing the trade-off between bias and variance. This multi-epoch advantage allows the algorithm to achieve a suboptimality rate that scales with the total number of epochs, as analyzed in SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs by Ayush Sekhari et al.

The Dark Side: Overfitting and Fragility

While data reuse grants optimization superpowers, it also introduces substantial risks that the single-pass assumption conveniently hides: memorization and rapid overfitting.

In the online regime, over-parameterization can sometimes appear detrimental because extra hidden units collect noise. In contrast, when training on finite datasets over multiple epochs, these extra units help the network denoise predictions and align features, though they simultaneously increase the risk of memorizing label noise, as shown in Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup and Generalisation dynamics of online learning in over-parameterised neural networks by Sebastian Goldt et al.

The most dramatic illustration of this risk comes from Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization by Shira Vansover-Hager et al. They showed that while a single pass of SGD is minimax optimal for non-smooth stochastic convex optimization, performing just a second pass over the training data can cause the population loss to instantly jump from near-zero to a large constant value.

Single-Pass SGD:  [Data Point 1] ──> [Data Point 2] ──> [Data Point 3]  (Weights remain independent of future data)

Multi-Pass SGD:   [Data Point 1] ──> [Data Point 2] ──> [Data Point 1*] (Weights are now correlated with Data Point 1)
                                                        └─ Overfitting Risk / Feature Learning Superpower

This reveals that the theoretical optimality of single-pass SGD is incredibly fragile. Reusing data can trigger catastrophic overfitting in scenarios where an online model would remain perfectly stable, highlighting why closing the one-pass theory gap remains one of the most critical frontiers in machine learning theory.

Key Foundational Work

Optimal Learning for Multi-pass Stochastic Gradient Methods (2016) — contributed 2 concept elements to this direction.
Generalization Properties and Implicit Regularization for Multiple Passes SGM (2016) — contributed 1 concept elements to this direction.
Online Passive-Aggressive Algorithms for Non-Negative Matrix Factorization and Completion (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_single_pass_training_assumption_03a8361a,
  title = {single-pass training assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/single-pass-training-assumption/rdr_03a8361a06214c0593632866e7043a0a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_single_pass_training_assumption_03a8361a_v1,
  title = {single-pass training assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/single-pass-training-assumption/rdr_03a8361a06214c0593632866e7043a0a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake