Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regime

• URL: http://arxiv.org/abs/2205.06798v1
• Date: Fri, 13 May 2022 17:50:54 GMT
• Title: Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regime
• Authors: Hong Hu and Yue M. Lu
• Abstract summary: kernel ridge regression (KRR) exhibits a multi-phased pattern that crucially depends on the scaling relationship between the sample size $n$ and the underlying dimension $d$. We show that the learning curves of KRR can have a delicate "double descent" behavior due to specific bias-variance trade-offs at different scaling regimes.
• Score: 22.58196673815647
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The generalization performance of kernel ridge regression (KRR) exhibits a multi-phased pattern that crucially depends on the scaling relationship between the sample size $n$ and the underlying dimension $d$. This phenomenon is due to the fact that KRR sequentially learns functions of increasing complexity as the sample size increases; when $d^{k-1}\ll n\ll d^{k}$, only polynomials with degree less than $k$ are learned. In this paper, we present sharp asymptotic characterization of the performance of KRR at the critical transition regions with $n \asymp d^k$, for $k\in\mathbb{Z}^{+}$. Our asymptotic characterization provides a precise picture of the whole learning process and clarifies the impact of various parameters (including the choice of the kernel function) on the generalization performance. In particular, we show that the learning curves of KRR can have a delicate "double descent" behavior due to specific bias-variance trade-offs at different polynomial scaling regimes.

Related papers

• 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)
• Universality of kernel random matrices and kernel regression in the quadratic regime [18.51014786894174]
  In this work, we extend the study of kernel kernel regression to the quadratic regime. We establish an operator norm approximation bound for the difference between the original kernel random matrix and a quadratic kernel random matrix. We characterize the precise training and generalization errors for KRR in the quadratic regime when $n/d2$ converges to a nonzero constant.
  arXiv  Detail & Related papers  (2024-08-02T07:29:49Z)
• Scaling and renormalization in high-dimensional regression [72.59731158970894]
  This paper presents a succinct derivation of the training and generalization performance of a variety of high-dimensional ridge regression models. We provide an introduction and review of recent results on these topics, aimed at readers with backgrounds in physics and deep learning.
  arXiv  Detail & Related papers  (2024-05-01T15:59:00Z)
• Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime [22.666759017118796]
  Recent advances in machine learning have been achieved by using overparametrized models trained until near the training data. How does model complexity and generalization depend on the number of parameters $p$? In particular, RFRR exhibits an intuitive trade-off between approximation and generalization power.
  arXiv  Detail & Related papers  (2024-03-13T00:59:25Z)
• Overparameterized random feature regression with nearly orthogonal data [21.97381518762387]
  We study the non-asymptotic behaviors of the random feature ridge regression (RFRR) given by a two-layer neural network. Our results hold for a wide variety of activation functions and input data sets that exhibit nearly deterministic properties.
  arXiv  Detail & Related papers  (2022-11-11T09:16:25Z)
• Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regression [41.48538038768993]
  We focus on the problem of kernel ridge regression for dot-product kernels. We observe a peak in the learning curve whenever $m approx dr/r!$ for any integer $r$, leading to multiple sample-wise descent and nontrivial behavior at multiple scales.
  arXiv  Detail & Related papers  (2022-05-30T04:21:31Z)
• 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)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)
• Kernel and Rich Regimes in Overparametrized Models [69.40899443842443]
  We show that gradient descent on overparametrized multilayer networks can induce rich implicit biases that are not RKHS norms. We also demonstrate this transition empirically for more complex matrix factorization models and multilayer non-linear networks.
  arXiv  Detail & Related papers  (2020-02-20T15:43:02Z)

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.