A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regression
Authors: Tin Sum Cheng
Aurelien Lucchi
Anastasis Kratsios
Ivan Dokmanić
David Belius
Venue: NeurIPS 2023 poster (2023)
Keywords: Kernel
regression
bias-variance
generalization
TL;DR: Sharp generalization bounds for finite-rank kernel ridge regressors; these arise when fine-tuning the final layer of pre-trained deep neural networks during transfer learning and multi-task learning.

Abstract: Existing statistical learning guarantees for general kernel regressors often yield loose bounds when used with finite-rank kernels. Yet, finite-rank kernels naturally appear in a number of machine learning problems, e.g. when fine-tuning a pre-trained deep neural network's last layer to adapt it to a novel task when performing transfer learning.  We address this gap for finite-rank kernel ridge regression (KRR) by deriving sharp non-asymptotic upper and lower bounds for the KRR test error of any finite-rank KRR. Our bounds are tighter than previously derived bounds on finite-rank KRR and, unlike comparable results, they also remain valid for any regularization parameters.

A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regression
Tin Sum Cheng Aurelien Lucchi Ivan Dokmanić
Department of Mathematics and Computer Science
University of Basel
(tinsum. Itinsum.cheng, aurelien.lucchi ivan. www.ddookiinnninnoooo ch
Anastasis Kratsios
David Belius
Department Mathematics and Statistics,
Faculty of Mathematics and Computer Science
McMaster University and Vector Institute, kratsicodhncmaserr.cc
UniDistance Suisse
david. bel bewiiddbelus@@aatab..oo
Abstract
Existing statistical learning guarantees for general kernel regressors often yield loose bounds when used with finite-rank kernels. Yet, finite-rank kernels naturally appear in several machine learning problems, e.g. when fine-tuning a pre-trainng pre-trained deep neural network's 's last layer to adapt it to novel task when performing transfer learning. We address this gap for finite-rank kernel ridge regression (KRR) by deriving sharp con-asymptotic upper and lower bounds for the KRR test error of any finite-rank KRR. Our bounds are tighter than previously derived bounds on finite-rank KRR, and unlike comparable results, they also remain valid for any regularization parameters.
Introduction
Generalization is a central theme in statistical learning theory. The recent renewed interest in kernel methods, especially Kernel Ridge Regression (KRR), is largely due the f'ct that deep neural network (DNN) training can be approximated using kernels under appropriate conditions [19, 3, 10), in which the test error more tractable analytically and thus enjoys stronger theoretical guarantees. However, many prior results have been derived under conditions incompatible with practical settings. For instance [24, 26, 27, 29] give asymptotic bounds on KRR test error, which requires the input dimension d to tend to infinity. In reality, the input dimension of the data set and the target function is typically finite. technical difficulty provide sharp aon-tsymto bound on the KRR test error comes from the infinite dimensionality of the kernel While this curse of dimensionality may be unavoidable for infinite-rank kernels (at least without additional restrictions), one may likely derive tighter bounds in a finite-rank setting. Therefore, other works [6, 2] focused kernel is lnike-rank, where nom-asympo bounds and exact formula of test error can be derived.
setting where the
Since different generalization behaviours are observed depending whether the rank of the ker- nel rank M is smaller than the sample size N, one typically differentiates between the under- parameterized (M < N) and over-parameterized regime (M > N). We focus on the former due to relevance several applications in the field of machine learning, including random feature
For a fixed input dimension d' and sample size N, there exists an (aninite-dimensiooaa) subspace in the feature space in which we cannot control the feature vector.
37th Conference Neural Information Processing Systems (NeurIPS 2023).

---

models [32, 35, 25, 14, 17] such as reservoir computers [14, 15, 16, 11] where all the hidden layers of a deep learning model are randomly generated, and only the final layer is trainable, or when fine-tuning the final layers of pre-trained deep neural networks for transfer learning [4] or in few-shot learning [38]. The practice of only re-training pre-trained deep neural networks final layer [40, 23] justified by the fact that earlier layers encode general features which are common to similar tasks thus aee-ttning can support's a network's s ability to generalize to new tasks [21]. J. In this case, the network's s frozen hidden layers define feature map into finitedimenniooall RKHS, which induces finite-rank kernel; however, similar finite-rank kernels are often considered [13] in which features are extracted directly from several hidden layers in deep pre-trainess neural network which is then fed into a trainable linear regressor.
Contribution Our main objective is to provide sharp non-asymptotic upper and lower bounds for the finite-rank KRR test error in the under-parameteriaee regime. We make the following contributions:
(i) Non-vacuous bound in ridgeless case: In contrast prior work, bounds exhibit better accuracy when the ridge parameter À - 0, matching the intuition that a smaller ridge yields smaller test error;
(ii) Sharp non-asymptotic lower bound: We provide sharp lower bound of test error, which matches our derived upper bound as the sample size N increases. In this sense, our bounds are tight;
(iii) Empirical validation: We experimentally validate our results and show our improvement bounds over [6].
As detailed in Section D, Table I compares our results to the available risk-bounds for finite-rank KRR.
Table 1: Comparison of risk-bounds for finite-rank kernel ridge regressors. (*): The bound for the inconsistent case is implicit. See Section 5 for details. (**): By decay, mean the difference between the upper bound and its limit as N oc.
Assumptions/ / results
Mohri
Amini et al.[2]
Bach [6]
This paper
et al. [30]
Include inconsistent case
x
(V)*
Bias-variance decomposition
Test error high probability upper bound Test error high probability lower bound Bounds improve with smaller ridge?
X
XXX
X
x
Upper bound decay rate**
log N
lng N A
(A
+
Ing
A.
Organization of Paper Our paper is organized as follows: Section 2 motivates the importance of finite-rank KRR. Section introduces the notation and necessary background main findings and illustrates
the uuder-parameter
material required in results' formulation. Section 4 summarizes their implications via a numerical study. All notation is tabulated in Appendix A for the reader's s convenience. All proofs be found in Appendices B and C, and numerical validation of theoretical findings in Appendix D.
2 Applications
In this section, we motivate the importance of the mnder-parameterizzed finite-rank KRR in practical settings. For readers more interested in our main results, please start from Section 3.
Application: Fine-tuning Pre-Trained Deep Neural Networks For Transfer Learning Consider the transfer-learing problem of fine-tuning the final layer of a pre-trained deep neural network model

---

f: F -RR so that it can be adapted to task that is similar to what it was initially trained for. This procedure defines finite-rank kernel regressor because, for any x E IR can be factored
f(z) A((x)) <(x) = W
(x),
where A is D x dr -mtrrxx, de denotes element-wise application of a univariate non- non-linear function, for 1 = 1, 1....,,,, L, is a positive integer, and W : RR - Rd4 = dg- In pre- pre-training, all parameters defining the affine maps W the hidden layers o W( ..... o W()) are simultaneously optimized, while in fine-tuning, only the parameters in the final A are trained, and the others are frozen. This reduces f to a finite-rank kernel regressor with finite-rank kernel given for Jr IR by
Kxx del
(x)).
Stably optimizing f to the new task requires strict convexity of the KRR problem
1 [(A(IE)) - yn)² + A|I
min N
(I)
where the hyperparameter > 0 ensures strong convexity of the KRR's loss function and where || denotes the Frobenius norm of A. The unique solution Á (1), determines the optimally trained KRR model f(x)) def. Åδ(z) corresponding the finite-rank kernel K.
Application: Random Feature Models Popularized by [32] to enable more efficient kernel computations, random feature model has recently seen substantial spike in popularity and has been the topic of many theoretical works [20, 27J. Note that random feature models are finite-rank kernel regressors once their features are randomly sampled [32, 35, 25, 14, 11].
We emphasize that, though fine-tuning and random feature models provide simple typical examples of when finite-rank KRR arise in machine learning, there are several other instances where our results apply, e.g. when deriving generalization bounds for infinite-rank kernels by truncation, thereby replacing them by finite-rank kernel;; e.g. [27].
Application:
General Use
3
Preliminary
We now formally define all concepts and notation used throughout this paper. complete glossary is found in Appendix A.
3.1 The Training and Testing Data
We fix a (non-empty) input space C Rd and a target function f + R which to be learned by the KRR from a finite number of i.i.d. (possibly noisy) samples Z (X,y) ((r)) (v)) e A x RV The inputs 2; are drawn from sampling distribution p X' and outputs modelled y: fxx) + R Nx1 for some i.i.d. independent random variable e, which is also
independent of the X, satisfying [E(c] = 0 and [ o² 2 0. Our analysis is set in the space of
all square-integrable "function" with respect to the sampling distribution L2(p) def. { X + R Ex<v]f(2) < x.}.
We abbreviate = f(X) +EE N.11, where f(x) = [f(.)) and e [e]]
3.2 The Assumption: The Finite-Ranm Kernel Ridge Regressor
As in [2. 6], fix a rank M N4 for the kernel K. Definition 3.1 (Finite Rank Kernel), Let be a positive integer. A (finite) rank-M kernel is a map K : X x X R defined for any x'' E X by
K ((x,x')
Σ (=)x())
(2)
3

---

where the positive numbers {A are called the eigenvalues, and orthonormal functions t/y E L called the eigenfunctions.
Remark 3.2 (Figenvalues are Ordered). Without loss of generality, we will assume that the kernel K's eigenvalues are ordered X1 A2 ... AM > 0.
We denote by H. span associated to K. See Appendix for additional details on kernels and RKHSs.
1/2///1/1110 $1....... ........,,,,,? /,
the reproducing kernel Hilbert space (RKHS)
Together, the kernel K and ridge À > 0 define an optimal regressor for the training data Z. Definition 3.3 (Kernel Ridge Regressor (KRR)). Fix ridge À 0, the regressor fz,x of the finite-rank kernel K is the (unique) minimizer of
N Σ 1=1
JZ,
min JEN
(((x)-y))) + Al1
(3)
N
3.3 The Target Function
The only regularity assumed the target function / that is square-integrable with respect to the sampling distribution y; i.e. f E T.g. We typically assume that contains strictly more features than can be expressed by the finite-rank kernel K. Thus, f can be arbitrarily complicated even if the kernel K is not. Since { M k=1 is an orthonormal set of L decompose the target function f as
M
ik tk +7M0SM.
(4)
k=
fCM
for some real numbers " and M and for some normal function i orthogonal to {v/ 1M We call di M the orthonormal complement and Я As the complementary coefficient. The component fsas del Σk=1 71.2% of f in H. For the case ?>M M = O, we call a consistent case, as the target function f lies in the hypothesis set H. else we call it an inconsistent case.
I==1
Alternatively, the orthonormal complement th M can be understood as some input-dependent noise. Assume we have chosen suitable finite rank kernel K with corresponding RKHS H such that the target function lies in H. For this purpose, we can write the target function as fgM Σ 1 Tu t/a for some real numbers 7x ss Suppose that we sample in a noisy environment; then for each sample input 24, the sample output 3/1 can be written as
Vi fx,( S +
(5)
imput- mnputddependent noise
input-independdet noise
3.4 Test Error
Next, we introduce the subject of interest of this paper in more detail. Our statistical analysis quantifies the deviation the learned function from the ground truth of the test error.
Definition 3.4 (KRR Test Error). Fix a sample = (X, + c). The finite-rank KRR (3)'s test error is
Er. (F2A(z)- = US (FzAl0)- F(x)) dolx)
Rz,
(6)
The analysis of this paper also follows the classical bias-variance decomposition, thus we write
Rz, bias variance,
where bias measures the error when there is noise in the label, that is,
def. S (J)x) - -f())))))))))))))))()))))))))- dp(x),
bias
and variance is defined be the difference between test error and bias: variance Rz, bias.
This means that fx th (x(x))((()ddp(e) dRi for all 1 < SL5 M.

---

Main Result
We now present the informal version of our main result, which gives bogh-probbbility upper and lower bounds on the test error. This result is obtained by bounding both the bias and variance, and the probability that the bounds hold is quantified with respect to the sampling distribution p. Here we emphasize the condition that N > M and hence our statement is valid only in under-parametrized
case.
We can assume the data-generating distribution p and eigenfunctions tha are well-behaved in the sense that:
Assumption 4.1 Sub--Gaussinn-na variable (x).,, where x E p. has sub- Gaussian norm bounded by positive constant > 0, for all k { [I....,MM. M J { MY.
We assume that the probability distribution of the random
In particular, if the random variable (x) is bounded, the assumption 4.1 fulfilled.
Theorem 4.2 (High Probability Bounds on Bias and Variance). Suppose Assumption 4. holds, for N M sufficient large. there exists some constants C1, C2 independent to N and X such that, with probability of at least - 2/N w.r.. random sampling, we have the following results simultaneously:
(i) Upper-Bound Bound on Bias: The bias upper bounded by:
bias S R.SM + Allfgmili + ( (d1/fiig + 2N11 FMI
log N N
log N
+
+
(8)
N
where we denote fea EK= nissa = -
(ii) Lower-Bound on Bias: The bias is lower bounded by an analogous result:
X2 bias 2 333 (AM + A)2 11f
(LIATRE; + A1 (
2X²
log N
log N
C1
N
(9)
(iii Upper-Bound on Variance: The variance is upper bounded by:
M N
log N
log N N
variance < <a²
N + C2
(10)
(iv) Lower-Bound on Variance: The variance lower bounded by an analogous result:
X (AM + LK N
M
(1 (1-V
llg N
C20 M log
variance
(11)
For X - O, we have simpler bound on the bias; with probability of at least 1 2/N, we have
log N
log N N
lim bias 7..0
1
2
N
(12)
logg N $
log N lim bias MM
N 67
If 1 = O, then we are in the consistent case, meaning that f belongs to H. In this case, we have simpler bound on the bias: with a probability of at least 1 2/N, we have
log N N
log N + +
bias S XII [ 1++2/
(13)
'it means the orthonormal complement s wr also mentioned the assumption.
5

---

Proof Sketch: The main technical tools are 1) more careful algebraic manipulations when dealing with terms involving the regularizer and 2) the use of a concentration result for a sub-Gaussian random covariance matrix in [37] followed by the Neumann series expansion of matrix inverse. Hence, unlike previous work, our result holds for any X, which can be chosen independence to N. The complete proof of this result, together with the explicit form of the lower bound, is presented in Theorems C.19 and C.20 in the Appendix C.
Remark 4.3. Note that one also easily derive bounds on the expected value of the test error to allow comparisons with prior works, such as [6, 36, 33).
Remark 4.4. The main technical difference from prior works is that we consider the basis ( M in the function space L2 instead of {xx - 1/) ) in the RKHS H. This way. we exploit decouple the effect of spectrum from the sampling randomness to obtain a sharper bound. For further details, Remark C.12 in Appendix C.
Combining Theorem 4.2 and the upper and lower bounds of the test error KRR.
decomposition in Definition 3.4, we have both the
Corollary 4,4.1. Under mild conditions on the kernel K. for N sufficiently large. there exist some constants C1, C2 independent to N and X such that, with a probability of least 2/N w.r.f. random sampling, we have the bounds on the test error Rz,x
RZ. I R.M- + A1l + (1 + +211 )
log N
log N
V
+ C1
N
N
M + 0
log N
log N N
)
1
+ C2
N
N
A²AM
21²
log N
log N N
Rz, 2 75M
11
SM 11:
C1
(Au + 2)2
A + x
N
M
(1
log N
log N N
+ t N
-C2
In particular, we have:
lim Rz, S (1 log N X-0
log
+ o M
(1
log N N
log N N
33M + 693MM
1
+ C2
N
N
N
The corresponding lower bounds are given analogously:
lim Rz, [ A
log N
35mm - 6..3
llog N
t
M
1
log N N
C2
log N N
N
N
See Section 5 for more details and validations of Theorem 4.2.
Discussion
In this section, we first elaborate on the result from Theorem 4.2, which we then compare in detail to prior works, showcasing the improvements this paper makes. Finally, we discuss several future research directions.
5.1 Elaboration on Main Result
Bias From Eq. (8), we can draw the following observations: 1) The term 43 in the upper bound is the finite rank error due to the inconsistency between RKHS and the orthogonal complement of the target function, which cannot be improved no matter what sample size we have. We can also view this term as the sample-dependen noise variance (see Eq. (5)). Hence, unlike the sample-independent noise variance a in Eq. (10), the sample-dependent noise variance does not vanish when N + oo.
2) Note that the third term 1l 12 V
log is a residue term proportional to [fl] and vanishes N

---

when N + oc, which means we have better control of the sample-dependent noise around its expected value for large N. Also, note that the factor I Σ 2 + 1 depends solely the target function but not on the kernel K or ridge parameter A. 3) The second plus the fourth
terms 1 11+2V
log N
X > M l depends strongly the kernel training: the sum is proportional
to the ridge A, and the RKHS norm square [lfeM lix = = M oi k= Ay target functions with the chosen kernel K is. Again, larger N favors the control the residue
measures how well-aligned the
|og N 0 as N + oc. 4) The fifth term C1 log N is small residue term with fast decay rate,
V N'
which the other terms will overshadow as N xc.
Ridge parameter The bounds in Eq. (12) demonstrate that in the ridgeless case, the bias can be controlled solely by the finite rank error 72 with a confidence level depending on N; also the upper and lower bounds coincide as N + co.
Variance For the variance bounds in Eq. (10), we have similar results: the variance can controlled solely by the (sample-independen) noise variance o² with confidence level depending on N, also the upper and lower bounds coincides as N + oC.
5.2 Comparison with Prior Works
We discuss how our results add to, and improve on, what is known about finite-rank KRRs following the presentation in Table 1.
Classical tools to study generalization The test error measures the average difference between the trained model and the target function. It is one of the most common measures to study the generalization performance of machine learning model. Nevertheless, generally applicable statistical learming-theone theoretic tools from VC-theory [8], (local) Rademacher complexities [22, 7, 30., PAC-Bayes methods [1, 28]. or smooth optimal transport theory [18] all yield pessimistic bounds on the KRR test error. For example, Mohri et al. [30] bound the generalization error using Rademacher Complexity: there exists some constant C 0 independent to N and À such that, with probability of at least
1 T:
1 2
log
test error train error S
1+
(14)
2
If we set 7 to 2/N, the decay in the generalization gap is O to other kernel-specific analyses.
log N
which is too slow compared
Amini al. [2] suggests interesting type of finite-rank kernels: for any (infinite-rank) kernel K(s)), fix a sample Z (X,y) of size N and define a rank-N kernel K by the eigendecomposition of the kernel matrix K(oo), Note that different random sample results in completely different rank-N kernel K. Assume that the target function f lies in the N-dimensional RKHS corresponding to K, then one can obtain an exact formula for the expected value of the test error of the kernel K (but not only the original ((e)). However, the formula obtained in [2] only takes into account the expectation over the noise but not over the samples x. Hence, our paper yields more general result for the test error.
Truncated KRR
Upper bound Comparison To the best of our knowledge, the following result is the closest and most related to ours:
Theorem 5.1. (Proposition 7.4 in [6]) With notation as before, assume, in addition, that: 1)5>M M that is, f E H; for all k 1,... M, we have v Ei ds S R; 3) and N x 8X
log
14R²
Xr
7

---

Then we have, with probability of at least 1
bias - <4>11f
80 I2²
14-2log 2
variance
AN
In comparison to [6], Theorem 4.2 makes the following significant improvements:
(i) In Theorem 5.1, as the ridge parameter X O, the minimum requirement of N and the upper bound of the variance explode; while in our case, both the minimum requirement of and the bounds on the variance are independent of
(ii) While [6] also mentioned the case where 7>M M O, however their bound for the inconsistent case is implicit; while our work clearly states the impact of 7> on the test error.
iii) Our upper bounds are sharper than [6]:
(a) For the bias, assume 4> for comparison purposes. Then by line (13) our upper bound would become:
log N N
log N N
bias AIll3 1 2V
C1
which improves [6]'s upper bound bias S 4 significantly. First, we observe a minor improvement in the constant (by a factor of {) when N + cc. Second and more importantly, for finite N, we observe non-asymptotic decay on the upper bound, while [6]'s upper bound is insensitive to N.
(b) For the variance, if we replace by 2/N in [6]'s upper bound: with probability of at least 1 2/N,
802
variance
(1 + 2 log
(15)
AN
which has decay rate of log N our work shows much faster decay of 1. Moreover, we show that the "unscaled" variance, that is N (variance), is actually bounded by
log.N N
while [6]'s upper bound on it would explode.
(iv) We also provide lower bound for the test error that matches with the upper bound when
N + cc, while [6] does not derive any lower bound.
While our work offers overall better bounds, there are some technical differences between the bounds of [6] and ours:
(i) We require some explicit mild condition on input distribution and on kernel K, while [6]
rely on the assumption EM A < R which gives an alternative implicit requirement;
(ii) Our work eventually assumes under-paree paramttrrttttioonooonn M N, while [6] does not requires this. Essentially, we exploit the assumption on the under-parameterizee regime to obtain sharper bound than [6]. In short, we select the L, basis dh for analysis while [6] selects the basis in RKHS, which eventually affects the assumptions and conclusions. For more details, see Appendix C.
Nyström Subsampling and Random Feature Model Nyström Subsampling and Random feature models are two setting closely related to our work. [34, 35] bound the test error from above where the regularizer X = X N) decays as N - co. In comparison, one main contribution of our work is that we provide both tighter upper bound and tighter lower bound than these prior works (they derive the same convergence rate the upper bound up constants but they do not derive lower bound). Another major difference is that our bounds work for any regularization independent to N.
'For inconsistent cases (or misspecified model), [6] only derives an upper bound on the expected value of test error. Also, the bound involves function defined as an infimum of some set.

---

Effective Dimension In [34, 35] and other related works on kernel, the quantity (( M
An+t Tr [P] is called the effective dimension and it appeared
factor in the up-
(AL Tr [P*), which appears in our bound (See Proposition C.14 for details.). Note that (2 S (V() M. Indeed, (A)
per bound. In our work, we can define a related quantity (A) = E
A
we can sharpen the factor M in line (10) to N
N
5.3 Experiments
We examine the test enror and showcase the validity of the bounds derived for different finite-rank kernels: the truncated neural tangent kernel (tNTK) and the Legendre kernel (LK) (see details of their definitions Appendix D). Figure shows the test error as a function of the sample size N. Figure 2 plots our upper bound compared to [6], clearly demonstrating significant improvements. We for instance note that the bound is tighter for any value of X. Finally, Figure shows both the upper and lower bound closely enclose the true test error. For more details on the experiment setup, including evaluating the lower bound, please see Appendix D.
tNTK training
Varying Sample Size
Median
Quartiles
14
6122
Test Error
6:13
2.
0:31
0.55
Target Function Regressor
014
-12
Sample
682
030
X
N
Legendre Kernel Training
Varying Sample Size
Regressor
Median
0:34
Target Function
Quartiles
Sample
Test Error
0:34
6:22
-123
-275
-055
-2.25
1.00
0.25
5.00
0.5
1.00
22
54
75
130
155
150
175
20
N
Figure 1: KRR finite-rank kernel. Left: KRR training; right: test error for varying N, over 10 iterations. The upper and lower quartiles are used as error bars.
5.4 Future Research Direction
An interesting extension would be to combine our results with [36, 10] in the ver-parameterized regime to give an accurate transition and observe double descent. However, since we are interested in the sharpest possible bounds for the madeer-prametterized regime, we treat these cases separately, We will do the same for the over- weer-paameeerizee regime in future work. A special case is where the parameterization is at the threshold M N and X 0. The blow-up of variance as M + N is well-known, where [5, 9] gives empirical and theoretical reports on the blow-up for kernels. We expect that formally prove this result for any finite-rank kernels using our exact formula in Proposition C.7 and some anti-concentration inequalities on random matrices.

---

Varying Sample Size on tNTK
Varying Ridge on tNTK
log Scale
Bach's Upper Bound our Upper Bound
Bach's Upper Bound our Upper Bound
1000
1/1
Varying Sample Size on LK
Varying Ridge on LK
log Scale
Bach's Upper Bound our Upper Bound
Bach's Upper Bound our Upper Bound
-3
1/1
Figure 2: Comparison of test error bounds. Left: upper bounds for varying N; right: upper bounds
for varying A. natural log scale.
Test Error on tNTK
Test Error on LK
u.b. w/o Residue
u.b. w/o Residue
w/o Residue
w/o Residue
Median
Median
Quartiles
Quartiles
log scale
28 50
75
100
150
175
200
25
50
75
100
125
150
175
200
Figure 3: Our bounds (u.b. = upper bound, Iw. = lower bound) comparing to the test error with varying N, over 10 iterations, in natural log scale. The residues with coefficients C₁ and C2 dropped by simplicity. As a result, the bounds are not "bounding" the averaged test error for small N. But for large N, the residues become negligible.
References
[1] Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approxi- mations of Gibbs posteriors. J. Mach. Learn. Res., 17:Paper No. 239, 41, 2016.
10

---

[2] Arash Amini, Richard Baumgartner, and Dai Feng. Target alignment in truncated kernel ridge regression. Advances in Neural Information Processing Systems. 15:21948-2196 2022.
[3] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterizee two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
[4] Hossein Azizpour, Ali Sharif Razavian, Josephine Sullivan, Atsuto Maki, and Stefan Carlsson. Factors of transferability for generic convnet representation. IEEE transactions on pattern analysis and machine intelligence, 38(9):190-11802 2015.
[5] Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. arXiv preprint arXivv2303.01332, 2023.
[6] Francis Bach. Learning theory from first principles. Online version, 2023.
[7] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities. Ann. Statist., 3394:11477 2005.
[8] Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: risk bounds and structural results. J. Mach. Learn. Res., 3(Spec. Issue Comput. Learn. Theory):463-444 482, 2002.
[9] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, (6632):15849-111 158544 2019.
[10] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pages 1024-1034. PMLR, 2020.
[11] Enea Monzio Compagnoni, Anna Scampicchio, Luca Biggio, Antonio Orvicto, Thomas Hof- mann, and Josef Teichmann. On the effectiveness of randomized signatures reservoir for learning rough dynamics. IEEE IJCNN 2023, 2023.
[12] Eernesoo De Vito, Lorenzo Rosasco, and Andrea Caponnetto. Discretization error analysis for tikonov regularization. Analysis and Applications, 04((0)):1-99) 2006.
[13] Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In Eric P. Xing and Tony Jebara, editors. Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 647-655, Bejing, China, 22-24 Jun 2014. PMLR.
[14] L. Gonon, L. Grigoryeva, and J.P Ortega. Approximation bounds for random neural networks and reservoir systems. Annals of Applied Probability, 2022.
[15] Lukas Gonon, Lyudmila Grigoryeva, and Kuan-Pable Ortega. Risk bounds for reservoir comput- ing. Journal of Machine Learning Research (JMLR), 21, 2020.
[16] Lukas Gonon, Lyudmila Grigoryeva, and Juan-Pable Ortega. Infinite-dimensionaal reservoir computing, arXiv preprint MxXvv:2304.00490. 2023.
[17] Calypso Herrera, Florian Krach, Pierre Ruyssen, and Josef Teichmann. Optimal stopping via randomized neural networks. arXiv preprint arXiv:2104. 13669, 2021.
[18] Songyan Hou, Parnian Kassraie, Anastasis Kratsios, Jonas Rothfuss, and Andreas Krause, Instance-dependee generalization bounds via optimal transport. arXiv preprint arXiv:2211.012 1.002558 2022.
[19] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl:: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.

---

[20] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regularization of random feature models. International Conference on Machine Learning. pages 4631 16440. PMLR, 2020.
[21] Haotian Ju, Dongyue Li, and Hongyang R Zhang. Robust fine-tuning of deep neural networks with hessian-based generalization guarantees. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari. Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 10431-10611 PMLR, 17-23 Jul 2022.
[22] Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances in neural information processing systems, 21, 2008.
[23] Xuhong LI, Yves Grandvalet, and Franck Davoine. Explicit inductive bias for transfer learning with convolutional networks. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2825-2834 PMLR, 10-15 Jul 2018.
[24] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3), Jun 2020.
[25] Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel approximation: A survey algorithms, theory, and beyond. IEEE Transactions Pattern Analysis and Machine Intelligence, 44(10):7128-7148 2021.
[26] Fanghui Liu, Zhenyu Liao, and Johan Suykens. Kernel regression in high dimensions: Refined analysis beyond double descent. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 649 657. PMLR, 13-15 Apr 2021.
[27] Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 2021.
[28] Zakaria Mhammedi, Peter Grünwald, and Benjamin Guedj. Pac-bayes un-expected bernstein inequality. Advances in Neural Information Processing Systems, 32, 2019.
[29] Theodor Misiakiewiez. Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression, 2022.
[30] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[31] K. B. Petersen and M. S. Pedersen. The matrix cookbook, nov 2012. Version 20121115.
[32] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
[33] Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. Advances in Neural Information Processing Systems, 32, 2019.
[34] Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco. Less is more: Nyström computa- tional regularization. Advances in Neural Information Processing Systems, 28, 2015.
[35] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. Advances in neural information processing systems, 30, 2017.
[36] Alexander Tsigler and Peter L. Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 24( 24(123):1-76, 2023.
[37] Roman Vershynin. Introduction the non-asymptotic analysis of random matrices. arXiv preprint arXiv:101 100:1001,,00, 1,3027, 2010.
12

---

[38] Oriol Vinyals, Charles Blundell, Timothy Lillicrap. Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems. 29, 2016.
[39] Martin Wainwright. HlighDiimensions Statistics: A Non-Asymplotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[40] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? Advances in neural information processing systems, 27, 2014.
13

---

Appendix
A Glossary
Table 2: Glossary
Name
Notation
Expression
Dimension
sampling distribution
X' + RR
sampling size
N
integer
input matrix
X
(x:)
~ PX
N
iid
output vector
(1:)
N 1
sample
(X,y)
N (d + 1)
noise
E
random scalar
noise variance
o²
scalar
ridge
A
scalar
finite-rank kernel
K
(o
X' x X R
kernel rank
M
integer
kth eigenfunction
thk
X' - IR
kth value
d
scalar
(b(x)
(x))<)
M x 1
v
M x N
diag [As]
M X M
kernel matrix
K
K (x Jz May T A&
N N
resolvent
R
K ANIN)-
N N
target function
IM k= iash + +
X' + RR
f&M
E Tath
X'
kth target coefficient
7n
Sx (1)))b()))dpx(
scalar
(Td)
M x
orthonormal complement complementary coefficient
X' +
7> m
scalar
1 >M
[ m (x:)
x
error
Rz.
Ex,c (zz
scalar
bias
fx (xxxf(x)).xx=)- - f(xx) dp(x)) scalar
variance
Rz. bias Ez,s (KJ. Re)
scalar
fluctuation matrix
A
1 LVO
IMM
M x M
N
fluctuation
8
A lop
scalar
error vector
E
[TR]
M x
T
N ΣN
ii=1 (
scalar
(IM
+ -1-
M x
P
diag
M x
X
14

---

B Classical KRR Theory
In effort keep manuscript self-contained possible, recall the Mereer decomposition, representer theorem for kernel ridge regression as well as the form the bias-variance tradcoff the KRR context.
B.1 Mercer Decomposition
We begin with general kernel K((0); x
Proposition B.1. [12] Fix sample distribution Let K( :X x R be a reproducing kernel with corresponding RKHS H(x)) There exists decreasing sequence of real numbers À Z X2 2 ... called the eigenvalues of the kernel K(x)); and a sequence of cetrwis-oortonormne ( 1o0
functions L. called the eigenfinctions of K())) sscch that for all x, x' X, we have
K K(00) (2, (I, (xba(t)(boe'))
(16)
In particular, we assume X 0, Vk > M. In this case, we say the kernel ((x, x') = Eke A (z) (x') ) is of finite rank M with corresponding finite-dimensiona) RKHS H. re- covering equation (2).
The first these results, allows us to explicitly express the finite-rank kernel ridge regressor fz,x- Proposition B.2 (Representer Theorem - [39, Chapter 12]). Let R (K + ANIN) )-1 NxN be the resolvent matrix and recall the kernel ridge regressor fz.x given by equation (3):
Jz,
de arg min SCH
(I(a.) - y:)² + AllS
1=1
Then, for every E X, we have the expression
fzx(2) = y RK,, Vo E X,
(17)
where K,
Jef. [K(
B.2 Compact Matrix Expression
First, let T def. (+)((z:)) M.N be the random M N matrix defined by evaluating the M
eigenfunctions on all input training instances X del. (z.)
def diag[Aa] RMXM and
ab()) (x) E RMX1, The advantage of this notation is that we can rewrite the equa- tions in more compact form. For equation (17):
(2, y
T A& + ANIM) V Abb(x);
(18)
R
for equation (4):
f(x) = (b(x)) + M (()).
(19)
Last but not least, we define some important quantities for later analysis. Definition B.3 (Fluctuation matrix). The fluctuation matrix is the random M x M-matrix given by Las. Our analysis will often involve the operator norm of A, which we denote by lop-
M 2 T
A
The fluctuation matrix A measures the first source of randomness in the KRR's 's test error. Namely encodes the degree of non-orthonormalliy between the vectors obtained by evaluating of the M eigenfunctions v1, ....... ......,, d'M the input X.
The second source of randomness in the KRR's test error comes from the empirical evaluation of the dot product of the eigenfunction db 's and the orthogonal complement $>M
Definition B.4 (Error Vector). E Valsar (XX)
(X) is called the error vector.
The random matrix A and the random vector E are centered; i.c. Ex [ 0 and Ex [ 0.
15

---

B.3 Bias-Variance Variance Decomposition
The derivation of several contemporary KRR generalization bounds [6, 26, 27] involves the classical Bias- Variance Trade-off:
Proposition B,5 (Bias- Variance Trade-off), Fix a sample Z. Recall the definition 3.4 of test emor Rz,,, bias, and variance:
=E, [// (FZAlH)- dp(x)
Rz, del Ez,e
bias Jxx (FXx f(x)) dp(z);
variance Rz,> - bias.
Then, we can write variancener En,e (K2 Re)² and hence the test error Rz, admits decompo- sition:
Rz. bias Exg (Kg) Re)
Proof. See the proof of Theorem C.8.
C Proofs
In this section, we will derive the essential lemmata and propositions for proving the main theorems.
C.1 Formula Derivation
We begin with writing the test error in convenient forms.
C.1.1 Bias
We first derive, from the definition of the bias, convenient expression proceed:
Proposition C.1 (Bias Expression). Let V M
[ as an 1 x N- row vector, (VSA))
as an (M + 1) x N matrix. Denote P def. (PSM
P>M) = P~M)==AD
AVR v JMM Mx(++1
P SM E RxM and P P>M E Mx1, Then the bias admits the following expression:
bias
T-M
1I PEMY 72 PPMMPMM
Finite Rank Error
Fitting Error
Proof. Recall that, by equations (18) and (19),
write
f(x) TT (xxx + +>M
(x) = (5 T ア RV (Z))..
Hence
bias Ex (77 (z))(() TSMPSM (z) T + +7 M Ry AV(()))
= =1((300)
7 P
((
12 ?
(20)
0
1SM
11
P P 7 P > M
Finite Rank Error
Fitting Error
in line (20), we use Parseval's identity.
We proceed by reformulating the projection matrix P. first with the left matrix P SM:
16

---

Lemma C.2. Recall the following notations
K del.
AV,
R del
KK + ANTM) (NTM)
P SM del AVRY
Define the symmetric random matrix del (La + A + +)- holds that
P P&M IM ABA
Proof. We first observe that
V/ P PSM = TND AVRYE
(21)
bK(( + ANTM) T TT T
T (INs AN(K ANIM) ) V T
T -ANN + A
(22)
From lines (21)- (22) and the definition of the fluctuation matrix A deduce
1
N (IM PSM) ( ANIM) '
(IM A)(IM PgM) = APRYY
(IM + A) -PMM) = AA -PSM
(A + AA) P&M) AP
A AA = (A + AA + A
(23)
Rearranging (23) and applying the definition of B we find that
P&M (A AA + AlM) (A + AA)
(24)
IM X(A + AA ALM)
IM X(A MA+AA AA-
IM -BA-1
(25)
Arguing analogously for the right matrix Paas, we draw the subsequent similar conclusion.
Lemma C.3. Recall the following notations
K
def
V
A
R
def.
KK + AANNM
P>M der AVR >M
1
E
V
T
B (IM +4++10 A 11-
N
>M
We have that P> = BE.
Proof. Similarly to (21)- (22) note that
L P DE AVRI SM
T
=KKKK ANI I 2
= V =V(IM - AN(K + AN -1 v SM
-VVT AN + -
Analogously to the computations in (24)-(25)
(IM + A)P>MM
AP(K ANTM) T
(IM + A)P = E XA AV ANT SM
(IM + A)P E - XA 'P
+ AA)P >M AE AM
(A + A4 + AI P> AE
Р>м (A AA + -
P P>M BE.
17

---

Lemma C.4 (Fitting Error), Recall the notation
fitting error
= |1 PSM - - P> 11
B def. (IM A 11-
We have fatiigg error = | (AA E
Proof. By lemmata C.2 and C.3,
I1 - Pssm - 7 P.MMPMMM > = =16 -18-- - (IM ABA 1)55 - BE
= B (AA-Y E8>M))l2
Hence up with new expression of the bias:
Proposition C.5 (Bias). Recall that B the following expression:
(IM + A AA 1)- The bias E. (f)(z) - =(x))² has
bias = 3200 | ( E)
Proof. We apply Proposition C.I and Lemma C.4 to obtain the result.
C.1.2 Variance
If consider noise in the label, we have compute the variance part of the test error. Proposition C.6 (Variance Expression). Define
M
de. Ey K
E2 (zb
V T (EL
V AV
T A
We can further simplify the variance part:
variance def.
EE,,, (K, RE)
=Er,e E RK, K. R
F. [s "RMRe]]
= T...TRRMR
Theorem C.7 (Variance). Recall that B del. (INs A AA 7)- be expressed as:
The variance part, variance, can
0² N
variance
Tr [B + +
Proof. We argue similarly as lemma C.2. Since
TT T A VKK + -
VI ANR) -NNRR
18

---

therefore, we deduce that
(IM + AJAVR
N VP XPR
(26)
(IM + AJAVR V -A-AAAAAPP A
(IM + A AA
J A
v
AVR
(IM + A + -
N
A
B
(27)
N
By leveraging the identity M tions in (26)-(27) imply that
V T 2 and clementary properties of the trace map, the computa-
Tr RMR
Tr R A
(28)
= TT
(AVR)
(AVR)
(29)
(N
BB
BU
BVF
(30)
N
N
T
B
Bv
N
N
1
B
B
B
V
(31)
N
N
Tr
B(I A)
(32)
N
Tr [ (LM + +A]]:
(33)
in more detail: in line (28), we use the definition of M; line (29), we use the fact that both and R are symmetric; in line (30), we use line (27); in line (31), we use the cyclicity of the trace; in line (32), we use the definition of A; line (33), we use the symmetry of B. We obtain the result upon applying Lemma C.6.
C.1.3 Test Error
The Bias- Variance trade-off (see Proposition B.5) decomposed KRR's test error into two terms, the bias and variance. Since Propositions C.5 and C.7 give us exact expressions for the bias and variance, respectively, we deduce the following exact expression for the KRR's test error. Theorem C.8 (Exact Formula for KRR's Test Error). The test error Rz.,x of KRR equals
litting error
fonite rank
B (AA l i EM 112
o noise Tr [ A)]
Rz.A
7.M
N
bias
variance
where
del. (IM + +
Proof. We begin with the bias/variance decomposition:
R₂ E., 1 fl2iz xx
= Er.y (K. ((x)y-f(x))
=Ec,r (K]R(F(X)++) (((((((()))--( -f)))(())²
=E, ((())) + Ex,e [K] ?1
= bias + variance,
19

---

then we apply Propositions C.5 and C.7.
For the validation of the Theorem C.8, please see Appendix D) for details.
The matrix B plays an important role in the expression since encodes most information of the KRR. Therefore, the following subsection will discuss the approximation of the matrix B.
C.2 Matrix Approximation
Recall that the matrix B def.
(IM + + XA-1)-1 the inverse of a random matrix. The following 1. We have
lemma helps to approximate B. Informally, it says that: given that 6 del.
lop
B
PAY
in operator norm ||- llop for an M x M matrix P depending only on the M eigenvalues } and on the ridge À > 0. More precisely we have the following.
Lemma C.9 (B (B-Expansion). Given that def.
A lop
< 1. It holds that
lim 2700
B
PA
'P
where P
def.
diag
Au A++
= A(A + AM) ER
Proof. Set A = IM - AA-1 and repeatedly use the formula (A+A) = A-1 A-1-A-AA(+A)--
from [31], we have
B
(IM + A + +
(A + A -1
A- A A AA(A+
A A A A A(A+)))))
A- -1 A AA + (A- -1
A A (- (A A)
Note that A = (IM + AA -1)- A(A + -M) = P with operator norm
A
< 1, hence
A1
we have (A A--Ajnnt== PP n-1 in operator norm - oo. Hence
B
A A A'-A-
8=0
PA)
operator norm.
Due to the convergence result in lemma C.9, it is natural to define:
Definition C.10. For any NU (oo), write B (n)
-.' (- (PP)) For example, We have
B (0) P
(1) P PAP
(x)) B
20

---

Although lemma C.9 is valid when ó < 1, we need slightly stronger condition that g is upper bounded by an arbitrary constant strictly small than For simplicity, we assume this constant be in the following lemma:
Lemma C.11 (B-Approximation) Assume that å del.
|
op 2.2 Let Ler = ( be
the nth-order approximation the matrix B in definition C.10. Then have
B
B-B
< 28
op
Proof. We first bound the operator norm of the matrix B: since the minimum singular value of the matrix P + A is at least
A +
A
1
1+
An
2
2'
and hence
(P + A -1
B
22
op
Also, we have
00 B-
Σ (-PA)'P
s=
DO
(-PA) n+1 Σ (-PA
= (-PA m++1 B.
Hence
(
llop
<
PA n+1
|Bllop
R+1 lpp
-2 28 since we have |Ploop
op
ArtA < 1.
Note that the upper bound 2 of 5 can be replaced by any constant strictly small than I to get similar conclusion.
Remark C.12. Using the concentration result from random matrix theory, for M < N. one can show with high probability that the operator norm 8 of the fluctuation matrix A is less than 1. 5
See subsection C.3 for details. Then we can use the the above lemmata C.9 and C.11 to approximate the test error of KRR:
Proposition C.13 (Bias Approximation). Fix a sample Z of p such that 5 bias term bounded above and below by
A
< 2' Then the
bias (1|Pw|
33.) - 25 Pw 2
|| 52p((),
where P del A(A + AIM) w XA -A 1ā
7, and p(8) det 5 + 48 482. By writing
E (m the bounds simplify to
(Xñx Mm (Ae + X)2 + 11
bias < 3..M + (11 28)
k=1
M
(Nitk - >))))
bias 2 33. + (1 28)
| 82 p()))
(A++ - X)2
'From there, we di differentiate the approach from Bach [6]: From Propositions C.5 and C.7, it is inevitable to approximate the matrix B, and have Im support of the inverse. Bach instead uses RHKS basis to express the fluctuation matrix and is hence forced use Al the support. As result, he would need to require that the fluctuation less than and hence his requirement on N is antiproportional À Theorem 5.
21

---

Proof. Let w = AA- - > - E. We apply lemma C.4 followed by the Ist-order approximation
B(1) of the matrix B in lemma C.11:
fitring error
BBel
B w
B (B-B") m/
B ()
+ w
B - B(1)
B -BB(())
w T (
B Q-BB B
w +
B B())
w |
B (1)
+ B
op B - B
| 2 +
B B (1)
| 2
op
op
2
B (
+ (1 + 5) 282 1| + 45t ||0112
w
2
2
+ 4
|| 8 (1+5+08
2
< (P- PAP)
w
2
+ 4
||0
1
2
(1+
IM
PA
2
||
0
2
1 2
PA
PA
|P
1 +4 01+8800)
op
$ (1+ 2 PA
Pw
1
+ |
S (1+ [ 28)
Pwll
||
+ |1012 (5 + 48 4 4
Hence we have the upper bound:
bias S 1 + (1 28)
|| Pu 1|22 + || 5'p(6).
We argue similarly for the lower bound using: A llop |10112 2 T A 2 - || llop ||0| for any
A E IR M
V U MXI
We argue similarly for variance.
Proposition C.14 (Variance Approximation), Fix sampling Z such that 8 def || < Z.2 Then
have
M
M
M 2 (1
variance
(1)))))()))
D + X)
(A + A)²
N
where p(5) def. 5 + 48 + 482, and 2² del. 2 is the noise variance.
Proof. Note that A < M || up for any matrix A E MXM, Since Ba + A)
(B()) + A) + (1))) (B - -)) 1 + (B B()) 2 (IM + A), we can bound the residue term by
(IM + A) + B 8--B (D-BO)) 2 (Irr + A)
Tr 2B(1) B (
< <M(1 + 8) B ((1)
(2 [ 1p
+ +|lB-B01 (()
0p
op
- MM + 6) (2
< (1 +1)
+
For the main terms, we have
(II + A)] < THP²)
[IM AP) (Iar + 1)
[p
IM + A 2P) + (AP)2 2APA + (AP)
< TT
LM + A 2P) + M (AP)² - 2APA + (AP) op
Tr|P"
8) + M (1 + 6))
22

---

We apply Theorem C.7 to yield bound on variance:
M
+ M o²
variance
N (1+)))pp())
X)
N
(Ak
X)2
k=
Note that the above propositions C.13 and C. 14 give absolute (non (non-probabilistic) bounds on the test emror, once ô is controlled.
C.3 Concentration Results
In this subsection, focus on bounding the operator norm of the fluctuation matrix A.
First, we establish some concentration results.
Lemma C.15 (Theorem 3.59 in [37]). Let be an N mutrix with independent isotropic sub- Gaussian columns in R" which sub gaussian norm is bounded by positive constant G >> 0. Then for all t 2 0, with probability at least 2 exxp( 2 ). we have
J N
AAT
In
S max(a n²),
(34)
where a def CVN + for all constant C 2 12G
Proof. Let def CVN N VN
with C> >> to be determined, and c dt max(a, a²). The first step to
show that
1 A x
1 Sc
max sEN
sc
N
2 9". T Choose such net N with M (1 + 174
for some -ete A' the sphere -
Let A, be the ith column of the matrix A and let Z₁ A be random variable. By definition of A. Z; is centered with unit variance with sub-Gaussian norm upper bounded by G. Note that
and the random variable Z? centered and has sub-exponential norm upper bounded by 4G2. Hence by exponential deviation inquality 6, have, for any Sn-1;
G 2 R[zg]//2 22'
P{ J N | 2 2 $ =
=P
1 N
z
2 2
1
$ 2 exp
-
) G
- -
=5 2exp
(
S 2exp
(-Ze - G (0
( (onntt? +19).
Then by union bound, we have
1 N
1
max P
A
AAT
1
< 9" -
ZEN
2
1
16-
< 2exp
Thii inequality is Corollary 5.17 from [37].
23

---

for C 2 v 2e log 9G² Since 12 > logl, for simplicity, we assumee C 12G². Moreover, since
G z V2' we have ze G
3. we have
max xEN
A x
2
2 - 2 exp
6
1 t2
N
2
3
Then by the --net argument, with probability at least 1 - 2 exp
(-
we have
1
AAT
I
max JEN
A x
N
N
op
S max (a, a
Lemma C.16. Assume Assumption 4.1 holds and that N exp(4(12G)))(MM + 1)). Then with probability of at least 1 2/N, we have
log N N
max {ō, Earl12)
Proof.
Set n = M + A
SM
E (M
Then
(X)
AAT
In
SM
L
EM
-
A M E
EM
EM
T
+
M
where M/
ii d (2,)²
1. On one hand, the operator norm of the above matrix bounds
8 and | 2l from above:
A M
Ess
A M
max ||ul| -2
E
M
E
17
op
M + E.M
max
|| 2
E + 1/
A M/ u + EE ll2
max
||1|2-===1
max
A A vEM
||,||=1,,0=0
max
A AAuu//2 6.
||
and
A M
Ess
2 max =1
|| A + EM 2 max A + EEM l2 |
E
M>
||l|
lop
On the other hand, set t Vlog N, C= 12G², since N exp(4C + 1)). we have
M+1 W11
log
log <1.
a a=
12G²
+ 2\ N =
N
V
N
N
By Lemma C.16, then with probability of least 1--2exp( we have
(11(2) =1 -cxpe / > 2/N,
A
EM
)
Tog
< max = V
ET
T>
N
Combine the both results and we conclude the upper bounds.
In particular, as N + oc, 8 vanishes almost surely. In empirical calculation, if the requirement is too demanding for large integer M, we can take t = No for any positive number s E (0, 1)) instead of log N. In this way, we decrease the
N exp(4(12G2)) + 1)) exponential
requirement to polynomial M in sacrificing the decay from (V LogN N
to O (N=-1/2). For
simplicity purpose, do not list out the result with this decay in this paper.
24

---

C.4 Refined Test Error Analysis
We can apply the above concentration results refine the following bounds on the finite-rank KRR test enror. First of all, we realize the decay of target function coefficient comparable to the spectral decay:
Definition C.17 (Comparable Decay). Denote r del. ming minx(15k/Aaa (15k/Adl and de max: / }
C.4.1 Refined Bounds on Bias
Recall that Proposition C.13 bounding the bias in terms of and 7%- For the former one, we can choose: for N > max (exp(4(1222) (M 1)),9), by Lemma C.16, with probability of least
1 2/N, we have S V
log N
log N
For the latter one, we have to control the vector we 2"
9
Lemma C.18. Let u XA 1-11
7/2 M
We have
|| < (AFVM + 15 Baaaa|lE1)) [[Eill)) 2
A²AM (AM + 2)2
[ like 3 || Puol2 < X1Issarli l1 -
1
| + 73.r |
Proof. Since 22r2 < | - X and | Eli = -33M ||
E
2 we have
| s (ArV Fi [181112
Similarly, we can bound
Pwll
Observe that:
M
M JA +73M
M
Pwll
2
kk
2A7S M
Xu + 2)
(Ak + 212
(AR + X)2
111
Since 2 dutt 2
Aar we have the upper bound:
I 2
(35)
(Ax X)
A
where JSM det. M M
Ju/2 = f 3/M M. For the lower bound, we have:
M
12
Mf
A
1= 2
2 2
X2
(Aur + a12 Ilffaalli
(36)
(Xx X)2
(Ak + X)2 d
k=
Similarly, since 4AA+ S (A+ + 2)2
M1 1iv Fe mm
M
M
M
1 1
1 F
[ = 2A
15 Ml
Fimmll S
Th
- 2 1i
[1l5sM Ml2 ||
(A+ + A)2
2
2
k++
h+1
k=1
And
M
M
=
S R5.M
mh
73.M
E
(Ax + X)2
k=1
Combining the above result, state the following theorem:
25

---

Theorem C.19. For N > max
+ 1)).9} and for any constant C1 > 2 + ii (independent to N), with a probability of at least - 2/N,
8 (ArVM +
1 2 21
we have the upper and lower bounds of bias:
(d1riiig +2A1f log N
log N
bias S 72-0 + A11fssM lB
+ C1
N
N
bias 2 Pias + (AM + AY2 lIfemiliee (HIFVis +
A²AM
22²
log
log N N
Ci
À +
N
For À + O, we have simpler bound: with a probability of at least 1 - 2/N, we have
8
log N N
log N N
lim bias
11+
3.. 667.M
x-0
(37)
log N $
log N
lim bias
67
2-0
N
For 93 1/M O, that is f H. we have simpler upper bound on bias: with a probability of at least
1 1 2/N, we have
log N N
log N
bias S Al1f1
1 1+
2/
+ +
N
(38)
APAM (AM 2)
log N
log N N
bias
1 - 2
C1
N
Proof. By Proposition C.13 and Lemma C.18. fitting error $ (1 + 28)
Pwl 2 + || pp)(
(39)
< (1 + 25) (All + マ hー ar [ |E]| + A5m || + 11 v())
(40)
< <1 + 25) 11 + + 11 |Ell + + E 1
+ | 8 p()).
(41)
where in line (39), we use Proposition C.13; in line (40), we use Lemma C.18; in line (40), we use the fact that 2ab s a² 8² where a = // b = |lfgarllug.
Now we apply the concentration result in Lemma C.16: with a probability of at least 2/N:
log N
log N
fitting error -
1 2
All.f 11 + 7
11
N
log N + N
[|mm12
p(d) [|u]2p(00=
+ (1+ 20) + +111f111,
( [1151122 + 2N1 +211 FE
llog N N
log N N
$ Al 1 +
+ +C1
where we choose Cj > 0 to be such that:
1)
|| p(6) (1 + 28)53 + 111112 < | (00l((())) p(0)
[1 +-22
2
< 1w062 + (1 (1 2
1
I15
+ 2/
2
5
8 Arv M + hism
[|
+
2 f1ffli:
2
5
< 8 Xrv ArVM M + =2
+ 2
< <..
26

---

Hence we have an upper bound for the bias. We argue similarly for the lower bound:
log
A²AM (AM + X)2 1l2e
1
log
fitting error 2
1 2 2/
7
1111113 N
N
log N
(1wo1B (() + (1 +26)555 + +17 +17 1Il
N
(Ax + 2\2 1lfa (1 fl.fligg
Aa
d1 x [1 [1f
2x
V
log N
C1
log N
For À + 0, note that w + > E. This yields
< lim { (1 + 26) |wil + | 2 52p(6) } x-0
lim fitting error X-0
= =(1+ + 26) 11 E12 + +| - 21 p(6)
= -35M E (1 + 8(2 + 5p())))
Hence, by plugging in 8 < 2. with probability of at least 1 2/N,
log N
log N
lim fitting error S 75 A
1 11+6
N
N
log N
log N
Tim bias
S
1
3.. + 65.MM
A
For lower bound, it follows similarly:
lim bias
(1-
log N
N ?>M M 693
log N
A-0
and we obtain line (37). For the case where ?>M = 0, recalculate and simplify line (40) to obtain line (38).
C.4.2 Refined Bounds on Variance
Similarly, we can refine Theorem C.14 to get a bound on the variance:
Theorem C.20. For N > max ((12G)(M + 1)2,9}, and set C2 = 12 (independent to N), with
probability of at least 1 2/N, we have the upper and lower bounds of variance:
variance S 0² M
log N
log N N
1+
+
C2
N
X2 (AM + A)2
M
log N N
C2a2 2 M log N
variance
N
N
N
Proof. We argue analogously in Theorem C.19: by Proposition C. and Lemma 1. we have
M
M o² N (1
variance S (1 5)
11+8)6pp(0 p(0)
N
(AR + l)K
M
M
< (1 + 6)0
(1 + 8)82p(6)
N
N
log N
M
M log N N
1
1 2
+
+
t
1+ p
N
N
log
N
M
120 2 M log N
1 +
N
N
N
N
27

---

x2
Xir
Hence we can choose C2 12. For the lower bound, since
+AJ+ we have
(Ap-A)
2
M 0²
variance 2 (1
(1
+())2p(6)
N
(Au + +222
N
.
log N
M log N
2
1-
12x
(Axr + X)2
N
N
N N
Note that in both Theorems C.19 and C.20, the constants C1, C2 > 0 is not optimized.
D Numerical Validation
In this section, we illustrate our result for KRR with two different finite rank kernels.
D.1 Truncated NTK
First, we need to define a finite-rank kernel K X x R. We set X = = R By
reparametrization, we write g ~ [0, [2m]/o-22 We assume the data are drawn uniformly on the circle, that is Px uni We can use the Fourier functions cos(k)), sin(())) as the orthogonal eigenfunctions of the kernel. We define the NTK
(x)) der. cos(@ 8') (T 1 1
2x
for all 0' E [0, We choose rank-M truncation k0) Σk=1 A (0) ()))))(()))))))))))))))))) (0') for all
0, 0' E [0, 2T). For the first few eigenvalues of the kernel, please see Table 3 for example. Before
k
4
8
Ae
5
17
17 225m
9
Sw2
225m
(0)
v2 co)
v (i)
V2 cos(8))
v sin(
2 cos((49)
v2 sin(6))
E* LI=ED Ave
0.1013
0.2263
0.3513
0.4076
0.4639
0.4716
0.4792
0.5
Table 3: The first few eigenvalues the NTK
proceeding test computation, present training example, Figure 4, to give readers intuition on the truncated NTK (INTK).
NTK Training
tNTK Training
1.
A
Targer Funcion
Target Function
Regressor
Regresacr
Sample
Sample
Figure 4: (left): NTK training; (right): tNTK training where N = 50, M = 7. 0² = -0.5,
a² o²/N.
28

---

D.2 Test Error Computations
In the following tNTK training, we set the hyperparameters as follows:
Target function We choose simple target function f(x) cos V2 (2() Throughout the experiment, we set the noise variance x² = 0.05.
N. In Figure 5 (left), we set N = 50, À 0.05/50 for tNTK training; (right) we set set 0.05/50 for varying N from 10 200.
Ridge We choose À o²
Error bars In Figure 7 (right), for each value of N, we run over 10 iterations of random samples and compute the test error. The enror bars shown the difference between the upper and the lower quartiles.
tNTK training
Varying Sample Size
0.19
10
Median
0.14
Quartiles
0.12
Test Error
0.10
0.0
0.m
0.05
Target Function Regressor
-05
0.M
Sample
0.2
0.0
X
N
Figure 5: (left): (NTK training; (right): the decay of test error as varies.
Lower bound See the subsection below.
D.3 Bound Comparison
We continue with the experiment on the tNTK this time with varying N and compare our upper bound with [6].
Upper bounds Figure 6, the expression of Bach's and our upper bounds are directly computed:
80 122
Bach's upper bound 4 + AN
(1 + 2lg N)
log N
Our upper bound without residue 21
1 11-2//
N
where the constants | and R can be computed directed from the choice of kernel and target
function. For simplicity reason, we drop the residue term C₁ log N since it is overshadowed by the other terms and the constant C₁ is not optimized.
D.4 Legendre Kernel
To illustrate the bounds with another finite-rank, we choose simple legendre kernel (LK):
K K(x, 2) Σ (xPa(()
k=0
where Pk is the Legendre polynomial of degree k. and A > O are the eigenvalues.
29

---

Throughout Varying Sample Size on tNTK
Varying Ridge on tNTK
log Scale
Bach's Upper Bound
Bach's Upper Bound our Upper Bound
our Upper Bound
1000
1/A
Figure 6: Test error bound improvement tNTK. Same as Figure 2.
Eigenvalues To better compare the Legendre kernel K with the NTK, we choose dE C-(K+1)-2 of quadratic decay such that the spectral sums are the same: E A 0.5. Hence choose C' = 0.5/ E
Target function We choose simple target function f(x) x² PPo((( + ( P2().. the experiment, we set the noise variance o² 0.05.
D.5 Test Error Computation
Ridge As before, our bound suggests that, to balance the bias and the variance with fixed N, we In Figure 7 (left), set N 50, 0.05/50 55 for KRR training; (right) we set set = 0.05/50 for varying N from 10 to 200.
choose À o² N.
Error bars In Figure 7 (right), for each value of N, over 10 iterations of random samples and compute the test error. The error bars are shown as the different between the upper and the lower quartiles. The median is taken average.
Legendre Kernel Training
Varying Sample Size
Regressor
Median
0.06
Target Function
Quartiles
Sample
Test Error
X
N
Figure (left): LK training; (right): the decay of test error as N varies. Same as Figure
30

---

Upper bounds
In Figure 8, the expression of Bach's 's and our upper bounds are directly computed:
80 R2
Bach's upper bound 4111s1 +
(1 + 2 N)
AN
log N
Our upper bound without residue Allfl
1 1 2
N
where the constants |1/ and R2 can be computed directed from the choice of kernel and target function.
Varying Sample Size on LK
Varying Ridge on LK
log Scale
Bach's Upper Bound
Bach's Upper Bound our Upper Bound
our Upper Bound
-2
-3
100
800
1002
N
1/X
Figure 8: Test error bound improvement on LK. Same Figure 2.
Lower Bound Last but not least, we need to show our lower bound is valid. To see this clearly, we need to write the bound in exact sums instead of in HKRS norm square [| namely, we compute
A (AM X)
M
| < T
A)2 S >1
(42)
2
De
k=1
instead of using the inequality (42) in Lemma C.18; and
X
M ( + x)
xyz S M,
(43)
(
instead of using the inequality (42) in Theorem C.20. Then we can compute our bounds as:
log N
X
log N
Our upper bound without residue A²I 1 + 2
1
N
(Ax
X)
N
log N
M
X
log N
Our lower bound without residue 121
1 2/
N
N
DA +
X)2
N
and we drop the residue terms C1 log N and C2 o² . log N N by the same reason before. From Figure 3, we can see that our bounds precisely describe the decay of the test error. Our bounds are not "bounding" the errors smaller instances due the absence of the residue terms, which increases the interval of confidence of our approximation. But for larger instances, say N 100, all upper and lower bounds, and the averaged test error converge to the same limit.
31

---

Test Error on tNTK and its Bounds
log Scale
0.16
u.b. w/o Residue
U.b. w/o Residue
6.16
I.b. w/o Residue
I.b. w/o Residue
Median
Median
Test Error
Quartiles
Quartiles
log scale
25
50
100
125
150
175
200
25
50
75
100
125
130
175
200
N
Test Error on LK and its Bounds
log Scale
u.b. w/o Residue
u.b. w/o Residue
I.b. w/o Residue
I.b. w/o Residue
Median
Median
Test Error
Quartiles
Quartiles
0.01
6.00
125
175
200
103
150
200
N
Figure 9: Our bounds comparing the averaged test error with varying N, over 10 iterations. Same as Figure 3.
32


Reviews:
[{"review_id": "srpdExwRhU", "reviewer": "Reviewer_MpJJ", "summary": "This paper gives a refined analysis of the test error of kernel ridge regression with a finite kernel in the underparametrized regime, where the rank M of the kernel is smaller than the number of data points N. The analysis improves upon previous ones by providing tighter non-asymptotic upper and lower bounds, which remain tight even as the ridge parameter goes to zero. When the target function lies in the RKHS, the bounds show that estimation is consistent as N goes to infinity.", "questions": "- Can the authors elaborate the technical difficulties in extending beyond the finite rank setting, or even when M ~ N? Can analogous results be shown when the kernel is approximately low rank?\n\n- It is unclear that realistic NTK or random features will fall in this underparametrized regime. Can the authors give elaborate if this should be the case? Is it possible to experiment in more realistic NTK settings to truncate the kernel and apply the bounds?", "limitations": "No limitations. Authors give some directions or future work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and clear. The authors state the contributions clearly and compare carefully with previous work. Establishing tight bounds for this basic learning setting is an important problem.", "weaknesses": "No major weaknesses, just some minor typos. I would also suggest that the authors include the explicit lower bounds in the main paper. Given that this a major focus of the paper it should not be required for the reader to go to the appendix. It would also be nice for the appendix to give a bit clearer account for the technical differences in the proof techniques of their bounds versus previous ones.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Explicit lower bound\n\n**\\[review\\]** *“I would also suggest that the authors include the explicit lower bounds in the main paper. Given that this a major focus of the paper it should not be required for the reader to go to the appendix.”*\n\n**\\[answer\\]**  We concur with the reviewer's viewpoint and, consequently, plan to relocate the lower bound in the main theorem and move the proof technique section to the appendix.\n\n## Technical tool\n\n**\\[review\\]** *“It would also be nice for the appendix to give a bit clearer account for the technical differences in the proof techniques of their bounds versus previous ones.”*\n\n**\\[answer\\]** The main technical tools we used in the paper are 1) more careful algebraic manipulations when dealing with terms involving the regularizer $\\lambda$ and 2) a concentration of the spectrum of a centered random matrix with sub-Gaussian entries followed by the Neumann series expansion of a matrix inverse. To this end, we require that $M<N$, such that the fluctuation matrix $\\mathbf{\\Delta}\\in\\mathbb{R}^{M\\times M}$ is of full rank with operator norm converges to zero as $N\\to\\infty$, then we argue with Neumann series expansion in $\\mathbf{\\Delta}$, instead of in the terms with leading factor $\\lambda$. Hence, unlike previous work, our result holds for any $\\lambda>0$ which can be chosen independence to $N$. See Section C.2 in the appendix for details.\n\n## Under-parametrized regime\n\n**\\[review\\]** *\"Can the authors elaborate the technical difficulties in extending beyond the finite rank setting, or even when M ~ N?\"*\n\n**\\[answer\\]** In the main theorem, we require $N$ to be exponential in $M$ in order to have a decay of the order $\\frac{\\log N}{N}$. But as indicated in the remark of Lemma C.17 (lines 547 - 551) in the appendix, we can relax the requirement that N to be only polynomial in M, with the tradeoff of a slower decay rate. For the case $M=N$, it is where the well-known variance explosion would happen unless we regularize, that is, unless $\\lambda > 0$. Since this paper focuses on bounding the test error with a general $\\lambda$, we refer the readers to [Bach (2023)](https://www.di.ens.fr/~fbach/ltfp_book.pdf) for the test error bound for $M\\geq N,\\ \\lambda > c$. For over-parametrized regime ($M>N$) where the kernel is approximately low-rank, our strategy does not does not apply, but it is one of our future research direction. Note that there are already some published non-asymptotic result, for instance, see  [Tsigler and Bartlett (2023)](https://www.jmlr.org/papers/v24/22-1398.html). \n\n## Practical use\n\n**\\[review\\]** *\"It is unclear that realistic NTK or random features will fall in this underparametrized regime. Can the authors give elaborate if this should be the case? Is it possible to experiment in more realistic NTK settings to truncate the kernel and apply the bounds?\"*\n\n**\\[answer\\]** The NTK of any finite-width (shallow) fully-connected network is finite-dimensional with random eigenfunctions. For simplicity, we truncate the NTK (of a infinite-width network) by selecting only the first few eigenfunctions in the experiment as a toy example. In general, as long as the sample size $N$ is larger than the number of trainable parameters in the network, our result can be applied. In practical scenarios like fine-tuning or transfer learning in large language models, most of the pre-trained parameters are fixed except the last layer (see Section 2) or smaller low-rank matrices as in the popular LoRA approach [Hu et al.(2021)](https://arxiv.org/pdf/2106.09685.pdf). In this case, the training is simply a kernel ridge regression in the under-parametrized regime. We regard further analysis of such specific model trainings as a future research dierection. \n"}, {"review_id": "10ZSfGsC9W", "reviewer": "Reviewer_Gn3m", "summary": "The paper studies the kernel ridge regression under the non-asymptotic setting. The authors give the upper and lower bounds for bias and variance term, respectively. The authors argue the results improve upon those in Bach 2023.", "questions": "Could the authors mention the lower bound for the problem? \n\nWith optimal choice of \\lambda, we can derive the optimal upper bound for the test error. However, the current result does not show a bias-variance tradeoff with respect to \\lambda. Could the authors explain?", "limitations": "No.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The paper is well-structured. The authors give rigorous proofs, following by careful experiments.", "weaknesses": "1. The paper requires further improvement and polishing in writing. To name a few, line 57-58; line 107-110.\n\n2. The paper would benefit from a more consistent and standardized use of symbols and notations. For example, in line 90, it would be better to use L_2(\\rho) instead of L_\\rho^2. In lien 92, the notation of \\tilde{f}(\\textbf{X}) is not proper. In Definition 3.1, it would be better to include the decreasing order of eigenvalues in the statement rather than adding an additional remark 3.2. In line 200-207, notation K^{(\\infty)}\n\n3. As mentioned in Bach 2023, more refined bounds can be found in Rudi et al. 2015, Rudi and Rosasco 2017. However, the authors failed to mention them and other related results in the comparison. In the absence of such comparisons, it is hard to tell the novelty and improvements of the current submission.\n\n4. The dependency of \\lambda seems to be incorrect for the variance term.\n\n5. Given Corollary 4.3.1 in the submission, I cannot see significant improvements against those in Bach 2023. Also, the authors did not give a proper explanation for considering \\lambda goes to 0.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Polishing\n**\\[review\\]** *\"The paper requires further improvement and polishing in writing.\"*\n\n**\\[answer\\]** Thank you for pointing out certain issues with the writing; we will address them in the revised edition. \n\n## More references\n\n**\\[review\\]** *\"As mentioned in Bach 2023, more refined bounds can be found in Rudi et al. 2015, Rudi and Rosasco 2017. However, the authors failed to mention them... it is hard to tell the novelty and improvements of the current submission.\"*\n\n**\\[answer\\]** We agree with the comment made by the reviewer and will discuss both papers  [Rudi et al. (2015)](https://papers.nips.cc/paper_files/paper/2015/hash/03e0704b5690a2dee1861dc3ad3316c9-Abstract.html), [Rudi and Rosasco (2017)](https://proceedings.neurips.cc/paper_files/paper/2017/file/61b1fb3f59e28c67f3925f3c79be81a1-Paper.pdf)  as related work in the revised edition.The citations were not included in the current submission because their focus is on the upper bound of the test error for specific sketching algorithms (Nyström approximation and random feature) while our work focuses on any under-parametrized finite rank kernel ridge regression. One main contribution is that we provide both tighter upper bound and tighter lower bound than the two (they derive the same convergence rate on the upper bound up to constants but they do not derive a lower bound). Another major difference is that our bound works for any regularization $\\lambda$, while the mentioned prior works require it to be dependent on the sample size $N$ (we for instance refer the reviewer to Theorem 1 in  [Rudi and Rosasco (2017)](https://arxiv.org/abs/1602.04474)). \n\n## Dependence on $\\lambda$\n\n**\\[review\\]** *\"The dependency of $\\lambda$ seems to be incorrect for the variance term.\"*\n\n**\\[answer\\]**\nFor simplicity in the main theorem, we have suppressed the dependence of $\\lambda$ in the variance by upper bounding the term $S=\\sum_{k=1}^M\\frac{\\lambda_k^2}{(\\lambda_k+\\lambda)^2}$ by M. Please see Proposition C.14 for a more detailed bound on the variance. Indeed this sum $S$ is less than the so-called effective dimension $\\mathcal{N}_M(\\lambda) =\\sum \\frac{\\lambda_k}{\\lambda_k+\\lambda}$, which appears in the upper bound of the variance in Lemma 6 in [Rudi and Rosasco (2017)](https://arxiv.org/abs/1602.04474)). Ultimately, our bound is sharper. \n\n## Contribution of Corollary 4.3.1\n\n**\\[review\\]** *\"Given Corollary 4.3.1 in the submission, I cannot see significant improvements against those in Bach 2023.\"*\n\n**\\[answer\\]** The three major improvements are: a lower bound (that matches the upper bound up to constants), a better dependence on $\\lambda$ (note that prior bound are vacuous for small $\\lambda$, see details above) and tighter leading coefficients. Please also see our experimental results (Figure 2) that clearly shows significant improvements of our bounds.\n\n## Ridgeless regression\n\n**\\[review\\]** *\"Also, the authors did not give a proper explanation for considering $\\lambda$ goes to 0.\"*\n\n**\\[answer\\]** Stating the case where $\\lambda\\to0$ is a way to understand the role of regularization. It also gives us some insights into the behavior of the bound for small (but non-zero) values of $\\lambda$, for which our bound is also tighter than prior work. In practical scenarios, excessive l2-regularization can adversely affect test error, making smaller values of $\\lambda$ equally noteworthy.\n\n## Lower bound\n\n**\\[review\\]** *\"Could the authors mention the lower bound for the problem?\"*\n\n**\\[answer\\]** Yes, we have addressed the lower bounds in Theorems C.20-21 in the appendix and this is to our knowledge novel. We will do as you suggest and explicitly state them in the main theorem.\n\n## optimal choice of $\\lambda$\n\n**\\[review\\]** *\"With optimal choice of $\\lambda$, we can derive the optimal upper bound for the test error. However, the current result does not show a bias-variance tradeoff with respect to $\\lambda$. Could the authors explain?\"*\n\n**\\[answer\\]** From the previous paragraphs, it is possible to derive an optimal $\\lambda>0$ to balance the bias-variance tradeoff which depends on the kernel spectrum. We will put this as a possible future research direction. \n"}, {"review_id": "tLpr11K8nw", "reviewer": "Reviewer_cigT", "summary": "This paper analyzes the test error of ridge regression with a finite rank kernel. The finite rank kernel appears in several practical settings such as transfer learning and random neural networks. The authors provide a new analysis in this setting using tools from random matrix theory. A detailed comparison to other generalization bounds is presented.", "questions": "1. The bound in Theorem 4.1 and the bound in Eq. (12) both scale as $\\sqrt{\\frac{\\log(n)}{n}}$. Which one is tighter and why? What is C in Eq. (12)?\n2. The test error definition is not standard: Shouldn’t the label be $y$ in the MSE and not $\\tilde{f}$? Is the definition of the test error the same in other works? Also, the bias-variance decomposition does not seem to be standard. Usually the learned predictor is the same in the bias expression (e.g., see the Wikipedia definition of bias-variance decomposition), whereas here the predictor is different: it changes from $f_{Z,\\lambda}$ to $f_{(X,f(X)),\\lambda)}$. Is this standard for analyzing kernel methods?\n3. Where in the analysis is the under-parameterized assumption ($M <N$) needed?\n4. In Eq. (10) if $\\tilde{\\gamma}_{>M} = 0$, the bias is exactly zero for all $N$? Is this a mistake?\n\n", "limitations": "Limitations are not discussed in detail. Some of the limitations are mentioned throughout the paper. Maybe it will be helpful to add a limitations section and summarize all limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. New generalization results in a practical and challenging setting.\n2. New analysis techniques.\n", "weaknesses": "1. The comparison to standard generalization results is not clear (Eq. (12)). Both bounds scale as $\\sqrt{\\frac{\\log(n)}{n}}$. It is not clear which one is tighter.\n2. The technical details of the proof are not given and the novelty of the analysis is not explained in detail. Instead, most of the paper is devoted to a discussion and experiments.\n3. There are some unclear technical issues (see questions below).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Technical details and novelty\n\n**\\[review\\]** *”The technical details of the proof are not given and the novelty of the analysis is not explained in detail.”*\n\n**\\[answer\\]** We will refactor the revised paper so that these things are stated more clearly and more prominently, while relegating some of the numerics to the appendices. Due to space constraints in the paper, we apologize for the absence of a paragraph dedicated to technical details. In short, the main technical tool we used in the paper is the concentration of the spectrum of a centered random matrix with sub-Gaussian entries followed by the Neumann expansion of a matrix inverse. Another novel aspect is that we demonstrate how this same novel technique can also be used to derive the lower bound for the test error.\n\n## Rademacher bound in Equation (12)\n\n**\\[review\\]** *”The bound in Theorem 4.1 and the bound in Eq. (12) both scale as \n $\\frac{\\log N}{N}$. Which one is tighter and why? What is C in Eq. (12)?”*\n\n**\\[answer\\]**\nHere is Theorem 10.7 from [Mohri et al. (2018)](https://cs.nyu.edu/~mohri/mlbook/): \n> Let $K:\\mathcal{X}\\times\\mathcal{X}\\to\\mathbb{R}$ be a PDS kernel, $\\mathbf{\\Phi}:\\mathcal{X}\\to\\mathcal{H}$ a feature mapping associated to $K$, and $H=\\\\{ x\\mapsto\\mathbf{w}\\cdot\\mathbf{\\Phi}:\\\\|\\mathbf{w}\\\\|\\_\\mathcal{H}\\leq\\Lambda \\\\}$. Assume there exists $r\\>0$ such that $K(x,x)\\leq r$ and $\\|f(x)\\|\\leq \\Lambda r$ for all $x\\in\\mathcal{X}$. Then for any $\\delta>0$, with probability at least $1-\\delta$, the following holds for all $h\\in H$:\n$$ R(h) \\leq \\hat{R}(h) + \\frac{8r^2\\Lambda^2}{\\sqrt{N}}\\Big(1+\\frac{1}{2}\\sqrt{\\frac{\\log \\frac{1}{\\delta}}{2}}\\Big), $$\n> where $R(h)=\\mathbb{E}_x[(h(x)-\\tilde{f}(x))^2]$ is the test error and $\\hat{R}(h)=\\frac{1}{N}\\sum\\_{i=1}^N[(h(x\\_i)-\\tilde{f}(x\\_i))^2]$ is the train error.\n\nOur bound in Theorem 4.1 is tighter than equation (12) in two ways: first, the decay rate of bias bound in equation (10) is $\\frac{\\log N}{N}$ as $\\lambda\\to0$, which one cannot obtain in Rademacher bound, since it is insensitive to $\\lambda$; second, the total decay in the variance bound in equation (9) is $\\frac{1}{N}\\cdot\\sqrt{\\frac{\\log N}{N}}$.\n\n## Test error and bias-variance decomposition\n\n**\\[review\\]** *”The test error definition is not standard… Is the definition of the test error the same in other works? Also, the bias-variance decomposition does not seem to be standar…Is this standard for analyzing kernel methods?”*\n\n**\\[answer\\]** Our definition of test error measures the difference between the regressor trained on a noisy sample and the (noiseless) target function, which is standard in KRR research, and is equivalent to, for example, the generalization error in [Mohri et al. (2018)](https://cs.nyu.edu/~mohri/mlbook/) , the integrated square risk in [Liang (2019)](https://arxiv.org/abs/1808.00387), out-of-sample risk in [Hastie et al. (2020)](https://arxiv.org/abs/1903.08560), excess risk in [Bach (2023)](https://www.di.ens.fr/~fbach/ltfp_book.pdf). Previous works and we choose this definition as the noise only comes from the noisy sample (train set), but not from the test point. Indeed, we have\n$$ \n\\mathbb{E}\\_{x,y} [(f\\_{\\mathbf{Z},\\lambda}(x)-y)^2] \n= \\mathbb{E}\\_{x,\\epsilon}[(f\\_{\\mathbf{Z},\\lambda}(x)-\\tilde{f}(x)-\\epsilon)^2]\n= \\mathbb{E}\\_{x}[(f\\_{\\mathbf{Z},\\lambda}(x)-\\tilde{f}(x))^2] - 2\\mathbb{E}\\_{x,\\epsilon}[\\epsilon(f\\_{\\mathbf{Z},\\lambda}(x)-\\tilde{f}(x))] +\\mathbb{E}\\_{x,\\epsilon}[\\epsilon^2]\n$$\n$$\n= \\mathbb{E}\\_{x}[(f_{\\mathbf{Z},\\lambda}(x)-\\tilde{f}(x))^2] + \\sigma^2\n$$\nsince $\\epsilon$ is noise with mean zero and variance $\\sigma^2$ independent to $x$.\nNote that we are averaging over all test points $x$ but fix the sample $\\mathbf{Z}$ (as done in prior work, e.g. [Bach (2023)](https://www.di.ens.fr/~fbach/ltfp_book.pdf)), and our main theorem gives high probability bound over the sampling $\\mathbf{Z}$ on the average mean square distance between the regressor and the target function. Also, our bias-variance decomposition is also standard and performed the same as in the above cited works, where we separate the effect of the sample noise to the test error as the variance. we will add a remark in the revision.\n\n## Under-parametrization\n\n**\\[review\\]** *”Where in the analysis is the under-parameterized assumption ($M<N$) needed?”*\n\n**\\[answer\\]** The requirement that $N>M$ ensures the fluctuation matrix $\\mathbf{\\Delta}\\in\\mathbb{R}^{M\\times M}$ is full-rank with operator norm that converges to zero as $N\\to\\infty$, then we argue with Neumann series expansion. Please see Section C.2 in the appendix for details.\n\n## Consistent case ($\\tilde{\\gamma}_{ > M}=0$)\n\n**\\[review\\]** *”In Eq. (10) if $\\tilde{\\gamma}\\_{ > M}=0 $, the bias is exactly zero for all $N$? Is this a mistake?”*\n\n**\\[answer\\]** Note that for $\\tilde{\\gamma}\\_{ > M} = 0 $, we have the target function $\\tilde{f}$ belongs to the finite-dimensional RKHS $\\mathcal{H}$. Indeed, since the bias measures the fitness of the regressor with a noiseless sample $(\\mathbf{X},\\tilde{f}(\\mathbf{X}))$, and if there is no regularization, we have the regressor\n\\begin{equation*}\n\tf_{(\\mathbf{X},\\tilde{f}(\\mathbf{X})),\\lambda} = \\arg \\min\\_{f\\in\\mathcal{H}}\n\\sum_{i=1}^N(f(x)-\\tilde{f}(x))^2\n\\end{equation*}\nand it is clearly equal to $\\tilde{f}$, hence the bias $\\mathbb{E}\\_x[(f\\_{(\\mathbf{X},\\tilde{f}(\\mathbf{X})),\\lambda}-\\tilde{f})^2]=0$ and this is no mistake.\n"}, {"review_id": "WkqpLFWQPO", "reviewer": "Reviewer_S6gY", "summary": "The paper highlights the inadequacy of existing statistical learning guarantees for general kernel regressors when applied to finite-rank kernels. The authors have addressed this issue by developing non-asymptotic upper and lower bounds for the test error of finite-rank kernel ridge regression. These new bounds are more precise than the previously established ones and are applicable for any regularization parameters. This research provides a more dependable framework for utilizing finite-rank kernels in machine learning applications.", "questions": "1. It looks a little bit weird that you don't need to take $\\lambda=O(N^\\theta)$ for some $\\theta<0$ to balance the bias and variance. Any insights for this?\n\n2. In Theorem 4.1 and Corollary 4.3.1, what are the mild conditions on the kernel K? I cannot find the mild condition on input distribution either.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper addresses an important gap in the current understanding of machine learning algorithms by developing more accurate and reliable bounds for finite-rank kernel ridge regression, which is frequently used in practical applications.\n\n2. The research provides a more precise and dependable framework for using finite-rank kernels in machine learning problems, which could result in better performance and more efficient algorithms.", "weaknesses": "1. The paper only considers under-parameterized regime.\n\n2. Low bound is a main argument of this paper, but all details are given in the Appendix.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Lower bound \n**\\[review\\]** *”Low bound is a main argument of this paper, but all details are given in the Appendix.”*\n\n**\\[answer\\]** Yes, we should have stated the lower bound in the main theorem explicitly. As mentioned in responses to other reviewers, it is in hindsight very clear to us that the lower bound should have been duly highlighted in the main text; we will do so in the revision\n\n## Dependence of $\\lambda$ w.r.t. $N$ \n\n**\\[review\\]** *”It looks a little bit weird that you don't need to take $\\lambda=O(N^\\theta)$\n for some $\\theta<0$...?”*\n\n**\\[answer\\]** Indeed, this is one of the key contributions of our work. Compared with [Rudi et al. (2015)](https://papers.nips.cc/paper_files/paper/2015/hash/03e0704b5690a2dee1861dc3ad3316c9-Abstract.html), [Rudi and Rosasco (2017)](https://proceedings.neurips.cc/paper_files/paper/2017/file/61b1fb3f59e28c67f3925f3c79be81a1-Paper.pdf) and [Bach (2023)](https://www.di.ens.fr/~fbach/ltfp_book.pdf), in our theorem, the regularization $\\lambda$ can be chosen independent of sample size $N$ or kernel rank $M$.\n\n## Balancing bias and variance\n\n**\\[review\\]** *”It looks a little bit weird that you don't need to take $\\lambda=O(N^\\theta)$\n for some $\\theta<0$ to balance the bias and variance. Any insights for this?”*\n\n**\\[answer\\]** For simplicity in the main theorem, we have suppressed the dependency of $\\lambda$ in variance by upper bounding the term $S=\\sum_{k=1}^M\\frac{\\lambda\\_k^2}{(\\lambda\\_k+\\lambda)^2}$ by $M$. Please see Proposition C.14 for a more detailed approximation of the variance. Hence it is possible to derive an optimal $\\lambda>0$ to balance the bias-variance tradeoff which depends on the kernel spectrum. Since we have the lower bound as well, such $\\lambda$ would be minimax optimal. Traditional analysis suggests $\\lambda$ should be in the magnitude of $\\sqrt{\\sigma}$, but our detailed analysis could also relate the choice $\\lambda$ with the spectrum $\\lambda_k$. We will put this as a possible future research direction. \n\n## Mild condition\n\n**\\[review\\]** *”In Theorem 4.1 and Corollary 4.3.1, what are the mild conditions on the kernel K? ”*\n\n**\\[answer\\]** The mild condition on the kernel $K$ is indeed Assumption C.15, stating for $x\\sim\\rho$, the distribution $\\psi\\_k(x)$ is sub-Gaussian with sub-Gaussian norm bounded from above, where $\\psi\\_k$ is any eigenfunction of $K$. Note that for compact input space $\\mathcal{X}$ and finite rank $M$, Assumption C.15 always holds, since any bounded distribution is sub-Gaussian. This assumption is often used in KRR results, for example, in [Tsigler and Bartlett (2023)](https://www.jmlr.org/papers/v24/22-1398.html). \n"}, {"review_id": "jxRb0tnMNP", "reviewer": "Reviewer_BvqB", "summary": "The authors address the problem of kernel ridge regression with a finite rank kernel, in the under-paramatrized regime. They prove sharper upper bounds on the test error, compared to previous existing works.", "questions": "- (minor) While the comparison with the bound of [6] in Fig. 2 is compelling, is there a reason why the bound of [30] is not also plotted? Its addition, or a brief sentence justifying its non-inclusion, would be welcome.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The discussion is very well-written and easy to follow, with a number of illustrations being provided to set up the problem. Careful and detailed comparison to previous work is given, making it easy to understand the novelty of the present manuscript. Overall, the addressed problem is an important one, and I believe the derived bound will be of interest to the community. I have not checked the proof, and therefore give a low confidence score.", "weaknesses": "I do not have any major concern. A minor remark is that while all experimental details are provided in Appendix D, it would be good to add at least a short description of the target functions and regularization used in Fig.1 and 2 in the main text or in the corresponding captions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Experimental details\n\n**\\[review\\]** *” A minor remark is that while all experimental details are provided in Appendix D, it would be good to add at least a short description of the target functions and regularization used in Fig.1 and 2 in the main text or in the corresponding captions.”*\n\n**\\[answer\\]** Thank you for your suggestion; we will illustrate the experiments in more detail in the revised edition.\n\n## Not plotting Rademacher bound\n\n**\\[review\\]** *”While the comparison with the bound of [6] in Fig. 2 is compelling, is there a reason why the bound of [30] is not also plotted? ”*\n\n**\\[answer\\]** The Rademacher bound is independent of $\\lambda$, hence if we pick a very small $\\lambda$, its learning curve as a function of $N$ would be way higher than ours and Bach’s. We will indeed add a sentence about this in the revised version, thank you for pointing this out.\n"}]

Author rebuttal:
**General response to all the reviewers:** Thank you for your comprehensive review of our paper. We sincerely appreciate the time and effort you have dedicated to evaluating our work.

Below, we outline the primary issues highlighted by the reviewers based on our interpretation of their feedback. We would be grateful if the reviewers could indicate if they have any additional inquiries or if they find our responses satisfactory.

### Lower bound of the test error
We acknowledge your valuable feedback regarding the need for emphasizing the lower bound of the test error in the main text. This aspect represents a significant and novel contribution of our research since we are not aware of other prior work deriving a lower bound that matches the upper bound. We will ensure that it receives proper attention in the revised version.

### Dependence of $\lambda$
In our paper, the regularization $\lambda$ can be chosen to be any positive number independent of $N$, in contrast to previous works (please see individual rebuttals for more details). This is also a novel contribution of our research.

### Technical details
Additionally, we understand the importance of providing more technical details in the main text to aid readers in understanding the overall proof procedure. We provide further details in the detailed answers and we will make the necessary improvements to address this concern.


We kindly request you to please refer to our detailed rebuttals to the individual reviews provided below. Once again, we sincerely thank you for your thoughtful evaluation and valuable suggestions.

Meta-review: The paper elegantly contributes by analyzing kernel ridge regression in finite dimensions, offering sharp and novel insights. It's remarkable to find fresh results in this mature field, yet the paper effectively defines its scope and presents these findings clearly.
Decision: Accept (poster)