Target alignment in truncated kernel ridge regression

• URL: http://arxiv.org/abs/2206.14255v1
• Date: Tue, 28 Jun 2022 19:16:10 GMT
• Title: Target alignment in truncated kernel ridge regression
• Abstract summary: We study how the alignment between the target function and the kernel affects the performance of the Kernel ridge regression (KRR) We show that for alignment, there is an emphover-aligned regime, in which TKRR can achieve a faster rate than what is achievable by full KRR. We also consider the bandlimited alignment setting and show that the regularization surface of TKRR can exhibit transient effects including multiple descent and non-monotonic behavior.
• Score: 12.139222986297264
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kernel ridge regression (KRR) has recently attracted renewed interest due to its potential for explaining the transient effects, such as double descent, that emerge during neural network training. In this work, we study how the alignment between the target function and the kernel affects the performance of the KRR. We focus on the truncated KRR (TKRR) which utilizes an additional parameter that controls the spectral truncation of the kernel matrix. We show that for polynomial alignment, there is an \emph{over-aligned} regime, in which TKRR can achieve a faster rate than what is achievable by full KRR. The rate of TKRR can improve all the way to the parametric rate, while that of full KRR is capped at a sub-optimal value. This shows that target alignemnt can be better leveraged by utilizing spectral truncation in kernel methods. We also consider the bandlimited alignment setting and show that the regularization surface of TKRR can exhibit transient effects including multiple descent and non-monotonic behavior. Our results show that there is a strong and quantifable relation between the shape of the \emph{alignment spectrum} and the generalization performance of kernel methods, both in terms of rates and in finite samples.

Related papers

• Analysis of Nystrom method with sequential ridge leverage scores [69.32538992633842]
  Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t.<n>Recent works show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for the approximation.<n>We introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates.
  arXiv  Detail & Related papers  (2026-04-22T00:49:25Z)
• KROM: Kernelized Reduced Order Modeling [3.988493458010939]
  KROM formulates PDE solution as a minimum-norm (Gaussian-process) recovery problem in an RKHS.<n>A central ingredient is an empirical kernel constructed from a snapshot library of PDE solutions.
  arXiv  Detail & Related papers  (2026-02-27T22:52:22Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• 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)
• On the Saturation Effects of Spectral Algorithms in Large Dimensions [14.63552944833659]
  Main focus of this paper is to explore the saturation effects for a large class of spectral algorithms in large dimensional settings.<n>We show that the saturation effect occurs in large dimensional setting as long as the source condition $s>tau$ while it occurs in fixed dimensional setting as long as $s>2tau$
  arXiv  Detail & Related papers  (2025-03-01T14:21:38Z)
• Supervised Kernel Thinning [6.6157730528755065]
  kernel thinning algorithm of Dwivedi & Mackey (2024) provides a better-than-i.i.d. compression of a generic set of points. We generalize the KT algorithm to speed up supervised learning problems involving kernel methods.
  arXiv  Detail & Related papers  (2024-10-17T16:48:51Z)
• Have ASkotch: A Neat Solution for Large-scale Kernel Ridge Regression [16.836685923503868]
  ASkotch is a scalable, accelerated, iterative method for full KRR that provably obtains linear convergence. ASkotch outperforms state-of-the-art KRR solvers on a testbed of 23 large-scale KRR regression and classification tasks. Our work opens up the possibility of as-yet-unimagined applications of full KRR across a number of disciplines.
  arXiv  Detail & Related papers  (2024-07-14T04:11:10Z)
• Optimal Rates and Saturation for Noiseless Kernel Ridge Regression [4.585021053685196]
  We present a comprehensive study of Kernel ridge regression (KRR) in the noiseless regime. KRR is a fundamental method for learning functions from finite samples. We introduce a refined notion of degrees of freedom, which we believe has broader applicability in the analysis of kernel methods.
  arXiv  Detail & Related papers  (2024-02-24T04:57:59Z)
• Solving Kernel Ridge Regression with Gradient Descent for a Non-Constant Kernel [1.5229257192293204]
  KRR is a generalization of linear ridge regression that is non-linear in the data, but linear in the parameters. We address the effects of changing the kernel during training, something that is investigated in this paper. We show theoretically and empirically that using a decreasing bandwidth, we are able to achieve both zero training error in combination with good generalization, and a double descent behavior.
  arXiv  Detail & Related papers  (2023-11-03T07:43:53Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation [72.71398034617607]
  KERPLE is a framework that generalizes relative position embedding for extrapolation by kernelizing positional differences. The diversity of CPD kernels allows us to derive various RPEs that enable length extrapolation in a principled way.
  arXiv  Detail & Related papers  (2022-05-20T01:25:57Z)
• Optimally tackling covariate shift in RKHS-based nonparametric regression [43.457497490211985]
  We show that a kernel ridge regression estimator with a carefully chosen regularization parameter is minimax rate-optimal. We also show that a naive estimator, which minimizes the empirical risk over the function class, is strictly sub-optimal. We propose a reweighted KRR estimator that weights samples based on a careful truncation of the likelihood ratios.
  arXiv  Detail & Related papers  (2022-05-06T02:33:24Z)
• Scaling Neural Tangent Kernels via Sketching and Random Features [53.57615759435126]
  Recent works report that NTK regression can outperform finitely-wide neural networks trained on small-scale datasets. We design a near input-sparsity time approximation algorithm for NTK, by sketching the expansions of arc-cosine kernels. We show that a linear regressor trained on our CNTK features matches the accuracy of exact CNTK on CIFAR-10 dataset while achieving 150x speedup.
  arXiv  Detail & Related papers  (2021-06-15T04:44:52Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• Optimal Rates of Distributed Regression with Imperfect Kernels [0.0]
  We study the distributed kernel regression via the divide conquer and conquer approach. We show that the kernel ridge regression can achieve rates faster than $N-1$ in the noise free setting.
  arXiv  Detail & Related papers  (2020-06-30T13:00:16Z)
• Off-the-grid: Fast and Effective Hyperparameter Search for Kernel Clustering [2.304694255100371]
  We study the impact of kernel parameters on kernel $k$-means. In particular, we derive a lower bound, tight up to constant factors, below which the parameter of the RBF kernel will render kernel $k$-means meaningless.
  arXiv  Detail & Related papers  (2020-06-24T08:58:58Z)
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime [50.510421854168065]
  We show that the averaged gradient descent can achieve the minimax optimal convergence rate. We show that the target function specified by the NTK of a ReLU network can be learned at the optimal convergence rate.
  arXiv  Detail & Related papers  (2020-06-22T14:31:37Z)
• 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)

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.