Theoretical insights into the optimization landscape of over-parameterized shallow neural networks

2017/07/16 by Mahdi Soltanolkotabi, Adel Javanmard, Soltanolkotabi, Mahdi +3 · 13 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Artificial neural network #Computer science #Differentiable function #FOS: Computer and information sciences #FOS: Mathematics #Gaussian #Gradient descent #Heuristics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and ELM #Mathematical optimization #Mathematics #Neural Networks and Applications #Optimization and Control (math.OC) #Optimization problem #Parameterized complexity #Quadratic equation #Set (abstract data type) #Variety (cybernetics) #cs.IT #cs.LG #math.IT #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1707.04926

published in arXiv (Cornell University) (Cornell University) · A mistake in the argument of Proposition 7.1 in the previous version of this manuscript was fixed

openalex publication_date 2017/07/16 · arxiv created 2022/08/24 · arxiv updated 2022/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

In this paper we study the problem of learning a shallow artificial neural network that best fits a training data set. We study this problem in the over-parameterized regime where the number of observations are fewer than the number of parameters in the model. We show that with quadratic activations the optimization landscape of training such shallow neural networks has certain favorable characteristics that allow globally optimal models to be found efficiently using a variety of local search heuristics. This result holds for an arbitrary training data of input/output pairs. For differentiable activation functions we also show that gradient descent, when suitably initialized, converges at a linear rate to a globally optimal model. This result focuses on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted weight coefficients.

Cited by

• Nonlinear Dynamics In Optimization Landscape of Shallow Neural Networks with Tunable Leaky ReLU
• A Law of Data Reconstruction for Random Features (and Beyond)
• Visualization and Analysis of the Loss Landscape in Graph Neural Networks
• Quantum Relational Knowledge Distillation
• Second-order methods for provably escaping strict saddle points in composite nonconvex and nonsmooth optimization
• Understanding Learning Invariance in Deep Linear Networks
• Models of Heavy-Tailed Mechanistic Universality
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Convexified Message-Passing Graph Neural Networks
• Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensions
• The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks
• Statistical Inference for Online Algorithms
• Model-Free Design and Analysis of 2DOF PI Controller for Noisy LTI Systems

Related

• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Stationary Points of a Shallow Neural Network with Quadratic Activations and the Global Optimality of the Gradient Descent Algorithm
• On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensions
• An Improved Analysis of Training Over-parameterized Deep Neural Networks