Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations

Abstract

In this paper, it is shown theoretically that spurious local minima are common for deep fully-connected networks and convolutional neural networks (CNNs) with piecewise linear activation functions and datasets that cannot be fitted by linear models. A motivating example is given to explain the reason for the existence of spurious local minima: each output neuron of deep fully-connected networks and CNNs with piecewise linear activations produces a continuous piecewise linear (CPWL) output, and different pieces of CPWL output can fit disjoint groups of data samples when minimizing the empirical risk. Fitting data samples with different CPWL functions usually results in different levels of empirical risk, leading to prevalence of spurious local minima. This result is proved in general settings with any continuous loss function. The main proof technique is to represent a CPWL function as a maximization over minimization of linear pieces. Deep ReLU networks are then constructed to produce these linear pieces and implement maximization and minimization operations.

References in corpus (30)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• On the Number of Linear Regions of Deep Neural Networks
• The Loss Surfaces of Multilayer Networks
• 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
• Deep ReLU Networks Have Surprisingly Few Activation Patterns
• Depth Creates No Bad Local Minima
• Identity Matters in Deep Learning
• Depth with Nonlinearity Creates No Bad Local Minima in ResNets
• The Landscape of Empirical Risk for Non-convex Losses
• Complexity of Linear Regions in Deep Networks
• Theory II: Landscape of the Empirical Risk in Deep Learning
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Adding One Neuron Can Eliminate All Bad Local Minima
• Elimination of All Bad Local Minima in Deep Learning
• Are ResNets Provably Better than Linear Predictors?
• Local minima in training of neural networks
• Critical Points of Neural Networks: Analytical Forms and Landscape Properties
• Topology and Geometry of Half-Rectified Network Optimization
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Small nonlinearities in activation functions create bad local minima in neural networks
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• Piecewise linear activations substantially shape the loss surfaces of neural networks
• Depth creates no more spurious local minima
• Piecewise Strong Convexity of Neural Networks
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Low-loss connection of weight vectors: distribution-based approaches
• Deforming the Loss Surface to Affect the Behaviour of the Optimizer