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

arXiv: https://arxiv.org/abs/2305.18502 · HTML: https://mlsanity.com/paper/2305.18502/

## 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 (most cited first, 30 of 32)

- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup](https://mlsanity.com/paper/1906.08632/) (2019)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Mean Field Analysis of Neural Networks: A Central Limit Theorem](https://mlsanity.com/paper/1808.09372/) (2018)
- [Trainability and Accuracy of Neural Networks: An Interacting Particle System Approach](https://mlsanity.com/paper/1805.00915/) (2018)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Limitations of Lazy Training of Two-layers Neural Networks](https://mlsanity.com/paper/1906.08899/) (2019)
- [Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs](https://mlsanity.com/paper/2206.00939/) (2022)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [Learning time-scales in two-layers neural networks](https://mlsanity.com/paper/2303.00055/) (2023)
- [Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions](https://mlsanity.com/paper/2006.15459/) (2020)
- [Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networks](https://mlsanity.com/paper/2202.00293/) (2022)
- [From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks](https://mlsanity.com/paper/2302.05882/) (2023)
- [Fundamental Limits of Weak Recovery with Applications to Phase Retrieval](https://mlsanity.com/paper/1708.05932/) (2017)
- [Phase retrieval in high dimensions: Statistical and computational phase transitions](https://mlsanity.com/paper/2006.05228/) (2020)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem](https://mlsanity.com/paper/2103.04902/) (2021)
- [Exact asymptotics for phase retrieval and compressed sensing with random generative priors](https://mlsanity.com/paper/1912.02008/) (2019)
- [Complex Dynamics in Simple Neural Networks: Understanding Gradient Flow in Phase Retrieval](https://mlsanity.com/paper/2006.06997/) (2020)
- [The nonsmooth landscape of phase retrieval](https://mlsanity.com/paper/1711.03247/) (2017)
- [Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalization](https://mlsanity.com/paper/2110.08084/) (2021)

## Built on by (most cited first, 15 of 15)

- [Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index models](https://mlsanity.com/paper/2308.08977/) (2023)
- [Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime](https://mlsanity.com/paper/2509.24882/) (2025)
- [A theoretical perspective on mode collapse in variational inference](https://mlsanity.com/paper/2410.13300/) (2024)
- [Asymptotics of SGD in Sequence-Single Index Models and Single-Layer Attention Networks](https://mlsanity.com/paper/2506.02651/) (2025)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval](https://mlsanity.com/paper/2601.22652/) (2026)
- [Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data](https://mlsanity.com/paper/2511.18661/) (2025)
- [Implicit bias produces neural scaling laws in learning curves, from perceptrons to deep networks](https://mlsanity.com/paper/2505.13230/) (2025)
- [Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networks](https://mlsanity.com/paper/2604.09412/) (2026)
- [Stochastic Gradient Flow Dynamics of Test Risk and its Exact Solution for Weak Features](https://mlsanity.com/paper/2402.07626/) (2024)
- [Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrieval](https://mlsanity.com/paper/2602.17779/) (2026)
- [Escape dynamics and implicit bias of one-pass SGD in overparameterized quadratic networks](https://mlsanity.com/paper/2604.03068/) (2026)
- [Classifying Overlapping Gaussian Mixtures in High Dimensions: From Optimal Classifiers to Neural Nets](https://mlsanity.com/paper/2405.18427/) (2024)
- [A Theory of Saddle Escape in Deep Nonlinear Networks](https://mlsanity.com/paper/2605.01288/) (2026)
- [Homogenization of ℓ2-Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent](https://mlsanity.com/paper/2607.00207/) (2026)

## 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.