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.
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.
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