Stationary Points of Shallow Neural Networks with Quadratic Activation Function

Abstract

We consider the teacher-student setting of learning shallow neural networks with quadratic activations and planted weight matrix $W^{\ast }\in {\mathbb{R}}^{m\times d}$, where $m$ is the width of the hidden layer and $d\le m$ is the data dimension. We study the optimization landscape associated with the empirical and the population squared risk of the problem. Under the assumption the planted weights are full-rank we obtain the following results. First, we establish that the landscape of the empirical risk admits an "energy barrier" separating rank-deficient $W$ from $W^{\ast }$: if $W$ is rank deficient, then its risk is bounded away from zero by an amount we quantify. We then couple this result by showing that, assuming number $N$ of samples grows at least like a polynomial function of $d$, all full-rank approximate stationary points of the empirical risk are nearly global optimum. These two results allow us to prove that gradient descent, when initialized below the energy barrier, approximately minimizes the empirical risk and recovers the planted weights in polynomial-time. Next, we show that initializing below this barrier is in fact easily achieved when the weights are randomly generated under relatively weak assumptions. We show that provided the network is sufficiently overparametrized, initializing with an appropriate multiple of the identity suffices to obtain a risk below the energy barrier. At a technical level, the last result is a consequence of the semicircle law for the Wishart ensemble and could be of independent interest. Finally, we study the minimizers of the empirical risk and identify a simple necessary and sufficient geometric condition on the training data under which any minimizer has necessarily zero generalization error. We show that as soon as $N\ge N^{\ast }=d(d+1)/2$, randomly generated data enjoys this geometric condition almost surely, while that ceases to be true if $N<N^{\ast }$.

arXiv comment54 pages

References in corpus (26)

• The Loss Surfaces of Multilayer Networks
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• 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
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Recovery Guarantees for One-hidden-layer Neural Networks
• Towards Understanding Generalization of Deep Learning: Perspective of Loss Landscapes
• Learning One-hidden-layer Neural Networks with Landscape Design
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Learning Functions: When Is Deep Better Than Shallow
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Norm-Based Capacity Control in Neural Networks
• The Power of Normalization: Faster Evasion of Saddle Points
• Reliably Learning the ReLU in Polynomial Time
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima
• The Landscape of Deep Learning Algorithms
• Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena

Cited by in corpus (6)

• Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions
• Neural Spectrahedra and Semidefinite Lifts: Global Convex Optimization of Polynomial Activation Neural Networks in Fully Polynomial-Time
• Avoiding Spurious Local Minima in Deep Quadratic Networks
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Neural Networks with Complex-Valued Weights Have No Spurious Local Minima
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron