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

Abstract

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.

References in corpus (8)

• Improving neural networks by preventing co-adaptation of feature detectors
• Deep Residual Learning for Image Recognition
• Train faster, generalize better: Stability of stochastic gradient descent
• Qualitatively characterizing neural network optimization problems
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Gradient Descent Converges to Minimizers
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Smoothed Analysis of Tensor Decompositions

Cited by in corpus (98)

• A Convergence Theory for Deep Learning via Over-Parameterization
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Systematic evaluation of CNN advances on the ImageNet
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Essentially No Barriers in Neural Network Energy Landscape
• Scaling description of generalization with number of parameters in deep learning
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• The jamming transition as a paradigm to understand the loss landscape of deep neural networks
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Learning One-hidden-layer Neural Networks with Landscape Design
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Global optimality conditions for deep neural networks
• Universal Effectiveness of High-Depth Circuits in Variational Eigenproblems
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Local minima in training of neural networks
• An empirical analysis of the optimization of deep network loss surfaces
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Critical Points of Neural Networks: Analytical Forms and Landscape Properties
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Theoretical properties of the global optimizer of two layer neural network
• Mathematical Models of Overparameterized Neural Networks
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• Distribution-Specific Hardness of Learning Neural Networks
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• Transport Analysis of Infinitely Deep Neural Network
• Regularizing Activation Distribution for Training Binarized Deep Networks
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training
• Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape
• LCA: Loss Change Allocation for Neural Network Training
• The Landscape of Deep Learning Algorithms
• Convergence Rates of Variational Inference in Sparse Deep Learning
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?
• Fix your classifier: the marginal value of training the last weight layer
• Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision
• Learning Two Layer Rectified Neural Networks in Polynomial Time
• Towards Robust Deep Neural Networks
• Self-Paced Contrastive Learning for Semi-supervised Medical Image Segmentation with Meta-labels
• Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex
• Weight Sharing is Crucial to Succesful Optimization
• Landscape Complexity for the Empirical Risk of Generalized Linear Models
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Non-attracting Regions of Local Minima in Deep and Wide Neural Networks
• Are deep ResNets provably better than linear predictors?
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
• Orthogonal Over-Parameterized Training
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Supervised Deep Neural Networks (DNNs) for Pricing/Calibration of Vanilla/Exotic Options Under Various Different Processes
• Perspective: A Phase Diagram for Deep Learning unifying Jamming, Feature Learning and Lazy Training
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetry
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• The global optimum of shallow neural network is attained by ridgelet transform
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Understanding over-parameterized deep networks by geometrization
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Optimization Landscapes of Wide Deep Neural Networks Are Benign
• Ridge Regression with Over-Parametrized Two-Layer Networks Converge to Ridgelet Spectrum
• A Mixture of $h-1$ Heads is Better than $h$ Heads
• A Relaxation Argument for Optimization in Neural Networks and Non-Convex Compressed Sensing
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model
• BPGrad: Towards Global Optimality in Deep Learning via Branch and Pruning
• Approximate Fisher Information Matrix to Characterise the Training of Deep Neural Networks
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
• Training Deep Neural Networks via Branch-and-Bound
• Universality of Gradient Descent Neural Network Training
• Layer Dynamics of Linearised Neural Nets
• On Symmetry and Initialization for Neural Networks
• Accelerated Dual Learning by Homotopic Initialization
• The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions
• How regularization affects the critical points in linear networks
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
• The Restricted Isometry of ReLU Networks: Generalization through Norm Concentration
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations
• Quadratic number of nodes is sufficient to learn a dataset via gradient descent
• A study of local optima for learning feature interactions using neural networks
• Non-Convex Compressed Sensing with Training Data