While the empirical success of neural networks is undeniable, our theoretical understanding of how the training loss drops over time has remained somewhat fuzzy. Most existing theories provide "loose bounds"—rigorous mathematical guarantees that the loss won't exceed a certain value, but which often fail to describe the actual trajectory seen in practice.
In this NeurIPS 2021 paper, Maksim Velikanov and Dmitry Yarotsky take a "physics-style" approach to the problem. Instead of looking for bounds, they derive explicit power-law formulas that describe the long-term evolution of the training loss. They demonstrate that for wide neural networks in the "lazy training" regime, the training loss follows a predictable power law: $L(t) \sim Ct^{-\xi}$. The decay exponent $\xi$ is not random; it is determined by the input dimension, the smoothness of the activation function, and the "roughness" of the target function.
The Challenge of Quantifying Convergence
In the "lazy training" or Neural Tangent Kernel (NTK) regime, a very wide neural network behaves essentially like a linear model. While this simplification has allowed theorists to prove that networks will converge, it hasn't traditionally been used to predict how fast they converge in a quantitative way.
Real-world data and models are complex. Previous attempts to find exact solutions often relied on highly symmetric assumptions, such as data being perfectly distributed on a hypersphere. This paper seeks a more "universal" description that works for general, smooth data distributions, providing a much-needed bridge between abstract theory and empirical observation.
Analytical Methods
The authors treat the training process as the evolution of a singular integral operator. Their approach relies on several key technical steps:
- Linearized Evolution: By focusing on the NTK regime where the network's weights don't move far from their initialization, the training dynamics can be linearized.
- Spectral Analysis: They decompose the loss evolution into the eigenvalues ($\lambda_n$) of the NTK and the coefficients ($c_n$) of the target function.
- Diagonal Singularity Extraction: The authors show that the decay of eigenvalues is primarily determined by how the NTK behaves when two input points are very close to each other (the "diagonal"). By performing a Taylor expansion around this diagonal, they extract the power-law behavior of the spectrum.
- Integrated Localization: To handle the coefficients of the target function, they use a technique similar to a short-time Fourier transform, analyzing how the target function's "roughness" interacts with the network's architecture locally across the input space.
Key Insights and Results
The theoretical predictions were validated using synthetic data (mixtures of Gaussian distributions in 2D and 4D spaces) and real-world image data (MNIST). The target functions tested included discontinuous "Indicator Functions" (representing classification tasks) and smoother "Gaussian Processes" (GP).
Several core insights emerged from this analysis:
- The Power Law is Universal: The speed of learning ($\xi$) is largely indifferent to the specific shape of the data distribution. If the data is "smoothly distributed" in $d$ dimensions, the same exponents apply.
- Smoothness Dictates Speed: The "sharper" your activation function (like ReLU) or your target function (like an indicator function), the slower the learning.
- The Formula for $\xi$: For a ReLU network in $d$ dimensions, if the target is an indicator function, the loss decays as $t^{-1/(d+1)}$. If the target is a smoother Gaussian Process, the loss decays faster, as $t^{-3/(d+1)}$.
- Deep vs. Shallow: Making a network deeper changes the constant factor of the loss, but it doesn't change the exponent $\xi$. The fundamental "speed limit" of learning is set by the first layer's interaction with the input dimension.
- Eigenvalue Decay: The authors proved that NTK eigenvalues decay as $n^{-(1+1/d)}$. This explains why training slows down over time: the network captures "coarse" features quickly (large eigenvalues) but struggles with "fine" details (tiny eigenvalues).
On MNIST, the loss, eigenvalues, and coefficients all followed clear power laws. While the theory couldn't predict the exact exponent—because the "intrinsic dimension" of MNIST isn't exactly its 784 ambient pixels—the theoretical relationship between the exponents held true.
Limitations and Future Work
A notable limitation highlighted by the formulas is the Curse of Dimensionality. The exponents $\xi$ contain $1/d$ in the denominator. As the dimension $d$ increases, $\xi$ approaches zero, implying that learning should become infinitesimally slow. For real-world tasks like image recognition, the "effective" or "intrinsic" dimension of the data manifold is likely much lower than the ambient pixel dimension, which allows networks to train in practice. Future work is needed to automatically determine this intrinsic dimension to make these formulas truly predictive for complex datasets.
Furthermore, the current theory is rooted in the NTK/lazy regime. Extending these explicit asymptotics to the "feature learning" regime—where weights move significantly during training—remains a major open challenge for the field.
Summary updated