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

By Lili Su, Pengkun Yang. 2019

62 citations recorded by the source corpus.

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^*$ that generates the responses/labels. We show that if $f^*$ 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^*$ and $\rho$ only, i.e., the rate is independent of the sample size $n$. Furthermore, if $f^*$ 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^*$ is a polynomial. Throughout this paper, we consider the scenario where the input dimension $d$ is fixed.

Subfields: Artificial Intelligence, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Quanquan Gu
2. Lechao Xiao
3. Wei Hu
4. Jeffrey Pennington
5. Greg Yang
6. Meirav Galun
7. Amnon Geifman
8. Yuan Cao

In Scaling & Learning Theory

1. Lechao Xiao
2. Jeffrey Pennington
3. Meirav Galun
4. Amnon Geifman
5. Ronen Basri
6. Quanquan Gu
7. Greg Yang
8. Wei Hu

Citations in the corpus

• The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, methodology): “We consider circular padding (as in Xiao et al. [2018], Li et al.”
• Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks (2021, methodology): “In particular, for data distributed uniformly in the hypersphere S d − 1 , it was shown that the eigenfunctions of FC-NTK are the spherical harmonics and the eigenvalues decay at the rate of k − d , where k denotes frequency (Bietti & Mairal, 2019; Bietti & Bach, 2020).”
• Defending Distributed Systems Against Adversarial Attacks: Consensus, Consensusbased Learning, and Statistical Learning (2020, background): “In our recent work [20], we showed that nearly-linear over-parameterization is sufficient for two-layer network training.”
• Communication-efficient federated learning via knowledge distillation (2021, unknown): “This is because large deep learning models have the over-parameterization problem 43 , and thereby the model parameters are low-rank.”
• Towards Understanding the Spectral Bias of Deep Learning (2019, background): “Compared with [Su and Yang, 2019], the key difference is that while [Su and Yang, 2019] studied the full residual }y ´ pypT q}2 and required that the target function lies approximately in the eigenspace of large eigenvalues of the neural tangent kernel, our result in Theorem 3.2 works for arbitrary…”