mlsanityData to 14 Oct 2026

No bad local minima: Data independent training error guarantees for multilayer neural networks

arXiv 1605.08361 ↗First posted 26 May 2016stat.ML cs.LG cs.NEcited by 30

Not on the map. Why?

Abstract (arXiv)

We use smoothed analysis techniques to provide guarantees on the training loss of Multilayer Neural Networks (MNNs) at differentiable local minima. Specifically, we examine MNNs with piecewise linear activation functions, quadratic loss and a single output, under mild over-parametrization. We prove that for a MNN with one hidden layer, the training error is zero at every differentiable local minimum, for almost every dataset and dropout-like noise realization. We then extend these results to the case of more than one hidden layer. Our theoretical guarantees assume essentially nothing on the training data, and are verified numerically. These results suggest why the highly non-convex loss of such MNNs can be easily optimized using local updates (e.g., stochastic gradient descent), as observed empirically.

Key facts. Cited by 30 papers in the map (data through 14 Oct 2026). First posted on arXiv 26 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 4; 2023: 4; 2024: 5; 2025: 2; 2026: 3.

30 papers.

Sort:

  1. 2021Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Trainingcited by 110
  2. 2022Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscapecited by 39
  3. 2021Self-Paced Contrastive Learning for Semi-supervised Medical Image Segmentation with Meta-labelscited by 32
  4. 2021Exponentially Many Local Minima in Quantum Neural Networkscited by 22
  5. 2021Discovering Diverse Nearly Optimal Policies with Successor Featurescited by 20
  6. 2023Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Timecited by 20
  7. 2023Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscapecited by 17
  8. 2022On Feature Learning in Neural Networks with Global Convergence Guaranteescited by 13
  9. 2021Landscape analysis for shallow neural networks: complete classification of critical points for affine target functionscited by 11
  10. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  11. 2024Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivitycited by 9
  12. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
18 more
  1. 2021A Recipe for Global Convergence Guarantee in Deep Neural Networkscited by 8
  2. 2022When Expressivity Meets Trainability: Fewer than n Neurons Can Workcited by 8
  3. 2021Tilting the playing field: Dynamical loss functions for machine learningcited by 7
  4. 2021Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activationscited by 7
  5. 2024Loss Landscape of Shallow ReLU-like Neural Networks: Stationary Points, Saddle Escape, and Network Embeddingcited by 6
  6. 2022Why Quantization Improves Generalization: NTK of Binary Weight Neural Networkscited by 5
  7. 2021Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resiliencecited by 3
  8. 2023Gradient is All You Need? How Consensus-Based Optimization can be Interpreted as a Stochastic Relaxation of Gradient Descentcited by 3
  9. 2025Flat Channels to Infinity in Neural Loss Landscapescited by 3
  10. 2025Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networkscited by 2
  11. 2021Non-Convex Compressed Sensing with Training Datacited by 1
  12. 2026Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrievalcited by 1
  13. 2021Training Deep Neural Networks via Branch-and-Boundcited by 0
  14. 2023Black holes and the loss landscape in machine learningcited by 0
  15. 2024On the Convergence of (Stochastic) Gradient Descent for Kolmogorov--Arnold Networkscited by 0
  16. 2024Dynamical loss functions shape landscape topography and improve learning in artificial neural networkscited by 0
  17. 2026Don't stop me now: How Validation Criteria Affect Checkpoint Selection and Early Stoppingcited by 0
  18. 2026WisdomNet: trustable machine learning toward error-free classificationcited by 0