# On the Saturation Effect of
Kernel Ridge Regression

Yicheng Li & Haobo Zhang
Center for Statistical Science, Department of Industrial Engineering
Tsinghua University, Beijing, China
<EMAIL_ADDRESS>
&Qian Lin
Center for Statistical Science, Department of Industrial Engineering
Tsinghua University, Beijing, China
and
Beijing Academy of Artificial Intelligence, Beijing, China
<EMAIL_ADDRESS>
###### 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.

##  1 Introduction

Suppose that we have observed $n$ i.i.d. samples
$\left\\{(x_{i},y_{i})\right\\}_{i=1}^{n}$ from an unknown distribution $\rho$
supported on $\mathcal{X}\times\mathcal{Y}$ where
$\mathcal{X}\subseteq\mathbb{R}^{d}$ and $\mathcal{Y}\subseteq\mathbb{R}$. One
of the central problems in the statistical learning theory is to find a
function $\hat{f}$ based on these observations such that the generalization
error

$\displaystyle\mathbb{E}_{(x,y)\sim\rho}\left[\left(\hat{f}(x)-y\right)^{2}\right]$
(1)

is small. It is well known that the conditional mean
$f_{\rho}^{*}(x)\coloneqq\mathbb{E}_{\rho}[~{}y\;|\;x~{}]=\int_{\mathcal{Y}}y\differential\rho(y|x)$
minimizes the square loss $\mathcal{E}(f)=\mathbb{E}_{\rho}(f(x)-y)^{2}$ where
$\rho(y|x)$ is the distribution of $y$ conditioning on $x$. Thus, this
question is equivalent to looking for an $\hat{f}$ such that the
generalization error

$\displaystyle\mathbb{E}_{x\sim\mu}\left[\left(\hat{f}(x)-f_{\rho}^{*}(x)\right)^{2}\right]$
(2)

is small, where $\mu$ is the marginal distribution of $\rho$ in $\mathcal{X}$.
In other words, $\hat{f}$ can be viewed as an estimator of $f_{\rho}^{*}$.
When there is no explicit parametric assumption made on the distribution
$\rho$ or the function $f_{\rho}^{*}$, researchers often assumed that
$f^{*}_{\rho}$ falls into a class of certain functions and developed lots of
non-parametric methods to estimate $f^{*}_{\rho}$ (e.g., Györfi (2002);
Tsybakov (2009)).

The kernel method, one of the most widely applied non-parametric regression
methods (e.g., Kohler & Krzyzak (2001); Cucker & Smale (2001); Caponnetto & De
Vito (2007); Steinwart et al. (2009); Fischer & Steinwart (2020)), assumes
that $f^{*}_{\rho}$ belongs to certain reproducible kernel Hilbert space
(RKHS) $\mathcal{H}$, a separable Hilbert space associated to a kernel
function $k$ defined on $\mathcal{X}$. The kernel ridge regression (KRR),
which is also known as the Tikhonov regularization or regularized least
squares, estimates $f^{*}_{\rho}$ by solving the penalized least square
problem:

$\displaystyle\hat{f}_{\lambda}^{\mathrm{KRR}}$
$\displaystyle=\operatorname*{arg\,min}_{f\in\mathcal{H}}\left(\frac{1}{n}\sum_{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda\norm{f}_{\mathcal{H}}^{2}\right),$
(3)

where $\lambda>0$ is the so-called regularization parameter. By the
representer theorem (see e.g., Andreas Christmann (2008)), this estimator has
an explicit formula (please see (8) for the exact meaning of the notation):

$\displaystyle\hat{f}_{\lambda}^{\mathrm{KRR}}(x)=\mathbb{K}(x,X)\left(\mathbb{K}(X,X)+n\lambda
I\right)^{-1}\mathbf{y}.$

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^{*}_{\rho}\in\mathcal{H}$ without any further smoothness assumptions,
Caponnetto & De Vito (2007) and Steinwart et al. (2009) showed that the
generalization error of KRR achieves the information theoretical lower bound
$n^{-\frac{1}{1+\beta}}$, where $\beta$ is a characterizing quantity of the
RKHS $\mathcal{H}$ (see e.g., the eigenvalue decay rate defined in Condition
(A)).

Further studies reveal that when more regularity(or smoothness) of
$f^{*}_{\rho}$ is assumed, the KRR fails to achieve the information theoretic
lower bound of the generalization error. More precisely, when $f^{*}_{\rho}$
is assumed to belong some interpolation space $[\mathcal{H}]^{\alpha}$ of the
RKHS $\mathcal{H}$ where $\alpha>2$, the information theoretical lower bound
of the generalization error is $n^{-\frac{\alpha}{\alpha+\beta}}$ (Rastogi &
Sampath, 2017) and the best upper bound of the generalization error of KRR is
$n^{-\frac{2}{2+\beta}}$ (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. Bauer et
al. (2007); Gerfo et al. (2008)). It has been conjectured for decades that no
matter how carefully one tunes the KRR, the rate of the generalization error
can not be faster than $n^{-\frac{2}{2+\beta}}$ (Gerfo et al., 2008; Dicker et
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^{-\frac{2}{2+\beta}}$ 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 algorithms including kernel gradient descent, spectral cut-
off, etc, see e.g. Rosasco et al. (2005); Bauer et al. (2007); Gerfo et al.
(2008); Mendelson & Neeman (2010). The spectral regularization algorithms 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 et al., 2010). Since the spectral algorithms were
introduced into the statistical learning theory, the saturation effect has
been also observed in practice and reported in literatures (Bauer et al.,
2007; Gerfo et al., 2008).

Researches on spectral algorithms show that the asymptotic performance of
spectral algorithms is mainly determined by two ingredients (Bauer et al.,
2007; Rastogi & Sampath, 2017; Blanchard & Mücke, 2018; Lin et al., 2018). One
is 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 not achieve the information
theoretical lower bound when the regularity of $f^{*}_{\rho}$ is high. This is
the (conjectural) saturation effect for the spectral regularized algorithms
(Bauer et al., 2007; Lin & Cevher, 2020; Lian et al., 2021). To the best of
our knowledge, most works pursue showing that spectral regularized algorithm
with high qualification can 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 us to solve the saturation effect of other spectral
algorithms.

##### Notation.

Let us denote by $X=(x_{1},\dots,x_{n})$ the sample input matrix and
$\mathbf{y}=(y_{1},\dots,y_{n})^{\prime}$ the sample output vector. We denote
by $\mu$ the marginal distribution of $\rho$ on $\mathcal{X}$. Let
$\epsilon_{i}\coloneqq y_{i}-f^{*}(x_{i})$ be the noise.

We use $L^{p}(\mathcal{X},\differential\mu)$ (sometimes abbreviated as
$L^{p}$) to represent the Lebesgue $L^{p}$ spaces, where the corresponding
norm is denoted by $\norm{\cdot}_{L^{p}}$. Hence, we can express the
generalization error as

$\displaystyle\mathbb{E}_{x\sim\mu}\left[\left(\hat{f}(x)-f_{\rho}^{*}(x)\right)^{2}\right]=\norm{\hat{f}-f_{\rho}^{*}}_{L^{2}}^{2}.$

We use the asymptotic notations $O(\cdot)$, $o(\cdot)$, $\Omega(\cdot)$ and
$\omega(\cdot)$. We also denote $a_{n}\asymp b_{n}$ iff $a_{n}=O(b_{n})$ and
$a_{n}=\Omega(b_{n})$. We use the asymptotic notations in probability
$O_{\mathbb{P}}(\cdot)$ and $\Omega_{\mathbb{P}}(\cdot)$ to state our results.
Let $\\{a_{n}\\}_{n\geq 1}$ be a sequence of positive numbers and
$\\{\xi_{n}\\}_{n\geq 1}$ a sequence of non-negative random variables. If for
any $\delta>0$ there exists $M_{\delta}>0$ and $N_{\delta}>0$ such that
$\mathbb{P}\\{\xi_{n}<M_{\delta}a_{n}\\}\geq 1-\delta,\ \forall n\geq
N_{\delta}$, we say that $\xi_{n}$ is bounded (above) by $a_{n}$ in
probability and write $\xi_{n}=O_{\mathbb{P}}(a_{n})$. The definition of
$\Omega_{\mathbb{P}}(b_{n})$ follows similarly.

##  2 Brief review of the saturation effect

###  2.1 Regression over Reproducing kernel Hilbert space

Throughout the paper, we assume that $\mathcal{X}\subset\mathbb{R}^{d}$ is
compact and $k$ is a continuous positive-definite kernel function defined on
$\mathcal{X}$. Let $T:L^{2}(\mathcal{X},\differential\mu)\to
L^{2}(\mathcal{X},\differential\mu)$ be the integral operator defined by

$\displaystyle(Tf)(x)\coloneqq\int_{\mathcal{X}}k(x,y)f(y)\differential\mu(y).$
(4)

It is well known that $T$ is trace-class(thus compact), positive and self-
adjoint (Steinwart & Scovel, 2012). The spectral theorem of compact self-
adjoint operators together with Mercer’s theorem (see e.g., Steinwart & Scovel
(2012)) yield that

$\displaystyle T$ $\displaystyle=\sum_{i\in
N}\lambda_{i}\left\langle{\cdot,e_{i}}\right\rangle_{L^{2}}e_{i},$ (5)
$\displaystyle k(x,y)$ $\displaystyle=\sum_{i\in
N}\lambda_{i}e_{i}(x)e_{i}(y),$ (6)

where $\lambda_{i}$’s are the positive eigenvalues of $T$ in descending order,
$e_{i}$’s are the corresponding eigenfunctions, and $N\subseteq\mathbb{N}$ is
an at most countable index set. Let $\mathcal{H}$ be the separable RKHS
associated to the kernel $k$ (see, e.g., Wainwright (2019, Chapter 12)). One
may easily verify that $\left\\{\lambda_{i}^{1/2}e_{i}\right\\}_{i\in N}$ is
an orthonormal basis of $\mathcal{H}$. Since we are interested in the
infinite-dimensional cases, we may assume that $N=\mathbb{N}$.

Recall that the kernel ridge regression estimates the regression function
$f^{*}_{\rho}$ through the following optimization problem:

$\displaystyle\hat{f}_{\lambda}^{\mathrm{KRR}}$
$\displaystyle=\operatorname*{arg\,min}_{f\in\mathcal{H}}\left(\frac{1}{n}\sum_{i=1}^{n}(y_{i}-f(x_{i}))^{2}+\lambda\norm{f}_{\mathcal{H}}^{2}\right).$
(7)

The representer theorem (see e.g., Andreas Christmann (2008)) implies that

$\displaystyle\hat{f}^{\mathrm{KRR}}_{\lambda}(x)=\mathbb{K}(x,X)(\mathbb{K}(X,X)+n\lambda
I)^{-1}\mathbf{y},$ (8)

where

$\displaystyle\mathbb{K}(x,X)=\left(k(x,x_{1}),\dots,k(x,x_{n})\right)\mbox{
and }\mathbb{K}(X,X)=\big{(}k(x_{i},x_{j})\big{)}_{n\times n}.$

The following conditions are commonly adopted when discussing the performance
of $\hat{f}_{\lambda}^{\mathrm{KRR}}$.

${\bf(A)}$ Eigenvalue decay rate: there exists absolute constant $c_{1}>0$,
$c_{2}>0$ and $\beta\in(0,1)$ such that the eigenvalues
$\lambda_{i}^{\prime}s$ of $T$, the integral operator associated to the kernel
$k$, satisfy

$\displaystyle c_{1}i^{-1/\beta}\leq\lambda_{i}\leq
c_{2}i^{-1/\beta},~{}\forall~{}i=1,2,\dots$ (9)

${\bf(B)}$ Smoothness condition: the conditional mean
$f_{\rho}^{*}=\mathbb{E}_{\rho}[~{}y\mid x~{}]$ satisfies that
$\norm{f_{\rho}^{*}}_{\mathcal{H}}\leq R$ for some $R>0$;

${\bf(C)}$ Moment condition of the noise:

$\displaystyle\int_{\mathcal{Y}}\absolutevalue{y-f_{\rho}^{*}(x)}^{m}\differential\rho(y|x)\leq\frac{1}{2}m!\sigma^{2}M^{m-2},\quad\mu\text{-a.e.
}x\in\mathcal{X},\quad\forall m=2,3,\dots,$

where $\sigma,M>0$ are some constants.

The quantity $\beta$ appearing in the condition ${\bf(A)}$ is often referred
to as the eigenvalue decay rate of an RKHS or the corresponding kernel
function $k$. It describes the span of the RKHS and depends only on the kernel
function $k$ (or equivalently, the RKHS $\mathcal{H}$). This polynomial decay
rate condition is quite standard in the literature and is also known as the
capacity condition or effective dimension condition (Caponnetto & De Vito,
2007; Steinwart et al., 2009; Blanchard & Mücke, 2018), which is closely
related to the covering/entropy number conditions of the RKHS (see, e.g.,
Steinwart et al. (2009, Theorem 15)). The condition ${\bf(B)}$ requires that
the conditional mean $f_{\rho}^{*}(x)$ falls into the RKHS $\mathcal{H}$ with
norm smaller than a given constant $R$. The condition ${\bf(C)}$ requires that
the tail probability of the ‘noise’ decays fast, which is satisfied if the
noise $\varepsilon=y-f^{*}_{\rho}(x)$ is bounded or sub-Gaussian.

######  Proposition 2.1 (Optimality of KRR).

Suppose that $\mathcal{H}$ satisfies the condition ${\bf(A)}$ and
$\mathcal{P}$ consists of all the distributions satisfying the conditions
${\bf(B)}$ and ${\bf(C)}$.

i) The minimax rate of estimating $f_{\rho}^{*}$ is $n^{-\frac{1}{1+\beta}}$,
i.e., we have

$\displaystyle\inf_{\hat{f}}\sup_{\rho\in\mathcal{P}}\mathbb{E}_{\rho}\norm{\hat{f}-f^{*}_{\rho}}^{2}_{L^{2}}=\Omega\left(n^{-\frac{1}{1+\beta}}\right),$
(10)

where $\inf_{\hat{f}}$ is taken over all estimators and both the expectation
$\mathbb{E}_{\rho}$ and the conditional mean $f^{*}_{\rho}$ depend on $\rho$.

ii) If we choose $\lambda\asymp n^{-\frac{1}{1+\beta}}$, then we have

$\displaystyle\norm{\hat{f}^{\mathrm{KRR}}_{\lambda}-f^{*}_{\rho}}_{L^{2}}^{2}=O_{\mathbb{P}}\left(n^{-\frac{1}{1+\beta}}\right).$
(11)

This theorem comes from a combination (with a slight modification) of the
upper rates and lower rates given in Caponnetto & De Vito (2007). It says that
the optimally tuned KRR can achieve the information theoretical lower bound if
$f_{\rho}^{*}(x)$ falls into $\mathcal{H}$ and no further regularity condition
is imposed.

###  2.2 The saturation effect

When further regularity assumption is made on the conditional mean
$f_{\rho}^{*}(x)$, there will be a 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 describe the
saturation effect, we need to introduce a family of interpolation spaces of
the RKHS $\mathcal{H}$ (see, e.g. Fischer & Steinwart (2020)).

For any $s\geq 0$, the operator $T^{s}:L^{2}(\mathcal{X})\rightarrow
L^{2}(\mathcal{X})$ is given by

$\displaystyle T^{s}(f)$ $\displaystyle=\sum_{i\in
N}\lambda_{i}^{s}\left\langle{f,e_{i}}\right\rangle_{L^{2}}e_{i}$ (12)

and the interpolation space $[\mathcal{H}]^{\alpha}$ for $\alpha\geq 0$ is
defined by

$\displaystyle[\mathcal{H}]^{\alpha}\coloneqq\operatorname{Ran}T^{\alpha/2}=\left\\{\sum_{i\in
N}a_{i}\lambda_{i}^{\alpha/2}e_{i}\Big{|}(a_{i})_{i\in
N}\in\ell^{2}(N)\right\\},$ (13)

with the inner product defined by

$\displaystyle\left\langle{f,g}\right\rangle_{[\mathcal{H}]^{\alpha}}=\left\langle{T^{-\alpha/2}f,T^{-\alpha/2}g}\right\rangle_{L^{2}}.$
(14)

From the definition, it is easy to verify that
$\left\\{\lambda_{i}^{\alpha/2}e_{i}\right\\}_{i\in N}$ forms an orthonormal
basis of $[\mathcal{H}]^{\alpha}$ and thus $[\mathcal{H}]^{\alpha}$ is also a
separable Hilbert space. It is obvious that $[\mathcal{H}]^{0}\subseteq L^{2}$
and $[\mathcal{H}]^{1}\subseteq\mathcal{H}$. Moreover, we have isometric
isomorphisms $T^{s/2}:[\mathcal{H}]^{\alpha}\to[\mathcal{H}]^{\alpha+s}$ and
compact embeddings
$[\mathcal{H}]^{\alpha_{1}}\hookrightarrow[\mathcal{H}]^{\alpha_{2}},\quad\forall\alpha_{1}>\alpha_{2}\geq
0$. The example below illustrates the intuition of $\alpha$: it describes the
smoothness of functions with respect to the kernel.

######  Example 2.1 (Sobolev RKHS (Fischer & Steinwart, 2020)).

Let $\mathcal{X}=\Omega\subseteq\mathbb{R}^{d}$ be a bounded domain with
smooth boundary. We consider the Sobolev space $\mathcal{H}=H^{s}(\Omega)$,
which, roughly speaking, consists of functions with weak derivatives up to
order $s$, see, e.g., Adams & Fournier (2003). It is known that if
$s>\frac{d}{2}$, we have the Sobolev embedding $H^{s}(\Omega)\hookrightarrow
C^{r}(\Omega)$ where $C^{r}(\Omega)$ is the Hölder space of continuous
differentiable functions and $r=s-\frac{d}{2}$, and thus $H^{s}(\Omega)$ is an
RKHS (Fischer & Steinwart, 2020). Moreover, by the method of real
interpolation (Steinwart & Scovel, 2012, Theorem 4.6), we have
$[\mathcal{H}]^{\alpha}\cong H^{\alpha s}(\Omega)$ for $\alpha>0$. This
example shows that the larger the $\alpha$, the “smoother” the functions in
$[\mathcal{H}]^{\alpha}$.

If one believes that $f_{\rho}^{*}(x)$ possesses more regularity (i.e.,
$f_{\rho}^{*}(x)\in[\mathcal{H}]^{\alpha}$), we may replace the condition
${\bf(B)}$ by the following condition:

${\bf(B^{\prime})}$ Smoothness condition: the conditional mean
$f_{\rho}^{*}=\mathbb{E}_{\rho}[~{}y\mid x~{}]$ satisfies that
$\norm{f_{\rho}^{*}}_{[\mathcal{H}]^{\alpha}}\leq R$ for some $R>0$.

In this condition, the parameter $\alpha$ describes the smoothness of the
regression function with respect to the underlying kernel. The larger $\alpha$
is, the “smoother” the regression function is. This assumption is also
referred to as the source condition in the literature, see, e.g., Bauer et al.
(2007); Rastogi & Sampath (2017). With this new regularity assumption, we have
the following statement.

######  Proposition 2.2 (Saturation phenomenon of KRR).

Suppose that $\mathcal{H}$ satisfies the condition ${\bf(A)}$ and
$\mathcal{P}$ consists of all the distributions satisfying the conditions
${\bf(B^{\prime})}$ and ${\bf(C)}$.

i) The minimax rate of estimating $f_{\rho}^{*}$ is
$n^{-\frac{\alpha}{\alpha+\beta}}$, i.e., we have

$\displaystyle\inf_{\hat{f}}\sup_{\rho\in\mathcal{P}}\mathbb{E}_{\rho}\norm{\hat{f}-f^{*}_{\rho}}^{2}_{L^{2}}=\Omega\left(n^{-\frac{\alpha}{\alpha+\beta}}\right),$
(15)

where $\inf_{\hat{f}}$ is taken over all estimators and both the expectation
$\mathbb{E}_{\rho}$ and the regression function $f^{*}_{\rho}$ depend on
$\rho$.

ii) Let $\tilde{\alpha}=\min(\alpha,2)$. Then, by choosing $\lambda\asymp
n^{-\frac{1}{\tilde{\alpha}+\beta}}$, we have

$\displaystyle\norm{\hat{f}^{\mathrm{KRR}}_{\lambda}-f^{*}}_{L^{2}}^{2}=O_{\mathbb{P}}\left(n^{-\frac{\tilde{\alpha}}{\tilde{\alpha}+\beta}}\right).$
(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 1 (ii)). It says that the
optimally tuned KRR can achieve the information theoretical lower bound if
$f^{*}_{\rho}(x)\in[\mathcal{H}]^{\alpha}$ when $\alpha\leq 2$. However, when
$\alpha>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 1 (RKHS).

We assume that $\mathcal{H}$ is an RKHS over a compact set
$\mathcal{X}\subseteq\mathbb{R}^{d}$ associated with a Hölder-continuous
kernel $k$, that is, there exists some $s\in(0,1]$ and $L>0$ such that

$\displaystyle\absolutevalue{k(x_{1},x_{2})-k(y_{1},y_{2})}\leq
L\norm{(x_{1},x_{2})-(y_{1},y_{2})}_{\mathbb{R}^{d\times d}}^{s},\quad\forall
x_{1},x_{2},y_{1},y_{2}\in\mathcal{X}.$

######  Assumption 2 (Noise).

The conditional variance satisfies that

$\displaystyle\mathbb{E}_{(x,y)\sim\rho}\left[(y-f^{*}_{\rho}(x))^{2}\;|\;x\right]\geq\bar{\sigma}^{2}>0,\quad\mu\text{-a.e.
}x\in\mathcal{X}.$ (17)

The first assumption is a Hölder condition on the kernel, which is slightly
stronger than assuming that $k$ is continuous. It is satisfied, for example,
when $k$ is Lipschitz or $C^{1}$. Kernels that satisfy this assumption include
the popular RBF kernel, Laplace kernel and kernels of the form
$(1-\norm{x-y})^{p}_{+}$ (Wendland, 2004, Theorem 6.20), and kernels
associated with Sobolev RKHS introduced in Example 2.1.

The second assumption requires that the variance of the noise
$\varepsilon=y-f^{*}_{\rho}(x)$ is lower bounded. When
$y=f^{*}(x)+\varepsilon$ where $\varepsilon\sim N(0,\sigma^{2})$ is an
independent noise, the second assumption simply requires that $\sigma\neq 0$.
In other words, Assumption 2 is a fairly weak assumption which just requires
that the noise is non-vanishing almost everywhere.

Now we are ready to state our main theorem.

######  Theorem 3.1 (Saturation effect).

Suppose that $\mathcal{H}$ satisfies the condition ${\bf(A)}$, the
distribution $\rho$ satisfies that $f_{\rho}^{*}\neq 0$ and
$f_{\rho}^{*}\in[\mathcal{H}]^{\alpha}$ for some $\alpha\geq 2$, and
Assumptions 1 and 2 hold.

For any $\delta>0$, for any choice of regularization parameter $\lambda(n)$
satisfying that $\lambda(n)\to 0$, we have that, for sufficiently large $n$,

$\displaystyle\mathbb{E}\left[\norm{\hat{f}_{\lambda}^{\mathrm{KRR}}-f^{*}}^{2}_{L^{2}}\;\Big{|}\;X\right]\geq
cn^{-\frac{2}{2+\beta}}$ (18)

holds with probability at least $1-\delta$ for some positive constant $c$.
Consequently, we have

$\displaystyle\mathbb{E}\left[\norm{\hat{f}_{\lambda}^{\mathrm{KRR}}-f^{*}}^{2}_{L^{2}}\;\Big{|}\;X\right]=\Omega_{\mathbb{P}}\left(n^{-\frac{2}{2+\beta}}\right).$

######  Remark 3.2.

The saturation effect of KRR states that when the regression function is very
smooth, i.e., $\alpha\geq 2$, no matter how the regularization parameter is
tuned, the convergence rate of KRR is bounded below by $\frac{2}{2+\beta}$.
The saturation lower bound also coincides with the upper bound (16) in
Proposition 2.2. Therefore, Theorem 3.1 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 $f^{*}\in[\mathcal{H}]^{\alpha}$, 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
$K_{x}:\mathbb{R}\to\mathcal{H}$ defined by $K_{x}y=yk(x,\cdot)$ and its
adjoint operator $K_{x}^{*}:\mathcal{H}\to\mathbb{R}$ given by
$K_{x}^{*}f=f(x)$. We further introduce the sample covariance operator
$T_{X}:\mathcal{H}\to\mathcal{H}$ by

$\displaystyle T_{X}$
$\displaystyle\coloneqq\frac{1}{n}\sum_{i=1}^{n}K_{x_{i}}K_{x_{i}}^{*},$ (19)

and define the sample basis function

$\displaystyle
g_{Z}\coloneqq\frac{1}{n}\sum_{i=1}^{n}K_{x_{i}}y_{i}\in\mathcal{H}.$ (20)

The following explicit operator form of the solution of KRR is shown in
Caponnetto & De Vito (2007):

$\displaystyle\hat{f}_{\lambda}^{\mathrm{KRR}}=(T_{X}+\lambda)^{-1}g_{Z}.$
(21)

The first step of our proof is the bias-variance decomposition, which differs
from the commonly used approximation-estimation error decomposition in the
literature (e.g. Caponnetto & De Vito (2007); Fischer & Steinwart (2020)). It
can be shown that

$\displaystyle\mathbb{E}\left[\norm{\hat{f}^{\mathrm{KRR}}_{\lambda}-f^{*}_{\rho}}^{2}_{L^{2}}\;\Big{|}\;X\right]$
$\displaystyle=\lambda^{2}\norm{(T_{X}+\lambda)^{-1}f^{*}_{\rho}}^{2}_{L^{2}}+\frac{1}{n^{2}}\sum_{i=1}^{n}\sigma_{x_{i}}^{2}\norm{(T_{X}+\lambda)^{-1}k(x_{i},\cdot)}^{2}_{L^{2}}$
$\displaystyle\eqqcolon\mathbf{Bias}^{2}+\mathbf{Var}.$

Then, the desired lower bound can be derived by proving the following lower
bounds of the two terms respectively:

$\displaystyle\mathbf{Bias}^{2}=\Omega_{\mathbb{P}}\left(\lambda^{2}\right),\quad\mathbf{Var}=\Omega_{\mathbb{P}}\left(\frac{\lambda^{-\beta}}{n}\right).$
(22)

These two lower bounds follow from our bias-variance trade-off intuition:
smaller $\lambda$ (less regularization) leads to smaller bias but larger
variance, while the variance decreases as $n$ 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
$\norm{(T_{X}+\lambda)^{-1}f^{*}_{\rho}}^{2}_{L^{2}}\approx\norm{(T+\lambda)^{-1}f^{*}_{\rho}}^{2}_{L^{2}}$,
where we refine the concentration result between $(T_{X}+\lambda)^{-1/2}$ and
$(T+\lambda)^{-1/2}$ obtained in the previous literature. Second, we use the
eigen-decomposition and the fact that KRR’s qualification is limited to show
that $\lambda\norm{(T+\lambda)^{-1}f^{*}_{\rho}}_{L^{2}}\geq c\lambda$ for
some constant $c>0$. Consequently, we have

$\displaystyle\mathbf{Bias}^{2}\approx\lambda^{2}\norm{(T+\lambda)^{-1}f^{*}_{\rho}}^{2}_{L^{2}}\geq
c\lambda^{2}.$

This lower bound shows that the bais of KRR can only decrease in linear order
with respect to $\lambda$ 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

$\displaystyle\mathbf{Var}\geq\frac{\bar{\sigma}^{2}}{n}\int_{\mathcal{X}}\norm{(T_{X}+\lambda)^{-1}k(x,\cdot)}_{L^{2},n}^{2}\differential\mu(x),$
(23)

where $\norm{f}_{L^{2},n}^{2}\coloneqq\frac{1}{n}\sum_{i=1}^{n}f(x_{i})^{2}$.
This observation (23) is key and novel in the proof, allowing us to make the
following two-step approximation:

$\displaystyle\norm{(T_{X}+\lambda)^{-1}k(x,\cdot)}_{L^{2},n}^{2}\approx\norm{(T+\lambda)^{-1}k(x,\cdot)}_{L^{2},n}^{2}\approx\norm{(T+\lambda)^{-1}k(x,\cdot)}_{L^{2}}^{2}.$

The main difficulty here is to control the errors in the approximation so that
they are infinitesimal 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 Steinwart et al. (2009)), applying tight concentration
inequalities and analyzing the covering number of regularized basis function
family $\left\\{(T+\lambda)^{-1}k(x,\cdot)\right\\}_{x\in\mathcal{X}}$.
Finally, by Mercer’s theorem and the eigenvalue decay rate, we obtain that

$\displaystyle\int_{\mathcal{X}}\norm{(T+\lambda)^{-1}k(x,\cdot)}_{L^{2}}^{2}\differential\mu(x)$
$\displaystyle=\int_{\mathcal{X}}\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda+\lambda_{i}}\right)^{2}e_{i}(x)^{2}\differential\mu(x)$
$\displaystyle=\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda+\lambda_{i}}\right)^{2}\eqqcolon\mathcal{N}_{2}(\lambda).$

It can be shown that
$\mathcal{N}_{2}(\lambda)=\Tr\left[(T+\lambda)^{-1}T\right]^{2}$ and it is a
variant of the effective dimension
$\mathcal{N}(\lambda)=\Tr\left[(T+\lambda)^{-1}T\right]$ introduced in the
literature (Caponnetto & De Vito, 2007). The condition ${\bf(A)}$ implies that
$\mathcal{N}_{2}(\lambda)\geq c\lambda^{-\beta}$. As a result, we get

$\displaystyle\mathbf{Var}$
$\displaystyle\geq\frac{\bar{\sigma}^{2}}{n}\int_{\mathcal{X}}\norm{(T_{X}+\lambda)^{-1}k(x,\cdot)}_{L^{2},n}^{2}\differential\mu(x)\approx\frac{\bar{\sigma}^{2}}{n}\int_{\mathcal{X}}\norm{(T+\lambda)^{-1}k(x,\cdot)}_{L^{2}}^{2}\differential\mu(x)$
$\displaystyle=\frac{\bar{\sigma}^{2}}{n}\mathcal{N}_{2}(\lambda)\geq\tilde{c}\frac{\lambda^{-\beta}}{n}.$

##  4 Numerical Experiments

The saturation effect in KRR has been reported in a number of works (e.g.,
Gerfo et al. (2008); Dicker et al. (2017)). In this section, we illustrate the
saturation effect through a toy example.

Suppose that $\mathcal{X}=[0,1]$ and $\mu$ is the uniform distribution on
$[0,1]$. Let us consider the following first-order Sobolev space containing
absolutely continuous functions

$\displaystyle H^{1}\coloneqq\left\\{f:[0,1]\to\mathbb{R}~{}\Big{|}~{}f\text{
is A.C., }f(0)=0,\ \int_{0}^{1}(f^{\prime}(x))^{2}\differential
x<\infty\right\\}.$ (24)

It is well-known that it is the RKHS associated to the kernel
$k(x,y)=\min(x,y)$ (Wainwright, 2019). Let $T$ be the integral operator
associated to the kernel function $k$. We know explicitly the eigenvalues and
eigenfunctions of this operator:

$\displaystyle\lambda_{n}=\left(\frac{2n-1}{2}\pi\right)^{-2},\quad
e_{n}(x)=\sqrt{2}\sin(\frac{2n-1}{2}\pi x),\quad n=1,2,\dots.$ (25)

It is clear that the eigenvalue decay rate $\beta$ of the kernel function $k$
(or the RKHS $H^{1}$) is $0.5$. To illustrate the saturation effect better, we
choose the second eigen-function $e_{2}=\sqrt{2}\sin\left(\frac{3}{2}\pi
x\right)$ to be the regression function in our experiment. The significance of
this choice is that for any $\alpha>0$, we have
$e_{2}\in[\mathcal{H}]^{\alpha}$. We further set the noise to be an
independent Gaussian noise with variance $\sigma=0.2$. In other words, we
consider the following data generation model:

$\displaystyle y=f^{*}(x)+\sigma\varepsilon,$ (26)

where $f^{*}(x)=e_{2}(x)$ and $\varepsilon\sim N(0,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 $\alpha\geq 1$ and any
$f_{\rho}^{*}\in[\mathcal{H}]^{\alpha}$ (Yao et al., 2007; Lin et al., 2018),
we make a comparison between KRR and GF to 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 $\alpha$’s, we choose the regularization parameter in KRR as
$\lambda=cn^{-\frac{1}{\alpha+\beta}}$ for a fixed constant $c$, and set the
stopping time in the gradient flow by $t=\lambda^{-1}$. It is shown in Lin et
al. (2018) that the choice of stopping time $t$ (i.e., $t=\lambda^{-1}$) is
optimal for the gradient descent algorithm under the assumption that
$f^{*}_{\rho}\in[\mathcal{H}]^{\alpha}$. By choosing different $\alpha$’s, we
also evaluate the performance of the algorithms with different selections of
parameters. For the generalization error
$\|\hat{f}-f^{*}_{\rho}\|_{L^{2}}^{2}$, we numerically compute the integration
($L^{2}$-norm) by Simpson’s formula with $N\gg 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\mathrm{err}=r\log n+b$ to fit the error with respect to the sample size,
and report the slope $r$ as the convergence rate.

The results are reported in Figure 1 on page 1. We also change the regression
function to be other eigenfunctions and list the results in Table 1 on page 1.
First, the error curves show that the error converges indeed in the rate of
$n^{-r}$. Moreover, when we apply the GF method, the convergence rate
increases as the $\alpha$ 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
$\frac{\alpha}{\alpha+\beta}$. In contrast, when we apply the KRR method, the
convergence rate achieves its best performance at $\alpha=2$, and the rate
decreases as $\alpha$ gets bigger, showing the saturation effect. The
resulting best rate also coincides with our theoretic value
$\frac{2}{2+\beta}=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).

Figure 1: 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 one 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^{*}=e_{1}$ | $f^{*}=e_{2}$ | $f^{*}=e_{3}$ | $f^{*}=e_{4}$
---|---|---|---|---
$\alpha$ | 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 | .83 | .59 | .84 | .56 | .87
3.5 | .49 | .84 | .54 | .85 | .51 | .86 | .48 | .90
Table 1: Convergence rates comparison between KRR and GF with
$\lambda=cn^{-\frac{1}{\alpha+\beta}}$ for various $\alpha$’s. Bold numbers
represent the max rate over different choices of $\lambda$.

We conduct further experiments with different kernels and report them in
Section E. 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.

##  5 Conclusion

The saturation effect refers to the phenomenon that kernel ridge regression
fails to achieve the information theoretical lower bound when the regression
function is too smooth. When the regression function is sufficiently smooth, a
saturation lower bound of KRR has been conjectured for decades. In this paper,
we provide a rigorously proof of the saturation effect of KRR, i.e., we show
that, if $f\in[\mathcal{H}]^{\alpha}$ for some $\alpha>2$, the rate of
generalization error of the KRR can not be better than
$n^{-\frac{2}{2+\beta}}$, no matter how one tunes the KRR.

Our results suggest that the KRR method of regularization may be inferior to
some special regularization algorithms, including spectral cut-off and kernel
gradient descent, which never saturate and are capable of achieving optimal
rates (Bauer et al., 2007; Lin et al., 2018). The technical tools developed
here may also help us 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.

We would like to thank Dimitri Meunier and Zikai Shen (Meunier et al., 2024)
for pointing out some issues in the proof (mainly Lemma C.7 and Lemma C.10) of
this paper after its publication. These mistakes do not affect the main
results in this paper and they are corrected in this new revision. We
apologize for any inconvenience caused.

## References

  * Adams & Fournier (2003) Robert A Adams and John JF Fournier.  _Sobolev Spaces_.  Elsevier, 2003.
  * Andreas Christmann (2008) Ingo Steinwart (auth.) Andreas Christmann.  _Support Vector Machines_.  Information Science and Statistics. Springer-Verlag New York, New York, NY, first edition, 2008.
  * Bauer et al. (2007) F. Bauer, S. Pereverzyev, and L. Rosasco.  On regularization algorithms in learning theory.  _Journal of complexity_ , 23(1):52–72, 2007.
  * Blanchard & Mücke (2018) G. Blanchard and Nicole Mücke.  Optimal rates for regularization of statistical inverse learning problems.  _Foundations of Computational Mathematics_ , 18:971–1013, 2018.
  * Caponnetto & Yao (2010) A. Caponnetto and Y. Yao.  Cross-validation based adaptation for regularization operators in learning theory.  _Analysis and Applications_ , 08:161–183, 2010.
  * Caponnetto & De Vito (2007) Andrea Caponnetto and Ernesto De Vito.  Optimal rates for the regularized least-squares algorithm.  _Foundations of Computational Mathematics_ , 7(3):331–368, 2007.
  * Cucker & Smale (2001) Felipe Cucker and Steve Smale.  On the mathematical foundations of learning.  _Bulletin of the American Mathematical Society_ , 39(1):1–49, October 2001.
  * Dai & Xu (2013) 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.
  * Dicker et al. (2017) 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.
  * Engl et al. (1996) Heinz Werner Engl, Martin Hanke, and Andreas Neubauer.  _Regularization of Inverse Problems_ , volume 375.  Springer Science & Business Media, 1996.
  * Fischer & Steinwart (2020) Simon-Raphael Fischer and Ingo Steinwart.  Sobolev norm learning rates for regularized least-squares algorithms.  _Journal of Machine Learning Research_ , 21:205:1–205:38, 2020.
  * Fujii et al. (1993) Junichi Fujii, Masatoshi Fujii, Takayuki Furuta, and Ritsuo Nakamoto.  Norm inequalities equivalent to Heinz inequality.  _Proceedings of the American Mathematical Society_ , 118(3):827–830, 1993.
  * Gerfo et al. (2008) L. Lo Gerfo, Lorenzo Rosasco, Francesca Odone, E. De Vito, and Alessandro Verri.  Spectral algorithms for supervised learning.  _Neural Computation_ , 20(7):1873–1897, 2008.
  * Györfi (2002) László Györfi (ed.).  _A Distribution-Free Theory of Nonparametric Regression_.  Springer Series in Statistics. Springer, New York, 2002.
  * Herdman et al. (2010) T. Herdman, R. Spies, and Karina G. Temperini.  Global saturation of regularization methods for inverse ill-posed problems.  _Journal of Optimization Theory and Applications_ , 148:164–196, 2010.
  * Kohler & Krzyzak (2001) Michael Kohler and Adam Krzyzak.  Nonparametric regression estimation using penalized least squares.  _IEEE Transactions on Information Theory_ , 47(7):3054–3058, 2001.
  * Lian et al. (2021) Heng Lian, Jiamin Liu, and Zengyan Fan.  Distributed learning for sketched kernel regression.  _Neural Networks_ , 143:368–376, November 2021.
  * Lin & Cevher (2020) Junhong Lin and Volkan Cevher.  Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms.  _Journal of Machine Learning Research_ , 21:147–1, 2020.
  * Lin et al. (2018) Junhong Lin, Alessandro Rudi, L. 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.
  * Mathé (2004) Peter Mathé.  Saturation of regularization methods for linear ill-posed problems in Hilbert spaces.  _SIAM journal on numerical analysis_ , 42(3):968–973, 2004.
  * Mendelson & Neeman (2010) Shahar Mendelson and Joseph Neeman.  Regularization in kernel learning.  _The Annals of Statistics_ , 38(1):526–565, February 2010.
  * Meunier et al. (2024) Dimitri Meunier, Zikai Shen, Mattes Mollenhauer, Arthur Gretton, and Zhu Li.  Optimal rates for vector-valued spectral regularization learning algorithms, 2024.
  * Minsker (2017) Stanislav Minsker.  On some extensions of Bernstein’s inequality for self-adjoint operators.  _Statistics & Probability Letters_, 127:111–119, April 2017.
  * Neubauer (1997) Andreas Neubauer.  On converse and saturation results for Tikhonov regularization of linear ill-posed problems.  _SIAM journal on numerical analysis_ , 34(2):517–527, 1997.
  * Rastogi & Sampath (2017) Abhishake Rastogi and Sivananthan Sampath.  Optimal rates for the regularized learning algorithms under general source condition.  _Frontiers in Applied Mathematics and Statistics_ , 3, 2017.
  * Rosasco et al. (2005) 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-18_ , 2005.
  * Steinwart & Scovel (2012) Ingo Steinwart and C. Scovel.  Mercer’s theorem on general domains: On the interaction between measures, kernels, and RKHSs.  _Constructive Approximation_ , 35(3):363–417, 2012.
  * Steinwart et al. (2009) Ingo Steinwart, D. Hush, and C. Scovel.  Optimal rates for regularized least squares regression.  In _COLT_ , pp. 79–93, 2009.
  * Tropp (2012) Joel A. Tropp.  User-friendly tools for random matrices: An introduction.  Technical report, Defense Technical Information Center, Fort Belvoir, VA, December 2012.
  * Tsybakov (2009) Alexandre B. Tsybakov.  _Introduction to Nonparametric Estimation_.  Springer Series in Statistics. Springer, New York ; London, 1st edition, 2009.
  * Vershynin (2018) Roman Vershynin.  _High-Dimensional Probability: An Introduction with Applications in Data Science_ , volume 47.  Cambridge university press, 2018.
  * Wainwright (2019) Martin J. Wainwright.  _High-Dimensional Statistics: A Non-Asymptotic Viewpoint_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
  * Wendland (2004) Holger Wendland.  _Scattered Data Approximation_.  Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, 2004.
  * Yao et al. (2007) Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto.  On early stopping in gradient descent learning.  _Constructive Approximation_ , 26(2):289–315, 2007.

##  Appendix A Basic facts in RKHS

Let $k$ be a continuous positive definite kernel function defined on a compact
set $\mathcal{X}$ and $\mathcal{H}$ be the RKHS associated to the kernel $k$.
Since $k$ is a continuous function and $\mathcal{X}$ is a compact set, there
exists a constant $\kappa$ such that

$\displaystyle|k(x,y)|\leq\kappa^{2}\mbox{ for any }x,y\in\mathcal{X}.$ (27)

It is well known that $k(x,\cdot)\in\mathcal{H}$ as a function and that the
inner product satisfies that

$\displaystyle\left\langle{k(x,\cdot),f}\right\rangle=f(x),\quad\forall
f\in\mathcal{H}.$ (28)

In particularly, we have
$\left\langle{k(x,\cdot),k(y,\cdot)}\right\rangle_{\mathcal{H}}=k(x,y)$.

Let $T:L^{2}\rightarrow L^{2}$ be the integral operator associated to the
kernel fucntion $k$. By the spectral decomposition of $T$, it can be easily
shown that $\operatorname{Ran}T|_{\mathcal{H}}\subseteq\mathcal{H}$ and
$\norm{Tf}_{\mathcal{H}}\leq\kappa^{2}\norm{f}_{\mathcal{H}}$, which implies
that $T$ can also be viewed a bounded linear operator on $\mathcal{H}$. With a
little abuse of notation, we still use $T$ to indicate it.

We denote by $\mathscr{B}(\mathcal{H})$ the set of bounded linear operators
over $\mathcal{H}$ and $\norm{\cdot}_{\mathscr{B}(\mathcal{H})}$ 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 $\mathcal{H}$ is the RKHS associated to the kernel $k$. Let
$\norm{f}_{\infty}\coloneqq\sup_{x\in\mathcal{X}}\absolutevalue{f(x)}$ be the
supremum-norm of a function $f:\mathcal{X}\to\mathbb{R}$. Then for any
$f\in\mathcal{H}$, we have $\norm{f}_{\infty}\leq\kappa\norm{f}_{\mathcal{H}}$

###### Proof.

It is easy to verify that for $f\in\mathcal{H}$,

$\displaystyle\norm{f}_{\infty}$
$\displaystyle=\sup_{x\in\mathcal{X}}\absolutevalue{f(x)}\leq\sup_{x\in\mathcal{X}}\absolutevalue{\left\langle{k(x,\cdot),f}\right\rangle_{\mathcal{H}}}$
$\displaystyle\leq\sup_{x\in\mathcal{X}}\norm{k(x,\cdot)}_{\mathcal{H}}\norm{f}_{\mathcal{H}}\leq\kappa\norm{f}_{\mathcal{H}}.$

∎

######  Definition A.2.

Let $K\subseteq\mathbb{R}^{d}$ be a compact set and $\alpha\in[0,1]$. For a
function $f:K\to\mathbb{R}$, we introduce the Hölder semi-norm

$\displaystyle[f]_{\alpha,K}\coloneqq\sup_{x,y\in K,\ x\neq
y}\frac{\absolutevalue{f(x)-f(y)}}{\absolutevalue{x-y}^{\alpha}},$ (29)

where $\absolutevalue{\cdot}$ represents the usual Euclidean norm. Then, we
define the Hölder space

$\displaystyle
C^{\alpha}(K)\coloneqq\left\\{f:K\to\mathbb{R}\;|\;[f]_{\alpha,K}<\infty\right\\},$
(30)

which is equipped with norm

$\displaystyle\norm{f}_{C^{\alpha}(K)}\coloneqq\sup_{x\in
K}\absolutevalue{f(x)}+[f]_{\alpha,K}.$

######  Lemma A.3.

Assume that $\mathcal{H}$ is an RKHS over a compact set
$\mathcal{X}\subseteq\mathbb{R}^{d}$ associated with a kernel $k\in
C^{\alpha}(\mathcal{X}\times\mathcal{X})$ for $\alpha\in(0,1]$. Then, we have
$\mathcal{H}\subseteq C^{\alpha/2}(\mathcal{X})$ and

$\displaystyle[f]_{\alpha/2,\mathcal{X}}\leq\sqrt{2[k]_{\alpha,\mathcal{X}\times\mathcal{X}}}\norm{f}_{\mathcal{H}}.$
(31)

###### Proof.

By the properties of RKHS, we have

$\displaystyle f(x)-f(y)$
$\displaystyle=\left\langle{f,k(x,\cdot)}\right\rangle_{\mathcal{H}}-\left\langle{f,k(y,\cdot)}\right\rangle_{\mathcal{H}}=\left\langle{f,k(x,\cdot)-k(b,\cdot)}\right\rangle_{\mathcal{H}}\leq\norm{f}_{\mathcal{H}}\norm{k(x,\cdot)-k(y,\cdot)}_{\mathcal{H}}.$

Moreover,

$\displaystyle\|k(x,\cdot)-k(y,\cdot)\|_{\mathcal{H}}^{2}=k(x,x)+k(y,y)-2k(x,y)$
$\displaystyle\leq$
$\displaystyle\absolutevalue{k(x,x)-k(x,y)}+\absolutevalue{k(y,y)-k(x,y)}\leq
2[k]_{\alpha,\mathcal{X}\times\mathcal{X}}\absolutevalue{x-y}^{\alpha}.$

Therefore, we obtain

$\displaystyle\absolutevalue{f(x)-f(y)}\leq\norm{f}_{\mathcal{H}}\sqrt{2[k]_{\alpha,\mathcal{X}\times\mathcal{X}}}\absolutevalue{x-y}^{\alpha/2}.$

∎

###  A.2 Sample subspace and semi-norm

It is convenient to introduce the following commonly used notations

$\displaystyle\mathbb{K}(x,X)\coloneqq\left(k(x,x_{1}),\dots,k(x,x_{n})\right),\quad\mathbb{K}(X,x)\coloneqq\mathbb{K}(x,X)^{\prime},$
(32)
$\displaystyle\mathbb{K}(X,X)\coloneqq\big{(}k(x_{i},x_{j})\big{)}_{i,j},$
(33) $\displaystyle K\coloneqq\frac{1}{n}\mathbb{K}(X,X),$ (34)

where $K$ is known as the (normalized) kernel matrix. For a function $f$, we
also denote by

$\displaystyle f[X]=(f(x_{1}),\dots,f(x_{n}))^{\prime}$

the column vector of function values.

######  Definition A.4.

Given $\\{x_{1},...,x_{n}\\}\subset\mathcal{X}$, the subspace

$\displaystyle\mathcal{H}_{n}\coloneqq\operatorname{span}\left\\{k(x_{1},\cdot),\dots,k(x_{n},\cdot)\right\\}\subset\mathcal{H}.$
(35)

of $\mathcal{H}$ is called the sample subspace. We also call the operator
$Q_{n}:\mathcal{H}\to\mathcal{H}_{n}$ given by

$\displaystyle Q_{n}(f)(x)=\mathbb{K}(x,X)\mathbb{K}(X,X)^{-1}f(X).$ (36)

the sample projection map.

Recall that we have defined the operator
$T_{X}=\frac{1}{n}\sum_{i}K_{x_{i}}K_{x_{i}}^{*}$ in (19). It is clear that
$T_{X}=T_{X}Q_{n}$ and $\operatorname{Ran}T_{X}=\mathcal{H}_{n}$. Under the
natural base $\\{k(x_{1},\cdot),\dots,k(x_{1},\cdot)\\}$ of $\mathcal{H}_{n}$,
we have

$\displaystyle
T_{X}k(x_{i},\cdot)=\frac{1}{n}\sum_{j=1}^{n}K_{x_{j}}k(x_{i},x_{j})=\frac{1}{n}k(x_{i},x_{j})k(x_{j},\cdot),$

i.e., $T_{X}$ can be represented by the matrix $K$ under the natural basis. We
can use

$\displaystyle T_{X}\mathbb{K}(X,\cdot)=K\mathbb{K}(X,\cdot)$ (37)

to express this result. Furthermore, for any continuous function $\varphi(x)$,
the operator $\varphi(T_{X})$ satisfies that

$\displaystyle\varphi(T_{X})\mathbb{K}(X,\cdot)=\varphi(K)\mathbb{K}(X,\cdot).$
(38)

In particlar, we have

$\displaystyle(\varphi(T_{X})f)[X]=\varphi(K)f[X].$ (39)

Since $g_{Z}\in\mathcal{H}_{n}$ ( see (20)). Therefore, we know that

$\displaystyle\hat{f}_{\lambda}^{\mathrm{KRR}}(x)=\frac{1}{n}\mathbb{K}(x,X)\left(K+\lambda\right)^{-1}\mathbf{y}.$

####  A.2.1 Semi-inner products in the sample space

We consider the following sample semi-inner products:

$\displaystyle\left\langle{f,g}\right\rangle_{L^{2},n}$
$\displaystyle\coloneqq\frac{1}{n}\sum_{i=1}^{n}f(x_{i})g(x_{i})=\frac{1}{n}f[X]^{\prime}g[X],$
(40) $\displaystyle\left\langle{f,g}\right\rangle_{\mathcal{H},n}$
$\displaystyle\coloneqq\left\langle{Q_{n}f,Q_{n}g}\right\rangle_{\mathcal{H}}.$
(41)

######  Lemma A.5.

$\displaystyle\left\langle{f,g}\right\rangle_{\mathcal{H},n}=\frac{1}{n}f[X]^{\prime}K^{-1}g[X]$
(42)

###### Proof.

By the definition (36) of $Q_{n}$ , we have

$\displaystyle\left\langle{f,g}\right\rangle_{\mathcal{H},n}$
$\displaystyle=\left\langle{\mathbb{K}(\cdot,X)\mathbb{K}(X,X)^{-1}f[X],\mathbb{K}(\cdot,X)\mathbb{K}(X,X)^{-1}g[X]}\right\rangle_{\mathcal{H}}$
$\displaystyle=\left(\mathbb{K}(X,X)^{-1}f[X]\right)^{\prime}\mathbb{K}(X,X)\left(\mathbb{K}(X,X)^{-1}g[X]\right)$
$\displaystyle=f[X]^{\prime}\mathbb{K}(X,X)^{-1}g[X]=\frac{1}{n}f[X]^{\prime}K^{-1}g[X].$

∎

######  Proposition A.6.

For $f,g\in\mathcal{H}$, we have

$\displaystyle\left\langle{f,g}\right\rangle_{L^{2},n}$
$\displaystyle=\left\langle{T_{X}f,g}\right\rangle_{\mathcal{H}}=\left\langle{T_{X}^{1/2}f,T_{X}^{1/2}g}\right\rangle,$
(43) $\displaystyle\norm{f}_{L^{2},n}$
$\displaystyle=\norm{T_{X}^{1/2}f}_{\mathcal{H}}.$

###### Proof.

Since $\operatorname{Ran}T_{X}=\mathcal{H}_{n}$, we have

$\displaystyle\left\langle{T_{X}f,g}\right\rangle_{\mathcal{H}}=\left\langle{Q_{n}T_{X}f,Q_{n}g}\right\rangle=\left\langle{T_{X}f,g}\right\rangle_{\mathcal{H},n}.$

Since $(T_{X}f)[X]=Kf[X]$, we obtain

$\displaystyle\left\langle{T_{X}f,g}\right\rangle_{\mathcal{H},n}$
$\displaystyle=\frac{1}{n}[(T_{X}f)[X]]^{\prime}K^{-1}g[X]=\frac{1}{n}f[X]^{\prime}g[X]=\left\langle{f,g}\right\rangle_{L^{2},n}.$

∎

###  A.3 Covering number and entropy number

######  Definition A.7.

Let $(E,\norm{\cdot}_{E})$ be a normed space and $A\subset E$ be a subset. For
$\varepsilon>0$, we say $S\subseteq A$ is an $\varepsilon$-net of $A$ if
$\forall a\in A$, $\exists s\in S$ such that $\norm{a-s}\leq\varepsilon$.
Moreover, we define the $\varepsilon$-covering number of $A$ to be

$\displaystyle\mathcal{N}(A,\norm{\cdot}_{E},\varepsilon)$
$\displaystyle\coloneqq\inf\left\\{n\in\mathbb{N}^{*}:\exists
s_{1},\dots,s_{n}\in A\text{ such that
}A\subseteq\bigcup_{i=1}^{n}B_{E}(s_{i},\varepsilon)\right\\},$ (44)
$\displaystyle=\inf\left\\{\absolutevalue{S}:S\text{ is an $\varepsilon$-net
of }A\right\\}$ (45)

where $B_{E}(x_{0},\varepsilon)\coloneqq\left\\{x\in
E\mid\norm{x_{0}-x}_{E}\leq\varepsilon\right\\}$ be the closed ball centered
at $x_{0}\in E$ with radius $\varepsilon$.

The following result about the covering number of a bounded set in the
Euclidean space is well-known, see, e.g., Vershynin (2018, Section 4.2).

######  Lemma A.8.

Let $A\subseteq\mathbb{R}^{d}$ be a bounded set. Then there exists a constant
$C$ (depending on $A$) such that

$\displaystyle\mathcal{N}\left(A,\norm{\cdot}_{\mathbb{R}^{d}},\varepsilon\right)\leq
C\varepsilon^{-d}.$ (46)

##  Appendix B Proof of the main theorem

###  B.1 Bias-variance decomposition

The first step of the proof is the traditional bias-variance decomposition.
Recalling (21), we have

$\displaystyle\hat{f}_{\lambda}^{\mathrm{KRR}}$
$\displaystyle=\frac{1}{n}(T_{X}+\lambda)^{-1}\sum_{i=1}^{n}K_{x_{i}}y_{i}=\frac{1}{n}(T_{X}+\lambda)^{-1}\sum_{i=1}^{n}K_{x_{i}}(K_{x_{i}}^{*}f^{*}+\epsilon_{i})$
$\displaystyle=(T_{X}+\lambda)^{-1}T_{X}f^{*}+\frac{1}{n}\sum_{i=1}^{n}(T_{X}+\lambda)^{-1}K_{x_{i}}\epsilon_{i},$

so that

$\displaystyle\hat{f}_{\lambda}^{\mathrm{KRR}}-f^{*}=-\lambda(T_{X}+\lambda)^{-1}f^{*}+\frac{1}{n}\sum_{i=1}^{n}(T_{X}+\lambda)^{-1}K_{x_{i}}\epsilon_{i}.$

Taking expectation over the noise $\epsilon$ conditioned on $X$, since
$\varepsilon|x$ are independent noise with mean 0 and variance
$\sigma_{x}^{2}$, we have

$\displaystyle\mathbb{E}\left(\norm{\hat{f}_{\lambda}^{\mathrm{KRR}}-f^{*}}^{2}_{L^{2}}\;\Big{|}\;X\right)=\mathbf{Bias}^{2}+\mathbf{Var},$
(47)

where

$\displaystyle\mathbf{Bias}^{2}\coloneqq\lambda^{2}\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}^{2},\quad\mathbf{Var}\coloneqq\frac{1}{n^{2}}\sum_{i=1}^{n}\sigma_{x_{i}}^{2}\norm{(T_{X}+\lambda)^{-1}k(x_{i},\cdot)}^{2}_{L^{2}}.$
(48)

###  B.2 Lower bound for the bias term

######  Proposition B.1.

Suppose that $f^{*}\in[\mathcal{H}]^{0}$ is a non-zero function. There is some
$c>0$ independent of $\lambda$ such that

$\displaystyle\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}^{2}\geq c\mbox{\quad
as\quad}\lambda\to 0.$ (49)

###### Proof.

Since $f^{*}\in[\mathcal{H}]^{0}$ and it is non-zero, we may assume that

$\displaystyle f^{*}=\sum_{i=1}^{\infty}a_{i}e_{i}.$

Because $\lambda\to 0$, we have

$\displaystyle\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}^{2}=\sum_{i=1}^{\infty}\left(\frac{a_{i}}{\lambda_{i}+\lambda}\right)^{2}\geq\sum_{i=1}^{\infty}\left(\frac{a_{i}}{\lambda_{i}+1}\right)^{2}>0\quad\text{(Since
$f^{*}\neq 0$)}.$

∎

######  Theorem B.2 (Lower bound of the Bias term).

Suppose that $\alpha\geq 2$, $f^{*}\in[\mathcal{H}]^{\alpha}$ is a non-zero
function and $\lambda=\lambda(n)=\Omega(n^{-(1-\varepsilon)})$ for some
$\varepsilon\in(0,1)$. Then, for any $\delta>0$, there exists an integer
$n_{0}$ such that for any $n>n_{0}$, we have that

$\displaystyle\mathbf{Bias}^{2}\geq c\lambda^{2},$ (50)

holds with probability at least $1-\delta$ where $c>0$ is a constant
independent of $\lambda$. As a consequence,
$\mathbf{Bias}^{2}=\Omega_{\mathbb{P}}(\lambda^{2})$.

###### Proof.

Corollary C.8 together with Proposition B.1 yields that with probability at
least $1-\delta$ we have

$\displaystyle\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}^{2}$
$\displaystyle\geq\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}^{2}-O(n^{-q})\left(\ln\frac{4}{\delta}\right)^{2}$
$\displaystyle\geq c-O(n^{-q})\left(\ln\frac{4}{\delta}\right)^{2}$

for some $q>0$. Therefore, we get

$\displaystyle\mathbf{Bias}^{2}=\lambda^{2}\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}^{2}\geq
c\lambda^{2}\left(1-O(n^{-q})\left(\ln\frac{4}{\delta}\right)^{2}\right)$
$\displaystyle\geq\frac{c}{2}\lambda^{2}$

when $n$ is sufficiently large. ∎

###  B.3 Lower bound for the variance term

For the variance term, Assumption 2 yields that
$\sigma_{x_{i}}^{2}\geq\bar{\sigma}^{2}$ almost surely. Recalling the
discussion of sample subspaces in Section A.2, we have

$\displaystyle\mathbf{Var}$
$\displaystyle\geq\frac{\bar{\sigma}^{2}}{n^{2}}\sum_{i=1}^{n}\norm{(T_{X}+\lambda)^{-1}k(x_{i},\cdot)}^{2}_{L^{2}}$
(51)
$\displaystyle=\frac{\bar{\sigma}^{2}}{n^{2}}\norm{(T_{X}+\lambda)^{-1}\mathbb{K}(X,\cdot)}_{L^{2}(\mathcal{X},\differential\mu;\mathbb{R}^{n})}^{2}$
(By (38))
$\displaystyle=\frac{\bar{\sigma}^{2}}{n^{2}}\norm{(K+\lambda)^{-1}\mathbb{K}(X,\cdot)}_{L^{2}(\mathcal{X},\differential\mu;\mathbb{R}^{n})}^{2}$
$\displaystyle=\frac{\bar{\sigma}^{2}}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)(K+\lambda)^{-2}\mathbb{K}(X,x)\differential\mu(x).$

Let us denote $h_{x}=k(x,\cdot)$. Then by definition it is obvious that
$h_{x}[X]=\mathbb{K}(X,x)$. From (39), we find that

$\displaystyle\left((T_{X}+\lambda)^{-1}h_{x}\right)[X]=(K+\lambda)^{-1}h_{x}[X]=(K+\lambda)^{-1}\mathbb{K}(X,x),$

so we obtain

$\displaystyle\frac{1}{n}\mathbb{K}(x,X)(K+\lambda)^{-2}\mathbb{K}(X,x)$
$\displaystyle=\frac{1}{n}\norm{(K+\lambda)^{-1}\mathbb{K}(X,x)}_{\mathbb{R}^{n}}^{2}$
$\displaystyle=\frac{1}{n}\norm{\left((T_{X}+\lambda)^{-1}h_{x}\right)[X]}_{\mathbb{R}^{n}}^{2}$
$\displaystyle=\norm{(T_{X}+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}.$

from the definition (40) of sample semi-inner product. Consequently, we get

$\displaystyle\mathbf{Var}\geq\frac{\bar{\sigma}^{2}}{n}\int_{\mathcal{X}}\norm{(T_{X}+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}\differential\mu(x).$
(52)

Combining with some concentration results, we can obtain the following
theorem.

######  Theorem B.3.

Assume that Assumptions 1 and 2 and condition (A) (e.g., the eigenvalue decay
rate (9)) hold. Suppose that $\lambda=\lambda(n)\to 0$ satisfying that
$\lambda=\Omega\left(n^{-\frac{1}{2}+p}\right)$ for some $p\in(0,1/2)$. Then,
for any $\delta>0$, when $n$ is sufficiently large, the following holds with
probability at least $1-\delta$:

$\displaystyle\mathbf{Var}\geq\frac{c\lambda^{-\beta}}{n}.$ (53)

As a consequence, we have
$\mathbf{Var}=\Omega_{\mathbb{P}}\left(\frac{\lambda^{-\beta}}{n}\right)$.

###### Proof.

First, we assert that the approximation

$\displaystyle\norm{(T_{X}+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}\geq\frac{1}{2}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}-\left(o(1)\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}+o(1)\ln\frac{4}{\delta}\right)\ln\frac{4}{\delta}$
(54)

holds with probability at least $1-\delta$. Then, plugging the approximation
into (52) gives

$\displaystyle\mathbf{Var}$
$\displaystyle\geq\frac{\bar{\sigma}^{2}}{n}\int_{\mathcal{X}}\norm{(T_{X}+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}\differential\mu(x)$
$\displaystyle\geq\frac{\bar{\sigma}^{2}}{2n}\int_{\mathcal{X}}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}\differential\mu(x)-\frac{o(1)}{n}\int_{\mathcal{X}}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}\differential\mu(x)-\frac{o(1)}{n}\left(\ln\frac{4}{\delta}\right)^{2}.$

For the two integral terms, applying Mercer’s theorem, we get

$\displaystyle\int_{\mathcal{X}}$
$\displaystyle\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}\differential\mu(x)=\int_{\mathcal{X}}\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda+\lambda_{i}}\right)^{2}e_{i}(x)^{2}\differential\mu(x)$
(55)
$\displaystyle=\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda+\lambda_{i}}\right)^{2}=\mathcal{N}_{2}(\lambda)\geq
c\lambda^{-\beta},$

and

$\displaystyle\int_{\mathcal{X}}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}\differential\mu(x)$
$\displaystyle\leq\left(\int_{\mathcal{X}}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}\differential\mu(x)\right)^{1/2}$
$\displaystyle=\left(\mathcal{N}_{2}(\lambda)\right)^{1/2}\leq
C\lambda^{-\beta/2},$

where the estimation of $\mathcal{N}_{2}(\lambda)$ comes from Proposition D.1.
Therefore, we obtain that

$\displaystyle\mathbf{Var}$
$\displaystyle\geq\frac{c\bar{\sigma}^{2}}{2n}\lambda^{-\beta}-\frac{o(\lambda^{-\beta/2})}{n}\ln\frac{4}{\delta}-\frac{o(1)}{n}\left(\ln\frac{4}{\delta}\right)^{2}\geq\frac{c\bar{\sigma}^{2}}{4n}\lambda^{-\beta}$

as $n$ goes to infinity.

It remains to establish the approximation (54). Lemma C.11 and Lemma C.12
yield that

$\displaystyle\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}\leq\frac{3}{2}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}+o(1)\ln\frac{4}{\delta},$
(56)
$\displaystyle\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}\geq\frac{1}{2}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}-o(1)\ln\frac{4}{\delta},$
(57)
$\displaystyle\absolutevalue{\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1}h_{x}}_{\mathcal{H}}-\norm{T_{X}^{1/2}(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}}\leq
o(1)\ln\frac{4}{\delta}$ (58)

with probability at least $1-\delta$. Consequently, from (43) and (56), we get

$\displaystyle\norm{T_{X}^{1/2}(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}$
$\displaystyle=\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}$ $\displaystyle\leq
C\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}+o(1)\left(\ln\frac{4}{\delta}\right)^{1/2}.$

Combining it with (58), we find that

$\displaystyle\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1}h_{x}}_{\mathcal{H}}+\norm{T_{X}^{1/2}(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}$
$\displaystyle\leq
2\norm{T_{X}^{1/2}(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}+o(1)\ln\frac{4}{\delta}$
$\displaystyle\leq
C\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}+o(1)\ln\frac{4}{\delta},$

which gives the approximation of the squared norm

$\absolutevalue{\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1}h_{x}}_{\mathcal{H}}^{2}-\norm{T_{X}^{1/2}(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}^{2}}\\\
\leq
o(1)\ln\frac{4}{\delta}\cdot\left(\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}+o(1)\ln\frac{4}{\delta}\right).$
(59)

Finally, combining (59) and (57) yields

$\displaystyle\quad\norm{(T_{X}+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}=\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1}h_{x}}_{\mathcal{H}}^{2}$
$\displaystyle\geq\norm{T_{X}^{1/2}(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}^{2}-o(1)\ln\frac{4}{\delta}\cdot\left(\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}+o(1)\ln\frac{4}{\delta}\right)$
$\displaystyle=\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}-o(1)\ln\frac{4}{\delta}\cdot\left(\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}+o(1)\ln\frac{4}{\delta}\right)$
$\displaystyle\geq\frac{1}{2}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}-o(1)\ln\frac{4}{\delta}-o(1)\ln\frac{4}{\delta}\cdot\left(\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}+o(1)\ln\frac{4}{\delta}\right)$
$\displaystyle=\frac{1}{2}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}-\left(o(1)\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}+o(1)\ln\frac{4}{\delta}\right)\ln\frac{4}{\delta}.$

∎

###  B.4 Proof of Theorem 3.1

Let $\lambda=\lambda(n)$ be an arbitrary choice of regularization parameter
satisfying that $\lambda(n)\to 0$. We consider the truncation

$\displaystyle\bar{\lambda}\coloneqq\max\left(\lambda,n^{-\frac{1}{2+\beta}}\right),$
(60)

which satisfies that $\bar{\lambda}=\Omega\left(n^{-\frac{1}{2+\beta}}\right)$
and $\bar{\lambda}\to 0$. Applying Theorem B.2 and Theorem B.3 to
$\bar{\lambda}$, we obtain that

$\displaystyle\mathbf{Bias}^{2}(\bar{\lambda})\geq
c_{1}\bar{\lambda}^{2},\quad\quad\mathbf{Var}(\bar{\lambda})\geq\frac{c_{2}\bar{\lambda}^{-\beta}}{n}$

with probability at least $1-\delta$ for sufficiently large $n$, where we use
$\mathbf{Bias}^{2}(\bar{\lambda})$ and $\mathbf{Var}(\bar{\lambda})$ to
highlight the choice of regularization parameter. Let us consider two cases.

##### Case 1: $\lambda>n^{-\frac{1}{2+\beta}}$

In this case $\lambda=\bar{\lambda}$, so

$\displaystyle\mathbb{E}\left(\norm{\hat{f}_{\lambda}^{\mathrm{KRR}}-f^{*}}^{2}\;\Big{|}\;X\right)$
$\displaystyle=\mathbf{Bias}^{2}(\lambda)+\mathbf{Var}(\lambda)$
$\displaystyle=\mathbf{Bias}^{2}(\bar{\lambda})+\mathbf{Var}(\bar{\lambda})$
$\displaystyle\geq
c_{1}\bar{\lambda}^{2}+\frac{c_{2}\bar{\lambda}^{-\beta}}{n}$
$\displaystyle\geq cn^{-\frac{2}{2+\beta}},$

where the last inequality is obtained by elementary inequalities in Lemma D.3
with $\frac{1}{p}=\frac{\beta}{2+\beta}$ and $\frac{1}{q}=\frac{2}{2+\beta}$.

##### Case 2: $\lambda\leq n^{-\frac{1}{2+\beta}}$

From the intermediate result (51) in proving the lower bound of the variance,
we know that

$\displaystyle\mathbf{Var}(\bar{\lambda})$
$\displaystyle\geq\frac{\bar{\sigma}^{2}}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)(K+\bar{\lambda})^{-2}\mathbb{K}(X,x)\differential\mu(x)\geq\frac{c_{2}\bar{\lambda}^{-\beta}}{n}$

and

$\displaystyle\mathbf{Var}(\lambda)\geq\frac{\bar{\sigma}^{2}}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)(K+\lambda)^{-2}\mathbb{K}(X,x)\differential\mu(x).$

Noticing that

$\displaystyle(K+\lambda_{1})^{-2}\succeq(K+\lambda_{2})^{-2}\mbox{\quad
if\quad}\lambda_{1}\leq\lambda_{2},$

where $\succeq$ represents the partial order induced by positive definite
matrices, we get

$\displaystyle\mathbf{Var}(\lambda)$
$\displaystyle\geq\frac{\bar{\sigma}^{2}}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)(K+\lambda)^{-2}\mathbb{K}(X,x)\differential\mu(x)$
$\displaystyle\geq\frac{\bar{\sigma}^{2}}{n^{2}}\int_{\mathcal{X}}\mathbb{K}(x,X)(K+\bar{\lambda})^{-2}\mathbb{K}(X,x)\differential\mu(x)$
$\displaystyle\geq\frac{c_{2}\bar{\lambda}^{-\beta}}{n}=c_{2}n^{-\frac{2}{2+\beta}},$

where we note that $\bar{\lambda}=n^{-\frac{1}{2+\beta}}$ in this case.
Consequently,

$\displaystyle\mathbb{E}\left(\norm{\hat{f}_{\lambda}^{\mathrm{KRR}}-f^{*}}^{2}\;\Big{|}\;X\right)\geq\mathbf{Var}(\lambda)\geq
c_{2}n^{-\frac{2}{2+\beta}}.$

The proof is completed by concluding two cases.

######  Remark B.4.

It is worth noticing that both the requirement that $f^{*}\neq 0$ and that the
noise is non-vanishing are necessary. If the former does not hold, choosing
$\lambda=\infty$ will yield the best estimator $\hat{f}=0$ with zero loss. If
the latter does not hold, the interpolation with $\lambda=0$ will be the best
estimator since there is no noise.

##  Appendix C Approximation Lemmas

In the following proofs, we always assume that $\delta\in(0,1)$. For
convenience, we use notations like $C,c$ to represent constants independent of
$n,\delta$, which may vary from appearance to appearance.

###  C.1 Concentration results

######  Lemma C.1.

Suppose that Assumption 1 holds. Let $f\in\mathcal{H}$ be given. We have

$\displaystyle\norm{(T_{X}-T)f}_{\mathcal{H}}\leq
2\kappa\left(\frac{2\norm{f}_{\infty}}{n}+\frac{\norm{f}_{L^{2}}}{\sqrt{n}}\right)\ln\frac{2}{\delta}$
(61)

holds with probability at least $1-\delta$.

###### Proof of Lemma C.1.

Let us define an $\mathcal{H}$-valued random variable $\xi_{x}=T_{x}f\coloneqq
K_{x}K_{x}^{*}f=f(x)k(x,\cdot)$. It is easy to verify that

$\displaystyle\mathbb{E}_{x\sim\mu}\xi_{x}=Tf,\mbox{\quad
and\quad}\frac{1}{n}\sum_{i=1}^{n}\xi_{x_{i}}=T_{X}f.$

Furthermore, we have

$\displaystyle\norm{\xi_{x}}_{\mathcal{H}}=\norm{f(x)k(x,\cdot)}_{\mathcal{H}}\leq\kappa\norm{f}_{\infty}$

and

$\displaystyle\mathbb{E}_{x\sim\mu}\norm{\xi_{x}}_{\mathcal{H}}^{2}=\mathbb{E}_{x\sim\mu}\norm{f(x)k(x,\cdot)}_{\mathcal{H}}^{2}=\mathbb{E}_{x\sim\mu}\absolutevalue{f(x)}^{2}\kappa^{2}$
$\displaystyle=\kappa^{2}\norm{f}_{L^{2}}^{2}.$

Therefore, the proof is concluded by applying Lemma D.6 with
$L=2\kappa\norm{f}_{\infty}$ and $\sigma=\kappa\norm{f}_{L^{2}}$. ∎

The following lemma shows that $(T_{X}+\lambda)^{-1}$ approximates to
$(T+\lambda)^{-1}$. It is similar to Lin & Cevher (2020, Lemma 19), but here
we do not require that $\lambda=n^{-\theta}$.

######  Lemma C.2.

Suppose that the Assumption 1 holds. If $n,\lambda$ satisfy

$\displaystyle\frac{\kappa^{2}}{\lambda
n}\ln\frac{4\mathcal{N}(\lambda)}{\delta}\leq\frac{1}{16},$ (62)

where $\mathcal{N}(\lambda)=\Tr(T+\lambda)^{-1}T$, then with probability at
least $1-\delta$ we have

$\displaystyle\norm{(T+\lambda)^{-\frac{1}{2}}(T_{X}+\lambda)^{\frac{1}{2}}}_{\mathscr{B}(\mathcal{H})}^{2},\norm{(T+\lambda)^{\frac{1}{2}}(T_{X}+\lambda)^{-\frac{1}{2}}}_{\mathscr{B}(\mathcal{H})}^{2}\leq
2.$ (63)

If Condition ${\bf(A)}$ ( i.e, the eigen-value decay condition (9) ) holds and
$\lambda=\Omega(n^{-(1-\varepsilon)})$ for some $\varepsilon\in(0,1)$, then
condition (62) holds for sufficiently large $n$.

To prove Lemma C.2, we first prove the following lemma, which is a modified
version of Lin & Cevher (2020, Lemma 16).

######  Lemma C.3.

Under Assumption 1 and condition (9), the following holds with probability at
least $1-\delta$:

$\displaystyle\norm{(T+\lambda)^{-\frac{1}{2}}(T-T_{X})(T+\lambda)^{-\frac{1}{2}}}\leq\frac{4\kappa^{2}B}{3\lambda
n}+\sqrt{\frac{2\kappa^{2}B}{\lambda n}},$ (64)

where

$\displaystyle
B=\ln\frac{4(\norm{T}+\lambda)\mathcal{N}(\lambda)}{\delta\norm{T}}.$

###### Proof.

We prove by using Lemma D.7. Let

$\displaystyle
A_{i}=A(x_{i})=(T+\lambda)^{-\frac{1}{2}}(T_{x_{i}}-T)(T+\lambda)^{-\frac{1}{2}}.$

Then, $\mathbb{E}A_{i}=0$ and

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}A_{i}=(T+\lambda)^{-\frac{1}{2}}(T_{x}-T)(T+\lambda)^{-\frac{1}{2}}.$

Calculation shows that

$\displaystyle\norm{A}\leq\norm{(T+\lambda)^{-\frac{1}{2}}}\left(\norm{T_{X}}+\norm{T}\right)\norm{(T+\lambda)^{-\frac{1}{2}}}\leq
2\kappa^{2}\lambda^{-1}=L.$

Using the fact that $\mathbb{E}(B-\mathbb{E}B)^{2}\preceq\mathbb{E}B^{2}$ for
self-adjoint operator $B$, we have

$\displaystyle\mathbb{E}A^{2}\preceq\mathbb{E}\left[(T+\lambda)^{-\frac{1}{2}}T_{x}(T+\lambda)^{-\frac{1}{2}}\right]^{2}.$

Moreover, noticing that $T\succeq 0$ and $0\preceq T_{x}\preceq\kappa^{2}$, we
have

$\displaystyle
A\preceq(T+\lambda)^{-\frac{1}{2}}\kappa^{2}(T+\lambda)^{-\frac{1}{2}}\preceq\kappa^{2}\lambda^{-1}$

and hence

$\displaystyle\mathbb{E}A^{2}\preceq\kappa^{2}\lambda^{-1}\mathbb{E}\left[(T+\lambda)^{-\frac{1}{2}}T_{x}(T+\lambda)^{-\frac{1}{2}}\right]=\kappa^{2}\lambda^{-1}T(T+\lambda)^{-1}\eqqcolon
V.$

We get

$\displaystyle\norm{V}$
$\displaystyle=\kappa^{2}\lambda^{-1}\norm{T(T+\lambda)^{-1}}=\kappa^{2}\lambda^{-1}\frac{\lambda_{1}}{\lambda+\lambda_{1}}=\kappa^{2}\lambda^{-1}\frac{\norm{T}}{\norm{T}+\lambda}$
$\displaystyle\Tr V$
$\displaystyle=\kappa^{2}\lambda^{-1}\Tr\left[T(T+\lambda)^{-1}\right]=\kappa^{2}\lambda^{-1}\mathcal{N}(\lambda),$

implying that

$\displaystyle B=\ln\frac{4\Tr
V}{\delta\norm{V}}=\ln\frac{4(\norm{T}+\lambda)\mathcal{N}(\lambda)}{\delta\norm{T}},$

and $\norm{V}\leq\kappa^{2}\lambda^{-1}$. ∎

Now we are ready to prove Lemma C.2.

###### Proof of Lemma C.2.

Let

$\displaystyle u=\frac{\kappa^{2}B}{\lambda n}=\frac{\kappa^{2}}{\lambda
n}\ln\frac{4(\norm{T}+\lambda)\mathcal{N}(\lambda)}{\delta\norm{T}}.$

By Lemma C.3, with probability at least $1-\delta$, we have

$\displaystyle
a=\norm{(T+\lambda)^{-\frac{1}{2}}(T-T_{X})(T+\lambda)^{-\frac{1}{2}}}\leq\frac{4}{3}u+\sqrt{2u}\leq\frac{1}{2},$

where the last inequality comes from (62), namely $u\leq\frac{1}{16}$.

Then, for the first term we have

$\displaystyle\norm{(T+\lambda)^{-\frac{1}{2}}(T_{X}+\lambda)^{\frac{1}{2}}}^{2}$
$\displaystyle=\norm{(T+\lambda)^{-1/2}(T_{X}+\lambda)(T+\lambda)^{-1/2}}$
$\displaystyle=\norm{(T+\lambda)^{-1}(T_{X}-T+T+\lambda)(T+\lambda)^{-1}}$
$\displaystyle=\norm{(T+\lambda)^{-1}(T_{X}-T)(T+\lambda)^{-1}+I}$
$\displaystyle\leq a+1\leq 2.$

Similarly, the second term can be bounded by

$\displaystyle\norm{(T+\lambda)^{\frac{1}{2}}(T_{X}+\lambda)^{-\frac{1}{2}}}^{2}$
$\displaystyle=\norm{(T+\lambda)^{1/2}(T_{X}+\lambda)^{-1}(T+\lambda)^{1/2}}$
$\displaystyle=\norm{\left[(T+\lambda)^{-1/2}(T_{X}+\lambda)(T+\lambda)^{-1/2}\right]^{-1}}$
$\displaystyle\leq(1-a)^{-1}\leq 2.$

Furthermore, if condition (9) holds and
$\lambda=\Omega(n^{-(1-\varepsilon)})$, then from Proposition D.1 we get

$\displaystyle\mathcal{N}(\lambda)\leq
C\lambda^{-\beta}=O\left(n^{\beta(1-\varepsilon)}\right).$

Therefore,

$\displaystyle\frac{\kappa^{2}}{\lambda
n}\ln\frac{4(\norm{T}+\lambda)\mathcal{N}(\lambda)}{\delta\norm{T}}\leq
Cn^{-\varepsilon}\left((1+\beta)(1-\varepsilon)\ln
n+\ln\frac{4}{\delta}+C\right)\to 0\mbox{\quad as\quad}n\to\infty.$

∎

###  C.2 Norm control of regularized functions

######  Proposition C.4.

Suppose that $f\in[\mathcal{H}]^{\alpha}$. Then, for any
$0\leq\gamma\leq\alpha$ such that $\alpha-\gamma\leq 2$, we have

$\displaystyle\norm{(T+\lambda)^{-1}f}_{[\mathcal{H}]^{\gamma}}\leq\lambda^{\frac{\alpha-\gamma}{2}-1}\norm{f}_{[\mathcal{H}]^{\alpha}}.$
(65)

###### Proof.

From the definition of $\norm{\cdot}_{[\mathcal{H}]^{\gamma}}$, we have
$f=T^{\alpha/2}f_{0}$ for some $f_{0}\in L^{2}$ such that
$\norm{f_{0}}_{L^{2}}=\norm{f}_{[\mathcal{H}]^{\alpha}}$, and

$\displaystyle\norm{(T+\lambda)^{-1}f}_{[\mathcal{H}]^{\gamma}}$
$\displaystyle=\norm{T^{-\gamma/2}(T+\lambda)^{-1}T^{\alpha/2}f_{0}}_{L^{2}}$
$\displaystyle=\norm{T^{\frac{\alpha-\gamma}{2}}(T+\lambda)^{-1}f_{0}}_{L^{2}}$
$\displaystyle\leq\norm{T^{\frac{\alpha-\gamma}{2}}(T+\lambda)^{-1}}_{\mathscr{B}(L^{2})}\norm{f_{0}}_{L^{2}}$
$\displaystyle\leq\lambda^{\frac{\alpha-\gamma}{2}-1}\norm{f}_{[\mathcal{H}]^{\alpha}},$

where the last inequality comes from applying Proposition D.2 to operator
calculus. ∎

The following special cases of Proposition C.4 are useful in our proofs. We
present them as corollaries. Notice that we have (A.1), so from estimations of
the RKHS-norm we can also get estimations of the sup-norm.

######  Corollary C.5.

For $f\in[\mathcal{H}]^{2}$, we have the following estimations:

$\displaystyle\norm{(T+\lambda)^{-1}f}_{L^{2}}$
$\displaystyle\leq\norm{f}_{[\mathcal{H}]^{2}},$
$\displaystyle\norm{(T+\lambda)^{-1}f}_{\infty}$
$\displaystyle\leq\kappa\lambda^{-1/2}\norm{f}_{[\mathcal{H}]^{2}}.$

###### Proof.

Applying Proposition C.4 with $\alpha=2$ and $\gamma=0,1$ respectively, we
obtain

$\displaystyle\norm{(T+\lambda)^{-1}f}_{L^{2}}$
$\displaystyle\leq\norm{f}_{[\mathcal{H}]^{2}},$
$\displaystyle\norm{(T+\lambda)^{-1}f}_{\infty}$
$\displaystyle\leq\kappa\norm{(T+\lambda)^{-1}f}_{\mathcal{H}}\leq\kappa\lambda^{-1/2}\norm{f}_{[\mathcal{H}]^{2}}.$

∎

Similarly, noticing that $k(x,\cdot)\in[\mathcal{H}]^{1}$, we also have the
following corollary controlling the norms of regularized kernel basis function
$(T+\lambda)^{-1}k(x,\cdot)$:

######  Corollary C.6.

We have the following estimations: $\forall x\in\mathcal{X}$,

$\displaystyle\norm{(T+\lambda)^{-1}k(x,\cdot)}_{L^{2}}$
$\displaystyle\leq\kappa\lambda^{-1/2},\quad\norm{(T+\lambda)^{-1}k(x,\cdot)}_{\mathcal{H}}\leq\kappa\lambda^{-1},$
(66) $\displaystyle\norm{(T+\lambda)^{-1}k(x,\cdot)}_{\infty}$
$\displaystyle\leq\kappa^{2}\lambda^{-1}.$

where $C$ is a positive constant.

###  C.3 Approximation of the regularized regression function

######  Lemma C.7.

Suppose that $f^{*}\in[\mathcal{H}]^{2}$. If
$\lambda=\lambda(n)=\Omega(n^{-(1-\varepsilon)})$ for some $\varepsilon>0$ and
$\lambda(n)\to 0$, then there exist some $q>0$ such that for sufficient large
$n$, the following holds with probability at least $1-\delta$:

$\displaystyle\absolutevalue{\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}-\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}}=O(n^{-q})\ln\frac{4}{\delta}.$
(67)

###### Proof.

By the triangle inequality and noticing that

$\displaystyle(T+\lambda)^{-1}-(T_{X}+\lambda)^{-1}=(T_{X}+\lambda)^{-1}(T_{X}-T)(T+\lambda)^{-1},$

we have

$\displaystyle\quad\absolutevalue{\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}-\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}}$
$\displaystyle\leq\norm{\left((T+\lambda)^{-1}-(T_{X}+\lambda)^{-1}\right)f^{*}}_{L^{2}}$
$\displaystyle=\norm{T^{1/2}(T_{X}+\lambda)^{-1}(T_{X}-T)(T+\lambda)^{-1}f^{*}}_{\mathcal{H}}$
$\displaystyle\leq\norm{T^{1/2}(T_{X}+\lambda)^{-1}}_{\mathscr{B}(\mathcal{H})}\norm{(T_{X}-T)(T+\lambda)^{-1}f^{*}}_{\mathcal{H}}.$
(68)

For the first term in (68), we have

$\displaystyle\norm{T^{1/2}(T_{X}+\lambda)^{-1}}_{\mathscr{B}(\mathcal{H})}$
$\displaystyle=\norm{T^{1/2}(T+\lambda)^{-1/2}(T+\lambda)^{1/2}(T_{X}+\lambda)^{-1}(T+\lambda)^{1/2}(T+\lambda)^{-1/2}}_{\mathscr{B}(\mathcal{H})}$
$\displaystyle\leq\norm{T^{1/2}(T+\lambda)^{-1/2}}_{\mathscr{B}(\mathcal{H})}\norm{(T+\lambda)^{1/2}(T_{X}+\lambda)^{-1}(T+\lambda)^{1/2}}_{\mathscr{B}(\mathcal{H})}\norm{(T+\lambda)^{-1/2}}_{\mathscr{B}(\mathcal{H})}$
(By Proposition D.2)
$\displaystyle\leq\lambda^{-1/2}\norm{(T+\lambda)^{1/2}(T_{X}+\lambda)^{-1}(T+\lambda)^{1/2}}_{\mathscr{B}(\mathcal{H})}.$

Since $\lambda=\Omega(n^{-(1-\varepsilon)})$, Lemma C.2 yields that

$\displaystyle\norm{(T+\lambda)^{1/2}(T_{X}+\lambda)^{-1}(T+\lambda)^{1/2}}_{\mathscr{B}(\mathcal{H})}\leq
4$

holds with probability at least $1-\delta/2$ for sufficient large $n$.
Therefore, we obtain the upper bound

$\displaystyle\norm{T^{1/2}(T_{X}+\lambda)^{-1}}_{\mathscr{B}(\mathcal{H})}\leq
4\lambda^{-1/2}.$ (69)

For the second term in (68), we apply Lemma C.1 with $f=(T+\lambda)^{-1}f^{*}$
and get that

$\displaystyle\norm{(T_{X}-T)(T+\lambda)^{-1}f^{*}}_{\mathcal{H}}\leq
2\kappa\left(\frac{2\norm{(T+\lambda)^{-1}f^{*}}_{\infty}}{n}+\frac{\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}}{\sqrt{n}}\right)\ln\frac{4}{\delta}$

holds with probability at least $1-\delta/2$. Plugging in the bounds from
Corollary C.5, we obtain that

$\displaystyle\norm{(T_{X}-T)(T+\lambda)^{-1}f^{*}}_{\mathcal{H}}\leq
C\left(\frac{\lambda^{-1/2}}{n}+\frac{1}{\sqrt{n}}\right)\ln\frac{4}{\delta}.$
(70)

Plugging (69) and (70) back into (68), we finally get

$\displaystyle\absolutevalue{\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}-\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}}\leq
C\left(\frac{\lambda^{-1}}{n}+\frac{\lambda^{-1/2}}{\sqrt{n}}\right)\ln\frac{4}{\delta}=O(n^{-q})\ln\frac{4}{\delta},$

where we use the condition $\lambda=\Omega(n^{-(1-\varepsilon)})$ in the last
equality. ∎

Combining the previous lemma with $L^{2}$-norm control of the regularized
regression function, we obtain the following corollary:

######  Corollary C.8.

Suppose that $f^{*}\in[\mathcal{H}]^{2}$. If
$\lambda=\lambda(n)=\Omega(n^{-(1-\varepsilon)})$ for some $\varepsilon>0$ and
$\lambda(n)\to 0$, for sufficient large $n$, the following holds with
probability at least $1-\delta$:

$\displaystyle\absolutevalue{\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}^{2}-\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}^{2}}=O(n^{-q})\left(\ln\frac{4}{\delta}\right)^{2}.$
(71)

###### Proof.

From Lemma C.7 and
$\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}\leq\norm{f^{*}}_{[\mathcal{H}]^{2}}$ in
Corollary C.5, we have

$\displaystyle\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}$
$\displaystyle\leq\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}+\absolutevalue{\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}-\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}}$
$\displaystyle\leq\norm{f^{*}}_{[\mathcal{H}]^{2}}+o(1)\ln\frac{4}{\delta}=O(1)\ln\frac{4}{\delta},$

and hence

$\displaystyle\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}+\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}=O(1)\ln\frac{4}{\delta}.$

Therefore, we get

$\displaystyle\quad\absolutevalue{\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}^{2}-\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}^{2}}$
$\displaystyle=\absolutevalue{\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}-\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}}\cdot\left(\norm{(T+\lambda)^{-1}f^{*}}_{L^{2}}+\norm{(T_{X}+\lambda)^{-1}f^{*}}_{L^{2}}\right)$
$\displaystyle=O(n^{-q})\ln\frac{4}{\delta}\cdot O(1)\ln\frac{4}{\delta}$
$\displaystyle=O(n^{-q})\left(\ln\frac{4}{\delta}\right)^{2}.$

∎

###  C.4 Approximation of the regularized kernel basis function

The following proposition about estimating the $L^{2}$ norm with empirical
norms is a corollary of Lemma D.5.

######  Proposition C.9.

Let $\mu$ be a probability measure on $\mathcal{X}$, $f\in
L^{2}(\mathcal{X},\differential\mu)$ and $\norm{f}_{\infty}\leq M$. Suppose we
have $x_{1},\dots,x_{n}$ sampled i.i.d. from $\mu$. Then, for any $\alpha>0$,
the following holds with probability at least $1-\delta$:

$\displaystyle\absolutevalue{\norm{f}_{L^{2},n}^{2}-\norm{f}_{L^{2}}^{2}}\leq\alpha
M^{2}\norm{f}_{L^{2}}^{2}+\frac{3+4\alpha M^{2}}{6\alpha
n}\ln\frac{2}{\delta}.$

By choosing $\alpha=\frac{1}{2M^{2}}$, we have

$\displaystyle\frac{1}{2}\norm{f}_{L^{2}}^{2}-\frac{5M^{2}}{3n}\ln\frac{2}{\delta}\leq\norm{f}_{L^{2},n}^{2}\leq\frac{3}{2}\norm{f}_{L^{2}}^{2}+\frac{5M^{2}}{3n}\ln\frac{2}{\delta}.$
(72)

###### Proof.

Defining $\xi_{i}=f(x_{i})^{2}$, we have

$\displaystyle\mathbb{E}\xi_{i}$ $\displaystyle=\norm{f}_{L^{2}}^{2},$
$\displaystyle\mathbb{E}\xi_{i}^{2}$
$\displaystyle=\mathbb{E}_{x\sim\mu}f(x)^{4}\leq\norm{f}_{\infty}^{2}\norm{f}_{L^{2}}^{2}.$

Therefore, applying Lemma D.5, we get

$\displaystyle\absolutevalue{\norm{f}_{L^{2},n}^{2}-\norm{f}_{L^{2}}^{2}}\leq\alpha\norm{f}_{\infty}^{2}\norm{f}_{L^{2}}^{2}+\frac{3+4\alpha
M^{2}}{6\alpha n}\ln\frac{2}{\delta}.$

∎

We establish the following lemma about covering numbers of the regularized
kernel basis functions. For simplicity, let us denote
$h_{x}=k(x,\cdot)\in\mathcal{H}$ and

$\displaystyle\mathcal{K}_{\lambda}\coloneqq\left\\{(T+\lambda)^{-1}h_{x}\right\\}_{x\in\mathcal{X}}.$
(73)

######  Lemma C.10.

Assuming that $\mathcal{X}\subseteq\mathbb{R}^{d}$ is bounded and $k\in
C^{s}(\mathcal{X}\times\mathcal{X})$ for some $s\in(0,1]$. Then, we have

$\displaystyle\mathcal{N}\left(\mathcal{K}_{\lambda},\norm{\cdot}_{\infty},\varepsilon\right)$
$\displaystyle\leq C\left(\lambda\varepsilon\right)^{-\frac{2d}{s}},$ (74)

where $C$ is a positive constant not depending on $\lambda$ or $\varepsilon$.

###### Proof.

We first prove (74). By Mercer’s theorem, we have

$\displaystyle(T+\lambda)^{-1}h_{a}=\sum_{i\in
N}\frac{\lambda_{i}}{\lambda+\lambda_{i}}e_{i}(a)e_{i},$

and thus

$\displaystyle\left[(T+\lambda)^{-1}h_{a}\right](x)$ $\displaystyle=\sum_{i\in
N}\frac{\lambda_{i}}{\lambda+\lambda_{i}}e_{i}(a)e_{i}(x)$
$\displaystyle=\left[(T+\lambda)^{-1}h_{x}\right](a).$

Therefore,

$\displaystyle\norm{(T+\lambda)^{-1}h_{a}-(T+\lambda)^{-1}h_{b}}_{\infty}$
$\displaystyle=\sup_{x\in\mathcal{X}}\absolutevalue{\left[(T+\lambda)^{-1}h_{a}\right](x)-\left[(T+\lambda)^{-1}h_{b}\right](x)}$
$\displaystyle=\sup_{x\in\mathcal{X}}\absolutevalue{\left[(T+\lambda)^{-1}h_{x}\right](a)-\left[(T+\lambda)^{-1}h_{x}\right](b)}.$

Since $k$ is Hölder-continuous, by Lemma A.3 we know that
$(T+\lambda)^{-1}h_{x}$ is also Hölder-continuous. Plugging the bound
$\norm{(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}\leq\kappa\lambda^{-1}$ obtained in
Corollary C.6 into (31), we get

$\displaystyle[(T+\lambda)^{-1}h_{x}]_{s/2,\mathcal{X}}\leq\sqrt{2[k]_{s,\mathcal{X}\times\mathcal{X}}}\norm{(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}\leq\kappa\sqrt{2[k]_{s,\mathcal{X}\times\mathcal{X}}}\lambda^{-1},$

which implies that

$\displaystyle\absolutevalue{\left[(T+\lambda)^{-1}h_{x}\right](a)-\left[(T+\lambda)^{-1}h_{x}\right](b)}\leq
C_{0}\lambda^{-1}\absolutevalue{a-b}^{s/2},$

where $C_{0}=\kappa\sqrt{2[k]_{s,\mathcal{X}\times\mathcal{X}}}$.
Consequently, we have

$\displaystyle\norm{(T+\lambda)^{-1}h_{a}-(T+\lambda)^{-1}h_{b}}_{\infty}\leq
C_{0}\lambda^{-1}\absolutevalue{a-b}^{s/2}.$ (75)

(75) yields that to find an $\varepsilon$-net of $\mathcal{K}_{\lambda}$ with
respect to $\norm{\cdot}_{\infty}$, we only need to find an
$\tilde{\varepsilon}$-net of $\mathcal{X}$ with respect to the Euclidean norm,
where
$\tilde{\varepsilon}=\left(\frac{\lambda\varepsilon}{C_{0}}\right)^{2/s}$.
Since the result of the covering number of the latter one is already known in
Lemma A.8, we finally obtain that

$\displaystyle\mathcal{N}\left(\mathcal{K}_{\lambda},\norm{\cdot}_{\infty},\varepsilon\right)\leq\mathcal{N}\left(\mathcal{X},\norm{\cdot}_{\mathbb{R}^{d}},\tilde{\varepsilon}\right)\leq
C\tilde{\varepsilon}^{-d}=C\left(\frac{\lambda\varepsilon}{C_{0}}\right)^{-\frac{2d}{s}}=\tilde{C}\left(\lambda\varepsilon\right)^{-\frac{2d}{s}}.$

∎

######  Lemma C.11.

Suppose that Assumption 1 holds. Assume that
$\lambda=\lambda(n)=\Omega(n^{-1/2+p})$ for some $p\in(0,1/2)$. Then, there
exists some $q>0$ such that for any $\delta>0$, the following holds with
probability at least $1-\delta$: $\forall x\in\mathcal{X}$,

$\displaystyle\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}$
$\displaystyle\leq\frac{3}{2}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}+O(n^{-q})\ln\frac{2}{\delta},$
$\displaystyle\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}$
$\displaystyle\geq\frac{1}{2}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}-O(n^{-q})\ln\frac{2}{\delta},$

where the constants in $O(n^{-q})$ do not depend on $x$.

###### Proof.

By Lemma C.10, we can find an $\varepsilon$-net
$\mathcal{F}\subseteq\mathcal{K}_{\lambda}\subseteq\mathcal{H}$ with respect
to sup-norm of $\mathcal{K}_{\lambda}$ such that

$\displaystyle\absolutevalue{\mathcal{F}}\leq
C\left(\lambda\varepsilon\right)^{-\frac{2d}{s}},$ (76)

where $\varepsilon=\varepsilon(n)$ will be determined later.

Applying Proposition C.9 to $\mathcal{F}$ with the
$\norm{\cdot}_{\infty}$-bound in Corollary C.6, with probability at least
$1-\delta$ we have

$\displaystyle\frac{1}{2}\norm{f}_{L^{2}}^{2}-\frac{C\lambda^{-2}}{n}\ln\frac{2\absolutevalue{\mathcal{F}}}{\delta}\leq\norm{f}_{L^{2},n}^{2}\leq\frac{3}{2}\norm{f}_{L^{2}}^{2}+\frac{C\lambda^{-2}}{n}\ln\frac{2\absolutevalue{\mathcal{F}}}{\delta},\quad\forall
f\in\mathcal{F}.$ (77)

Now, since $\mathcal{F}$ is an $\varepsilon$-net of $\mathcal{K}_{\lambda}$
with respect to $\norm{\cdot}_{\infty}$, for any $x\in\mathcal{X}$, there
exists some $f\in\mathcal{F}$ such that

$\displaystyle\norm{(T+\lambda)^{-1}h_{x}-f}_{\infty}\leq\varepsilon,$

which implies that

$\displaystyle\absolutevalue{\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}-\norm{f}_{L^{2}}}\leq\varepsilon,\quad\absolutevalue{\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}-\norm{f}_{L^{2},n}}\leq\varepsilon.$

Since $\norm{(T+\lambda)^{-1}h_{x}}_{\infty}\leq C\lambda^{-1}$ and
$a^{2}-b^{2}=(a-b)(2b+(a-b))$, we get

$\displaystyle\absolutevalue{\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}-\norm{f}_{L^{2}}^{2}}\leq
C\varepsilon\lambda^{-1},\quad\absolutevalue{\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}-\norm{f}_{L^{2},n}^{2}}\leq
C\varepsilon\lambda^{-1}.$ (78)

For the upper bound, we have

$\displaystyle\norm{(T+\lambda)^{-1}h_{x}}_{L^{2},n}^{2}$
$\displaystyle\leq\norm{f}_{L^{2},n}^{2}+C\varepsilon\lambda^{-1}\mbox{\quad(By
{(\ref{eq:L2NormEstimation})})\quad}$ (By (77))
$\displaystyle\leq\frac{3}{2}\norm{f}_{L^{2}}^{2}+\frac{C\lambda^{-2}}{n}\ln\frac{2\absolutevalue{\mathcal{F}}}{\delta}+C\varepsilon\lambda^{-1}$
(By (78) again)
$\displaystyle\leq\frac{3}{2}\norm{(T+\lambda)^{-1}h_{x}}_{L^{2}}^{2}+\frac{C\lambda^{-2}}{n}\ln\frac{2\absolutevalue{\mathcal{F}}}{\delta}+C\varepsilon\lambda^{-1}.$

Noticing that $\lambda=\Omega\left(n^{-1/2+p}\right)$ and (76), by choosing
$\varepsilon=n^{-1}$, it is easy to verify that

$\displaystyle\frac{C\lambda^{-2}}{n}\ln\frac{2\absolutevalue{\mathcal{F}}}{\delta}+C\varepsilon\lambda^{-1}$
$\displaystyle=O\left(n^{-2p}\right)\left(\ln\absolutevalue{\mathcal{F}}+\ln\frac{2}{\delta}\right)+O(n^{-\frac{1}{2}-p})$
$\displaystyle=O\left(n^{-2p}\right)\left(C_{1}\ln
n+C_{2}+\ln\frac{2}{\delta}\right)+O(n^{-\frac{1}{2}-p})$
$\displaystyle=O\left(n^{-q}\right)\ln\frac{2}{\delta}$

for some $q>0$. The lower bound follows similarly. ∎

######  Lemma C.12.

Suppose that Assumption 1 and Condition ${\bf(A)}$ ( i.e., the eigenvalue
decay rate (9) ) hold. Assume that
$\lambda=\Omega\left(n^{-\frac{1}{2}+p}\right)$ for some $p\in(0,1/2)$. Then,
there exists some $q>0$ such that

$\displaystyle\absolutevalue{\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1}h_{x}}_{\mathcal{H}}-\norm{T_{X}^{1/2}(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}}\leq
O(n^{-q})\ln\frac{2}{\delta},\quad\forall x\in\mathcal{X},$

with probability at least $1-\delta$, where the constant in $O(n^{-q})$ is
independent of $x$.

###### Proof.

We begin with

$\displaystyle\absolutevalue{\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1}h_{x}}_{\mathcal{H}}-\norm{T_{X}^{1/2}(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}}\leq\norm{T_{X}^{1/2}\left[(T_{X}+\lambda)^{-1}-(T+\lambda)^{-1}\right]h_{x}}_{\mathcal{H}}.$

Noticing that

$\displaystyle(T_{X}+\lambda)^{-1}-(T+\lambda)^{-1}=(T_{X}+\lambda)^{-1}\left(T-T_{X}\right)(T+\lambda)^{-1},$

we obtain

$\displaystyle\quad\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1}\left(T-T_{X}\right)(T+\lambda)^{-1}h_{x}}_{\mathcal{H}}$
$\displaystyle=\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1/2}\cdot(T_{X}+\lambda)^{-1/2}(T+\lambda)^{1/2}\cdot(T+\lambda)^{-1/2}\left(T-T_{X}\right)(T+\lambda)^{-1/2}\cdot(T+\lambda)^{-1/2}h_{x}}_{\mathcal{H}}$
$\displaystyle\leq\norm{T_{X}^{1/2}(T_{X}+\lambda)^{-1/2}}_{\mathscr{B}(\mathcal{H})}\cdot\norm{(T_{X}+\lambda)^{-1/2}(T+\lambda)^{1/2}}_{\mathscr{B}(\mathcal{H})}$
$\displaystyle\quad\cdot\norm{(T+\lambda)^{-1/2}\left(T-T_{X}\right)(T+\lambda)^{-1/2}}_{\mathscr{B}(\mathcal{H})}\cdot\norm{(T+\lambda)^{-1/2}h_{x}}_{\mathcal{H}}$
$\displaystyle\leq
1\cdot\sqrt{2}\cdot\lambda^{-1/2}\norm{(T+\lambda)^{-1/2}\left(T-T_{X}\right)(T+\lambda)^{-1/2}}_{\mathscr{B}(\mathcal{H})}.$

Now, Lemma C.3 gives that, with probability at least $1-\delta$,

$\displaystyle\norm{(T+\lambda)^{-1/2}\left(T-T_{X}\right)(T+\lambda)^{-1/2}}_{\mathscr{B}(\mathcal{H})}\leq\frac{4}{3}u+\sqrt{2u},$

where

$\displaystyle u=\frac{\kappa^{2}}{\lambda
n}\ln\frac{4(\norm{T}+\lambda)\mathcal{N}(\lambda)}{\delta\norm{T}}.$

Consequently, using $\lambda=\Omega\left(n^{-\frac{1}{2}+p}\right)$, we find
that $\lambda^{-1}u=O(n^{-q})$ for some $q$ and thus

$\displaystyle\lambda^{-1/2}\norm{(T+\lambda)^{-1/2}\left(T-T_{X}\right)(T+\lambda)^{-1/2}}_{\mathscr{B}(\mathcal{H})}=O(n^{-q/2}).$

Plugging this back yields the desired result.

∎

##  Appendix D Auxiliary Results

For any $p\geq 1$, let us introduce the $p$-effective dimension

$\displaystyle\mathcal{N}_{p}(\lambda)\coloneqq\Tr\left(T(T+\lambda)^{-1}\right)^{p}=\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda+\lambda_{i}}\right)^{p},\quad
p\geq 1.$

######  Proposition D.1.

If $\lambda_{i}\asymp i^{-1/\beta}$, we have

$\displaystyle\mathcal{N}_{p}(\lambda)\asymp\lambda^{-\beta}.$ (79)

###### Proof.

Since $c~{}i^{-1/\beta}\leq\lambda_{i}\leq Ci^{-1/\beta}$, we have

$\displaystyle\mathcal{N}_{p}(\lambda)$
$\displaystyle=\sum_{i=1}^{\infty}\left(\frac{\lambda_{i}}{\lambda_{i}+\lambda}\right)^{p}\leq\sum_{i=1}^{\infty}\left(\frac{Ci^{-1/\beta}}{Ci^{-1/\beta}+\lambda}\right)^{p}=\sum_{i=1}^{\infty}\left(\frac{C}{C+\lambda
i^{1/\beta}}\right)^{p}$
$\displaystyle\leq\int_{0}^{\infty}\left(\frac{C}{\lambda
x^{1/\beta}+C}\right)^{p}\differential
x=\lambda^{-\beta}\int_{0}^{\infty}\left(\frac{C}{y^{1/\beta}+C}\right)^{p}\differential
y\leq\tilde{C}\lambda^{-\beta}.$

for some constant $C$. Similarly, we hace

$\displaystyle\mathcal{N}_{p}(\lambda)\geq\tilde{C^{\prime}}\lambda^{-\beta}.$

for some constant $\tilde{C}^{\prime}$. ∎

######  Proposition D.2.

For $\lambda>0$ and $s\in[0,1]$, we have

$\displaystyle\sup_{t\geq 0}\frac{t^{s}}{t+\lambda}\leq\lambda^{s-1}.$

###### Proof.

It follows from the inequality $a^{s}\leq a+1$ for any $a\geq 0$ and
$s\in[0,1]$. ∎

######  Lemma D.3.

(Young’s inequality) Let $a,b>0$. For $p,q>1$ satisfying
$\frac{1}{p}+\frac{1}{q}=1$, we have

$\displaystyle ab\leq\frac{1}{p}a^{p}+\frac{1}{q}b^{q},$ (80)

or equivalently

$\displaystyle a+b\geq\sqrt[p]{p}\sqrt[q]{q}\cdot
a^{\frac{1}{p}}b^{\frac{1}{q}}.$ (81)

The following operator inequality(Fujii 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

$\displaystyle\norm{A^{s}B^{s}}_{\mathscr{B}(H)}\leq\norm{AB}_{\mathscr{B}(H)}^{s},\quad\forall
s\in[0,1].$ (82)

###  D.1 Concentration inequalities

The following concentration inequality is adopted from Caponnetto & Yao
(2010):

######  Lemma D.5.

Let $\xi_{1},\dots,\xi_{n}$ be $n$ i.i.d. bounded random variables such that
$\absolutevalue{\xi_{i}}\leq B$, $\mathbb{E}\xi_{i}=\mu$, and
$\mathbb{E}(\xi_{i}-\mu)^{2}\leq\sigma^{2}$. Then for any $\alpha>0$, any
$\delta\in(0,1)$, we have

$\displaystyle\absolutevalue{\frac{1}{n}\sum_{i=1}^{n}\xi_{i}-\mu}\leq\alpha\sigma^{2}+\frac{3+4\alpha
B}{6\alpha n}\ln\frac{2}{\delta}$ (83)

holds with probability at least $1-\delta$.

###### Proof of Lemma D.5.

The high probability form of bound in (83) is equivalent to the following
probability form:

$\displaystyle\mathbb{P}\left\\{\absolutevalue{\frac{1}{n}\sum_{i=1}^{n}\xi_{i}-\mu}\geq\alpha\sigma^{2}+\varepsilon\right\\}\leq
2\exp(-\frac{6n\alpha\varepsilon}{3+4\alpha B}),$

where $\varepsilon=\frac{3+4\alpha B}{6\alpha n}\ln\frac{2}{\delta}$. By
symmetry, it suffices to prove the following one-sided inequality:

$\displaystyle\mathbb{P}\left\\{\frac{1}{n}\sum_{i=1}^{n}\xi_{i}-\mu\geq\alpha\sigma^{2}+\varepsilon\right\\}\leq\exp(-\frac{6n\alpha\varepsilon}{3+4\alpha
B}).$

Taking exponent with some factor $s>0$, we obtain

$\displaystyle\mathbb{P}\left\\{\frac{1}{n}\sum_{i=1}^{n}\xi_{i}-\mu\geq\alpha\sigma^{2}+\varepsilon\right\\}$
$\displaystyle=\mathbb{P}\left\\{\exp(\frac{s}{n}\sum_{i=1}^{n}(\xi_{i}-\mu))\geq\exp(s(\alpha\sigma^{2}+\varepsilon))\right\\}$
(Markov Inequality)
$\displaystyle\leq\exp(-s(\alpha\sigma^{2}+\varepsilon))\mathbb{E}\exp(\frac{s}{n}\sum_{i=1}^{n}(\xi_{i}-\mu))$
(Independency)
$\displaystyle\leq\exp(-s(\alpha\sigma^{2}+\varepsilon))\prod_{i=1}^{n}\mathbb{E}\exp(\frac{s}{n}(\xi_{i}-\mu))$
(84)

Let $X_{i}=\xi_{i}-\mu$, $t=\frac{s}{n}$ and $M=2B$. As long as
$t<\frac{3}{M}$, we have

$\displaystyle\mathbb{E}\exp(\frac{s}{n}(\xi_{i}-\mu))$
$\displaystyle=\mathbb{E}\exp(tX_{i})=\sum_{k=0}^{\infty}\frac{t^{k}}{k!}\mathbb{E}X_{i}^{k}$
$\displaystyle\leq 1+\sum_{k=2}^{\infty}\frac{t^{k}}{k!}M^{k-2}\sigma^{2}$
$\displaystyle\leq
1+\frac{t^{2}\sigma^{2}}{2}\sum_{k=0}^{\infty}\left(\frac{Mt}{3}\right)^{k}$
$\displaystyle=1+\frac{3t^{2}\sigma^{2}}{6-2Mt}$
$\displaystyle\leq\exp(\frac{3t^{2}\sigma^{2}}{6-2Mt}).$

Therefore,

(84)
$\displaystyle\leq\exp(-s(\alpha\sigma^{2}+\varepsilon)+n\frac{3t^{2}\sigma^{2}}{6-2Mt})=\exp(-s(\alpha\sigma^{2}+\varepsilon)+\frac{3s^{2}\sigma^{2}}{6n-4Bs})$
$\displaystyle=\exp(-s\varepsilon+s\sigma^{2}\left(\alpha+\frac{3s}{6n-4Bs}\right))$

Solving $\alpha+\frac{3s}{6n-4Bs}=0$ and we get $s=\frac{6\alpha n}{3+4\alpha
B}$, which satisfies that $t=\frac{s}{n}<\frac{3}{M}$, hence we have

$\displaystyle\text{{(\ref{eq:p_ProbIneq1})}}\leq\exp(-\frac{6\alpha
n}{3+4\alpha B}\varepsilon)$

and the proof is complete. ∎

The following concentration inequality about vector-valued random variables is
commonly used in the literature, see, e.g. Caponnetto & De Vito (2007,
Proposition 2) and references therein.

######  Lemma D.6.

Let $H$ be a real separable Hilbert space. Let $\xi,\xi_{1},\dots,\xi_{n}$ be
i.i.d. random variables taking values in $H$. Assume that

$\displaystyle\mathbb{E}\norm{\xi-\mathbb{E}\xi}_{H}^{m}\leq\frac{1}{2}m!\sigma^{2}L^{m-2},\forall
m=2,3,\dots.$ (85)

Then for fixed $\delta\in(0,1)$, one has

$\displaystyle\mathbb{P}\left\\{\norm{\frac{1}{n}\sum_{i=1}^{n}\xi_{i}-\mathbb{E}\xi}_{H}\leq
2\left(\frac{L}{n}+\frac{\sigma}{\sqrt{n}}\right)\ln\frac{2}{\delta}\right\\}\geq
1-\delta.$ (86)

Particularly, a sufficient condition for (85) is

$\displaystyle\norm{\xi}_{H}\leq\frac{L}{2}\ \text{a.s., and}\
\mathbb{E}\norm{\xi}_{H}^{2}\leq\sigma^{2}.$

The following Bernstein type concentration inequality about self-adjoint
Hilbert-Schmidt 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 $A_{1},\dots,A_{n}$ be i.i.d. random
variables taking values of self-adjoint Hilbert-Schmidt operators such that
$\mathbb{E}A_{1}=0$, $\norm{A_{1}}\leq L$ almost surely for some $L>0$ and
$\mathbb{E}A_{1}^{2}\preceq V$ for some positive trace-class operator $V$.
Then, for any $\delta\in(0,1)$, with probability at least $1-\delta$ we have

$\displaystyle\norm{\frac{1}{n}\sum_{i=1}^{n}A_{i}}\leq\frac{2LB}{3n}+\sqrt{\frac{2\norm{V}B}{n}},\quad
B=\ln\frac{4\Tr V}{\delta\norm{V}}.$

##  Appendix E More Experiments

In this section we provide more results about the experiments.

###  E.1 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 $f^{*}$ as one of its
eigenfunctions. We also compare KRR with another regularization 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

$\displaystyle k(x,y)=\min(x,y)(1-\max(x,y))=\begin{cases}(1-x)y&\mbox{\quad
if\quad}x\geq y;\\\ (1-y)x&\mbox{\quad if\quad}x<y.\end{cases}$ (87)

The associated RKHS is

$\displaystyle H^{1}(0,1)\coloneqq\left\\{f:[0,1]\to\mathbb{R}\mid f\text{ is
A.C., }f(0)=f(1)=0,\ \int_{0}^{1}(f^{\prime}(x))^{2}\differential
x<\infty\right\\},$ (88)

with inner product
$\left\langle{f,g}\right\rangle_{H^{1}}\coloneqq\int_{0}^{1}f^{\prime}(t)g^{\prime}(t)\differential
t$. It is known that the eigen-system of this kernel is

$\displaystyle\lambda_{n}=\frac{1}{\pi^{2}n^{2}},\quad e_{n}=\sqrt{2}\sin(n\pi
x),\quad n=1,2,\dots,$ (89)

and hence $\beta=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 2 on page 2. The
results are generally the same as that of Section 4: GF and CUT methods are
similar and they both achieve better performances as $\alpha$ increases, while
KRR reaches its best performance at $\alpha=2$ with resulting max rate
approximately $0.8$, verifying our 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 are small. In
conclusion, the numerical results are supportive.

|  | $f^{*}=e_{1}$ | $f^{*}=e_{2}$ | $f^{*}=e_{3}$
---|---|---|---|---
Kernel | $\alpha$ | KRR | GF | CUT | KRR | GF | CUT | KRR | GF | CUT
$\min(x,y)$ | 1.5 | .73 | .72 | .73 | .76 | .74 | .73 | .75 | .74 | .75
2 | .76 | .76 | .78 | .80 | .78 | .79 | .78 | .78 | .81
2.5 | .69 | .80 | .81 | .73 | .81 | .82 | .69 | .82 | .83
3 | .58 | .82 | .84 | .62 | .83 | .83 | .59 | .84 | .85
| 3.5 | .49 | .84 | .86 | .54 | .85 | .88 | .51 | .86 | .90
Heavy-side step | 1.5 | .77 | .83 | .71 | .80 | .75 | .73 | .88 | .75 | .72
2 | .83 | .83 | .74 | .80 | .80 | .79 | .78 | .80 | .77
2.5 | .83 | .87 | .76 | .68 | .84 | .84 | .64 | .84 | .84
3 | .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
$\lambda=cn^{-\frac{1}{\alpha+\beta}}$ for various $\alpha$’s. Bold numbers
represent the max rate over different choices of $\lambda$.

###  E.2 Experiments on the sphere

In this part we conduct experiments beyond dimension 1. We consider some
inner-product kernels on the sphere
$\mathcal{X}=\mathbb{S}^{2}\subset\mathbb{R}^{3}$ with $\mu$ being the uniform
distribution. The reason is that in general it is hard to find an explicit
eigen-decomposition of a general kernel, where we can obtain explicit forms of
eigen-functions for inner-product kernels on $\mathbb{S}^{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 (2013) for a detailed
introduction. On $\mathbb{S}^{2}$, the spherical harmonics are often denoted
by $Y_{l}^{m},~{}l=0,1,2,\dots,~{}m=-l,\dots,l$, and $Y_{l}^{m}$ is a
homogeneous polynomial of order $l$. We pick some of them to be our underlying
truth function $f^{*}$, which are listed below:

$\displaystyle Y_{1}^{1}(x_{1},x_{2},x_{3})=\sqrt{\frac{3}{4\pi}}x_{1},\quad
Y_{2}^{-2}(x_{1},x_{2},x_{3})=\frac{1}{2}\sqrt{\frac{15}{\pi}}x_{1}x_{2},\quad$
$\displaystyle
Y_{3}^{2}(x_{1},x_{2},x_{3})=\frac{1}{4}\sqrt{\frac{105}{\pi}}(x_{1}^{2}-x_{2}^{2})x_{3}.$

In terms of kernels, we use the truncated power function
$k(x,y)=(1-\norm{x-y})_{+}^{p}$, where $a_{+}=\max(a,0)$. It is known that if
$p>\lfloor\frac{d}{2}\rfloor+1$, this kernel is positive definite on
$\mathbb{R}^{d}$ and thus positive definite on $\mathbb{S}^{d-1}$ (Wendland,
2004, Theorem 6.20). However, we do not know the eigen-decay rate $\beta$ for
these kernels.

In the following experiment, we basically follow the same procedure as
described in Section 4, except that we choose the regularization parameter by
$\lambda=n^{-\theta}$ with various $\theta$. The results are collected in
Table 3 on page 3. We also plot the error curves of one of the experiments in
Figure 2 on page 2. The results show that the convergences rates of KRR
increase and then decrease as $\theta$ 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.

|  | $f^{*}=Y_{1}^{1}$ | $f^{*}=Y_{2}^{-2}$ | $f^{*}=Y_{3}^{2}$
---|---|---|---|---
Kernel | $\theta$ | KRR | GF | KRR | GF | KRR | GF
$(1-\norm{x-y})_{+}^{3}$ | 0.6 | .50 | .49 | .49 | .38 | .49 | .49
0.4 | .77 | .70 | .71 | .65 | .70 | .69
0.3 | .71 | .80 | .73 | .74 | .73 | .78
0.2 | .45 | .96 | .49 | .83 | .50 | .89
$(1-\norm{x-y})_{+}^{4}$ | 0.6 | .40 | .37 | .39 | .38 | .39 | .37
0.4 | .70 | .65 | .65 | .65 | .65 | .65
0.3 | .77 | .76 | .74 | .74 | .74 | .75
0.2 | .56 | .90 | .64 | .83 | .65 | .84
Table 3: Convergence rates comparison between KRR and GF with
$\lambda=cn^{-\theta}$ for various $\theta$’s. Bold numbers represent the max
rate over different choices of $\lambda$.

Figure 2: Error decay curves of KRR and GF with kernel
$(1-\norm{x-y})_{+}^{4}$ on $\mathbb{S}^{2}$ and $f^{*}=Y_{1}^{1}$.