Spurious Local Minima are Common in Two-Layer ReLU Neural Networks

Abstract

We consider the optimization problem associated with training simple ReLU neural networks of the form $\mathbf{x}\mapsto {\sum }_{i=1}^k\max \{0,{\mathbf{w}}_i^{\top }\mathbf{x}\}$ with respect to the squared loss. We provide a computer-assisted proof that even if the input distribution is standard Gaussian, even if the dimension is arbitrarily large, and even if the target values are generated by such a network, with orthonormal parameter vectors, the problem can still have spurious local minima once $6\le k\le 20$. By a concentration of measure argument, this implies that in high input dimensions, \emph{nearly all} target networks of the relevant sizes lead to spurious local minima. Moreover, we conduct experiments which show that the probability of hitting such local minima is quite high, and increasing with the network size. On the positive side, mild over-parameterization appears to drastically reduce such local minima, indicating that an over-parameterization assumption is necessary to get a positive result in this setting.

Cited by in corpus (73)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• On the Convergence Rate of Training Recurrent Neural Networks
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• On the loss landscape of a class of deep neural networks with no bad local valleys
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Adding One Neuron Can Eliminate All Bad Local Minima
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets
• Understanding self-supervised Learning Dynamics without Contrastive Pairs
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Mathematical Models of Overparameterized Neural Networks
• A Closer Look at Deep Policy Gradients
• On the Power and Limitations of Random Features for Understanding Neural Networks
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Recent advances in deep learning theory
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• Do We Actually Need Dense Over-Parameterization? In-Time Over-Parameterization in Sparse Training
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Over Parameterized Two-level Neural Networks Can Learn Near Optimal Feature Representations
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex
• The Local Elasticity of Neural Networks
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• Taxonomizing local versus global structure in neural network loss landscapes
• Interpreting Deep Learning: The Machine Learning Rorschach Test?
• Approximation power of random neural networks
• Selection dynamics for deep neural networks
• Symmetry & critical points for a model shallow neural network
• Hessian based analysis of SGD for Deep Nets: Dynamics and Generalization
• PAC Confidence Predictions for Deep Neural Network Classifiers
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• Are deep ResNets provably better than linear predictors?
• On the Principle of Least Symmetry Breaking in Shallow ReLU Models
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetry
• The Global Optimization Geometry of Shallow Linear Neural Networks
• When does gradient descent with logistic loss find interpolating two-layer networks?
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms
• Collective evolution of weights in wide neural networks
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• When Hardness of Approximation Meets Hardness of Learning
• Trap of Feature Diversity in the Learning of MLPs
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• On the Provable Generalization of Recurrent Neural Networks
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• The Nonconvex Geometry of Linear Inverse Problems
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes
• A Relaxation Argument for Optimization in Neural Networks and Non-Convex Compressed Sensing
• Non-Convex Compressed Sensing with Training Data
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations
• Universality of Gradient Descent Neural Network Training
• SGD Through the Lens of Kolmogorov Complexity
• Deep Neural Networks Are Congestion Games: From Loss Landscape to Wardrop Equilibrium and Beyond
• When Are Solutions Connected in Deep Networks?
• Benefits of over-parameterization with EM
• Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II
• Learning Graph Neural Networks with Approximate Gradient Descent