Nearly Minimal Over-Parametrization of Shallow Neural Networks

Abstract

A recent line of work has shown that an overparametrized neural network can perfectly fit the training data, an otherwise often intractable nonconvex optimization problem. For (fully-connected) shallow networks, in the best case scenario, the existing theory requires quadratic over-parametrization as a function of the number of training samples. This paper establishes that linear overparametrization is sufficient to fit the training data, using a simple variant of the (stochastic) gradient descent. Crucially, unlike several related works, the training considered in this paper is not limited to the lazy regime in the sense cautioned against in [1, 2]. Beyond shallow networks, the framework developed in this work for over-parametrization is applicable to a variety of learning problems.

arXiv commentThis paper is submitted without consent of the co-authors

References in corpus (20)

• Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
• Empirical Evaluation of Rectified Activations in Convolutional Network
• A Convergence Theory for Deep Learning via Over-Parameterization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• On Lazy Training in Differentiable Programming
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Spurious Valleys in Two-layer Neural Network Optimization Landscapes
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes