Subquadratic Overparameterization for Shallow Neural Networks

Abstract

Overparameterization refers to the important phenomenon where the width of a neural network is chosen such that learning algorithms can provably attain zero loss in nonconvex training. The existing theory establishes such global convergence using various initialization strategies, training modifications, and width scalings. In particular, the state-of-the-art results require the width to scale quadratically with the number of training data under standard initialization strategies used in practice for best generalization performance. In contrast, the most recent results obtain linear scaling either with requiring initializations that lead to the "lazy-training", or training only a single layer. In this work, we provide an analytical framework that allows us to adopt standard initialization strategies, possibly avoid lazy training, and train all layers simultaneously in basic shallow neural networks while attaining a desirable subquadratic scaling on the network width. We achieve the desiderata via Polyak-Lojasiewicz condition, smoothness, and standard assumptions on data, and use tools from random matrix theory.

arXiv commentTo appear at the conference on Neural Information Processing Systems (NeurIPS 2021)

References in corpus (14)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Gaussian Error Linear Units (GELUs)
• Empirical Evaluation of Rectified Activations in Convolutional Network
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Semi-supervised Learning with GANs: Manifold Invariance with Improved Inference
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• On the linearity of large non-linear models: when and why the tangent kernel is constant
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Overparameterization From Depth
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization