We present the first optimal rates for infinite-dimensional vector-valued ridge regression on a continuous scale of norms that interpolate between $L_2$ and the hypothesis space, which we consider as a vector-valued reproducing kernel Hilbert space. These rates allow to treat the misspecified case in which the true regression function is not contained in the hypothesis space. We combine standard assumptions on the capacity of the hypothesis space with a novel tensor product construction of vector-valued interpolation spaces in order to characterize the smoothness of the regression function. Our upper bound not only attains the same rate as real-valued kernel ridge regression, but also removes the assumption that the target regression function is bounded. For the lower bound, we reduce the problem to the scalar setting using a projection argument. We show that these rates are optimal in most cases and independent of the dimension of the output space. We illustrate our results for the special case of vector-valued Sobolev spaces.

Keywords. Statistical learning, regularized least squares, optimal rates, interpolation norms.

2020 Mathematics Subject Classification.
68T05, 62G08.

§ INTRODUCTION

Optimal learning rates for least-squares regression with scalar outputs have been studied  extensively in the context of reproducing kernel Hilbert spaces (RKHS) over the last two decades. While some analyses considered vector-valued outputs, the optimality of vector-valued kernel-based algorithms remained an open question in important settings which include model misspecification or infinite-dimensional response variables.  We consider a data set $D=\left\{\left(x_i, y_i\right)\right\}_{i=1}^n$ of observations independently sampled from a joint unknown distribution $P$ on $E_X \times \cY$, where $\cY$ is a potentially infinite-dimensional output space
and $E_X$ is the covariate space. Let $(X,Y)$ be a random variable taking values in $E_X \times \cY$ distributed according to $P$. The objective is to estimate the regression function or conditional mean function $F_*: E_X \rightarrow \cY$ given by $F_*(x):=\mathbb{E}[Y \mid X=x]$.
Our focus in this work is to approximate $F_*$ with kernel-based regularized least-squares algorithms, where we pay special attention to the case when $\cY$ is of high or infinite dimension—a setting including important applications in multitask learning, functional data analysis and inference with kernel mean embeddings. We consider the estimate $\hat F_{\lambda}: E_X \to \cY$, obtained by solving the convex optimization problem

\begin{equation}\label{eq:hatflambda}
\hat F_{\lambda}=\underset{F \in \cG}{\operatorname{argmin}}\left\{\frac{1}{n} \sum_{i=1}^n\left\|y_i-F(x_i)\right\|^2_{\cY} + \lambda\|F\|_{\cG}^2\right\},
\end{equation}

where a vector-valued reproducing kernel Hilbert space (vRKHS) $\cG$ over $E_X$ serves as the hypothesis space and $\lambda>0$ is a regularization parameter. A vRKHS, as detailed in Section <ref>, is a generalization of the standard RKHS, allowing us to model functions that take values in a Hilbert space. This algorithm is commonly referred to as (vector-valued) ridge regression or
simply the regularized least squares (RLS) algorithm—even though it can be understood as a special instance of Tikhonov regularization in the more general context of regularization theory.
A central theoretical challenge in this context is to establish learning rates, either in expectation or in probability with respect to the distribution of $D$, for the error

\begin{equation}\label{eq:gen_error}
\|\hat F_{\la} - F_*\|
\end{equation}

in some relevant norm. In this paper, we investigate the behavior of Eq. (<ref>) with respect to the norms of a continuum of suitable Hilbert spaces $[\cG]^{\gamma}$ with $\cG \subseteq [\cG]^{\gamma} \subseteq L_2$; see Definition <ref> for an exact definition. We focus on the class of vector-valued RKHSs induced by the vector-valued kernel

\begin{equation}\label{eq:vkernel}
K(x,x') := k_{X}(x,x')B,
\end{equation}

where $B:\cY \to \cY$ is a positive-semidefinite
self-adjoint operator and $k_X: E_X \times E_X \to \R$
is a scalar-valued kernel.
This choice of kernel is the de-facto standard for
infinite-dimensional learning problems, as it allows
to practically compute $\hat F_{\lambda}$ defined
by Eq. (<ref>) conveniently in a variety of practical applications. Notable examples
for such an infinite-dimensional learning setting are the estimation of dynamical systems [Song et al., 2009, Kostic et al., 2022, Kostic et al., 2023], functional response regression [Kadri et al., 2016], structured prediction [Ciliberto et al., 2016, Ciliberto et al., 2020],
the estimation of linear operators [Mollenhauer and Koltai, 2020, Mollenhauer et al., 2022], the conditional mean embedding
[Grünewälder et al., 2012, Grünewälder et al., 2012, Park and Muandet, 2020], causal effect estimation under observed covariates [Singh et al., 2023] and kernel regression with instrumental  [Singh et al., 2019] and proximal [Mastouri et al., 2021] variables.

The RLS algorithm has been extensively studied in literature <cit.>. However, existing results concerning the optimal rates for RLS often cover the real-valued output space only. One exception is the work by [Caponnetto and De Vito, 2007],
where the output space $\cal Y$ is potentially infinite-dimensional. Their analysis does not generally hold for
the kernel $K$ defined by Eq. (<ref>), however, in the setting that $\cY$ is infinite-dimensional, as it relies
on a trace condition which is violated when $B$ is not
trace class—a restriction which rules out the choice $B = \operatorname{Id}_\cY$, used for example in the analysis of conditional mean embedding [Grünewälder et al., 2012, Li et al., 2022]. This
issue has been noted by multiple authors in the context of specific applications [Grünewälder et al., 2012, Grünewälder et al., 2012, Kadri et al., 2016, Mollenhauer and Koltai, 2020, Park and Muandet, 2020]. In addition, Caponnetto and De Vito, 2007 assume that $\cal Y$ is finite dimensional in order to obtain the matching lower bound and only consider the well-specified case.

This manuscript extends the results from the earlier work of [Li et al., 2022] in the following ways:

* While [Li et al., 2022] consider a  specific instance of infinite-dimensional RLS in terms of the conditional mean embedding, by assuming that the response variable $Y$ takes values in a RKHS, we offer an updated analysis of the RLS algorithm which applies to more general infinite-dimensional spaces $\cal Y$. Our study covers both the hard learning scenario (misspecified setting) when $F_* \notin \cG$ and the easy learning scenario (well-specified setting) when $F_* \in \cG$ (see Theorem <ref>). In order to cover the misspecified case, we construct novel interpolation spaces of vector-valued functions in terms of an isomorphism which allows to represent functions and linear operators in terms of a tensor product [Mollenhauer and Koltai, 2020, Mollenhauer et al., 2022]. In both cases, when $\cal Y$ is real-valued, we recover the same rate as in [Fischer and Steinwart, 2020], the current best known rate for real-valued kernel ridge regression in the literature. We adopt and modify the integral operator technique in order to avoid assuming the trace condition required by Caponnetto and De Vito, 2007. Furthermore, with the reduction technique, we obtain, in many cases, a matching lower rate even when $\cal Y$ is infinite-dimensional (see Theorem <ref>). We provide a thorough comparison to previous works after stating our results. In particular, we provide new dimension-free results for misspecified multitask learning in finite-dimensional spaces, which were not studied before in this context, to the best of our knowledge.

* The available analysis of scalar-valued kernel ridge regression requires boundedness of the regression function ($\sup_{x \in E_X} |F_*(x)| < \infty$), see Fischer and Steinwart, 2020. [Zhang et al., 2023] have recently shown that same rates can be obtained by replacing the boundedness condition with the weaker assumption that $|F_*|^q$ is integrable for some $q \geq 2$. Similarly, the present paper shows that we can derive learning rates in the vector-valued setting under the assumption that $\|F_*\|_{\cY}^q$ is integrable for some $q \geq 2$ without requiring boundedness of $F_*$ (see Theorem <ref> and Remark <ref>).

* As a final contribution, we study RLS learning in the setting of vector-valued Sobolev spaces (see Definition <ref>) which was not covered in [Li et al., 2022]. We obtain, for the first time, the minimax optimal learning rate for RLS learning in vector-valued Sobolev spaces (see Corollary <ref> and <ref>). In particular, we show that the requirement that $\|F_*\|_{\cY}^q$ is integrable for some $q \geq 2$ is automatically satisfied, but boundedness of $F_*$ is not always satisfied. This emphasizes why our second contribution is crucial in obtaining optimal rates without additional requirements on $F_*$.

The paper is organised as follows.
In Section <ref>, we introduce the concept of a vRKHS and the required mathematical preliminaries. Section <ref> discusses the formal construction of vector-valued interpolation spaces, which will be central to our analysis.
We provide upper rates for the vector-valued learning
problem in Section <ref>, while
a corresponding lower bound on the rates is presented
in Section <ref>. Section <ref>
sets our results in line with known rates for the scalar
learning setting in the context of Sobolev spaces,
and Section <ref> compares our result with other contributions. In order to improve the readability,
we defer proofs and technical auxiliary results to the appendices.

§ MATHEMATICAL PRELIMINARIES

Throughout the paper, we consider a random variable $X$ (the covariate) defined on a second countable locally compact Hausdorff space[Under additional technical assumptions, the results in this paper can also be formulated when $E_X$ is a more general topological space (for example when $E_X$ is Polish). However, some properties of kernels defined on $E_X$ such as the so-called $c_0$-universality [Carmeli et al., 2010] simplify the exposition when $E_X$ is a second countable locally compact Hausdorff space; see Remark <ref>.] $E_X$ endowed with its Borel $\sigma$-field $\mathcal{F}_{E_X}$, and the random variable $Y$ (the output) defined on a potentially infinite dimensional separable real Hilbert space $(\mathcal{Y}, \langle \cdot, \cdot \rangle_{\mathcal{Y}})$ endowed with its Borel $\sigma$-field $\mathcal{F}_{\mathcal{Y}}$. We let $(\Omega, \mathcal{F},\mathbb{P})$ be the underlying probability space with expectation operator $\mathbb{E}$. Let $P$ be the pushforward of $\mathbb{P}$ under $(X,Y)$ and $\pi$ and $\nu$ be the marginal distributions on $E_X$ and $\cY$, respectively; i.e., $X \sim \pi$ and $Y \sim \nu$. We use the Markov kernel $p: E_X \times \mathcal{F}_{\mathcal{Y}} \rightarrow \mathbb{R}_+$ to express
the distribution of $Y$ conditioned on $X$ as

\[
\mathbb{P}[Y \in A|X = x] = \int_{A} p(x,dy),
\]
for all $x \in E_X$ and events $A \in \mathcal{F}_{\mathcal{Y}}$,
see e.g. Dudley, 2002.

We now introduce some notation related
to linear operators and vector-valued integration. For more details, the reader may consult
Weidmann, 1980 and Diestel and Uhl, 1977, respectively.
We denote the space of real-valued Lebesgue square integrable functions on $(E_X,\mathcal{F}_{E_X})$ with respect to $\pi$ as $L_2(E_X,\mathcal{F}_{E_X},\pi)$ abbreviated $L_2(\pi)$ and similarly for $\nu$ we use $L_2(\mathcal{Y},\mathcal{F}_{\mathcal{Y}},\nu)$ abbreviated $L_2(\nu)$. Let $B$ be a separable Banach space with norm $\|\cdot\|_{B}$ and $H$ a separable real Hilbert space with inner product $\langle \cdot, \cdot \rangle_{H}$. We write $\mathcal{L}(B,B')$ as the Banach space of bounded linear operators from $B$ to another Banach space $B'$, equipped with the operator norm $\|\cdot\|_{B \rightarrow B'}$. When $B=B'$, we simply write $\mathcal{L}(B)$ instead. We also let $L_p(E_X,\mathcal{F}_{E_X},\pi; B)$, abbreviated $L_p(\pi; B)$, the space of strongly $\mathcal{F}_{E_X}-\mathcal{F}_B$ measurable and Bochner $p$-integrable functions from $E_X$ to $B$ for $1 \leq p \leq \infty$ with the norms

\[
\| f \|_{L_p(\pi;B)}^p
= \int_{E_X} \|f  \|_B^p \, \mathrm{d}\pi, \quad 1\leq p<\infty, \qquad \| f \|_{L_{\infty}(\pi;B)} = \inf\left\{C \geq 0: \pi\{\|f\|_{B}> C\}=0\right\}.
\]

We denote the $p$-Schatten class $S_p(H,H')$ to be the space of all compact operators $C$ from $H$ to another Hilbert space $H'$ such that $\|C\|_{S_p(H,H')} := \left\|\left(\sigma_i(C)\right)_{i\in J}\right\|_{\ell_p}$ is finite. Here $\|\left(\sigma_i(C)\right)_{i\in J}\|_{\ell_p}$ is the $\ell_p$ sequence space norm of the sequence of the strictly positive singular values of $C$ indexed by the countable set $J$. For $p = 2$, $S_2(H,H')$ is the Hilbert space of Hilbert-Schmidt operators from $H$ to $H'$. Finally, for two normed vector spaces $B,B'$, we say that $B$ is  (continuously) embedded in $B'$ and denote it as $B \hookrightarrow B'$ if $B$ can be interpreted as a vector subspace of $B'$ and the inclusion operator $i: B \to B'$
performing the change of norms with $i x = x$ for $x \in B$ is continuous; and we say that $B$ is isometrically isomorphic to $B'$ and denote it as $B \simeq B'$ if there is a linear isomorphism $\Psi: B  \to B'$ which is an isometry.

Tensor Product of Hilbert Spaces (Aubin, 2000, Section 12):
Denote $H\otimes H'$  the tensor product of Hilbert spaces $H$, $H'$. The Hilbert space $H\otimes H'$ is the completion of the algebraic tensor product with respect to the norm induced by the inner product $\langle x_1\otimes x_1', x_2\otimes x_2'\rangle_{H\otimes H'} = \langle x_1,x_2 \rangle_H \langle x_1', x_2'\rangle_{H'}$ for $x_1,x_2 \in H$ and $x_1', x_2' \in H'$ defined on the elementary tensors
of $H\otimes H'$. This definition extends to
$\operatorname{span}\{x\otimes x'| x\in H, x'\in H'\}$ and finally to
its completion. The space $H\otimes H'$ is separable whenever both $H$ and $H'$ are separable. The element $x\otimes x' \in H \otimes H'$ is treated as the linear rank-one operator $x\otimes x': H' \rightarrow H$ defined by $y' \rightarrow \langle y',x' \rangle_{H'}x $ for $y' \in H'$.
Based on this identification, the tensor product space $H\otimes H'$ is isometrically isomorphic to the space of Hilbert-Schmidt operators from $H'$ to $H$, i.e., $H\otimes H' \simeq S_2(H',H)$. We will hereafter not make the distinction between those two spaces and see them as identical. If $\{e_i\}_{i \in I}$ and $\{e'_j\}_{j \in J}$ are orthonormal basis in $H$ and $H'$, $\{e_i\otimes e'_j\}_{i\in I, j\in J}$ is an orthonormal basis in $H \otimes H'$.

Consider the Bochner space $L_2(\pi;H)$ where $H$ is a separable Hilbert space. One can show that $L_2(\pi;H)$ is isometrically identified with the tensor product space $H \otimes L_2(\pi)$.

Reproducing Kernel Hilbert Spaces, Covariance Operators:
We let $k_{X}: E_X \times E_X \rightarrow \mathbb{R}$ be a symmetric and positive definite kernel function and $\mathcal{H}_{X}$ be a vector space of functions from $E_X$ to $\mathbb{R}$, endowed with a Hilbert space structure via an inner product $\langle\cdot, \cdot\rangle_{\mathcal{H}_{X}}$. We say $k_{X}$ is a reproducing kernel of $\mathcal{H}_{X}$ if and only if for all $ x \in E_X$ we have $k_{X}(\cdot,x) \in \mathcal{H}_{X}$ and for all $x \in E_X$ and $f \in \mathcal{H}_{X}$, we have $f(x)=\left\langle f, k_{X}(x,\cdot)\right\rangle_{\mathcal{H}_{X}}$. A space $\mathcal{H}_{X}$ which possesses a reproducing kernel is called a reproducing kernel Hilbert space (RKHS; Berlinet and Thomas-Agnan, 2011). We denote the canonical feature map of $\mathcal{H}_{X}$ as $\phi_{X}(x) = k_{X}(\cdot,x)$.

We require some technical assumptions on the previously defined RKHS and kernel:

$\mathcal{H}_{X}$ is separable, this is satisfied
if $k_{X}$ is continuous, given that $E_X$ is separable[This follows from <cit.>. Note that the lemma requires separability of $E_X$, which is satisfied since we assume that $E_X$ is a second countable locally compact Hausdorff space.];

$k_{X}(\cdot,x)$ is measurable for $\pi$-almost all $x \in E_X$;

$k_X(x,x) \leq \kappa_X^2$ for $\pi$-almost all $x \in E_X$.

Note that the above assumptions are not restrictive in practice, as well-known kernels such as the Gaussian, Laplacian and Matérn kernels satisfy all of the above assumptions on $E_X \subseteq \mathbb{R}^d$ [Sriperumbudur et al., 2011]. We now introduce some facts about the interplay between $\mathcal{H}_{X}$ and $L_{2}(\pi),$ which has been extensively studied by [Smale and Zhou, 2004, Smale and Zhou, 2005], [De Vito et al., 2006] and [Steinwart and Scovel, 2012]. We first define the (not necessarily injective) embedding $I_{\pi}: \mathcal{H}_{X} \rightarrow L_{2}(\pi)$, mapping a function $f \in \mathcal{H}_{X}$ to its $\pi$-equivalence class $[f]$. The embedding is a well-defined compact operator as long as its Hilbert-Schmidt norm is finite. In fact,
this requirement is satisfied since its Hilbert-Schmidt norm can be computed as <cit.>

\left\|I_{\pi}\right\|_{S_{2}\left(\mathcal{H}_{X}, L_{2}(\pi)\right)}=\|k_{X}\|_{L_{2}(\pi)}:=\left(\int_{E_X} k_{X}(x, x) \mathrm{d} \pi(x)\right)^{1 / 2}<\infty.

The adjoint operator $S_{\pi}:=I_{\pi}^{*}: L_{2}(\pi) \rightarrow \mathcal{H}_{X}$ is an integral operator with respect to the kernel $k_{X}$, i.e. for $f \in L_{2}(\pi)$ and $x \in E_X$ we have <cit.>

\left(S_{\pi} f\right)(x)=\int_{E_X} k_{X}\left(x, x^{\prime}\right) f\left(x^{\prime}\right) \mathrm{d} \pi\left(x^{\prime}\right).

Next, we define the self-adjoint and positive semi-definite integral operators

L_{X}:=I_{\pi} S_{\pi}: L_{2}(\pi) \rightarrow L_{2}(\pi) \quad \text { and } \quad C_{XX}:=S_{\pi} I_{\pi}: \mathcal{H}_{X} \rightarrow \mathcal{H}_{X}.

These operators are trace class and their trace norms satisfy

$$\left\|L_{X}\right\|_{S_{1}\left(L_{2}(\pi)\right)}=\left\| C_{XX}\right\|_{S_{1}(\mathcal{H}_{X})}=\left\|I_{\pi}\right\|_{S_2(\mathcal{H}_{X}, L_{2}(\pi))}^{2}=\left\|S_{\pi}\right\|_{S_2(L_{2}(\pi),\mathcal{H}_{X})}^{2}. $$

Vector-valued RKHS: We give a brief overview of the vector-valued reproducing kernel Hilbert space. We refer the reader to [Carmeli et al., 2006] and [Carmeli et al., 2010] for more details.

Let $K: E_X \times E_X \rightarrow \mathcal{L}(\cY)$ be an operator valued positive-semidefinite (psd) kernel such that $K(x,x') = K(x',x)^*$ for all $x,x' \in E_X$, and for all $x_1,\dots,x_n\in E_X$ and $h_i,h_j \in \cY$,

\[\sum_{i,j =1}^n \langle h_i,K(x_i,x_j)h_j \rangle_{\cY} \geq 0.\]

Fix $K$, $x \in E_X$, and $h \in \cY$, then $\left[K_{x} h\right](\cdot):=K(\cdot, x) h$
defines a function from $E_X$ to $\cY$. We now consider

\mathcal{G}_{\text {pre }}:=\operatorname{span}\left\{K_{x} h \mid x \in E_X, h \in \cY\right\}

with inner product on $\mathcal{G}_{\text {pre }}$ by linearly extending the expression
⟨K_x h, K_x^' h^'⟩_𝒢:=⟨h, K(x, x^') h^'⟩_ .

Let $\mathcal{G}$ be the completion of $\mathcal{G}_{\text{pre}}$ with respect to this inner product. We call $\mathcal{G}$ the vRKHS induced by the kernel $K$. The space $\mathcal{G}$ is a Hilbert space consisting of functions from $E_X$ to $\cY$ with the reproducing property
⟨F(x), h⟩_=⟨F, K_x h⟩_𝒢,

for all $F \in \mathcal{G}, h \in \cY$ and $x \in E_X$. For all $F \in \mathcal{G}$ we obtain

\|F(x)\|_{\cY} \leq\|K(x, x)\|^{1 / 2}_{\cY \rightarrow \cY}\|F\|_{\mathcal{G}}, \quad x \in E_X.

The inner product given by Eq. (<ref>) implies that $K_{x}$ is a bounded operator for all $x \in E_X$. For all $F \in \mathcal{G}$ and $x \in E_X$, Eq. (<ref>) can be written as $F(x)=K_{x}^{*} F$. The linear operators $K_{x}: \cY \rightarrow \mathcal{G}$ and $K_{x}^{*}: \mathcal{G} \rightarrow \cY$ are bounded with

\left\|K_{x}\right\|_{\cY \rightarrow \mathcal{G}}=\left\|K_{x}^{*}\right\|_{\mathcal{G} \rightarrow \cY}=\|K(x, x)\|_{\cY \rightarrow \cY}^{1 / 2}

and we have $K_{x}^{*} K_{x^{\prime}}=K\left(x, x^{\prime}\right), x, x^{\prime} \in E_X$. In the following, we will denote $\mathcal{G}$ as the vRKHS induced by the kernel $K: E_X \times E_X \rightarrow \mathcal{L}(\mathcal{Y})$ with

\[K(x,x') := k_{X}(x,x')\operatorname{Id}_{\mathcal{Y}}, \quad x,x' \in E_X.\]

Without loss of generality, we provide our results for the vRKHS
$\mathcal{G}$ induced by the operator-valued kernel given by
$K(x,x') = k_{X}(x,x')\operatorname{Id}_{\mathcal{Y}}$.
However, with suitably adjusted constants in the assumptions,
our results transfer directly to the more general
vRKHS $\widetilde{\mathcal{G}}$ induced by the more general operator-valued kernel

\[
\widetilde K(x,x') := k_{X}(x,x')B
\]

where $B: \mathcal{Y} \to \mathcal{Y}$
is any positive-semidefinite self-adjoint operator.
In fact, this setting is covered by straightforwardly
replacing the response variable $Y$ with the modified response
$\widetilde{Y} := B^{1/2}Y$ in our learning problem.
We note that the space $\widetilde{\mathcal{G}}$ is alternatively
obtained as the vRKHS induced by $K(x,x') = k_{X}(x,x')\operatorname{Id}_{\mathcal{Y}}$ when the target space $\mathcal{Y}$ is equipped with the modified inner product
$\langle y, y' \rangle_B := \langle y , B y' \rangle_\mathcal{Y}$
for all $y,y' \in \mathcal{Y}$.
This can readily be seen by the construction of $\widetilde{\mathcal{G}}$.
By (<ref>), we have

\[
\left\langle
\widetilde{K}_{x} y, \widetilde{K}_{x^{\prime}} y^{\prime}
\right\rangle_{\widetilde{\mathcal{G}}}
\left\langle
y, k_X\left(x, x^{\prime}\right) B y^{\prime}
\right\rangle_{\mathcal{Y}}
\left\langle
y, k_X\left(x, x^{\prime}\right)\operatorname{Id}_{\mathcal{Y}} y^{\prime}
\right\rangle_B
%    K_{x} B^{1/2}y, K_{x^{\prime}} B^{1/2}y^{\prime}
\]

for all $x,x' \in E_X$ and $y, y' \in \mathcal{Y}$. See also <cit.>.

An important property of $\mathcal{G}$ is that elements in $\mathcal{G}$ are isometric to Hilbert-Schmidt operators between $\mathcal{H}_{X}$ and $\mathcal{Y}$.

[Example 5 (i) in Carmeli et al., 2010] For $g \in \mathcal{Y}$ and $f \in \mathcal{H}_{X}$, define the map $\bar{\Psi}$ on the elementary tensors as

\[\left[\bar{\Psi}\left(g \otimes f\right)\right](x):= f(x)g = \left(g \otimes f\right)\phi_{X}(x).\]

Then $\bar{\Psi}$ defines an isometric isomorphism between $S_2(\mathcal{H}_{X}, \mathcal{Y})$ and $\mathcal{G}$ through linearity and completion.

More details regarding Theorem <ref> (for the special case where $\mathcal{Y}$ is a RKHS) can be found in <cit.>. The isometric isomorphism $\bar{\Psi}$ induces the operator reproducing property stated below.

For every function $F\in \mathcal{G}$ there exists an operator $C := \bar{\Psi}^{-1}(F) \in S_2(\mathcal{H}_{X}, \mathcal{Y})$ such that
\[F(x) = C\phi_{X}(x) \in \mathcal{Y},\]
for all $x \in E_X$ with $\|C\|_{S_2(\mathcal{H}_{X}, \mathcal{Y})} = \|F\|_{\mathcal{G}}$ and vice versa. Conversely, for any pair $F \in \mathcal{G}$ and $C \in S_2(\mathcal{H}_{X}, \mathcal{Y})$, we have $C = \bar{\Psi}^{-1}(F)$ as long as $F(x) = C \phi_{X}(x)$ for all $x \in E_X$.

The proof of Corollary <ref> is a simple extension of Lemma $15$ in [Ciliberto et al., 2016] and Corollary $4.5$ in [Mollenhauer and Koltai, 2020]. Corollary <ref> shows that the vRKHS $\mathcal{G}$ is generated via the space of Hilbert-Schmidt operators $S_2(\mathcal{H}_{X}, \mathcal{Y})$
\[\mathcal{G}= \left\{F: E_X \rightarrow \mathcal{Y} \mid F = C\phi_{X}(\cdot), \quad C \in S_2(\mathcal{H}_{X}, \mathcal{Y})\right\}.\]

Vector-valued regression: We briefly recall the basic setup of regularized least squares regression with Hilbert space-valued random variables. The risk for vector-valued regression is
ℰ(F):= 𝔼[Y - F(X)^2_𝒴 ] = ∫_E_X ×𝒴 y - F(x)^2_𝒴p(x,dy)π(dx) ,

for measurable functions $F: E_X \rightarrow \mathcal{Y}$. The analytical minimiser of the risk over all those measurable functions is the regression function or the conditional mean function $F_\star \in L_2(\mathbb{\pi}; \cY)$ given by
F_*(x):= 𝔼[Y |X = x] = ∫_𝒴 y   p(x,dy),   x ∈E_X.

This fact can for example be proven via a classical decomposition of the risk, see e.g. <cit.>. Throughout the paper, we assume that $\E[\Vert Y \Vert_\cY^2] < +\infty$, i.e., the random variable $Y$ is square integrable. Note that this ensures that we have $F_\star \in L_2(\pi; \cY)$.

We pick $\mathcal{G}$ as an hypothesis space of functions to estimate $F_*$. Given a data set $D = \{(x_i, y_i)\}_{i=1}^n$ independently and identically sampled from the joint distribution of $X$ and $Y$, a regularized estimate of $F_*$ is the solution of the following optimization problem:
F̂_λ:= _F ∈𝒢 1/n∑_i = 1^n y_i - F(x_i)^2_𝒴 + λF_𝒢^2,

where $\lambda > 0$ is the regularization parameter. According to Corollary <ref>, $\hat{F}_{\lambda}(\cdot) := \bar{\Psi}\left(\hat{C}_{\lambda}\right)(\cdot)  = \hat{C}_{\lambda}\phi_X(\cdot)$ where
Ĉ_λ:= _C ∈S_2(ℋ_X, 𝒴) 1/n∑_i = 1^n y_i - Cϕ_X(x_i)^2_𝒴 + λC_S_2(ℋ_X, 𝒴)^2,

An explicit solution is given by

\hat{F}_{\lambda}(x) = \hat{C}_{\lambda}\phi_{X}(x)=\sum_{i=1}^{n}y_{i}\beta_{i}(x), \qquad \beta(x) := \left[\mathbf{K}_{XX}+n\lambda \operatorname{Id}\right]^{-1}\mathbf{k}_{Xx} \in \mathbb{R}^n

\begin{aligned}
(\mathbf{K}_{XX})_{ij} & =k(x_{i},x_{j}) \qquad &i,j \in [n] \\
\left(\mathbf{k}_{Xx}\right)_{i} & = k(x_{i},x) \qquad &i \in [n]
\end{aligned}

The above model is well-specified
if the equivalence class $F_\star \in L_2(\pi; \cY)$ admits
a representative which is contained in $\cG$. In what follows, we will simply write this scenario as $F_\star \in \cG$ by abuse of notation.
We note that universal consistency of this approach
at least requires that $\cG$ is dense in $L_2(\pi; \cY)$ such that for every possible
$F_\star$, we can achieve
$\hat{F}_{\lambda} \to F_\star$
in the norm of $L_2(\pi; \cY)$
either in expectation or with high probability
with respect to the distribution of the
samples $D$ for some admissible regularization scheme $\lambda = \lambda_n \to 0$ whenever $n \to \infty$. This denseness is well-investigated and generally satisfied; see Remark <ref>.

Real-valued Interpolation Space:
We now introduce the background required in order to characterize the Hilbert spaces used to deal with the misspecified setting $F_* \notin \mathcal{G}$.
We  review the results of
Steinwart and Scovel, 2012 and Fischer and Steinwart, 2020
that set out the eigendecompositions of $L_{X}$ and $C_{XX}$, and apply these in constructing the interpolation spaces  used for the misspecified setting. By the spectral theorem for self-adjoint compact operators, there exists an at most countable index set $I$, a non-increasing sequence $(\mu_i)_{i\in I} > 0$, and a family $(e_i)_{i \in I} \in \mathcal{H}_{X}$, such that $\left([e_i]\right)_{i \in I}$ is an orthonormal basis (ONB) of $\overline{\text{ran}~I_{\pi}} \subseteq L_2(\pi)$ and $(\mu_i^{1/2}e_i)_{i\in I}$ is an ONB of $\left(\operatorname{ker} I_{\pi}\right)^{\perp} \subseteq \mathcal{H}_{X}$, and we have

\begin{equation} \label{eq:SVD}
L_{X} = \sum_{i\in I} \mu_i \langle\cdot, [e_i] \rangle_{L_2(\pi)}[e_i], \qquad C_{XX} = \sum_{i \in I} \mu_i \langle\cdot, \mu_i^{\frac{1}{2}}e_i \rangle_{\mathcal{H}_{X}} \mu_i^{\frac{1}{2}}e_i
\end{equation}

For $\alpha \geq 0$, we define the $\alpha$-interpolation space [Steinwart and Scovel, 2012] by

\[[\mathcal{H}]_{X}^{\alpha}:=\left\{\sum_{i \in I} a_{i} \mu_{i}^{\alpha / 2}\left[e_{i}\right]:\left(a_{i}\right)_{i \in I} \in \ell_{2}(I)\right\} \subseteq L_{2}(\pi),\]

equipped with the $\alpha$-power norm

\[\left\|\sum_{i \in I} a_{i} \mu_{i}^{\alpha / 2}\left[e_{i}\right]\right\|_{[\mathcal{H}]_{X}^{\alpha}}:=\left\|\left(a_{i}\right)_{i \in I}\right\|_{\ell_{2}(I)}=\left(\sum_{i \in I} a_{i}^{2}\right)^{1 / 2}.\]

For $\left(a_{i}\right)_{i\in I} \in \ell_{2}(I)$, the $\alpha$-interpolation space becomes a Hilbert space with inner product defined as
\[\left\langle \sum_{i \in I}a_i(\mu_i^{\alpha/2}[e_i]), \sum_{i \in I}b_i(\mu_i^{\alpha/2}[e_i]) \right\rangle_{[\mathcal{H}]_{X}^{\alpha}} = \sum_{i \in I} a_i b_i.\]
Moreover, $\left(\mu_{i}^{\alpha / 2}\left[e_{i}\right]\right)_{i \in I}$ forms an ONB of $[\mathcal{H}]_{X}^{\alpha}$ and consequently $[\mathcal{H}]_{X}^{\alpha}$ is a separable Hilbert space. In the following, we use the abbreviation $\|\cdot\|_{\alpha}:=\|\cdot\|_{[\mathcal{H}]_{X}^{\alpha}}$. For $\alpha=0$ we have $[\mathcal{H}]_{X}^{0}=\overline{\operatorname{ran} I_{\pi}} \subseteq L_{2}(\pi)$ with $\|\cdot\|_{0}=\|\cdot\|_{L_{2}(\pi)}$. Moreover, for $\alpha=1$ we have $[\mathcal{H}]_{X}^{1}=\operatorname{ran} I_{\pi}$ and $[\mathcal{H}]_{X}^{1}$ is isometrically isomorphic to the closed subspace $\left(\operatorname{ker} I_{\pi}\right)^{\perp}$ of $\mathcal{H}_{X}$ via $I_{\pi}$, i.e. $\left\|[f]\right\|_{1}=\|f\|_{\mathcal{H}_{X}}$ for $f \in\left(\operatorname{ker} I_{\pi}\right)^{\perp}$. For $0<\beta<\alpha$, we have
[ℋ]_X^α ↪[ℋ]_X^β  ↪[ℋ]_X^0 ⊆L_2(π).

For $\alpha > 0$, the $\alpha$-interpolation space is given by the image of the fractional integral operator, namely

[\cH]_X^\alpha=\operatorname{ran} L_X^{\alpha / 2} \quad \text { and } \quad\left\|L_X^{\alpha / 2} f\right\|_\alpha=\|f\|_{L_2(\pi)}

for $f \in \overline{\operatorname{ran} I_\pi}$.

Under assumptions <ref> to <ref> and $E_X$ being a second-countable locally compact Hausdorff space, if $k_X(\cdot, x)$ is continuous and vanishing at infinity, then $[\mathcal{H}]_{X}^{0} = L_{2}(\pi)$ if and only if $\cH$ is dense in the space of continuous functions vanishing at infinity equipped with the uniform norm [Carmeli et al., 2010]. Such RKHS are called $c_0-$universal. As a special case of <cit.>, one can show that on $\Rd$, Gaussian, Laplacian, inverse multiquadrics and Matérn kernels are $c_0$-universal.

S_2(L_2(π), 𝒴) [r, "Ψ"']       L_2(π;𝒴)

S_2(ℋ_X, 𝒴) [r, "Ψ̅"'] [u, bend left, dotted, "ℐ_π", red, xshift=-4ex]     𝒢

$\Psi$ and $\bar{\Psi}$ are the isometric isomorphisms between each pair of spaces. $\mathcal{I}_{\pi}$ denotes the canonical embedding between the two Hilbert-Schmidt spaces.

§ APPROXIMATION OF F* WITH VECTOR-VALUED INTERPOLATION SPACE

In this section, we deal with the misspecified setting where $F_* \notin \mathcal{G}$. To do this, we first define the vector-valued interpolation space via the tensor product space. We recall from Remark <ref> that $L_2(\pi;\mathcal{Y})$ is isometrically isomorphic to $S_2\left(L_2(\pi), \mathcal{Y}\right)$ and we denote by $\Psi$ the isometric isomorphism between the two spaces. Similarly, we have $\mathcal{G} \simeq S_2(\mathcal{H}_X,
\mathcal{Y})$ and we denote by $\bar\Psi$ the isometric isomorphism between both spaces in accordance with Theorem <ref>. This is summarized in Figure <ref>. The second chain of spaces is not isometric to the first but can be naturally embedded into the first as follows. Recall that we denote by $I_{\pi}: \mathcal{H}_X \rightarrow L_2(\pi)$ the embedding that maps each function to its equivalence class, $I_{\pi}(f) = [f]$. We therefore naturally define the embedding $\mathcal{I}_{\pi}: S_2(\mathcal{H}_X, \mathcal{Y}) \rightarrow S_2(L_2(\pi), \mathcal{Y})$ through $\mathcal{I}_{\pi}(g \otimes f) = g \otimes I_{\pi}(f) = g \otimes [f]$ for all $f \in \mathcal{H}_X$, $g \in \mathcal{Y}$, and obtain the extension to the whole space by linearity and continuity.[$\mathcal{I}_{\pi}$ is formally the tensor product of the operator $I_{\pi}$ with the operator $\operatorname{Id}_{\mathcal{Y}}$, see <cit.>] Therefore, for $F \in \mathcal{G}$ we define $[F] :=  \Psi \circ \mathcal{I}_{\pi} \circ \bar{\Psi}^{-1}(F)$. In the rest of the paper, every embedding will be denoted using the notation $[~\cdot~]$. A stricter requirement would be to write $[~\cdot~]_{\pi}$ due to dependence on the measure $\pi$, but we omit the subscript for ease of notation.

Let $k_X$ be a real-valued kernel with associated RKHS $\mathcal{H}_X$ and let $[\mathcal{H}]_X^{\alpha}$ be the real-valued interpolation space associated to $\mathcal{H}_X$ with some $\alpha \geq 0$. Since $[\mathcal{H}]_X^{\alpha} \subseteq L_2(\pi)$, it is natural to define the vector-valued interpolation space $[\mathcal{G}]^{\alpha}$ as

\[[\mathcal{G}]^{\alpha}
:= \Psi\left(S_2([\mathcal{H}]_X^{\alpha},\mathcal{Y}) \right) = \{F \mid F = \Psi(C), ~C \in S_2([\mathcal{H}]_X^{\alpha},\mathcal{Y})\}.\]

$[\mathcal{G}]^{\alpha}$ is a Hilbert space equipped with the norm
$$\|F\|_{\alpha} := \|C\|_{S_2([\mathcal{H}]_X^{\alpha}, \mathcal{Y})} \qquad (F \in [\mathcal{G}]^{\alpha}),$$
where $C = \Psi^{-1}(F)$. For $\alpha = 0$, we retrieve,
$$\|F\|_{0} = \|C\|_{S_2(L_2(\pi), \mathcal{Y})}.$$

The vector-valued interpolation space $[\mathcal{G}]^{\alpha}$ allows us to study the approximation of $F_*$ in the misspecified case. Note that we have $F_* \in L_2(\pi;\mathcal{Y})$ since $Y \in L_2(\P; \cY)$ by assumption. In light of Eq. (<ref>), for $0< \beta <\alpha$ we have
\[[\mathcal{G}]^{\alpha} \hookrightarrow [\mathcal{G}]^{\beta}  \hookrightarrow [\mathcal{G}]^{0}\subseteq L_2(\pi;\mathcal{Y}).\]

While the well-specified case corresponds to $F_* \in \mathcal{G}$, the misspecified case corresponds to $F_* \in [\mathcal{G}]^{\beta}$ for some $0 \leq \beta <1$. One can see from Remark <ref> that under assumptions <ref> to <ref> and $E_X$ being a second-countable locally compact Hausdorff space, $[\mathcal{G}]^{0} = L_2(\pi;\mathcal{Y})$ if and only if $k_X$ is $c_0-$universal.

§ UPPER LEARNING RATES

In this section, we derive the learning rate for the difference between $[\hat{F}_{\lambda}]$ and $F_*$ in the interpolation norm. As our assumptions match those of [Fischer and Steinwart, 2020], we include their corresponding labels
for ease of reference. Recall that $(\mu_i)_{i\in I}$ are the positive eigenvalues of the integral operator. We now list our assumptions:

$5$. For some constants $c_1 >0$ and $p \in (0,1]$ and for all $i \in I$,

\begin{equation}\label{asst:evd}
\mu_i \leq c_1i^{-1/p}.\tag{EVD}
\end{equation}

$6$. For $\alpha \in [p, 1]$, the inclusion map $I^{\alpha, \infty}_{\pi}: [\mathcal{H}]_{X}^{\alpha} \hookrightarrow L_{\infty}(\pi)$ is continuous, there is a constant $A > 0$ such that

\begin{equation}\label{asst:emb}
\|I^{\alpha, \infty}_{\pi}\|_{[\mathcal{H}]_{X}^{\alpha} \rightarrow L_{\infty}(\pi)} \leq A \tag{EMB}
\end{equation}

$7$. There exists $0 < \beta$ and a constant $B \geq 0$ such that $F_* \in [\mathcal{G}]^{\beta}$

\begin{equation}\label{asst:src}
\|F_*\|_{\beta} \leq B. \tag{SRC}
\end{equation}

We let $C_{*} := \Psi^{-1}(F_*) \in S_2([\mathcal{H}]_X^{\beta}, \mathcal{Y})$.

$8$.We assume that there are constants $\sigma, R > 0$ such that

\begin{equation}\label{asst:mom}
\int_{\mathcal{Y}}\|y- F_{*}(x)\|_{\mathcal{Y}}^q p(x,dy) \leq \frac{1}{2}q!\sigma^2R^{q-2}, \tag{MOM}
\end{equation}

is satisfied for $\pi$-almost all $x \in E_X$ and all $q \geq 2$.

(<ref>) is a standard assumption on the eigenvalue decay of the integral operator (see more details in Caponnetto and De Vito, 2007, Fischer and Steinwart, 2020).
Property (<ref>) is referred to as the embedding property in [Fischer and Steinwart, 2020].
It can be shown that it holds if and only if there exists a constant $A \geq 0$ with $\sum_{i \in I} \mu_i^{\alpha} e_i^2(x) \leq A^2$ for $\pi$-almost all $x \in E_X$ <cit.>. Since we assume $k_X$ to be bounded, the embedding property always hold true when $\alpha = 1$. Furthermore, (<ref>) implies a polynomial eigenvalue decay of order $1/\alpha$, which is why we take $\alpha \geq p$. (<ref>) is justified by Remark <ref> and is often referred to as the source condition in literature [Caponnetto and De Vito, 2007, Fischer and Steinwart, 2020, Lin and Cevher, 2018, Lin et al., 2020]. It measures the smoothness of the regression function $F_*$. In particular, when $\beta \geq 1$, the source condition implies that $F_*$ has a representative from $\mathcal{G}$, indicating the well-specified scenario. However, once we let $\beta < 1$, we are in the misspecified learning setting, which is the main interest in this manuscript. Finally, the (<ref>) condition on the Markov kernel $p(x,dy)$ is a Bernstein moment condition used to control the noise of the observations (see Caponnetto and De Vito, 2007, Fischer and Steinwart, 2020 for more details). If $Y$ is almost surely bounded, for example $\|Y\|_{\cY} \leq Y_{\infty}$ almost surely, then (<ref>) is satisfied with $\sigma=R=2Y_{\infty}$. It is possible to prove that the Bernstein condition is equivalent to sub-exponentiality,
see <cit.>.

Let $\mathcal{H}_X$ be a RKHS on $E_X$ with respect to a kernel $k_X$ such that assumptions <ref> to <ref> hold. Furthermore, let the conditions (<ref>), (<ref>),  (<ref>) be satisfied for some $0 < p \leq \alpha \leq 1$. For $0 \leq \gamma \leq 1$, if (<ref>) is satisfied with $\gamma < \beta \leq 2$, and then

* in the case $\beta + p \leq \alpha$ and $\|F_*\|_{L_q(\pi; \cY)} \leq C_q$ for a constant $C_q> 0$ and $q \geq \frac{2\alpha}{\alpha-\beta}$, let $\lambda_n = \Theta \left(\left(n/\log^{\theta}(n)\right)^{-\frac{1}{\alpha}}\right)$ for some $\theta > 1$, for all $\tau > \log(5)$ and sufficiently large $n \geq 1$, there is a constant $J > 0$ independent of $n$ and $\tau$ such that
\[\left\|[\hat{F}_{\lambda}] - F_*\right\|^2_{\gamma} \leq \tau^2 J\left(\frac{n}{\log ^{\theta} n}\right)^{-\frac{\beta-\gamma}{\alpha}}\]
is satisfied with $P^n$-probability not less than $1-5e^{-\tau}$.

* in the case $\beta + p > \alpha$, suppose either of the following holds and $\lambda_n = \Theta \left(n^{-\frac{1}{\beta + p}}\right)$,

(a) $\beta \geq \alpha$,

(b) $\alpha -p < \beta < \alpha$ and $\|F_*\|_{L_q(\pi; \cY)} \leq C_q$ for a constant $C_q> 0$ and $q > \frac{2(\beta+p)}{\beta +2p-\alpha }$,

then for all $\tau > \log(5)$ and sufficiently large $n \geq 1$, there is a constant $J > 0$ independent of $n$ and $\tau$ such that
\[\left\|[\hat{F}_{\lambda_n}] - F_*\right\|^2_{\gamma} \leq \tau^2 J n^{-\frac{\beta-\gamma}{\beta + p}}\]
is satisfied with $P^n$-probability not less than $1-5e^{-\tau}$.

The index bound hidden in the phrase “sufficiently large $n$” depends on the parameters and constants from (<ref>) and (<ref>), on $\tau$, on a lower bound $0 < c \leq 1$ for the operator norm $c \leq \|C_{XX}\|$, on $C_q$, $q$ and on the regularization parameter sequence $(\la_n)_{n \geq 1}$. We can see that the constant $J$ in Theorem <ref> does not depend on $\|F_*\|_{\infty}$, and only depends on the parameters and constants from (<ref>), (<ref>),  (<ref>), (<ref>), on $C_q$ and $q$, and on the regularization parameter sequence $(\la_n)_{n \geq 1}$.

Theorem <ref> states that the learning rate for $[\hat{F}_{\lambda}]$ is governed by the interplay between $p$, $\alpha$, and $\beta$.

To simplify the discussion, we focus on the $L_2(\pi; \mathcal{Y})$ learning rate, corresponding to $\gamma = 0$. The exponent $\beta / \max\{\alpha, \beta+p\}$ explicitly provides the learning rate. For example, if we have $\alpha \leq \beta$, we obtain a learning rate of $\beta/ (\beta + p)$. In particular, for a Gaussian kernel on a bounded convex set $E_X$ with $\pi$ uniform on $E_X$, $p$ and $\alpha$ are arbitrarily close to $0$ <cit.>, and our learning rate can achieve
$O(\log(n)/ n)$ rate simply by taking $\lambda_n = \Theta\left(\left(\log(n)/n\right)^{1/\beta}\right)$. We address the case of kernels with slower eigenvalue decay such as the Matérn kernel in Section <ref>.

When analyzing the RLS algorithm for both scalar and vector-valued outputs, it is standard to assume that the regression function $F_\star$ is bounded, as discussed in prior studies <cit.>. This boundedness is inherently met when $\beta \geq \alpha$, which falls in line with the assumption (<ref>). However, when $\beta < \alpha$, this condition must be explicitly assumed. Our previous work, [Li et al., 2022], did not provide a way to relax this assumption (see Appendix <ref>). Nonetheless, when $\cal Y=\R$ and $\alpha-p < \beta < \alpha$, recent insights by Zhang et al., 2023 suggest that this boundedness criterion can be substituted with the requirement that $F_*$ belongs to $L_q(\pi;\R)$ for some $q \geq 2$. Adopting a similar methodology, our Theorem <ref> extends the scope of [Zhang et al., 2023] in two significant ways. First, for the range $\alpha-p < \beta < \alpha$, we achieve a similar learning rate as established in [Zhang et al., 2023], but with a broader scope where $\cY$ can be any Hilbert space, not just a subset of $\mathbb{R}$. Second, Theorem <ref> demonstrates the possibility of discarding the boundedness assumption for the entire range of $0 < \beta < \alpha$, expanding beyond the limited range of $\alpha -p < \beta < \alpha$ as considered in their study. As will be demonstrated in subsequent sections, these enhancements, building upon the findings in [Li et al., 2022], are pivotal in achieving minimax rates for the RLS algorithm within vector-valued Sobolev spaces.

§ LOWER BOUND

Our final theorem provides a lower bound for the convergence rates, which eventually allows us to confirm the optimality of  the learning rates given in the preceding section. In deriving the lower bound, we need the following extra assumption.

$8$. For some constants $c_1,c_2 >0$ and $p \in (0,1]$ and for all $i\in I$,

\begin{equation}\label{asst:evd+}
c_2 i^{-1/p} \leq \mu_i \leq c_1i^{-1/p}\tag{EVD+}
\end{equation}

Let $k_X$ be a kernel on $E_X$ such that assumptions <ref> to <ref>  hold and $\pi$ be a probability distribution on $E_X$ such that (<ref>) holds with $0< p \leq 1$. Then for all parameters $0 < \beta \leq 2$, $0 \leq \gamma \leq 1$ with $\gamma < \beta$ and all constants $\sigma, R, B$, there exist constants $J_0, J, \theta > 0$ such that for all learning methods $D\rightarrow \hat{F}_{D}$ ($D:=\{(x_i,y_i)\}_{i=1}^n$), all $\tau > 0$, and all sufficiently large $n \geq 1$ there is a distribution $P$ defined on $E_X \times \mathcal{Y}$ used to sample $D$, with marginal distribution $\pi$ on $E_X$, such that (<ref>) with respect to $B,\beta$ and (<ref>) with respect to $\sigma, R$ are satisfied, and with $P^n$-probability not less than $1-J_0\tau^{1/\theta}$,

\[\|[\hat{F}_D] - F_*\|^2_{\gamma} \geq \tau^2 J n^{-\frac{\beta-\gamma}{\beta+p}}.\]

Theorem <ref> states that under the assumptions of Theorem <ref> and Assumption (<ref>) no learning method can achieve a learning rate faster than

\begin{equation} \label{eq:lb}
n^{-\frac{\beta - \gamma}{\beta+p}}.
\end{equation}

To our knowledge, this is the first analysis that demonstrates the lower rate for vector-valued regression in infinite dimension. In the context of regularized regression, Caponnetto and De Vito, 2007,
Steinwart et al., 2009 and Blanchard and Mücke, 2018 provide lower bounds on the learning rate under comparable assumptions. However, one key difference in our analysis is that the output of the regression learning now takes values in a potentially infinite dimensional Hilbert space $\mathcal{Y}$, rather than in $\mathbb{R}$ or $\Rd$.

Our analysis reveals that for $\beta \geq \alpha$, the RLS estimator leads to the minimax optimal rate (by combining Theorem <ref> and case 2.(a) in Theorem <ref>), namely
$O(n^{-(\beta-\gamma)/(\beta + p)})$. Furthermore, when $[\cG]^{\beta} \subseteq L_q(\pi;\cY)$ with $q > \frac{2(\beta+p)}{\beta + 2p - \alpha}$, the obtained upper rate maintains optimality for $\beta  \in (\alpha-p, \alpha)$. This scenario is particularly relevant for vector-valued Sobolev RKHSs, a topic we will explore in the following section. We point out that finding the optimal rate for $\beta < \alpha$ – a situation where $F_*$ is not necessarily bounded – remains a longstanding challenge, even when the output is in $\mathbb{R}$.

§ EXAMPLE: VECTOR-VALUED SOBOLEV SPACE

In this section we illustrate our main results in the case of vector-valued Sobolev RKHSs, extending the results of Fischer and Steinwart, 2020 in the scalar-valued setting. To this end, we assume that $E_X \subseteq \Rd$ is a bounded domain with smooth
boundary equipped with the Lebesgue measure $\mu$. $L_2(E_X; \mathcal{Y}) := L_2(E_X, \mu; \mathcal{Y})$ denotes the corresponding Bochner space. We start by introducing vector-valued Sobolev spaces.

For $m \in \mathbb{N}$, the vector-valued Sobolev space $W^{m, 2}(E_X ; \cY)$ is the Hilbert space of all $f \in L_2(E_X ; \cY)$ whose weak derivatives of all orders[$r := (r_1, \ldots, r_d) \in \N^d$ is a multi-index and $|r|$ denotes the sum of its values.] $|r| \leqslant m$ exist and belong to $L_2(E_X ; \cY)$, endowed with the norm

\|f\|_{W^{m, 2}(E_X ; \cY)}^2:=\sum_{|r| \leqslant m}\left\|\partial^r f\right\|_{L_2(E_X ; \cY)}^2.

For $m=0$, $W^{0, 2}(E_X ; \cY) := L_2(E_X; \mathcal{Y})$.

For the definition of weak derivatives of functions in $L_2(E_X ; \cY)$ see <cit.>. The following theorem allows us to connect vector-valued Sobolev spaces to our framework.

[Aubin, 2000, Theorem 12.7.1]
For $m \in \N$, the vSobolev space $W^{m, 2}(E_X ; \cY)$ is isometric to the Hilbert tensor product $\cY \otimes W^{m, 2}(E_X)$, where $W^{m, 2}(E_X):= W^{m, 2}(E_X ; \R)$ is the standard scalar-valued Sobolev space.

When $k_X$ is a translation invariant kernel on $\Rd$ whose Fourier transform behaves as $\left(1+\|\cdot\|_2^2\right)^{-m}$ with $m > d/2$, such as the Matérn kernel (see Definition <ref>), the induced RKHS $\cH_X$ restricted to $E_X$ coincides with $W^{m, 2}(E_X)$, and their norms are equivalent, see <cit.>. Therefore, if we choose such a kernel $k_X$ to construct $K = k_X\operatorname{Id}_{\cY}$
and $\cG$, we obtain by Theorem <ref> and Theorem <ref>,

\cG \simeq \cY \otimes \cH_X \simeq \cY \otimes W^{m, 2}(E_X) \simeq W^{m, 2}(E_X ; \cY).

The induced vector-valued RKHS therefore corresponds to a vector-valued Sobolev space.

For $m \in \N$ with $m>d/2$, the Matérn kernel of order $m$ is defined as

k_X\left(x^{\prime}, x\right)= \frac{1}{2^{m-d/2-1}\Gamma(m-d/2)}\left(\sqrt{2(m-d/2)}\left\|x^{\prime}-x\right\|\right)^{m-d / 2} \mathcal{K}_{m-d/2}\left(\sqrt{2(m-d/2)}\left\|x^{\prime}-x\right\|\right), \quad x,x' \in \Rd,

where $\mathcal{K}_{m-d/2}$ is the modified Bessel function of the second kind of order $m-d/2$ and $\Gamma$ is the Gamma function (see e.g., Kanagawa et al., 2018, Examples 2.2 and 2.6).

We now specify Theorem <ref> and Theorem <ref> in the setting of vector-valued Sobolev spaces. We make the assumption that the marginal $\pi$ is equivalent to the Lebesgue measure so that $L_2(E_X; \mathcal{Y}) \simeq L_2(E_X, \pi; \mathcal{Y})$.

Let $k_X$ be a kernel on $E_X$ such that assumptions <ref> to <ref>  hold and such that $\cG \simeq W^{m, 2}(E_X ; \cY)$ with $m > d/2$, and let $P$ be a probability distribution on $E_X \times \mathcal{Y}$ such that $\pi:=P_{E_X}$ (the marginal distribution on $E_X$) is equivalent to the Lebesgue measure $\mu$ on $E_X$. Furthermore, let $B> 0$ be a constant such that $\|F_*\|_{W^{s, 2}(E_X ; \cY)} \leq B$ for some $0 < s \leq 2m$, and (<ref>) be satisfied. Then for a choice $\lambda_n = \Theta \left(n^{-\frac{m}{s + d/2}}\right)$, for all $\tau > \log(4)$ and sufficiently large $n \geq 1$, there is a constant $J > 0$ independent of $n$ and $\tau$ such that
\[\left\|[\hat{F}_{\lambda_n}] - F_*\right\|^2_{L_2(\pi; \mathcal{Y})} \leq \tau^2 J n^{-\frac{s}{s + d/2}}\]
is satisfied with $P^n$-probability not less than $1-4e^{-\tau}$.

Let $k_X$ be a kernel on $E_X$ such that assumptions <ref> to <ref> hold and such that $\cG \simeq W^{m, 2}(E_X ; \cY)$ with $m > d/2$, $P$ be a probability distribution on $E_X \times \mathcal{Y}$ such that $\pi:=P_{E_X}$ (the marginal distribution on $E_X$) is equivalent to the Lebesgue measure $\mu$ on $E_X$. Then for all parameters $0 < s \leq 2m$, and all constants $\sigma, R,B > 0$ there exist constants $J_0, J, \theta > 0$ such that for all learning methods $D\rightarrow \hat{F}_{D}$ ($D:=\{(x_i,y_i)\}_{i=1}^n$), all $\tau > 0$, and all sufficiently large $n \geq 1$ there is a distribution $P$ defined on $E_X \times \mathcal{Y}$ used to sample $D$, with marginal distribution $\pi$ on $E_X$, $\|F_*\|_{W^{s, 2}(E_X ; \cY)} \leq B$ and (<ref>) with respect to $\sigma, R$, are satisfied, and with $P^n$-probability not less than $1-J_0\tau^{1/\theta}$,
\[\|[\hat{F}_D] - F_*\|^2_{L_2(\pi; \mathcal{Y})} \geq \tau^2 J n^{-\frac{s}{s+d/2}}.\]

Corollary <ref> and <ref> are proved simply by inserting the values for $p, \al$ and $\beta$ from (<ref>), (<ref>) and (<ref>) into Theorem <ref> and <ref>. For $\cG \simeq  W^{m, 2}(E_X ; \cY)$ and $\pi$ equivalent to the Lebesgue measure, we show in the appendix (Propositions <ref> and <ref> with Theorem <ref>) that $p = \frac{d}{2m}$, $\alpha = p + \epsilon$ for all $\epsilon>0$ and for $s \in \N$, $W^{s, 2}(E_X ; \cY) \simeq [\cG]^{s/m}$, which implies $\beta = s/m$. Since $\alpha - p$ is
arbitrarily close to zero, we are in the regime $\beta + p > \alpha$ and achieve the rate $n^{-\frac{\beta}{\beta+p}} = n^{-\frac{s}{s+d/2}}$ by Theorem <ref>. Furthermore, the requirement that $F_* \in L_q$ for $q > \frac{2(\beta+p)}{\beta+2p-\alpha} = 2$ is automatically satisfied since a generalization of the Sobolev embedding Theorem <cit.> shows that $W^{1, 2}(E_X ; \cY) \hookrightarrow L_q(\pi;\cY)$ for some $q \geq 2$.

Our results show that the RLS estimator in Eq. (<ref>) leads to minimax optimal rates for any $\beta \in (0, 2]$ when $\cG$ is a vector-valued Sobolev RKHS, since the rates obtained in Corollary <ref> match the lower bound in Corollary <ref>. This aligns with the recent findings obtained in [Zhang et al., 2023] for scalar-valued Sobolev RKHS. Notice that in obtaining the minimax optimal rate for $\beta \in (0,2]$, we prove that $W^{s, 2}(E_X ; \cY) \simeq [\cG]^{s/m}$ is valid for any $s \in \N$, which relies on the fact that $W^{s, 2}(E_X ; \R) \simeq [\cH]^{s/m}_{X}$. A similar proof can be found when $s < m$ in [Fischer and Steinwart, 2020]. However, to our knowledge, we provide the first proof of this fact for $s \geq m$ (see Proposition <ref> in the appendix). We thank Haobo Zhang who brought us a sketch of proof for this case.

§ RELATED WORK

In this section, we compare our results with learning rates obtained in the literature.

We provide a systematic comparison
to the most important work in Table <ref>.
Due to the large amount of available types of rates
for the scalar learning setting, we primarily focus on optimal rates
derived under comparable assumptions on the underlying distributions.
For the much less investigated vector-valued learning case, we provide a more general overview of recent results.

As discussed previously, the closest work to our results is [Caponnetto and De Vito, 2007]. By assuming that
$F_* \in \cal G$, [Caponnetto and De Vito, 2007] provide the first analysis of RLS with Tikhonov regularization for when $\cal Y$ is infinite dimensional. In this work, the smoothness of the
Bayes function is naturally expressed as an element of the range
of a power iterate of the corresponding covariance operator
(this is known as a Hölder source condition
in regularization theory, see e.g. Blanchard and Mücke, 2018).
They show the $L_2$ learning rate $n^{-\beta/(\beta+p)}$, when $K(x,x')$ is trace class for all $x,x' \in E_X$—this condition is violated for the standard choice of kernel $K(x,x')=k_{X}(x,x')\operatorname{Id}_\cY$ whenever $\cal Y$ is infinite dimensional. For finite dimensional $\cal Y$, Caponnetto and De Vito, 2007 obtain the matching lower bound. In contrast, we study the RLS algorithm beyond the well-specified setting. Our analysis covers both the well-specified case and the hard learning scenario with $F_* \notin \cal G$, without assuming the trace class condition for the kernel $K$. When $F_* \in \cal G$,
the construction of our vector-valued interpolation space
can be interpreted as a generalisation of the Hölder source condition
(this is seen by interpreting the covariance operator in terms
of the tensor product structure of $\cG$, see Mollenhauer et al., 2022).
Hence, in the well-specified case, our rates recover the same rate as [Caponnetto and De Vito, 2007]. Moreover, instead of $L_2$-rate, we derive a general $\gamma$-learning rate, such that the $L_2$ learning rate is recovered when $\gamma =0$. Finally, we obtain the dimension-free matching lower rate without requiring finite dimensional $\cal Y$.

In the real-valued RLS setting, [Blanchard and Mücke, 2018] and [Fischer and Steinwart, 2020] provide the $\gamma$-learning rate with general regularization schemes for the well-specified case under the Hölder source condition [Blanchard and Mücke, 2018] and Tikhonov regularization for the misspecified case based on
real-valued interpolation spaces [Fischer and Steinwart, 2020] respectively. For Tikhonov RLS in the well-specified regime, they obtain the same $L_2$ learning rate as in [Caponnetto and De Vito, 2007]
given by $n^{-\beta/(\beta+p)}$. They both provide the matching lower bound when $F_* \in \cal G$. A key difference between the two is that [Fischer and Steinwart, 2020] extend the learning rate analysis to the hard learning scenario by employing the embedding property. We use similar techniques to [Fischer and Steinwart, 2020], and generalize the study to the vector-valued RLS setting through our construction of
vector-valued interpolation spaces. Thus, when $\cal Y$ is real-valued, our results recover the known kernel ridge regression rate of Fischer and Steinwart, 2020.

In addition to the previously mentioned work, there are some comparable results
for infinite-dimensional RLS which do not explicitly contain optimal upper rates and/or do not
provide corresponding lower bounds.
To our knowledge, Mollenhauer et al., 2022 derive the first upper learning rates for the infinite-dimensional RLS algorithm for the case of general regularisation schemes which are not exclusively based on vector-valued RKHSs. These rates hold for the $\gamma$-norm
and cover our setting with the kernel $K(x,x')=k_{X}(x,x')\operatorname{Id}_\cY$ as a special case.
Technically, their approach is similar to the real-valued analysis by Blanchard and Mücke, 2018—thus, they only cover the well-specified setting
under Hölder source conditions. As a major difference compared to our results,
Mollenhauer et al., 2022 only consider rates up to the order $O(n^{-1/2})$
without additional assumptions about the marginal of $X$ (which are needed for faster rates). [Singh et al., 2019] study the vector-valued RLS problem in a setting which is similar to ours. They obtain a suboptimal $O(n^{-1/4})$ upper rate in the well-specified setting, however, due to the use of a less sharp concentration bound. Finally, there are extensive studies concerning real-valued RLS <cit.>. In particular, [Lin and Cevher, 2018] derive the $\gamma$-learning rate of $n^{- (\beta-\gamma) /\max\{\beta+p,1\}}$ using the integral operator technique, while [Steinwart et al., 2009] obtain an $L_2$ rate of $n^{- \beta /\max\{\beta+p,1\}}$ using an empirical process technique.

Kernel    Output space     Misspecified case     smoothness     Algorithm     Norm
Blanchard and Mücke, 2018     scalar $k_X(x,x')$    Real-valued     no     Hölder source condition     general    $\gamma$-norm
Fischer and Steinwart, 2020     scalar $k_X(x,x')$     Real-valued     yes     interpolation space     ridge regression     $\gamma$-norm
Caponnetto and De Vito, 2007     $K(x,x')$ trace class for all $x,x' \in E_X$     Vector-valued     no     Hölder source condition     ridge regression      $L_2$-norm
This work     $k_{X}(x,x')B$ with $B$ psd.    Vector-valued     yes     vector-valued interpolation space     ridge regression    $\gamma$-norm

An overview of articles providing lower rates and corresponding optimal upper rates for kernel-based least squares algorithms based on the integral operator technique in various scenarios under comparable assumptions on the underlying distributions.

In this paper, we provide a rigorous theoretical foundation for approximating the CME operator, and study the statistical learning rate. Utilizing recently developed interpolation space techniques, we first define the vector-valued interpolation space $[\mathcal{G}]^{\alpha}$. This  allows to define the target CME operator in the larger interpolation space $[\mathcal{G}]^{\alpha}$, in contrast to the well-specified setting where $F_* \in \mathcal{G}$. By doing so, we are able to study the convergence rate of the empirical CME operator in the misspecified scenario. We then provide a $\gamma$-norm learning rate for the CME without any assumption on the interplay between $\beta$ and $p$, with matching lower bound. Our analysis shows that under appropriate conditions, we can obtain a fast $O(\log n / n)$ convergence rate, which matches the rate obtained in the existing literature for finite dimensional $\mathcal{H}_Y$. In more challenging settings, we  still obtain the minimax optimal rate $O(n^{-1/2})$.

Looking beyond the present work, our current interpolation space setting indicates that the convergence rate can be arbitrarily slow if $\beta \rightarrow 0$. This prevents learning the constant function, which plays a crucial role in completing the theory of the CME, as pointed out by <cit.>. Addressing this challenge is an important direction of future  research.

§ ACKNOWLEDGEMENTS

MM is supported by the Deutsche Forschungsgemeinschaft (DFG) through grant EXC 2046 MATH+, Project EF1-19:  Machine Learning Enhanced Filtering Methods for Inverse Problems. ZL, DM and AG are supported by the Gatsby Charitable Foundation. The authors wish to thank Haobo Zhang for helpful discussions.

[Adams and Fournier, 2003]
Robert Adams and John Fournier.
Sobolev spaces.
Elsevier, 2003.

[Aubin, 2000]
Jean-Pierre Aubin.
Applied Functional Analysis.
John Wiley & Sons, Inc., 2nd edition, 2000.

[Bauer et al., 2007]
Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco.
On regularization algorithms in learning theory.
Journal of complexity, 230 (1):0 52–72, 2007.

[Berlinet and Thomas-Agnan, 2011]
Alain Berlinet and Christine Thomas-Agnan.
Reproducing Kernel Hilbert Spaces in Probability and
Springer Science & Business Media, 2011.

[Blanchard and Mücke, 2018]
Gilles Blanchard and Nicole Mücke.
Optimal rates for regularization of statistical inverse learning
Foundations of Computational Mathematics, 180
(4):0 971–1013, 2018.

[Bogachev, 1998]
V.I. Bogachev.
Gaussian Measures.
American Mathematical Society, 1998.

[Caponnetto and De Vito, 2007]
Andrea Caponnetto and Ernesto De Vito.
Optimal rates for the regularized least-squares algorithm.
Foundations of Computational Mathematics, 70
(3):0 331–368, 2007.

[Carmeli et al., 2006]
Claudio Carmeli, Ernesto De Vito, and Alessandro Toigo.
Vector valued reproducing kernel Hilbert spaces of integrable
functions and Mercer theorem.
Analysis and Applications, 40 (04):0 377–408,

[Carmeli et al., 2010]
Claudio Carmeli, Ernesto De Vito, Alessandro Toigo, and Veronica Umanitá.
Vector valued reproducing kernel Hilbert spaces and universality.
Analysis and Applications, 80 (01):0 19–61,

[Ciliberto et al., 2016]
Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi.
A consistent regularization approach for structured prediction.
Advances in Neural Information Processing Systems, 29, 2016.

[Ciliberto et al., 2020]
Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi.
A general framework for consistent structured prediction with
implicit loss embeddings.
The Journal of Machine Learning Research, 210
(1):0 3852–3918, 2020.

[De Vito et al., 2006]
Ernesto De Vito, Lorenzo Rosasco, and Andrea Caponnetto.
Discretization error analysis for tikhonov regularization.
Analysis and Applications, 40 (01):0 81–99,

[Dicker et al., 2017]
L.H. Dicker, D.P. Foster, and Daniel Hsu.
Kernel ridge vs. principal component regression: Minimax bounds and
the qualification of regularization operators.
Electronic Journal of Statistics, 11:0 1022–1047,

[Diestel and Uhl, 1977]
Joe Diestel and J.J. Uhl.
Vector Measures.
American Mathematical Society, 1977.

[Dudley, 2002]
R.M. Dudley.
Real Analysis and Probability.
Cambridge University Press, 2nd edition edition, 2002.

[Edmunds and Triebel, 1996]
D.E. Edmunds and Hans Triebel.
Function Spaces, Entropy Numbers, Differential Operators.
Cambridge University Press, 1996.

[Fine and Scheinberg, 2002]
Shai Fine and Katya Scheinberg.
Efficient SVM training using low-rank kernel representations.
Journal of Machine Learning Research, 2:0 243–264,

[Fischer and Steinwart, 2020]
Simon Fischer and Ingo Steinwart.
Sobolev norm learning rates for regularized least-squares algorithms.
Journal Of Machine Learning Research, 21:0 205–1,

[Gretton, 2013]
Arthur Gretton.
Introduction to rkhs, and some simple kernel algorithms.
Lecture Notes, University College London, 2013.

[Grünewälder et al., 2012]
Steffen Grünewälder, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur
Gretton, and Massimilano Pontil.
Conditional mean embeddings as regressors.
In Proceedings of the 29th International Coference on
International Conference on Machine Learning, pages 1803––1810,

[Grünewälder et al., 2012]
Steffen Grünewälder, Guy Lever, Luca Baldassarre, Massimilano Pontil,
and Arthur Gretton.
Modelling transition dynamics in mdps with rkhs embeddings.
In Proceedings of the 29th International Conference on Machine
Learning, pages 535–542, 2012b.

[Kadri et al., 2016]
Hachem Kadri, Emmanuel Duflos, Philippe Preux, Stéphane Canu, Alain
Rakotomamonjy, and Julien Audiffren.
Operator-valued kernels for learning from functional response data.
Journal of Machine Learning Research, 170
(20):0 1–54, 2016.

[Kanagawa et al., 2018]
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath Sriperumbudur.
Gaussian processes and kernel methods: A review on connections and
arXiv preprint arXiv:1807.02582, 2018.

[Kostic et al., 2022]
Vladimir Kostic, Pietro Novelli, Andreas Maurer, Carlo Ciliberto, Lorenzo
Rosasco, and Massimiliano Pontil.
Learning dynamical systems via koopman operator regression in
reproducing kernel hilbert spaces.
Advances in Neural Information Processing Systems,
35:0 4017–4031, 2022.

[Kostic et al., 2023]
Vladimir Kostic, Karim Lounici, Pietro Novelli, and Massimiliano Pontil.
Koopman operator learning: Sharp spectral rates and spurious
arXiv preprint arXiv:2302.02004, 2023.

[Kreuter, 2015]
Marcel Kreuter.
Sobolev spaces of vector-valued functions.
Ulm University Faculty of Mathematics and Economies, 2015.

[Li et al., 2022]
Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton.
Optimal rates for regularized conditional mean embedding learning.
In Advances in Neural Information Processing Systems,
volume 35, pages 4433–4445, 2022.

[Lin and Cevher, 2018]
Junhong Lin and Volkan Cevher.
Optimal distributed learning with multi-pass stochastic gradient
In International Conference on Machine Learning, pages
3092–3101. PMLR, 2018.

[Lin et al., 2020]
Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher.
Optimal rates for spectral algorithms with least-squares regression
over Hilbert spaces.
Applied and Computational Harmonic Analysis, 480
(3):0 868–890, 2020.

[Mastouri et al., 2021]
Afsaneh Mastouri, Yuchen Zhu, Limor Gultchin, Anna Korba, Ricardo Silva, Matt
Kusner, Arthur Gretton, and Krikamol Muandet.
Proximal causal learning with kernels: Two-stage estimation and
moment restriction.
In International conference on machine learning, pages
7512–7523. PMLR, 2021.

[Meunier et al., 2023]
Dimitri Meunier, Zhu Li, Arthur Gretton, and Samory Kpotufe.
Nonlinear meta-learning can guarantee faster rates.
arXiv preprint arXiv:2307.10870, 2023.

[Mollenhauer and Koltai, 2020]
Mattes Mollenhauer and Péter Koltai.
Nonparametric approximation of conditional expectation operators.
arXiv preprint arXiv:2012.12917, 2020.

[Mollenhauer et al., 2022]
Mattes Mollenhauer, Nicole Mücke, and T.J. Sullivan.
Learning linear operators: Infinite-dimensional regression as a
well-behaved non-compact inverse problem.
arXiv preprint arXiv:2211.08875, 2022.

[Park and Muandet, 2020]
Junhyung Park and Krikamol Muandet.
A measure-theoretic approach to kernel conditional mean embeddings.
Advances in Neural Information Processing Systems,
33:0 21247–21259, 2020.

[Singh et al., 2019]
Rahul Singh, Maneesh Sahani, and Arthur Gretton.
Kernel instrumental variable regression.
Advances in Neural Information Processing Systems, 32, 2019.

[Singh et al., 2023]
Rahul Singh, Liyuan Xu, and Arthur Gretton.
Kernel methods for causal functions: dose, heterogeneous and
incremental response curves.
Biometrika, page asad042, 07 2023.
ISSN 1464-3510.

[Smale and Zhou, 2004]
Steve Smale and Ding-Xuan Zhou.
Shannon sampling and function reconstruction from point values.
Bulletin of the American Mathematical Society, 410
(3):0 279–305, 2004.

[Smale and Zhou, 2005]
Steve Smale and Ding-Xuan Zhou.
Shannon sampling II: Connections to learning theory.
Applied and Computational Harmonic Analysis, 190
(3):0 285–302, 2005.

[Smale and Zhou, 2007]
Steve Smale and Ding-Xuan Zhou.
Learning theory estimates via integral operators and their
Constructive approximation, 260 (2):0
153–172, 2007.

[Song et al., 2009]
Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu.
Hilbert space embeddings of conditional distributions with
applications to dynamical systems.
In Proceedings of the 26th Annual International Conference on
Machine Learning, pages 961–968. ACM, 2009.

[Sriperumbudur et al., 2011]
Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet.
Universality, characteristic kernels and RKHS embedding of
Journal of Machine Learning Research, 120
(Jul):0 2389–2410, 2011.

[Steinwart and Christmann, 2008]
Ingo Steinwart and Andreas Christmann.
Support Vector Machines.
Springer, 2008.

[Steinwart and Scovel, 2012]
Ingo Steinwart and Clint Scovel.
Mercer’s theorem on general domains: On the interaction between
measures, kernels, and RKHSs.
Constructive Approximation, 350 (3):0
363–417, 2012.

[Steinwart et al., 2009]
Ingo Steinwart, Don Hush, and Clint Scovel.
Optimal rates for regularized least squares regression.
In COLT, pages 79–93, 2009.

[Weidmann, 1980]
Joachim Weidmann.
Linear Operators in Hilbert Spaces.
Springer, 1980.

[Wendland, 2004]
Holger Wendland.
Scattered Data Approximation.
Cambridge University Press, 2004.

[Zhang et al., 2023]
Haobo Zhang, Yicheng Li, Weihao Lu, and Qian Lin.
On the optimality of misspecified kernel ridge regression.
arXiv preprint arXiv:2305.07241, 2023.

[Adams and Fournier, 2003]
Robert Adams and John Fournier.
Sobolev spaces.
Elsevier, 2003.

[Aubin, 2000]
Jean-Pierre Aubin.
Applied Functional Analysis.
John Wiley & Sons, Inc., 2nd edition, 2000.

[Bauer et al., 2007]
Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco.
On regularization algorithms in learning theory.
Journal of complexity, 230 (1):0 52–72, 2007.

[Berlinet and Thomas-Agnan, 2011]
Alain Berlinet and Christine Thomas-Agnan.
Reproducing Kernel Hilbert Spaces in Probability and
Springer Science & Business Media, 2011.

[Blanchard and Mücke, 2018]
Gilles Blanchard and Nicole Mücke.
Optimal rates for regularization of statistical inverse learning
Foundations of Computational Mathematics, 180
(4):0 971–1013, 2018.

[Bogachev, 1998]
V.I. Bogachev.
Gaussian Measures.
American Mathematical Society, 1998.

[Caponnetto and De Vito, 2007]
Andrea Caponnetto and Ernesto De Vito.
Optimal rates for the regularized least-squares algorithm.
Foundations of Computational Mathematics, 70
(3):0 331–368, 2007.

[Carmeli et al., 2006]
Claudio Carmeli, Ernesto De Vito, and Alessandro Toigo.
Vector valued reproducing kernel Hilbert spaces of integrable
functions and Mercer theorem.
Analysis and Applications, 40 (04):0 377–408,

[Carmeli et al., 2010]
Claudio Carmeli, Ernesto De Vito, Alessandro Toigo, and Veronica Umanitá.
Vector valued reproducing kernel Hilbert spaces and universality.
Analysis and Applications, 80 (01):0 19–61,

[Ciliberto et al., 2016]
Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi.
A consistent regularization approach for structured prediction.
Advances in Neural Information Processing Systems, 29, 2016.

[Ciliberto et al., 2020]
Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi.
A general framework for consistent structured prediction with
implicit loss embeddings.
The Journal of Machine Learning Research, 210
(1):0 3852–3918, 2020.

[De Vito et al., 2006]
Ernesto De Vito, Lorenzo Rosasco, and Andrea Caponnetto.
Discretization error analysis for tikhonov regularization.
Analysis and Applications, 40 (01):0 81–99,

[Dicker et al., 2017]
L.H. Dicker, D.P. Foster, and Daniel Hsu.
Kernel ridge vs. principal component regression: Minimax bounds and
the qualification of regularization operators.
Electronic Journal of Statistics, 11:0 1022–1047,

[Diestel and Uhl, 1977]
Joe Diestel and J.J. Uhl.
Vector Measures.
American Mathematical Society, 1977.

[Dudley, 2002]
R.M. Dudley.
Real Analysis and Probability.
Cambridge University Press, 2nd edition edition, 2002.

[Edmunds and Triebel, 1996]
D.E. Edmunds and Hans Triebel.
Function Spaces, Entropy Numbers, Differential Operators.
Cambridge University Press, 1996.

[Fine and Scheinberg, 2002]
Shai Fine and Katya Scheinberg.
Efficient SVM training using low-rank kernel representations.
Journal of Machine Learning Research, 2:0 243–264,

[Fischer and Steinwart, 2020]
Simon Fischer and Ingo Steinwart.
Sobolev norm learning rates for regularized least-squares algorithms.
Journal Of Machine Learning Research, 21:0 205–1,

[Gretton, 2013]
Arthur Gretton.
Introduction to rkhs, and some simple kernel algorithms.
Lecture Notes, University College London, 2013.

[Grünewälder et al., 2012]
Steffen Grünewälder, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur
Gretton, and Massimilano Pontil.
Conditional mean embeddings as regressors.
In Proceedings of the 29th International Coference on
International Conference on Machine Learning, pages 1803––1810,

[Grünewälder et al., 2012]
Steffen Grünewälder, Guy Lever, Luca Baldassarre, Massimilano Pontil,
and Arthur Gretton.
Modelling transition dynamics in mdps with rkhs embeddings.
In Proceedings of the 29th International Conference on Machine
Learning, pages 535–542, 2012b.

[Kadri et al., 2016]
Hachem Kadri, Emmanuel Duflos, Philippe Preux, Stéphane Canu, Alain
Rakotomamonjy, and Julien Audiffren.
Operator-valued kernels for learning from functional response data.
Journal of Machine Learning Research, 170
(20):0 1–54, 2016.

[Kanagawa et al., 2018]
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath Sriperumbudur.
Gaussian processes and kernel methods: A review on connections and
arXiv preprint arXiv:1807.02582, 2018.

[Kostic et al., 2022]
Vladimir Kostic, Pietro Novelli, Andreas Maurer, Carlo Ciliberto, Lorenzo
Rosasco, and Massimiliano Pontil.
Learning dynamical systems via koopman operator regression in
reproducing kernel hilbert spaces.
Advances in Neural Information Processing Systems,
35:0 4017–4031, 2022.

[Kostic et al., 2023]
Vladimir Kostic, Karim Lounici, Pietro Novelli, and Massimiliano Pontil.
Koopman operator learning: Sharp spectral rates and spurious
arXiv preprint arXiv:2302.02004, 2023.

[Kreuter, 2015]
Marcel Kreuter.
Sobolev spaces of vector-valued functions.
Ulm University Faculty of Mathematics and Economies, 2015.

[Li et al., 2022]
Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton.
Optimal rates for regularized conditional mean embedding learning.
In Advances in Neural Information Processing Systems,
volume 35, pages 4433–4445, 2022.

[Lin and Cevher, 2018]
Junhong Lin and Volkan Cevher.
Optimal distributed learning with multi-pass stochastic gradient
In International Conference on Machine Learning, pages
3092–3101. PMLR, 2018.

[Lin et al., 2020]
Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher.
Optimal rates for spectral algorithms with least-squares regression
over Hilbert spaces.
Applied and Computational Harmonic Analysis, 480
(3):0 868–890, 2020.

[Mastouri et al., 2021]
Afsaneh Mastouri, Yuchen Zhu, Limor Gultchin, Anna Korba, Ricardo Silva, Matt
Kusner, Arthur Gretton, and Krikamol Muandet.
Proximal causal learning with kernels: Two-stage estimation and
moment restriction.
In International conference on machine learning, pages
7512–7523. PMLR, 2021.

[Meunier et al., 2023]
Dimitri Meunier, Zhu Li, Arthur Gretton, and Samory Kpotufe.
Nonlinear meta-learning can guarantee faster rates.
arXiv preprint arXiv:2307.10870, 2023.

[Mollenhauer and Koltai, 2020]
Mattes Mollenhauer and Péter Koltai.
Nonparametric approximation of conditional expectation operators.
arXiv preprint arXiv:2012.12917, 2020.

[Mollenhauer et al., 2022]
Mattes Mollenhauer, Nicole Mücke, and T.J. Sullivan.
Learning linear operators: Infinite-dimensional regression as a
well-behaved non-compact inverse problem.
arXiv preprint arXiv:2211.08875, 2022.

[Park and Muandet, 2020]
Junhyung Park and Krikamol Muandet.
A measure-theoretic approach to kernel conditional mean embeddings.
Advances in Neural Information Processing Systems,
33:0 21247–21259, 2020.

[Singh et al., 2019]
Rahul Singh, Maneesh Sahani, and Arthur Gretton.
Kernel instrumental variable regression.
Advances in Neural Information Processing Systems, 32, 2019.

[Singh et al., 2023]
Rahul Singh, Liyuan Xu, and Arthur Gretton.
Kernel methods for causal functions: dose, heterogeneous and
incremental response curves.
Biometrika, page asad042, 07 2023.
ISSN 1464-3510.

[Smale and Zhou, 2004]
Steve Smale and Ding-Xuan Zhou.
Shannon sampling and function reconstruction from point values.
Bulletin of the American Mathematical Society, 410
(3):0 279–305, 2004.

[Smale and Zhou, 2005]
Steve Smale and Ding-Xuan Zhou.
Shannon sampling II: Connections to learning theory.
Applied and Computational Harmonic Analysis, 190
(3):0 285–302, 2005.

[Smale and Zhou, 2007]
Steve Smale and Ding-Xuan Zhou.
Learning theory estimates via integral operators and their
Constructive approximation, 260 (2):0
153–172, 2007.

[Song et al., 2009]
Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu.
Hilbert space embeddings of conditional distributions with
applications to dynamical systems.
In Proceedings of the 26th Annual International Conference on
Machine Learning, pages 961–968. ACM, 2009.

[Sriperumbudur et al., 2011]
Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet.
Universality, characteristic kernels and RKHS embedding of
Journal of Machine Learning Research, 120
(Jul):0 2389–2410, 2011.

[Steinwart and Christmann, 2008]
Ingo Steinwart and Andreas Christmann.
Support Vector Machines.
Springer, 2008.

[Steinwart and Scovel, 2012]
Ingo Steinwart and Clint Scovel.
Mercer’s theorem on general domains: On the interaction between
measures, kernels, and RKHSs.
Constructive Approximation, 350 (3):0
363–417, 2012.

[Steinwart et al., 2009]
Ingo Steinwart, Don Hush, and Clint Scovel.
Optimal rates for regularized least squares regression.
In COLT, pages 79–93, 2009.

[Weidmann, 1980]
Joachim Weidmann.
Linear Operators in Hilbert Spaces.
Springer, 1980.

[Wendland, 2004]
Holger Wendland.
Scattered Data Approximation.
Cambridge University Press, 2004.

[Zhang et al., 2023]
Haobo Zhang, Yicheng Li, Weihao Lu, and Qian Lin.
On the optimality of misspecified kernel ridge regression.
arXiv preprint arXiv:2305.07241, 2023.

§ APPENDICES

We now report proofs which were omitted in the main text.
As discussed in Remark <ref>, the proof
for the upper rates given in Theorem <ref> builds on the results from conditional mean embedding learning in [Li et al., 2022]. In particular, we proceed in two steps to prove Theorem <ref>. Firstly, in Section <ref>, we extend the analysis in [Li et al., 2022] to general vector-valued regression setting with a bounded regression function. Secondly, in Section <ref>, we replace this boundedness assumption by a weaker integrability condition, leading to Theorem <ref>.
In Section <ref>,
we prove the lower bound on the rates given in
Theorem <ref>.
Section <ref> contains the proofs for the results related to Sobolev spaces presented in Section <ref>.
Finally, in Section <ref>, we collect some technical supporting results.

§ LEARNING RATES FOR BOUNDED REGRESSION FUNCTION

Let $\mathcal{H}_X$ be a RKHS on $E_X$ with respect to a kernel $k_X$ such that assumptions <ref> to <ref> hold. Let $P$ be a probability distribution on $E_X \times \mathcal{Y}$ with $\pi:=P_{E_X}$ (the marginal distribution on $E_X$). Furthermore, let the conditions (<ref>), (<ref>),  (<ref>) be satisfied for some $0 < p \leq \alpha \leq 1$ and let $B_{\infty}> 0$ be a constant with $\|F_*\|_{L_{\infty}(\pi;\cY)} \leq B_{\infty}$. Then for $0 \leq \gamma \leq 1$, if (<ref>) is satisfied with $\gamma < \beta \leq 2$,

* in the case $\beta + p \leq \alpha$ and $\lambda_n = \Theta \left(\left(n/\log^{\theta}(n)\right)^{-\frac{1}{\alpha}}\right)$ for some $\theta > 1$, for all $\tau > \log(4)$ and sufficiently large $n \geq 1$, there is a constant $J > 0$ independent of $n$ and $\tau$ such that
\[\left\|[\hat{F}_{\lambda_n}] - F_*\right\|^2_{\gamma} \leq \tau^2 J\left(\frac{n}{\log ^{\theta} n}\right)^{-\frac{\beta-\gamma}{\alpha}}\]
is satisfied with $P^n$-probability not less than $1-4e^{-\tau}$.

* in the case $\beta + p > \alpha$ and $\lambda_n = \Theta \left(n^{-\frac{1}{\beta + p}}\right)$, for all $\tau > \log(4)$ and sufficiently large $n \geq 1$, there is a constant $J > 0$ independent of $n$ and $\tau$ such that
\[\left\|[\hat{F}_{\lambda_n}] - F_*\right\|^2_{\gamma} \leq \tau^2 J n^{-\frac{\beta-\gamma}{\beta + p}}\]
is satisfied with $P^n$-probability not less than $1-4e^{-\tau}$.

The proof of Theorem <ref> reveals that the index bound hidden in the phrase “sufficiently large $n$” just depends on the parameters and constants from (<ref>) and (<ref>), on $\tau$, on a lower bound $0 < c \leq 1$ for the operator norm $c \leq \|C_{XX}\|$, and on the regularization parameter sequence $(\la_n)_{n \geq 1}$. Moreover, the constant $J$ only depends on the parameters and constants from (<ref>), (<ref>),  (<ref>), (<ref>), on $B_{\infty}$, and on the regularization parameter sequence $(\la_n)_{n \geq 1}$.

Structure of the proof.
Recall that $\hat{F}_{\lambda} \in \mathcal{G}$ is defined as $\hat{F}_{\lambda} := \bar{\Psi}\left(\hat{C}_{\lambda}\right)$ where $\hat{C}_{\lambda}$ is solution of Eq. (<ref>). We introduce its population counterpart, the solution of the following problem:
C_λ:= _C ∈S_2(ℋ_X, 𝒴) 𝔼_P Y -C ϕ_X(X)^2_𝒴 + λC_S_2(ℋ_X, 𝒴)^2,     F_λ := Ψ̅(C_λ) ∈.

It can be readily shown (see for example  and ) that

\begin{equation*}
\begin{aligned}
C_{\lambda} &= C_{YX}\left(C_{XX} + \lambda Id_{\mathcal{H}_X}\right)^{-1}, \\
\hat{C}_{\lambda} &= \hat{C}_{YX}\left(\hat{C}_{XX} + \lambda Id_{\mathcal{H}_X} \right)^{-1},
\end{aligned}
\end{equation*}

where $Id_{\mathcal{H}_X}$ is the identity operator in $\cH_X$ and

\begin{equation*}
\begin{aligned}
C_{XX} &= \mathbb{E}[\phi_{X}(X)\otimes \phi_{X}(X)] \qquad~~~~~ C_{YX} = \mathbb{E}[Y\otimes \phi_{X}(X)]& \\
\hat{C}_{XX} &= \frac{1}{n}\sum_{i=1}^n\phi_{X}(x_i) \otimes \phi_{X}(x_i) \qquad\hat{C}_{YX} = \frac{1}{n}\sum_{i=1}^n y_i \otimes \phi_{X}(x_i).&
\end{aligned}
\end{equation*}

Finally, recall that $F_{*} \in L_2(\pi; \mathcal{Y})$ and $C_{*} := \Psi^{-1}\left(F_{*}\right)$ is in $S_2(L_2(\pi), \cY)$. From the definition of the vector-valued interpolation norm we introduce the following decomposition,
[F̂_λ] - F_* _γ    ≤    [F̂_λ - F_λ]_γ + [F_λ] -F_*_γ
=    [Ĉ_λ - C_λ]_S_2([ℋ]_X^γ,𝒴) + [C_λ] -C_* _S_2([ℋ]_X^γ,𝒴)

We can see that the error for the first term is mainly due to the sample approximation. We therefore refer to the first term as the Variance.  We refer to the second term as the Bias. Our proof of convergence of the bias adapts the proof by Fischer and Steinwart, 2020, and utilizes the fact that $C_{*}$ is Hilbert-Schmidt to obtain a sharp rate.

§.§ Bounding the Bias

In this section, we establish the bound on the bias. The key insight is that due to <cit.> the conditional mean function can be expressed as a Hilbert-Schmidt operator. The proof generalizes <cit.>, which addresses the scalar case; and <cit.>.

If $F_{*} \in [\mathcal{G}]^{\beta}$ is satisfied for some $0 \leq \beta \leq 2$, then the following bound is satisfied, for all $\lambda > 0$ and $0 \leq \gamma \leq \beta$:

\begin{equation}
\left\|[F_{\lambda}] - F_{*}\right\|_{\gamma}^{2} \leq\left\|F_{*}\right\|_{\beta}^{2} \lambda^{\beta-\gamma} \label{eq:bias_bound}
\end{equation}

We first recall that since $F_{*} \in [\mathcal{G}]^{\beta}$, $F_{*} = \Psi\left(C_{*} \right)$ with $C_{*} \in S_2([\mathcal{H}]_X^{\beta}, \mathcal{Y})$, furthermore $F_{\lambda} = \bar{\Psi}\left(C_{\lambda}\right)$ with $C_{\lambda} \in S_2(\mathcal{H}_X, \mathcal{Y})$. Hence, $\left\|[F_{\lambda}] - F_{*}\right\|_{\gamma} = \left\|[C_{\lambda}] - C_{*}\right\|_{S_2\left([\mathcal{H}]_X^{\gamma},\mathcal{Y}\right)}$ and $\left\|F_{*}\right\|_{\beta} = \left\|C_{*}\right\|_{S_2\left([\mathcal{H}]_X^{\beta},\mathcal{Y}\right)}$. We first decompose $[C_{\lambda}]- C_{*}$, and follow this by establishing an upper bound on the bias. Since $C_{*} \in S_2([\mathcal{H}]_X^{\beta}, \mathcal{Y}) \subseteq  S_2(\overline{\text{ran}~I_{\pi}}, \mathcal{Y})$, it admits the decomposition

\begin{equation*}
C_{*}=\sum_{i \in I} \sum_{j \in J} \check{a}_{ij} d_j \otimes [e_{i}].
\end{equation*}

where $(d_j)_{j \in J}$ is any countable basis of $\mathcal{Y}$ and $\sum_{i \in I} \sum_{j \in J} \check{a}_{ij}^2 < +\infty$ with $\check{a}_{ij}=\left\langle C_*,d_j \otimes [e_{i}] \right\rangle_{S_2(L_2(\pi), \mathcal{Y})}  = \left\langle C_* [e_i],d_j\right\rangle_{\mathcal{Y}}$ for all $i \in I, j \in J$ (see e.g. Gretton, 2013, Lecture on “testing statistical dependence”). On the other hand, $C_{\lambda} = C_{YX}\left(C_{XX} + \lambda Id_{\mathcal{H}_X} \right)^{-1}$. Since $\left(\mu_{i}^{1 / 2} e_{i}\right)_{i \in I}$ is an ONB of $\left(\operatorname{ker} I_{\pi}\right)^{\perp}$, we can complete it with an at most countable basis $\left(\bar{e}_i\right)_{i \in I'}$ (with $I \cap I' = \varnothing$) of $\operatorname{ker} I_{\pi}$ such that the union of the family forms a basis of $\mathcal{H}_X$. We get a basis of $S_2(\mathcal{H}_X, \mathcal{Y})$ through $\left(d_j \otimes f_i\right)_{i \in I \cup I', j \in J}$ where  $f_i = \mu_{i}^{1 / 2} e_{i}$ if $i \in I$ and $f_i = \bar{e}_i$ if $i \in I'$. By the spectral decomposition of $C_{XX}$ Eq. (<ref>), for $a > 0$ we then have

\begin{equation*}
\left(C_{XX}+\lambda Id_{\mathcal{H}_X}\right)^{-a}=\sum_{i \in I}\left(\mu_{i}+\lambda\right)^{-a}\left\langle\mu_{i}^{1 / 2} e_{i}, \cdot\right\rangle_{\mathcal{H}_X} \mu_{i}^{1 / 2} e_{i}+\lambda^{-a} \sum_{i \in I'}\left\langle\bar{e}_{i}, \cdot\right\rangle_{\mathcal{H}_X} \bar{e}_{i}.
\end{equation*}

C_YX    =    𝔼_P[Y ⊗ϕ_X(X)]

=    𝔼_X[ 𝔼_Y|X[Y] ⊗ϕ_X(X)]

=    𝔼_X[F_*(X) ⊗ϕ_X(X)]

=    𝔼_X[Ψ(C_*)(X) ⊗ϕ_X(X)]

=    ∑_i ∈I ∑_j ∈J ǎ_ij 𝔼_X[Ψ(d_j ⊗[e_i])(X) ⊗ϕ_X(X)]

=    ∑_i ∈I ∑_j ∈J ǎ_ij 𝔼_X[[e_i](X) d_j ⊗ϕ_X(X)].

In the last step we used the explicit form of the isomorphism between $L_2(\pi;\mathcal{Y})$ and $S_2(L_2(\pi), \mathcal{Y})$ mentioned in Remark <ref>: $\Psi$ is characterized by $\Psi\left(g \otimes f\right) = \left(x \mapsto gf(x) \right)$, for all $g \in \mathcal{Y}, f \in L_2(\pi)$. Then, using that $\left([e_{i}]\right)_{i \in I}$ is an ONS in $L_2(\pi),$

\begin{equation*}
[C_{\lambda}] = \sum_{i \in I} \sum_{j \in J} \check{a}_{ij}\frac{\mu_i}{\lambda + \mu_i} d_j \otimes [e_{i}],
\end{equation*}

and hence

\begin{equation*} %\label{eq:decomposition_bias}
[C_{\lambda}] - C_{*} = -\sum_{i \in I} \sum_{j \in J} \check{a}_{ij}\frac{\lambda}{\lambda + \mu_i} d_j \otimes [e_{i}].
\end{equation*}

We are now ready to compute the upper bound. Parseval's identity w.r.t. the ONB $\left(d_j \otimes \mu_{i}^{\gamma / 2}\left[e_{i}\right]\right)_{i \in I, j \in J}$ of $S_2\left([\mathcal{H}]_{X}^{\gamma}, \mathcal{Y}\right)$ yields

\begin{equation*}
\begin{aligned}
\left\|[C_{\lambda}] - C_{*}\right\|_{S_2\left([\mathcal{H}]_X^{\gamma},\mathcal{Y}\right)}^{2} &= \left\|\sum_{i \in I} \sum_{j \in J} \check{a}_{ij}\frac{\lambda}{\lambda + \mu_i} d_j \otimes [e_{i}]\right\|_{S_2\left([\mathcal{H}]_X^{\gamma},\mathcal{Y}\right)}^{2}\\
&= \sum_{i \in I} \sum_{j \in J} \check{a}_{ij}^2\left(\frac{\lambda}{\lambda + \mu_i}\right)^2\mu_i^{-\gamma}.
\end{aligned}
\end{equation*}

Next we notice that,

\begin{equation*}
\begin{aligned}
\left( \frac{\lambda }{\mu_i + \lambda}\right)^2\mu_i^{-\gamma} &= \left( \frac{\lambda }{\mu_i + \lambda}\right)^2 \mu_i^{-\gamma} \left( \frac{\lambda}{\lambda} \frac{\mu_i+ \lambda}{\mu_i + \lambda}\right)^{\beta-\gamma}\\
&= \lambda^{\beta-\gamma}\mu_i^{-\beta} \left( \frac{\lambda }{\mu_i + \lambda}\right)^2 \left(\frac{\mu_i}{\mu_i+ \lambda} \right)^{\beta-\gamma} \left( \frac{\mu_i+ \lambda}{ \lambda}\right)^{\beta-\gamma}\\
&= \lambda^{\beta-\gamma}\mu_i^{-\beta} \left(\frac{\mu_i}{\mu_i+ \lambda} \right)^{\beta-\gamma} \left( \frac{ \lambda}{ \lambda+ \mu_i}\right)^{2-\beta+\gamma}\\
&\leq \lambda^{\beta-\gamma}\mu_i^{-\beta},
\end{aligned}
\end{equation*}

where we used $\beta - \gamma \geq 0$ and $2 - \beta + \gamma \geq 0$. Hence,

\begin{equation*}
\begin{aligned}
\left\|[C_{\lambda}] - C_{*}\right\|_{S_2\left([\mathcal{H}]_X^{\gamma},\mathcal{Y}\right)}^{2} &\leq \lambda^{\beta - \gamma}\sum_{i \in I} \sum_{j \in J} \check{a}_{ij}^2\mu_i^{-\beta} \\
&= \lambda^{\beta-\gamma}\left\|C_{*}\right\|_{S_2\left([\mathcal{H}]_X^{\beta},\mathcal{Y}\right)}^{2}
\end{aligned}
\end{equation*}

§.§ Bounding the Variance

The proof will require several lemmas in its construction, which we now present. We start with a  lemma that allows to go from the $\gamma$-norm of embedded vector-valued maps to their norm in the original Hilbert-Schmidt space.

For $0 \leq \gamma \leq 1$ and $F \in \mathcal{G}$ the inequality
[F]_γ ≤CC_XX^1-γ/2 _S_2(ℋ_X, 𝒴)

holds, where $C = \bar{\Psi}^{-1}(F) \in S_2(\mathcal{H}_X, \mathcal{Y})$. If, in addition, $\gamma<1$ or $C \perp \mathcal{Y} \otimes \operatorname{ker} I_{\pi}$ is satisfied, then the result is an equality.

Let us fix $F \in \mathcal{G}$, and define $C := \bar{\Psi}^{-1}(F) \in S_2(\mathcal{H}_X, \mathcal{Y})$. Since $\left(\mu_{i}^{1 / 2} e_{i}\right)_{i \in I}$ is an ONB of $\left(\operatorname{ker} I_{\pi}\right)^{\perp}$, we can complete it with a basis $\left(\bar{e}_i\right)_{i \in I'}$ (with $I \cap I' = \varnothing$) of $\operatorname{ker} I_{\pi}$ such that the union of the family forms a basis of $\mathcal{H}_X$. Let $\left(d_j\right)_{j \in J}$ be a basis of $\mathcal{Y}$, we get a basis of $S_2(\mathcal{H}_X, \mathcal{Y})$ through $\left(d_j \otimes f_i\right)_{i \in I \cup I', j \in J}$ where  $f_i = \mu_{i}^{1 / 2} e_{i}$ if $i \in I$ and $f_i = \bar{e}_i$ if $i \in I'$. Then $C$ admits the decomposition
$$C=\sum_{i \in I} \sum_{j \in J} a_{ij} d_j \otimes \mu_{i}^{1 / 2} e_{i} + \sum_{i \in I'} \sum_{j \in J} a_{ij} d_j \otimes \bar{e}_{i},$$
where $a_{ij}=\left\langle C,d_j \otimes f_i \right\rangle_{S_2(\mathcal{H}_X, \mathcal{Y})}  = \left\langle C f_i,d_j\right\rangle_{\mathcal{Y}}$ for all $i \in I \cup I', j \in J$. Since
$$[C]=\sum_{i \in I} \sum_{j \in J} a_{ij} d_j \otimes \mu_{i}^{1 / 2} [e_{i}],$$
with Parseval's identity w.r.t. the ONB $\left(d_j \otimes \mu_{i}^{\gamma / 2}\left[e_{i}\right]\right)_{i \in I, j \in J}$ of $S_2([\mathcal{H}]_X^{\gamma}, \mathcal{Y})$ this yields

\left\|[C]\right\|_{S_2([\mathcal{H}]_X^{\gamma}, \mathcal{Y})}^{2}=\left\|\sum_{i \in I} \sum_{j \in J} a_{ij}\mu_{i}^{\frac{1-\gamma}{2}} d_j \otimes \mu_{i}^{\gamma / 2} [e_{i}]\right\|_{S_2([\mathcal{H}]_X^{\gamma}, \mathcal{Y})}^{2}=\sum_{i \in I} \sum_{j \in J} a_{ij}^2\mu_{i}^{1-\gamma}.

For $\gamma<1$, the spectral decomposition of $C_{XX}$ Eq. (<ref>) together with the fact that $\left(d_j \otimes \mu_{i}^{1 / 2} e_{i}\right)_{i \in I, j \in J}$ is an ONS in $S_2(\mathcal{H}_X, \mathcal{Y})$ yields

\begin{equation*}
\begin{aligned}
\left\|CC_{XX}^{\frac{1-\gamma}{2}}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{2} &= \left\|C\sum_{l \in I} \mu_l^{\frac{1-\gamma}{2}} \langle\cdot, \mu_l^{\frac{1}{2}}e_l \rangle_{\mathcal{H}_{X}} \mu_l^{\frac{1}{2}}e_l\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{2} \\ &= \sum_{i \in I}\left\|\sum_{l \in I} \mu_l^{\frac{1-\gamma}{2}} \langle \mu_i^{\frac{1}{2}}e_i, \mu_l^{\frac{1}{2}}e_l \rangle_{\mathcal{H}_{X}} \mu_l^{\frac{1}{2}}Ce_l\right\|_{\mathcal{Y}}^{2} + \sum_{i \in I'}\left\|\sum_{l \in I} \mu_l^{\frac{1-\gamma}{2}} \langle \bar{e}_i, \mu_l^{\frac{1}{2}}e_l \rangle_{\mathcal{H}_{X}} \mu_l^{\frac{1}{2}}Ce_l\right\|_{\mathcal{Y}}^{2} \\ &= \sum_{i \in I}\left\|\mu_i^{\frac{1-\gamma}{2}} \mu_i^{\frac{1}{2}}Ce_i\right\|_{\mathcal{Y}}^{2} \\ &= \sum_{i \in I} \sum_{j \in J}\mu_i^{1-\gamma}\left\langle C\left(\mu_i^{\frac{1}{2}}e_i\right), d_j\right\rangle_{\mathcal{Y}}^{2} \\ &= \sum_{i \in I} \sum_{j \in J} a_{ij}^2 \mu_i^{1-\gamma} .
\end{aligned}
\end{equation*}

This proves the claimed equality in the case of $\gamma<1$. For $\gamma=1$, we have $C_{XX}^{\frac{1-\gamma}{2}}=\operatorname{Id}_{\mathcal{H}_X}$ and the Pythagorean theorem together with Parseval's identity yields

\begin{equation*}
\begin{aligned}
\left\|CC_{XX}^{\frac{1-\gamma}{2}}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{2} &=\left\|\sum_{i \in I} \sum_{j \in J} a_{ij} d_j \otimes \mu_{i}^{1 / 2} e_{i} + \sum_{i \in I'} \sum_{j \in J} a_{ij} d_j \otimes \bar{e}_{i}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{2} \\ &=\left\|\sum_{i \in I} \sum_{j \in J} a_{ij} d_j \otimes \mu_{i}^{1 / 2} e_{i}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{2}+\left\| \sum_{i \in I'} \sum_{j \in J} a_{ij} d_j \otimes \bar{e}_{i}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{2} \\ &=\sum_{i \in I} \sum_{j \in J} a_{ij}^{2}+ \left\| \sum_{i \in I'} \sum_{j \in J} a_{ij} d_j \otimes \bar{e}_{i}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{2}
\end{aligned}
\end{equation*}

This gives the claimed equality if $C \perp \mathcal{Y} \otimes \operatorname{ker} I_{\pi}$, as well as the claimed inequality for general $C \in S_2(\mathcal{H}_X, \mathcal{Y})$. We conclude with $\|[F]\|_{\gamma} = \|[C]\|_{S_2([\mathcal{H}]_X^{\gamma}, \mathcal{Y})}$ by definition.

If $F_{*} \in [\mathcal{G}]^{\beta}$ is satisfied for some $0 \leq \beta \leq 2$, then the following bounds is satisfied, for all $\lambda>0$ and $\gamma \geq 0$:

\begin{equation} \label{eq:lemma3_2}
\left\|\left[F_{\lambda}\right]\right\|_{\gamma}^{2} \leq \left\|F_{*}\right\|_{\min \{\gamma, \beta\}}^{2} \lambda^{-(\gamma-\beta)_{+}}. %\qquad (\gamma \geq 0).
\end{equation}

By Parseval's identity

\left\|\left[F_{\lambda}\right]\right\|_{\gamma}^{2}=\sum_{i \in I} \sum_{j \in J}\left(\frac{\mu_{i}}{\mu_{i}+\lambda}\right)^{2} \mu_{i}^{-\gamma} \check{a}_{ij}^{2} .

where $\check{a}_{ij} = \left\langle C_{*} [e_i],d_j\right\rangle_{\mathcal{Y}}$ for all $i \in I, j \in J$ as in the proof of Lemma <ref>. In the case of $\gamma \leq \beta$ we bound the fraction by 1 and then Parseval's identity gives us

\left\|\left[F_{\lambda}\right]\right\|_{\gamma}^{2} \leq \sum_{i \in I} \sum_{j \in J} \mu_{i}^{-\gamma} \check{a}_{ij}^{2}=\left\|F_{*}\right\|_{\gamma}^{2} .

In the case of $\gamma>\beta$,

\left\|\left[F_{\lambda}\right]\right\|_{\gamma}^{2}=\sum_{i \in I} \sum_{j \in J}\left(\frac{\mu_{i}^{1-\frac{\gamma-\beta}{2}}}{\mu_{i}+\lambda}\right)^{2} \mu_{i}^{-\beta} \check{a}_{ij}^{2} \leq \lambda^{-(\gamma-\beta)} \sum_{i \in I} \sum_{j \in J} \mu_{i}^{-\beta} \check{a}_{ij}^{2}=\lambda^{-(\gamma-\beta)}\left\|F_{*}\right\|_{\beta}^{2} ,

where  we used Parseval's identity in the equality and Lemma 25 from [Fischer and Steinwart, 2020].

By (<ref>), the inclusion map $I^{\alpha, \infty}_{\pi}: [\mathcal{H}]_{X}^{\alpha} \hookrightarrow L_{\infty}(\pi)$ has bounded norm $A > 0$ i.e. for $f \in [\mathcal{H}]_{X}^{\alpha}$, $f$ is $\pi-$a.e. bounded and $\|f\|_{\infty} \leq A\|f\|_{\alpha}$. We now show that (<ref>) automatically implies that the inclusion operator for $[\mathcal{G}]^{\alpha}$ is bounded.

Under (<ref>) the inclusion operator $\mathcal{I}_{\pi}^{\alpha, \infty}: [\mathcal{G}]^{\alpha} \hookrightarrow L_{\infty}(\pi; \mathcal{Y})$ is bounded with operator norm less than or equal to $A$.

$L_{\infty}(\pi; \mathcal{Y})$ denotes the space of $\mathcal{F}_{E_X} - \mathcal{F}_{\mathcal{Y}}$ measurable $\mathcal{Y}$-valued functions (gathered by $\pi$-equivalent classes) that are essentially bounded with respect to $\pi$. $L_{\infty}(\pi; \mathcal{Y})$ is endowed with the norm $\|F\|_\infty := \inf \{c \geq 0 : \|F(x)\|_{\mathcal{Y}} \leq c \text{ for $\pi$-almost all } x \in E_X\}$.

For every $F \in [\mathcal{G}]^{\alpha}$, there is a sequence $b_{ij} \in \ell_2(I \times J)$ such that for $\pi-$almost all $x \in E_X$,
\[F(x) = \sum_{i \in I, j \in J} b_{ij} d_j \mu_i^{\alpha/2}[e_i](x)\]
where $(d_j)_{j \in J}$ is any orthonormal basis of $\mathcal{Y}$ and $\|F\|_{\alpha}^2  = \sum_{i \in I, j \in J} b_{ij}^2$. We consider $F \in [\mathcal{G}]^{\alpha}$ such that $\sum_{i \in I, j \in J} b_{ij}^2 \leq 1$. For $\pi-$almost all $x \in E_X$,

\begin{equation*} %\label{eq:inf_vector_embedding}
\begin{aligned}
\|F(x)\|_{\mathcal{Y}}^2 &= \left\|\sum_{j \in J}\left(\sum_{i \in I} b_{ij}\mu_i^{\alpha/2}[e_i](x)\right)d_j\right\|_{\mathcal{Y}}^2 \\
&= \sum_{j \in J}\left(\sum_{i \in I} b_{ij}\mu_i^{\alpha/2}[e_i](x)\right)^2 \\
& \leq \sum_{j \in J} \left(\sum_{i \in I}b_{ij}^2\right)\left(\sum_{i \in I}\mu_i^{\alpha}[e_i]^2(x)\right)\\
&\leq A^2 \sum_{j \in J}\sum_{i \in I} b_{ij}^2 \\ &\leq A^2
\end{aligned}
\end{equation*}

where we used the Cauchy-Schwarz inequality for each $j \in J$ for the first inequality and a consequence of (<ref>) in the second inequality (see Theorem 9 in Fischer and Steinwart, 2020). We therefore conclude $\|\mathcal{I}_{\pi}^{\alpha, \infty}\| \leq A$.

Combining Lemmas <ref>, <ref> and <ref> we have the following result.

If $F_{*} \in [\mathcal{G}]^{\beta}$ and (<ref>) are satisfied for some $0 \leq \beta \leq 2$ and $0< \alpha \leq 1$, then the following bounds are satisfied, for all $0< \lambda \leq 1$:

\begin{equation} \label{eq:lemma4_1}
\left\|\left[F_{\lambda}\right] - F_{*}\right\|_{L_\infty}^{2} \leq \left(\left\|F_{*}\right\|_{L_\infty} + A\|F_*\|_{\beta}\right)^2 \lambda^{\beta - \alpha},
\end{equation}

\begin{equation} \label{eq:lemma4_2}
\left\|\left[F_{\lambda}\right]\right\|_{L_\infty}^{2} \leq A^2\left\|F_{*}\right\|_{\min \{\alpha, \beta\}}^{2} \lambda^{-(\alpha-\beta)_{+}}.
\end{equation}

For Eq. (<ref>), we use Lemma <ref> and Eq. (<ref>) in Lemma <ref>.

\begin{equation*}
\left\|\left[F_{\lambda}\right]\right\|_{\infty}^{2} \leq A^2 \left\|\left[F_{\lambda}\right]\right\|_{\alpha}^{2} \leq A^2\left\|F_{*}\right\|_{\min \{\alpha, \beta\}}^{2} \lambda^{-(\alpha-\beta)_{+}}
\end{equation*}

To show Eq. (<ref>), in the case $\beta \leq \alpha$ we use the triangle inequality, Eq. (<ref>) and $\lambda \leq 1$ to obtain

\begin{equation*}
\begin{aligned}
\left\|\left[F_{\lambda}\right] - F_{*}\right\|_{\infty} &\leq \left\|F_{*}\right\|_{\infty} + \left\|\left[F_{\lambda}\right]\right\|_{\infty} \\ &\leq \left(\left\|F_{*}\right\|_{\infty} + A\left\|F_{*}\right\|_{\beta} \right)\lambda^{-\frac{\alpha-\beta}{2}}
\end{aligned}
\end{equation*}

In the case $\beta > \alpha$, Eq. (<ref>) is a consequence of Lemma <ref> and Eq. (<ref>) in Lemma <ref> with $\gamma = \alpha$,

\begin{equation*}
\left\|\left[F_{\lambda}\right] - F_{*}\right\|_{\infty}^{2} \leq A^2 \left\|\left[F_{\lambda}\right] - F_{*}\right\|_{\alpha}^{2} \leq A^2 \left\|F_{*}\right\|_{\beta}^{2} \lambda^{\beta-\alpha} \leq \left(\left\|F_{*}\right\|_{\infty} + A\|F_*\|_{\beta}\right)^2 \lambda^{\beta - \alpha}.
\end{equation*}

Let $\mathcal{H}_X$ be a RKHS on $E_X$ with respect to a kernel $k_X$ such that assumptions <ref> to <ref> hold. Let $P$ be a probability distribution on $E_X \times \mathcal{Y}$ with $\pi:=P_{E_X}$ (the marginal distribution on $E_X$). Furthermore, let $\|F_*\|_{\infty} < \infty$, (<ref>) and (<ref>) be satisfied. We define

\begin{aligned}
M(\lambda) &= \left\|[F_{\lambda}]-F_*\right\|_{\infty},\\
\mathcal{N}(\lambda) &=\operatorname{tr}\left(C_{XX}\left(C_{XX}+\lambda \operatorname{Id}_{\cH_X}\right)^{-1}\right), \\
Q_{\lambda} &=\max \{M(\lambda), R \}, \\
g_{\lambda}& = \log \left( 2e\mathcal{N}(\lambda) \frac{\|C_{XX}\|+\lambda}{\|C_{XX}\|}\right).
\end{aligned}

Then, for $0 \leq \gamma \leq 1$, $\tau \geq 1$, $\lambda > 0$ and $n \geq 8A^{2} \tau g_{\lambda} \lambda^{-\alpha}$, with probability $1-4e^{-\tau}$:
[Ĉ_λ - C_λ]_S_2([ℋ]_X^γ,𝒴)^2 ≤576τ^2/nλ^γ(σ^2 𝒩(λ)+F_*-[F_λ]_L_2(π; 𝒴)^2A^2/λ^α + 2Q_λ^2A^2/nλ^α)

We first decompose the variance term as
[Ĉ_λ - C_λ]_S_2([ℋ]_X^γ,𝒴 )

=    [Ĉ_Y X(Ĉ_X X+λId__X)^-1-C_Y X(C_X X+λId__X)^-1]_S_2([ℋ]_X^γ,𝒴 )

≤    (Ĉ_Y X(Ĉ_X X+λId__X )^-1-C_Y X(C_X X+λId__X)^-1) C_X X^1-γ/2_S_2(ℋ_X, 𝒴)

≤    (Ĉ_Y X-C_Y X(C_X X+λId__X)^-1(Ĉ_X X+λId__X))(C_X X+λId__X)^-1/2_S_2(ℋ_X, 𝒴)

·(C_X X+λId__X )^1/2(Ĉ_X X+λId__X )^-1(C_X X+λId__X )^1/2_ℋ_X →ℋ_X

·(C_X X+λId__X )^-1/2C_X X^1-γ/2_ℋ_X →ℋ_X

where we used Lemma <ref> in the first inequality. Eq. (<ref>) is bounded as
in Lemma $17$ and Theorem $16$ in [Fischer and Steinwart, 2020],

\left\|\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{\frac{1}{2}}\left(\hat{C}_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-1}\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{\frac{1}{2}}\right\|_{\mathcal{H}_X \to \mathcal{H}_X}\ \leq 3

for $n \geq 8A^{2} \tau g_{\lambda} \lambda^{-\alpha}$ with probability $1-2e^{-\tau}$ for all $\tau \geq 1$. For Eq. (<ref>) we have, using Lemma 25 from [Fischer and Steinwart, 2020]

\left\|\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-\frac{1}{2}}C_{X X}^{\frac{1-\gamma}{2}}\right\|_{\mathcal{H}_X \to \mathcal{H}_X}\ \leq \sqrt{\sup _{i} \frac{\mu_{i}^{1-\gamma}}{\mu_{i}+\lambda}} \leq \lambda^{-\frac{\gamma}{2}}.

Finally for the bound of Eq. (<ref>) Lemma <ref> show that for $\tau \geq 1$, $\lambda > 0$ and $n \geq 1$ with probability $1-2e^{-\tau}$:

\begin{equation}
\begin{aligned}
&\bigg\|\left(\hat{C}_{Y X}-C_{Y X}\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-1}(\hat{C}_{X X}+\lambda \operatorname{Id}_{\cH_X} )\right)\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-\frac{1}{2}}\bigg\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^2 \\ &\leq \frac{64\tau^2}{n}\left(\sigma^{2} \mathcal{N}(\lambda)+\frac{\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}}{\lambda^{\alpha}} + \frac{2Q_{\lambda}^2A^2}{n\lambda^{\alpha}}\right).\nonumber
\end{aligned}
\end{equation}

Assume the conditions in Theorem <ref> hold. Then for $\tau \geq 1$, $\lambda > 0$ and $n \geq 1$ with probability $1-2e^{-\tau}$:

\begin{equation}
\begin{aligned}
&\bigg\|\left(\hat{C}_{Y X}-C_{Y X}\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-1}(\hat{C}_{X X}+\lambda \operatorname{Id}_{\cH_X} )\right)\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-\frac{1}{2}}\bigg\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^2 \\ &\leq \frac{64\tau^2}{n}\left(\sigma^{2} \mathcal{N}(\lambda)+\frac{\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}}{\lambda^{\alpha}} + \frac{2Q_{\lambda}^2A^2}{n\lambda^{\alpha}}\right). \nonumber
\end{aligned}
\end{equation}

We begin with the decomposition
Ĉ_Y X-C_Y X(C_X X+λId__X )^-1(Ĉ_X X+λId__X )

=    Ĉ_Y X-C_Y X(C_X X+λId__X )^-1(C_X X+λId__X + Ĉ_X X-C_X X)

=    Ĉ_Y X-C_Y X+C_Y X(C_X X+λId__X )^-1(C_X X-Ĉ_X X)

=    Ĉ_Y X-C_Y X(C_X X+λId__X )^-1 Ĉ_X X-(C_Y X-C_Y X(C_X X+λId__X )^-1 C_X X)

=    Ĉ_Y X-C_Y X(C_X X+λId__X )^-1 𝔼̂[ϕ_X(X) ⊗ϕ_X(X)]-(C_YX - C_Y X(C_X X+λId__X )^-1 𝔼[ϕ_X(X) ⊗ϕ_X(X)])

=    𝔼̂[(Y-F_λ(X)) ⊗ϕ_X(X)]-𝔼[(Y-F_λ(X)) ⊗ϕ_X(X)]

where we denote $\hat{\mathbb{E}}[\phi_X(X) \otimes \phi_X(X)] = \frac{1}{n}\sum_{i=1}^n \phi_X(x_i) \otimes \phi_X(x_i)$. We wish to apply Theorem <ref> with $H = S_2(\mathcal{H}_X, \mathcal{Y})$. Consider the random variables $\xi_{0}, \xi_{2}: E_X \times \mathcal{Y} \rightarrow \mathcal{Y} \otimes \mathcal{H}_X$ defined by
ξ_0(x, y)   :=(y-F_λ(x)) ⊗ϕ_X(x),

ξ_2(x, y)   :=ξ_0(x, y)(C_XX+λId__X )^-1 / 2.

Since our kernel $k_X$ is bounded,

\begin{equation*}
\begin{aligned}
\left\|\xi_{0}(x, y)\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})} &= \left\|y-F_{\lambda}(x)\right\|_{\mathcal{Y}}\|\phi_X(x)\|_{\mathcal{H}_X} \\
&\leq \left\|y-F_{\lambda}(x)\right\|_{\cY}\kappa_X \\
&\leq \left(\left\|y\right\|_{\cY} + \left\|F_{\lambda}\right\|_{L_{\infty}(\pi; \mathcal{Y})}\right)\kappa_X, \\
\end{aligned}
\end{equation*}

is satisfied for $\pi-$almost all $x \in E_X$ and $F_{\lambda}$ is $\pi$-almost surely bounded by Lemma <ref>. Since $y \in L_2(\pi;\cal Y)$, we have that $y \in L_1(\pi;\cal Y)$.

This yields

\begin{equation}
\frac{1}{n} \sum_{i=1}^{n}\left(\xi_{2}\left(x_{i}, y_{i}\right)-\mathbb{E} \xi_{2}\right) = \hat{\mathbb{E}} \xi_{2}-\mathbb{E} \xi_{2} = \left(\hat{C}_{Y X}-C_{Y X}\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-1}\left(\hat{C}_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)\right)\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-\frac{1}{2}}, \label{eq:noise_decom}
\end{equation}

and therefore Eq. (<ref>) coincides with the left hand side of a Bernstein's inequality for $H$-valued random variables (Theorem <ref>). Consequently, it remains to bound the $m$-th moment of $\xi_{2}$, for $m \geq 2$,

\begin{equation}
\mathbb{E}\left\|\xi_{2}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{m}=\int_{E_X}\left\|\left(C_{XX}+\lambda \operatorname{Id}_{\cH_X}\right)^{-1 / 2} \phi_X(x)\right\|_{\mathcal{H}_X}^{m} \int_{\mathcal{Y}}\left\|y-F_{\lambda}(x)\right\|_{\mathcal{Y}}^{m} p(x, \mathrm{~d} y) \mathrm{d} \pi(x). \label{eq:xi_decom}
\end{equation}

First, we consider the inner integral. Using the triangle inequality and (<ref>),
∫_𝒴y-F_λ(x)_𝒴^m p(x,  d y)    ≤    2^m-1(Id_𝒴-F_*(x)_L_m(p(x, ·); 𝒴)^m+F_*(x)-F_λ(x)_𝒴^m)

≤   1/2 m !(2 R)^m-2 2 σ^2+2^m-1F_*(x)-F_λ(x)_𝒴^m.

for $\pi$-almost all $x \in E_X$. If we plug this bound into the outer integral and use the abbreviation $h_{x}:=\left(C_{XX}+\lambda\operatorname{Id}_{\cH_X}\right)^{-1 / 2} \phi_X(x)$ we get

\begin{equation} \label{eq:m_moment_1}
\begin{aligned}
\mathbb{E}\left\|\xi_{2}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{m} \leq \frac{1}{2} m !(2 R)^{m-2} 2 \sigma^{2} \int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{m} \mathrm{~d} \pi(x) +2^{m-1} \int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{m}\left\|F_{*}(x)-F_{\lambda}(x)\right\|_{\mathcal{Y}}^{m} \mathrm{~d} \pi(x).
\end{aligned}
\end{equation}

Using Lemma <ref>, we can bound the first term in Eq. (<ref>) above by

\begin{aligned}
\frac{1}{2} m !(2 R)^{m-2} 2 \sigma^{2}\int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{m} \mathrm{~d} \pi(x) & \leq \frac{1}{2} m !(2 R)^{m-2} 2 \sigma^{2}\left(\frac{A}{\lambda^{\alpha / 2}}\right)^{m-2} \int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{2} \mathrm{~d} \pi(x) \\
&=\frac{1}{2}m !\left(\frac{2RA}{\lambda^{\alpha / 2}}\right)^{m-2} 2\sigma^{2} \mathcal{N}(\lambda) \\
&\leq \frac{1}{2} m !\left(\frac{2Q_{\lambda} A}{\lambda^{\alpha / 2}}\right)^{m-2} 2 \sigma^{2} \mathcal{N}(\lambda)
\end{aligned}

where we only used $R \leq Q_{\lambda}$ in the last step. Again, using Lemma <ref>, the second term in Eq. (<ref>) can be bounded by

\begin{aligned}
& 2^{m-1} \int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{m}\left\|F_{*}(x)-F_{\lambda}(x)\right\|_{\mathcal{Y}}^{m} \mathrm{~d} \pi(x) \\
\leq & \frac{1}{2}\left(\frac{2A}{\lambda^{\alpha / 2}}\right)^{m}M(\lambda)^{m-2} \int_{E_X}\left\|F_{*}(x) - F_{\lambda}(x)\right\|_{\mathcal{Y}}^{2} \mathrm{~d} \pi(x) \\
=& \frac{1}{2}\left(\frac{2AM(\lambda)}{\lambda^{\alpha / 2}}\right)^{m-2}\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2} \frac{4A^2}{\lambda^{\alpha}} \\
\leq & \frac{1}{2} m !\left(\frac{2Q_{\lambda}A}{\lambda^{\alpha / 2}}\right)^{m-2}\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2} \frac{2A^2}{\lambda^{\alpha}},
\end{aligned}

where we only used $M(\lambda) \leq Q_{\lambda}$ and $2 \leq m!$ in the last step. Finally, we get

\begin{equation}\label{eq:xi2_m}
\mathbb{E}\left\|\xi_{2}\right\|_{S_2(\mathcal{H}_X, \cY)}^{m} \leq \frac{1}{2} m !\left(\frac{2Q_{\lambda}A}{\lambda^{\alpha / 2}}\right)^{m-2} 2\left(\sigma^{2} \mathcal{N}(\lambda)+\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2} \frac{A^{2}}{\lambda^{\alpha}}\right)
\end{equation}

and an application of Bernstein's inequality from Theorem <ref> with $L=2Q_{\lambda}A\lambda^{-\alpha / 2}$ and
$\sigma^{2}=2\left(\sigma^{2} \mathcal{N}(\lambda)+\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}\lambda^{-\alpha}\right)$ yields the bound. Putting all the terms together, we obtain our result.

§.§ Learning Rates - Proof of Theorem <ref>

In this section, we aim to establish our upper bound on the learning rate for vector-valued regression by combining the learning rates obtained for the bias and variance.

Let us fix some $\tau \geq 1$ and a lower bound $0 < c \leq 1$ with $c \leq \|C_{XX}\|$. We first show that Theorem <ref> is applicable. To this end, we prove that there is an index bound $n_0 \geq 1$ such that $n \geq 8A^{2} \tau g_{\lambda_n} \lambda_n^{-\alpha}$ is satisfied for all $n \geq n_0$. Since $\lambda_n \rightarrow 0$ we choose $n_0' \geq 1$ such that $\lambda_n \leq c \leq \min\{1, \|C_{XX}\|\}$ for all $n \geq n_0'$. We get for $n \geq n_0'$,

\begin{equation}
\begin{aligned}
\frac{8A^{2} \tau g_{\lambda_{n}} \lambda_{n}^{-\alpha}}{n} &=\frac{8A^{2} \tau \lambda_{n}^{-\alpha}}{n} \cdot \log \left(2 e \mathcal{N}\left(\lambda_{n}\right) \frac{\left\|C_{XX}\right\|+\lambda_{n}}{\left\|C_{XX}\right\|}\right) \nonumber\\
& \leq \frac{8A^{2} \tau \lambda_{n}^{-\alpha}}{n} \cdot \log \left(4 D e \lambda_{n}^{-p}\right) \nonumber \\
&=8A^{2}\tau \left(\frac{\log\left(4 D e\right) \lambda_{n}^{-\alpha}}{n}+\frac{p \lambda_{n}^{-\alpha} \log \lambda_{n}^{-1}}{n}\right) \label{eq:a_l}
\end{aligned}
\end{equation}

where the second step uses Lemma <ref>. Hence, it is enough to show $\frac{\log(\lambda_n^{-1})}{n\lambda_n^{\alpha}} \rightarrow 0$. We consider the cases $\beta + p \leq \alpha$ and $\beta + p > \alpha$.

* $\beta + p \leq \alpha.$ By substituting that $\lambda_n = \Theta \left(\left(\frac{n}{\log^{\theta} n}\right)^{-\frac{1}{\alpha}}\right)$ for some $\theta > 1$ we have
\[\frac{\lambda_{n}^{-\alpha} \log \lambda_{n}^{-1}}{n}=\Theta\left(\frac{\log(n)}{n}\frac{n}{\log^{\theta}(n)}\right)  = \Theta \left( \frac{1}{\log^{\theta-1}(n)}\right) \rightarrow 0, \text{ as }~n \rightarrow \infty.\]

* $\beta + p > \alpha.$ By substituting that $\lambda_n = \Theta \left(n^{-\frac{1}{\beta + p}}\right)$ and using $1 - \frac{\alpha}{\beta + p} > 0$ we have
\[\frac{\lambda_{n}^{-\alpha} \log \lambda_{n}^{-1}}{n}=\Theta\left(\frac{\log(n)}{n}n^{\frac{\alpha}{\beta + p}}\right)  = \Theta \left( \frac{\log(n)}{n^{1-\frac{\alpha}{\beta + p}}}\right) \rightarrow 0, \text{ as }~n \rightarrow \infty.\]

Consequently, there is a $n_0 \geq n_0'$ with $n \geq 8A^{2} \log \tau g_{\lambda_n} \lambda_n^{-\alpha}$ for all $n \geq n_0$. Moreover, $n_0$ just depends on $\lambda_n, c, D, \tau, A$, and on the parameters $\alpha,p$.

Let $n \geq n_0$ be fixed. By Theorem <ref>, we have
[Ĉ_λ_n - C_λ_n]_S_2([ℋ]_X^γ, 𝒴)^2 ≤576τ^2/nλ_n^γ(σ^2 𝒩(λ_n)+F_*-[F_λ]_L_2(π; 𝒴)^2A^2/λ_n^α + 2Q_λ_n^2A^2/nλ_n^α).

Using Lemma <ref> and Lemma <ref> with $\gamma=0$, we have
[Ĉ_λ_n-C_λ_n]_S_2([ℋ]_X^γ, 𝒴)^2 ≤576τ^2/nλ_n^γ(σ^2 Dλ_n^-p+A^2F_*_β^2λ_n^β-α + 2Q_λ_n^2A^2/nλ_n^α)
For the last term, using the definition of $Q_{\lambda}$ in Theorem <ref> with Lemma <ref> and $\lambda_n \leq 1,$ we get
Q_λ_n^2    =    max{R^2, [F_λ]-F_*_∞^2}
≤    max{R^2, (F_*_∞ + A F_*_β)^2 λ_n^-(α-β)}

≤    K_0 λ_n^-(α-β)_+,
where $K_0 := \max\left\{R^2, \left(B_{\infty} + A\|F_*\|_{\beta}\right)^2\right\}$. Thus,
[Ĉ_λ_n-C_λ_n]_S_2([ℋ]_X^γ, 𝒴)^2 ≤576τ^2/nλ_n^γ(σ^2 Dλ_n^-p+A^2F_*_β^2λ_n^β-α + 2A^2K_01/nλ_n^α+(α-β)_+) .

For the first and second terms in the bracket, we use again the fact that $\lambda_n \leq 1,$ and get

\[D\sigma^2\lambda_n^{-p} + A^2\|F_*\|_{\beta}^2 \lambda_n^{-(\alpha-\beta)} \leq \left(D\sigma^2 + A^2\|F_*\|_{\beta}^2\right)\max\{\lambda_n^{-p}, \lambda_n^{-(\alpha-\beta)}\} \leq K_1 \lambda_n^{-\max\{p,\alpha-\beta\}}\]

with $K_1 := D\sigma^2 + A^2\|F_*\|_{\beta}^2$. We now have
[Ĉ_λ_n-C_λ_n]_S_2([ℋ]_X^γ, 𝒴)^2    ≤    576τ^2/nλ_n^γ(K_1 λ_n^-max{p,α-β} + 2A^2K_01/nλ_n^α+(α-β)_+)

=     576τ^2/nλ_n^γ+max{p,α-β}(K_1 + 2A^2K_01/nλ_n^α+(α-β)_+-max{p,α-β}).
Again, we treat the cases $\beta + p \leq \alpha$ and $\beta + p > \alpha$ separately.

* $\beta + p \leq \alpha$. In this case we have
\[\alpha +(\alpha-\beta)_{+}-\max\{p,\alpha-\beta\} = \alpha.\]
Since \(\lambda_n = \Theta \left(\left(\frac{n}{\log^{\theta} n}\right)^{-\frac{1}{\alpha}}\right),\) for some $\theta > 1$ we therefore have
\[\frac{1}{n\lambda_n^{\alpha +(\alpha-\beta)_{+}-\max\{p,\alpha-\beta\}}} = \frac{1}{n\lambda^{\alpha}} = \Theta\left( \frac{1}{\log^{\theta}n}\right).\]

* $\beta + p > \alpha$. We have $p > \alpha - \beta$ and \(\lambda_n = \Theta \left(n^{-\frac{1}{\beta + p}}\right),\) and hence
\[\frac{1}{n\lambda_n^{\alpha +(\alpha-\beta)_{+}-\max\{p,\alpha-\beta\}}} = \frac{1}{n\lambda_n^{\alpha+(\alpha-\beta)_{+} -p}} = \Theta\left(\left(\frac{1}{n}\right)^{1-\frac{\alpha+(\alpha-\beta)_{+}-p}{\beta+p}}\right).\]
Using $p > \alpha - \beta$ again gives us
$$1-\frac{\alpha+(\alpha-\beta)_{+}-p}{\beta+p} = \frac{2p - (\alpha-\beta)_{+} - (\alpha - \beta)}{\beta+p} > 0.$$

As such, there is a constant $K_2 > 0$ with

\[\left\|[\hat{F}_{\lambda_n} - F_{\lambda_n}]\right\|_{\gamma}^2  =\left\|[\hat{C}_{\lambda_n}-C_{\lambda_n}]\right\|_{S_2([\mathcal{H}]_X^{\gamma}, \mathcal{Y})}^2 \leq 576 \frac{\tau^2}{n\lambda_n^{\gamma+\max\{p,\alpha-\beta\}}}\left(K_1 + 2A^2K_0K_2\right)\]
for all $n \geq n_0.$ Defining $K_3 := 576(K_1 + 2A^2K_0K_2)$, and using the bias-variance splitting from Eq. (<ref>) and Lemma <ref>, we have

[F̂_λ_n]-F_*_γ^2    ≤    2C_*_S_2([ℋ]_X^β, 𝒴)^2 λ_n^β-γ + 2K_3τ^2/nλ_n^γ+max{p,α-β}

≤    τ^2 λ_n^β-γ(2C_*_S_2([ℋ]_X^β, 𝒴)^2+2K_3 1/nλ_n^max{β+p,α}),
where we used $\tau \geq 1$. Since in both cases $\beta + p \leq \alpha$ and $\beta + p > \alpha$, $\lambda_n \succcurlyeq n^{-1/\max\{\alpha, \beta + p\}}$ there is some constant $J>0$ such that
\[\left\|[\hat{F}_{\lambda_n}]-F_*\right\|_{\gamma}^2 \leq  \tau^2 J \lambda_n^{\beta - \gamma}\]
for all $n \geq n_0$.

§ PROOF OF THEOREM <REF>

In this section, we prove our main results, Theorem <ref>. The case where $\beta \geq \alpha$ is identical to Theorem <ref>. Hence we will only focus on the rate when $\beta < \alpha$ without assuming the boundedness of $F_*$. We adopt the same risk decomposition as in Eq. (<ref>). The bias is upper bounded in the same way as in Section <ref>. For the variance, we have the following results.

Let $\mathcal{H}_X$ be a RKHS on $E_X$ with respect to a kernel $k_X$ such that assumptions <ref> to <ref> hold. Let $P$ be a probability distribution on $E_X \times \mathcal{Y}$ with $\pi:=P_{E_X}$ (the marginal distribution on $E_X$). Furthermore, let (<ref>), (<ref>) and (<ref>) be satisfied. Suppose that $F_* \in L_q(\pi;\cal Y)$ and $\|F_*\|_{L_q} \leq C_q < \infty$ for some $q \geq 1$. Denote $\Omega_0 = \left\{x \in E_X: \|F_*(x) \|_{\cY} \leq t \right\}$ and
\[Q(t,\lambda) := \max \{t+ 2A\left\|F_{*}\right\|_{\beta} \lambda^{\frac{\be-\al}{2}},R\}.\]
Then, for $0 \leq \gamma \leq 1$, $\tau \geq 1$, $\lambda > 0$ and $n \geq 8A^{2} \tau g_{\lambda} \lambda^{-\alpha}$, with probability $1 - 4e^{-\tau}-\tau_n$ with $\tau_n = 1-\left(1-\frac{C_q^q}{t^q}\right)^n$:
[Ĉ_λ - C_λ]_S_2([ℋ]_X^γ,𝒴)^2    ≤   1152τ^2/nλ^γ(σ^2 𝒩(λ)+F_*-[F_λ]_L_2(π; 𝒴)^2A^2/λ^α + 2Q(t,λ)^2A^2/nλ^α)

+18/λ^γ(σ^2 𝒩(λ)+F_*-[F_λ]_L_2(π; 𝒴)^2 A^2/λ^α) C_q^q/t^q,

where $g_{\la}$ is defined in Theorem <ref>.

The proof adopts the same strategy as in Theorem <ref>. The difference is that for Eq. (<ref>), instead of using Lemma <ref>, we use Lemma <ref> below.

Lemma <ref> provides the upper bound under the assumption that $\|F_*\|_{L_{\infty}(\pi; \cY)} < \infty$. For $\beta \geq \alpha$ this assumption is automatically satisfied by the condition (<ref>), but for $\beta < \alpha$, this assumption remains crucial. However, as indicated in [Zhang et al., 2023], in the scalar-valued setting, when $\alpha - p < \be < \alpha$, this assumption can be replaced by an assumption of the form $\|F_*\|_{L_{q}(\pi; \cY)} < \infty$ for some $q\geq 1$. Below, we generalise their technique to the vector-valued setting.

Assume the conditions in Theorem <ref> holds. Then for $\tau \geq 1$, $\lambda > 0$ and $n \geq 1$ with probability over $1 - 2e^{-\tau}-\tau_n$ with $\tau_n = 1-\left(1-\frac{C_q^q}{t^q}\right)^n$,

\begin{equation}
\begin{aligned}
&\bigg\|\left(\hat{C}_{Y X}-C_{Y X}\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-1}(\hat{C}_{X X}+\lambda \operatorname{Id}_{\cH_X} )\right)\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-\frac{1}{2}}\bigg\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^2 \\ &\leq \frac{384\tau^2}{n}\left(\sigma^{2} \mathcal{N}(\lambda)+\frac{\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}}{\lambda^{\alpha}} + \frac{2Q(t,\lambda)^2A^2}{n\lambda^{\alpha}}\right) +6\left(\sigma^{2} \mathcal{N}(\lambda)+\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2} \frac{A^{2}}{\lambda^{\alpha}}\right) \frac{C_q^q}{t^{q}}. \label{eq:var_q}
\end{aligned}
\end{equation}

Denote $\Omega_0 := \left\{x \in E_X: \|F_*(x) \|_{\cY} \leq t \right\}$ and $\Omega_1 = E_X\backslash\Omega_0$. Since $\|F_*\|_{L_q} \leq C_q$, we have

\begin{equation}
\P(X \in \Omega_1) = \P(\|F_*(X)\|_{\cY} >t)\leq \frac{\mathbb{E}\left[\|F_*(X)\|^q_{\cY}\right]}{t^q} \leq \frac{C_q^q}{t^q}.
\end{equation}

Let $\xi_2(x,y)$ be defined as in Eq. (<ref>). As shown before in Eq. (<ref>), we have

\left(\hat{C}_{Y X}-C_{Y X}\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-1}\left(\hat{C}_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)\right)\left(C_{X X}+\lambda \operatorname{Id}_{\cH_X} \right)^{-\frac{1}{2}}=\frac{1}{n} \sum_{i=1}^{n}\left(\xi_{2}\left(x_{i}, y_{i}\right)-\mathbb{E} \xi_{2}\right).

Decomposing $\xi_2 = \xi_2\mathbbm{1}_{x\in \Omega_0} + \xi_2\mathbbm{1}_{x\in \Omega_1} $, we have

1/n∑_i=1^nξ_2(x_i, y_i)-𝔼 ξ_2 ^2_S_2(ℋ_X, 𝒴) ≤       3 1/n∑_i=1^nξ_2(x_i, y_i)1_x_i∈Ω_0-𝔼[ ξ_21_X ∈Ω_0] ^2_S_2(ℋ_X, 𝒴) _I

+ 3 1/n∑_i=1^nξ_2(x_i, y_i)1_x_i∈Ω_1 ^2_S_2(ℋ_X, 𝒴)_II + 3 𝔼[ ξ_21_X∈Ω_1 ]^2_S_2(ℋ_X, 𝒴)

For term I, we employ Proposition <ref> and obtain that for any $\tau \geq 1$, with probability over $1 - 2e^{-\tau}$,

\begin{equation}
\begin{aligned}
\bigg\|\frac{1}{n} \sum_{i=1}^{n}\left(\xi_{2}\left(x_{i}, y_{i}\right)\mathbbm{1}_{x_i\in \Omega_0}-\mathbb{E} \xi_{2}\mathbbm{1}_{x\in \Omega_0}\right)\bigg\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^2 \leq \frac{64\tau^2}{n}\left(\sigma^{2} \mathcal{N}(\lambda)+\frac{\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}}{\lambda^{\alpha}} + \frac{2Q(t,\lambda)^2A^2}{n\lambda^{\alpha}}\right):=C_{I}. \nonumber
\end{aligned}
\end{equation}

For term II, we have
τ_n :=(II > C_I)    ≤    (∃x_i, s.t.  x_i∈Ω_1) = 1-(x_i∈Ω_0, ∀i =[n])

=    1-(X∈Ω_0)^n

=    1-(F_*(X)_ ≤t)^n

≤    1-(1-C_q^q/t^q)^n.

For term III, we have
𝔼 ξ_21_X∈Ω_1 ^2_S_2(ℋ_X, 𝒴)    ≤    𝔼[ ξ_2 _S_2(ℋ_X 𝒴)1_X∈Ω_1]^2

≤     𝔼[  ξ_2^2_S_2(ℋ_X 𝒴)] (X ∈Ω_1)

≤    2(σ^2 𝒩(λ)+F_*-[F_λ]_L_2(π; 𝒴)^2 A^2/λ^α) C_q^qt^-q.

where for the last inequality, we used Eq. (<ref>).

Suppose that conditions (<ref>), (<ref>) and (<ref>) are satisfied with $0 \leq \alpha \leq 1$ and $\beta \in(0,2]$. Let $\xi_2(x,y)$ be defined as in Eq. (<ref>) and $\Omega_0 = \left\{x \in E_X: \|F_*(x) \|_{\cY} \leq t \right\}$. We have for any $\tau \geq 1$, with probability over $1 - 2e^{-\tau}$,

\begin{equation}
\begin{aligned}
\bigg\|\frac{1}{n} \sum_{i=1}^{n}\left(\xi_{2}\left(x_{i}, y_{i}\right)\mathbbm{1}_{x_i\in \Omega_0}-\mathbb{E} \xi_{2}\mathbbm{1}_{X\in \Omega_0}\right)\bigg\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^2 \leq \frac{64\tau^2}{n}\left(\sigma^{2} \mathcal{N}(\lambda)+\frac{\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}}{\lambda^{\alpha}} + \frac{2Q(t,\lambda)^2A^2}{n\lambda^{\alpha}}\right). \nonumber
\end{aligned}
\end{equation}

We would like to apply the Bernstein's inequality from Theorem <ref> to obtain the desired bound. To this end, we bound the $m$-th moment of $\xi_2\mathbbm{1}_{X\in \Omega_0}$. Similar to Eq. (<ref>), we have
𝔼ξ_21_X∈Ω_0_S_2(ℋ_X, 𝒴)^m=∫_E_X(C_XX+λId__X)^-1 / 2 ϕ_X(x)_ℋ_X^m 1_X∈Ω_0∫_𝒴y-F_λ(x)_𝒴^m p(x,  d y) d π(x).

Apply Eq. (<ref>) to the above inner integral, we obtain

\begin{equation} \label{eq:m_moment_2}
\begin{aligned}
\mathbb{E}\left\|\xi_{2}\mathbbm{1}_{X\in \Omega_0}\right\|_{S_2(\mathcal{H}_X, \mathcal{Y})}^{m} \leq  & \frac{1}{2} m !(2 R)^{m-2} 2 \sigma^{2} \int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{m}\mathbbm{1}_{X\in \Omega_0} \mathrm{~d} \pi(x) \\
&+2^{m-1} \int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{m}\left\|F_{*}(x)-F_{\lambda}(x)\right\|_{\mathcal{Y}}^{m}\mathbbm{1}_{X\in \Omega_0} \mathrm{~d} \pi(x).
\end{aligned}
\end{equation}

The first term in Eq. (<ref>) can be bounded using Lemma <ref> as below:

\begin{aligned}
\frac{1}{2} m !(2 R)^{m-2} 2 \sigma^{2}\int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{m} \mathbbm{1}_{x\in \Omega_0}\mathrm{~d} \pi(x) \leq \frac{1}{2} m !\left(\frac{2R A}{\lambda^{\alpha / 2}}\right)^{m-2} 2 \sigma^{2} \mathcal{N}(\lambda).
\end{aligned}

For the second term, note that if $\beta \geq \alpha$, by Lemma <ref> Eq. (<ref>),

\left\|\left(F_{*}-[F_{\lambda}]\right)\mathbbm{1}_{X\in \Omega_0}\right\|_{L_{\infty}} \leq \left\|F_{*}-[F_{\lambda}]\right\|_{L_{\infty}} \leq \left(\left\|F_{*}\right\|_{L_\infty} + A\|F_*\|_{\beta}\right) \lambda^{\frac{\beta - \alpha}{2}} \leq  2A\|F_*\|_{\beta}\lambda^{\frac{\beta - \alpha}{2}},

and if $\beta < \alpha$, by Lemma <ref> Eq. (<ref>),

\left\|\left(F_{*}-[F_{\lambda}]\right)\mathbbm{1}_{X\in \Omega_0}\right\|_{L_{\infty}} \leq \left\|F_{*}\mathbbm{1}_{X\in \Omega_0}\right\|_{L_{\infty}} + \left\|[F_{\lambda}]\right\|_{L_{\infty}} \leq t+ A\left\|F_{*}\right\|_{\beta} \lambda^{\frac{\be-\al}{2}}.

Therefore, for all $\beta \in (0,2]$,

\left\|\left(F_{*}-[F_{\lambda}]\right)\mathbbm{1}_{X\in \Omega_0}\right\|_{L_{\infty}} \leq t+ 2A\left\|F_{*}\right\|_{\beta} \lambda^{\frac{\be-\al}{2}} \leq  Q(t,\la).

We have, using Lemma <ref> again,

\begin{equation}\label{eq:term2}
\begin{aligned}
& 2^{m-1} \int_{E_X}\left\|h_{x}\right\|_{\mathcal{H}_X}^{m}\left\|F_{*}(x)-F_{\lambda}(x)\right\|_{\mathcal{Y}}^{m}\mathbbm{1}_{x\in \Omega_0} \mathrm{~d} \pi(x) \\
\leq & \frac{1}{2}\left(\frac{2A}{\lambda^{\alpha / 2}}\right)^{m}Q(t,\lambda)^{m-2} \int_{E_X}\left\|F_{*}(x) - F_{\lambda}(x)\right\|_{\mathcal{Y}}^{2} \mathbbm{1}_{x\in \Omega_0}\mathrm{~d} \pi(x) \\
\leq & \frac{1}{2}m!\left(\frac{2Q(t,\lambda)A}{\lambda^{\alpha / 2}}\right)^{m-2} \left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}\frac{2A^2}{\lambda^{\alpha}}. \\
\end{aligned}
\end{equation}

Finally, we get

\mathbb{E}\left\|\xi_{2}\right\|_{S_2(\mathcal{H}_X, \cY)}^{m} \leq \frac{1}{2} m !\left(\frac{2Q(t,\lambda)A}{\lambda^{\alpha / 2}}\right)^{m-2} 2\left(\sigma^{2} \mathcal{N}(\lambda)+\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2} \frac{A^{2}}{\lambda^{\alpha}}\right).

An application of Bernstein's inequality from Theorem <ref> with
L=2Q(t,\lambda)A\lambda^{-\alpha / 2}, \qquad \sigma^{2}=2\left(\sigma^{2} \mathcal{N}(\lambda)+\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}\lambda^{-\alpha}\right)

yields the bound.

§.§ Learning Rates

In this section, we establish the upper bound on the learning rate for Theorem <ref>. To this end, we first look at Theorem <ref>, with probability over $1 - 4e^{-\tau}-\tau_n$ with $\tau_n = 1-\left(1-\frac{C_q^q}{t^q}\right)^n$,

\begin{equation*}
\begin{aligned}
\left\|\left[\hat{C}_{\lambda} - C_{\lambda}\right]\right\|_{S_2\left([\mathcal{H}]_X^{\gamma},\mathcal{Y}\right)}^2 &\leq \frac{1152\tau^2}{n\lambda^{\gamma}}\left(\sigma^{2} \mathcal{N}(\lambda)+\frac{\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}}{\lambda^{\alpha}} + \frac{2Q(t,\lambda)^2A^2}{n\lambda^{\alpha}}\right) \\
&+\frac{18}{\lambda^{\gamma}}\left(\sigma^{2} \mathcal{N}(\lambda)+\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2} \frac{A^{2}}{\lambda^{\alpha}}\right) \frac{C_q^q}{t^{q}}.
\end{aligned}
\end{equation*}

We first notice that if $t > n^{1/q}$, the second term on the r.h.s is
\[\frac{18C_q^q}{n\lambda^{\gamma}}\left(\sigma^{2} \mathcal{N}(\lambda)+\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2} \frac{A^{2}}{\lambda^{\alpha}}\right).\]

Moreover, by Bernouilli's inequality, $\tau_n \leq \frac{C_q^qn}{t^q}$. As such, given any $\tau \geq 1$, if $t > n^{1/q}$, there is a $n'_0 \geq 1$ such that $\tau_n \leq e^{-\tau}$ for all $n \geq n'_0$. We therefore have with probability greater than $1 - 5e^{-\tau}$, for all $n \geq n_0'$,

\begin{equation}
\begin{aligned}
\left\|\left[\hat{C}_{\lambda} - C_{\lambda}\right]\right\|_{S_2\left([\mathcal{H}]_X^{\gamma},\mathcal{Y}\right)}^2\leq \frac{c_0\tau^2}{n\lambda^{\gamma}}\left(\sigma^{2} \mathcal{N}(\lambda)+\frac{\left\|F_{*}-\left[F_{\lambda}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}}{\lambda^{\alpha}} + \frac{2Q(t,\lambda)^2A^2}{n\lambda^{\alpha}}\right). \label{eq:var_q_l}
\end{aligned}
\end{equation}

where $c_0 = \max\{1152,18C_q^q\}$.

From now on, we denote $\lambda$ as $\lambda_n$ to indicate that $\lambda$ is a function of $n$ and we pick $n_1 \geq 1$ such that $\lambda_n \leq 1$ for all $n \geq n_1$. For $n \geq n_1$, we have,
Q(t,λ_n)^2    =    max{R^2, (t+ 2AF_*_β λ_n^-/2)^2}
≤    max{R^2,2t^2+8A^2B^2 λ_n^-(α-β)}
≤    max{R^2,8A^2B^2 λ_n^-(α-β)} + 2t^2

≤    C_0 (λ_n^-(α-β)_+ +t^2),

where $C_0 := \max\left\{R^2, 8A^2B^2, 2\right\}$. As a result, Eq. (<ref>) become

\begin{equation}
\begin{aligned}
\left\|\left[\hat{C}_{\lambda_n} - C_{\lambda_n}\right]\right\|_{S_2\left([\mathcal{H}]_X^{\gamma},\mathcal{Y}\right)}^2 &\leq \frac{c_0\tau^2}{n\lambda_n^{\gamma}}\left(\sigma^{2} \mathcal{N}(\lambda_n)+\frac{\left\|F_{*}-\left[F_{\lambda_n}\right]\right\|_{L_{2}(\pi; \mathcal{Y})}^{2}A^{2}}{\lambda_n^{\alpha}} + 2C_0A^2\frac{\lambda_n^{-(\alpha-\beta)_+}}{n\lambda_n^{\alpha}}\right)\\
& +2C_0A^2c_0\tau^2\frac{t^2}{n^2\lambda_n^{\alpha+\gamma}}. \label{eq:var_q_l1}
\end{aligned}
\end{equation}

Using Lemma <ref> and Lemma <ref> with $\gamma=0$, we can see that the first term on the r.h.s coincides with Eq. (<ref>) up to some constants. Hence, the analysis in Section <ref> carries on. In particular, the choice of $n_0 \geq 1$, such that $n \geq 8A^2 \tau g_{\lambda_n}\lambda_n^{-\alpha}$ for all $n \geq n_0$ remains the same as in Section <ref> (see Eq. (<ref>)). For $n \geq n_1$, using $\lambda_n \leq 1$ and $C_1 := D\sigma^2 + A^2B^2$,

\begin{aligned}
\left\|[\hat{F}_{\lambda_n} - F_{\lambda_n}]\right\|_{\gamma}^2 &=\left\|[\hat{C}_{\lambda_n}-C_{\lambda_n}]\right\|_{S_2([\mathcal{H}]_X^{\gamma}, \mathcal{Y})}^2 \leq \frac{c_0\tau^2}{n\lambda_n^{\gamma}}\left(C_1\lambda_n^{-\max\{p,\alpha-\beta\}} + 2C_0A^2\frac{\lambda_n^{-(\alpha-\beta)_+}}{n\lambda_n^{\alpha}}\right) +2C_0A^2c_0\tau^2\frac{t^2}{n^2\lambda_n^{\alpha+\gamma}} \\ &\leq
\frac{c_0\tau^2}{n\lambda_n^{\gamma+\max\{p,\alpha-\beta\}}}\left(C_1 + 2C_0A^2\frac{1}{n\lambda_n^{\alpha+(\alpha-\beta)_+-\max\{p,\alpha-\beta\}}}\right) + 2C_0A^2c_0\tau^2\frac{t^2}{n^2\lambda_n^{\alpha+\gamma}}
\end{aligned}

There is a constant $C_2 > 0$ such that for all $n \geq n_2$, for $n_2 := \max\{n'_0,n_0,n_1\}$,

\[\left\|[\hat{F}_{\lambda_n} - F_{\lambda_n}]\right\|_{\gamma}^2 \leq  \frac{c_0\tau^2}{n\lambda_n^{\gamma+\max\{p,\alpha-\beta\}}}\left(C_1 + 2C_0A^2C_2\right) + 2C_0A^2c_0\tau^2\frac{t^2}{n^2\lambda_n^{\alpha+\gamma}}.\]

Using the bias-variance splitting from Eq. (<ref>) and Lemma <ref>, let $C_3 := \max\{c_0\left(C_1 + 2A^2C_0C_2\right), 2C_0A^2c_0\}$, we have
[F̂_λ_n]-F_*_γ^2    ≤    2C_*_S_2([ℋ]_X^β, 𝒴)^2 λ_n^β-γ + 2C_3τ^2(1/nλ_n^γ+max{p,α-β}+t^2/n^2λ_n^α+γ)

≤    τ^2 λ_n^β-γ(2C_*_S_2([ℋ]_X^β, 𝒴)^2+2C_3 1/nλ_n^max{β+p,α})+ 2C_3τ^2t^2/n^2λ_n^α+γ,
where we used $\tau \geq 1$.

We now have two scenarios. We first assume that $\beta + p > \alpha$. If we choose $\lambda_n = n^{-1/(\beta + p)}$ there is some constant $J>0$ such that
\[\left\|[\hat{F}_{\lambda_n}]-F_*\right\|_{\gamma}^2 \leq  \tau^2 J \left(\lambda_n^{\beta - \gamma} + \frac{t^2}{n^2\lambda_n^{\alpha+\gamma}}\right)\]
for all $n \geq n_2$. In order for the second term to match the first term, we will need $\frac{t^2}{n^2\lambda_n^{\alpha}} \leq \lambda_n^{\beta}$ when $\lambda_n = n^{-\frac{1}{\beta+p}}$. This amounts to require that
\[t \leq n^{\frac{\beta+2p-\alpha}{2(\beta+p)}}.\]
Recall that we require $t > n^{1/q}$, combining with the above, we need
\[q > \frac{2(\beta+p)}{\beta +2p-\alpha }.\]

Secondly, we assume that $\beta +p \leq \alpha$. If we choose $\lambda_n = \left(n/\log^{\theta} n \right)^{-\frac{1}{\alpha}}$ with $\theta >1$, we obtain, for some constant $J >0$ that
\[\left\|[\hat{F}_{\lambda_n}]-F_*\right\|_{\gamma}^2 \leq  \tau^2 J \left(\lambda_n^{\beta - \gamma} + \frac{t^2}{n^2\lambda_n^{\alpha+\gamma}}\right)\]
for all $n \geq n_2$. In order for the second term to match the first term, we will need $\frac{t^2}{n^2\lambda_n^{\alpha}} \leq \lambda_n^{\beta}$ when $\lambda_n = \left(n/\log^{\theta} n \right)^{-\frac{1}{\alpha}}$. This amounts to require that
\[t \leq n \left(\frac{\log^{\theta} n}{n} \right)^{\frac{\alpha+\beta}{2\alpha}}.\]
Merging with the constraint $t > n^{1/q}$, we require
\[q \geq \frac{2\alpha}{\alpha -\beta }.\]

§ PROOF OF THEOREM <REF>

The proof of the lower bound is performed
by projecting the infinite-dimensional response variable $Y$ onto a one-dimensional subspace of $\mathcal{Y}$ and applying arguments from the real-valued learning scenario.

We start by noticing that for any $F \in L_2(\pi; \mathcal{Y})$ and $a \in \mathcal{Y}$,

\begin{equation} \label{eq:bound_scalar}
\begin{aligned}
\int_{E_X} \left(\langle F(x), a \rangle_{\mathcal{Y}} - \langle F_*(x), a \rangle_{\mathcal{Y}} \right)^2 d\pi(x) &\leq \int_{E_X} \|F(x) - F_{*}(x)\|_{\mathcal{Y}}^2 \|a\|^2_{\mathcal{Y}} d\pi(x) \\ &=  \|a\|^2_{\mathcal{Y}}\|F - F_{*}\|^2_{L_2(\pi; \mathcal{Y})}.
\end{aligned}
\end{equation}

Moreover, by Lemma <ref>, the inequality holds for general $\gamma$-norm (which implies the previous equation, setting $\gamma=0$),
⟨F(.), a⟩_𝒴-⟨F_*(.), a ⟩_𝒴_γ ≤a_𝒴F-F_*_γ.

Let $\gamma \geq 0$, for any $F \in [\mathcal{G}]^{\gamma}$ and $a \in \cY$, we have
\[\|\langle F(.), a\rangle_{\mathcal{Y}}\|_{\gamma} \leq \|a\|_{\mathcal{Y}} \|F\|_{\gamma}.\]

The case where $\gamma = 0$ is already proved in Eq. (<ref>). We now let $\gamma > 0$. Recall $\{d_j\}_{j\in J}$ and $\{\mu_i^{\gamma/2}[e_i]\}_{i \in I}$ are the orthonormal basis of $\mathcal{Y}$ and $[\mathcal{H}]_{X}^{\gamma}$, since $F \in [\mathcal{G}]^{\gamma}$, we can write $F$ as
\[F = \sum_{i\in I,j \in J} a_{ij} d_j \mu_i^{\gamma/2}[e_i].\]
Therefore, we have
\[\langle F(\cdot), a\rangle_{\mathcal{Y}} = \sum_{i\in I,j \in J} a_{ij}\langle d_j, a\rangle_{\mathcal{Y}}\mu_i^{\gamma/2}[e_i](\cdot).\]
$\langle F(\cdot), a \rangle_{\mathcal{Y}}$ is an element of $[\mathcal{H}]_X^{\gamma}$ as