mlsanityData to 14 Oct 2026

Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGD

arXiv 2305.18502 ↗First posted 29 May 2023stat.ML cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

This study explores the sample complexity for two-layer neural networks to learn a generalized linear target function under Stochastic Gradient Descent (SGD), focusing on the challenging regime where many flat directions are present at initialization. It is well-established that in this scenario n=O(d log d) samples are typically needed. However, we provide precise results concerning the pre-factors in high-dimensional contexts and for varying widths. Notably, our findings suggest that overparameterization can only enhance convergence by a constant factor within this problem class. These insights are grounded in the reduction of SGD dynamics to a stochastic process in lower dimensions, where escaping mediocrity equates to calculating an exit time. Yet, we demonstrate that a deterministic approximation of this process adequately represents the escape time, implying that the role of stochasticity may be minimal in this scenario.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 32 of its 48 references that are in the map. First posted on arXiv 29 May 2023.

Builds on

32 of 48 references.

References · 32

  1. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  2. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  3. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  4. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  5. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  6. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  7. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
  8. 2019Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setupcited by 112
  9. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  10. 2018Mean Field Analysis of Neural Networks: A Central Limit Theoremcited by 107
  11. 2018Trainability and Accuracy of Neural Networks: An Interacting Particle System Approachcited by 106
  12. 2016A Geometric Analysis of Phase Retrievalcited by 92
20 more
  1. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  2. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 88
  3. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
  4. 2022Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputscited by 76
  5. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  6. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 70
  7. 2023Learning time-scales in two-layers neural networkscited by 57
  8. 2020Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functionscited by 50
  9. 2022Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networkscited by 50
  10. 2023From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networkscited by 43
  11. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  12. 2020Phase retrieval in high dimensions: Statistical and computational phase transitionscited by 39
  13. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  14. 2021Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problemcited by 23
  15. 2019Exact asymptotics for phase retrieval and compressed sensing with random generative priorscited by 20
  16. 2020Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrievalcited by 18
  17. 2017The nonsmooth landscape of phase retrievalcited by 16
  18. 2021Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalizationcited by 16
  19. 2017Phase Retrieval via Randomized Kaczmarz: Theoretical Guaranteescited by 15
  20. 2022On the symmetries in the dynamics of wide two-layer neural networkscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 5; 2026: 6.

15 papers.

Sort:

By area:

  1. 2023Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index modelscited by 26
  2. 2025Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regimecited by 20
  3. 2024A theoretical perspective on mode collapse in variational inferencecited by 14
  4. 2025Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networkscited by 9
  5. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 7
  6. 2026Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrievalcited by 6
  7. 2025Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Datacited by 3
  8. 2025Implicit bias produces neural scaling laws in learning curves, from perceptrons to deep networkscited by 2
  9. 2026Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networkscited by 2
  10. 2024Stochastic Gradient Flow Dynamics of Test Risk and its Exact Solution for Weak Featurescited by 1
  11. 2026Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrievalcited by 1
  12. 2026Escape dynamics and implicit bias of one-pass SGD in overparameterized quadratic networkscited by 1
3 more
  1. 2024Classifying Overlapping Gaussian Mixtures in High Dimensions: From Optimal Classifiers to Neural Netscited by 0
  2. 2026A Theory of Saddle Escape in Deep Nonlinear Networkscited by 0
  3. 2026Homogenization of ℓ2-Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descentcited by 0