Elimination of All Bad Local Minima in Deep Learning

Abstract

In this paper, we theoretically prove that adding one special neuron per output unit eliminates all suboptimal local minima of any deep neural network, for multi-class classification, binary classification, and regression with an arbitrary loss function, under practical assumptions. At every local minimum of any deep neural network with these added neurons, the set of parameters of the original neural network (without added neurons) is guaranteed to be a global minimum of the original neural network. The effects of the added neurons are proven to automatically vanish at every local minimum. Moreover, we provide a novel theoretical characterization of a failure mode of eliminating suboptimal local minima via an additional theorem and several examples. This paper also introduces a novel proof technique based on the perturbable gradient basis (PGB) necessary condition of local minima, which provides new insight into the elimination of local minima and is applicable to analyze various models and transformations of objective functions beyond the elimination of local minima.

arXiv commentAccepted to appear in AISTATS 2020

References in corpus (17)

• The Loss Surfaces of Multilayer Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• The loss surface of deep and wide neural networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Learning One-hidden-layer Neural Networks with Landscape Design
• Learning ReLUs via Gradient Descent
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Identity Matters in Deep Learning
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• Exponentially vanishing sub-optimal local minima in multilayer neural networks
• Optimization Landscape and Expressivity of Deep CNNs
• Adding One Neuron Can Eliminate All Bad Local Minima
• Are ResNets Provably Better than Linear Predictors?
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
• Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex

Cited by in corpus (15)

• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Optimization for deep learning: theory and algorithms
• The Global Landscape of Neural Networks: An Overview
• Dynamics of Deep Neural Networks and Neural Tangent Hierarchy
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Classification Logit Two-sample Testing by Neural Networks
• On generalization bounds for deep networks based on loss surface implicit regularization
• Eliminating all bad Local Minima from Loss Landscapes without even adding an Extra Unit
• 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
• Differentiable Visual Computing
• Theoretical Exploration of Flexible Transmitter Model
• Invexifying Regularization of Non-Linear Least-Squares Problems
• 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