Porcupine Neural Networks: (Almost) All Local Optima are Global

Abstract

Neural networks have been used prominently in several machine learning and statistics applications. In general, the underlying optimization of neural networks is non-convex which makes their performance analysis challenging. In this paper, we take a novel approach to this problem by asking whether one can constrain neural network weights to make its optimization landscape have good theoretical properties while at the same time, be a good approximation for the unconstrained one. For two-layer neural networks, we provide affirmative answers to these questions by introducing Porcupine Neural Networks (PNNs) whose weight vectors are constrained to lie over a finite set of lines. We show that most local optima of PNN optimizations are global while we have a characterization of regions where bad local optimizers may exist. Moreover, our theoretical and empirical results suggest that an unconstrained neural network can be approximated using a polynomially-large PNN.

References in corpus (17)

• Understanding deep learning requires rethinking generalization
• The Loss Surfaces of Multilayer Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• The loss surface of deep and wide neural networks
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Recovery Guarantees for One-hidden-layer Neural Networks
• Benefits of depth in neural networks
• An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis
• The Landscape of Empirical Risk for Non-convex Losses
• Global optimality conditions for deep neural networks
• Beyond Convexity: Stochastic Quasi-Convex Optimization
• On the ability of neural nets to express distributions
• Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with ${\ell }^1$ and ${\ell }^0$ Controls
• The spectrum of random kernel matrices: universality results for rough and varying kernels
• The Spectral Norm of Random Inner-Product Kernel Matrices
• Minimax Lower Bounds for Ridge Combinations Including Neural Nets

Cited by in corpus (14)

• Optimization for deep learning: theory and algorithms
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• From Symmetry to Geometry: Tractable Nonconvex Problems
• KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Symmetry & critical points for a model shallow neural network
• On the Principle of Least Symmetry Breaking in Shallow ReLU Models
• Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetry
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Understanding Global Loss Landscape of One-hidden-layer ReLU Networks, Part 1: Theory
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations
• Backprojection for Training Feedforward Neural Networks in the Input and Feature Spaces
• Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations