The Three Stages of Learning Dynamics in High-dimensional Kernel Methods

Nikhil Ghosh, Song Mei, Bin Yu

Introduction

While deep learning has achieved incredible empirical success, our theoretical understanding of how neural networks learn over time remains limited. Researchers have observed several "intriguing phenomena" during training—such as networks learning simple functions before complex ones, or the "deep bootstrap" where models generalize well even while heavily overfitting their training data. However, these observations have largely lacked a unified mathematical explanation in high-dimensional settings.

This paper provides a rigorous theoretical framework for the training dynamics of high-dimensional kernel methods, identifying three distinct stages of learning. By mathematically formalizing empirical deep learning phenomena, the authors demonstrate how models navigate the trade-off between memorization and generalization, and show that faster training does not necessarily lead to better generalization.

Bridging the Gap with Kernel Methods

To bridge the gap between empirical observation and theoretical proof, the authors study kernel least-squares gradient flow. Because wide neural networks in certain regimes (specifically the "lazy training" regime) behave like kernel methods—such as Neural Tangent Kernels (NTKs)—understanding the trajectory of a kernel model provides a tractable, mathematically rigorous proxy for understanding deep learning dynamics.

The core challenge lies in analyzing these dynamics when both the data dimension ($d$) and the number of samples ($n$) are very large. The researchers characterize these dynamics by comparing two distinct scenarios:

  1. The Oracle World: The model is trained on the entire population distribution (representing infinite data).
  2. The Empirical World: The model is trained on a finite, sampled dataset of size $n$.

By using precise high-dimensional asymptotics (letting $d, n \to \infty$), the authors derive exact expressions for the training and test errors over time. They specifically analyze standard dot-product kernels (used for fully connected networks) and group-invariant kernels (which incorporate symmetries like rotations or translations, analogous to CNNs or data augmentation).

The Three-Stage Lifecycle of Learning

A central insight of the paper is that learning is not a smooth, uniform slide to zero error; rather, it occurs in three distinct phases. In high dimensions, kernels learn functions in a "staircase" fashion—first fitting simple degree-1 polynomials, then degree-2, and so on.

Error dynamics over time showing the three distinct stages of learning.
  • Stage 1 (Early Training): The Oracle and Empirical models behave almost identically. Both models focus on learning the simplest, lowest-degree components of the target function (e.g., the linear parts). The empirical training and test errors track closely together.
  • Stage 2 (The Deep Bootstrap): This is the most surprising and counterintuitive phase. The empirical training error plummets toward zero as the model begins to "overfit" the specific samples in the training set. Yet, remarkably, the empirical test error remains almost exactly aligned with the Oracle's test error. The model fits the training data's noise and specific details without degrading its ability to generalize to unseen data.
  • Stage 3 (Late Training & Approximation Error): The Oracle model continues to improve indefinitely as it learns increasingly complex, higher-degree features from the infinite population. However, the Empirical model hits a floor. Its test error plateaus because it has exhausted the statistical information available in its finite $n$ samples, leaving a permanent approximation error gap between the empirical and oracle models.
Function fitting behavior across the three stages, comparing the target, oracle, and empirical models.

Key Results and Implications

Formal Proof of the Deep Bootstrap: The authors provide the first mathematical proof that for a significant portion of training (Stage 2), the "Real World" (empirical) test error perfectly tracks the "Ideal World" (oracle) error. This occurs despite a massive, growing gap between empirical training performance and empirical test performance, formalizing why deep networks can generalize well even when training error drops to near zero.

The Invariance Trade-off: The paper shows that using a kernel aware of data symmetries (an invariant kernel) is mathematically equivalent to having a much larger dataset—specifically, a dataset augmented by the size of the symmetry group. However, there is a catch: these invariant models actually train slower initially.

Numerical simulations, confirmed by the authors' theorems, show that a standard dot-product kernel optimizes faster but ultimately generalizes worse than a cyclic invariant kernel. This serves as a crucial warning for practitioners: "speed of convergence" during early training is not a reliable proxy for a model's final generalization capability.

Limitations and Future Directions

While this framework provides deep insights, it is restricted to the "linear" or "lazy" regime of neural networks where features are fixed at initialization. It does not capture "feature learning," where a network's internal representations adapt significantly to the task.

Additionally, the results rely on the assumption that the data dimension $d$ is uniformly very large. Real-world data often resides on lower-dimensional manifolds, which might alter these exact dynamics. Finally, the study focuses on squared loss for regression; classification tasks using cross-entropy loss might exhibit different late-stage behaviors, as models can continue to improve their decision margins even after training error reaches zero. Extending this rigorous high-dimensional framework to non-linear feature learning and discrete-time SGD remains an exciting frontier for future work.

Summary updated

Abstract

To understand how deep learning works, it is crucial to understand the training dynamics of neural networks. Several interesting hypotheses about these dynamics have been made based on empirically observed phenomena, but there exists a limited theoretical understanding of when and why such phenomena occur. In this paper, we consider the training dynamics of gradient flow on kernel least-squares objectives, which is a limiting dynamics of SGD trained neural networks. Using precise high-dimensional asymptotics, we characterize the dynamics of the fitted model in two “worlds”: in the Oracle World the model is trained on the population distribution and in the Empirical World the model is trained on an i.i.d finite dataset. We show that under mild conditions on the kernel and $L^2$ target regression function the training dynamics have three stages that are based on the behaviors of the models in the two worlds. Our theoretical results also mathematically formalize some interesting deep learning phenomena. Specifically, in our setting we show that SGD progressively learns more complex functions and that there is a "deep bootstrap" phenomenon: during the second stage, the test error of both worlds remain close despite the empirical training error being much smaller. Finally, we give a concrete example comparing the dynamics of two different kernels which shows that faster training is not necessary for better generalization.
BibTeX
@inproceedings{ghosh2022three,
  author = {Nikhil Ghosh and Song Mei and Bin Yu},
  title = {{The Three Stages of Learning Dynamics in High-dimensional Kernel Methods}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=lrpd5PIKj8},
}
Figure