Spurious Valleys in Two-layer Neural Network Optimization Landscapes

Abstract

Neural networks provide a rich class of high-dimensional, non-convex optimization problems. Despite their non-convexity, gradient-descent methods often successfully optimize these models. This has motivated a recent spur in research attempting to characterize properties of their loss surface that may explain such success. In this paper, we address this phenomenon by studying a key topological property of the loss: the presence or absence of spurious valleys, defined as connected components of sub-level sets that do not include a global minimum. Focusing on a class of two-layer neural networks defined by smooth (but generally non-linear) activation functions, we identify a notion of intrinsic dimension and show that it provides necessary and sufficient conditions for the absence of spurious valleys. More concretely, finite intrinsic dimension guarantees that for sufficiently overparametrised models no spurious valleys exist, independently of the data distribution. Conversely, infinite intrinsic dimension implies that spurious valleys do exist for certain data distributions, independently of model overparametrisation. Besides these positive and negative results, we show that, although spurious valleys may exist in general, they are confined to low risk levels and avoided with high probability on overparametrised models.

References in corpus (22)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• The Loss Surfaces of Multilayer Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Essentially No Barriers in Neural Network Energy Landscape
• Characterizing Implicit Bias in Terms of Optimization Geometry
• The loss surface of deep and wide neural networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Learning One-hidden-layer Neural Networks with Landscape Design
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• On the Computational Efficiency of Training Neural Networks
• Risk and parameter convergence of logistic regression
• Are ResNets Provably Better than Linear Predictors?
• Local minima in training of neural networks
• Topology and Geometry of Half-Rectified Network Optimization
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition

Cited by in corpus (30)

• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Optimization for deep learning: theory and algorithms
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Denoising and Regularization via Exploiting the Structural Bias of Convolutional Generators
• On the loss landscape of a class of deep neural networks with no bad local valleys
• A mean-field limit for certain deep neural networks
• Gradient Dynamics of Shallow Univariate ReLU Networks
• Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation
• Depth creates no more spurious local minima
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• On Connected Sublevel Sets in Deep Learning
• Landscape Connectivity and Dropout Stability of SGD Solutions for Over-parameterized Neural Networks
• The critical locus of overparameterized neural networks
• Pure and Spurious Critical Points: a Geometric Study of Linear Networks
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• A Note on Connectivity of Sublevel Sets in Deep Learning
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations
• PDE constraints on smooth hierarchical functions computed by neural networks
• Learning the mapping $\mathbf{x}\mapsto {\sum }_{i=1}^d{x}_i^2$: the cost of finding the needle in a haystack
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• DessiLBI: Exploring Structural Sparsity of Deep Networks via Differential Inclusion Paths