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

2017/10/05 by Soheil Feizi, Hamid Javadi, Feizi, Soheil +5 · 6 citations
Computer Science · #Neural Networks and Applications #Machine Learning and Algorithms #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1710.02196

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.

Citations

• The Loss Surfaces of Multilayer Networks
• The spectrum of random kernel matrices: universality results for rough and varying kernels

Cited by

• Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale of Symmetry
• KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Spurious Local Minima Are Common for Deep Neural Networks with Piecewise Linear Activations
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Sub-Optimal Local Minima Exist for Neural Networks with Almost All Non-Linear Activations

Related

• Qualitatively characterizing neural network optimization problems
• Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalization
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Statistical Guarantees for Approximate Stationary Points of Shallow Neural Networks
• Adding One Neuron Can Eliminate All Bad Local Minima