Spectrally-truncated kernel ridge regression and its free lunch

Arash A. AminiarXiv 2019 · OpenReview

TL;DR

This paper introduces a simple yet powerful approximation for Kernel Ridge Regression (KRR) by spectrally truncating the kernel matrix. Surprisingly, this truncation not only maintains optimal statistical performance but can actually improve it over the full KRR for finite sample sizes, offering a "free lunch" in terms of reduced risk.

What Problem Does This Paper Address?

Kernel Ridge Regression (KRR) is a highly effective nonparametric regression technique, known for its ability to achieve optimal rates of convergence when estimating functions within Reproducing Kernel Hilbert Spaces (RKHS). However, its practical application is severely hampered by computational costs. Specifically, KRR requires operations on an $n \times n$ kernel matrix, where $n$ is the number of data points. This leads to cubic time complexity ($O(n^3)$) for solving the problem, making it infeasible for large datasets. While various approximation methods like Nyström and sketching exist, this paper focuses on the most direct approximation: spectral truncation.

Methods

The core of this paper is the analysis of spectrally-truncated KRR (ST-KRR). This method involves:

  1. Eigenvalue Decomposition: Computing the eigenvalue decomposition of the $n \times n$ kernel matrix $K$.
  2. Truncation: Keeping only the top $r$ largest eigenvalues and their corresponding eigenvectors, effectively creating a rank-$r$ approximation of $K$.
  3. Regularized Regression: Solving the KRR problem using this truncated kernel matrix and a regularization parameter $\lambda$.

The authors derive an exact expression for the maximum (worst-case) mean-squared error (MSE) of ST-KRR over the unit ball of the RKHS. This allows for a precise study of the trade-off between the truncation level $r$ and the regularization parameter $\lambda$. They then analyze this expression to understand the statistical implications of spectral truncation.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic data for simulations.

Key Insights and Ideas

  • The "Free Lunch" of Truncation: The most striking finding is that for a sufficiently large truncation level $r$, ST-KRR can achieve a strictly smaller minimax risk than the full KRR. This means that by simplifying the problem (truncating the kernel), we can actually get a statistically better estimator, not just a computationally faster one.
  • Optimal Truncation Level: There exists an optimal truncation level $r_n$ such that for any $r \ge r_n$, the ST-KRR is statistically superior to the full KRR (provided the eigenvalues don't all decay to zero). This suggests that for large datasets, it's not just computationally beneficial but statistically optimal to truncate.
  • Truncation vs. $\lambda$-Regularization: Spectral truncation provides an implicit form of regularization. However, the paper clarifies that this is not a substitute for explicit $\lambda$-regularization (Hilbert norm regularization). Both are necessary to achieve the best possible performance.
  • Trade-off Analysis: The exact MSE expression allows for a detailed understanding of the trade-off between the degree of truncation ($r$) and the regularization strength ($\lambda$). This is crucial for practitioners to select optimal parameters.

Key Results

  • An exact expression for the worst-case MSE of ST-KRR is derived, depending on kernel eigenvalues, $\lambda$, $r$, and noise level $\sigma^2$.
  • For infinite-dimensional RKHSs, there's a threshold $r_n$ above which ST-KRR outperforms full KRR in terms of minimax risk.
  • Numerical simulations (Figure 1) demonstrate that the optimally truncated KRR achieves a lower maximum theoretical MSE and typical empirical MSE compared to the full KRR for both Gaussian and Sobolev-1 kernels.
  • The paper shows that even with spectral truncation, the optimal regularization parameter $\lambda$ is always positive, confirming the need for both forms of regularization.

Limitations and Future Work

  • Finite Sample vs. Asymptotic: While the paper shows improvement for finite samples, asymptotic analysis might reveal different behaviors.
  • Computational Complexity of EVD: The paper mentions that computing the top $r$ eigenpairs of $K$ can be computationally intensive (e.g., $O(n^2(r+\log n))$ on average for Lanczos). While ST-KRR is simpler than full KRR, its initial step still requires this computation. Future work could explore faster ways to obtain these top eigenpairs or alternative truncation strategies.
  • Generalization to Other Kernels/Spaces: The analysis is primarily for RKHSs and specific kernels. Extending these findings to broader function spaces or different kernel approximation methods would be valuable.
  • Practical Implementation: While the theory is strong, practical implementation details for very large $n$ might require further investigation into efficient EVD algorithms or approximations thereof.

Summary updated

Abstract

Kernel ridge regression (KRR) is a well-known and popular nonparametric regression approach with many desirable properties, including minimax rate-optimality in estimating functions that belong to common reproducing kernel Hilbert spaces (RKHS). The approach, however, is computationally intensive for large data sets, due to the need to operate on a dense $n \times n$ kernel matrix, where $n$ is the sample size. Recently, various approximation schemes for solving KRR have been considered, and some analyzed. Some approaches such as Nystr\"{o}m approximation and sketching have been shown to preserve the rate optimality of KRR. In this paper, we consider the simplest approximation, namely, spectrally truncating the kernel matrix to its largest $r < n$ eigenvalues. We derive an exact expression for the maximum risk of this truncated KRR, over the unit ball of the RKHS. This result can be used to study the exact trade-off between the level of spectral truncation and the regularization parameter. We show that, as long as the RKHS is infinite-dimensional, there is a threshold on $r$, above which, the spectrally-truncated KRR surprisingly outperforms the full KRR in terms of the minimax risk, where the minimum is taken over the regularization parameter. This strengthens the existing results on approximation schemes, by showing that not only one does not lose in terms of the rates, truncation can in fact improve the performance, for all finite samples (above the threshold). Moreover, we show that the implicit regularization achieved by spectral truncation is not a substitute for Hilbert norm regularization. Both are needed to achieve the best performance.
BibTeX
@misc{amini2019spectrally,
  author = {Arash A. Amini},
  title = {{Spectrally-truncated kernel ridge regression and its free lunch}},
  year = {2019},
  eprint = {1906.06276},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.06276},
}
Figure