On Kernel Eigen-alignments of KRR: Reconstruction and Generalization

• URL: http://arxiv.org/abs/2605.15240v1
• Date: Thu, 14 May 2026 05:46:31 GMT
• Title: On Kernel Eigen-alignments of KRR: Reconstruction and Generalization
• Abstract summary: We establish a direct connection between generalization performance in kernel methods and the estimation of eigenvectors and eigenvalues of matrices.<n>We show that strong generalization requires increasing eigenvector alignment, eigenvalue magnitude, or gaps between consecutive eigenvalues.
• Score: 3.344730946122235
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: This paper investigates the critical role of eigenalignments between the kernel matrix and learning targets in achieving robust generalization in learning problems. We establish a direct connection between generalization performance in kernel methods and the estimation of eigenvectors and eigenvalues of matrices, offering a more intuitive understanding compared to prior work with minimal assumptions. We also show that, since the prediction task in KRR is essentially the weighted sum of eigenvectors/singular vectors, by analyzing how much error can be caused by perturbations to the kernel matrix, we can then derive a bound on this generalization error using the estimation stability of matrix eigenvalues and eigenvectors. Compared with previous work, our analysis concentrates on finite-sample settings and on the generalization error arising from having a suboptimal finite training set. Our findings reveal that in kernel methods, as long as the kernel is of high rank, the near-zero reconstruction error can be trivially obtained, implying that the reconstruction error will have limited predictive power for generalization. Finally, we establish a generalization bound from an eigenvalues/eigenvectors estimation perspective, showing that strong generalization requires increasing eigenvector alignment, eigenvalue magnitude, or gaps between consecutive eigenvalues.

Related papers

• Spectral Analysis of the Weighted Frobenius Objective [2.7857707184602165]
  We analyze a weighted Frobenius loss for approxingimating symmetric definite matrices in the context of preconditioning iterative solvers.<n>Our analysis reveals that each eigenmode is scaled by the corresponding square of its eigenvalue, and that, under a fixed error budget, the loss is minimized only when the error is confined to the direction of the largest eigenvalue.
  arXiv  Detail & Related papers  (2025-09-20T19:15:24Z)
• Resolvent-based quantum phase estimation: Towards estimation of parametrized eigenvalues [0.0]
  We propose a novel approach for estimating the eigenvalues of non-normal matrices.<n>We construct the first efficient algorithm for estimating the phases of the unimodular eigenvalues of a given non-unitary matrix.<n>We then construct an efficient algorithm for estimating the real eigenvalues of a given non-Hermitian matrix.
  arXiv  Detail & Related papers  (2024-10-07T08:51:05Z)
• 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)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  This work takes the first step toward understanding the inductive bias of the minimum trace of the Hessian solutions in deep linear networks. We show that for all depth greater than one, with the standard Isometry Property (RIP) on the measurements, minimizing the trace of Hessian is approximately equivalent to minimizing the Schatten 1-norm of the corresponding end-to-end matrix parameters.
  arXiv  Detail & Related papers  (2023-06-22T23:14:57Z)
• Fine-grained Generalization Analysis of Vector-valued Learning [28.722350261462463]
  We start the generalization analysis of regularized vector-valued learning algorithms by presenting bounds with a mild dependency on the output dimension and a fast rate on the sample size. To understand the interaction between optimization and learning, we further use our results to derive the first bounds for descent with vector-valued functions. As a byproduct, we derive a Rademacher complexity bound for loss function classes defined in terms of a general strongly convex function.
  arXiv  Detail & Related papers  (2021-04-29T07:57:34Z)
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps [95.62172085878132]
  Eigenvector perturbation analysis plays a vital role in various statistical data science applications. We develop a suite of statistical theory that characterizes the perturbation of arbitrary linear functions of an unknown eigenvector. In order to mitigate a non-negligible bias issue inherent to the natural "plug-in" estimator, we develop de-biased estimators.
  arXiv  Detail & Related papers  (2021-04-07T17:55:10Z)
• 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)
• A simpler spectral approach for clustering in directed networks [1.52292571922932]
  We show that using the eigenvalue/eigenvector decomposition of the adjacency matrix is simpler than all common methods. We provide numerical evidence for the superiority of the Gaussian Mixture clustering over the widely used k-means algorithm.
  arXiv  Detail & Related papers  (2021-02-05T14:16:45Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  We develop a relative error bound for nuclear norm regularized matrix completion. We derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix.
  arXiv  Detail & Related papers  (2015-04-26T13:12:16Z)

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.