Learning between the peaks: sharp asymptotics for kernel ridge regression under power-law anisotropy
Authors: Lorenzo Rizzi, Arie Wortsman Zurich, Bruno Loureiro
Organizations: Departement d’Informatique, École Normale Supérieure, PSL & CNRS · Dipartimento di Fisica e Astronomia, Università degli Studi di Padova · Scuola Galileiana di Studi Superiori, Università degli Studi di Padova
We study kernel ridge regression under anisotropic Gaussian data, where the input covariance decays as a power law with exponent α≥0 for polynomial inner-product kernels. We derive asymptotically sharp expressions for the kernel spectrum and the generalization error in the polynomial high-dimensional regime n=Θ(dκ), revealing how anisotropy reshapes the learning curves. For weak anisotropy (0<α<1), the problem remains effectively high-dimensional and retains some features of the isotropic case, while departing from it in others: the variance still peaks at integer sample complexities κ∈N, but these peaks are progressively damped as α grows; meanwhile, for targets strongly aligned with the data's principal directions, the bias drops at fractional sample complexities, decoupling the bias transitions from the interpolation peaks. For strong anisotropy (α>1), the effective dimension of the problem is constant, and the variance stops depending on sample size altogether, plateauing under ridgeless interpolation or vanishing at an explicit rate under fixed ridge penalty. The bias undergoes a sharp transition governed by the target's decay rate: below a threshold, learning is abrupt rather than gradual; above it, the bias decays as a power law that recovers the classical source and capacity rates. We finally specialize these results to single-index targets, showing how the alignment of the index with the data's principal directions determines the effect of anisotropy on learning. Together, our results clarify how the input geometry shapes the kernel features and fundamentally impacts its generalization properties.
Figures & tables
Figure 1: Numerical illustration of the asymptotic variance of KRR. We use a null target function ( f⋆=0 ) to isolate the variance component of the risk. The experimental parameters are h(t)=1+8t+3t2+0.1t3+t4 , λ=0 , ψ=0.8 and σε2=1.52 . ( Left ) For fractional sample complexity ( κ=0.7 ), the empirical variance vanishes. The curve matches the theoretical power-law decay rate predicted by Eq. ( 4.10 ) (dashed line). ( Right ) For integer sample complexity, the variance instead plateaus to a finite, order-one constant given by Eq. ( 4.8 ).
Figure 2: Behaviour of τ as a function of input covariance power-law exponent α∈[0,1) , obtained by numerically solving the Kernel state lemma 4.1 . (Left) Different sample complexities n=ψdκ with ψ∈{0.1,2,4,5,10} , in the interpolation limit ( λ=0 ). (Right) Different regularization strengths λ∈{0,0.1,0.5,1,5} at fixed sample complexity ( ψ=2 ). In both figures, we take κ=2 ( n=ψd2 ) under the fourth-order truncated exponential kernel h(t)=∑j=04tj/j! .
Figure 3: Deterministic equivalent of the variance as a function of the sample complexity for κ=2 , σε=4 and polynomial kernel h(t)=1+t+21t2+61t3+241t4 . ( Left ) Fixed λ=0 for different values of anisotropy. The inset shows the variance curve for a fixed ψ=2 ; ( Right ) Fixed α=0.5 for different regularization λ . As expected, stronger regularization suppresses the variance.
Figure 4: Residual bias η as a function of the sample complexity ψ for α=0.5 , κ=2 , σε=4 and polynomial kernel h(t)=1+t+21t2+61t3+241t4 , evaluated by solving eqs. eq. 4.6 , ( 4.8 ), and ( 4.18 ). ( Left ) Varying ω for fixed λ=0 . The inset shows a cross-section of η as a function of ω at a fixed load ψ=1.0 , highlighting how a stronger target anisotropy accelerates the learning of the κ -th shell. ( Right ) Fixed ω=0.25 for varying ridge λ . As expected, regularization increases the bias.
Figure 5: Schematic learning curves for the bias Bn in the weakly anisotropic regime, comparing different target functions with different ω but same energies E(m) and fixed power-law exponent α=0.25 . When ω<1/2 , polynomial features are still learned at integer transitions κ∈N . However, higher value of ω causes the κ -th sector to be learned more rapidly. When ω>1/2 , the model can learn higher-order features at fractional scaling exponents κ=m(1−α)=0.75m . This accelerates the learning process: for example, given a sample size n=O(d2−ϵ) , the isotropic model has only learned the linear part of the target, whereas the anisotropic model can learn a fraction of the quadratic components of the target.
Figure 6: Schematic learning curves for the excess risk in the weakly anisotropic regime ( α<1 ). The figure compares a target function with a slow decay 0<ω<21 (top panel) and a fast decay ω>21 (bottom panel) against the isotropic baseline ( ω=0 ). Solid lines represent the total excess risk, dashed lines indicate the bias contribution, and dotted lines show the variance. ( Top ): For 0<ω<21 , the variance peaks exactly at integer polynomial scaling ( n≍dm ), in-phase with the resolution of new polynomial features. Here, the target decay ω accelerates the learning of the active κ -th shell. ( Bottom ): For ω>21 , a decoupling occurs. The bias drops at fractional scales n≍dm(1−α) , while the variance continues to peak at integer scalings.
Figure 7: Schematic learning curves for the bias B in the strongly anisotropic regime. ( Top ) 0≤ω<1/2 : In the ridgeless limit ( λ=0 , red), learning is instantaneous and occurs abruptly at n=Θ(dm+ϵ) . In the regularized regime ( λ=Θ(1) , orange), the ridge penalty shifts the activation of the m -th shell to a further delayed sample complexity n=Θ(dmα) . ( Bottom ) ω>1/2 : The bias collapses to zero as a power-law (using λ=0 ). Below the critical threshold ω<α+1/2 (light and forest green), the learning rate continuously accelerates as the target energy compresses. Once the threshold is crossed at ω=α+1/2 (dark green, red), the asymptotic decay rate saturates to −2κ
Figure 8: Phase diagram summarizing the asymptotic bias Bn in the ridgeless limit ( λ=0 ), highlighting the various regimes as α (data anisotropy) and ω (target decay rate) are varied. The red dashed lines represent the critical values where new qualitative behaviours appear.
Figure 9: Mapping of the various Single-Index Model (SIM) scenarios onto the general phase diagram of Fig. 8 , assuming λ=0 . Power-law single-index models (PL-SIMs) with target decay γ yield an effective decay rate ω=2α+γ , translating into a series of diagonal lines that intersect the different generalization regimes. The sparse SIM limit ( j=1 ) corresponds to ω→∞ , while the perfectly delocalized scenario is captured by ω=α/2 .
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 10: Asymptotic behavior of the integration boundaries ymin and ymax derived in Eqs. ( D.7 ). Notably, when m=κ or m=1−ακ∈N , the respective boundary converges to a strictly positive, macroscopic constant Θd(1) .
Figure 11: Finite-size scaling of the variance learning curve. The empirical variance Vn is plotted as a function of the load parameter ψ=n/dκ for varying system dimensions d (blue gradients). As the dimension increases, the empirical realizations progressively collapse onto the asymptotic theoretical prediction (black dashed line) derived from our state equations in Theorem 1 . Fixed parameters: κ=1 , α=0.3 , and σε=2 , h(t)=1+8t+3t2+0.1t3+t4 , λ=0 , ψ=0.8
Figure 12: Asymptotic behavior of the integration boundaries ymin and ymax derived in Eqs. ( E.33 ). At variance with Fig. 10 , when m=κ the respective boundary does not converge to a constant Θ(1) due to the diverging factor f(d) .
Figure 13: Kernel spectrum (left panel) and cumulative target function comparison (right panel) for different values of α . In the left panel, we observe that the asymptotic theoretical spectrum obtained from Eq. ( 3.4 ) closely matches the spectrum empirically extracted via empirical diagonalization. In the right panel, we see that the cumulative curves A(u) computed on the Hermite basis and on the kernel eigenbasis are in close agreement. Simulation parameter: d=35 , polynomial kernel k(x,x′)=(2+⟨x,x′⟩)3 , random index v . The empirical diagonalization was performed using M=10000 Monte-Carlo samples
Figure 14: Left: Asymptotic versus empirical bias for a sparse SIM in the weakly anisotropic regime. Right: Asymptotic versus empirical bias for a sparse SIM in the strongly anisotropic regime. Simulation parameters: exponential kernel truncated at the fourth order, κ=1 , ψ=0.8 . Each empirical KRR run is repeated 20 times and averaged, with errors representing the standard deviations.
Figure 15: Left: Asymptotic versus empirical bias for a power-law SIM in the weakly anisotropic regime with an effective ω<0.5 . Right: Asymptotic versus empirical bias for a power-law SIM in the weakly anisotropic regime for an effective ω>0.5 . The link function g is chosen such that its expansion is truncated at degree 3 ( g(t)=∑m=03gmHem(t) ), allowing the kernel to fully learn it in the ω>21 regime. All other parameters match those of Fig. 14 .
Figure 16: Left: Asymptotic versus empirical bias for a power-law SIM in the strongly anisotropic regime when ω>α+21 . Right: Asymptotic versus empirical bias for a power-law SIM in the strongly anisotropic regime when ω<α+21 . All other parameters match those of Fig. 14 .
We study kernel regression with common rotation-invariant kernels on real datasets including CIFAR-5m, SVHN, and ImageNet. We give a theoretical framework that predicts learning curves (test risk vs. sample size) from only two measurements: the empirical data covariance matrix and an empirical polynomial decomposition of the target function f∗. The key new idea is an analytical approximation of a kernel's eigenvalues and eigenfunctions with respect to an anisotropic data distribution. The eigenfunctions resemble Hermite polynomials of the data, so we call this approximation the Hermite eigenstructure ansatz (HEA). We prove the HEA for Gaussian data, but we find that real image data is often "Gaussian enough" for the HEA to hold well in practice, enabling us to predict learning curves by applying prior results relating kernel eigenstructure to test risk. Extending beyond kernel regression, we empirically find that MLPs in the feature-learning regime learn Hermite polynomials in the order predicted by the HEA. Our HEA framework is a proof of concept that an end-to-end theory of learning which maps dataset structure all the way to model performance is possible for nontrivial learning algorithms on real datasets.
Recent studies have reported saturation effects and multiple descent behavior in large dimensional kernel ridge regression (KRR). However, these findings are predominantly derived under restrictive settings, such as inner product kernels on sphere or strong eigenfunction assumptions like hypercontractivity. Whether such behaviors hold for other kernels remains an open question. In this paper, we establish a broad, new family of large dimensional kernels and derive the corresponding convergence rates of the generalization error. As a result, we recover key phenomena previously associated with inner product kernels on sphere, including: i) the minimax optimality when the source condition s≤1; ii) the saturation effect when s>1; iii) a periodic plateau phenomenon in the convergence rate and a multiple-descent behavior with respect to the sample size n.
Yang Zhou, Yicheng Li, Yuqian Cheng +1
Department of Statistics and Data Science Tsinghua University Beijing, 100084, China · Department of Mathematical Science Tsinghua University Beijing, 100084, China
Random features provide a standard approach to scaling kernel methods to large datasets by approximating the kernel with a finite-dimensional feature map. Existing works of random feature methods primarily focus on well-specified models and light-tailed noise conditions, leaving a gap in understanding their performance under more general conditions, such as misspecified models and heavy-tailed noise. In this paper, we provide a comprehensive and improved analysis of kernel ridge regression with random features (KRR-RF) under general conditions. In the light-tailed noise setting, we improve upon the worst-case uniform bounds of the feature map used in the previous works and lead to the minimax optimal learning rates with 2r+γ>α0, where (r,γ,α0) denote the regularity of the target function, the effective dimension of the kernel, and the embedding index of the RKHS, respectively. In the heavy-tailed noise setting, we leverage a recently developed Hilbert-valued Fuk-Nagaev inequality and extend the same optimal results under finite weak moment conditions. The additional cost to achieve robustness is a mildly stronger explicit sample-size requirement than in the light-tailed case. For both settings, our results recover the conditions random features budgets (up to log factors) required in the previous works. In the most benign case when α0=γ, KRR-RF are minimax optimal for all r∈(0,1]. To the best of our knowledge, this is the first work to establish optimal learning rates for KRR-RF under weak moment conditions in the misspecified setting. Numerical experiments and a real data analysis validate the derived learning rates and demonstrate their practical relevance in the presence of mis-specification and heavy-tailed noise.
Caixing Wang
School of Statistics and Data Science, Southeast University, Nanjing, China