On the Saturation Effect of Kernel Ridge Regression
Authors: Yicheng Li
Haobo Zhang
Qian Lin
Venue: ICLR 2023 poster (2023)
Keywords: Kernel ridge regression
Saturation effect
Reproducing kernel Hilbert space
Learning theory

Abstract: The saturation effect refers to the  phenomenon that the kernel ridge regression (KRR) fails to achieve the information theoretical lower bound when the smoothness of the underground truth function exceeds certain level. The saturation effect  has been widely observed in practices and a saturation lower bound of KRR has been conjectured for decades. In this paper, we provide a proof of this long-standing conjecture.

Published as a conference paper at ICLR 2023
ON THE SATURATION EFFECT OF KERNEL RIDGE REGRESSION
Yicheng Li & Haobo Zhang
Center for Statistical Science, Department of Industrial Engineering Tsinghua University, Beijing, China
(liyc22, zhang-hb21 @maallss 1s. .wtpsaaaedu..oom adu.cn
Qian Lin
Center for Statistical Science, Department of Industrial Engineering Tsinghua University, Beijing, China and
Beijing Academy of Artificial Intelligence, Beijing, China caanin@tsinghin edu. cn
ABSTRACT
The saturation effect refers to the phenomenon that the kernel ridge regression (KRR) fails to achieve the information theoretical lower bound when the smooth- ness of the underground truth function exceeds certain level. The saturation effect has been widely observed in practices and saturation lower bound of KRR has been conjectured for decades. In this paper, we provide a proof of this long- standing conjecture.
INTRODUCTION
Suppose that we have observed n i.i.d. samples { 3:) from an unknown distribution sup- ported on A' x ) where C Rd and y C R. One of the central problems in the statistical learning theory is to find a function f based on these observations such that the generalization error
B(s,a)> (f(x) -
(1)
small. It is well known that the conditional mean f (1)) = E,ly x = ydl(ylæ) minimizes the square loss E(f) (f(())) y)2 where p(z](z) is the distribution of y conditioning Thus, this question equivalent to looking for an ff such that the generalization error
Ezna
small, where y1 is the marginal distribution of p in X. other words, can be viewed as an estimator of fü. When there is explicit parametric assumption made the distribution p the function f researchers often assumed that f falls into a class of certain functions and developed
lots of non-parametric methods to estimate f (e.g.. Györfi (2002): Tsybakov (2009)).
The kernel method, one of the most widely applied non- paramerriitiic regression methods (e.g., Kohler Krzyzak (2001); Cucker & Smale (2001); Capomnetto & De Vito (2007); Steinwarr et 2009 )
Fischer & Steinwart (2020)), assumes that 1 belongs to certain reproducible kernel Hilbert space
(RKHS) H. separable Hilbert space associated
kernel function defined X' The kernel
ridge regression (KRR), which is also known as the Tikhonov regularization regularized least
squares, estimates f by solving the penalized least square problem:
(
ARRR = arg min
Σ (v4 f(x;))² + A n
(3)
JEH
i=1

---

Published as a conference paper at ICLR 2023
where À 0 is the so-called regularization parameter. By the representer theorem (see e.g.. An- dreas Christmann 2008)), this estimator has an explicit formula (please see (8) for the exact meaning of the notation):
PARR (x) (L, X) (IK(X, + +
Theories have been developed for KRR from many aspects over the last decades, especially for the convergence rate of the generalization error. For example, if f E H without any further smooth- ness assumptions, Caponnetto & De Vito 2007) and [Steinwart et al. (2009) showed that the gen- eralization error of KRR achieves the information theoretical lower bound n I+ø, where 3 is a characterizing quantity of the RKHS H. (see e.g. the eigenvalue decay rate defined in Condition (A)).
Further studies reveal that when more regularity smoothness) of fp is assumed, the KRR fails to achieve the information theoretic lower bound of the generalization error. More precisely, when fü is assumed to belong some interpolation space [7]] of the RKHS H. where > 2. the information
theoretical lower bound of the generalization error is n at Rastogi & Sampath 2017) 7 and the
best upper bound of the generalization error of KRR is 2ns Caponnetto De Vito 2007). This gap between the best existing KRR upper bounds and the information theoretical lower bounds of the generalization error has been widely observed in practices (e.g. Bauur al. (2007); Gerfo et al. 22088) ). It has been conjectured for decades that no matter how carefully one tunes the KRR, the rate of the generalization error not be faster than n-= शạΑ (Gerfo et al. 2008 Dicker al. 2017) This phenomenon is often referred to as the saturation effect (Bauer et al. 2007) and we refer to the conjectural fastest generalization error rate n अीक of KRR as the saturation lower bound. The main focus of this paper is to prove this long-standing conjecture.
1.1 RELATED WORK
KRR also belongs to the spectral regularization algorithms, a large class of kernel regression algo- rithms including kernel gradient descent, spectral cut-off, etc, see e.g. Rosasco al. (2005): Bauer al. (2007); Gerfo et al. (208);; Mendelson & Neeman (2010). The spectral regularization algo- rithms were originally proposed to solve the linear inverse problems (Engl et al. 1996), where the saturation effect was firstly observed and studied (Neubauer) 1997 Mathé] 2004 Herdman al.
2010). Since the spectral algorithms were introduced into the statistical learning theory, the satura- tion effect has been also observed in practice and reported in literatures (Bauer al. 2007 Gerfo
ct al. 2008).
Researches spectral algorithms show that the asymptotic performance of spectral algorithms is mainly determined by two ingredients (Bauer et al.] 2007] Rastogi & Sampath 2017 7 Blanchard & Mücke 2018 Lin al. 2018). One the relative smoothness(regularity) of the regression function with respect to the kernel, which is also referred to as the source condition (see, e.g. [Bauer et al. 2007 Section 2.3)). The other is the qualification of the spectral algorithm, a quantity describing the algorithm's fitting capability(see, e.g. Bauer et al. (2007) Definition 1)). It is widely believed that algorithms with low qualification can achieve the information theoretical lower bound when the regularity of f is high. This is the (conjectural) saturation effect for the spectral regularized algorithms (Bauer al., 2007 Lin Cevher 2020 Lian et al., (00II) I). To the best our knowledge, most works pursue showing that spectral regularized algorithm with high qualification achieve better generalization error rate while few work tries to answer this conjecture directly (Gerfo et al. 2008 Dicker et al. 2017).
The main focus of this paper is to provide a rigorous proof of the saturation effect of KRR for its simplicity and popularity. The technical tools introduced here might help to solve the saturation effect of other spectral algorithms.
Let us denote by X (......, Fx)) the sample input matrix and y (V1,... Vn. the sample output vector. We denote by μ the marginal distribution of p on X. Let E; = Vi - f (xx) be the noise.
Notation.
2

---

Published as a conference paper at ICLR 2023
We use [' du) (sometimes abbreviated as L²) to represent the Lebesgue L spaces, where the corresponding norm is denoted by I1-1Ize- Hence, we can express the generalization error as
- 1/)) -1 1
Exzay
We use the asymptotic notations 0(+), o(-) 22(-) and w()). We also denote on bn iff a, = (b,,)
and an = (2(,).). We use the asymptotic notations in probability O+(-) and S2p(-) to state our results. Let {an 1=21 be a sequence of positive numbers and (22 a sequence of non-negative random variables. If for any 8 > 0 there exists M3 > 0 and N₂ > 0 such that PfS, < Mşa, 2 1- 6, Vn 2 Ns, we say that &n bounded (above) by on probability and write En = Or(an). The definition of 9zp (b.)) follows similarly.
2 BRIEF REVIEW OF THE SATURATION EFFECT
2.1 REGRESSION OVER REPRODUCING KERNEL HILBERT SPACE
Throughout the paper, we assume that Rd is compact and k is a continuous positive-definite kernel function defined on X. Let T 12 dp) + 12 duj be the integral operator defined by
(T)) = / (()d)))))
(4)
It is well known that T is race-classsthus compact), positive and self-adjoint (Steinwart & Scovel, 2012). The spectral theorem compact self-adjoint operators together with Mercer's theorem (see e.g., Steinwart & (2012) yield that
T
Σ Ce
(5)
IEN
k(2, 9) E Aece)))(
iEN
where \ are the positive eigenvalues of T in descending order, e;'s the corresponding eigen- functions, and N C is an at most countable index set. Let H be the separable RKHS associated
to the kernel &s (see, e.g., Wainwright 2011 (2019 Chapter 12)). One may easily verify that { [x! 1/2 es iEN
an orthonormal basis of H. Since we are interested in the infiniteddimensione cases, we may assume that N N.
Recall that the kernel ridge regression estimates the regression function I through the following optimization problem:
A KRR arg min JEH
Σ (y - f(x,))² A
nt
The representer theorem (see e.g.. Andreas Christmann (2008) implies that
jKRR
(x) K(x, (X(,(X X) +AA))
(8)
where
K(x,
k(I, xx)) and K(X,X) (k(2i, 2z)) nxn" mxm
The following conditions commonly adopted when discussing the performance of fKRR.
(A) Eigenvalue decay rate: there exists absolute constant 61 > 0, 02 > 0 and (0, 1) such that the eigenvalues X.8 of T, the integral operator associated to the kernel k satisfy
c/i-1/3 & > S ezi -/8-1/8 1/8 V 1,2....
(B) Smoothness condition: the conditional mean f E,[ y satisfies that ||52 S R some R 0:
3

---

Published as a conference paper at ICLR 2023
(C) Moment condition of the noise:
| (z)x) dp(u)x) S m p.a.e. EX Vm 2,3,....
where o, M > are some constants.
The quantity 3 appearing in the condition an RKHS or the corresponding kernel function k. describes the span the RKHS and depends only the kernel function &o (or equivalently, the RKHS H-). This polynomial decay rate condition is quite standard in the literature and also known as the capacity condition or effective dimension condition (Caponnetto
A is often referred to the eigenvalue decay rate of
De Vito. 2007| Steinwart et al.) 2009 Blanchard & Mücke (018), which is closely related to the covering/entropy number conditions of the RKHS (see, e.g., [te.iwStinwwrt et al. 2009 Theorem 15)). The condition (B) requires that the conditional mean fa( falls into the RKHS H with norm smaller than given constant R. The condition
[C]
requires that the tail
probability of the 'noise' decays fast, which is satisfied if the noise sub- Gaussiass
(2)
is bounded or
Proposition 2.1 (Optimality of KRR). Suppose that H satisfies the condition A and P consists of all the distributions satisfying the conditions and (C)
i) The minimax rate of estimating fo is n T47, i.e, we have
inf sup F. 1/11 22 (n-
(10)
f PEP
where inf j is taken over all estimators and both the expectation E, and the conditional mean fü depend on p.
ii If we choose X x n 17P, then we have
KRRR
so =0p (n T
(n-Ttt))
(11)
This theorem comes from a combination (with a slight modification) of the upper rates and lower rates given in Caponnetto & De Vito (2007). says that the optimally tuned KRR can achieve the information theoretical lower bound if Jp (a)) falls into H and no further regularity condition is imposed.
2.2 THE SATURATION EFFECT
When further regularity assumption is made the conditional mean (z), there will be gap between the information theoretical lower bound and the upper bound provided by the KRR. This phenomenon is now referred to the saturation effect in KRR. In order to explicitly deseribe the saturation effect, we need to introduce a family of interpolation spaces of the RKHS H (see, e.g. Fischer & Steinwart (.200))
For any 8 2 0, the operator T 12((2) + 1.2(2) is given by
(*) Σ (f
(12)
iEN
and the interpolation space [7] for a 2 0 is defined
aare/ (e ( }
[H] = Ran /2
Σ
(13)
iEN
with the inner product defined by From the definition, it is easy to verify that { a/2 KEN
( (f.))p
(n-a/28, Faaaa//Taaa//// p-aa21))
(14)
forms an orthonormal basis of [7]]
and thus [7] is also separable Hilbert space. It is obvious that [7]0 I.2 and [7]] C H.
4

---

Published as a conference paper at ICLR 2023
Moreover, we have isometric isomorphisms T [H] [M| and compact embeddings [H] - [A] Ya1 > 0g 2 0. The example below illustrates the intuition of a: describes the smoothness of functions with respect to the kernel.
Example 2.1 (Sobolev RKHS (Fischer & Steinwart (0200). Let X' = = S Rd be bounded domain with smooth boundary. We consider the Sobolev space H. = (22),, which, roughly speaking, consists of functions with weak derivatives up order 8, see, e.g., Adams & Fournier (2003). It is known that & > d we have the Sobolev embedding (22 <> (S2) where C" ($2) is the Hölder d and thus (² is an RKHS (Fischer 2.
2" space of continuous differentiable functions and
Steinwart 2020). Moreover, by the method of real interpolation (Steinwart & Scovel, 2012 Theorem 4.6), we have [H] = H**( for >> 0. This example shows that the larger the a, the "smoother" the functions in [H]].
If one believes that (1) possesses more regularity (i.e., (x) E [H)]), we may replace the condition B by the following condition:
(B') Smoothness condition: the conditional mean f Pppl y |x] satisfies that | S R for
some 0.
In this condition, the parameter describes the smoothness of the regression function with respect to the underlying kernel. The larger a is, the "smoother" the regression function is. This assumption also referred to the source condition in the literature, see, e.g.. |Bauer al. (2007); Rastogi &
Sampath (0117). With this new regularity assumption, we have the following statement.
Proposition 2.2 (Saturation phenomenon of KRR). Suppose that H satisfies the condition P consists of all the distributions satisfying the conditions B and C
A
and
i) The minimax rate of estimating f is a+3 i.e., have
E sp113- 2
inf sup PEP
0t8
(15)
where inf j is taken over all estimators and both the expectation Ep and the regression function fü depend on p.
ii) Let ā min(a, 2). Then, by choosing n2 ata, we have
KRR
Op
(n" 2-3
(16)
This proposition comes from a combination (with a slight modification) of the lower rate derived in Rastogi & Sampath| [2017] Corollary 3.3) and the upper rate given in Fischer & Steinwart (2020)
Theorem (ii)). It says that the optimally tuned KRR can achieve the information theoretical lower
bound if (+)) E [7| when < 2. However, when > 2, there is a gap between the information theoretical lower bound and the upper bound provided by the KRR.
3 MAIN RESULTS
We introduce two additional assumptions in order to state our main result.
Assumption (RKHS). We assume that H is an RKHS over a compact set X' C gd associated with a Hölder-continuous kernel k. that is, there exists some s (0, 1] and L > 0 such that
[k(21,22) k(v1 122l < LIl(x1, x2) (11, l2)l
Va,, 22. U1. U2 X.
Assumption (Noise). The conditional variance satisfies that
((zaa)~ [vv (x))) 22 0, p.
(17)
The first assumption is Hölder condition the kernel, which is slightly stronger than assuming that & is continuous. is satisfied, for example, when l is Lipsehitz or C., Kernels that satisfy this assumption include the popular RBF kernel, Laplace kernel and kernels of the form (1 ||ar >
5

---

Published as a conference paper at ICLR 2023
and 2004 Theorem 6.20), and kernels associated with Sobolev RKHS introduced in Exam-
ple 2.1
The second assumption requires that the variance of the noise y - (z) is lower bounded. When y = (x) + e where N N(, o²) is an independent noise, the second assumption simply requires that a A O. In other words, Assumption 2 is a fairly weak assumption which just requires that the noise
non-vanishing almost everywhere.
Now we are ready to state our main theorem.
Theorem 3.1 (Saturation effect). Suppose that H satisfies the condition A
the distribution
satisfies that fø # and fo [H] for some Z 2. and Assumptions and hold.
For any 8 for any choice of regularization parameter Xn) satisfying that Xn2) - 0, have that, for sufficiently large n,
E AKRR |
X
2
cn
(18)
holds with probability at least
ō for some positive constant c. Consequently. we have
E
KRRR
X = S2
n z+d
Remark 3.2. The saturation effect of KRR states that when the regression function is very smooth, ie., a 2 2, no matter how the regularization parameter is tuned, the convergence rate of KRR is bounded below by 243 The saturation lower bound also coincides with the upper bound (16) in Proposition 2.2, Therefore, Theorem 3.J rigorously proves the saturation effect of KRR.
Moreover, we would like to emphasize that the saturation lower bound is established for arbitrary fixed non-zero E [H]], and it is essentially different from the information theoretical lower bound, e.g., (15) in both the statement and the proof technique.
3.1 SKETCH OF THE PROOF
We present the sketch of our proofs in this part and defer the complete proof to Section B Let
us introduce the sampling operator Kg : R + H defined by Kzy yk(x,-) and its adjoint
operator K2- H + I given by KJ f(x).. We further introduce the sample covariance operator Tx : H > H by
Tx
Ka K
(19)
and define the sample basis function
1 gz n
K Yo E H.
(20)
The following explicit operator form of the solution of KRR is shown in Caponnetto & De Vito 2007):
RKRR 1
+
(21)
The first step of our proof is the bias-variance decomposition, which differs from the commonly used approximation-estimali
error decomposition the literature (e.g. Caponnetto & De Vito 2007 :: Fischer & Steinwart 2020)). It can be shown that
E
RRR -f
x
= = + + 1i + n
2 (Tx + +) ->-
12
Bias² Var.

---

Published as a conference paper at ICLR 2023
Then, the desired lower bound can be derived by proving the following lower bounds of the two terms respectively:
Bias = Sp (A?), Var = Sp
(22)
These two lower bounds follow from our birs-variance trade-off intuition: smaller (less regulariza- tion) leads to smaller bias but larger variance, while the variance decreases increases. They also coincide with the main terms of the upper bound in the literature, see, e.g.. Caponnetto & De Vito (2007) Fischer & Steinwart 2020).
The bias term First, we establish the approximation [[Tx + A) spllz= 2 +
where we refine the concentration result between (Tx + A) 1/2 and (T' X) obtained in the previous literature. Second, we use the eigen-decomposition and the fact that KRR's ' qualification is limited show that A (T + X) -- fill 2 cA for some constant 0. Consequently, we have
Bias 2 sv X² (T + [T+ 2 cA2
This lower bound shows that the bais of KRR can only decrease in linear order with respect to À no matter how smooth the regression function is, limiting the performance of KRR.
The variance term
We first rewrite the variance term in matrix forms and deduce that
Var 2 σ² f
k(x, 11 L2... du(x),
(23)
where = to make the following two-step approximation:
- = f (..)).
This observation 23 is key and novel in the proof, allowing us
+ AA= IlA,,, ~ A)) I ~ + A)=,,(,,
The main difficulty here is control the errors in the approximation compared to the main term, while errors of the same order as the main term are sufficient in the proof of upper bounds. To resolve the difficulty, we refine the analysis by combining both the integral operator technique (e.g. in Caponnetto & De Vito (2007)) and the empirical process technique (e.g. in Steiiwarr et al.] (2009)), applying tight concentration inequalities and analyzing the covering number of regularized basis function family {(T + >)-=k(r, ))>x>> Finally, by Mercer's 's theorem and the eigenvalue decay rate, we obtain that
that they are infinitesimal
| ||C + (0- (l)
A
2
cx(x)
X
i=1
00
+ )
can be shown that N2(A) Tr (T and is variant of the effective dimension
((A) = [(T+ + 2) - introduced the literature Caponnetto & De Vito 2007). The condition A implies that (2 2 cA As a result, we get
0²
[Tx + - (1 du(x)= ~ 0² / [[T -)- d)) x
Var >
x
z2 8
-N2(1)
n
4 NUMERICAL EXPERIMENTS
The saturation effect in KRR has been reported in a number of works (c.g.. Gerfo et al. (2008); Dicker et al. (2017)) In this section, illustrate the saturation effect through toy example.

---

Published as a conference paper at ICLR 2023
Suppose that X' [0, 1] and a is the uniform distribution [0. 1]. Let consider the following first-order Sobolev space containing absolutely continuous functions
(( < =0).
sis f(0) - /
H S -
(24)
well-known that it is the RKHS associated to the kernel k(æz, y) min(x. y) (Waiwwright 2019). Let T' be the integral operator associated to the kernel function k. We know explicitly the eigenvalues and eigenfunctions of this operator:
2n - π
-2
en(x) = =V2sin 2n
An =
nT
n2 = 1,
(25)
2
clear that the eigenvalue decay rate 3 of the kernel function (or the RKHS H') is 0.5. To illustrate the saturation effect better, we choose the second eigen-function C2 22 (2 πT) to
be the regression function in our experiment. The significance of this choice is that for any > 0, we have E2 E [H]/. We further set the noise to an independent Gaussian noise with variance 0.2. In other words, we consider the following data generation model:
y = (x) + de,
(26)
where f*(x) = ez(x) and ((00 1) is the standard normal distribution.
Since the gradient flow (GF) method with proper early stopping is a spectral algorithm proved to be rate optimal for any a 2 1 and any fü E [7]] (Yao et al. 2007 Lin et al. 20188), we make a comparison between KRR and GF show the saturation effect. More precisely, we report and compare the decaying rates of the generalization errors produced by the KRR and GF methods with different selections of parameters.
For various a's ''s, we choose the regularization parameter in KRR as À en a+3 for a fixed constant c, and set the stopping time in the gradient flow by & = X- 1 It is shown in Lin al. (2018) that the choice of stopping time (i.e., = ) is optimal for the gradient descent algorithm under the assumption that f/ E [7]]. By choosing different a's, we also evaluate the performance of
the algorithms with different selections of parameters. For the generalization error |lf fill numerically compute the integration (Lo-norm) by Simpson's 's formula with N n points. For each n, we perform 100 trials and show the average as well as the region within one standard deviation. Finally, we use logarithmic least-squares log err rlog n + fit the error with respect to the sample size, and report the slope r' as the convergence rate.
The results are reported in Figure ! on page We also change the regression function be other eigenfunctions and list the results in Table on page 9 First, the error curves show that the error converges indeed in the rate of n -" Moreover, when we apply the GF method, the convergence rate increases as the increases, confirming that spectral algorithms with high qualification can adapt to the smoothness of the regression function. The convergence rates also match the theoretical value B In contrast, when we apply the KRR method, the convergence rate achieves its best performance at 2, and the rate decreases resulting best rate also coincides with our theoretic value 2+.9 = 0.8. We also remark that besides the best rate, rates of other selection of regularization parameter also correspond to theoretical lower bounds that can be further obtained by the bias-variance decomposition (22).
gets bigger, showing the saturation effectt The
We conduct further experiments with different kerness and report them in Section The results are also approving.
In conclusion, our numerical results confirm the saturation effect and approve our theory, and all the results can be explained and understood by the theory.
CONCLUSION
The saturation effect refers to the phenomenon that kernel ridge regression fails to achieve the in- formation theoretical lower bound when the regression function is too smooth. When the regression function is sufficiently smooth, saturation lower bound of KRR has been conjectured for decades.
8

---

Published as a conference paper at ICLR 2023
Error Detayx-5501.f-22248
Error Detay:k-Soblff==2..6
-2.
-32
-30
-1.4
-34
0=1.5.
-3.6
-4.0
2-25 1-100.m- m3773
2.2.
-38
a=3.0, 0=100.r 0m
-4.2
3=3.0
C=100
rm-0.8
4.0
1000
2 10
3x10
1x 5000
2x10
x 10
4
Figure I: Error decay curves of KRR and GF. Both axes are logarithmic. The colored curves show the averaged error over 100 trials and the regions within standard deviation are shown in green. The dashed black lines are computed using logarithmic least-squares and the slopes are reported as convergence rates.
f
G1
ft
62
f
= C3
f
C4
KRR
GF
KRR
GF
KRR
GF
KRR
GF
1.5
.73
.72
.76
.74
.75
.74
.74
.75
2.0
.76
.76
.80
.78
.78
.78
.80
.80
2.5
.69
.80
.73
.81
.69
.82
.67
.84
3.0
.58
.82
.62
.59
.84
.56
3.5
.49
.84
.54
.85
.51
.86
.48
.90
Table 1:
Convergence rates comparison between KRR and GF with X = on a4. for various a's. Bold numbers represent the max rate over different choices of X.
In this paper, provide a rigorously proof of the saturation effect of KRR, i.e., we show that, if [H] for some 2, the rate of generalization error of the KRR can be better than 249 no matter how one tunes the KRR.
Our results suggest that the KRR method regularization may be inferior some special regu- larization algorithms. including spectral cut-off and kernel gradient descent, which never saturate and are capable of achieving optimal rates (Bauer al., 2007: Lin al. 2018). The technical tools developed here may also help establish the lower bound of the saturation effects for other spectral regularization algorithms.
ACKNOWLEDGMENTS
This research was partially supported by the National Natural Science Foundation of China (Grant 11971257), Beijing Natural Science Foundation (Grant Z190001), National Key R&D Program of China (2020AAA0105200), and Beijing Academy of Artificial Intelligence.
REFERENCES
Robert A Adams and John JF Foumner. Sobolev Spaces. Elsevier, 2003.
Ingo Steinwart (auth.) Andreas Christmann. Support Vector Machines. Information Science and Statistics. Springer- Verlag New York, New York. NY, first edition, 2008.
Bauer, S. Pereverzyev, and L. Rosasco. On regularization algorithms in learning theory. Journal of complexity, 23(1):52-72, 2007.
G. Blanchard and Nicole Mücke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18:971-1013, 2018.

---

Published as a conference paper at ICLR 2023
A. Caponnetto and Y. Yao. Cross-vate validation based adaptation for regularization operators in learning theory. Analysis and Applications, 08:161-183, 2010.
Andrea Caponnetto and Emesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American Mathematical Society, 39(1):1-49, October 2001.
Feng Dai and Yuan Xu. Approximation Theory and Harmonic Analysis on Spheres and Balls. Springer Monographs in Mathematics. Springer New York, New York, NY, 2013.
L. Dicker, Dean Phillips Foster, and Daniel J. Hsu. Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators. Electronic Journal of Statistics, 11:1022-1047, 2017.
Heinz Werner Engl. Martin Hanke, and Andreas Neubauer. Regularization of Inverse Problems, volume 375. Springer Science & Business Media, 1996.
Simon-Raphael Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least- squares algorithms. Journal of Machine Learning Research, 21:205:1-200:38, 2020.
Junichi Fujüi. Masatoshi Fujüi. Takayuki Furuta, and Ritsuo Nakamoto. Norm inequalities equivalent to Heinz inequality. Proceedings of the American Mathematical Society, 11(3))827-830, 1993.
L. Lo Gerfo, Lorenzo Rosasco, Francesca Odone, E. De Vito, and Alessandro Verri. Spectral algo- rithms for supervised learning. Neural Computation, 20(7):1873-111 2008.
László Györfi (ed.). A Distribution- Free Theory of Nonparametric Regression. Springer Series in Statistics. Springer, New York, 2002.
Herdman, R. Spies, and Karina G. Temperini. Global saturation of regularization methods for in- verse iol-posed problems. Journal of Optimization Theory and Applications, 148:164-196, 2010.
Michael Kohler and Adam Krzyzak. Nonparametric regression estimation using penalized least squares. IEEE Transactions on Information Theory, 47(7):3054-3058, 2001.
Heng Lian, Jiamin Liu, and Zengyan Fan. Distributed learning for sketched kernel regression. Neural Networks, 143:368-311 November 2021.
Junhong Lin and Volkan Cevher. Optimal convergence for distributed learning with stochastic gra- dient methods and spectral algorithms. Journal of Machine Learning Research, 21:147-1, 2020.
Junhong Lin, Alessandro Rudi, I.. Rosasco, and V. Cevher. Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces. Applied and Computational Harmonic Analysis, 48:868-890, 2018.
Peter Mathé. Saturation of regularization methods for linear ill-posed problems in Hilbert spaces. SIAM journal on numerical analysis, 42(3):968-973) 2004.
Shahar Mendelson and Joseph Neeman. Regularization in kernel learning. The Annals of Statistics,
38(1):526-565, February 2010.
Stanislav Minsker. On some extensions of Bernstein's inequality for self-adjoint operators. Statistics & Probability Letters, 127:111-111 April 2017.
Andreas Neubauer. On converse and saturation results for Tikhonov regularization of linear ill ill-posed problems. SIAM journal on numerical analysis, 34(2):517-52) 1997.
Abhishake Rastogi and Sivananthan Sampath. Optimal rates for the regularized learning algorithms under general source condition. Frontiers in Applied Mathematics and Statistics, 3, 2017.
Lorenzo Rosasco, Ernesto De Vito, and Alessandro Verri. Spectral methods for regularization in learning theory. DISI, Universita degli Studi di Genova, Italy, Technical Report DISI-TR-05-11 2005.
10

---

Published as a conference paper at ICLR 2023
Ingo Steinwart and C. Scovel. Mercer's theorem general domains: On the interaction between measures, kernels, and RKHSs. Constructive Approximation, 35(3):363 417, 2012.
Ingo Steinwart, D. Hush, and C. Scovel. Optimal rates for regularized least squares regression. In COLT, pp. 79-93, 2009.
Joel A. Tropp. User-friendly tools for random matrices: An introduction. Technical report, Defense Technical Information Center, Fort Belvoir, VA, December 2012.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statisties. Springer, New York London, 1st edition, 2009.
Roman Vershynin. High-Dimennsooal Probability: An Introduction with Applications in Data Sci- ence, volume 47. Cambridge university press, 2018.
Martin J. Wainwright. High--Dimessiona Statisties: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Holger Wendland. Scattered Data Approximation. Cambridge Monographs Applied and Com- putational Mathematics. Cambridge University Press, Cambridge, 2004.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learn- ing. Constructive Approximation, 26(2):88--15, 3 2007.

---

Published as a conference paper at ICLR 2023
A BASIC FACTS IN RKHS
Let & be continuous positive definite kernel function defined on compact set A' and H. be the RKHS associated the kernel k. Since & is a continuous function and X' is a compact set, there exists constant y such that
[k(z, y)1 S for any E X.
(27)
It is well know that k(x,-) E H as a function and that the inner product satisfies that
(k(z,-), = f(x), Ef H.
(28)
In particularly, we have (k(x, )), kyy )) = k(z,y) y).
Let T (2(x) + (x) be the integral operator associated to the kernel fucntion k. By the spectral decomposition of T' it can be easily shown that Ran T' S H and |[T S x If x which implies that T can also be viewed a bounded linear operator on H. With little abuse of notation, still use T to indicate it.
We denote by (H) the set bounded linear operators over H and (1-)la())) the corresponding operator norm, where the subscript may be omitted if there is no confusion.
A.1 FUNCTIONS IN RKHS
Lemma A.1. Suppose that H is the RKHS associated to the kernel k. Let [If == supzex [f(x) be the supremun-norm of a function f X -> R. Then for any f H. we have If S kllfflu
Proof. It is easy verify that for fE H,
If
sup [f(x) S sup (k(,,)). fl xE
sEX
s sup [ I xl]ffl eex
Definition A.2. Let K C Rdd be a compact set and a E 00, 1]. For function f K - RR we
introduce the Hölder semi-norm
IS(x) - f(y)] 1 y
Ma.k= =
sup x.yEK, xøy
(29)
where represents the usual Euclidean norm. Then, we define the Hölder space
(K)
IR | < <x),
(30)
which is equipped with norm
lffloo()
sup f(x) + [f]a. zek
Lemma A.3. Assume that H. is an RKHS over compact set X C Rd associated with kernel
E (a for a E (0, 1). Then, we have H (x)2(X) and
Maa22x S v 2n 22 20.xxx1]
(31)
where x² = =uup [k(zx)).
Proof. Since & is positive definite, from det (xx,,) x) k(x, y) k(y.v)
k( v)
0 we
know that
supx,ex (k(2, 8)1 < x² By the properties of RKHS, we have
f(x) (vv k(r, )) (S,k(u, 1) (J, k(b,,)) )) S 11 (b(=,)) kl
12

---

Published as a conference paper at ICLR 2023
Moreover,
[k(z, k(y, )134 = ((x,)))((.)) k(x,
Sk(x, 2),,,))Ko (KV, A=z,, v)1 + ((, k(0,201 S 2xx - y/
Therefore, obtain
(f(x) - f(v) - 2 xxxx y/a/2
A.2 SAMPLE SUBSPACE AND SEMI-NORM
It is convenient introduce the following commonly used notations
K(x, X) = (M. K(X,2) = K)x,X),,
(32)
[(X, X) = (k(1);
(33)
K X),,X,
(34)
where K is known as the (normalized) kernel matrix. For a function f. we also denote by
f[x] (f(z))....
the column vector of function values.
Definition A.4. Given {21. In C X, the subspace
Hn = span (k(#1, .)... klan, )} C. H.
(35)
of H. is called the sample subspace. We also call the operator Qn H. given by
Qn(()(z) = K((,, X)X((X,))*
(36)
the sample projection map.
Recall that we have defined the operator Tx = E, K2 K in 19 It is clear that Tx TxQn and Ran Tx Ha. Under the natural base (k<21), )) ..... k( of H.s have
Txk(zn, = n Σ K k(x,, xz) = k(o,, xy )((,,))
iee, Tx can he represented by the matrix K under the natural basis. We can use
TxK(X,,) KK((..)
(37)
to express this result. Furthermore, for any continuous function (px)) the operator (TTx) satisfies that
((Tx)K(X.)) (X))K(XX)) )
(38)
In particlar, we have
(x(Tx) ((K)(()
(39)
Since gz E H, ( see 20 Therefore, know that
KRR (x) = ! (K
13

---

Published as a conference paper at ICLR 2023
A.2.1 SEMI-INNER PRODUCTS THE SAMPLE SPACE
We consider the following sample semi-inner products:
(2 = ! Σ f(x))g(z.)= - -[x]'lx,, T1 (f.9).. 1Q2II
(40)
72
(41)
Lemma A.5.
(.. = n -
(42)
Proof. By the definition (36) of On we have
(f.9)..
(MK.- 9(x])
-KK(X,X) K(C))))))KXX,,,, (KXX
= - g[ - g[X].
f[x]
Proposition A.6. For f,9 E H. we have
(f.9) (f.9) = (Txf.9)H xx?"9)
(43)
10 =1|72/-/ 11x""111x
Proof. Since Ran Tx Hn. we have
(Txf.9) (Q,Txf. (Txf.9)
Since (Txf)XX] = Kf[X], we obtain
(Txf.)) = - - -1X =ffg))
A.3 COVERING NUMBER AND ENTROPY NUMBER
Definition A.7. Let (E, l1-l1 be normed space and E be subset. For > O, we say S C A is an e-net of A if va E A. 3s e S such that ||a - s|| S e. Moreover, we define the E-covering number of A to be
((A, e)) = inf n N" Bs,,..., E A such that C Ü Be(snee)
(44)
i=1
inf (|S] is an e-net of A}
(45)
where Bg(xo,e) = fa E E |20 zllæ I {} be the closed ball centered at wo E with radius
The following result about the covering number of bounded set in the Euclidean space is well- known, see, e.g., /ershynin (2018 Section 4.2).
Lemma A.S. Let A Rd be a bounded set. Then there exists a constant C (depending on A) such that
N (A,11-1lee,e) S Ce-d.
(46)
14

---

Published as a conference paper at ICLR 2023
B PROOF OF THE MAIN THEOREM
B.1 BIAS-VARIANCE DECOMPOSITION
The first step of the proof is the traditional bias-variance decomposition. Recalling (1). have
FKRR
(Tx + A)
K Vi = -T'x + A) Σ
Ku, (K2 + +&)
1=1
1=1
= - +1) Tx
+
(Tx A) Kz,tis
so that
@KRR - -f= + +)=
1 Σ (Tx + A) Kr,G. n
Taking expectation over the noise conditioned on X, since E|x independent noise with mean 0 and variance o² we have
1
fz
Bias 2 + Var,
(47)
12
where
Bias = =Ix + A)-15/1
Var
(Tx + A)-
(48)
B.2 LOWER BOUND FOR THE BIAS TERM
Proposition B.1. Suppose that f E [H]] is non-zero function. There is some e >> 0 independent of X such that
x 0.
(49)
Proof. Since f [H] and is non-zero, we may assume that
E=
Because A + O, we have
I(T
>0 (Since f* + O).
Ai +
Theorem B.2 (Lower bound of the Bias term). Suppose that a 2 2, f E [H] is a non-zero function and X X(n) l2n -(l-))(e)) for some e E (0, Then, for any 0, there exists an integer nh such that for any > no we have that
Bias² 2 cX²
(50)
holds with probability at least 1 - 8 where e > 0 is a constant independent of X. As consequence, B = ()p()
Proof. Corollary together with Proposition B.1 yields that with probability at least 5 have
[n 4 4
[[Tx + -) M > |TT + A) 122 OOn
15

---

Published as a conference paper at ICLR 2023
2 c O(n
for some q Therefore, we get
Bias +X) et2 (1- (1-0(19(113) (
(In 4 2) 2 x2
when n is sufficiently large.
B.3 LOWER BOUND FOR THE VARIANCE TERM
For the variance term, Assumption yields that o 2 0² almost surely. Recalling the discussion of sample subspaces in Section we have
(Tx + A) 1)''k((S -) I12
Var
n²a
i=1
[ + A)-KK(X 11 (XX.
n2
(51)
(By (38)
|| + X) 'K(X, (1122(x
n1
σ²
/
K(x, X X)( + ((X
n²
Ix
Let us denote h2 k(,,, :). Then by definition obvious that 1t, [X] KK(X,)) x). From (39). we
find that
((Tx + 2) [X] (K X) h (K (K+
so we obtain
1 [K + + [I(CK + 2)-kK(( xz) 11
1 ||(( + -)-1 [X]
[| + + 1,,0"
from the definition (40) of sample semi-inner product. Consequently, we get
σ² n / ( du(x).
Var
(52)
Combining with some concentration results, we can obtain the following theorem.
Theorem B.3. Assume that Assumptions Zandiionnnnnnnnnnn condition (A) (e.g.. g.. the eigenvalue decay rate
91) hold. Suppose that >(n) - 0 satisfying that X 5t ( ((-- -t-) for some (0, 102).
Then, for any d > O, when n is sufficiently large, the following holds with probability at least 1 - 6:
cx
Var
(53)
n
As a consequence, we have Var Sp
A
Proof. First, assert that the approximation
||Tx h 2 I|( + 1) 11
(o()))(T A) hy-hhalle> o(1) 4 In 4
(54)
16

---

Published as a conference paper at ICLR 2023
holds with probability at least - 6. Then, plugging the approximation into 52 gives
Var
[Tx + h L2,n du(xx)
x
0² (T' + 1) h1 dp(x) o(1) / ||(T | h (lll2
=(1) In
4 2
2m
For the two integral terms, applying Mercer's theorem, we get
[T + h = / 1=1
di x (px))
(55)
A x+ = -22(1) 2 cA-
and
(T + +1)++ (pal) = (/, +1+)))/aap t/ (()d)(())
1/2
= (NG(A)) CC--1/2
where the estimation of (A) comes from Proposition
D.I Therefore, we obtain that
o(A
-
3/2
4
o(1) In 5
Var 2
-
2n
n
n
4n
goes infinity.
remains to establish the approximation
54
Lemma C.11 and Lemma C.12
yield that
3
4
[[ + 1)
(T + A) 11 + +[1) In
(56)
12,n
8'
|[T A) hr2 1 1,,n
2
(T + A) 1a-hhell 11-11 - o(1) In
(57)
8'
/ (Tx + X) 1) hm
| (T + 2) ho
S o()) In
(58)
7
#
with probability at least Consequently, from (3 and (6). we get
| /2 (T + 2) 2/1 1 = [| A) 10 11
s < + 2) ho 112 + o(1) (In 4 1/2
Combining it with (58) we find that
T2 (Tx 2) hx
T (T + +1)++) -)-
<// (T + a) 1)-1/1z + o1 4
+
72
4
s CT + ->11/>11 + o(1) In
3'
which gives the approximation of the squared norm
| /2 (Tx
2)
h
2 A) h
H
H
4 (IICT
>)= + =0 (59)
s o(1) In =
Finally, combining (59) and 57 yields
[1 + A) hz 13, = | (Tx + 1 2
17

---

Published as a conference paper at ICLR 2023
(ICT+ + o[1 In 4 5
T (T + +1) 1)-111z (1)
= ||(T + 2) >)-1h=ll 1lll2,,m -o(1) ln
4
() t 4
8
1
4
o(1) 4 ///
(1((++))11)) + (() In 4
2 2 ||(T + 1) -o(1) In
1 | + A) -1 (o(1)](T+ x) - + o(1) ) In 5/4
4
B.4 PROOF OF THEOREM 3.
Let À X(n) be arbitrary choice of regularization parameter satisfying that X(n) 0. We consider the truncation
À = max (A n A.n))s)))
(60)
which satisfies that x= 22 (n ズ and X + O. Applying Theorem B.2 and Theorem B.3 we obtain that
c2 Bias (x)) 2 ax², Var(A) 2
n
with probability at least 1-6 for sufficiently large n, where we use Bias (④) and Var(A) to highlight the choice of regularization parameter. Let us consider two cases.
Case 1: >>> 2= In this case À 2, so
E
AKRR A
gr| p-1 x
Bias (A) Var(A)
Bias (A) Var(A)
2 c +
cn शों
where the last inequality is obtained by elementary inequalities in Lemma D.3 with 8
and
2+3
243
Case 2: A < aee we know that
From the intermediate result 51 in proving the lower bound of the variance,
/² n²
c2
Var K(x, x)
n
and
σ²
/ K(o, A) xK(x))))) n2
Var (A) 2
Noticing that
(K +1) (K +x2 if A < A2.
where > represents the partial order induced by positive definite matrices, we get
Var(A) 2 x2 K(x, X)(K + A) (X,
n
18

---

Published as a conference paper at ICLR 2023
σ²
2
K(x, X) +
n²a
x
C2) ~8 8
C2
where we note that = 248 in this case. Consequently,
E (1
PKRR
f- 111 x 2 Var(A) 2 C2n शील.
The proof is completed by concluding two cases.
Remark B.4. It is worth noticing that both the requirement that f * 0 and that the noise is vanishing are necessary. If the former does not hold, choosing À = oo will yield the best estimator
= O with zero loss. If the latter does not hold, the interpolation with À = 0 will be the best estimator since there is noise.
C APPROXIMATION LEMMAS
In the following proofs, we always assume that (0, 1). For convenience, we use notations like
C, c to represent constants independent of n, 5, which may vary from appearance to appearance.
C.I CONCENTRATION RESULTS
Lemma C.1. Suppose that Assumption holds. Let f E be given. We have
[21
||f
2
[1 - fll s 2x
In
(61)
n
vn
holds with probability at least 1-
Proof of Lemma Let us define an H-valued random variable & Tef = KgKyf (())k(r) :). It easy verify that
E Bx-aho Tf. and Σ 1=1
Ex. Txf.
Furthermore, we have and
[kell = [If(=)b(2, 12 S k1lffllo
E SernullEalll Ex-, (z))) )) ) = Eney ([x)) = =
Therefore, the proof is concluded by applying Lemma D.6 with I 2 and = k| xlll L
The following lemma shows that (Tx + A) approximates to (T + ( It is similar to Lin & Cevher 2020 Lemma 19), but here we do not require that =
Lemma C.2. Suppose that the Assumption hoold. n,, À satisfy
4N(A)
1
An In
(62)
8
16
where N(A) Tr(T + A) 'T then with probability at least 1 ô we have
(T + 2) 2 (Tx + x)
x) +>)) + A) 2 (HH)
2.
(63)
200
If Condition
A) Le. the eigen-value decay condition 99 holds and = 2(n (1 -(--)) for some E (0, 1), then condition
(2) holds for sufficiently large
19

---

Published as a conference paper at ICLR 2023
To prove Lemma first prove the following lemma, which is modified version of Lin & Cevher 2020 Lemma 16).
Lemma C.3. Under Assumption 1-6: 8:
1 and condition
the following holds with probability at least
4x2
2x² B
(T + 1) 2) (T (x) +1)
(64)
3An
An
where
+ ()W(2)
B= In
8 T
Proof.
We prove by using Lemmal D.7 Let
A; A(x;) = (T + +T)
Then, EA, = and
- = (T (1=
Calculation shows that
|| S (T + 2) [1|xx] |T|I)
(T + A S 2x² L.
Using the fact that E(B EB)²
EB² for self-adjoint operator B, we have
E.A² = E
(T + A) TT
Moreover, noticing that T > 0 and 0= n have
AT X)
(T A) 1 1 1
and hence
EA 3 - +)
We get
\1 = |T
|[V| > +
1 A
1
Tr > TT (T( - WA(),
implying that
4Tr V
= 4(1T)) + A)
B In
8||
and || < -
Now we are ready to prove Lemma C.2 Proof of Lemma
2
Let
R B
x² In
4(1ITT| + (A)A(())
An
An
81|T1
By Lemma C.3 with probability at least 1 8, we have
4
=
(T - - + A)
S s-u+
2u -
3
2'
where the last inequality comes from 62 namely u S T6
20

---

Published as a conference paper at ICLR 2023
Then, for the first term have
(T + 1) (Tx + 2)
= [T+ + (T
= (Ix + ()(T + +
+/1
=
- aa+152.
Similarly, the second term can be bounded by
T + x)= + 2
(T +
+1 + +I= 1)1/21
(T A) 1/2 + A)(T + 1122
S (1 a) 22
Furthermore, if condition (9) holds and x = Qin (2--)), then from Proposition D.I we get
N(A) < CA- = 0 (n
Therefore,
4(1T) + ()
(1+ + In +C) + as n + 0o.
In
S Cnn
An
T|
C.2 NORM CONTROL OF REGULARIZED FUNCTIONS
Proposition C.4. Suppose that ʃ E [H] Then, for any 0 S S a such that & Y S 2, we have
[(T + 1)- ">''sl(ppp I -1
-1
(65)
Proof. From the definition of [1-1|pa70 we have f = Ta/2 fo for some fo E L2 such that [l =
|l lpguo and
||T + -)-11|1(p0)
T 7/2 + A) 11/0// fo
12
T - (T + 2) -o
(T + x) (a())) 11oll
where the last inequality comes from applying Proposition D.2 operator calculus.
The following special cases of Proposition C.4 are useful in our proofs. We present them as corol-
laries. Notice that we have 29 from estimations of the RKHS-norm can also get estimations of the sup-norm.
Corollary C.5. For f E [H]2, have the following estimations:
||T + (()++))=+))) fll S [[]fll
[[ fl <x-1/22 [|
Proof. Applying Proposition C.4 with a and : 0, respectively, we obtain
[[T + - |11fl[mzz
[T - 5 x
(T x) S 1 1890
21

---

Published as a conference paper at ICLR 2023
Similarly, noticing that k(x,-) E [H]', we also have the following corollary controlling the norms of regularized kernel basis function (T + A) k( )):
Corollary C.6. We have the following estimations: Vr X.
[| A) -) (
S xx2
I| + x)= )11 S $KA-1,
(66)
11.00 S 1
where C/ a positive constant.
C.3 APPROXIMATION OF THE REGULARIZED REGRESSION FUNCTION
Lemma C.7. Suppose that f E [7] 1 = Mn) D(n (((n-11-)) for some & >> O and X(1) O. then there exist some > O such that for sufficient large n, the following holds with probability at least 1 8:
[I | || + 12 = In
(67)
Proof. By the triangle inequality and noticing that
(T +)+ (Tx -|) (Tx + (Tx
(Tx - (T
have
+ + 1111al
[([++)--((xx+)] 1
(Tx T) #
(Tx + (Tx
1Tx- - - + 11 #
(68)
2(1)
For the first term in 668) we have
T + +
T1/2(T+ + +A-- + 1) + 11) ((((())
(H))
T1/ + >) ||T + +)((Tx + +1)
(By Proposition D.2
S x 1/T A) 1) (0(14)
Since 22n ((n-(1))) Lemma C.2 yields that
+ () 1 1/2
2
(8))
holds with probability least 1 8/2 for sufficient large n. Because the operator (T' (T+ 1 is invertible, we get
1
(Tx +
+ ( (0()))
2
2
By Lemma D.4 we have
|| +) - 11)))))) 2 +2) + +) 2222
+ 2)2
B(K)
which implies that
[[T + +1-11 (|an) < 4.
Therefore, we obtain the upper bound
(1 +\)-1
$ -1/2
(69)
((H)
22

---

Published as a conference paper at ICLR 2023
For the second term in (68 we apply Lemma C.I with f (T + 2) f and get that
(T X) 1 || + X) -
4 8
[Tx (T 11x S 2k
In
n
n2
holds with probability at least - -.22. Plugging in the bounds from Corollary
C.5
we obtain that
(
A X-1/2
|| - +T f*1 11 So
In
(70)
n
Plugging 669 and 770 back into (68 we finally get
[TT L
(1Tx A)
C
(
+
A 1/2
In 4
4 O(n In
Vni
where we use the condition ((n=((1-)) in the last equality.
Combining the previous lemma with L control of the regularized regression function, we obtain the following corollary:
Corollary C.8. Suppose that 1* E [H] 1fλ X(n) = 9nn ((-=) ) for sufficient large n, the following holds with probability at least 1 - 6:
some forsome 0 and X(n) O.
||((T
(Txx +
1) L7 On
In
(71)
L7
Proof. From Lemma
C.7 and
(T+
< |
[ |x/2 in Corollary C.5 we have
[Tx + A)
(T x) fz1 1/ || + -) f-
|| + A) 10-11111 1-11
4
< || + o1) 0
and hence
||(T + A) 8r +1] || 0
Therefore, we get
||(T + +))- |
(Tx + 2) 1
+[](T++)) fr
|| + -)) (I (A) + [ 1) (011))))
L7
4
4
O(n () In 8
00(1)
In
8
In 4
O(n 8)
g
C.4 APPROXIMATION OF THE REGULARIZED KERNEL BASIS FUNCTION
The following proposition about estimating the L norm with empirical norms is a corollary of Lemma D.5
Proposition C.9. Let be probability measure on X, E [2 du) and llf < M. Suppose we have T1..... Zn sampled i.i.d. from μ. Then, for any a > the following holds with probability
at least - 8:
| - 11 <aM + 3 4aM2
2 g
In
6an
By choosing a 2nrz.
I
we have
11.11
5
In
2
<
11
S
1l +
5M2
In 8'
(72)
3n
3n
23

---

Published as a conference paper at ICLR 2023
Proof. Defining & fz,)), we have
EC, = IIflli
E Exrna (a)) - 1 f.
Therefore, applying Lemma D.5 we get
| 11 s
alllIl
3 + 4a.M2
2 In
6an
8
We establish the following lemma about covering numbers of the regularized kernel basis functions. For simplicity, let us denote lig = k(z, -) E H and
Kx { (T + h1) m
(73)
Lemma C.10. Assuming that X S & is bounded and l E C* x 2) some s E (0, 1]. Then, we have
N (Ka,, 11--1110:0 <) (C(A))
(74)
24
N (Kx, xl: S (x(+
(75)
where a positive constant not depending on sr
Proof. We first prove 74 By Mercer's theorem, we have
A ej(a)e
(T+)) Σ
A+
iEN
and thus
X (x)))(())
[(T+)] 1)) (x)= Σ
iEN
= =[(T + A) 112] (a).
Therefore,
([ + - - -TT >)-1/oll
sup |[ +) h/a (x) - [ + +) >>- (x)
zEX
sup
[[T + A) 112] (a) - [(T + 2) (b)
zEx'
Since k is Hölder-continuous, by Lemma A.3 Plugging the bound |I + -, I Ad
we know that (T +T+ 1) is also Hölder-continuous. obtained in Corollary into into (31 get
S x² [T hh S / 2k xxxx [[T + A) hr H
2[k 2xxxx
which implies that
[[(T+ + 1-- had (a) - + x) |r]] (b) S Cod Cod-1la- 1aaa-pj 1/60//
where Co = x²2 22(k) xxxx Consequently, we have
||(T + -ha (T + A) - - <coA-1 1a -11
(76)
76 yields that to find an s-net of KA with respect to I1 we only need to find an ě-net of with respect to the Euclidean norm, where E
2/s
Since the result of the covering number of the finally obtain that
Co
latter one is already known in Lemma A.8
24 = (AE) 2d
AE
N (KC, <) SV 11 8) < C C
Co
24

---

Published as a conference paper at ICLR 2023
Now prove 75 By Mercer's theorem and the series definition of the RHKS norm, we have
As (ei(z)) es(w))
(T + 1) hr (T+ 2) h
Σ
X+ 23
IEN
HH
X (ei(x) ev)) (A+1s))
ENN
Since ||e:ll X, by Lemma A.3 we have
[ x² 2 22 1/2
and thus (es(x)) ec()))² < 1 x y1" Therefore, get
||(T + 1/ - (T 2) thy 1 S
| y
+ Xx) iEN
Cl 51
A A
KEN
I - -1 x (2-18)
Using a similar covering argument over X' gives the desired result.
Lemma C.11. Suppose that Assumption holds. Assume that À A(n) Ω2n (f/2+) for some
p E 1/2). Then, there exists some q 0 such that for any > 0, the following holds with probability at least - 8: Vx X.
[[ 2) he 12.n
21(( A)
3
->> O(n -) In
2
2
8" 2
|| + -) hom 1.?.n
2
21((T + A) h) 1 11: On In
1
2
8¹
where the constants in ( do not depend on x.
Proof. By Lemma C.10 we can find an e-net F C K.x S H with respect to sup-norm of K.A such
that
C(E)
(77)
where en) will be determined later.
Applying Proposition C.9 F with the 11--ll.--buu bbound in Corollary we have
C.6 with probability at least 8
CA 2
2F
3 I
CX 2
2 In
In
< 11
VfEF.
(78)
n
2
n
Now, since F is an e-net of Xc with respect to |1-11 for any x E X, there exists some f E F Fuchh that
[[T ()-+A)-1ha he - -fllce Se.
which implies that
[|( + A)- h || Se, ||[T + x) -) 1 SE.
Since || + -- CC and a² -2 62 (a - (26 + -b),, we get
(T +) llf= 1 s CEX-1 ||[(T + - h 1
11.22mm - 11.112 S CEX (79)
For the upper bound, we have
[[ - X) h0 1oll 11:2, I 11f1122n
CEA-1 (By 79
25

---

Published as a conference paper at ICLR 2023
3
CA-2
2|
(By 78
If L2
+
In
+ CEA-
2
n
(By 779 again)
3
(T
+ A)
1
CX In 2
+ CEA
2
8
Noticing that x Q (2n
and
77 by choosing 8 n- it easy to verify that
Cx 2
In
2|
+ CaA -=x=+=
In |n| In 2
8
2
O(n t
n
C Cnn++ + C2 In 2
= =0(n (m)
+ +0(n
8)
= =0 (n 9) In
for some > 0. The lower bound follows similarly. Lemma C.12. Suppose that Assumption and Condition AA) i.e. the eigenvalue decay rate
hold. Assume that 12
(n )t) for some p E (0, 1/2). Then, there exists some q > such that
r| (Tx + 1)- 12z 1 - (T=))) 1rd s O(n 7) 2 8
(Tx
Vo E X
with probability at least 1 - 5, where the constant in O ") is independent of I.
Proof. We begin with
T (Tx + +) hr 1 -
T (T A)
$ 11) A1- hz
Noticing that
(Tx
we obtain
T + (I+
= T (Tx + (T ( 1/2
< / (Tx + ((x
- 11
x- 1/2 Tx) (T ll
(80)
where we apply Proposition D.2 in the last inequality.
Now, deal with the last term in 80). By Lemma C.10
we find E-covering F of Kxx with
respect to ||-11a such that
2+d FFI C (A
(81)
Applying Lemma C.1 to F and noticing the L and sup-norm bounds obtained in Corol- lary C.6. find that Vf E FF
2211fll
1lfll
2
[I( - Tx) fll 2m
+
In
VTi
5
--1 1-1
2|F
<
+
In
n
Vn
Then, for any Xx we can find some f E J such that ||(T' + 1) 1 - fl1x S s, and thus
[[T Tx) (T +) h = [T - Tx) ((T + A) - - -1) + ||(TTT - -Tx) fllx
I Tx Txllsemull((T + - - -111 + +I[[T- -Tx) fll -x))fla
x-1 +
11/
2
< 2k² + C
In
(82)
vn
8
26

---

Published as a conference paper at ICLR 2023
Plugging 82 into 80).
obtain
x-2 --1
2|
Txx [Tx + 2) (T (T+ +] Pr S SCx C
In
n
vn
8
Finally, noticing À = 5t (n= and 81), by letting = =n= we have
T [(Tx + 1) (T 1) 1r S On 2 In
2
for some q > O.
D AUXILIARY RESULTS
For any p x2 1, let us introduce the p-effective dimension
de ( p21
NG(A)= Tr (T(++)))))=>>>
Proposition D.1. X₂ x 1/8, we have
x
(83)
Proof. Since c 1-1100 < A S Ci-1/8
we have
A
Ci-1/8 1/8
P
20
N₂(() = Σ
= =Σ
Ai
Ci-
C+ C+
i=1
i=1
P
dx = X- /0
C
dy S ČX-B.
Xr
+C
(g11+C))
for some constant C. Similarly, we hace
N₂(A) Ō'X-
for constant Č'
Proposition D.2. For À > and E [0, 11. we have
S 1
sup 220 t+
Proof. It follows from the inequality a² a for any a 2 0 and E [0, 1].
Lemma D.3. (Young's inequality) Let a, b > For p.g > satisfying
1, we have
ab < _a" + 1 11- p q
(84)
or equivalently
a b+b> /D a b
(85)
The following operator inequality et al. 1993 will be used in our proofs.
Lemma D.4 (Cordes' Inequality). Let A, B be two positive semi-definite bounded linear operators on separable Hilbert space H. Then
|| A B B*ll ( S || ( vs [0, 1].
(86)
27

---

Published as a conference paper at ICLR 2023
D.1 CONCENTRATION INEQUALITIES
The following concentration inequality is adopted from Caponnetto & Yao (011)) Lemma D.5. Let f1,...,,, Sn be ii.dd bounded random variables such that Kdl S B, ES; μ., and
E(G: u12 Σ o². Then for any a > 0, any E (0, 1), we have
n
4a
2
&
S ao² +
In
(87)
7 ==1
6an
8
holds with probability at least
8.
Proof of Lemma D.5
The high probability form of bound in (87 is equivalent to the following
probability form:
n2 1 2 2x +e 2cxp
6nas
Σ Si
72
4a
where E
3+ Gon
In
By symmetry, it suffices to prove the following one-sided inequality:
8.
E ao² } exp (- 3 4aB
6nAE
P
Taking exponent with some factor 8 > O, we obtain
Σ E -
ao +E
exp Σ (5: - 14) 2 exp(s(aa² + +E))
n2
S expp(ss(a0* + E)) Exp - " (5: 14)
(Markov Inequality)
(Independency)
+ +E)) II Eexp
8 (Ee
- 11)
(88)
n
Let X; = 5: 44,4, t
and M = -BB. As long as <
3
we have
M.
E Exxp ( (8(Es (E: 11)) Exxp((xx,) =
t
EX
hd
k=0
20 th
$
M 222
h!
k=2
8-2 00
Mt
1
k=0
3t202
-1
2Mt
3t20²
exp
6 2Mt
Therefore,
3t2a²
3s20²
88 < exp
-s(a02 + + + n
-exp -s(ao= +c)+ 6n 4Bs
6 2Mt
3s
exp
88 + 2
a +
6n 4Bs
Solving a: +
3s
and we get
6an
which satisfies that t <
M hence we have
6n-1Bs
BtiBB
6am
88 S exp
3 + 4o
and the proof complete.
28

---

Published as a conference paper at ICLR 2023
The following concentration inequality about vector-valued random variables is commonly used in the literature, see, c.g. Caponnetto & De Vito (2007 Proposition 2) and references therein. Lemma D.6. Let H be real separable Hilbert space. Let & En be i..d. random variables taking values H. Assume that
1 mlmo 1 mm Vm 2,3....
E BEI
(89)
2
Then for fixed & E (0, 1), one has
2
BE
2 2 n
+
In
(90)
n
vn
H
Particularly, a sufficient condition for
89 is
|| H 2 a.s., and Ell S o².
The following Bernstein type concentration inequality about self-adjoint Hilbert-Schmict operator valued random variable results from applying the discussion in Minsker (2017) Section 3.2) to Tropp 2012 Theorem 7.3.1). It can be found in, e.g., Lin & Cevher (2020) Lemma 24).
Lemma D.7. Let H be a separable Hilbert space. Let AI,..., A, be i..dd random variables taking values of self-adjoint
Cllberr--chhmie operators such that EA1 O. ||A1|| S L almost surely for
some L > 0 and EA2 3 V for some positive trace-class operator V. Then, for any E (0, 1), with
probability at least - 8 we have
a
2LB 3n
2 n
B In 4
+V
8|]
E MORE EXPERIMENTS
In this section we provide more results about the experiments.
E. MORE EXPERIMENTS ON THE INTERVAL
In the following experiments, we use the same setting as in Section 4 We consider other commonly used kernels and set I' of its eigenfunctions. We also compare KRR with another regulariza- tion algorithm called spectral cut-off (CUT), which also never saturates like GF (see, e.g. Lin et al. (2018 Example 3.1)).
We introduce another kernel with known explicit forms of eigenfunction, which will be used as the underlying regression function.
Heavy-side step kernel
The heavy-side step kernel on [0, 1] is defined by
(1 x)y
x 2 yi if I I< y-
k(x, y) = min(z, (1 max(x, v)) =
(91)
(1 1 y)x
The associated RKHS is
ff H (0. f / f(0) f11= = 0, J (()())))
<
(92)
with inner product (f.g) m: = So (tt (t) is known that the eigen-system of this kernel is
A 2n en (Zsin(uTT)) n= 1,2,
(93)
and hence / 0.5.
We conduct experiments on the two kernels and set the regression function to be one of the eigen- functions. We report the results in Table E. on page 30 The results are generally the same as that of Section 4 GF and CUT methods are similar and they both achieve better performances as increases, while KRR reaches its best performance at a 2 with resulting max rate approximately 0.8, verifying theory. We also notice that there are some numerical fluctuation. We attribute them to randomness where we find the deviance is large and numerical error since the eigenvalues small. In conclusion, the numerical results supportive.
29

---

In this part conduct experiments beyond dimension 1. We consider inner-product kernlls on the sphere X' S I3 with being the uniform distribution. The reason is that in general is hard to find an explicit dggn-ddcoopooiitinn of general kernel, where we can obtain explicit forms of Sigen-functions for inner-product kernels on $d-1 which are necessary for us to construct smooth regression functions. These eigen-functions are known as the spherical harmonics, which turn out to be homogeneous polynomials. We refer to Dai & Xu (013) for detailed introduction. Published as a conference paper at ICLR 2023
f E1
f "=6
E2
f E3
Kernel
KRR
GF
CUT
KRR
GF
CUT
KRR
GF
CUT
1.5
.73
.72
.73
.76
.74
.73
.75
.74
.75
.76
.76
.78
.80
.78
.79
.78
.78
.81
min(x,1)
2.5
.69
.80
.81
.73
.81
.82
.69
.82
.83
.58
.82
.84
.62
.83
.83
.59
.84
.85
3.5
.49
.84
.86
.54
.85
.88
.51
.86
.90
1.5
.77
.83
.71
.80
.75
.73
.88
.75
.72
.83
.83
.74
.80
.80
.79
.78
.80
.77
Heavy-side step
2.5
.83
.87
.76
.68
.84
.84
.64
.84
.84
.75
-90
.79
.57
.87
.86
.54
.88
.89
3.5
.65
.92
.81
.49
.89
.88
.46
.92
.95
Table 2: Convergence rates comparison between KRR, GF and CUT with = on aT for various a's. Bold numbers represent the max over different choices of X.
E.2 EXPERIMENTS ON THE SPHERE
On S², the spherical harmonics are often denoted by Y," / = 0, 1,2,.... m -l,...,4 and Y is a homogeneous polynomial of order I. We pick some of them to be our underlying truth function f*, which are listed below:
3
1
15
(21,
4T
Z1,
Y2
2x1,
2 π
Z1
1
105 {o}
Y3 22,
x2)233
π
In terms of kernels, we use the truncated power function k(æ, y) = (1- || - -y1 where a, max(a, 0). It is known that if p > definite gd-1 (Wendland 2004 Theorem 6.20). However, do not know the eigen-decay rate 33 for these kernels.
[ + 1, this kernel is positive definite on IR and thus positive
In the following experiment, basically follow the same procedure described in Section 4 except that we choose the regularization parameter by x = nー with various The results are collected in Table B.2 on [3] We also plot the error curves of one of the experiments in Figure on p3ge The results show that the convergences rates of KRR increase and then decrease as decrease, while the convergences rates of GF keep increasing, and the best convergence rate of KRR is significant slower than that of GF. We conclude that this experiment also justifies the saturation effect and our theory.
30

---

Published as a conference paper at ICLR 2023
-"= Y!
1= -===²
= Y
Kernel
0
KRR
GF
KRR
GF
KRR
0.6
.50
.49
.49
.38
.49
.49
0.4
.77
.70
.71
.65
.70
.69
(1 || y|)
0.3
.71
.80
.73
.74
.73
.78
0.2
.45
.96
.49
.83
.50
.89
0.6
.40
.37
.39
.38
.39
0.4
.70
.65
.65
.65
.65
.65
(1 |
v
0.3
.77
.76
.74
.74
.74
.75
0.2
.56
.90
.64
.83
.65
.84
Table Convergence rates comparison between KRR and GF with À en for various 0's. Bold numbers represent the max rate over different choices of X.
Error Decay:k=P44.fy11.1
Error Decay:k= TP4;f=111,GF
-1.
-2.
-2
-2.
-2.4
log
-24
-2.6
-2.8
26
8m0.3, c=100 rm-8.77
8m0.3, cm rm-0.76
6-0.4, c-0 r= 0.70
B-0.4, 100 m 0.65
8-0.5,
1000
2 10
3x100
4x100
2x10
10
4x100
Figure 2: Error decay curves of KRR and GF with kernel (1 || - =1l on 8 and f = Y
31


Reviews:
[{"review_id": "fXJJifW9JKG", "reviewer": "Reviewer_VSqD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper is dedicated to a theoretical analysis of the saturation effect, that is the gap between information theoretical lower bound on the generalization error of KRR and the actual error. This effect has been widely observed in practices. The main result of the paper is given in Theorem 3.1, that deduces a lower bound on the accuracy of KRR under assumptions (A) eigenvalues decay rate, 1) smoothness of kernel and 2) lower bound on the variance of noice. ", "summary_of_the_review": "A paper is theoretical. Statements are justified. Since ICLR is more oriented towards experiments, a paper needs to enhance experimental section. Is everything understood with the saturation effect after that theory was built, or something is still present in experiments that was not covered by theory?", "strength_and_weaknesses": "I have not checked mathematical proofs completely, though major arguments seems to be correct. \n\nFirst general question that appears after reading the article is: can the condition (2) be weakened. Does the saturation effect disappear is we have zero noise? E.g. what changes if we set sigma=0 in numerical experiments of Section 4? From the bias-variance decomposition formula on page 4 it seems that the effect should disappear, because the variance term will disappear. Could you comment on that.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "OMYF2Ifh1q5", "reviewer": "Reviewer_iDfT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the saturation effect of KRR. Under some additional assumptions, the paper provides a lower bound of the rate of generalization error for the case where $f\\in[\\mathcal{H}]^\\alpha$ for some $\\alpha>2$. The proposed lower bound matches the existing upper bound when $\\alpha>2$ and verifies the saturation effect of KRR.", "summary_of_the_review": "Overall, I think this paper provides an important contribution to the saturation effect of KRR. But the authors need to provide more discussions on the additional assumptions.\n", "strength_and_weaknesses": "The paper is well-written and easy to follow. The authors provide proof of a long-standing conjecture about the information-theoretical lower bound of KRR. The theoretical contribution is significant.\n\nHowever, I still have some concerns about the assumptions. The lower bound is obtained under different assumptions than the upper bound. The upper bound (prop 2.2) requires the distributions satisfying conditions (B') and (C), while the proposed lower bound (thm 3.1) requires Assumption 1 and 2. Thus I do not think this paper completely proves the conjecture since it is still unknown whether the proposed lower bound can be obtained under condition (B') and (C).\n\nI'm also confused about the assumptions on the noise. Notice that condition (C) assumes the momentum of the noise is upper bounded but Assumption 2 requires the noise to be non-vanishing. These two assumptions seem somewhat opposite. I hope the authors can provide a detailed discussion of the required assumptions.\n\nminors:\n\nLine 2 of thm 3.1: \"satisfies the that\" -> \"satisfies that\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MgM0fvYv7s5", "reviewer": "Reviewer_1PPr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the saturation effect of kernel ridge regression (KRR), providing a proof of the conjecture. The main result is a lower bound on the generalization error which suggests that KRR cannot achieve the information theoretical lower bound when the smoothness of the underground truth function exceeds certain level.", "summary_of_the_review": "Overall, I think this is an interesting paper with solid theoretical contributions to kernel methods.", "strength_and_weaknesses": "The paper presents new insights into the saturation phenomenon: the optimally tuned KRR can achieve the minimax rate $n^{-\\alpha/(\\alpha+\\beta)}$ when the smoothness of the underlying truth function is within certain threshold; however, the rate for the estimator is bounded from below by $n^{-2/(2+\\beta)}$ if the smoothness exceeds the threshold. This could be a useful contribution to learning theory.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FtckJcP0udT", "reviewer": "Reviewer_s1WT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors explain the slow convergence of the Nonparametric Kernel regression with ridge regularization in the regime where the true prediction function is too smooth compared with that of the kernel. \n\nTwo parameters have been introduced: although not explicitly explained, \\beta controls the span of the kernel in the RKHS, and \\alpha controls the smoothness of the true prediction function compared with the used kernel. When \\alpha=2, the smoothness is equal to the that of the kernel, and if \\alpha > 2, the prediction function is smoother than the used kernel. In this case, the convergence can be slow even though generally the smooth functions are preferred for generalization.\n\nThe authors provided an analysis on this regime and showed some experiments confirming the derivation.", "summary_of_the_review": "The focus of the paper is on the regime where the prediction function is too smooth compared with that of the kernel function. I find the paper  interesting and think the paper can be published at ICLR, but I am not an expert to provide reviews for the quality of the proof techniques.", "strength_and_weaknesses": "The paper is partially interesting in terms of considering an unexplored regime where our model is too complex compared with the true prediction function. I am not an expert who can look into the details of the proof, but the derived result seems to provide a clear interpretation and the coincidence with the experiments.\n\nHowever in practice, the proposed saturation effect can be addressed by changing the kernel functions.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster