Research map / Optimization / Implicit bias and generalization
Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit
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 two-layer ReLU-like networks trained by layer-wise SGD with minibatch reuse learn single-index polynomial targets with near-linear (d·polylog d) samples, and n ≈ d^{(p*-1)∨1} for general link functions with generative exponent p*.
Problem
Gradient-based training of two-layer networks on single-index targets with information exponent p is believed to need n ≳ d^{Θ(p)} samples (CSQ lower bound ~ d^{p/2}), leaving a gap to the information-theoretic limit n ≍ d.
Approach
Reusing the same minibatch over two consecutive GD steps creates a non-correlational term that applies a polynomial transformation to the labels, lowering the information exponent (to 1 or 2) so SGD can escape the high-entropy initialization; combined with interpolation step, normalized SGD, randomized polynomial activations, and a second-layer ridge regression.
Key results
- Two-layer NN with SGD and batch reuse learns arbitrary polynomial single-index models with n, T = Theta~(d) samples/steps (up to constants depending on degree).
- For general link functions, sample complexity n = Theta~(d^{(p*-1)∨1}) with generative exponent p*, disproving the d^{p/2} conjecture for SGD.
- Empirically, batch-reuse SGD reaches low test error at n≈d for He_3 target while online SGD fails to reach weak recovery at n=Ω(d^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reuse minibatches across consecutive gradient steps instead of using online SGD | Two-layer ReLU neural network on the single-index polynomial target He_3 · Single-index polynomial target He_3 | test error: n\simeq d; online SGD test error does not drop | Helped |
| Reuse minibatches across consecutive gradient steps instead of using online SGD | Two-layer ReLU neural network on the single-index polynomial target He_3 · Single-index polynomial target He_3 | weak recovery: n=\Omega(d^2) | Helped |
| Use SGD with reused data for polynomial single-index learning | Two-layer neural network · Single-index polynomial targets | sample complexity: n = \tilde{O}(d\varepsilon^{-2}) | Helped |
| Use SGD with reused data for targets with generative exponent p_* | Two-layer neural network · Single-index models with generative exponent p_* | sample complexity: n = \tilde{\Theta}(d^{(p_*-1)\vee 1}) | Helped |
Surprising findings
- Online SGD fails to achieve even weak recovery at n=Ω(d^2) on a p=3 target while batch-reuse SGD succeeds at n≈d.
- The d^{p/2} sample complexity conjectured for SGD on squared loss is disproved, since the sample complexity depends on the generative exponent rather than information exponent.
Limitations
- Requires layer-wise training and a specific batch reuse schedule rather than standard multi-pass SGD on all parameters.
- Constants depend exponentially on target degree; polynomial activations with randomized coefficients and a second-layer ridge regression are needed.
- For general link functions with p*>2, sample complexity is not information-theoretically optimal (n >> d).
Experimental setup
Datasets: synthetic isotropic Gaussian single-index data
Benchmarks: synthetic single-index target f*(x)=He_3(<x,theta>)
Metrics: weak recovery overlap population squared loss sample complexity scaling
Baselines: online SGD CSQ-limited SGD smoothed SGD (Damian et al. 2023) tensor partial-trace SQ algorithm
Builds on: Ben Arous et al. 2021 online SGD single-index analysis Dudeja and Hsu 2018 / Damian et al. 2023 smoothing Damian et al. 2024 generative exponent Bietti et al. 2022 learning single-index models with SGD Dandi et al. 2023 two-layer NN weak recovery
Closest papers by meaning
- Symmetric Single Index Learning (ICLR 2024 · similarity 0.91)
- Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis (NeurIPS 2025 · similarity 0.90)
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.89)
- Learning Hierarchical Polynomials with Three-Layer Neural Networks (ICLR 2024 · similarity 0.88)
- Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.88)
- Online Learning and Information Exponents: The Importance of Batch size & Time/Complexity Tradeoffs (ICML 2024 · similarity 0.88)
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.