On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes

Abstract

We study the optimization landscape and the stability properties of training problems with squared loss for neural networks and general nonlinear conic approximation schemes. It is demonstrated that, if a nonlinear conic approximation scheme is considered that is (in an appropriately defined sense) more expressive than a classical linear approximation approach and if there exist unrealizable label vectors, then a training problem with squared loss is necessarily unstable in the sense that its solution set depends discontinuously on the label vector in the training data. We further prove that the same effects that are responsible for these instability properties are also the reason for the emergence of saddle points and spurious local minima, which may be arbitrarily far away from global solutions, and that neither the instability of the training problem nor the existence of spurious local minima can, in general, be overcome by adding a regularization term to the objective function that penalizes the size of the parameters in the approximation scheme. The latter results are shown to be true regardless of whether the assumption of realizability is satisfied or not. We demonstrate that our analysis in particular applies to training problems for free-knot interpolation schemes and deep and shallow neural networks with variable widths that involve an arbitrary mixture of various activation functions (e.g., binary, sigmoid, tanh, arctan, soft-sign, ISRU, soft-clip, SQNL, ReLU, leaky ReLU, soft-plus, bent identity, SILU, ISRLU, and ELU). In summary, the findings of this paper illustrate that the improved approximation properties of neural networks and general nonlinear conic approximation instruments are linked in a direct and quantifiable way to undesirable properties of the optimization problems that have to be solved in order to train them.

arXiv commentFinal version, Journal of Machine Learning Research, 22(263):1-77, 2021, https://jmlr.org/papers/v22/20-1259.html

References in corpus (20)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Optimization for deep learning: theory and algorithms
• Nonlinear Approximation and (Deep) ReLU Networks
• The Global Landscape of Neural Networks: An Overview
• On the loss landscape of a class of deep neural networks with no bad local valleys
• Adding One Neuron Can Eliminate All Bad Local Minima
• Local minima in training of neural networks
• Critical Points of Neural Networks: Analytical Forms and Landscape Properties
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Training Neural Networks is $\exists \mathbb{R}$-complete
• An Integer Programming Approach to Deep Neural Networks with Binary Activation Functions
• Deep linear neural networks with arbitrary loss: All local minima are global
• Symmetry & critical points for a model shallow neural network
• The critical locus of overparameterized neural networks
• Avoiding Spurious Local Minima in Deep Quadratic Networks

Cited by in corpus (1)

• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations