We consider learning an unknown target function $f_*$ using kernel ridge
regression (KRR) given i.i.d. data $(u_i,y_i)$, $i\leq n$, where $u_i \in U$ is
a covariate vector and $y_i = f_* (u_i) +\varepsilon_i \in \mathbb{R}$. A
recent string of work has empirically shown that the test error of KRR can be
well approximated by a closed-form estimate derived from an `equivalent'
sequence model that only depends on the spectrum of the kernel operator.
However, a theoretical justification for this equivalence has so far relied
either on restrictive assumptions -- such as subgaussian independent
eigenfunctions -- , or asymptotic derivations for specific kernels in high
dimensions.
In this paper, we prove that this equivalence holds for a general class of
problems satisfying some spectral and concentration properties on the kernel
eigendecomposition. Specifically, we establish in this setting a non-asymptotic
deterministic approximation for the test error of KRR -- with explicit
non-asymptotic bounds -- that only depends on the eigenvalues and the target
function alignment to the eigenvectors of the kernel. Our proofs rely on a
careful derivation of deterministic equivalents for random matrix functionals
in the dimension free regime pioneered by Cheng and Montanari (2022).
We apply this setting to several classical examples and show an excellent
agreement between theoretical predictions and numerical simulations. These
results rely on having access to the eigendecomposition of the kernel operator.
Alternatively, we prove that, under this same setting, the generalized
cross-validation (GCV) estimator concentrates on the test error uniformly over
a range of ridge regularization parameter that includes zero (the interpolating
solution). As a consequence, the GCV estimator can be used to estimate from
data the test error and optimal regularization parameter for KRR.

通过对核岭回归进行一般性等价性和谱特性的分析，证明了从数据中可以获得核运算符的特征分解来近似预测错误，并证明广义交叉验证方法可以用于估计核岭回归的测试误差和最优正则化参数。

一种核岭回归的非渐进理论：确定性等效、测试误差和 GCV 估计器

A non-asymptotic theory of Kernel Ridge Regression: deterministic  equivalents, test error, and GCV estimator

Consider two parties who want to compare their strings, e.g., genomes, but do
not want to reveal them to each other. We present a system for
privacy-preserving matching of strings, which differs from existing systems by
providing a deterministic approximation instead of an exact distance. It is
efficient (linear complexity), non-interactive and does not involve a third
party which makes it particularly suitable for cloud computing. We extend our
protocol, such that it mitigates iterated differential attacks proposed by
Goodrich. Further an implementation of the system is evaluated and compared
against current privacy-preserving string matching algorithms.

该研究提出一种系统，可用于保护隐私的字符串匹配。该系统使用确定性逼近而不是精确的距离，适合于云计算，可以缓解由 Goodrich 提出的迭代差分攻击，并与当前的保护隐私的字符串匹配算法进行比较。