mlsanityData to 14 Oct 2026

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

arXiv 2302.11055 ↗First posted 21 Feb 2023cs.LG stat.MLcited by 143

Not on the map. Why?

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.

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

41 of 66 references.

References · 41

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  3. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  4. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  5. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  6. 2019Analysing Mathematical Reasoning Abilities of Neural Modelscited by 335
  7. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
  8. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  9. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  10. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  11. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  12. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
29 more
  1. 2019Linearized two-layers neural networks in high dimensioncited by 155
  2. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  3. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  4. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  5. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  6. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
  7. 2020Learning Parities with Neural Networkscited by 78
  8. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  9. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 69
  10. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
  11. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  12. 2020Towards Understanding Hierarchical Learning: Benefits of Neural Representationscited by 46
  13. 2019Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrievalcited by 34
  14. 2020Learning Polynomials of Few Relevant Dimensionscited by 34
  15. 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
  16. 2021Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalizationcited by 29
  17. 2021On the Power of Differentiable Learning versus PAC and SQ Learningcited by 28
  18. 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 26
  19. 2020Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexitycited by 25
  20. 2020Statistical Queries and Statistical Algorithms: Foundations and Applicationscited by 22
  21. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 18
  22. 2021Optimization-Based Separations for Neural Networkscited by 17
  23. 2022Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measurescited by 17
  24. 2013From average case complexity to improper learning complexitycited by 16
  25. 2022Feature selection with gradient descent on two-layer networks in low-rotation regimescited by 14
  26. 2022Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomialscited by 13
  27. 2022An initial alignment between neural network and target is needed for gradient descent to learncited by 12
  28. 2020Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methodscited by 9
  29. 2018Is your function low-dimensional?cited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 25; 2024: 33; 2025: 43; 2026: 42.

143 papers.

Sort:

By area:

  1. 2024The Evolution of Statistical Induction Heads: In-Context Learning Markov Chainscited by 118
  2. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  3. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  4. 2023Saddle-to-Saddle Dynamics in Diagonal Linear Networkscited by 57
  5. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  6. 2024How Feature Learning Can Improve Neural Scaling Lawscited by 56
  7. 2023Transformers learn through gradual rank increasecited by 52
  8. 2023The Local Learning Coefficient: A Singularity-Aware Complexity Measurecited by 51
  9. 2023The Shaped Transformer: Attention Models in the Infinite Depth-and-Width Limitcited by 47
  10. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  11. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 40
  12. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 39
38 more
  1. 2024Asymptotics of feature learning in two-layer networks after one gradient-stepcited by 38
  2. 2025When is Task Vector Provably Effective for Model Editing? A Generalization Analysis of Nonlinear Transformerscited by 38
  3. 2024Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functionscited by 37
  4. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 36
  5. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  6. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 31
  7. 2023Dynamical versus Bayesian Phase Transitions in a Toy Model of Superpositioncited by 29
  8. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 29
  9. 2025The emergence of sparse attention: impact of data distribution and benefits of repetitioncited by 25
  10. 2024A distributional simplicity bias in the learning dynamics of transformerscited by 24
  11. 2024Bayes-optimal learning of an extensive-width neural network from quadratically many samplescited by 23
  12. 2023Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputscited by 22
  13. 2024Provably learning a multi-head attention layercited by 21
  14. 2023Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Timecited by 20
  15. 2023Six Lectures on Linearized Neural Networkscited by 20
  16. 2023Leveraging the two timescale regime to demonstrate convergence of neural networkscited by 19
  17. 2023Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networkscited by 19
  18. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 19
  19. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  20. 2023On Single Index Models beyond Gaussian Datacited by 17
  21. 2024A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilitiescited by 16
  22. 2025RL for Reasoning by Adaptively Revealing Rationalescited by 16
  23. 2025Learning In-context n-grams with Transformers: Sub-n-grams Are Near-stationary Pointscited by 16
  24. 2023Understanding Multi-phase Optimization Dynamics and Rich Nonlinear Behaviors of ReLU Networkscited by 15
  25. 2024Towards a theory of model distillationcited by 15
  26. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 15
  27. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 15
  28. 2024Progressive distillation induces an implicit curriculumcited by 15
  29. 2025Survey on Algorithms for multi-index modelscited by 15
  30. 2025Saddle-to-Saddle Dynamics Explains A Simplicity Bias Across Neural Network Architecturescited by 15
  31. 2025Dynamics of Transient Structure in In-Context Linear Regression Transformerscited by 14
  32. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 14
  33. 2025Position: A Theory of Deep Learning Must Include Compositional Sparsitycited by 14
  34. 2023Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luckcited by 13
  35. 2024Complexity Matters: Dynamics of Feature Learning in the Presence of Spurious Correlationscited by 12
  36. 2024Sliding down the stairs: how correlated latent variables accelerate learning with neural networkscited by 12
  37. 2025Parameter Symmetry Potentially Unifies Deep Learning Theorycited by 12
  38. 2024Efficient Stagewise Pretraining via Progressive Subnetworkscited by 10

50 most cited of 143 All 143 (JSON)