mlsanityData to 7 Oct 2026

Spurious Local Minima are Common in Two-Layer ReLU Neural Networks

arXiv 1712.08968 ↗First posted 24 Dec 2017cs.LG stat.MLcited by 104

Not on the map. Why?

Abstract (arXiv)

We consider the optimization problem associated with training simple ReLU neural networks of the form xmapsto sumi=1kmax0,wi^top x with respect to the squared loss. We provide a computer-assisted proof that even if the input distribution is standard Gaussian, even if the dimension is arbitrarily large, and even if the target values are generated by such a network, with orthonormal parameter vectors, the problem can still have spurious local minima once 6≤ k≤ 20. By a concentration of measure argument, this implies that in high input dimensions, nearly all target networks of the relevant sizes lead to spurious local minima. Moreover, we conduct experiments which show that the probability of hitting such local minima is quite high, and increasing with the network size. On the positive side, mild over-parameterization appears to drastically reduce such local minima, indicating that an over-parameterization assumption is necessary to get a positive result in this setting.

Key facts. Cited by 104 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Dec 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 0; 2020: 0; 2021: 26; 2022: 25; 2023: 19; 2024: 13; 2025: 10; 2026: 10.

104 papers.

Sort:

By area:

  1. 2021Understanding self-supervised Learning Dynamics without Contrastive Pairscited by 254
  2. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 226
  3. 2021Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Trainingcited by 107
  4. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 67
  5. 2021Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectificationcited by 59
  6. 2022Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscapecited by 39
  7. 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
  8. 2022Understanding Deep Contrastive Learning via Coordinate-wise Optimizationcited by 35
  9. 2021Taxonomizing local versus global structure in neural network loss landscapescited by 34
  10. 2023NTK-SAP: Improving neural network pruning by aligning training dynamicscited by 30
  11. 2022Regression as Classification: Influence of Task Formulation on Neural Network Featurescited by 29
  12. 2021A Theory of Neural Tangent Kernel Alignment and Its Influence on Trainingcited by 25
38 more
  1. 2021Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programscited by 25
  2. 2023Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuroncited by 25
  3. 2022Exact Solutions of a Deep Linear Networkcited by 24
  4. 2024The Real Tropical Geometry of Neural Networkscited by 23
  5. 2021Exponentially Many Local Minima in Quantum Neural Networkscited by 22
  6. 2023An SDE for Modeling SAM: Theory and Insightscited by 22
  7. 2022On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Biascited by 21
  8. 2023On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensionscited by 21
  9. 2021Noether: The More Things Change, the More Stay the Samecited by 19
  10. 2022How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysiscited by 18
  11. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  12. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  13. 2021On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Settingcited by 16
  14. 2021Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry IIcited by 16
  15. 2023Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networkscited by 16
  16. 2023Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscapecited by 16
  17. 2021Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networkscited by 14
  18. 2021Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networkscited by 14
  19. 2018Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithmscited by 13
  20. 2022On Feature Learning in Neural Networks with Global Convergence Guaranteescited by 12
  21. 2024The Persistence of Neural Collapse Despite Low-Rank Biascited by 12
  22. 2021Landscape analysis for shallow neural networks: complete classification of critical points for affine target functionscited by 11
  23. 2021When Are Solutions Connected in Deep Networks?cited by 10
  24. 2022Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methodscited by 10
  25. 2022Special Properties of Gradient Descent with Large Learning Ratescited by 10
  26. 2022Annihilation of Spurious Minima in Two-Layer ReLU Networkscited by 9
  27. 2024Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivitycited by 9
  28. 2025Generative quantum advantage for classical and quantum problemscited by 9
  29. 2022On the Omnipresence of Spurious Local Minima in Certain Neural Network Training Problemscited by 8
  30. 2022Learning and generalization of one-hidden-layer neural networks, going beyond standard Gaussian datacited by 8
  31. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  32. 2023Should Under-parameterized Student Networks Copy or Average Teacher Weights?cited by 8
  33. 2024Learning Gaussian Multi-Index Models with Gradient Flow: Time Complexity and Directional Convergencecited by 8
  34. 2025A Tale of Two Symmetries: Exploring the Loss Landscape of Equivariant Modelscited by 8
  35. 2021Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activationscited by 7
  36. 2024Loss Landscape Characterization of Neural Networks without Over-Parametrizationcited by 7
  37. 2021On the Provable Generalization of Recurrent Neural Networkscited by 6
  38. 2023Random Teachers are Good Teacherscited by 6

50 most cited of 104 All 104 (JSON)