mlsanityData to 14 Oct 2026

Learning Single-Index Models with Shallow Neural Networks

arXiv 2210.15651 ↗First posted 27 Oct 2022cs.LG math.OC stat.MLcited by 92

Not on the map. Why?

Abstract (arXiv)

Single-index models are a class of functions given by an unknown univariate ``link'' function applied to an unknown one-dimensional projection of the input. These models are particularly relevant in high dimension, when the data might present low-dimensional structure that learning algorithms should adapt to. While several statistical aspects of this model, such as the sample complexity of recovering the relevant (one-dimensional) subspace, are well-understood, they rely on tailored algorithms that exploit the specific structure of the target function. In this work, we introduce a natural class of shallow neural networks and study its ability to learn single-index models via gradient flow. More precisely, we consider shallow networks in which biases of the neurons are frozen at random initialization. We show that the corresponding optimization landscape is benign, which in turn leads to generalization guarantees that match the near-optimal sample complexity of dedicated semi-parametric methods.

Key facts. Cited by 92 papers in the map (data through 14 Oct 2026). Builds on 51 of its 117 references that are in the map. First posted on arXiv 27 Oct 2022.

Builds on

51 of 117 references.

References · 51

  1. 2015Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)cited by 1,070
  2. 2018On Lazy Training in Differentiable Programmingcited by 675
  3. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
  4. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 320
  5. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  6. 2017How to Escape Saddle Points Efficientlycited by 285
  7. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  8. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  9. 2020Directional convergence and alignment in deep learningcited by 178
  10. 2016Generalization Properties of Learning with Random Featurescited by 164
  11. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  12. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
38 more
  1. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  2. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 138
  3. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  4. 2018Stochastic subgradient method converges on tame functionscited by 124
  5. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  6. 2019A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Casecited by 114
  7. 2019Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setupcited by 112
  8. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  9. 2019How do infinite width bounded norm networks look in function space?cited by 106
  10. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  11. 2016A Geometric Analysis of Phase Retrievalcited by 92
  12. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  13. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  14. 2019Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networkscited by 79
  15. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 70
  16. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
  17. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  18. 2017Learning ReLUs via Gradient Descentcited by 54
  19. 2022Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networkscited by 50
  20. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  21. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  22. 2016The non-convex Burer-Monteiro approach works on smooth semidefinite programscited by 46
  23. 2020Towards Understanding Hierarchical Learning: Benefits of Neural Representationscited by 46
  24. 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
  25. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  26. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  27. 2017The landscape of the spiked tensor modelcited by 34
  28. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  29. 2019Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Modelscited by 28
  30. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
  31. 2018Marvels and Pitfalls of the Langevin Algorithm in Noisy High-dimensional Inferencecited by 24
  32. 2018Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitionscited by 23
  33. 2017On the Optimization Landscape of Tensor Decompositionscited by 21
  34. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  35. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  36. 2021Optimization-Based Separations for Neural Networkscited by 17
  37. 2019Landscape Complexity for the Empirical Risk of Generalized Linear Modelscited by 15
  38. 2020Hardness of Learning Neural Networks with Natural Weightscited by 15

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 26; 2024: 22; 2025: 20; 2026: 22.

92 papers.

Sort:

By area:

  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  2. 2023Grokking as the Transition from Lazy to Rich Training Dynamicscited by 108
  3. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  4. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  5. 2023Learning time-scales in two-layers neural networkscited by 57
  6. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  7. 2023Transformers learn through gradual rank increasecited by 52
  8. 2023Grokking as a First Order Phase Transition in Two Layer Networkscited by 48
  9. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  10. 2024Computational-Statistical Gaps in Gaussian Single-Index Modelscited by 44
  11. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 39
  12. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 37
38 more
  1. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  2. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 31
  3. 2026There Will Be a Scientific Theory of Deep Learningcited by 29
  4. 2022Mechanism of feature learning in deep fully connected networks and kernel machines that recursively learn featurescited by 25
  5. 2024Sloth: scaling laws for LLM skills to predict multi-benchmark performance across familiescited by 24
  6. 2023Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Timecited by 20
  7. 2023Six Lectures on Linearized Neural Networkscited by 20
  8. 2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 19
  9. 2023On Single Index Models beyond Gaussian Datacited by 17
  10. 2024Wide Neural Networks Trained with Weight Decay Provably Exhibit Neural Collapsecited by 16
  11. 2023Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGDcited by 15
  12. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 15
  13. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 15
  14. 2025Survey on Algorithms for multi-index modelscited by 15
  15. 2023Provable Guarantees for Neural Networks via Gradient Feature Learningcited by 14
  16. 2023Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luckcited by 13
  17. 2024Mean-field Analysis on Two-layer Neural Networks from a Kernel Perspectivecited by 13
  18. 2024Shallow diffusion networks provably learn hidden low-dimensional structurecited by 12
  19. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  20. 2023Learning Hierarchical Polynomials with Three-Layer Neural Networkscited by 9
  21. 2024From Spikes to Heavy Tails: Unveiling the Spectral Evolution of Neural Networkscited by 9
  22. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 9
  23. 2025Robust Learning of Multi-index Models via Iterative Subspace Approximationcited by 9
  24. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 9
  25. 2023ReLU Neural Networks with Linear Layers are Biased Towards Single- and Multi-Index Modelscited by 8
  26. 2023Should Under-parameterized Student Networks Copy or Average Teacher Weights?cited by 8
  27. 2024How Neural Networks Learn the Support is an Implicit Regularization Effect of SGDcited by 8
  28. 2024Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysiscited by 8
  29. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  30. 2023Efficient Estimation of the Central Mean Subspace via Smoothed Gradient Outer Productscited by 7
  31. 2024The Role of the Time-Dependent Hessian in High-Dimensional Optimizationcited by 7
  32. 2023Unraveling Projection Heads in Contrastive Learning: Insights from Expansion and Shrinkagecited by 6
  33. 2026Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chainingcited by 6
  34. 2022Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networkscited by 5
  35. 2023Symmetric Single Index Learningcited by 5
  36. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  37. 2024Task Diversity Shortens the ICL Plateaucited by 5
  38. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5

50 most cited of 92 All 92 (JSON)