Research map / Optimization / Implicit bias and generalization
The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that multi-pass (batch-reusing) gradient descent on two-layer networks learns multi-index targets beyond the information/leap exponent limits of one-pass SGD, achieving weak recovery in two steps, via DMFT analysis.
Problem
Understanding which multi-index target functions two-layer networks can learn efficiently with gradient descent; prior theory limits one-pass SGD and gradient flow by information exponent, leap exponent and staircase property.
Approach
Reusing the same batch across GD iterations creates non-Gaussian pre-activation components correlated with the target ("hidden progress"), so the first layer learns directions in the orthogonal complement of the symmetric subspace within two steps; analyzed rigorously with dynamical mean-field theory.
Key results
- Multi-pass GD achieves weak recovery of non-staircase multi-index teacher directions in T=2 steps, while one-pass GD does not in finite time (simulations at d=5000, averaged over 32 runs).
- Symmetric (even) target directions remain unlearnable in any finite number of GD steps with batch size O(d).
- DMFT yields closed-form integro-differential equations describing low-dimensional weight projection dynamics for multi-pass GD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| multi-pass GD (reusing the same batch for multiple steps) instead of single-pass SGD with fresh batches | two-layer networks learning multi-index targets · multi-index / single-index teacher targets, high-dimensional limit n=alpha d | weak recovery (overlap with target subspace) | Helped |
| multi-pass GD with reused batches on a non-even single-index target with IE=3 | two-layer network, multi-pass GD · single-index target, IE=3, non-even | weak recovery in finite steps | Helped |
| multi-pass GD on even-symmetric target (IE=4) or committee with symmetric activation | two-layer network, multi-pass GD · even single-index target IE=4; symmetric committee machine | weak recovery in finite time | No clear effect |
| multi-pass GD on targets with symmetric (even) structure along a direction | two-layer network · phase retrieval / symmetric targets | overlap with symmetric directions over finite T | No clear effect |
Surprising findings
- Gradient descent on the same batch can outperform one-pass SGD on fresh batches even when one-pass uses more datapoints.
- Results disprove a conjecture that batch reuse only reduces sample complexity to the CSQ lower bound for leap-l targets.
Limitations
- Results are for Gaussian data and extensive batches of size O(d); mini-batch size 1 is only empirical.
- Symmetric target directions cannot be learned in finite steps.
- Second layer kept fixed at initialization.
Experimental setup
Datasets: synthetic Gaussian multi-index data
Metrics: overlap with teacher direction orthogonal overlap
Baselines: one-pass SGD gradient flow on population loss
Builds on: Dynamical Mean Field Theory information exponent leap exponent staircase property
Closest papers by meaning
- Online Learning and Information Exponents: The Importance of Batch size & Time/Complexity Tradeoffs (ICML 2024 · similarity 0.90)
- Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup (NeurIPS 2019 · similarity 0.90)
- Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration (ICML 2026 · similarity 0.89)
- Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization (NeurIPS 2024 · similarity 0.88)
- Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networks (NeurIPS 2025 · similarity 0.88)
- No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.