mlsanityData to 7 Oct 2026

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

arXiv 2402.03220 ↗First posted 5 Feb 2024stat.ML cs.LGcited by 50

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 50 papers in the map (data through 7 Oct 2026). Builds on 32 of its 55 references that are in the map. First posted on arXiv 5 Feb 2024.

Builds on

32 of 55 references.

References · 32

  1. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  2. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
  3. 2020Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networkscited by 200
  4. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  5. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  6. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 146
  7. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  8. 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
  9. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  10. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  11. 2018Mean Field Analysis of Neural Networks: A Central Limit Theoremcited by 107
  12. 2018Trainability and Accuracy of Neural Networks: An Interacting Particle System Approachcited by 105
20 more
  1. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 95
  2. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
  3. 2022Universality of empirical risk minimizationcited by 73
  4. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
  5. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  6. 2020Dynamical mean-field theory for stochastic gradient descent in Gaussian mixture classificationcited by 60
  7. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  8. 2018The committee machine: Computational to statistical gaps in learning a two-layers neural networkcited by 58
  9. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
  10. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 53
  11. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  12. 2023A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networkscited by 46
  13. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
  14. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  15. 2019Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Modelscited by 28
  16. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  17. 2019Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Modelcited by 25
  18. 2021The effective noise of Stochastic Gradient Descentcited by 25
  19. 2018Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inferencecited by 24
  20. 2021Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problemcited by 23

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 23; 2025: 13; 2026: 14.

50 papers.

Sort:

  1. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
  2. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 39
  3. 2024Towards a theory of how the structure of language is acquired by deep neural networkscited by 38
  4. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 35
  5. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 29
  6. 2024Bayes-optimal learning of an extensive-width neural network from quadratically many samplescited by 23
  7. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  8. 2025Survey on Algorithms for multi-index modelscited by 15
  9. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 14
  10. 2024A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilitiescited by 14
  11. 2024Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinationscited by 13
  12. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 13
38 more
  1. 2025The Hidden Width of Deep ResNets: Tight Error Bounds and Phase Diagramcited by 13
  2. 2024Sliding down the stairs: how correlated latent variables accelerate learning with neural networkscited by 12
  3. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 11
  4. 2024From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networkscited by 9
  5. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 8
  6. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  7. 2025On the Mechanisms of Weak-to-Strong Generalization: A Theoretical Perspectivecited by 7
  8. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
  9. 2025Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Modelscited by 6
  10. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 6
  11. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
  12. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  13. 2025Online Learning of Neural Networkscited by 5
  14. 2026Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrievalcited by 5
  15. 2024Pruning is Optimal for Learning Sparse Features in High-Dimensionscited by 4
  16. 2025Martingale Posterior Neural Networks for Fast Sequential Decision Makingcited by 4
  17. 2024Asymptotic Dynamics of Alternating Minimization for Bilinear Regressioncited by 3
  18. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  19. 2025A statistical physics framework for optimal learningcited by 3
  20. 2025Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Datacited by 3
  21. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  22. 2024Signal-Plus-Noise Decomposition of Nonlinear Spiked Random Matrix Modelscited by 2
  23. 2024Spring-block theory of feature learning in deep neural networkscited by 2
  24. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  25. 2026When pre-training hurts LoRA fine-tuning: a dynamical analysis via single-index modelscited by 2
  26. 2024Mean-Field Analysis for Learning Subspace-Sparse Polynomials with Gaussian Inputcited by 1
  27. 2024Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networkscited by 1
  28. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 1
  29. 2026The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledgecited by 1
  30. 2026Learning with Shallow Neural Networks on Cluster-Structured Featurescited by 1
  31. 2026Neuron Block Dynamics for XOR Classification with Zero-Margincited by 0
  32. 2026Improved high-dimensional estimation with Langevin dynamics and stochastic weight averagingcited by 0
  33. 2026The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficientlycited by 0
  34. 2026A Fourier perspective on the learning dynamics of neural networks: from sample complexities to mechanistic insightscited by 0
  35. 2026Feature Learning in Linear-Width Two-Layer Networks: Two vs. One Step of Gradient Descentcited by 0
  36. 2026Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biasescited by 0
  37. 2026The Kinetics of Training: A Driven-Nucleation Rate Law for Emergence, Plasticity Loss, and Circuit Control in Language Modelscited by 0
  38. 2026Minibatch persistency, eight years later: what batch reuse costs in steps and joules, and what it saves in datacited by 0