On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective

Abstract

We consider training over-parameterized two-layer neural networks with Rectified Linear Unit (ReLU) using gradient descent (GD) method. Inspired by a recent line of work, we study the evolutions of network prediction errors across GD iterations, which can be neatly described in a matrix form. When the network is sufficiently over-parameterized, these matrices individually approximate {\em an} integral operator which is determined by the feature vector distribution $\rho$ only. Consequently, GD method can be viewed as {\em approximately} applying the powers of this integral operator on the underlying/target function $f^{\ast }$ that generates the responses/labels. We show that if $f^{\ast }$ admits a low-rank approximation with respect to the eigenspaces of this integral operator, then the empirical risk decreases to this low-rank approximation error at a linear rate which is determined by $f^{\ast }$ and $\rho$ only, i.e., the rate is independent of the sample size $n$. Furthermore, if $f^{\ast }$ has zero low-rank approximation error, then, as long as the width of the neural network is $\Omega (n\log n)$, the empirical risk decreases to $\Theta (1/\sqrt{n})$. To the best of our knowledge, this is the first result showing the sufficiency of nearly-linear network over-parameterization. We provide an application of our general results to the setting where $\rho$ is the uniform distribution on the spheres and $f^{\ast }$ is a polynomial. Throughout this paper, we consider the scenario where the input dimension $d$ is fixed.

References in corpus (17)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• A Convergence Theory for Deep Learning via Over-Parameterization
• 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
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Recovery Guarantees for One-hidden-layer Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• Diverse Neural Network Learns True Target Functions
• Kernel and Rich Regimes in Overparametrized Models
• Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds

Cited by in corpus (13)

• Towards Understanding the Spectral Bias of Deep Learning
• A Generalized Neural Tangent Kernel Analysis for Two-layer Neural Networks
• Mathematical Models of Overparameterized Neural Networks
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• When Does Preconditioning Help or Hurt Generalization?
• Universal scaling laws in the gradient descent training of neural networks
• A Deep Conditioning Treatment of Neural Networks
• Subquadratic Overparameterization for Shallow Neural Networks
• Why Shallow Networks Struggle to Approximate and Learn High Frequencies
• Global Convergence of SGD On Two Layer Neural Nets
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks