Kernel ridge regression under power-law data: spectrum and generalization

2025/10/06 by Arie Wortsman, Wortsman, Arie, Bruno Loureiro +1 · 2 citations
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Gaussian Processes and Bayesian Inference #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2510.04780

Abstract

In this work, we investigate high-dimensional kernel ridge regression (KRR) on i.i.d. Gaussian data with anisotropic power-law covariance. This setting differs fundamentally from the classical source & capacity conditions for KRR, where power-law assumptions are typically imposed on the kernel eigen-spectrum itself. Our contributions are twofold. First, we derive an explicit characterization of the kernel spectrum for polynomial inner-product kernels, giving a precise description of how the kernel eigen-spectrum inherits the data decay. Second, we provide an asymptotic analysis of the excess risk in the high-dimensional regime for a particular kernel with this spectral behavior, showing that the sample complexity is governed by the effective dimension of the data rather than the ambient dimension. These results establish a fundamental advantage of learning with power-law anisotropic data over isotropic data. To our knowledge, this is the first rigorous treatment of non-linear KRR under power-law data.

Citations

• Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime
• On learning Gaussian multi‐index models with gradient flow part I: General properties and two‐timescale learning
• Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law
• Emergence and scaling laws in SGD learning of shallow neural networks
• Universality of Kernel Random Matrices and Kernel Regression in the Quadratic Regime
• Scaling Laws in Linear Regression: Compute, Parameters, and Data
• Dimension-free deterministic equivalents and scaling laws for random feature regression
• 4+3 Phases of Compute-Optimal Neural Scaling Laws
• Scaling and renormalization in high-dimensional regression
• Nonlinear spiked covariance matrices and signal propagation in deep neural networks
• A Dynamical Model of Neural Scaling Laws
• Gradient-Based Feature Learning under Structured Data
• Nonparametric Linear Feature Learning in Regression Through Regularisation
• A Solvable Model of Neural Scaling Laws
• Dimension free ridge regression
• An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings
• Failure and success of the spectral bias prediction for Kernel Ridge Regression: the case of low-dimensional data
• How rotational invariance of common kernels prevents generalization in high dimensions
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration
• Asymptotics of Ridge (less) Regression under General Source Condition
• Language Models are Few-Shot Learners
• Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks
• Scaling Laws for Neural Language Models
• The generalization error of random features regression: Precise asymptotics and double descent curve
• The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve
• Linearized two-layers neural networks in high dimension
• Learning with SGD and Random Features
• Deep Neural Networks as Gaussian Processes
• Generalization Properties of Learning with Random Features
• The Spectral Norm of Random Inner-Product Kernel Matrices
• On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions
• The Spectrum of Random Inner-product Kernel Matrices
• A theory for multiresolution signal decomposition: the wavelet representation

Cited by

• Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data
• Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval

Related

• A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression
• Kernel regression in high dimensions: Refined analysis beyond double descent
• A Geometrical Analysis of Kernel Ridge Regression and its Applications
• Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regime
• Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression