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

• URL: http://arxiv.org/abs/2510.04780v1
• Date: Mon, 06 Oct 2025 12:58:35 GMT
• Title: Kernel ridge regression under power-law data: spectrum and generalization
• Authors: Arie Wortsman, Bruno Loureiro,
• Abstract summary: We investigate high-dimensional kernel ridge regression (KRR) on i.i.d. Gaussian data with anisotropic power-law covariance.<n>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.<n>To our knowledge, this is the first rigorous treatment of non-linear KRR under power-law data.
• Score: 10.479735444470535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel [55.82768375605861]
  We establish a generalization bound for gradient flow that aligns with the classical Rademacher complexity for kernel methods.<n>Unlike static kernels such as NTK, the LPK captures the entire training trajectory, adapting to both data and optimization dynamics.
  arXiv  Detail & Related papers  (2025-06-12T23:17:09Z)
• A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression [6.749750044497731]
  This paper conducts a comprehensive study of the learning curves of kernel ridge regression (KRR) under minimal assumptions. We analyze the role of key properties of the kernel, such as its spectral eigen-decay, the characteristics of the eigenfunctions, and the smoothness of the kernel.
  arXiv  Detail & Related papers  (2024-10-23T11:52:52Z)
• Highly Adaptive Ridge [84.38107748875144]
  We propose a regression method that achieves a $n-2/3$ dimension-free L2 convergence rate in the class of right-continuous functions with square-integrable sectional derivatives. Har is exactly kernel ridge regression with a specific data-adaptive kernel based on a saturated zero-order tensor-product spline basis expansion. We demonstrate empirical performance better than state-of-the-art algorithms for small datasets in particular.
  arXiv  Detail & Related papers  (2024-10-03T17:06:06Z)
• Universality of Kernel Random Matrices and Kernel Regression in the Quadratic Regime [11.655527064124074]
  In this work, we extend the study of kernel regression to the quadratic regime, where $n asymp d2$.<n>Specifically, we establish an operator norm approximation bound for the difference between the original kernel random matrix and a quadratic kernel random matrix.<n>We characterize the precise training and test errors for KRR in the quadratic regime when $n/d2$ converges to a non-zero constant.
  arXiv  Detail & Related papers  (2024-08-02T07:29:49Z)
• High-Dimensional Kernel Methods under Covariate Shift: Data-Dependent Implicit Regularization [83.06112052443233]
  This paper studies kernel ridge regression in high dimensions under covariate shifts. By a bias-variance decomposition, we theoretically demonstrate that the re-weighting strategy allows for decreasing the variance. For bias, we analyze the regularization of the arbitrary or well-chosen scale, showing that the bias can behave very differently under different regularization scales.
  arXiv  Detail & Related papers  (2024-06-05T12:03:27Z)
• Learning Analysis of Kernel Ridgeless Regression with Asymmetric Kernel Learning [33.34053480377887]
  This paper enhances kernel ridgeless regression with Locally-Adaptive-Bandwidths (LAB) RBF kernels. For the first time, we demonstrate that functions learned from LAB RBF kernels belong to an integral space of Reproducible Kernel Hilbert Spaces (RKHSs)
  arXiv  Detail & Related papers  (2024-06-03T15:28:12Z)
• Kernel Identification Through Transformers [54.3795894579111]
  Kernel selection plays a central role in determining the performance of Gaussian Process (GP) models. This work addresses the challenge of constructing custom kernel functions for high-dimensional GP regression models. We introduce a novel approach named KITT: Kernel Identification Through Transformers.
  arXiv  Detail & Related papers  (2021-06-15T14:32:38Z)
• How rotational invariance of common kernels prevents generalization in high dimensions [8.508198765617196]
  Kernel ridge regression is well-known to achieve minimax optimal rates in low-dimensional settings. Recent work establishes consistency for kernel regression under certain assumptions on the ground truth function and the distribution of the input data.
  arXiv  Detail & Related papers  (2021-04-09T08:27:37Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees. Our approach leads to significantly better bounds for datasets with known rates of singular value decay. We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
  arXiv  Detail & Related papers  (2020-02-21T00:43:06Z)
• Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks [17.188280334580195]
  We derive analytical expressions for the generalization performance of kernel regression as a function of the number of training samples. Our expressions apply to wide neural networks due to an equivalence between training them and kernel regression with the Neural Kernel Tangent (NTK) We verify our theory with simulations on synthetic data and MNIST dataset.
  arXiv  Detail & Related papers  (2020-02-07T00:03:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.