The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents

Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborova, Florent Krzakala

Abstract

In the standard practice of deep learning, models are trained by iterating over the same dataset multiple times—a process known as training for multiple "epochs." Despite its ubiquity, the theoretical justification for why reusing data is so much more effective than using fresh data at each step has remained elusive. This paper provides a rigorous theoretical foundation for this phenomenon, demonstrating that multi-pass gradient descent (GD) can overcome complexity barriers—specifically the "Information Exponent" and "Leap Complexity"—that typically constrain single-pass methods. By analyzing two-layer neural networks through the lens of Dynamical Mean-Field Theory (DMFT), the authors show that reusing data allows the network to align with target features in as few as two steps, reducing sample complexity from $O(d^{LC})$ to $O(d)$ for a broad class of functions.

The Complexity Barrier in Single-Pass Learning

In high-dimensional machine learning, researchers often study "single-pass" or "online" Stochastic Gradient Descent (SGD), where each data point is used only once. Previous theory suggested that certain functions are fundamentally "hard" to learn this way unless they possess a "staircase property"—a hierarchy where simple features can be learned first to "unlock" more complex ones.

If a function lacks this property, its difficulty is measured by the Information Exponent (IE) or Leap Complexity (LC). For these "hard" functions, single-pass GD requires a number of samples that grows polynomially with the dimension ($d^{LC}$), which is often computationally prohibitive. This paper asks whether the common practice of reusing data (multi-pass GD) fundamentally changes these learnability limits.

The Mechanism of "Hidden Progress"

The core of the authors' analysis relies on Dynamical Mean-Field Theory (DMFT), a framework from statistical physics recently made rigorous for machine learning. DMFT allows the authors to track the evolution of the network's weights and "pre-activations" (the internal signals before the non-linear activation function) in the high-dimensional limit.

The key novel concept introduced is "hidden progress." The authors show that in the first step of multi-pass GD, even if the weights do not immediately align with the target function, the internal pre-activations become correlated with the target because the same samples are used again. This "primes" the network, allowing it to achieve a significant overlap with the target in the very next step. Essentially, the first gradient step "imprints" information about the specific samples into the weights, creating a feedback loop that allows the network to "jump" over complexity barriers.

Breaking the Leap Exponent

The authors disprove recent conjectures that batch reuse only provides a marginal benefit. They demonstrate that for a broad class of functions, the sample complexity drops from $O(d^{LC})$ to just $O(d)$, regardless of the leap complexity.

Using synthetic high-dimensional Gaussian data and testing various target functions (including single-index models like $\text{He}_3(z)$ and multi-index committee machines), the research highlights two major results:

  • Two-Step Learning: Multi-pass GD can learn non-staircase functions in just $T=2$ iterations, whereas single-pass GD learns nothing in the same timeframe.
  • Theoretical Precision: The DMFT equations provide a "closed-form" description of the training process that matches numerical simulations with remarkable precision.

Symmetry as the Real Bottleneck

While multi-pass GD is powerful, the paper identifies that the true limit to fast learning is not complexity, but symmetry. If a target function is perfectly even-symmetric (such as $x^2$ or phase retrieval), the "hidden progress" signals cancel each other out. In these cases, the function remains hard to learn in finite time, requiring a "symmetry-breaking" phase that takes much longer.

Conclusion and Future Directions

This work bridges the gap between empirical deep learning success and theoretical understanding. It confirms that reusing data is not merely a matter of convenience but a fundamental algorithmic advantage. While the current rigorous proof assumes Gaussian input data and large batches, the authors observe similar effects empirically for smaller mini-batches, suggesting that the "hidden progress" mechanism is a robust feature of neural network optimization. Future work remains to formally extend these results to non-Gaussian distributions and smaller batch limits.

Summary updated

Abstract

We investigate the training dynamics of two-layer neural networks when learning multi-index target functions. We focus on multi-pass gradient descent (GD) that reuses the batches multiple times and show that it significantly changes the conclusion about which functions are learnable compared to single-pass gradient descent. In particular, multi-pass GD with finite stepsize is found to overcome the limitations of gradient flow and single-pass GD given by the information exponent (Ben Arous et al., 2021) and leap exponent (Abbe et al., 2023) of the target function. We show that upon re-using batches, the network achieves in just two time steps an overlap with the target subspace even for functions not satisfying the staircase property (Abbe et al., 2021). We characterize the (broad) class of functions efficiently learned in finite time. The proof of our results is based on the analysis of the Dynamical Mean-Field Theory (DMFT). We further provide a closed-form description of the dynamical process of the low-dimensional projections of the weights, and numerical experiments illustrating the theory.
BibTeX
@inproceedings{dandi2024benefits,
  author = {Yatin Dandi and Emanuele Troiani and Luca Arnaboldi and Luca Pesce and Lenka Zdeborova and Florent Krzakala},
  title = {{The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=iKkFruh4d5},
}
Figure