mlsanityData to 7 Oct 2026

Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit

arXiv 2406.01581 ↗First posted 3 Jun 2024cs.LG stat.MLcited by 45

Not on the map. Why?

Abstract (arXiv)

We study the problem of gradient descent learning of a single-index target function f_*(boldsymbolx) = textstyleσ_*left(langleboldsymbolx,boldsymbolθrangleright) under isotropic Gaussian data in ℝd, where the unknown link function σ_*:ℝ→ℝ has information exponent p (defined as the lowest degree in the Hermite expansion). Prior works showed that gradient-based training of neural networks can learn this target with ngtrsim dTheta(p) samples, and such complexity is predicted to be necessary by the correlational statistical query lower bound. Surprisingly, we prove that a two-layer neural network optimized by an SGD-based algorithm (on the squared loss) learns f_* with a complexity that is not governed by the information exponent. Specifically, for arbitrary polynomial single-index models, we establish a sample and runtime complexity of n simeq T = Theta(d!·! polylog d), where Theta(·) hides a constant only depending on the degree of σ_*; this dimension dependence matches the information theoretic limit up to polylogarithmic factors. More generally, we show that ngtrsim d(p_*-1)vee 1 samples are sufficient to achieve low generalization error, where p_* ≤ p is the textitgenerative exponent of the link function. Core to our analysis is the reuse of minibatch in the gradient computation, which gives rise to higher-order information beyond correlational queries.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). Builds on 37 of its 54 references that are in the map. First posted on arXiv 3 Jun 2024.

Builds on

37 of 54 references.

References · 37

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018On Lazy Training in Differentiable Programmingcited by 671
  3. 2019Lookahead Optimizer: k steps forward, 1 step backcited by 333
  4. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  5. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  6. 2019Linearized two-layers neural networks in high dimensioncited by 155
  7. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  8. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  9. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  10. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  11. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
  12. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
25 more
  1. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  2. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  3. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  4. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 69
  5. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 61
  6. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 60
  7. 2023Learning time-scales in two-layers neural networkscited by 57
  8. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 53
  9. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  10. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  11. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 36
  12. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 35
  13. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  14. 2021How rotational invariance of common kernels prevents generalization in high dimensionscited by 32
  15. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  16. 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
  17. 2020Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexitycited by 25
  18. 2023Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index modelscited by 25
  19. 2024Nonlinear spiked covariance matrices and signal propagation in deep neural networkscited by 25
  20. 2020Statistical Queries and Statistical Algorithms: Foundations and Applicationscited by 21
  21. 2023Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Timecited by 20
  22. 2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 18
  23. 2022Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexitycited by 12
  24. 2024Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspectivecited by 12
  25. 2020Statistical Query Lower Bounds for Tensor PCAcited by 11

Built on by

Cited by year (2026 to 7 Oct)

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

45 papers.

Sort:

By area:

  1. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 29
  2. 2025Survey on Algorithms for multi-index modelscited by 15
  3. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 14
  4. 2024Wide Neural Networks Trained with Weight Decay Provably Exhibit Neural Collapsecited by 14
  5. 2024Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinationscited by 13
  6. 2025Position: A Theory of Deep Learning Must Include Compositional Sparsitycited by 13
  7. 2024Shallow diffusion networks provably learn hidden low-dimensional structurecited by 12
  8. 2024From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networkscited by 9
  9. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 8
  10. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  11. 2025Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descentcited by 8
  12. 2025On the Mechanisms of Weak-to-Strong Generalization: A Theoretical Perspectivecited by 7
33 more
  1. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
  2. 2025Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Modelscited by 6
  3. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 6
  4. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
  5. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  6. 2025Online Learning of Neural Networkscited by 5
  7. 2025Learning a Single Index Model from Anisotropic Data with vanilla Stochastic Gradient Descentcited by 4
  8. 2025Martingale Posterior Neural Networks for Fast Sequential Decision Makingcited by 4
  9. 2025Test time training enhances in-context learning of nonlinear functionscited by 3
  10. 2026How Do Transformers Learn to Associate Tokens: Gradient Leading Terms Bring Mechanistic Interpretabilitycited by 3
  11. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  12. 2024Learning with Hidden Factorial Structurecited by 2
  13. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  14. 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 2
  15. 2024Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networkscited by 1
  16. 2024Improving the Convergence Rates of Forward Gradient Descent with Repeated Samplingcited by 1
  17. 2025Guided by the Experts: Provable Feature Learning Dynamic of Soft-Routed Mixture-of-Expertscited by 1
  18. 2025Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learningcited by 1
  19. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 1
  20. 2026The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledgecited by 1
  21. 2026When Both Layers Learn: Training Dynamics of Representing Linear Models via ReLU Networkscited by 1
  22. 2024Robust Fourier Neural Networkscited by 0
  23. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0
  24. 2025Universality of high-dimensional scaling limits of stochastic gradient descentcited by 0
  25. 2025Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attentioncited by 0
  26. 2026Local EGOP for Continuous Index Learningcited by 0
  27. 2026Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrievalcited by 0
  28. 2026Improved high-dimensional estimation with Langevin dynamics and stochastic weight averagingcited by 0
  29. 2026Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Ratecited by 0
  30. 2026Feature Learning in Linear-Width Two-Layer Networks: Two vs. One Step of Gradient Descentcited by 0
  31. 2026Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biasescited by 0
  32. 2026How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysiscited by 0
  33. 2026Singular perturbations and hierarchical learning in two-layer neural networkscited by 0