In modern machine learning, we often operate in regimes where the data dimension ($d$) is comparable to or even larger than the number of samples ($n$). While classical statistics often treats $d$ as fixed, this high-dimensional reality introduces unique behaviors in learning algorithms. A prominent example is the "saturation effect"—a performance ceiling that certain algorithms hit even when the underlying target function is perfectly smooth.
This paper, presented at NeurIPS 2024, provides a rigorous theoretical framework to explain when and why spectral algorithms like Kernel Ridge Regression (KRR) and Gradient Flow succeed or fail as dimensions scale.
The Problem: High-Dimensional Saturation
Saturation occurs when an algorithm cannot leverage the extra smoothness of a target function to reduce error more quickly. In fixed dimensions, KRR is known to saturate when the smoothness ($s$) of the target function exceeds 2. However, this paper demonstrates that in high dimensions, the wall is hit much earlier.
Specifically, for spectral algorithms defined by a "qualification" parameter $ au$, saturation occurs as soon as $s > au$. Since KRR typically has a qualification of $ au=1$, it fails to achieve optimal error rates for even moderately smooth functions in the high-dimensional regime ($n \asymp d^\gamma$).
Visualizing the Performance Gap
The authors use numerical experiments on synthetic spherical data to validate their theoretical findings. By comparing the excess risk of kernel methods against the minimax optimal rate, the saturation effect becomes clearly visible as the smoothness parameter $s$ increases relative to the algorithm's qualification $ au$.
Key Insights and Theoretical Contributions
1. Gradient Flow as a Universal Winner
Unlike KRR, Gradient Flow (GF) with early stopping possesses an infinite qualification ($\tau = \infty$). The authors prove that GF never saturates and remains minimax optimal across all smoothness levels. This makes GF theoretically superior to KRR for learning very smooth functions in high dimensions.
2. The "Staircase" Error Decay
One of the most striking findings is that error does not decrease smoothly. Instead, the error curve follows a staircase pattern. The risk remains on a plateau until the number of samples $n$ reaches a threshold ($d^k$) sufficient to resolve the next degree of polynomial approximation, at which point the error drops sharply.
3. A Unified Error Formula
The paper provides a single, powerful formula (Theorem 1.1) that predicts the convergence rate for any spectral algorithm based on three variables:
- Qualification ($\tau$): The algorithm's inherent capacity to handle smoothness.
- Data Scaling ($\gamma$): The polynomial relationship between samples and dimension ($n \asymp d^\gamma$).
- Smoothness ($s$): The regularity of the target function.
Methodology
The analysis focuses on inner product kernels on a hypersphere (such as RBF or Neural Tangent Kernels). By leveraging the mathematics of spherical harmonics and analytic functional calculus, the researchers derived exact asymptotic rates for excess risk. They also established a new, tighter minimax lower bound that serves as the ultimate benchmark for algorithmic optimality in high dimensions.
Conclusion and Future Directions
This work clarifies the "lazy regime" of neural network training by connecting it to the behavior of kernel methods. While the current theory relies on the symmetry of the hypersphere and uniform distributions, it sets the stage for future research into more complex data manifolds. The findings suggest that for high-dimensional tasks involving smooth target functions, practitioners should favor algorithms with high qualification, like Gradient Flow, over traditional Ridge Regression to avoid premature performance plateaus.
Summary updated