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

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

## Key facts

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

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

- [Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training](https://mlsanity.com/paper/2102.02887/) (2021)
- [Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscape](https://mlsanity.com/paper/2201.08025/) (2022)
- [Self-Paced Contrastive Learning for Semi-supervised Medical Image Segmentation with Meta-labels](https://mlsanity.com/paper/2107.13741/) (2021)
- [Exponentially Many Local Minima in Quantum Neural Networks](https://mlsanity.com/paper/2110.02479/) (2021)
- [Discovering Diverse Nearly Optimal Policies with Successor Features](https://mlsanity.com/paper/2106.00669/) (2021)
- [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)
- [Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscape](https://mlsanity.com/paper/2305.19510/) (2023)
- [On Feature Learning in Neural Networks with Global Convergence Guarantees](https://mlsanity.com/paper/2204.10782/) (2022)
- [Landscape analysis for shallow neural networks: complete classification of critical points for affine target functions](https://mlsanity.com/paper/2103.10922/) (2021)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivity](https://mlsanity.com/paper/2404.06391/) (2024)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [A Recipe for Global Convergence Guarantee in Deep Neural Networks](https://mlsanity.com/paper/2104.05785/) (2021)
- [When Expressivity Meets Trainability: Fewer than n Neurons Can Work](https://mlsanity.com/paper/2210.12001/) (2022)
- [Tilting the playing field: Dynamical loss functions for machine learning](https://mlsanity.com/paper/2102.03793/) (2021)
- [Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations](https://mlsanity.com/paper/2102.13233/) (2021)
- [Loss Landscape of Shallow ReLU-like Neural Networks: Stationary Points, Saddle Escape, and Network Embedding](https://mlsanity.com/paper/2402.05626/) (2024)
- [Why Quantization Improves Generalization: NTK of Binary Weight Neural Networks](https://mlsanity.com/paper/2206.05916/) (2022)
- [Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience](https://mlsanity.com/paper/2103.09424/) (2021)
- [Gradient is All You Need? How Consensus-Based Optimization can be Interpreted as a Stochastic Relaxation of Gradient Descent](https://mlsanity.com/paper/2306.09778/) (2023)
- [Flat Channels to Infinity in Neural Loss Landscapes](https://mlsanity.com/paper/2506.14951/) (2025)
- [Overparametrization bends the landscape: BBP transitions at initialization in simple Neural Networks](https://mlsanity.com/paper/2510.18435/) (2025)
- [Non-Convex Compressed Sensing with Training Data](https://mlsanity.com/paper/2101.08310/) (2021)
- [Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrieval](https://mlsanity.com/paper/2602.17779/) (2026)
- [Training Deep Neural Networks via Branch-and-Bound](https://mlsanity.com/paper/2104.01730/) (2021)
- [Black holes and the loss landscape in machine learning](https://mlsanity.com/paper/2306.14817/) (2023)
- [On the Convergence of (Stochastic) Gradient Descent for Kolmogorov--Arnold Networks](https://mlsanity.com/paper/2410.08041/) (2024)
- [Dynamical loss functions shape landscape topography and improve learning in artificial neural networks](https://mlsanity.com/paper/2410.10690/) (2024)
- [Don't stop me now: How Validation Criteria Affect Checkpoint Selection and Early Stopping](https://mlsanity.com/paper/2602.22107/) (2026)
- [WisdomNet: trustable machine learning toward error-free classification](https://mlsanity.com/paper/2610.15299/) (2026)

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