Adding One Neuron Can Eliminate All Bad Local Minima

Abstract

One of the main difficulties in analyzing neural networks is the non-convexity of the loss function which may have many bad local minima. In this paper, we study the landscape of neural networks for binary classification tasks. Under mild assumptions, we prove that after adding one special neuron with a skip connection to the output, or one special neuron per layer, every local minimum is a global minimum.

References in corpus (9)

• The Loss Surfaces of Multilayer Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Learning ReLUs via Gradient Descent
• On the Computational Efficiency of Training Neural Networks
• Identity Matters in Deep Learning
• Understanding the Loss Surface of Neural Networks for Binary Classification
• Globally Optimal Training of Generalized Polynomial Neural Networks with Nonlinear Spectral Methods

Cited by in corpus (24)

• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Optimization for deep learning: theory and algorithms
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Elimination of All Bad Local Minima in Deep Learning
• On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layers
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• The Local Elasticity of Neural Networks
• Over-parametrized deep neural networks do not generalize well
• Non-attracting Regions of Local Minima in Deep and Wide Neural Networks
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• On the rate of convergence of a neural network regression estimate learned by gradient descent
• Are deep ResNets provably better than linear predictors?
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• McKernel: A Library for Approximate Kernel Expansions in Log-linear Time
• Global Convergence and Generalization Bound of Gradient-Based Meta-Learning with Deep Neural Nets
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Traversing the noise of dynamic mini-batch sub-sampled loss functions: A visual guide
• Analysis of the rate of convergence of neural network regression estimates which are easy to implement
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
• When Are Solutions Connected in Deep Networks?
• Training Deep Neural Networks via Branch-and-Bound
• A Comprehensive Study on Optimization Strategies for Gradient Descent In Deep Learning
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations
• WGAN with an Infinitely Wide Generator Has No Spurious Stationary Points