Explicit loss asymptotics in the gradient descent training of neural networks

Maksim Velikanov, Dmitry YarotskyNeurIPS 2021 · OpenReview

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:

  1. 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.
  2. Spectral Analysis: They decompose the loss evolution into the eigenvalues ($\lambda_n$) of the NTK and the coefficients ($c_n$) of the target function.
  3. 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.
  4. 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).

Experimental validation of power-law asymptotics for loss, eigenvalues, and coefficients.

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

Abstract

Current theoretical results on optimization trajectories of neural networks trained by gradient descent typically have the form of rigorous but potentially loose bounds on the loss values. In the present work we take a different approach and show that the learning trajectory of a wide network in a lazy training regime can be characterized by an explicit asymptotic at large training times. Specifically, the leading term in the asymptotic expansion of the loss behaves as a power law $L(t) \sim C t^{-\xi}$ with exponent $\xi$ expressed only through the data dimension, the smoothness of the activation function, and the class of function being approximated. Our results are based on spectral analysis of the integral operator representing the linearized evolution of a large network trained on the expected loss. Importantly, the techniques we employ do not require a specific form of the data distribution, for example Gaussian, thus making our findings sufficiently universal.
BibTeX
@inproceedings{velikanov2021explicit,
  author = {Maksim Velikanov and Dmitry Yarotsky},
  title = {{Explicit loss asymptotics in the gradient descent training of neural networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=EHUsTBGIP17},
}
Figure