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

Lili Su, Pengkun Yang

Introduction

In modern deep learning, models are routinely "over-parameterized," possessing far more parameters than there are training data points. Counterintuitively, these massive models do not simply memorize the data and overfit; they generalize remarkably well and can be optimized efficiently using simple first-order methods like Gradient Descent (GD).

Previous theoretical attempts to explain this phenomenon relied on "sufficiency guarantees," showing that if a network is sufficiently wide, GD converges to a global minimum. However, these theories often required the network width ($m$) to be a massive polynomial of the sample size ($n$), such as $m = \Omega(n^6)$. In practice, networks succeed with much smaller widths. Furthermore, many of these earlier theories yielded convergence rates that vanish as the dataset size grows ($n \to \infty$). This paper bridges the gap between theory and practice by providing a tighter, "nearly-linear" bound on the required width and characterizing a non-diminishing convergence rate.

A Functional Approximation Perspective

To achieve these tighter bounds, the authors shift the analytical lens from the parameter space (the weights) to a functional approximation perspective. Instead of tracking individual weights, they study the evolution of the network's prediction errors across GD iterations.

The core of their technique involves representing the error dynamics using matrices that, in the limit of infinite width, approximate a specific integral operator ($L_K$). This operator is determined entirely by the data's feature distribution ($\rho$). By analyzing how the target function ($f^*$) decomposes into the eigenspaces of this integral operator, the authors can precisely track learning dynamics.

Spectrum of the empirical matrix K versus the integral operator L_K

The analysis specifically focuses on two-layer networks using the Rectified Linear Unit (ReLU) activation function. By leveraging spectral projection concentration, they demonstrate that the empirical Gram matrix of the network closely concentrates around the integral operator.

Key Findings and Theoretical Guarantees

Nearly-Linear Width is Sufficient

Perhaps the most significant breakthrough in this work is the proof that massive polynomial over-parameterization is unnecessary. The authors prove that a network width of $m = \Theta(n \log n)$ is theoretically sufficient for the training error to converge, provided the target function is well-behaved relative to the integral operator. If the target function $f^*$ admits a low-rank approximation within the operator's eigenspaces, the empirical risk decreases at a linear rate determined by $f^*$ and $\rho$, independent of the sample size $n$.

Overcoming the "Vanishing Rate" Critique

The authors identify a critical flaw in previous influential papers: their predicted convergence rates relied on the minimum eigenvalue of the Gram matrix, which approaches zero as the sample size $n$ increases.

Minimum eigenvalue of the Gram matrix decaying as sample size n increases

By adopting the functional perspective, this paper identifies a constant convergence rate that does not disappear in large-scale applications. The target function's alignment with the top eigenfunctions of the integral operator dictates the speed of learning—if they align well, the network learns rapidly.

Dimensionality Impact

Using synthetic setups like uniformly distributed data on a unit sphere ($S^{d-1}$) and polynomial target functions, the authors demonstrate that convergence slows down as the input dimension ($d$) increases or as the degree of the polynomial target function increases.

Limitations and Future Directions

While this paper provides a substantial leap forward in understanding over-parameterization, it notes several areas for future exploration:

  • Fixed Dimension: The current analysis assumes the input dimension $d$ is fixed. Exploring the "high-dimensional region" where $d$ scales with $n$ is a necessary next step.
  • Network Depth: The proofs are centered on two-layer networks. While similar matrix representations exist for deeper architectures, formalizing the proofs for deep networks remains an open challenge.
  • Initialization Schemes: The study utilizes a specific "symmetric" initialization to guarantee zero output at the start, simplifying the mathematics. Analyzing standard initializations (like He or Xavier) through this functional perspective could yield further practical insights.

Summary updated

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^*$ 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.
BibTeX
@inproceedings{su2019learning,
  author = {Lili Su and Pengkun Yang},
  title = {{On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure