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 Zdeborová, Florent Krzakala

TL;DR

Reusing data batches during gradient descent fundamentally changes what two-layer neural networks can learn compared to single-pass methods. By breaking the theoretical constraints of "information" and "leap" exponents, multi-pass gradient descent can learn complex, non-staircase functions in as few as two steps—a feat previously thought to be computationally impossible in finite time.

What Problem Does This Paper Address?

In machine learning theory, researchers often analyze neural network training using "one-pass" (or single-pass) online stochastic gradient descent (SGD), where every iteration uses a fresh, unseen batch of data. Under this paradigm, previous work established strict mathematical limits on what networks can learn, dictated by the target function's information exponent or leap exponent. Essentially, single-pass algorithms can only learn functions that satisfy a strict "staircase property," where complex features must be built incrementally from simpler, already-learned linear features.

However, practitioners almost never train networks this way; they repeatedly cycle through the same data batches over multiple epochs. This paper addresses the massive gap between single-pass theory and multi-pass practice. The authors ask: Does reusing data batches allow gradient descent to overcome the inherent limitations of single-pass methods?

Methods

The authors analyze the training dynamics of a two-layer neural network (the "student") trying to learn a low-dimensional multi-index target function (the "teacher") in a high-dimensional setting where the number of samples $n$ and input dimensions $d$ both go to infinity ($n/d = \alpha = \Theta(1)$).

To track what happens when data is reused, standard Gaussian assumptions break down because the network weights become highly correlated with the data batch. To solve this, the authors deploy Dynamical Mean-Field Theory (DMFT), a framework originating in statistical physics. DMFT allows them to derive a set of exact, low-dimensional integro-differential equations that precisely describe the joint distribution of the network's weights and pre-activations over time, capturing the complex non-Gaussian correlations induced by batch reuse.

Datasets

The paper relies on synthetic high-dimensional datasets to provide rigorous mathematical guarantees:

  • Inputs: Standard i.i.d. Gaussian data ($\mathbf{z}_\nu \sim \mathcal{N}(0, \mathbf{I}_d)$).
  • Labels: Generated by multi-index target functions ($y_\nu = g^*(\mathbf{W}^* \mathbf{z}_\nu / \sqrt{d})$), including specific Hermite polynomials (like $\text{He}_3, \text{He}_4$) and staircase functions.

No real-world benchmarks were used, which is standard for this type of fundamental statistical mechanics analysis of deep learning.

Key Insights and Ideas

  • The "Hidden Progress" Mechanism: In single-pass GD, the network's pre-activations remain purely Gaussian. When a batch is reused, however, the first gradient step injects a non-Gaussian component into the pre-activations that correlates with the target function. Even if the network weights show zero initial overlap with a target direction, this "hidden progress" alters the gradients in the second step, allowing the network to abruptly learn entirely new orthogonal directions.
  • Symmetry is the Real Barrier: The paper disproves a recent conjecture that batch reuse is bounded by Correlational Statistical Query (CSQ) limits. Instead, it reveals that the true limitation to finite-time learning is symmetry. If a target function is completely symmetric along a certain direction (like the even function $g^* = \text{He}_4$), the hidden progress mechanism fails because the expectations cancel out, making the direction unlearnable in finite steps.
  • Implicit SQ Transformations: Multi-pass GD implicitly performs non-linear transformations on the data outputs. This allows it to bypass CSQ lower bounds and match the optimal complexity of more powerful Statistical Query (SQ) algorithms without needing specialized algorithmic warm-starts.

Key Results

  • Learning in Two Steps: For non-even target functions that single-pass GD completely fails to learn in finite time (such as the Hermite polynomial $\text{He}_3$), multi-pass GD achieves weak recovery of the target direction in exactly $T = 2$ iterations.
Comparison of single-pass and multi-pass GD on single-index targets. Multi-pass successfully learns $\text{He}_3(z)$ in two steps, while single-pass fails. Both fail on the even function $\text{He}_4(z)$.
  • Surpassing the Staircase Limitation: In multi-index settings, single-pass GD can only learn directions linearly connected to previously learned features. Multi-pass GD successfully learns orthogonal target subspaces that do not satisfy this staircase property.
Multi-index target learning curves showing multi-pass GD successfully capturing orthogonal overlaps that single-pass GD cannot see.
  • Mathematical Characterization: The authors proved Theorem 3.2, providing a strict geometric characterization of the subspace of directions ($P^*_\perp$) that can be efficiently learned in finite time versus those trapped by symmetry ($A^*$).

Limitations and Future Work

While groundbreaking, the paper notes a few limitations that pave the way for future research:

  1. Gaussian Data Assumption: The rigorous DMFT proofs rely on the input data being isotropic Gaussian. While the heuristic argument suggests the "hidden progress" mechanism applies to broader data distributions, extending the mathematical proof to structured data remains open.
  2. Fixed Second Layer: The analysis keeps the second-layer weights fixed at initialization, focusing entirely on representation learning in the first layer.
  3. Mini-batch Size Limits: The proof establishes results for batch sizes of order $\mathcal{O}(d)$. While empirical simulations show the same benefits hold for mini-batches as small as size 1 (SGD), proving this rigorously is currently beyond the reach of existing DMFT techniques.

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 Zdeborová 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