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

Nikhil Ghosh, Song Mei, Bin Yu

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 a sampled dataset. We show that under mild conditions on the kernel and $L^2$ target regression function the training dynamics undergo three stages characterized by 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.

Introduction

While deep learning has achieved remarkable success, a rigorous theoretical understanding of its training dynamics remains elusive. Empirical observations have highlighted phenomena like the "deep bootstrap"—where a model's test performance tracks its performance with infinite data long after it has memorized the training set—and the tendency of networks to learn simple functions before complex ones.

To bridge this gap, this research analyzes gradient flow on kernel least-squares objectives in high-dimensional settings. By focusing on the "Neural Tangent Kernel" (NTK) regime, where wide neural networks approximate linear models in high-dimensional feature spaces, the authors provide a precise mathematical characterization of the entire training trajectory.

The Three-Stage Life Cycle

The core of the paper's contribution is the identification of a distinct three-stage process in learning dynamics. This is analyzed by comparing two parallel scenarios: the Oracle World (trained on the true population distribution) and the Empirical World (trained on a finite dataset).

Schematic of the three stages of learning dynamics, comparing Oracle and Empirical error trajectories.
  1. Stage 1 (Initial Learning): In this early phase, the Oracle and Empirical models behave identically. Both models focus on learning the simplest, most prominent "linear" components of the target function.
  2. Stage 2 (The Deep Bootstrap): This stage is characterized by a divergence in training behavior. While the Empirical model's training error drops rapidly toward zero (memorization), its test error continues to track the Oracle model's performance. This provides a theoretical foundation for the "deep bootstrap" phenomenon: the model continues to learn generalizable features even as it fits the noise in the training data.
  3. Stage 3 (Convergence and Plateau): Eventually, the Empirical model hits a fundamental limit imposed by its finite sample size. While the Oracle model (with infinite data) continues to reduce error by learning increasingly complex features, the Empirical model's test error plateaus at a level determined by the approximation error of the finite dataset.

The Staircase of Functional Complexity

A key insight is that in high dimensions, kernels do not learn functions smoothly. Instead, they learn degree-by-degree in a "staircase" fashion. The model first masters linear approximations, then quadratic, then cubic, and so on.

Numerical validation of the 'staircase' effect, where error drops in discrete steps corresponding to functional complexity levels.

As shown in the figure above, each "step" in the error plot corresponds to the model unlocking a new level of functional complexity, represented by the projection of the target function onto higher-order polynomial spaces ($\|P_{>k} f_d\|^2$). This mathematical formalization confirms that SGD-trained models progressively learn more complex functions over time.

Invariance vs. Training Speed

The research also explores the impact of symmetries, such as cyclic shifts, through Group Invariant Kernels. A counter-intuitive finding is that while encoding these symmetries significantly improves generalization (lower final test error), it actually slows down the training process. This suggests that optimization speed is not always a reliable proxy for model quality; a model that trains slower may ultimately be learning a more robust, invariant representation.

Furthermore, the authors prove a "data augmentation equivalence," showing that using an invariant kernel is mathematically equivalent to training a standard kernel on a massively augmented dataset. This provides a rigorous link between architectural choices (like CNNs) and data-centric strategies.

Conclusion and Future Directions

This work provides a rigorous framework for understanding the temporal evolution of high-dimensional kernel methods. By characterizing the three stages of learning and the staircase effect, it offers a theoretical lens through which to view empirical deep learning phenomena.

However, several avenues for future work remain. The current analysis is situated in the NTK/linear regime, which does not account for "feature learning" where internal representations evolve. Additionally, extending these results from square loss to cross-entropy loss and from continuous gradient flow to discrete-time SGD would further align the theory with practical deep learning applications.

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 a sampled dataset. We show that under mild conditions on the kernel and $L^2$ target regression function the training dynamics undergo three stages characterized by 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