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