# SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics

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

## Key facts

- Cited by 143 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 66 references that are in the map.
- First posted on arXiv 21 Feb 2023.

## Builds on (most cited first, 30 of 41)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit](https://mlsanity.com/paper/1902.06015/) (2019)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [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)
- [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Limitations of Lazy Training of Two-layers Neural Networks](https://mlsanity.com/paper/1906.08899/) (2019)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Towards Understanding Hierarchical Learning: Benefits of Neural Representations](https://mlsanity.com/paper/2006.13436/) (2020)
- [Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval](https://mlsanity.com/paper/1910.12837/) (2019)
- [Learning Polynomials of Few Relevant Dimensions](https://mlsanity.com/paper/2004.13748/) (2020)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization](https://mlsanity.com/paper/2107.12580/) (2021)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)](https://mlsanity.com/paper/1710.09430/) (2017)

## Built on by (most cited first, 30 of 143)

- [The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains](https://mlsanity.com/paper/2402.11004/) (2024)
- [How Two-Layer Neural Networks Learn, One (Giant) Step at a Time](https://mlsanity.com/paper/2305.18270/) (2023)
- [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023)
- [Saddle-to-Saddle Dynamics in Diagonal Linear Networks](https://mlsanity.com/paper/2304.00488/) (2023)
- [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023)
- [How Feature Learning Can Improve Neural Scaling Laws](https://mlsanity.com/paper/2409.17858/) (2024)
- [Transformers learn through gradual rank increase](https://mlsanity.com/paper/2306.07042/) (2023)
- [The Local Learning Coefficient: A Singularity-Aware Complexity Measure](https://mlsanity.com/paper/2308.12108/) (2023)
- [The Shaped Transformer: Attention Models in the Infinite Depth-and-Width Limit](https://mlsanity.com/paper/2306.17759/) (2023)
- [Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit](https://mlsanity.com/paper/2406.01581/) (2024)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [Asymptotics of feature learning in two-layer networks after one gradient-step](https://mlsanity.com/paper/2402.04980/) (2024)
- [When is Task Vector Provably Effective for Model Editing? A Generalization Analysis of Nonlinear Transformers](https://mlsanity.com/paper/2504.10957/) (2025)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Gradient-Based Feature Learning under Structured Data](https://mlsanity.com/paper/2309.03843/) (2023)
- [Pretrained transformer efficiently learns low-dimensional target functions in-context](https://mlsanity.com/paper/2411.02544/) (2024)
- [Dynamical versus Bayesian Phase Transitions in a Toy Model of Superposition](https://mlsanity.com/paper/2310.06301/) (2023)
- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [The emergence of sparse attention: impact of data distribution and benefits of repetition](https://mlsanity.com/paper/2505.17863/) (2025)
- [A distributional simplicity bias in the learning dynamics of transformers](https://mlsanity.com/paper/2410.19637/) (2024)
- [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024)
- [Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs](https://mlsanity.com/paper/2306.16921/) (2023)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time](https://mlsanity.com/paper/2306.16361/) (2023)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [Leveraging the two timescale regime to demonstrate convergence of neural networks](https://mlsanity.com/paper/2304.09576/) (2023)
- [Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks](https://mlsanity.com/paper/2305.06986/) (2023)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)

## Abstract (arXiv)

We investigate the time complexity of SGD learning on fully-connected neural networks with isotropic data. We put forward a complexity measure -- the leap -- which measures how "hierarchical" target functions are. For d-dimensional uniform Boolean or isotropic Gaussian data, our main conjecture states that the time complexity to learn a function f with low-dimensional support is tildeTheta (dmax(Leap(f),2)). We prove a version of this conjecture for a class of functions on Gaussian isotropic data and 2-layer neural networks, under additional technical assumptions on how SGD is run. We show that the training sequentially learns the function support with a saddle-to-saddle dynamic. Our result departs from [Abbe et al. 2022] by going beyond leap 1 (merged-staircase functions), and by going beyond the mean-field and gradient flow approximations that prohibit the full complexity control obtained here. Finally, we note that this gives an SGD complexity for the full training trajectory that matches that of Correlational Statistical Query (CSQ) lower-bounds.