mlsanityData to 14 Oct 2026

Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models

arXiv 2305.10633 ↗First posted 18 May 2023cs.LG cs.IT math.ITcited by 61

Not on the map. Why?

Abstract (arXiv)

We focus on the task of learning a single index model σ(w^star · x) with respect to the isotropic Gaussian distribution in d dimensions. Prior work has shown that the sample complexity of learning w^star is governed by the information exponent k^star of the link function σ, which is defined as the index of the first nonzero Hermite coefficient of σ. Ben Arous et al. (2021) showed that n gtrsim dk^star-1 samples suffice for learning w^star and that this is tight for online SGD. However, the CSQ lower bound for gradient based methods only shows that n gtrsim dk^star/2 samples are necessary. In this work, we close the gap between the upper and lower bounds by showing that online SGD on a smoothed loss learns w^star with n gtrsim dk^star/2 samples. We also draw connections to statistical analyses of tensor PCA and to the implicit regularization effects of minibatch SGD on empirical losses.

Key facts. Cited by 61 papers in the map (data through 14 Oct 2026). Builds on 36 of its 44 references that are in the map. First posted on arXiv 18 May 2023.

Builds on

36 of 44 references.

References · 36

  1. 2015Rethinking the Inception Architecture for Computer Visioncited by 5,475
  2. 2018Measuring the Effects of Data Parallelism on Neural Network Trainingcited by 193
  3. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  4. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
  5. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  6. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  7. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  8. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  9. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  10. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  11. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  12. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
24 more
  1. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  2. 2016A Geometric Analysis of Phase Retrievalcited by 92
  3. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  4. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  5. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  6. 2014A statistical model for tensor PCAcited by 72
  7. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  8. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  9. 2017Learning ReLUs via Gradient Descentcited by 54
  10. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  11. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  12. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  13. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  14. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  15. 2017The landscape of the spiked tensor modelcited by 34
  16. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  17. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  18. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  19. 2018Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitionscited by 23
  20. 2019How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCAcited by 14
  21. 2016Homotopy Analysis for Tensor PCAcited by 12
  22. 2022Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexitycited by 12
  23. 2020Statistical Query Lower Bounds for Tensor PCAcited by 11
  24. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 8; 2024: 19; 2025: 20; 2026: 14.

61 papers.

Sort:

By area:

  1. 2023Grokking as the Transition from Lazy to Rich Training Dynamicscited by 108
  2. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  3. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  4. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 52
  5. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  6. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 44
  7. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 37
  8. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  9. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 31
  10. 2024A distributional simplicity bias in the learning dynamics of transformerscited by 24
  11. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 19
  12. 2024A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilitiescited by 16
38 more
  1. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 15
  2. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 15
  3. 2025Survey on Algorithms for multi-index modelscited by 15
  4. 2023Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luckcited by 13
  5. 2024Sliding down the stairs: how correlated latent variables accelerate learning with neural networkscited by 12
  6. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  7. 2024From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networkscited by 9
  8. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 9
  9. 2025Improving LLM Unlearning Robustness via Random Perturbationscited by 9
  10. 2025Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networkscited by 9
  11. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 9
  12. 2023Should Under-parameterized Student Networks Copy or Average Teacher Weights?cited by 8
  13. 2025Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recoverycited by 8
  14. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  15. 2023Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Productscited by 7
  16. 2025Feature learning from non-Gaussian inputs: the case of Independent Component Analysis in high dimensionscited by 7
  17. 2025Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Modelscited by 6
  18. 2025Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Lawscited by 6
  19. 2023Symmetric Single Index Learningcited by 5
  20. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
  21. 2024Gradient dynamics for low-rank fine-tuning beyond kernelscited by 5
  22. 2026A theory of learning data statistics in diffusion models, from easy to hardcited by 5
  23. 2024Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Modelscited by 4
  24. 2025Learning a Single Index Model from Anisotropic Data with vanilla Stochastic Gradient Descentcited by 4
  25. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  26. 2024Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffscited by 3
  27. 2025Bayes optimal learning of attention-indexed modelscited by 3
  28. 2025Test time training enhances in-context learning of nonlinear functionscited by 3
  29. 2025Learning Multi-Index Models with Hyper-Kernel Ridge Regressioncited by 3
  30. 2025Universality of high-dimensional scaling limits of stochastic gradient descentcited by 3
  31. 2026Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networkscited by 3
  32. 2026High-Dimensional Theory of LoRA Fine-Tuning in a Solvable Attention Modelcited by 3
  33. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  34. 2026When pre-training hurts LoRA fine-tuning: a dynamical analysis via single-index modelscited by 2
  35. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 2
  36. 2025Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensionscited by 1
  37. 2025Joint Learning in the Gaussian Single Index Modelcited by 1
  38. 2025Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learningcited by 1

50 most cited of 61 All 61 (JSON)