# On the Approximation of Kernel functions

Paul Dommel University of Technology, Chemnitz, Faculty of mathematics. 90126
Chemnitz, Germany Alois Pichler11footnotemark: 1
orcid.org/0000-0001-8876-2429. Contact<EMAIL_ADDRESS>0000-0001-8876-2429

###### Abstract

Various methods in statistical learning build on kernels considered in
reproducing kernel Hilbert spaces. In applications, the kernel is often
selected based on characteristics of the problem and the data. This kernel is
then employed to infer response variables at points, where no explanatory data
were observed.

The data considered here are located in compact sets in higher dimensions and
the paper addresses approximations of the kernel itself. The new approach
considers Taylor series approximations of radial kernel functions. For the
Gauss kernel on the unit cube, the paper establishes an upper bound of the
associated eigenfunctions, which grows only polynomially with respect to the
index. The novel approach substantiates smaller regularization parameters than
considered in the literature, overall leading to better approximations. This
improvement confirms low rank approximation methods such as the Nyström
method.

Keywords: statistical learning $\cdot$ kernel methods $\cdot$ reproducing
kernel Hilbert spaces $\cdot$ Nyström method

##  1 Introduction

This paper contributes to statistical methods building on reproducing kernel
Hilbert spaces. These methods have become popular in statistical learning, in
inference and in support vector machines due to the kernel trick. They
constitute powerful tools in different scientific areas such as geostatistics
(cf. Honarkhah and Caers 12), stochastic optimization (cf. Dommel and Pichler
8, Park et al. 13), digit recognition (cf. Schölkopf 16), computer vision (cf.
Zhang et al. 24) and bio informatics (cf. Schölkopf et al. 17).

The approach presented here approximates the kernel function by elements in
the range of the associated Hilbert–Schmidt integral operator. We choose these
elements so that its Taylor series expansion matches the initial coefficients.
The method applies for general radial kernels with variable bandwidth. Special
emphasize is given to the Gaussian kernel, which is of major importance in
practical applications.

Fundamental in statistical approximation is the regularization parameter.
Standard results suggest regularization parameters decreasing as
$\mathcal{O}(1/n)$, where $n$ is the sample size. This paper, in contrast,
justifies significantly smaller regularization parameters, often close to
machine precision. This leads to enhanced approximation quality.

An additional consequence of our approach, not sufficiently addressed in the
literature yet, are the magnitudes of the eigenfunctions of the related
Hilbert–Schmidt operator. We demonstrate that this magnitude grows only
polynomially in the index. Exploiting this crucial property, we present an
interpolation inequality, which allows bounding the uniform error by the much
weaker $L^{2}$-error.

The approximation of the kernel function builds on the function
$w_{m}^{x}(\cdot)$, smallest in $L^{2}([0,1])$-norm, satisfying the moment
constraints

$\int_{0}^{1}z^{\ell}w_{m}^{x}(z)\,dz=x^{\ell},\qquad\ell=0,\dots,m-1.$ (1.1)

We provide the explicit solution, which is a polynomial with coefficients
involving the Hilbert matrix.

The results have consequences for low rank kernel methods. For these methods,
they ensure a stable approximations quality by building only on few supporting
points. Prominent examples of these methods include the Nyström algorithms and
kernel principal component analysis.

#### Related literature.

Our results address the approximation of randomly located kernel functions.
This is of particular importance for low rank kernel methods, which build on
an approximation of the kernel matrix itself. The Nyström method, introduced
in Williams and Seeger [23], is a prominent example for this technique.
Drineas and Mahoney [9] analyze the error of the matrix approximation in the
Nyström method and relate it to the best approximating matrix, while Bach [1]
studies the precision of predictions directly. The excellent work of Rudi et
al. [14] relates the rank of the approximating matrix to the approximation of
kernel functions. The result is then employed to develop a low rank regression
approach, which is significantly cheaper in computations than kernel ridge
regression while maintaining stable prediction accuracy, cf. Rudi et al. [15].
Kernel principal component analysis builds on these results as well, cf.
Sterge and Sriperumbudur [22].

The approximation of kernel functions is the core research question of this
paper, for which we present new bounds. The second main result of this work
addresses the eigensystem of Mercer’s decomposition associated with the
Gaussian kernel. Shi et al. [19] address this issue for an unbounded domain,
building on the normal distribution as underlying design measure. The authors
provide an explicit expression of the eigenvalues and eigenfunctions by
involving the Hermite polynomials in an unbounded domain. In compact domains,
Diaconis et al. [5] consider the eigensystem for the Laplacian kernel.

The analysis of the divide and conquer approach relies on properties of the
eigenfunctions as well, cf. Zhang et al. [25], but the paper builds on
unverified assumptions. The analysis of the regression error in different
norms (cf. Fischer and Steinwart 11 and Steinwart et al. 21) can be related to
bounded eigenfunctions as well. This paper presents explicit bounds of the
maximum value the eigenfunction may attain.

#### Outline of the paper.

Section 2 addresses polynomial approximations of kernel functions. Section 3
addresses the Gaussian kernel specifically and presents bounds of the
eigenfunctions on bounded domains. This section contains the main results,
which are considered in Section 4 in applications. Section 5 concludes the
paper.

##  2 The minimal moment function

Reproducing kernel Hilbert spaces (RKHS) build on a kernel function, denoted
$k$. The approximations considered here build on the point evaluation function
$k_{x}(\cdot)\coloneqq k(x,\cdot)$. This section resumes the minimal moment
function $w_{m}^{x}$ from (1.1), for which the image $L_{k}w_{m}^{x}$ is a
suitable estimate of $k_{x}$. We first derive the function $w_{m}^{x}$ for the
simple design space $\mathcal{X}=[0,1]$, and then extend it to the
$d$-dimensional case with some non-uniform design measure $P$. Using the
moment property (1.1), we derive an error bound for the approximation quality
of $k_{x}(\cdot)$ by $L_{k}w_{m}^{x}$, which is based on the Taylor
coefficients of the kernel.

###  2.1  The minimal moment function

The central element of this paper is the function with smallest $L^{2}$-norm,
satisfying the moment properties (1.1). There are infinitely many functions
fulfilling the condition (1.1). We refer to the function with smallest
$L^{2}$-norm as the _minimal moment function_ , where the inner product is
$\left\langle
f,g\right\rangle_{L^{2}}\coloneqq\int_{\mathcal{X}}f(z)g(z)p(z)\,dz$ with the
density $p$ of the underlying measure $P$. Throughout this section, we
consider the design space $\mathcal{X}=[0,1]$ equipped with the uniform
measure $P\sim\mathcal{U}[0,1]$.

In what follows we provide an explicit representation of the minimal moment
function. We demonstrate that it is a polynomial of degree $m-1$, with
coefficients originating from a Hilbert matrix.

######  Theorem 2.1 (Explicit minimal moment function).

For $x\in[0,1]$ fixed, the optimization problem

$\vartheta^{*}\coloneqq\min\left\\{\left\|w\right\|_{L^{2}}^{2}\colon\int_{0}^{1}z^{\ell}w(z)dz=x^{\ell},\
\ell=0,1,\dots,m-1\right\\}$ (2.1)

has the unique solution

$w_{m}^{x}(z)=\sum_{i=1}^{m}\alpha_{x,i}z^{i-1},\qquad z\in(0,1),$ (2.2)

where $\alpha_{x}$ satisfies the equations $H_{m}\alpha_{x}=\bar{x}$ for the
Hilbert matrix $H_{m}\coloneqq\left(\frac{1}{i+j-1}\right)_{i=1,j=1}^{n,n}$
and the vector $\bar{x}\coloneqq(1,x,\dots,x^{m-1})\in\mathbb{R}^{m}$.

###### Proof.

The Lagrangian $\mathcal{L}$ of (2.1) is

$\mathcal{L}(w,\mu)=\left\langle
w(z),w(z)\right\rangle_{L^{2}}+\sum_{i=1}^{m}\mu_{i}\left(\left\langle
z^{i-1},w(z)\right\rangle_{L^{2}}-x^{i-1}\right),$

where $w\in L^{2}$ and $\mu=(\mu_{1},\dots,\mu_{m})\in\mathbb{R}^{m}$ are
Lagrange multipliers. The first order condition reads

$\displaystyle(\nabla_{w}\mathcal{L})(w_{\mu}^{\ast},\mu)$
$\displaystyle=2w_{\mu}^{\ast}+\sum_{i=1}^{m}\mu_{i}z^{i-1}=0,$

which is equivalent to
$w_{\mu}^{\ast}(z)=-\frac{1}{2}\sum_{i=1}^{m}\mu_{i}z^{i-1}$. For
$\mu=(\mu_{1},\dots,\mu_{m})$ fixed, the Lagrangian function $\mathcal{L}$ is
convex and $w_{\mu}^{\ast}$ thus a minimizer. Hence, the Lagrangian dual
function is

$\displaystyle g(\mu)$ $\displaystyle\coloneqq\min_{w\in
L^{2}}\mathcal{L}(w,\mu)=\mathcal{L}(w_{\mu}^{\ast},\mu)=\left\langle
w_{\mu}^{\ast},w_{\mu}^{\ast}\right\rangle_{L^{2}}+\sum_{i=1}^{m}\mu_{i}\left(\left\langle
z^{i-1},w_{\mu}^{\ast}\right\rangle_{L^{2}}-x^{i-1}\right),$

depending only on the multipliers $\mu$. As $\left\langle
z^{i-1},z^{j-1}\right\rangle_{L^{2}}=\frac{1}{i+j-1}$, we further have that

$\left\langle
z^{i-1},w_{\mu}^{\ast}\right\rangle_{L^{2}}-x^{i-1}=-\frac{1}{2}\sum_{i=1}^{m}\mu_{i}^{\ast}\frac{1}{j+i-1}-x^{j-1}=0$

by setting $\mu^{\ast}=-2H_{m}^{-1}\bar{x}$. It follows that

$g(\mu^{\ast})=\left\langle
w_{\mu^{\ast}}^{\ast},w_{\mu^{\ast}}^{\ast}\right\rangle_{L^{2}}\geq\vartheta^{\ast},$

as $w_{\mu^{\ast}}^{\ast}$ is feasible in (2.1). This implies strong duality
as well as the optimality of $w_{\mu^{\ast}}^{\ast}=w_{m}^{x}$, which is the
assertion. ∎

A minimal moment function of particular interest is the optimizer of (2.1)
associated with the point $x=1$. In contrast to the general case $x\in[0,1]$,
the $L^{2}$-norm of $w_{m}^{1}$ can be computed explicitly. Indeed, it holds
that

$\displaystyle\int_{0}^{1}w_{m}^{1}(z)^{2}dz$
$\displaystyle=\int_{0}^{1}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{1,i}\alpha_{1,j}z^{i+j-2}dz$
$\displaystyle=\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{1,i}\alpha_{1,j}\frac{1}{i+j-1}$
$\displaystyle=\sum_{i=1}^{m}\alpha_{1,i}1=\alpha_{1}^{\top}e=e^{\top}H_{m}^{-1}e=m^{2},$
(2.3)

as $\sum_{i,j=1}^{n}(H_{m}^{-1})_{i,j}=m^{2}$.

In what follows we bound the norm of the remaining moment functions. For that
we relate $w_{m}^{x}$ with a specific linear transformation of $w_{m}^{1}$.

######  Theorem 2.2 (Upper bound of the weight function).

The weight function $w_{m}^{x}$ satisfies the bound

$\left\|w_{m}^{x}\right\|_{L^{2}}^{2}\leq m^{2}$ (2.4)

for any $x\in[0,1]$.

###### Proof.

Note first that, for $x=0$,

$\int_{0}^{1}w_{m}^{0}(z)^{2}dz=e_{1}^{\top}H_{m}^{-1}e_{1}=\bigl{(}H_{m}^{-1}\bigr{)}_{1,1}=m^{2},$

where $e_{1}=(1,0,\dots.0)$ is the first vector in the canonical basis. To
verify the bound for the remaining points $x\in(0,1)$ we relate $w_{m}^{x}$
with an auxiliary function $\tilde{w}_{m}^{x}$ for which we are able to
calculate the norm more easily. Setting $g^{x}(z)\coloneqq
w_{m}^{1}(\frac{z}{x}){\mathds{1}}_{[0,x]}(z)$ we define the auxiliary
function

$\tilde{w}_{m}^{x}(z)\coloneqq\begin{cases}g^{x}(z)&\text{if }z\leq x,\\\
g^{1-x}(1-z)&\text{if }z>x,\end{cases}$

with $x\in(0,1).$ To relate $w_{m}^{x}$ with $\tilde{w}_{m}^{x}$, we
demonstrate first that $\tilde{w}_{m}^{x}$ satisfies the moment constraints
(1.1) and bound its norm afterwards. It holds that

$\int_{0}^{1}z^{h}g^{x}(z)dz=\int_{0}^{x}z^{h}\,w_{m}^{1}\Bigl{(}\frac{z}{x}\Bigr{)}\,dz=x\int_{0}^{1}(yx)^{h}w_{m}^{1}(y)dy=xx^{h}$
(2.5)

for the first part of the integral. We further have that

$\displaystyle\int_{0}^{1}z^{h}g^{1-x}(1-z)dz$
$\displaystyle=-\int_{1-x}^{0}(1-y)^{h}g^{1-x}(y)dz=\int_{0}^{1-x}(1-y)^{h}g^{1-x}(y)dy$

after changing the variables. By the binomial theorem,

$\displaystyle\int_{0}^{1-x}(1-y)^{h}g^{1-x}(y)dy$
$\displaystyle=\sum_{p=0}^{h}\binom{h}{p}(-1)^{h-p}\int_{0}^{1-x}y^{h-p}g^{1-x}(y)dy$
$\displaystyle=\sum_{p=0}^{h}\binom{h}{p}(-1)^{h-p}(1-x)(1-x)^{h-p}$
$\displaystyle=(1-x)(1-(1-x))^{h}=(1-x)x^{h},$

as $\int_{0}^{1-x}y^{h-p}g^{1-x}(y)dy=(1-x)(1-x)^{h-p}$ by (2.5). Connecting
both identities, we have that

$\int_{0}^{1}z^{h}\tilde{w}_{m}^{x}(z)dz=\int_{0}^{x}z^{h}g^{x}(z)dz+\int_{0}^{1-x}(1-y)^{h}g^{1-x}(y)dy=x^{h},$

and thus the moment property (1.1) of $\tilde{w}_{m}^{x}$. It is now evident
by (2.1) that $\left\|\tilde{w}_{m}^{x}\right\|_{L^{2}}$ is an upper bound of
$\left\|w_{m}^{x}\right\|_{L^{2}}.$ Employing the same substitutions as above,
we get that

$\displaystyle\int_{0}^{1}\tilde{w}_{m}^{x}(z)^{2}dz$
$\displaystyle=\int_{0}^{x}g^{x}(z)^{2}dz+\int_{x}^{1}g^{1-x}(1-z)^{2}dz$
$\displaystyle=x\int_{0}^{1}w_{m}^{1}(y)^{2}dy+(1-x)\int_{\text{0}}^{1}w_{m}^{1}(y)^{2}dz$
$\displaystyle=\int_{0}^{1}w_{m}^{1}(y)^{2}dy=m^{2}$

by (2.3), concluding the proof. ∎

The squared norm of the moments functions at the boundary points is $m^{2}.$
However, the norm of the minimal moment functions associated with the interior
points $x\in(0,1)$ might be significantly smaller.

###  2.2 Extensions and error estimates

The results of the preceding Section 2.1 crucially rely on the proposed
setting, i.e., the design space $[0,1]$ equipped with the uniform
distribution. These assumptions are quite restrictive and need to be relaxed
for situations of practical application. To this end we investigate a more
general setting throughout this section.

We consider the multivariate case where $\mathcal{X}=[0,1]^{d}$, with some
underlying design measure $P$. This measure has a strictly positive density
with

$\infty>C>\sup_{z\in[0,1]^{d}}p(z)\geq\inf_{z\in[0,1]^{d}}p(z)>c>0,$

giving rise to the inner product

$\left\langle f,g\right\rangle_{L^{2}}=\int_{[0,1]^{d}}f(z)g(z)p(z)dz.$

In what follows we specify the minimal moment functions for this more general
setting. Building on the univariate moment property of the functions (2.2), we
demonstrate that their product satisfies a multivariate version of (1.1). The
next proposition reveals the precise statement.

######  Proposition 2.3 (Upper bound of the weight function in higher
dimensions).

Let $x=(x_{1},\dots,x_{d})\in[0,1]^{d}$ and consider the function

$W_{m}^{x}(z_{1},\dots,z_{d})\coloneqq\left(\prod_{i=1}^{d}w_{m}^{x_{i}}(z_{i})\right)p(z_{1},\dots,z_{n})^{-1},$
(2.6)

where $w_{m}^{x_{i}}$ are the functions defined in (2.2). The function
$W_{m}^{x}$ satisfies the general moment property

$\int_{[0,1]^{d}}\left(\left\|y-z\right\|_{2}^{2}\right)^{\ell}W_{m}^{x}(z)p(z)dz=\left(\left\|y-x\right\|_{2}^{2}\right)^{\ell}$
(2.7)

for all integers $\ell\leq\frac{m}{2}$. Its norm is bounded by
$\left\|W_{m}^{x}\right\|_{L^{2}}^{2}\leq c_{p}m^{2d}$ with
$c_{p}=\sup_{z\in[0,1]^{d}}p(z)^{-1}.$

###### Proof.

The moment property (2.7) follows from

$\displaystyle\int_{[0,1]^{d}}\left(\left\|y-z\right\|_{2}^{2}\right)^{\ell}W_{m}^{x}(z)p(z)dz$
$\displaystyle=\int_{0}^{1}\dots\int_{0}^{1}\left(\sum_{i=1}^{d}(y_{i}-z_{i})^{2}\right)^{\ell}\prod_{i=1}^{d}w_{m}^{x_{i}}(z_{i})dz_{1}\dots
dz_{d}$
$\displaystyle=\sum_{h_{1}+\dots+h_{d}=\ell}\binom{\ell}{h_{1},\dots,h_{d}}\prod_{i=1}^{d}\int_{0}^{1}(y_{i}-z_{i})^{2h_{i}}w_{m}^{x_{i}}(z_{i})dz_{i}$
$\displaystyle=\sum_{h_{1}+\dots+h_{d}=\ell}\binom{\ell}{h_{1},\dots,h_{d}}\prod_{i=1}^{d}(y_{i}-x_{i})^{2h_{i}}$
$\displaystyle=\left(\left\|y-x\right\|_{2}^{2}\right)^{\ell},$

as $\int_{0}^{1}z_{i}^{\ell_{i}}w_{m}^{x_{i}}(z_{i})=x_{i}^{\ell_{i}}$ holds
for all integers $\ell_{i}\leq m-1$. This is the first assertion.

For the second assertion note that
$\left\|w_{m}^{x_{i}}\right\|_{L^{2}}^{2}\leq m^{2}$ holds by (2.4). Hence, we
get that

$\displaystyle\int_{[0,1]^{d}}(W_{m}^{x}(z))^{2}p(z)dz$
$\displaystyle=\int_{0}^{1}\dots\int_{0}^{1}\left(\prod_{i=1}^{n}w_{m}^{x_{i}}(z_{i})\right)^{2}p(z_{1},\dots,z_{n})^{-1}dz_{1}\dots
dz_{d}$
$\displaystyle\leq\sup_{z\in[0,1]^{d}}\left|p(z)^{-1}\right|\prod_{i=1}^{d}\int_{0}^{1}(w_{m}^{x_{i}}(z_{i}))^{2}dz_{i}=c_{p}m^{2d},$

which concludes the proof. ∎

######  Remark 2.4.

The function $W_{m}^{x}(\cdot)$ might not be the norm minimal function
satisfying (2.7). Indeed, the product structure of (2.6) leads to an
exponentially (with respect to the dimension) increasing norm of $W_{m}^{x}$.
However, the construction of the norm minimal moment function satisfying (2.7)
might require a significantly more involved representation, which is out of
the scope of this paper.

Continuing the general setting considered above, we now provide the first
error estimate. To this end we consider a radial kernel

$k(x,y)=\phi(\left\|x-y\right\|^{2})$ (2.8)

as well as the corresponding integral operator $L_{k}\colon
L^{2}(\mathcal{X},P)\to L^{2}(\mathcal{X},P)$ defined as

$(L_{k}f)(y)=\int_{\mathcal{X}}k(z,y)f(z)p(z)dz.$ (2.9)

Here, $\phi$ is a smooth function with Taylor series expansion

$\phi(x)=\sum_{\ell=0}^{\infty}\frac{\alpha_{\ell}}{\ell!}x^{\ell}.$ (2.10)

Building on the moment property (2.7), we utilize that the $\ell$th moment of
$k_{x}-L_{k}W_{m}^{x}$ vanishes. The subsequent theorem reveals the precise
bound.

######  Theorem 2.5 (Uniform bound in $d$-dimensions).

With the function $W_{m}^{x}$ defined in (2.6), the error estimate

$\sup_{x\in[0,1]^{d}}\left\|(L_{k}W_{m}^{x})(y)-k_{x}\right\|_{\infty}\leq(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{\left|a_{\ell}\right|}{\ell!}d^{\ell},$
(2.11)

holds true. Here, $\left\lfloor\cdot\right\rfloor$ denotes the floor function.

###### Proof.

Employing the series representation (2.10) of $\phi$, we have the
decomposition

$\displaystyle(L_{k}W_{m}^{x})(y)$
$\displaystyle=\int_{\mathcal{X}}\phi\left(\left\|y-z\right\|_{2}^{2}\right)W_{m}^{x}(z)p(z)dz$
$\displaystyle=\int_{\mathcal{X}}\sum_{\ell=0}^{\left\lfloor\frac{m-1}{2}\right\rfloor}\frac{a_{\ell}}{\ell!}(\left\|y-z\right\|_{2}^{2})^{\ell}W_{m}^{x}(z)p(z)dz$
$\displaystyle+\int_{\mathcal{X}}\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{a_{\ell}}{\ell!}(\left\|y-z\right\|_{2}^{2})^{\ell}W_{m}^{x}(z)p(z)dz.$

For the first part, it follows from the moment property (2.7) of $W_{m}^{x}$
that

$\displaystyle\int_{\mathcal{X}}\sum_{\ell=0}^{\left\lfloor\frac{m-1}{2}\right\rfloor}\frac{a_{\ell}}{\ell!}(\left\|y-z\right\|_{2}^{2})^{\ell}W_{m}^{x}(z)p(z)dz$
$\displaystyle=\sum_{\ell=0}^{\left\lfloor\frac{m-1}{2}\right\rfloor}\frac{a_{\ell}}{\ell!}\left(\left\|y-x\right\|_{2}^{2}\right)^{\ell},$

as the $2\left\lfloor\frac{m-1}{2}\right\rfloor\leq m-1$. Hence, we have that

$\displaystyle\left|k(y,x)-(L_{k}W_{m}^{x})(y)\right|$ $\displaystyle=$
$\displaystyle\left|k(y,x)-\sum_{\ell=0}^{\left\lfloor\frac{m-1}{2}\right\rfloor}\frac{a_{\ell}}{\ell!}(\left\|y-x\right\|_{2}^{2})^{\ell}+\int_{\mathcal{X}}\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{a_{\ell}}{\ell!}(\left\|y-z\right\|_{2}^{2})^{\ell}W_{m}^{x}(z)p(z)dz\right|$
$\displaystyle=$
$\displaystyle\left|\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{a_{\ell}}{\ell!}(\left\|y-x\right\|_{2}^{2})^{\ell}+\int_{\mathcal{X}}\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{a_{\ell}}{\ell!}(\left\|y-z\right\|_{2}^{2})^{2\ell}W_{m}^{x}(z)p(z)dz\right|$
$\displaystyle\leq$
$\displaystyle\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{\left|a_{\ell}\right|}{\ell!}d^{\ell}+\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{\left|a_{\ell}\right|}{\ell!}d^{\ell}\left\|W_{m}^{x}\right\|_{L^{2}}$
$\displaystyle\leq$
$\displaystyle\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{\left|a_{\ell}\right|}{\ell!}d^{\ell}+c_{p}^{\nicefrac{{1}}{{2}}}m^{d}\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{\left|a_{\ell}\right|}{\ell!}d^{\ell}.$

The assertion follows, as the result holds for each $x\in[0,1]^{d}$. ∎

The statement of Theorem 2.5 above applies for general translation invariant
kernels of the shape $k(x,y)=\phi(\left\|x-y\right\|^{2})$. To further specify
the associated error bound, one needs to include knowledge about the decay of
the Taylor coefficients of $\phi$. To this end we now consider a fixed kernel
for which these coefficients and their behavior are known.

##  3  The Gaussian kernel

The following results build on reproducing kernel Hilbert spaces (RKHS). For
these spaces, point evaluations are continuous linear functionals, and this
property is the decisive characteristic of RKHS. Each kernel functions
addressed above is associated with the corresponding space
$\bigl{(}\mathcal{H}_{k},\,\langle\cdot|\cdot\rangle_{k}\bigr{)}$, for which
$\langle f|\,k(x,\cdot)\rangle_{k}=f(x)$ whenever $f\in\mathcal{H}_{k}$. For a
detailed review of these spaces we refer to Berlinet and Thomas-Agnan [2] or
Steinwart and Christmann [20].

This section addresses the most popular kernel in machine learning, the
Gaussian kernel

$k(x,y)\coloneqq
e^{-\sigma\left\|x-y\right\|_{2}^{2}}=\phi\bigl{(}\sigma\cdot\left\|x-y\right\|_{2}^{2}\bigr{)},$
(3.1)

where $\sigma>0$ is a width parameter. We approximate the point evaluation
function in the range of the Hilbert–Schmidt operator and analyze its error
with respect to different norms. Building on these estimates, we derive
essential properties of the problem

$\inf_{w\in\mathcal{H}_{k}}\lambda\|w\|_{2}^{2}+\|L_{k}w-k_{x}\|_{k}^{2},$
(3.2)

which will be used in what follows. We employ these results to establish
polynomial bounds on the magnitude of the eigenfunctions of the Gaussian
kernel.

###  3.1 Approximation of the point evaluation function

In this section we investigate the approximation of the point evaluation
function $k_{x}$ for the Gaussian kernel. We relate the function $k_{x}$ with
an approximation from the image of the corresponding integral operator $L_{k}$
and provide bounds with respect to the infinity norm as well as the norm of
the RKHS. The following theorem provides the result for the uniform norm
first.

######  Theorem 3.1 (Uniform approximation of $k_{x}$ in
$\left\|\cdot\right\|_{\infty}$).

Let $k$ be the $d$-dimensional Gaussian kernel with width parameter $\sigma$.
Setting $c_{\sigma}\coloneqq\max\left\\{1,2e\sigma d\right\\}$,
$c_{p}=\sup_{z\in[0,1]^{d}}p(z)^{-1}$ and

$C(\sigma,m)\coloneqq\frac{1}{1-\frac{\sigma
ed}{\left\lfloor\frac{m}{2}\right\rfloor}},$

the uniform bound

$\sup_{x\in[0,1]^{d}}\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{\infty}\leq(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\,C(\sigma,m)\left(\left\lfloor\frac{m}{2}\right\rfloor\frac{1}{\sigma
ed}\right)^{\left\lfloor\frac{m}{2}\right\rfloor}$

holds for $W_{m}^{x}$ defined in (2.6) for $m>c_{\sigma}+1$.

Specifically, for $m(s)\coloneqq 3c_{\sigma}s+2$, we have that

$\sup_{x\in[0,1]^{d}}\left\|L_{k}W_{m(td)}^{x}-k_{x}\right\|_{\infty}\leq
3(t\,d)^{-3t\,d}$ (3.3)

whenever
$t\geq\max\left\\{\frac{\ln(3)+(d-1)\ln(2)+\frac{1}{2}\ln(c_{p})+d\ln(3c_{\sigma}d)}{2d\ln(3)},\
1\right\\}.$

###### Proof.

We defer the proof to Appendix A. ∎

The uniform bound (3.3) relates $L_{k}W_{m}^{x}$ and $k_{x}$ for all points
$x\in[0,1]^{d}$. However, the uniform norm is slightly too weak when studying
the objective (3.2), which relies on the approximation in RKHS norm. To
overcome this issue we extend the result obtained and establish a dedicated
bound, similar to (3.3), but with respect to the stronger norm
$\|\cdot\|_{k}$. The next proposition reveals the desired bound.

######  Proposition 3.2 (Uniform approximation of $k_{x}$ in the norm
$\left\|\cdot\right\|_{k}$).

Let $m=m(s)=3c_{\sigma}s+2$ and $t\geq
c\coloneqq\max\\{c_{0},c_{1},c_{2},1\\}$, where

$\displaystyle c_{0}$
$\displaystyle=\frac{\ln(3)+(d-1)\ln(2)+\frac{1}{2}\ln(c_{p})+d\ln(3c_{\sigma}d)}{2d\ln(3)}.$
$\displaystyle c_{1}$
$\displaystyle=\frac{(2d-1)\ln(2)+d\ln(3c_{\sigma})+\frac{1}{2}\ln(c_{p})}{d}+1,$
$\displaystyle c_{2}$
$\displaystyle=\frac{(2d-1)\ln(2)+\frac{1}{2}\ln(c_{p})}{d}.$

In the setting of Theorem (3.1), the uniform bound in $\|\cdot\|_{k}$-norm,

$\sup_{x\in[0,1]^{d}}\left\|L_{k}W_{m(td)}^{x}-k_{x}\right\|_{k}^{2}\leq
9(td)^{-2td},$ (3.4)

holds true.

###### Proof.

Let $x\in[0,1]^{d}$ and observe from (3.3) and the reverse triangle inequality
that

$(L_{k}W_{m}^{x})(x)\geq
k(x,x)-\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{\infty}\geq k(x,x)-3(td)^{-3td},$
(3.5)

whenever $m$ and $t$ are chosen appropriately (see Theorem 3.1). Hence,
setting $m=\left\lceil 3c_{\sigma}td\right\rceil+2$, it follows from (3.5)
that

$\displaystyle\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{k}^{2}$
$\displaystyle=\left\langle
L_{k}W_{m}^{x},L_{k}W_{m}^{x}\right\rangle_{k}-2\left\langle
L_{k}W_{m}^{x},k_{x}\right\rangle_{k}+k(x,x)$ $\displaystyle=\left\langle
L_{k}W_{m}^{x},L_{k}W_{m}^{x}\right\rangle_{k}-2\left(L_{k}W_{m}^{x}\right)(x)+k(x,x)$
$\displaystyle\leq\left\langle
L_{k}W_{m}^{x},W_{m}^{x}\right\rangle_{L^{2}}-\left(L_{k}W_{m}^{x}\right)(x)+3(td)^{-3td},$

as $\left\langle
L_{k}W_{m}^{x},k_{x}\right\rangle_{k}=\left(L_{k}W_{m}^{x}\right)(x)$ holds by
the reproducing property. Furthermore, we have that

$\displaystyle\left\langle L_{k}W_{m}^{x},W_{m}^{x}\right\rangle_{L^{2}}$
$\displaystyle=\left\langle
L_{k}W_{m}^{x}-k_{x},W_{m}^{x}\right\rangle_{L^{2}}+\left\langle
k_{x},W_{m}^{x}\right\rangle_{L^{2}}=\left\langle
L_{k}W_{m}^{x}-k_{x},W_{m}^{x}\right\rangle_{L^{2}}+\left(L_{k}W_{m}^{x}\right)(x).$

Employing the bound

$\left\langle L_{k}W_{m}^{x}-k_{x},W_{m}^{x}\right\rangle_{L^{2}}\leq
6(dt)^{-2dt}$

from Lemma A.7 in the appendix and combining the estimates above, we get

$\left\|L_{k}w_{m}^{x}-k_{x}\right\|_{k}^{2}\leq 6(td)^{-2td}+3(td)^{-3td}\leq
9(td)^{-2td},$

and thus the assertion. ∎

######  Remark 3.3.

The bound (3.4) depends only on the magnitude of the product $td$.
Substituting $s=td$ gives the more convenient bound

$\sup_{x\in[0,1]^{d}}\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{k}^{2}\leq
9s{}^{-2s},$ (3.6)

where $m=m(s)=3c_{\sigma}s+2$ and $s\geq d\cdot c.$

###  3.2 Implications for the weight function

Building on the bound (3.4) of Section 3.1, we now examine the optimal weight
function $w_{\lambda}^{x}$ solving the optimization problem

$\inf_{w\in
L^{2}}\lambda\left\|w\right\|_{L^{2}}^{2}+\left\|L_{k}w-k_{x}\right\|_{k}^{2},$

cf. (3.2). This optimal solution $w_{\lambda}^{x}$ and its norm determines the
approximation quality of the point evaluation $k_{x}$ in the range of $L_{k}$.
Moreover, they relate the continuous operator $L_{k}$ with discrete versions,
which we address and discuss in the following sections.

By Mercer’s theorem, the kernel $k$ enjoys the representation
$k(x,y)=\sum_{\ell=1}^{\infty}\mu_{\ell}\,\varphi_{\ell}(x)\varphi_{\ell}(y)$,
where $\mu_{\ell}$ are the eigenvalues (in non-increasing order) and
$\varphi_{\ell}$ the eigenfunctions, $\ell=1,2,\dots$, of the operator $L_{k}$
introduced in (2.9). The explicit representation

$w_{\lambda}^{x}(y)=\bigl{(}(\lambda+L_{k})^{-1}L_{k}k_{x}\bigr{)}(y)=\sum_{\ell=1}^{\infty}\frac{\mu_{\ell}}{\lambda+\mu_{\ell}}\varphi_{\ell}(x)\varphi_{\ell}(y)$

of the optimal solution involves the regularization parameter $\lambda$ and
the components of Mercer’s decomposition of the kernel $k$ (cf. Cucker and
Zhou 4, Proposition 8.6).

The next theorem provides a bound on the magnitude of the worst case norm,
more specifically, a bound for
$\sup_{x\in[0,1]^{d}}\left\|w_{\lambda}^{x}\right\|_{L^{2}}$.

######  Theorem 3.4 (Uniform bound of the weight function).

Let $k$ be the Gaussian kernel. The weight function $w_{\lambda}^{x}$
satisfies the bound

$\sup_{x\in[0,1]^{d}}\left\|w_{\lambda}^{x}\right\|_{L^{2}}^{2}\leq
9c_{p}\left(3c_{\sigma}s(\lambda)+2\right)^{2d}+1$ (3.7)

with
$s(\lambda)\coloneqq\max\left\\{-\frac{1}{2}\ln\left(\frac{\lambda}{9}\right),\,d\cdot
c,\,e\right\\}$ and $c_{\sigma}$, $c$ from Proposition 3.2.

###### Proof.

The function $w_{\lambda}^{x}$ minimizes (3.2) and thus

$\sup_{x\in[0,1]^{d}}\lambda\left\|w_{\lambda}^{x}\right\|_{L^{2}}^{2}\leq\sup_{x\in[0,1]^{d}}\lambda\left\|W_{m}^{x}\right\|_{L^{2}}^{2}+\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{k}^{2}\leq\sup_{x\in[0,1]^{d}}\lambda
c_{p}m^{2d}+\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{k}^{2},$ (3.8)

as $\left\|W_{m}^{x}\right\|_{2}^{2}\leq c_{p}m^{2d}$ (see Theorem 2.3).

Choosing
$s(\lambda)\coloneqq\max\left\\{-\frac{1}{2}\ln\left(\frac{\lambda}{9}\right),\,d\cdot
c,\,e\right\\}$ and $m=3c_{\sigma}\,s(\lambda)+2$ we derive from (3.6) that

$\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{k}^{2}\leq 9s^{-2s}\leq\lambda$

(as $s\geq e$ and $s\geq-\frac{1}{2}\ln\left(\frac{\lambda}{9}\right)$), and
thus

$\displaystyle\sup_{x\in[0,1]^{d}}\lambda\left\|w_{\lambda}^{x}\right\|_{L^{2}}^{2}$
$\displaystyle\leq\sup_{x\in[0,1]^{d}}\lambda
c_{p}m^{2d}+\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{k}^{2}\leq\lambda
c_{p}(3c_{\sigma}s(\lambda)+2)^{2d}+\lambda$

by (3.8). Multiplying with $\lambda^{-1}$ gives the assertion. ∎

The bound (3.7) characterizes the asymptotic growth of the norm
$\left\|w_{\lambda}^{x}\right\|_{L^{2}}$. Indeed, letting $\lambda\downarrow
0$, the bound (3.7) implies that $\left\|w_{\lambda}^{x}\right\|_{L^{2}}$
grows at most as $\bigl{(}\ln(\lambda^{-1})\bigr{)}^{d}$. The subsequent
sections heavily exploit this asymptotic behavior.

###  3.3 Eigenvalues and eigenfunctions

This section studies the elements in Mercer’s decomposition of the kernel,
$k(x,y)=\sum_{\ell=1}^{\infty}\mu_{\ell}\varphi_{\ell}(x)\varphi_{\ell}(y)$,
specifically for the Gaussian kernel. We first relate the maximal value of any
eigenfunction with its associated eigenvalue, demonstrating that
$\left\|\varphi_{\ell}\right\|_{\infty}$ is bounded by
$\bigl{(}\ln(\mu_{\ell}^{-1})\bigl{)}^{d}$. This bound is significantly
sharper than the standard bound $\max_{x\in\mathcal{X}}\varphi_{\ell}(x)\leq
k(x,x)^{\nicefrac{{1}}{{2}}}\mu_{\ell}^{\nicefrac{{-1}}{{2}}}$ derived from
the Cauchy–Schwartz inequality,
$\langle\varphi,\,k_{x}\rangle_{k}\leq\|\varphi\|_{k}\,k(x,x)$.

We next describe the decay of the eigenvalues $\mu_{\ell}$ and derive a bound
on $\left\|\varphi_{\ell}\right\|_{\infty}$, which turns out to be quadratic
in $\ell$. The results of this section enable us to infer convergence in
uniform norm from convergence in $L^{2}$. Generally, this approach leads to
faster convergence rates compared to results, which are derived from
convergence in the norm $\left\|\cdot\right\|_{k}$ (see Section 4.2).

Our approach builds on the following observation. For the regularization
$\lambda=\mu_{\ell}$, the series

$\left\|w_{\lambda}^{x}\right\|_{L^{2}}^{2}=\sum_{h=1}^{\infty}\frac{\mu_{h}}{\lambda+\mu_{h}}\varphi_{h}^{2}(x)$

involves the term $\frac{1}{2}\varphi_{\ell}^{2}(x)$. To bound the maximum of
$\left|\varphi_{\ell}\right|$, it is sufficient to assess
$\sup_{x\in[0,1]^{d}}\left\|w_{\lambda}^{x}\right\|_{L^{2}}^{2}$, which is
bounded by the inequality (3.7). The following result summarizes these
relations.

######  Theorem 3.5.

For the eigenfunctions of the Gaussian kernel, the inequality

$\sup_{x\in[0,1]^{d}}\left|\varphi_{\ell}(x)\right|\leq\sqrt{18c_{p}}\left(3c_{\sigma}s(\mu_{\ell})+2\right)^{d}+\sqrt{2}$
(3.9)

holds for every $\ell\in\mathbb{N}$, where
$s(\mu_{\ell})=\max\left\\{-\frac{1}{2}\ln\left(\frac{\mu_{\ell}}{9}\right),\
e,\ d\cdot c\right\\}$ is as in Theorem 3.4.

###### Proof.

For $\ell\in\mathbb{N}$, it holds that

$\frac{1}{2}\left|\varphi_{\ell}(x)\right|^{2}=\frac{\mu_{\ell}}{\mu_{\ell}+\mu_{\ell}}\varphi_{\ell}(x)^{2}\leq\sum_{h=1}^{\infty}\frac{\mu_{h}}{\mu_{\ell}+\mu_{h}}\varphi_{h}(x)^{2}=\left\|w_{\lambda^{\ast}}^{x}\right\|_{L^{2}}^{2},$

with $\lambda^{\ast}=\mu_{\ell}$. Taking the maximum on both sides, we deduce
from the latter inequality and (3.7) that

$\displaystyle\frac{1}{2}\left\|\varphi_{\ell}\right\|_{\infty}^{2}$
$\displaystyle\leq\sup_{x\in[0,1]^{d}}\left\|w_{\lambda^{\ast}}^{x}\right\|_{L^{2}}^{2}$
$\displaystyle\leq
9c_{p}\left(3c_{\sigma}s(\lambda^{\ast})+2\right)^{2d}+1=9c_{p}\left(3c_{\sigma}s(\mu_{\ell})+2\right)^{2d}+1.$

Reformulating this inequality as well as using the subadditivity of the square
root gives the assertion. ∎

The bound (3.9) relates the eigenfunctions and the eigenvalues of the operator
$L_{k}$. In what follows, we analyze the decay of
$(\mu_{\ell})_{\ell=1}^{\infty}$ to get a more concrete characterization of
the bound in (3.9).

The next lemma provides a lower bound of the eigenvalues
$(\mu_{\ell})_{\ell=1}^{\infty}$.

######  Lemma 3.6 (Maximal decay of eigenvalues).

Set $p_{\min}\coloneqq\inf_{x\in\mathcal{X}}p(x)$ and
$p_{\max}\coloneqq\sup_{x\in\mathcal{X}}p(x)$. For the eigenvalues of the
Gaussian kernel it holds that

$\mu_{\ell}\geq\frac{p_{\min}^{2}}{p_{\max}^{2}}C(d,\sigma)e^{-c_{\sigma,d}(\ell+d)^{\frac{2}{d}}},\qquad\ell=1,2,\dots,$
(3.10)

where the constants $c_{d,\sigma}$ and $C(d,\sigma)$ depend on the dimension
$d$ and the bandwidth $\sigma$.

###### Proof.

See Appendix B. ∎

The subsequent theorem combines the inequalities (3.9) and (3.10) and provides
an explicit bound on the maximal absolute value of the eigenfunctions
$(\varphi_{\ell})_{\ell=1}^{\infty}.$

######  Theorem 3.7 (Eigenfunctions).

The eigenfunctions of the $d$-dimensional Gaussian kernel satisfy the bound

$\max_{x\in[0,1]^{d}}\left|\varphi_{\ell}(x)\right|\leq\sqrt{18c_{p}}\max\left\\{h(\ell),\
\left(3c_{\sigma}e+2\right)^{d},\left(3c_{\sigma}(d\cdot
c)+2\right)^{d}\right\\}+\sqrt{2}$ (3.11)

with

$h(\ell)\coloneqq\left(3c_{\sigma}\left(\left(\frac{1}{2}\ln\left(9\right)-\frac{1}{2}\ln\left(\frac{p_{\min}^{2}}{p_{\max}^{2}}C(d,\sigma)\right)+\frac{1}{2}c_{d,\sigma}(\ell+d)^{\frac{2}{d}}\right)\right)_{+}+2\right)^{d}$

and the constants from the preceding Lemma 3.6.

###### Proof.

For the assertion note first that

$s(\lambda)=\max\left\\{-\frac{1}{2}\ln\left(\frac{\lambda}{9}\right),\ e,\
d\cdot
c\right\\}=\max\left\\{\left(-\frac{1}{2}\ln\left(\frac{\lambda}{9}\right)\right)_{+},\
e,\ d\cdot c\right\\},$

where $x_{+}\coloneqq\max\left\\{x,\ 0\right\\}$ is the positive part of $x$.
Hence, employing (3.10) in (3.9), we have the bound

$\displaystyle\left|\varphi_{\ell}(x)\right|$
$\displaystyle\leq\sqrt{18c_{p}}\left(3c_{\sigma}s(\mu_{\ell})+2\right)^{d}+\sqrt{2}$
$\displaystyle=\sqrt{18c_{p}}\left(3c_{\sigma}\max\left\\{-\frac{1}{2}\ln\left(\frac{p_{\min}^{2}C(d,\sigma)e^{-c_{\sigma,d}(\ell+d)^{\frac{2}{d}}}}{9p_{\max}^{2}}\right),\
e,\ d\cdot c\right\\}+2\right)^{d}+\sqrt{2}$
$\displaystyle=\sqrt{18c_{p}}\left(3c_{\sigma}\max\left\\{\left(\frac{1}{2}\ln\left(9\right)-\frac{1}{2}\ln\left(\frac{p_{\min}^{2}}{p_{\max}^{2}}C(d,\sigma)\right)+\frac{1}{2}c_{d,\sigma}(\ell+d)^{\frac{2}{d}}\right)_{+},\,e,\,d\cdot
c\right\\}+2\right)^{d}$ (3.12) $\displaystyle\qquad+\sqrt{2}.$

Note now that $x\mapsto x^{d}$ is an increasing function on $[0,\infty)$ and
thus $\max\left\\{a,b\right\\}^{d}=\max\\{a^{d},b^{d}\\}$, provided that
$a,b\geq 0.$ Using this property in (3.12) provides the assertion (3.11). ∎

######  Remark 3.8.

The right-hand side of (3.11) deserves additional attention. While $h(\ell)$
grows with $\ell$ increasing, the other terms do not depend on $\ell$. For
sufficiently large $\ell$, the inequality (3.11) thus reads

$\max_{x\in[0,1]^{d}}\left|\varphi_{\ell}(x)\right|\leq
18c_{p}^{\nicefrac{{1}}{{2}}}h(\ell)+\sqrt{2}.$

The function $h$ itself grows at most as a polynomial with degree $2$. That
is, there exists a constant $b>0$ with quadratic bound

$\max_{x\in[0,1]^{d}}\left|\varphi_{\ell}(x)\right|\leq
b\,\ell^{2},\qquad\ell=1,2,\dots.$ (3.13)

To the best of our knowledge, this is the first non-exponential bound of
$\varphi_{\ell}^{\prime}s$ absolute maximum. The following section addresses
various consequences of this main result.

######  Remark 3.9.

The approach chosen in this Section 3 is not limited to the Gaussian kernel.
All steps extend to general kernels of the form $\phi(\left\|x-y\right\|^{2})$
(cf. (2.8)), provided that a lower bound on the decay of its eigenvalues is
available.

##  4 Main results

This section connects the results of the preceding sections for general
statistical learning settings. We present improved concentration bound
inequalities, an interpolation inequality relating to uniform convergence, and
the Nyström method.

We adopt the well-established notation (cf. Rudi et al. 14) and introduce

$\mathcal{N}_{\infty}(\lambda)\coloneqq\sup_{x\in[0,1]^{d}}\left\|w_{\lambda}^{x}\right\|_{L^{2}}^{2}.$
(4.1)

As established above in (3.7), it holds that

$\mathcal{N}_{\infty}(\lambda)=\mathcal{O}\bigl{(}\ln(\lambda^{-1})^{2d}\bigr{)}$

for $\lambda\to 0$.

Building on the results of Section 3, we provide the results for the Gaussian
kernel.

###  4.1  Concentration bounds

Standard kernel ridge regression minimizes the regularized squared error at
the sample points. To infer the related error at other locations, one needs to
connect the discrete setting with the continuous setting from Section 3. This
is commonly done by relating the discrete operator

$L_{k}^{D}\colon C(\mathcal{X})\to\mathcal{H}_{k}\hskip
10.00002pt\text{with}\hskip
10.00002pt(L_{k}^{D}f)(y)\coloneqq\frac{1}{n}\sum_{i=1}^{n}f(x_{i})k(y,x_{i})$

with its continuous version $L_{k}$, as demonstrated in Caponnetto and De Vito
[3] as well as in Fischer and Steinwart [11]. However, the underlying
concentration results in these references generally require regularization
sequences not faster than $\lambda_{n}=\mathcal{O}(\nicefrac{{1}}{{n}})$,
which is too restrictive for many tasks including the analysis of low rank
kernel methods (cf. Zhang et al. 25, Bach 1).

This section addresses this issue. We provide the following result, which
allows significantly higher flexibility in choosing the regularization
sequence $\lambda_{n}$. Specifically, the regularizing sequence may be chosen
to decay faster than any polynomial.

The following proposition collects the detailed result for the concentration
inequality.

######  Proposition 4.1.

Assume that $\lambda$ satisfies

$\frac{4}{3}\tau\,g(\lambda)\frac{\mathcal{N}_{\infty}(\lambda)}{n}+\sqrt{2\tau\,g(\lambda)\frac{\mathcal{N}_{\infty}(\lambda)}{n}}\leq\frac{1}{2}$
(4.2)

with

$g(\lambda)=\ln\left(2e\frac{(\lambda+\mu_{1})\mathcal{N}(\lambda)}{\mu_{1}}\right),\quad\mathcal{N}(\lambda)=\sum_{\ell=1}^{\infty}\frac{\mu_{\ell}}{\lambda+\mu_{\ell}}$

and $\tau>0$. Then the inequality

$\displaystyle\left\|(\lambda+L_{k}^{D})^{-1}(L_{k}+\lambda)\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}$
$\displaystyle\leq 2$ (4.3)

holds with probability at least $1-2e^{-\tau}$.

###### Proof.

For the proof we refer to Appendix C. ∎

The condition (4.2) deserves some additional commentary. The term
$\mathcal{N}_{\infty}(\lambda)$ is asymptotically bounded by
$\mathcal{O}\bigl{(}\ln(\lambda^{-1})^{2d}\bigr{)}$, and the function
$g(\lambda)$ does not grow faster than
$\mathcal{O}\bigl{(}\ln(\lambda^{-1})\bigr{)}$. The condition (4.2) is
asymptotically satisfied, provided that the regularization parameter $\lambda$
does not decay faster than $c\exp\bigl{(}-n^{\frac{1}{2d+1}}\bigr{)}$. This is
a significant improvement compared to the common regularization choice
$n^{-1}$.

The conclusion of Proposition 4.1 can be given more general, not necessarily
involving the Gaussian kernel. Moreover, the bound (3.7) of
$\mathcal{N}_{\infty}(\lambda)$ only relies on the decay of the Taylor
coefficients associated with the kernel. The same method thus may be applied
to derive concentration inequalities for any other radial kernel functions.

###  4.2 Interpolation inequality

This section establishes results on the uniform approximation quality for
smooth functions. The following interpolation inequality ensures that the
uniform norm of smooth functions is comparable its norm in $L^{2}$, although
this norm is much weaker in general. We measure smoothness with reference to
the norm $\|\cdot\|_{s}$ introduced below.

######  Theorem 4.2 (Interpolation of norm).

For $f=\sum_{\ell=1}^{\infty}c_{\ell}\varphi_{\ell}\in L^{2}$ with
$\left\|f\right\|_{s}^{2}\coloneqq\sum_{\ell=1}^{\infty}\frac{c_{\ell}^{2}}{\ell^{-2s}}<\infty$
it holds that

$\left\|f\right\|_{\infty}\leq\frac{\pi}{\sqrt{6}}b\left\|f\right\|_{s}^{\frac{3}{s}}\cdot\left\|f\right\|_{2}^{1-\frac{3}{s}},$
(4.4)

where $s>3$ and $\max_{x\in\mathcal{X}}\left|\varphi_{\ell}(x)\right|\leq
b\,\ell^{2}$ for all $\ell=1,2,\dots$ (cf. (3.13)).

###### Proof.

Building on the bound
$\max_{x\in\mathcal{X}}\left|\varphi_{\ell}(x)\right|\leq b\ell^{2}$ we have
with the Cauchy–Schwarz inequality that

$\displaystyle f(x)=\sum_{\ell=1}^{\infty}c_{\ell}\varphi_{\ell}(x)$
$\displaystyle\leq
b\sum_{\ell=1}^{\infty}\frac{c_{\ell}}{\ell^{-\frac{s}{p}}}\cdot\ell^{2-\frac{s}{p}}$
$\displaystyle\leq
b\sqrt{\sum_{\ell=1}^{\infty}\frac{c_{\ell}^{2}}{\ell^{-\frac{2s}{p}}}}\sqrt{\sum_{\ell=1}^{\infty}\ell^{(2-\frac{s}{p})2}}=b\sqrt{\sum_{\ell=1}^{\infty}\frac{c_{\ell}^{\frac{2}{p}}}{\ell^{-\frac{2s}{p}}}c_{\ell}^{2-\frac{2}{p}}}\,\sqrt{\zeta\Bigl{(}\frac{2s}{p}-4\Big{)}},$

where $\zeta(\cdot)$ is the Riemann zeta function and $p\in[1,2s]$. Employing
Hölder?s inequality, it follows for the first term that

$\displaystyle\sqrt{\sum_{\ell=1}^{\infty}\frac{c_{\ell}^{\frac{2}{p}}}{\ell^{-\frac{2s}{p}}}c^{2-\frac{2}{p}}}$
$\displaystyle\leq\left(\sum_{\ell=1}^{\infty}\frac{c_{\ell}^{2}}{\ell^{-2s}}\right)^{\frac{1}{2p}}\left(\sum_{\ell=1}^{\infty}c_{\ell}^{(2-\frac{2}{p})(\frac{p}{p-1})}\right)^{\frac{1}{2}(1-\frac{1}{p})}$
$\displaystyle=\left(\sum_{\ell=1}^{\infty}\frac{c_{\ell}^{2}}{\ell^{-2s}}\right)^{\frac{1}{2p}}\left(\sum_{\ell=1}^{\infty}c_{\ell}^{2}\right)^{\frac{1}{2}(1-\frac{1}{p})}.$

Choosing $p=\frac{s}{3}$, we finally have that

$\displaystyle
b\left(\sum_{\ell=1}^{\infty}\frac{c_{\ell}^{2}}{\ell^{-2s}}\right)^{\frac{1}{2p}}\left(\sum_{\ell=1}^{\infty}c_{\ell}^{2}\right)^{\frac{1}{2}(1-\frac{1}{p})}\sqrt{\zeta\Bigl{(}\frac{2s}{p}-4\Big{)}}$
$\displaystyle=b\left\|f\right\|_{s}^{\frac{1}{p}}\left\|f\right\|_{2}^{1-\frac{1}{p}}\sqrt{\zeta\Bigl{(}\frac{2s}{p}-4\Big{)}}$
$\displaystyle=\frac{\pi}{\sqrt{6}}b\left\|f\right\|_{s}^{\frac{3}{s}}\left\|f\right\|_{2}^{\frac{s-3}{s}}$

by involving Euler’s famous formula $\zeta(2)=\frac{\pi^{2}}{6}$. This is the
assertion. ∎

#### Convergence in $L^{2}$ implies convergence in $L^{\infty}$:

Specifically, consider a sequence of functions $f_{n}$ with slowly increasing
norm $\|f_{n}\|_{s}$ and limit $\|f\|_{s}<\infty$. Then, for
$\|f_{n}-f\|_{2}\to 0$ sufficiently fast, it follows from Theorem 4.2 that
$\|f_{n}-f\|_{\infty}\to 0$.

######  Remark 4.3.

Fischer and Steinwart [11] study convergence in an interpolation space between
$\mathcal{H}_{k}$ and $L^{2}$, which the authors call _power spaces_. The norm
considered in Fischer and Steinwart [11], however, is stronger than the norm
$\|\cdot\|_{s}$ considered above.

###  4.3 Nyström method

The main result in Rudi et al. [14, Theorem 1] relates the function
$\mathcal{N}_{\infty}(\lambda)$ to the Nyström method. Their paper ensures
that the Nyström method does not require more than
$\mathcal{O}\left(\mathcal{N}_{\infty}(\lambda)\ln\lambda^{-1}\right)$
supporting points.

The results established in Section 3 above provides explicit access to the
function $\mathcal{N}_{\infty}(\lambda)$, so that their main result can be
refined and enhanced to the following form.

######  Theorem 4.4 (Cf. Rudi et al. 14, Theorem 1).

Let
$\mathcal{E}(f)\coloneqq\iint_{\mathcal{X}\times\mathbb{R}}\bigl{(}f(x)-y\bigr{)}^{2}\rho(dx,dy)$
be the common error function. Given the assumptions of Theorem 1 in [14], it
holds that the Nyström-approximation $\hat{f}_{\lambda,m}$ with regression
parameter $\lambda$ satisfies

$\mathcal{E}(\hat{f}_{\lambda,m})-\mathcal{E}(f_{\mathcal{H}})\leq
q^{2}n^{\frac{2\nu+1}{2nu+\gamma+1}}$

for at least

$m\geq(67\lor
5\left(9c_{p}\left(3c_{\sigma}s(\lambda)+2\right)^{2d}+1\right)\ln\lambda^{-1}$
(4.5)

supporting points. The reference provides the constant $q$ and $\nu$
explicitly.

###### Proof.

Invoking the bound (3.7) for $\mathcal{N}_{\infty}(\lambda)$, the result is
immediate from Rudi et al. [14, Theorem 1]. ∎

The adapter result (4.5) gives an explicit selection criterion for the
critical number of support points in the Nyström method.

##  5 Summary

The novel approach of this paper considers an explicit approximation of the
kernel function in the range of the associated integral operator. To this end
we provide an explicit weight function by matching the initial Taylor
coefficients of the kernel.

The approach has numerous consequences in theory and in applications. We
provide bounds for the eigenfunctions, which grow only quadratic in the
enumeration index. An interpolation inequality provided relates convergence in
uniform norm and the weaker convergence in $L^{2}$ for smooth functions. The
methods established justify smaller regression parameters for regression
problems, which is of particular importance for low-rank approximation
techniques.

## References

  * Bach [2013] F. Bach.  Sharp analysis of low-rank kernel matrix approximations.  In S. Shalev-Shwartz and I. Steinwart, editors, _Proceedings of the 26th Annual Conference on Learning Theory_ , volume 30 of _Proceedings of Machine Learning Research_ , pages 185–209, Princeton, NJ, USA, 12–14 Jun 2013. PMLR.  URL https://proceedings.mlr.press/v30/Bach13.html.
  * Berlinet and Thomas-Agnan [2004] A. Berlinet and C. Thomas-Agnan.  _Reproducing Kernel Hilbert Spaces in Probability and Statistics_.  Springer US, 2004.  doi:10.1007/978-1-4419-9096-9.
  * Caponnetto and De Vito [2006] A. Caponnetto and E. De Vito.  Optimal rates for the regularized least-squares algorithm.  _Foundations of Computational Mathematics_ , 7(3):331–368, Aug. 2006.  ISSN 1615-3383.  doi:10.1007/s10208-006-0196-8.
  * Cucker and Zhou [2007] F. Cucker and D. X. Zhou.  _Learning Theory: An Approximation Theory Viewpoint_.  Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2007.  doi:10.1017/CBO9780511618796.
  * Diaconis et al. [2008] P. Diaconis, S. Goel, and S. Holmes.  Horseshoes in multidimensional scaling and local kernel methods.  _The Annals of Applied Statistics_ , 2(3):777 – 807, 2008.  doi:10.1214/08-AOAS165.
  * Diederichs and Iske [2019] B. Diederichs and A. Iske.  Improved estimates for condition numbers of radial basis function interpolation matrices.  _Journal of Approximation Theory_ , 238:38–51, Feb. 2019\.  ISSN 0021-9045.  doi:10.1016/j.jat.2017.10.004.
  * Dommel [2024] P. Dommel.  A bound on the maximal marginal degrees of freedom, 2024.  URL https://arxiv.org/abs/2402.12885.
  * Dommel and Pichler [2023] P. Dommel and A. Pichler.  Dynamic programming for data independent decision sets.  _Journal of Convex Analysis_ , 2023.
  * Drineas and Mahoney [2005] P. Drineas and M. Mahoney.  On the nyström method for approximating a gram matrix for improved kernel-based learning.  _Journal of Machine Learning Research_ , 6:2153–2175, 12 2005.
  * Feller [1968] W. Feller.  _An Introduction to Probability Theory and Its Applications_ , volume 1.  Wiley, January 1968.  ISBN 0471257087.  URL http://www.amazon.ca/exec/obidos/redirect?tag=citeulike04-20{&}path=ASIN/0471257087.
  * Fischer and Steinwart [2020] S. Fischer and I. Steinwart.  Sobolev norm learning rates for regularized least-squares algorithms.  _J. Mach. Learn. Res._ , 21(1), jan 2020.  ISSN 1532-4435.
  * Honarkhah and Caers [2010] M. Honarkhah and J. Caers.  Stochastic simulation of patterns using distance-based pattern modeling.  _Mathematical Geosciences_ , 42(5):487–517, Apr. 2010.  ISSN 1874-8953.  doi:10.1007/s11004-010-9276-7.
  * Park et al. [2022] H. Park, Z. Jia, and G. A. Hanasusanto.  Data-driven stochastic dual dynamic programming: Performance guarantees and regularization schemes.  2022\.  URL https://optimization-online.org/?p=21376.
  * Rudi et al. [2015] A. Rudi, R. Camoriano, and L. Rosasco.  Less is more: Nyström computational regularization.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015.  URL https://proceedings.neurips.cc/paper_files/paper/2015/file/03e0704b5690a2dee1861dc3ad3316c9-Paper.pdf.
  * Rudi et al. [2017] A. Rudi, L. Carratino, and L. Rosasco.  Falkon: An optimal large scale kernel method.  In _Advances in Neural Information Processing Systems_ , 2017.  URL https://api.semanticscholar.org/CorpusID:25900554.
  * Schölkopf [1997] B. Schölkopf.  _Support Vector Learning_.  1997\.  URL https://pure.mpg.de/rest/items/item_1794215/component/file_3214422/content.
  * Schölkopf et al. [2004] B. Schölkopf, K. Tsuda, and J.-P. Vert.  _Kernel Methods in Computational Biology_.  The MIT Press, July 2004.  ISBN 9780262256926.  doi:10.7551/mitpress/4057.001.0001.
  * Shawe-Taylor et al. [2002] J. Shawe-Taylor, C. Williams, N. Cristianini, and J. Kandola.  _On the Eigenspectrum of the Gram Matrix and Its Relationship to the Operator Eigenspectrum_ , pages 12–12.  Springer Berlin Heidelberg, 2002.  ISBN 9783540361824.  doi:10.1007/3-540-36182-0_3.
  * Shi et al. [2009] T. Shi, M. Belkin, and B. Yu.  Data spectroscopy: Eigenspaces of convolution operators and clustering.  _The Annals of Statistics_ , 37(6B):3960 – 3984, 2009.  doi:10.1214/09-AOS700.  URL https://doi.org/10.1214/09-AOS700.
  * Steinwart and Christmann [2008] I. Steinwart and A. Christmann.  _Support vector machines_.  Springer Science & Business Media, 2008.  doi:https://doi.org/10.1007/978-0-387-77242-4.
  * Steinwart et al. [2009] I. Steinwart, D. R. Hush, and C. Scovel.  Optimal rates for regularized least squares regression.  In _Proceedings of the 22nd Annual Conference on Learning Theory_ , pages 79–93, 2009.
  * Sterge and Sriperumbudur [2021] N. Sterge and B. K. Sriperumbudur.  Statistical optimality and computational efficiency of nyström kernel pca.  _Journal of Machine Learning Research_ , 23:337:1–337:32, 2021.  URL https://api.semanticscholar.org/CorpusID:234777746.
  * Williams and Seeger [2000] C. Williams and M. Seeger.  Using the nyström method to speed up kernel machines.  In T. Leen, T. Dietterich, and V. Tresp, editors, _Advances in Neural Information Processing Systems_ , volume 13. MIT Press, 2000.  URL https://proceedings.neurips.cc/paper_files/paper/2000/file/19de10adbaa1b2ee13f77f679fa1483a-Paper.pdf.
  * Zhang et al. [2007] J. Zhang, M. Marszałek, S. Lazebnik, and C. Schmid.  Local features and kernels for classification of texture and object categories: A comprehensive study.  _International Journal of Computer Vision_ , 73(2):213–238, June 2007.  ISSN 0920-5691.  doi:10.1007/s11263-006-9794-4.
  * Zhang et al. [2013] Y. Zhang, J. Duchi, and M. Wainwright.  Divide and conquer kernel ridge regression.  In S. Shalev-Shwartz and I. Steinwart, editors, _Proceedings of the 26th Annual Conference on Learning Theory_ , volume 30 of _Proceedings of Machine Learning Research_ , pages 592–617, Princeton, NJ, USA, 12–14 Jun 2013. PMLR.  URL https://proceedings.mlr.press/v30/Zhang13.html.

##  Appendix A Gaussian approximation

This section provides the proof of the formula (3.3), which is of fundamental
importance for every other bound provided in Section 3. The proof of the bound
(3.3) builds on the error estimate (2.11), which involves the Taylor remainder
of the exponential series. To this end we utilize the formula

$\sum_{\ell=n}^{\infty}\alpha^{\ell}=\frac{\alpha^{n}}{1-\alpha}$ (A.1)

of the truncated geometric series as well as Stirling’s approximation

$\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}<n!,$ (A.2)

which relates the factorial with the exponential function. For future
reference convenience of the reader, we restate Theorem 3.1.

######  Theorem A.1.

Let $k$ be the $d$-dimensional Gaussian kernel with width parameter $\sigma$.
Setting $c_{\sigma}\coloneqq\max\left\\{1,2e\sigma d\right\\}$,
$c_{p}=\sup_{z\in[0,1]^{d}}p(z)^{-1}$ and

$C(\sigma,m)\coloneqq\frac{1}{1-\frac{\sigma
ed}{\left\lfloor\frac{m}{2}\right\rfloor}},$

the uniform bound

$\sup_{x\in[0,1]^{d}}\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{\infty}\leq(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\,C(\sigma,m)\left(\left\lfloor\frac{m}{2}\right\rfloor\frac{1}{\sigma
ed}\right)^{\left\lfloor\frac{m}{2}\right\rfloor}$

holds for $W_{m}^{x}$ defined in (2.6) for $m>c_{\sigma}+1$.

Specifically, for $m(s)\coloneqq 3c_{\sigma}s+2$, we have that

$\sup_{x\in[0,1]^{d}}\left\|L_{k}W_{m(td)}^{x}-k_{x}\right\|_{\infty}\leq
3(t\,d)^{-3t\,d}$ (A.3)

whenever
$t\geq\max\left\\{\frac{\ln(3)+(d-1)\ln(2)+\frac{1}{2}\ln(c_{p})+d\ln(3c_{\sigma}d)}{2d\ln(3)},\
1\right\\}.$

###### Proof.

Employing the inequality (2.11) involving the Taylor coefficients, we have
that

$\sup_{x\in[0,1]^{d}}\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{\infty}\leq(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\sum_{\ell=\left\lfloor\frac{m-1}{2}\right\rfloor+1}^{\infty}\frac{\sigma^{\ell}}{\ell!}d^{\ell}\leq(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\sum_{\ell=\left\lfloor\frac{m}{2}\right\rfloor}^{\infty}\frac{\sigma^{\ell}}{\ell!}d^{\ell},$
(A.4)

as
$\left\lfloor\frac{m}{2}\right\rfloor\leq\left\lfloor\frac{m-1}{2}\right\rfloor+1$.
Further, invoking Stirling’s approximation (A.2) for the right-hand side of
(A.4), it follows that

$\displaystyle(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\sum_{\ell=\left\lfloor\frac{m}{2}\right\rfloor}^{\infty}\sigma^{\ell}\left(\ell!\right)^{-1}d^{\ell}$
$\displaystyle\leq(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\sum_{\ell=\left\lfloor\frac{m}{2}\right\rfloor}^{\infty}\left(\sqrt{2\pi\ell}\left(\frac{\ell}{\sigma
ed}\right)^{\ell}\right)^{-1}.$

Now assume that $m$ satisfies the inequality
$1<\left\lfloor\frac{m}{2}\right\rfloor\left(\sigma ed\right)^{-1}$, then we
have from identity (A.1) of the truncated geometric series that

$\displaystyle\sup_{x\in[0,1]^{d}}\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{\infty}$
$\displaystyle\leq(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\sum_{\ell=\left\lfloor\frac{m}{2}\right\rfloor}^{\infty}\left(\frac{\ell}{\sigma
ed}\right)^{-\ell}$
$\displaystyle\leq(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})\frac{1}{1-\frac{\sigma
ed}{\left\lfloor\frac{m}{2}\right\rfloor}}\left(\left\lfloor\frac{m}{2}\right\rfloor\frac{1}{\sigma
ed}\right)^{-\left\lfloor\frac{m}{2}\right\rfloor}$ (A.5)
$\displaystyle=(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})C(\sigma,m)\left(\left\lfloor\frac{m}{2}\right\rfloor\frac{1}{\sigma
ed}\right)^{-\left\lfloor\frac{m}{2}\right\rfloor},$ (A.6)

which is the first assertion.

For the second assertion let $m=m(td)=6c_{\sigma}td+2$ and observe for the
constant $C(\sigma,m)$ that

$\displaystyle C(\sigma,m)$ $\displaystyle=\frac{1}{1-\frac{\sigma
ed}{\left\lfloor\frac{m}{2}\right\rfloor}}\leq\frac{1}{1-\frac{\sigma
ed}{3(\sigma ed)td}}\leq\frac{1}{1-\frac{1}{3td}}\leq\frac{3}{2}$

holds for every $t\geq 1$. Furthermore, employing $m(td)$, as well as
$C(\sigma,m)\leq\frac{3}{2}$, and arguing as above, we get for (A.6) that

$\displaystyle(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})C(\sigma,m)\left(\left\lfloor\frac{m}{2}\right\rfloor\frac{1}{\sigma
ed}\right)^{-\left\lfloor\frac{m}{2}\right\rfloor}$
$\displaystyle\leq\frac{3}{2}(1+c_{p}^{\nicefrac{{1}}{{2}}}m(t)^{d})\left(\frac{3\sigma
ed^{2}t}{\sigma ed}\right)^{-\left\lfloor\frac{m}{2}\right\rfloor}$
$\displaystyle\leq\frac{3}{2}(1+c_{p}^{\nicefrac{{1}}{{2}}}(3c_{\sigma}td+2)^{d})\left(3td\right)^{-3dt}$
$\displaystyle\leq\frac{3}{2}\left(3td\right)^{-3dt}+\frac{3}{2}2^{d-1}c_{p}^{\nicefrac{{1}}{{2}}}(3c_{\sigma}td)^{d}\left(3td\right)^{-3dt}+\frac{3}{2}2^{2d-1}\left(3td\right)^{-3dt},$

where we utilize $(a+b)^{d}\leq 2^{d-1}(a^{d}+b^{d})$ for the last inequality.
The latter is bounded by

$\frac{3}{2}2^{2d-1}\left(3td\right)^{-3dt}\leq(td)^{-3dt}$

as well as the middle term by

$\displaystyle
2^{d-1}c_{p}^{\nicefrac{{1}}{{2}}}(3c_{\sigma}td)^{d}3^{-3td}(td)^{-3td}$
$\displaystyle=\frac{1}{2}(e^{\ln(3)+(d-1)\ln(2)+\ln(c_{p}^{\nicefrac{{1}}{{2}}})+d\ln(3c_{\sigma}td)-\ln(3)3td})(td)^{-3td}$
$\displaystyle\leq\frac{1}{2}(e^{\ln(3)+(d-1)\ln(2)+\ln(c_{p}^{\nicefrac{{1}}{{2}}})+d\ln(3c_{\sigma}d)-\ln(3)2td})(dt)^{-3td}$
$\displaystyle\leq\frac{1}{2}(td)^{-3td}$

whenever
$t\geq\frac{\ln(3)+(d-1)\ln(2)+\ln(c_{p}^{\nicefrac{{1}}{{2}}})+d\ln(3\max\left\\{c_{\sigma},1\right\\}d)}{2d\ln(3)}.$
Hence, choosing

$t\geq\max\left\\{\frac{\ln(3)+(d-1)\ln(2)+\ln(c_{p}^{\nicefrac{{1}}{{2}}})+d\ln(3\max\left\\{c_{\sigma},1\right\\}d)}{2d\ln(3)},1\right\\},$

we have that

$(1+c_{p}^{\nicefrac{{1}}{{2}}}m^{d})C(\sigma,m)\left(\left\lfloor\frac{m}{2}\right\rfloor\frac{1}{\sigma
ed^{2}}\right)^{\left\lfloor\frac{m}{2}\right\rfloor}\leq\frac{3}{2}\left(3dt\right)^{-3dt}+\frac{3}{2}(dt)^{-3dt}\leq
3(dt)^{-3dt},$

which is the assertion. ∎

Building on the bound (3.3) in the uniform norm, we establish a bound in the
RKHS norm in Proposition 3.2. To this end the following technical Lemma is of
crucial importance.

######  Lemma A.2.

Given the assumptions of Theorem 3.1, the bound

$\sup_{x\in[0,1]^{d}}\left\langle
L_{k}W_{m}^{x}-k_{x},W_{m}^{x}\right\rangle_{L^{2}}\leq 6(td)^{-2td}$ (A.7)

holds whenever $t\geq\max\left\\{c_{0},c_{1},c_{2}\right\\}$ with constants

$\displaystyle c_{1}$
$\displaystyle=\frac{(2d-1)\ln(2)+d\ln(3c_{\sigma})+\frac{1}{2}\ln(c_{p})}{d}+1\hskip
10.00002pt\text{and}$ $\displaystyle c_{2}$
$\displaystyle=\frac{(2d-1)\ln(2)+\frac{1}{2}\ln(c_{p})}{d}.$

###### Proof.

Employing the Cauchy–Schwarz inequality, we have from (3.3) that

$\displaystyle\left\langle L_{k}W_{m}^{x}-k_{x},W_{m}^{x}\right\rangle_{2}$
$\displaystyle\leq\left\|L_{k}W_{m}^{x}-k_{x}\right\|_{L^{2}}\left\|W_{m}^{x}\right\|_{L^{2}}\leq
3(td)^{-3td}c_{p}^{\nicefrac{{1}}{{2}}}m^{d}$

whenever $m$ (and $t$) are chosen with respect to the constraints Theorem 3.1.
Involving $m=m(td)$ we further observe that

$\displaystyle 3(td)^{-3td}c_{p}^{\nicefrac{{1}}{{2}}}(3c_{\sigma}td+2)^{d}$
$\displaystyle\leq
2^{d-1}3(td)^{-3td}c_{p}^{\nicefrac{{1}}{{2}}}(3c_{\sigma}td)^{d}+2^{2d-1}3(td)^{-3td}c_{p}^{\nicefrac{{1}}{{2}}}.$
(A.8)

For the second term in (A.8) it follows that

$2^{2d-1}3(td)^{-3td}c_{p}^{\nicefrac{{1}}{{2}}}=2^{2d-1}(td)^{-td}c_{p}^{\nicefrac{{1}}{{2}}}3(td)^{-2td}\leq
3(td)^{-2td}$

whenever $t\geq\frac{(2d-1)\ln(2)+\frac{1}{2}\ln(c_{p})}{d}\coloneqq c_{2}.$
Reformulating the first term in (A.8) to

$2^{d-1}3(td)^{-3td}c_{p}^{\nicefrac{{1}}{{2}}}(3c_{\sigma}td)^{d}=3e^{-td\ln(td)+(2d-1)\ln(2)+\frac{1}{2}\ln(c_{p})+d\ln(3c_{\sigma}td)}(td)^{-2td}$

we get for the exponent that

$\displaystyle-
td\ln(td)+(d-1)\ln(2)+\frac{1}{2}\ln(c_{p})+d\ln(3c_{\sigma}td)$
$\displaystyle=$
$\displaystyle-d(t-1)\ln(td)+(d-1)\ln(2)+\frac{1}{2}\ln(c_{p})+d\ln(3c_{\sigma})$
$\displaystyle\leq$
$\displaystyle-d(t-1)\ln(2)+(d-1)\ln(2)+\frac{1}{2}\ln(c_{p})+d\ln(3c_{\sigma}).$

Thus, for

$t\geq\frac{(2d-1)\ln(2)+d\ln(3c_{\sigma})+\frac{1}{2}\ln(c_{p})}{d}+1\eqqcolon
c_{1}$

it follows that

$2^{d-1}3(td)^{-3td}c_{p}^{\nicefrac{{1}}{{2}}}(3c_{\sigma}td)^{d}\leq
3(td)^{-2td}.$

Combining the estimates of the terms in (A.8), we have for
$t\geq\max\left\\{c_{1},c_{2}\right\\}$ that

$\left\langle L_{k}W_{m}^{x}-k_{x},W_{m}^{x}\right\rangle_{2}\leq
6(td)^{-2td}$

and thus the assertion. ∎

##  Appendix B  Decay of eigenvalues

This section provides a lower bound on the eigenvalues
$(\mu_{\ell})_{\ell=1}^{\infty}$ of the operator $L_{k}$ associated with the
Gaussian kernel. We address the univariate case first, which is then extended
to the multivariate case. As a starting point we consider the most elementary
setting, i.e., $\mathcal{X}=[0,1]$, equipped with the uniform measure
$P=\mathcal{U}[0,1]$. The following lemma provides the precise eigenvalue
bound.

######  Lemma B.1 (Maximal decay of eigenvalues).

Let $k$ be the Gaussian kernel, $\mathcal{X}=[0,1]$ as well as
$P=\mathcal{U}[0,1]$. For every $\ell\in\mathbb{N}$ it holds that

$\mu_{\ell}\geq\frac{1}{\ell}C(\sigma)e^{-a_{\sigma}(\ell-1)^{2}},$ (B.1)

where $a_{\sigma}=8\cdot\frac{4\pi^{2}}{16\sigma}$ and $C(\sigma)$ is a
constant depending on the width parameter $\sigma$.

###### Proof.

Let $x_{1},\dots,x_{\ell}$ be independent random variables following the
uniform measure $\mathcal{U}[0,1]$. Let $K=(k(x_{i},x_{j}))_{i,j=1}^{\ell}$ be
the Gramian matrix and invoking Shawe-Taylor et al. [18, Proposition A], it
follows that

$\mu_{\ell}\geq\frac{1}{\ell}\operatorname{{\mathds{E}}}\lambda_{\min}(K),$

where $\lambda_{\min}(K)$ is the smallest eigenvalue of the matrix $K$ and the
expectation is with respect to the samples. Further, employing the result of
Diederichs and Iske [6, Example 2.6], we get with
$M\coloneqq\min_{i,j\leq\ell,i\neq j}\left|x_{i}-x_{j}\right|$ and (D.4) in
the auxiliary Lemma D.2 below (Appendix D) that

$\displaystyle\operatorname{{\mathds{E}}}\lambda_{\min}(K)$
$\displaystyle\geq\operatorname{{\mathds{E}}}M^{-1}\tilde{C}(\sigma)e^{-\frac{4\pi^{2}}{16M^{2}\sigma}}\geq\tilde{C}(\sigma)\operatorname{{\mathds{E}}}e^{-\frac{4\pi^{2}}{16M^{2}\sigma}}\geq
C(\sigma)e^{-a_{\sigma}(\ell-1)^{2}},$

as $M<1$, and where $C(\sigma)=C\cdot\tilde{C}(\sigma)$ with $C$ from as in
(D.4). This is the assertion. ∎

Extending the univariate case to the multivariate setting builds on the
product structure of the Gaussian kernel, that is, on
$\prod_{i=1}^{d}e^{-\sigma(x_{i}-y_{i})^{2}}=e^{-\sigma\sum_{i=1}^{n}(x_{i}-y_{i})^{2}}$.
Indeed, provided that the underlying measure is $\mathcal{U}[0,1]^{d}$, the
spectrum of the corresponding operator $L_{k}$ is

$\left\\{\prod_{i=1}^{d}\mu_{\ell_{i}}\colon\ell_{1},\dots,\ell_{d}\in\mathbb{N}\right\\},$

where $\mu_{\ell_{i}}$ is the $\ell_{i}$th eigenvalue in the univariate
setting. This is immediate, as every eigenfunction in the multivariate case is
a product of elementary eigenfunctions,
$\prod_{i=1}^{d}\varphi_{\ell_{i}}(x_{i})$. We may assume the multivariate
eigenvalues $\mu_{\ell}^{(d)}$ arranged in non-increasing order such that

$\left(\mu_{\ell}^{(d)}\right)_{\ell=1}^{\infty}=\left(\prod_{i=1}^{d}\mu_{\ell_{i}}\colon\ell_{i}\in\mathbb{N}\right)$
(B.2)

and $\mu_{1}^{(d)}\geq\mu_{2}^{(d)}\geq\dots$.

The subsequent auxiliary and combinatorial lemmata utilize the structure of
the spectrum to infer the maximal decay rate of the sequence
$\mu_{\ell}^{(d)}$. The first is a general combinatorial result, with which we
assess the eigenvalue decay in the second.

######  Lemma B.2.

It holds that

$\sum_{\begin{subarray}{c}i_{1}+\dots+i_{d}\leq n,\\\
i_{j}\in\mathbb{N}\end{subarray}}1\geq\frac{(n-1)^{d}}{(d-1)^{d-1}}-d$ (B.3)

for $n\geq d\geq 2.$

###### Proof.

We proof the assertion by employing on the _stars and bars formula_

$\sum_{i_{1}+\dots+i_{d}=i}1=\binom{i-1}{d-1},$

where $i_{j}\geq 1$ are positive integers (cf. Feller 10, p. 38) and
$i\in\mathbb{N}$. We have that

$\displaystyle\sum_{i_{1}+\dots+i_{d}\leq n}1$
$\displaystyle=\sum_{i=d}^{n}\sum_{i_{1}+\dots+i_{d}=i}1=\sum_{i=d}^{n}\binom{i-1}{d-1}\geq\sum_{i=d}^{n}\left(\frac{i-1}{d-1}\right)^{d-1}\geq\sum_{i=1}^{n}\left(\frac{i-1}{d-1}\right)^{d-1}-d,$
(B.4)

where we utilize that

$\binom{i-1}{d-1}=\frac{(i-1)(i-2)\cdots(i-d+1)}{(d-1)(d-2)\cdots
1}=\prod_{j=1}^{d-1}\frac{i-j}{d-j}\geq\prod_{j=1}^{d-1}\frac{i-1}{d-1}=\left(\frac{i-1}{d-1}\right)^{d-1}.$

Furthermore, employing

$\frac{n^{d}}{d}=\int_{0}^{n}x^{d-1}dx\leq\sum_{i=1}^{n}k^{d-1}$

in (B.4), it follows that

$\displaystyle\sum_{i=1}^{n}\left(\frac{i-1}{d-1}\right)^{d-1}-d$
$\displaystyle=\frac{1}{(d-1)^{d-1}}\sum_{i=1}^{n}\left(i-1\right)^{d-1}-d$
$\displaystyle=\frac{1}{(d-1)^{d-1}}\sum_{k=0}^{n-1}k^{d-1}-d\geq\frac{(n-1)^{d}}{d(d-1)^{d-1}}-d$

and thus the assertion. ∎

######  Lemma B.3.

Let $\mu_{\ell}\geq e^{-\rho\ell^{2}}$ for every $\ell\in\mathbb{N}$. Then the
sequence $\mu_{\ell}^{(d)}$ from (B.2) satisfies

$\mu_{\ell}^{(d)}\geq C\exp(-c\rho(\ell+d)^{\frac{2}{d}})$ (B.5)

for all $\ell\in\mathbb{N}$ and $d\geq 2$ for some $c>0$ and $C>0$.

###### Proof.

We first determine the number of combinations of
$\mu_{i_{1}},\dots,\mu_{i_{d}}$ for which the product
$\prod_{k=1}^{d}\mu_{i_{k}}$ is larger than $\exp(-\rho(\lambda+2)^{2})$ for
some threshold parameter $\lambda>0$. It holds that
$\prod_{i=1}^{d}\mu_{\ell_{i}}\geq
e^{-\rho\,i_{1}^{2}-\ldots-\rho\,i_{d}^{2}}\geq
e^{-\rho(i_{1}+\dots+i_{d})^{2}}\geq e^{-\rho(\lambda+2)^{2}}$, provided that
$i_{1}+\dots+i_{d}\leq\lambda+2$. From (B.3) we deduce that

$\sum_{i_{1}+\dots+i_{d}\leq\lambda+2}1\geq\frac{\left\lfloor\lambda+1\right\rfloor^{d}}{d(d-1)^{(d-1)}}-d$

and thus

$\mu_{\ell}^{(d)}\geq e^{-\rho(\lambda+2)^{2}}$

for all
$\ell\leq\frac{\left\lfloor\lambda+1\right\rfloor^{d}}{d(d-1)^{(d-1)}}-d.$
Choosing
$\lambda\coloneqq\bigl{(}d(d-1)^{d-1}(\ell+d)\bigr{)}^{\nicefrac{{1}}{{d}}}$
and employing $(a+b)^{2}\leq 2a^{2}+2b^{2}$, we get that

$\displaystyle\mu_{\ell}^{(d)}$ $\displaystyle\geq
e^{-\rho\left((d(d-1)^{d-1}(\ell+d)\bigr{)}^{\nicefrac{{1}}{{d}}}+2\right)^{2}}\geq
e^{-\rho 2^{3}}e^{-\rho
2d^{\nicefrac{{2}}{{d}}}(d-1)^{\frac{2(d-1)}{d}}(\ell+d)^{\nicefrac{{2}}{{d}}}}.$

The assertion follows by setting $C\coloneqq\exp(-8\rho)$ and $c\coloneqq
2d^{\nicefrac{{2}}{{d}}}(d-1)^{\frac{2(d-1)}{d}}$.

The bound (B.5) already implies (3.10), provided that the underlying measure
is uniform, i.e, the Lebesgue measure. The following lemma extends the
assertion for more general probability measures. ∎

######  Lemma B.4.

Let $\mathcal{X}=[0,1]^{d}$ and consider the operators $L_{k}\colon
L^{2}(\mathcal{X},\lambda)\to L^{2}(\mathcal{X},\lambda)$ and $L_{k}^{p}\colon
L^{2}(\mathcal{X},P)\to L^{2}(\mathcal{X},P)$ with

$(L_{k}f)(y)=\int_{\mathcal{X}}k(x,y)f(x)dx\hskip
10.00002pt(L_{k}^{P}f)(y)=\int_{\mathcal{X}}k(x,y)f(x)p(x)dx.$

Here, $\lambda$ is the Lebesgue (uniform) measure and $P$ is a probability
measure, satisfying the condition
$0<p_{\min}\coloneqq\inf_{x\in\mathcal{X}}p(x)\leq
p_{\max}\coloneqq\sup_{x\in\mathcal{X}}p(x)<\infty$. The eigenvalues
$(\mu_{\ell}^{(d)})_{\ell}$ of $L_{k}$ ($(\mu_{\ell,p}^{(d)})_{\ell}$ of
$L_{k}^{p}$, resp.), satisfy the relation

$\mu_{\ell,p}^{(d)}\geq\frac{p_{\min}^{2}}{p_{\max}^{2}}\mu_{\ell}^{(d)}$
(B.6)

for all $\ell\in\mathbb{N}.$

###### Proof.

By the Courant–Fischer–Weyl min-max principle it holds that

$\displaystyle\mu_{\ell,p}^{(d)}$
$\displaystyle=\max_{\dim(S_{k})=k}\min_{\begin{subarray}{c}\begin{subarray}{c}x\in
S_{k}\\\
\left\|x\right\|_{L^{2}(P)}=1\end{subarray}\end{subarray}}\left\langle
L_{k}^{p}x,x\right\rangle_{L^{2}(P)}$
$\displaystyle=\max_{\dim(S_{k})=k}\min_{\begin{subarray}{c}x\in
S_{k}\end{subarray}}\left(\frac{\|x\|_{\lambda}}{\|x\|_{p}}\right)^{2}\left\langle
L_{k}^{p}\frac{x}{\|x\|_{\lambda}},\frac{x}{\|x\|_{\lambda}}\right\rangle_{L^{2}(P)}$
$\displaystyle\geq\max_{\dim(S_{k})=k}\min_{\begin{subarray}{c}\begin{subarray}{c}x\in
S_{k}\\\
\left\|x\right\|_{L^{2}(\lambda)}=1\end{subarray}\end{subarray}}p_{\max}^{-2}\left\langle
L_{k}^{p}x,x\right\rangle_{L^{2}(P)}.$

It follows further that

$\displaystyle\mu_{\ell,p}^{(d)}$
$\displaystyle\geq\max_{\dim(S_{k})=k}\min_{\begin{subarray}{c}\begin{subarray}{c}x\in
S_{k}\\\
\left\|x\right\|_{L^{2}(\lambda)}=1\end{subarray}\end{subarray}}p_{\max}^{-2}\left\langle
L_{k}^{p}x,x\right\rangle_{L^{2}(P)}$
$\displaystyle\geq\max_{\dim(S_{k})=k}\min_{\begin{subarray}{c}\begin{subarray}{c}x\in
S_{k}\\\
\left\|x\right\|_{L^{2}(\lambda)}=1\end{subarray}\end{subarray}}p_{\max}^{-2}p_{\min}^{2}\left\langle
L_{k}x,x\right\rangle_{L^{2}(\lambda)}=\frac{p_{\min}^{2}}{p_{\max}^{2}}\mu_{\ell}^{(d)},$

as $0\leq p(x)p(y)-p_{\min}^{2}$. Hence, the assertion. ∎

We now combine the results of the preceding lemmata to bound the eigenvalues
of the $d$-dimensional Gaussian kernel for general measures.

######  Lemma B.5 (Maximal decay of eigenvalues).

For every $\ell\in\mathbb{N}$ it holds that

$\mu_{\ell}^{(d)}\geq\frac{p_{\min}^{2}}{p_{\max}^{2}}C(d,\sigma)e^{-c_{\sigma,d}(\ell+d)^{\frac{2}{d}}},$
(B.7)

where $c_{d,\sigma}$ and $C(d,\sigma)$ are constants depending on the
dimension $d$ and the bandwidth $\sigma$.

###### Proof.

We show the assertion only for the uniform measure $\mathcal{U}[0,1]^{d}$, as
the result for more general design measures follows immediately by (B.6). For
the eigenvalues $\mu_{\ell}$ in the univariate setting, we have from (B.1)
that

$\mu_{\ell}\geq\frac{1}{\ell}C(\sigma)e^{-a_{\sigma}(\ell-1)^{2}}\geq
C(\sigma)e^{-\tilde{a}_{\sigma}\ell^{2}}$ (B.8)

where $\tilde{a}_{\sigma}$ is chosen such that

$\tilde{a}_{\sigma}\ell^{2}\geq\ln(\ell)+a_{\sigma}(\ell-1)^{2},\qquad\ell=1,2,\dots.$

Combining (B.8) with (B.5) (cf. Lemma B.3), it follows that

$\mu_{\ell}^{(d)}\geq
C(\sigma)^{d}C\exp(-\tilde{a}_{\sigma}c(\ell+d)^{\frac{2}{d}})$

as $C(\sigma)$ appears in every factor of the product
$\prod_{i=1}^{d}\mu_{\ell_{i}}$. Setting $c_{\sigma,d}\coloneqq\tilde{a}c$
reveals the assertion. ∎

##  Appendix C  Concentration

This section provides a proof of the operator bound (4.3). To this end, we
restate the following concentration bound for random operators on Hilbert
spaces, which we then subsequently.

######  Proposition C.1 (See Fischer and Steinwart 11, Theorem A.3).

Let $(\Omega,\mathcal{B},P)$ be a probability space, $H$ a separable Hilbert
space, and $\xi\colon\Omega\to\mathcal{L}_{2}(H)$ be a random variable with
values in the set of self-adjoint Hilbert-Schmidt operators. Furthermore, let
the operator norm be uniformly, i.e., $\left\|\xi\right\|_{H\to H}\leq B$
$P$-a.s. and $V$ be a self-adjoint positive semi-definite trace class operator
with $\operatorname{{\mathds{E}}}_{P}\xi^{2}\preccurlyeq V$, i.e.
$V-\operatorname{{\mathds{E}}}_{P}\xi^{2}$ is positive semi-definite. Then,
for $g(V)\coloneqq\ln(2e\operatorname*{trace}(V)\left\|V\right\|_{H\to
H}^{-1})$, $\tau\geq 1$ and $n\geq 1$, the following concentration inequality
is satisfied:

$P^{n}\bigg{(}\left\|\frac{1}{n}\sum_{i=1}^{n}\xi_{i}-\operatorname{{\mathds{E}}}_{P}\xi\right\|_{H\to
H}\geq\frac{4\tau\,B\cdot g(V)}{3n}+\sqrt{\frac{2\tau\left\|V\right\|_{H\to
H}g(V)}{n}}\bigg{)}\leq 2e^{-\tau}.$ (C.1)

To demonstrate the desired bound (4.3), we show first that
$\left(L_{k}+\lambda\right)^{-1}L_{k}$ and
$\left(L_{k}+\lambda\right)^{-1}L_{k}^{D}$ are close in operator norm. To this
end we rephrase the operator $L_{k}^{D}$ in terms of simple operators. Letting
$x_{1},\dots,x_{n}\sim P$, independently distributed with respect to the
design measure, and defining the operators

$T_{z}\colon\mathcal{H}_{k}\to\mathcal{H}_{k}\hskip
10.00002pt\text{with}\hskip 10.00002pt(T_{z}f)(y)=f(z)k(y,z)$ (C.2)

gives the representation

$L_{k}^{D}=\frac{1}{n}\sum_{i=1}^{n}T_{x_{i}},$

which fits the setting of Proposition C.1. With this we have the subsequent
concentration bound, following from the same arguments as Proposition 3.4 in
Dommel [7].

######  Proposition C.2.

For $\mathcal{N}_{\infty}(\lambda)$ as in (4.1) it holds that

$P\left(\left\|\left(L_{k}+\lambda\right)^{-1}(L_{k}-L_{k}^{D})\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}\leq\frac{4\tau\mathcal{N}_{\infty}(\lambda)g(\lambda)}{3n}+\sqrt{\frac{2\tau\mathcal{N}_{\infty}(\lambda)g(\lambda)}{n}}\right)\geq
1-2e^{-\tau}$ (C.3)

with

$g(\lambda)\coloneqq\ln\left(2e\frac{\lambda+\mu_{1}}{\mu_{1}}\mathcal{N}(\lambda)\right)$
(C.4)

and $\tau\geq 1$.

###### Proof.

For $x\sim P$ and $T_{x}$ as in (C.2) we consider the operator-valued random
variable $\xi(\omega):=(L_{k}+\lambda)^{-1}T_{x(\omega)}$. We have from

$\operatorname{{\mathds{E}}}(T_{x}f)(y)=\operatorname{{\mathds{E}}}_{x}f(x)k(y,x)=\int_{\mathcal{X}}f(x)k(y,x)p(x)dx=(L_{k}f)(y)$

that

$\frac{1}{n}\sum_{i=1}^{n}\xi_{i}=(L_{k}+\lambda)^{-1}L_{k}^{D}\hskip
10.00002pt\text{and}\hskip
10.00002pt\operatorname{{\mathds{E}}}\xi=(L_{k}+\lambda)^{-1}L_{k},$

and thus the setting of Proposition C.1. It is thus sufficient to show that
$\xi$ satisfies the requirements of Proposition C.1, provided that there is an
appropriate constant $B$ as well as dominating operator $V$.

We bound the norm $\left\|\xi\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}$
first. For that recall the inequality

$\left\|\xi\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}^{2}\leq\sum_{\ell=1}^{\infty}\left\langle\psi_{\ell},\xi\psi_{\ell}\right\rangle_{k}^{2},$

which holds for any orthonormal basis
$\left(\psi_{\ell}\right)_{\ell=1}^{\infty}$of $\mathcal{H}_{k}$. Thus,
setting $\psi_{\ell}:=\mu_{\ell}^{\nicefrac{{1}}{{2}}}\varphi_{\ell}$ we
observe that

$\displaystyle\left\|\xi\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}^{2}\leq$
$\displaystyle\sum_{\ell=1}^{\infty}\left\langle\psi_{\ell},(L_{k}+\lambda)^{-1}T_{x}\psi_{\ell}\right\rangle_{k}^{2}=\sum_{\ell=1}^{\infty}\left\langle(L_{k}+\lambda)^{-1}\psi_{\ell}(\cdot),\psi_{\ell}(x)k(\cdot,x)\right\rangle_{k}^{2}$

as $(L_{k}+\lambda)^{-1}$ is a self-adjoint operator. Furthermore, using the
reproducing property, i.e. the identity
$\left\langle(L_{k}+\lambda)^{-1}\psi_{\ell}(\cdot),k(\cdot,x)\right\rangle_{k}=\left((L_{k}+\lambda)^{-1}\psi_{\ell}\right)(x)$,
we get for the latter term that

$\displaystyle\sum_{\ell=1}^{\infty}\left\langle(L_{k}+\lambda)^{-1}\psi_{\ell}(\cdot),\psi_{\ell}(x)k(\cdot,x)\right\rangle_{k}^{2}$
$\displaystyle=\sum_{\ell=1}^{\infty}\left(\psi_{\ell}(x)((L_{k}+\lambda)^{-1}\psi_{\ell})(x)\right)^{2},$

from which we conclude

$\displaystyle\left\|\xi\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}^{2}$
$\displaystyle\leq\sum_{\ell=1}^{\infty}\left(\psi_{\ell}(x)((L_{k}+\lambda)^{-1}\psi_{\ell})(x)\right)^{2}=\sum_{\ell=1}^{\infty}\left(\frac{\mu_{\ell}}{\mu_{\ell}+\lambda}\varphi_{\ell}(x)^{2}\right)^{2}\leq\mathcal{N}_{\infty}(\lambda)^{2}$
(C.5)

$P$-almost surely, which discloses the constant
$B=\mathcal{N}_{\infty}(\lambda)$.

To bound the second moment, note first that $\xi$ is a positive definite
operator. Hence, we have that

$\operatorname{{\mathds{E}}}\xi^{2}\preccurlyeq\left\|\xi\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}\operatorname{{\mathds{E}}}\xi=\left\|\xi\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}(L_{k}+\lambda)^{-1}L_{k}\leq\mathcal{N}_{\infty}(\lambda)(L_{k}+\lambda)^{-1}L_{k}\eqqcolon
V$

by employing the estimate in (C.5). The operator norm of $V$ is bounded by

$\left\|V\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}=\left\|\mathcal{N}_{\infty}(\lambda)(L_{k}+\lambda)^{-1}L_{k}\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}=\mathcal{N}_{\infty}(\lambda)\frac{\mu_{1}}{\lambda+\mu_{1}}\leq\mathcal{N}_{\infty}(\lambda)$

as well as

$\displaystyle g(V)$
$\displaystyle=\ln\bigl{(}2e\operatorname*{trace}(V)\cdot\left\|V\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}^{-1}\bigr{)}=\ln\left(2e\mathcal{N}_{\infty}(\lambda)\mathcal{N}(\lambda)\cdot\frac{1}{\mathcal{N}_{\infty}(\lambda)\frac{\mu_{1}}{\lambda+\mu_{1}}}\right)=\ln\left(2e\frac{\lambda+\mu_{1}}{\mu_{1}}\mathcal{N}(\lambda)\right)$

corresponding to $g(\lambda)$ in (C.4). The desired inequality (C.3) follows
from Proposition C.1. ∎

Building on the bound (C.3) above, the assertion of Proposition 4.1 follows
from the subsequent considerations. Note first the operator identity

$(I-(L_{k}+\lambda)^{-1}(L_{k}-L_{k}^{D}))^{-1}=(L_{k}^{D}+\lambda)^{-1}(L_{k}+\lambda),$

from which we conclude that

$\displaystyle\left\|(L_{k}^{D}+\lambda)^{-1}(L_{k}+\lambda)\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}$
$\displaystyle=\left\|(I-\left(L_{k}+\lambda\right)^{-1}(L_{k}-L_{k}^{D}))^{-1}\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}$
$\displaystyle\leq\frac{1}{1-\left\|\left(L_{k}+\lambda\right)^{-1}(L_{k}-L_{k}^{D})\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}}$

by involving the Neumann series. Assuming the condition (4.2), we have by
(C.3) that

$\left\|\left(L_{k}+\lambda\right)^{-1}(L_{k}-L_{k}^{D})\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}\leq\frac{4}{3}\tau\,g(\lambda)\frac{\mathcal{N}_{\infty}(\lambda)}{n}+\sqrt{2\tau\,g(\lambda)\frac{\mathcal{N}_{\infty}(\lambda)}{n}}\leq\frac{1}{2}$

with probability at least $1-2e^{-\tau}$. Therefore, the bound

$\left\|(L_{k}^{D}+\lambda)^{-1}(L_{k}+\lambda)\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}\leq\frac{1}{1-\left\|\left(L_{k}+\lambda\right)^{-1}(L_{k}-L_{k}^{D})\right\|_{\mathcal{H}_{k}\to\mathcal{H}_{k}}}\leq\frac{1}{1-\frac{1}{2}}=2$

holds also with probability at least $1-2e^{-\tau}$. This is the desired
inequality (4.3).

##  Appendix D Auxiliary lemmata

The following two lemmata provide a crucial element for the proof of Lemma
B.1. That is, a bound on the expectation

$\operatorname{{\mathds{E}}}e^{-\frac{1}{M^{2}}},$

where

$M\coloneqq\min_{\begin{subarray}{c}i,j=1,\dots,n\\\
i\not=j\end{subarray}}|U_{i}-U_{j}|$

is the minimal gap between $n$ independently chosen uniforms.

The first lemma provides the density of $M$ explicitly, the other bounds the
associated expectation.

######  Lemma D.1.

Let $U_{1},\dots,U_{n}\sim\mathcal{U}[0,1]$ be independent uniforms. The
random variable $M$ has the density

$p_{M}(m)=\begin{cases}n(n-1)(1-(n-1)m)^{n-1}&\text{for}\,m\in\left[0,\frac{1}{n-1}\right]\\\
0&\text{else}\end{cases}.$ (D.1)

###### Proof.

Let $U_{1},\dots,U_{n}$ be independent uniforms on $[0,1]$ and denote the
corresponding minimal absolute difference by
$M\coloneqq\min_{i,j=1,\dots,n,i\neq j}|U_{i}-U_{j}|$. Note here that
$M\leq\frac{1}{n-1}$, and $M=\frac{1}{n-1}$ if all $U_{1},\dots,U_{n}$ are
equidistant. Therefore, let $m\in[0,\frac{1}{n-1}]$ and observe that

$P(M>m)=n!P(M>m,U_{1}\leq U_{2}\dots\leq U_{n})$ (D.2)

as there are $n!$ possible rearrangements of the random variables
$U_{1},\dots,U_{n}$. For the latter probability we have that

$\displaystyle P(M>m,\ U_{1}\leq U_{2}\leq\ldots\leq U_{n})$
$\displaystyle=P(U_{1}\leq U_{2}-m,\ U_{2}\leq U_{3}-m,\dots,U_{n-1}\leq
U_{n}-m,\ U_{1}\leq\ldots\leq U_{n})$
$\displaystyle=\lambda\left(\mathcal{U}_{m}\right),$

where $\lambda\left(\mathcal{U}_{m}\right)$ is the Lebesgue measure of the set

$\mathcal{U}_{m}=\left\\{(u_{1},\dots,u_{n})\in[0,1]^{n}:u_{1}\leq u_{2}-m,\
u_{2}\leq u_{3}-m,\dots,u_{n-1}\leq u_{n}-m,\ u_{1}\leq u_{2}\dots\leq
u_{n}\right\\}.$

We next present a measure persevering bijection between $\mathcal{U}_{m}$ and

$Y_{m}\coloneqq\left\\{(y_{1},\dots,y_{n})\in[0,1-(n-1)m]^{n}:y_{1}\leq
y_{2}\leq\dots\leq y_{n}\right\\}.$

To this end, define $T\colon U_{m}\to Y_{m}$ with
$Tu=u-(0,m,2m,\dots,(n-1)m)$. For $u=(u_{1},\dots,u_{n})\in U_{m}$ and
$y=Tu=u-(0,m,2m,\dots,(n-1)m)$ it is evident that $y_{i}\geq 0$ as well as
$y_{1}\leq\dots\leq y_{n}$. Furthermore, it holds that $u_{i}\leq 1-m\,(n-i)$
as the distance between the $u_{i}$ and $u_{i+1}$ is at least $m$, for every
$i=1,\dots,n$. With this we have the inequality

$y_{i}=u_{i}-(i-1)m\leq 1-m\,(n-i)-(i-1)m=1-(n-1)m$

and therefore $y\in Y_{m}$. Conversely, let $y\in Y_{m}$ and set
$u=y+(0,m,2m,\dots,(n-1)m)=T^{-1}y$. It is again immediate that $u_{i}\geq 0$
as well as

$u_{i}=y_{i}+(i-1)m\leq 1-(n-1)m+(i-1)m\leq 1.$

From $y_{1}\leq\dots\leq y_{n}$ we further get that

$u_{i+1}-m=y_{i+1}+i\,m-m=y_{i+1}+(i-1)m\geq y_{i}+(i-1)m=u_{i}$

for all $i=1,\dots,n-1$ and thus $u\in\mathcal{U}_{m}$. Hence, $T$ is a
bijection, from which we conclude that $\lambda(U_{m})=\lambda(Y_{m})$. The
latter measure is

$\displaystyle\lambda(Y_{m})$
$\displaystyle=\lambda\left(\left\\{(y_{1},\dots,y_{n})\in[0,1-(n-1)m]^{n}:y_{1}\leq
y_{2}\leq\dots\leq y_{n}\right\\}\right)$
$\displaystyle=\frac{1}{n!}\lambda\left(\left\\{(y_{1},\dots,y_{n})\in[0,1-(n-1)m]^{n}\right\\}\right)=\frac{1}{n!}(1-(n-1)m)^{n}.$
(D.3)

Combining (D.2) with (D.3), we get that

$P(M>m)=n!\frac{1}{n!}(1-(n-1)m)^{n}=(1-(n-1)m)^{n}$

and hence the density

$p(m)=\frac{d}{dm}(1-P(M>m))=n(n-1)(1-(n-1)m)^{n-1}.$

This is the assertion. ∎

######  Lemma D.2.

Let $U_{1},\dots,U_{n}\sim\mathcal{U}[0,1]$ be independent uniforms and $M$
the minimum gap as in Lemma D.1. For any $c>0$ it holds that

$\operatorname{{\mathds{E}}}e^{-cM^{-2}}\geq 4e^{-c\frac{2}{a^{2}}}\geq
Ce^{-8c(n-1)^{2}},$ (D.4)

with $a=\min\\{\frac{1}{3}c^{-\frac{2}{3}},\ \frac{1}{2(n-1)}\\}$.

###### Proof.

We employ the density (D.1) of $M$. As $\frac{1}{n-1}\leq\frac{1}{2(n-1)}$ and
$e^{-cM^{-2}}\geq 0$, we have that

$\displaystyle\operatorname{{\mathds{E}}}e^{-cM^{-2}}$
$\displaystyle=\int_{0}^{\frac{1}{n-1}}e^{-c\frac{1}{m^{2}}}\,n(n-1)\bigl{(}1-(n-1)m\bigr{)}^{n-1}dm$
$\displaystyle>\int_{0}^{\frac{1}{2(n-1)}}e^{-c\frac{1}{m^{2}}}n(n-1)(1-(n-1)m)^{n-1}dm$
$\displaystyle\geq
e^{-(n-1)}\int_{0}^{\frac{1}{2(n-1)}}e^{-c\frac{1}{m^{2}}}dm.$

To bound the latter integral term, note that

$\displaystyle\frac{x^{3}}{c}e^{-\frac{x^{2}}{c}}$ $\displaystyle\leq 1$

whenever $x\geq 3c^{\frac{2}{3}}$, as

$\ln\frac{x^{3}}{c}e^{-\frac{x^{2}}{c}}=3\ln\frac{x}{c^{\frac{1}{3}}}-\frac{x^{2}}{c}\leq
3\frac{x}{c^{\frac{1}{3}}}-\frac{x^{2}}{c}\leq 0$

is satisfied for all $x\geq 3c^{\frac{2}{3}}.$ Thus, choosing
$a=\min\\{\frac{1}{3}c^{-\frac{2}{3}},\frac{1}{2(n-1)}\\}$ we get that

$\displaystyle\int_{0}^{\frac{1}{2(n-1)}}e^{-c\frac{1}{x^{2}}}dx$
$\displaystyle\geq\int_{0}^{a}\frac{c}{x^{3}}e^{-c\frac{2}{x^{2}}}dx=\left[4e^{-c\frac{2}{x^{2}}}\right]_{0}^{a}=4e^{-c\frac{2}{a^{2}}},$

which is the assertion. ∎