We study theoretical properties of a broad class of regularized algorithms with vector-valued output. These spectral algorithms include kernel ridge regression, kernel principal component regression, various
implementations of gradient descent and many more.
Our contributions are twofold. First, we rigorously confirm
the so-called saturation effect for ridge regression with vector-valued output by deriving a novel lower bound on learning rates; this bound is shown to be suboptimal when the smoothness of the regression function exceeds a certain level.
Second, we present the upper bound for the finite sample risk
general vector-valued spectral algorithms, applicable to both well-specified and misspecified scenarios (where the true regression function lies outside of the hypothesis space) which
is minimax optimal in various regimes. All of our results explicitly allow the case of infinite-dimensional output variables, proving consistency of recent practical applications.

§ INTRODUCTION

We investigate a fundamental topic in modern machine learning—the behavior and efficiency
of learning algorithms for regression  in high-dimensional and potentially infinite-dimensional output spaces $\cY$. Given two random variables $X$ and $Y$, we seek to empirically minimize the squared expected risk

\begin{equation}
\label{eq:risk_intro}
\mathcal{E}(F):= \mathbb{E}\left[\|Y - F(X)\|^2_{\mathcal{Y}} \right]
\end{equation}

over functions $F$ in a reproducing kernel Hilbert space consisting of vector-valued functions
from a topological space $\cX$ to a Hilbert space $\mathcal{Y}$.
The study of this setting as an ill-posed statistical inverse problem is well established: see e.g. Smale and Zhou, 2007, Caponnetto and De Vito, 2007, Yao et al., 2007, Bauer et al., 2007, Blanchard and Mücke, 2018, Fischer and Steinwart, 2020. In this work,
we study the setting when $\mathcal{Y}$ is high- or infinite-dimensional, since it  has been less well covered by the literature,  yet has many applications in multitask regression [Caponnetto et al., 2008, Baldassarre et al., 2012] and infinite-dimensional learning problems, including the conditional mean embedding [Grünewälder et al., 2012, Grünewälder et al., 2012, Park and Muandet, 2020], structured prediction [Ciliberto et al., 2016, Ciliberto et al., 2020], causal inference [Singh et al., 2023], regression with instrumental and proximal variables [Singh et al., 2019, Mastouri et al., 2021], the estimation of linear operators and dynamical systems [Song et al., 2009, Mollenhauer and Koltai, 2020, Kostic et al., 2022, Mollenhauer et al., 2022, Kostic et al., 2023], and functional regression [Kadri et al., 2016]. Interestingly,
the aforementioned infinite-dimensional applications typically use the classical
ridge regression algorithm. Our goal is to motivate the use of alternative learning algorithms in these settings, while providing strong theoretical guarantees.

Classically, the ill-posed problem (<ref>) is solved via regularization strategies, which are often implemented in terms
of so-called spectral filter functions
in the context of inverse problems in Hilbert spaces [Engl et al., 2000]. When applied to the learning problem given by (<ref>), these filter functions correspond to learning algorithms including ridge regression, a variety of different implementations of gradient descent, principal component regression and many more (we refer the reader to Gerfo et al., 2008
and Baldassarre et al., 2012 for overviews of the real-valued and vector-valued output variable case, respectively). Algorithms based on spectral filter functions when $\cY = \mathbb{R}$ are studied extensively, see e.g. [Blanchard and Mücke, 2018, Lin et al., 2020]. To the best of our knowledge, the detailed behavior of this general class of algorithms has remained unknown when $\cY$ is a general Hilbert space, with the exception of a few results for special cases in the setting of ridge regression [Caponnetto and De Vito, 2007, Li et al., 2023].

Overview of our contributions.
In this manuscript, we aim to theoretically understand vector-valued spectral learning algorithms.
The contribution of our work is twofold: (i) we
rigorously confirm the saturation effect of ridge regression for general Hilbert spaces $\cY$ (see paragraph below) in the context of lower bounds on rates for the learning problem (<ref>)
and (ii) we cover a gap in the existing literature by  providing upper rates for general
spectral algorithms in high- and infinite-dimensional spaces.
Our results explicitly allow  the misspecified learning case in which the true regression function is not contained in the hypothesis space. We base our analysis on
the concept of vector-valued interpolation spaces introduced by [Li et al., 2022, Li et al., 2023]. The interpolation space norms measure the smoothness of the true regression function,
replacing typical source conditions found in the literature which only cover the well-specified case. To the best of our knowledge, these are the first bounds covering this general setting for vector-valued spectral algorithms.

Saturation effect of ridge regression.
The widely-used ridge regression algorithm is known to exhibit the so-called saturation effect:
it fails to exploit additional smoothness in the target function beyond a certain threshold.
This effect has been thoroughly investigated in the context of Tikhonov regularization in inverse problems <cit.>, but is generally reflected only in
upper rates in the learning literature, see e.g. [Lin et al., 2020, Blanchard and Mücke, 2018].
Interestingly, existing lower bounds
[Caponnetto and De Vito, 2007, Blanchard and Mücke, 2018, Li et al., 2023] are usually formulated in a more general setting and do not reflect this
saturation effect, leaving a gap between upper and lower rates.
We leverage the bias-variance decomposition paradigm to lower bound the learning risk of kernel ridge regression with vector-valued output,
in order to close this gap.

Learning rates of vector-valued spectral algorithms.
Motivated by the fact that the saturation effect is technically unavoidable with vector-valued ridge regression,
we proceed to study the generalization error of popular alternative learning algorithms. In particular, we provide upper rates
in the vector-valued setting
consistent with the known behavior of spectral algorithms in the real-valued learning
setting, based on their so-called qualification property
[Blanchard and Mücke, 2018, Lin et al., 2020].
In particular, we confirm that a saturation effect can
be bypassed in high and infinite dimensions by algorithms such as
principal component regression and gradient descent, allowing
for a better sample complexity for high-smoothness problems.
Furthermore, we study the misspecified setting and show that upper rates for spectral algorithms match the state-of-the-art upper rates for
misspecified vector-valued ridge regression recently
obtained by [Li et al., 2023]. Those rates are optimal for a wide variety of settings. Moreover, we argue that applications of vector-valued spectral algorithms are easy to implement by making use
of an extended representer theorem based on [Baldassarre et al., 2012], allowing for the
numerical evaluation based on empirical data—even in the infinite-dimensional case.

Related Work.
The saturation effect of regularization techniques in deterministic inverse problems is well-known. For example, [Neubauer, 1997, Mathé, 2004, Herdman et al., 2011] study the saturation effect for
Tikhonov regularization and general spectral algorithms. In the kernel statistical learning framework,
the general phenomenon of saturation is discussed by e.g. [Bauer et al., 2007, Gerfo et al., 2008]. Recent work by [Li et al., 2023] investigates saturation effect in the learning context by providing a lower bound on the learning rate. To the best of our knowledge, however, all studies in the statistical learning context focus on the case when $Y$ is real-valued.
General upper bounds of kernel ridge regression with real-valued or finite-dimensional $Y$ have been extensively studied in the literature (see e.g., [Caponnetto and De Vito, 2007, Steinwart et al., 2009, Caponnetto and Yao, 2010, Fischer and Steinwart, 2020]), where minimax optimal learning rates are derived. Recent work [Li et al., 2022, Li et al., 2023] studies the infinite-dimensional output space setting with Tikhonov regularization and obtains analogous minimax optimal learning rates. For kernel learning with spectral algorithms, existing work (see e.g., [Bauer et al., 2007, Blanchard and Mücke, 2018, Lin and Cevher, 2018, Lin et al., 2020, Zhang et al., 2023]) focuses on real-valued output space setting and obtains optimal upper learning rates depending on the qualification number of the spectral algorithms,

where only [Zhang et al., 2023] considers the misspecified learning scenario where the target regression function does not lie in the hypothesis space. However, general investigations of spectral algorithms for vector-valued output spaces are absent in the literature.

Structure of this paper.
This paper is structured as follows. In Section <ref>, we introduce mathematical preliminaries related to reproducing kernel Hilbert spaces, vector-valued regression as well as the concept of vector-valued interpolation spaces. Section <ref> contains a brief review the so-called saturation effect and a corresponding novel lower bound for vector-valued kernel ridge regression. In Section <ref>, we investigate general spectral learning algorithms in the context of vector-valued interpolations spaces
and provide our main result: upper learning rates for this setting.

§ BACKGROUND AND 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 $\cX$ is a more general topological space. However, some properties of kernels defined on $\cX$ such as the so-called $c_0$-universality [Carmeli et al., 2010] simplify the exposition when $\cX$ is a second countable locally compact Hausdorff space.] $\cX$ endowed with its Borel $\sigma$-field $\mathcal{F}_{\cX}$, 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 push-forward of $\mathbb{P}$ under $(X,Y)$ and $\pi$ and $\nu$ be the marginal distributions on $\cX$ and $\cY$, respectively; i.e., $X \sim \pi$ and $Y \sim \nu$. We use the Markov kernel $p: \cX \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 \cX$ and events $A \in \mathcal{F}_{\mathcal{Y}}$,
see e.g. Dudley, 2002. We introduce some notation related
to linear operators on Hilbert spaces and vector-valued integration;
formal definitions can be found in Appendix <ref>
for completeness, or we refer the reader to Weidmann, 1980, Diestel and Uhl, 1977. The spaces of Bochner square-integrable functions with respect to $\pi$ and taking values in
$\mathcal{Y}$ are written as $L_2(\cX,\mathcal{F}_{\cX},\pi; \mathcal{Y})$, abbreviated as $L_2(\pi; \mathcal{Y})$. We obtain the classical Lebesgue spaces as $L_2(\pi):= L_2(\pi; \R)$.
Throughout the paper, we write $[F]$ or
more explicitly $[F]_\pi$
for the $\pi$-equivalence class of (potentially pointwise
defined) measurable functions from $\cX$ to $\cY$,
which we naturally interpret as elements in $L_2(\pi; \mathcal{Y})$ whenever
they are square integrable.
Let $H$ be a separable real Hilbert space with inner product $\langle \cdot, \cdot \rangle_{H}$. We write $\mathcal{L}(H,H')$ as the Banach space of bounded linear operators from $H$ to another Hilbert space $H'$, equipped with the operator norm $\|\cdot\|_{H \rightarrow H'}$. When $H=H'$, we simply write $\mathcal{L}(H)$ instead. We write $S_2(H,H')$ as the Hilbert space of Hilbert-Schmidt operators from $H$ to $H'$ and $S_1(H,H')$ as the Banach space of trace class operators (see Appendix <ref> for a complete definition).
For two Hilbert spaces $H,H'$, we say that $H$ is (continuously) embedded in $H'$ and denote it as
$H \hookrightarrow H'$ if $H$ can be interpreted as a vector subspace of $H'$ and the inclusion operator $i: H \to H'$
performing the change of norms with $i x = x$ for $x \in H$ is continuous; and we say that $H$ is isometrically isomorphic to $H'$ and denote it as $H \simeq H'$ if there is a linear isomorphism between $H$ and $H'$ which is an isometry.

Tensor Product of Hilbert Spaces: Denote $H\otimes H'$  the tensor product of Hilbert spaces $H$, $H'$. 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 these two spaces, and treat them as being identical.

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)$, and we denote as $\Psi$ the isometric isomorphism between the two spaces. See Appendix <ref> for more details on tensor product spaces and the explicit definition of $\Psi$.

Scalar-valued Reproducing Kernel Hilbert Space (RKHS).
We let $k: \cX \times \cX \rightarrow \mathbb{R}$ be a symmetric and positive definite kernel function and $\cH$ be a vector space of functions from $\cX$ to $\mathbb{R}$, endowed with a Hilbert space structure via an inner product $\langle\cdot, \cdot\rangle_{\cH}$. We say that $k$ is a reproducing kernel of $\cH$ if and only if for all $ x \in \cX$ we have $k(\cdot,x) \in \cH$ and for all $x \in \cX$ and $f \in \cH$, we have $f(x)=\left\langle f, k(x,\cdot)\right\rangle_{\cH}$. A space $\cH$ which possesses a reproducing kernel is called a reproducing kernel Hilbert space (RKHS; see e.g. Berlinet and Thomas-Agnan, 2011). We denote the canonical feature map of $\cH$ as $\phi(x) = k(\cdot,x)$.

We require some technical assumptions on the previously defined RKHS and kernel, which we assume to be satisfied throughout the text:

$\cH$ is separable, this is satisfied
if $k$ is continuous, given that $\cX$ is separable;[This follows from <cit.>. Note that the Lemma requires separability of $\cX$, which is satisfied since we assume that $\cX$ is a second countable locally compact Hausdorff space.]

$k(\cdot,x)$ is measurable for $\pi$-almost all $x \in \cX$;

$k(x,x) \leq \kappa^2$ for $\pi$-almost all $x \in \cX$.

The above assumptions are not restrictive in practice, as well-known kernels such as the Gaussian, Laplace and Matérn kernels satisfy them on $\cX \subseteq \mathbb{R}^d$ [Sriperumbudur et al., 2011]. We now introduce some facts about the interplay between $\cH$ 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}: \cH \rightarrow L_{2}(\pi)$, mapping a function $f \in \cH$ 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(\cH, L_{2}(\pi)\right)}=\|k\|_{L_{2}(\pi)} \leq \kappa.$
The adjoint operator $S_{\pi}:=I_{\pi}^{*}: L_{2}(\pi) \rightarrow \cH$ is an integral operator with respect to the kernel $k$, i.e. for $f \in L_{2}(\pi)$ and $x \in \cX$ we have <cit.>

\left(S_{\pi} f\right)(x)=\int_{\cX} k\left(x, x^{\prime}\right) f\left(x^{\prime}\right) \mathrm{d} \pi\left(x^{\prime}\right).

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

L_{X}:=I_{\pi} S_{\pi}: L_{2}(\pi) \rightarrow L_{2}(\pi) \quad \text { and } \quad C_{X}:=S_{\pi} I_{\pi}: \cH \rightarrow \cH.

Vector-valued Reproducing Kernel Hilbert Space (vRKHS). Let $K: \cX \times \cX \rightarrow \mathcal{L}(\cY)$ be an operator valued positive-semidefinite (psd) kernel. Fix $K$, $x \in \cX$, and $h \in \cY$, then $\left(K_x h\right)(\cdot):=K(\cdot, x) h$
defines a function from $\cX$ to $\cY$. The completion of

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

with inner product on $\mathcal{G}_{\text {pre }}$ defined on the elementary elements as $\left\langle K_x h, K_{x^{\prime}} h^{\prime}\right\rangle_{\mathcal{G}}:=\left\langle h, K\left(x, x^{\prime}\right) h^{\prime}\right\rangle_{\cY}$, defines a vRKHS denoted as $\mathcal{G}$. For a more complete overview of the vector-valued reproducing kernel Hilbert space, we refer the reader to [Carmeli et al., 2006], [Carmeli et al., 2010] and <cit.>. In the following, we will denote $\mathcal{G}$ as the vRKHS induced by the kernel $K: \cX \times \cX \rightarrow \mathcal{L}(\mathcal{Y})$ with

\begin{equation} \label{eq:v_kernel}
K(x,x') := k(x,x')\operatorname{Id}_{\mathcal{Y}}, \quad x,x' \in \cX.
\end{equation}

We emphasize that this family of kernels is the de-facto standard for
high- and infinite-dimensional applications
[Grünewälder et al., 2012, Grünewälder et al., 2012, Park and Muandet, 2020, Ciliberto et al., 2016, Ciliberto et al., 2020, Singh et al., 2019, Mastouri et al., 2021, Singh et al., 2023, Mollenhauer and Koltai, 2020, Kostic et al., 2022, Mollenhauer et al., 2022, Kostic et al., 2023, Kadri et al., 2016]
due to the crucial representer theorem which gives a closed form
solution for the ridge regression problem based on the data.
We generalize this representer theorem to cover the general
spectral algorithm case in Proposition <ref>.

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')\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')T
\]

where $T: \mathcal{Y} \to \mathcal{Y}$
is any positive-semidefinite self-adjoint operator. The precise
characterization of the adjusted constants is given by <cit.>.

An important property of $\mathcal{G}$ is that
it is isometrically isomorphic to the space of Hilbert-Schmidt operators between $\cH$ and $\mathcal{Y}$ <cit.>. Similarly to the scalar case we can map every element in $\cG$ into its $\pi-$equivalence class in $L_2(\pi;\cY)$ and we use the shorthand notation $[F] = [F]_{\pi}$ (see Definition <ref> in Appendix <ref> for more details).

[vRKHS isomorphism]
For every function $F\in \mathcal{G}$ there exists a unique operator $C \in S_2(\cH, \mathcal{Y})$ such that $F(\cdot) = C\phi(\cdot) \in \mathcal{Y}$ with $\|C\|_{S_2(\cH, \mathcal{Y})} = \|F\|_{\mathcal{G}}$ and vice versa. Hence $\cG \simeq S_2(\cH, \mathcal{Y})$ and we denote the isometric isomorphism between $S_2(\cH, \mathcal{Y})$ and $\mathcal{G}$ as $\bar{\Psi}$. It follows that $\cG$ can be written as $\mathcal{G}= \left\{F: \cX \rightarrow \mathcal{Y} \mid F = C\phi(\cdot),\, C \in S_2(\cH, \mathcal{Y})\right\}$.

§.§ Vector-valued Regression

We briefly recall the basic setup of regularized least squares regression with Hilbert space-valued random variables. The squared expected risk for vector-valued regression is

\begin{equation}\label{eqn:exp_risk}
\mathcal{E}(F):= \mathbb{E}\left[\|Y - F(X)\|^2_{\mathcal{Y}} \right] = \int_{\cX \times \mathcal{Y}} \|y - F(x)\|^2_{\mathcal{Y}}p(x,dy)\pi(dx),
\end{equation}

for measurable functions $F: \cX \rightarrow \mathcal{Y}$. The analytical minimizer 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

\begin{equation*}
F_*(x):= \mathbb{E}[Y \mid X = x] = \int_{\mathcal{Y}} y \, p(x,dy), \quad x \in \cX.
\end{equation*}

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 implies $F_\star \in L_2(\pi; \cY)$. 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. We pick $\mathcal{G}$ as a hypothesis space of functions in which to estimate $F_*$. Note that by Theorem <ref>, minimizing the functional $\mathcal{E}$ on $\cG$ is equivalent to minimizing the following functional on $S_2(\cH, \cY)$,

\begin{equation}\label{eq:risk_G}
\bar{\mathcal{E}}(C):= \mathbb{E}\left[\|Y - C\phi(X)\|^2_{\mathcal{Y}} \right].
\end{equation}

It is shown in <cit.> that the optimality condition can be written as

\begin{equation} \label{eq:normal_eq}
C_{YX} = C_*C_{X}, \qquad C_* \in S_2(\cH, \cY),
\end{equation}

where $C_{YX} := \E[Y \otimes \phi(X)]$ is the cross-covariance operator.
As discussed in full detail by Mollenhauer et al., 2022,
the problem <ref> can be formulated
as a potentially ill-posed inverse problem on the space of Hilbert–Schmidt operators. As such, a regularization
is required; we introduce regularized solutions of this problem in Section <ref> through
the classical concept of spectral filter functions.

§.§ Vector-valued Interpolation Space and Source Condition

We now introduce the background required in order to  characterize the smoothness of the target function $F_*,$ both in the well-specified setting ($F_* \in \cG$) and in the misspecified setting ($F_* \notin \mathcal{G}$).  We review the results of
[Steinwart and Scovel, 2012] and [Fischer and Steinwart, 2020] in constructing scalar-valued interpolation spaces, and [Li et al., 2022] in defining vector-valued interpolation spaces.

Real-valued Interpolation Space: 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 \cH$, such that $\left([e_i]\right)_{i \in I}$
[We recall that the bracket $[\cdot]$ denotes the embedding that maps $f$ to its equivalence class $I_{\pi}(f) \in L_2(\pi)$.] 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 \cH$, 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_{X} = \sum_{i \in I} \mu_i \langle\cdot, \mu_i^{\frac{1}{2}}e_i \rangle_{\cH} \mu_i^{\frac{1}{2}}e_i
\end{equation}

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

\[[\cH]^{\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 inner product

\[\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_{[\cH]^{\alpha}} = \sum_{i \in I} a_i b_i,\]

for $\left(a_{i}\right)_{i\in I}, \left(b_{i}\right)_{i\in I} \in \ell_{2}(I)$. The $\alpha$-interpolation space defines a Hilbert space. Moreover, $\left(\mu_{i}^{\alpha / 2}\left[e_{i}\right]\right)_{i \in I}$ forms an ONB of $[\cH]^{\alpha}$ and consequently $[\cH]^{\alpha}$ is a separable Hilbert space. In the following, we use the abbreviation $\|\cdot\|_{\alpha}:=\|\cdot\|_{[\cH]^{\alpha}}$.

Vector-valued Interpolation Space: Introduced in [Li et al., 2022], vector-valued interpolation spaces generalize the notion of scalar-valued interpolation spaces to vRKHS with a kernel of the form (<ref>).

Let $k$ be a real-valued kernel with associated RKHS $\cH$ and let $[\cH]^{\alpha}$ be the real-valued interpolation space associated to $\cH$ with some $\alpha \geq 0$. The vector-valued interpolation space $[\mathcal{G}]^{\alpha}$ is defined as (refer to Remark <ref> for the definition of $\Psi$)

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

The space $[\mathcal{G}]^{\alpha}$ is a Hilbert space equipped with the inner product
$$\left\langle F, G \right\rangle_{\alpha} := \left\langle C, L\right\rangle_{S_2([\cH]^{\alpha}, \mathcal{Y})} \qquad (F,G \in [\mathcal{G}]^{\alpha}),$$
where $C = \Psi^{-1}(F),$ $L = \Psi^{-1}(G)$. For $\alpha = 0$, we retrieve $\|F\|_{0} = \|C\|_{S_2(L_2(\pi), \mathcal{Y})}.$

Note that we have $F_* \in L_2(\pi;\mathcal{Y})$ since $Y \in L_2(\P; \cY)$ by assumption. Furthermore, for $0< \beta <\alpha$, <cit.> imply the inclusions
\[[\mathcal{G}]^{\alpha} \hookrightarrow [\mathcal{G}]^{\beta}  \hookrightarrow [\mathcal{G}]^{0}\subseteq L_2(\pi;\mathcal{Y}).\]

Under assumptions <ref> to <ref> and with $\cX$ being a second-countable locally compact Hausdorff space, $[\mathcal{G}]^{0} = L_2(\pi;\mathcal{Y})$ if and only if $\cH$ is dense in the space of continuous functions vanishing at infinity, equipped with the uniform norm <cit.>.

We say that we are in the well-specified setting if $F_* \in [\cG]^{1}$. In this case, there exists $\bar{F} \in \cG$ such that $F_* = \bar{F}$ $\pi-$almost surely and $\|F_*\|_{1} = \|\bar{F}\|_{\cG}$, i.e. $F_*$ admits a representer in $\cG$ (see Remark <ref> in Appendix <ref>). When $F_* \in [\cG]^{\beta}$ for $\beta < 1$, $F_*$ may not admit such a representation and we are in the misspecified setting, as $[\cG]^1 \subseteq [\cG]^{\beta}$.

Definition <ref> and Remarks <ref> and <ref> motivate the use of following assumption on the smoothness of the target function:
there exists $\beta > 0$ 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([\cH]^{\beta}, \mathcal{Y})$. (<ref>) directly generalizes the notion of a so-called Hölder-type source condition in the learning literature [Caponnetto and De Vito, 2007, Fischer and Steinwart, 2020, Lin and Cevher, 2018, Lin et al., 2020] and allows to characterize the misspecified learning scenario.

§.§ Further Assumptions

In addition to (<ref>), we require standard assumptions to obtain the precise learning rate for kernel learning algorithms. We list them below. For constants $D_2 >0$ and $p \in (0,1]$ and for all $i \in I$,

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

For constants $D_1,D_2 >0$ and $p \in (0,1)$ and for all $i \in I$,

\begin{equation}\label{asst:evd_plus}
D_1i^{-\frac{i}{p}}\leq \mu_i \leq D_2i^{-1/p}.\tag{EVD+}
\end{equation}

(<ref>) and (<ref>) are standard assumptions on the eigenvalue decay of the integral operator: they describe the interplay between the marginal distribution $\pi$ and the RKHS $\cH$ (see more details in Caponnetto and De Vito, 2007, Fischer and Steinwart, 2020). (<ref>) is needed in order to establish lower bounds on the excess risk. Note that we have excluded the value $p=1$ from (<ref>); indeed, $p=1$ is incompatible with the assumption of a bounded kernel, a fact missed by previous works and of independent interest (see Appendix, Remark <ref>).

For $\alpha \in [p, 1]$, the inclusion $I^{\alpha, \infty}_{\pi}: [\cH]^{\alpha} \hookrightarrow L_{\infty}(\pi)$ is continuous, and $\exists A > 0$ such that

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

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 \cX$ <cit.>. Since we assume $k$ 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 not needed when we deal with the well-specified setting, but is crucial to bound the excess risk in the misspecified setting.

Finally, 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 \cX$ and all $q \geq 2$.
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.>.

§ SATURATION EFFECT OF KERNEL RIDGE REGRESSION

The most established way of learning $F_*$ is by kernel ridge regression (KRR), which can be formulated as the following optimization problem: given a dataset $D = \{(x_i, y_i)\}_{i=1}^n$ independently and identically sampled from the joint distribution of $X$ and $Y$,

\begin{equation}\label{eq:ridge_estim}
\hat{F}_{\lambda}:= \argmin_{F \in \mathcal{G}} \frac{1}{n}\sum_{i = 1}^n \left\|y_i - F(x_i)\right\|^2_{\mathcal{Y}} + \lambda \|F\|_{\mathcal{G}}^2, %\label{eqn:vkrr_func}
\end{equation}

where $\lambda > 0$ is the regularization parameter. The generalization error of vector-valued KRR is expressed as $\hat{F}_{\lambda} - F_*$, and controlled in different norms: see [Li et al., 2023] for
an extensive study. We recall here a simplified
special case of the key results obtained in this work. In the next Theorem, $\lesssim, \gtrsim$ are inequality up to positive multiplicative constants that are independent of $n$.

[Upper and lower bounds for KRR in the well-specified regime]
Let $\hat{F}_{\lambda}$ be the KRR estimator from (<ref>).
Furthermore, let the conditions (<ref>), (<ref>) and (<ref>) be satisfied for some $0 < p \leq 1$ and $\beta \geq 1$. Then, with high probability
we have

\begin{equation*}
\left\|[\hat{F}_{\lambda_n}] - F_*\right\|^2_{L_2(\pi)} \lesssim n^{-\frac{\min\{\beta,2\}}{\min\{\beta,2\} + p}}
\quad
\text{for a choice } \lambda_n = \Theta \left(n^{-\frac{1}{\beta + p}}\right),
\end{equation*}

and furthermore for all learning methods
(i.e., measurable maps) of the form
$D \to \hat{F}_D$,
\[\|[\hat{F}_D] - F_*\|^2_{L_2(\pi)} \gtrsim n^{-\frac{\beta}{\beta+p}}.\]

Theorem <ref> shows the minimax optimal learning rate for vector-valued KRR for $\beta \in [1,2]$. However, when $\beta > 2$, the obtained upper bound saturates at $n^{-\frac{2}{2+p}}$, creating a gap with the lower bound. This phenomenon is referred to as the saturation effect of Tikhonov regularization, and has been well investigated in deterministic inverse problems [Neubauer, 1997].
In the case where $\cY$ is real-valued, [Li et al., 2023] prove that the saturation effect cannot be avoided with Tikhonov regularization. Below, we give a similar but generalized bound on lower rates for the case
that $\cY$ is a Hilbert space.
For this result only, we assume that $\cX$ is a compact subset of $\mathbb{R}^d$. We give the proof in Appendix <ref>.

[Saturation of KRR]

Let $\cX$ be a compact subset of $\mathbb{R}^d$.
Let $\lambda = \lambda(n)$ be an arbitrary choice of regularization parameter satisfying $\lambda(n) \to 0$ as $n \to +\infty$ and let $\hat{F}_{\lambda}$ be the KRR estimator from (<ref>). We assume that the noise is non-zero and bounded below, i.e. there exists $\sigma>0$, such that

\int_{\mathcal{Y}}\|y- F_{*}(x)\|_{\mathcal{Y}}^2 p(x,dy) \geq \sigma^2,

is satisfied for $\pi$-almost all $x \in \cX$. We assume in addition and for this result only that $k$ is Hölder continuous (see Definition <ref> in the appendix), i.e., $k \in C^{\theta}(\cX \times \cX)$ for $\theta \in (0,1]$. Suppose that Assumptions (<ref>) and (<ref>) hold with $p \in (0,1)$ and $\beta \geq 2$. For $\tau \geq 0$, for sufficiently large $n>0$, where the hidden index bound depends on $\tau$, with probability greater than $1-e^{-\tau}$, there exists some constant $c_{\tau}>0$ such that

\begin{equation*}
\mathbb{E}\left[\left\|[\hat{F}_{\lambda}]-F_{\ast}\right\|^2_{L_2(\pi; \cY)} \Big\mid x_1, \ldots, x_n\right] \geq c_{\tau} n^{-\frac{2}{2+p}}.
\end{equation*}

The assumption that $k$ is Hölder continuous is crucial in lower bounding the variance with a covering number argument. Kernels satisfying this assumption include Gaussian kernels, Laplace kernels and Matérn kernels. Theorem <ref> clearly demonstrates that the learning rate from vector-valued KRR cannot reach the information theoretic lower rate.

As discussed above, [Li et al., 2023] propose a similar lower bound in the real-valued case, and we now highlight two fundamental differences with [Li et al., 2023] in the proof. First, while both works adopt the same bias-variance decomposition, we need to lower bound the bias and the variance term with infinite-dimensional output in our setting. Second, we adopt a different and simpler approach in proving the lower bound, since there are a number of issues with the  proof of [Li et al., 2023], both in the treatment of the bias and of the variance. For a detailed comparison with the earlier work, and an explanation of the differences in our approach, please refer to Remark <ref> in the Appendix.

§ CONSISTENCY AND OPTIMAL RATES FOR GENERAL SPECTRAL ALGORITHMS

Regularized population solution: Our goal is to regularize
(<ref>) in such a way that we get a unique and well-defined solution that provides a good approximation to $F_*$.
We first recall the concept of a filter function
(i.e., a function on an interval which is applied on self-adjoint operators to each individual eigenvalue via
the spectral calculus, see Engl et al., 2000), that will allow to define a regularization strategy.
One may think of the following definition
as a class of functions approximating
the inversion map $x \mapsto 1/x$ while still
being defined for $x=0$ in a reasonable way.
We use the definition given by [Lin et al., 2020],
but equivalent definitions can be found throughout
the literature.

Let $\Lambda\subseteq \mathbb{R}^{+}$. A family of functions $g_{\lambda}: [0,\infty)\to [0,\infty)$ indexed by $\lambda\in \Lambda$ is called a filter with qualification $\rho\geq 0$ if it satisfies the following two conditions:

* There exists a positive constant $E$ such that, for all $\lambda\in \Lambda$

\begin{equation}
\label{eq:filter_fn_axiom1}
\sup_{\alpha\in[0,1]}\sup_{x\in \left[0,\kappa^2\right]}\lambda^{1-\alpha}x^{\alpha}g_{\lambda}(x)\leq E
\end{equation}

* There exists a positive constant $\omega_{\rho}<\infty$ such that

\begin{equation}
\label{eq:qualification_def}
\sup_{\alpha\in[0,\rho]}\sup_{\lambda\in\Lambda}\sup_{x\in \left[0,\kappa^2\right]}|r_{\lambda}(x)|x^{\alpha}\lambda^{-\alpha}\leq \omega_{\rho},
\end{equation}

with $r_{\lambda}(x) := 1 - g_{\lambda}(x)x$.

Below, we give some standard examples which are discussed by e.g.[Gerfo et al., 2008, Blanchard and Mücke, 2018] in the context of kernel regression with scalar output variables,
and in [Baldassarre et al., 2012] for the
vector-valued case. A variety of
additional algorithms can be expressed in terms of a filter

1. Ridge regression. From the Tikhonov filter function $g_{\lambda}(x) = (x+\lambda)^{-1}$, we obtain the known ridge regression algorithm. In this case, we have
$E = \rho = \omega_\rho = 1$.

2. Gradient Descent.
From the Landweber iteration filter function
given by

\begin{equation*}
g_k(x) := \tau \sum_{i=0}^{k-1}
(1-\tau x)^i
\text{ for } k := 1/\lambda, k \in \N
\end{equation*}

we obtain the gradient descent scheme with constant step size $\tau > 0$, which corresponds to the population gradient iteration given by
$F_{k+1} := F_{k} - \tau \nabla \mathcal{E}(F_k)$ for $k \in \N$.
In this case, we have $E = 1$ and
arbitrary qualification with
$\omega_\rho = 1$
whenever $0 < \rho \leq 1$ and
$\omega_\rho = \rho^\rho$ otherwise.
Gradient schemes with more complex update rules
can be expressed in terms of filter functions as well
[Mücke et al., 2019, Lin and Cevher, 2018, Lin et al., 2020].

3. Kernel principal component regression.
The truncation filter function
$g_\lambda(x) = x^{-1} \mathds{1}[x \geq \lambda]$ yields kernel principal component regression , corresponding to
a hard thresholding of eigenvalues at a
truncation level $\lambda$.
In this case we have
$E = \omega_\rho = 1$ for arbitrary qualification $\rho$.

Population solution:
Given a filter function $g_{\lambda}$, we call $g_{\lambda}(C_{X})$[$g_{\lambda}(C_{X})$ is defined with the rules of spectral calculus, see Definition <ref> in the Appendix.] the regularized inverse of $C_{X}$. We may think of the regularized inverse as approximating the pseudoinverse
of $C_X$ (see e.g. [Engl et al., 2000]) when $\lambda \to 0$. We define the regularized population solution to (<ref>) as

\begin{equation}
\label{eq:pop_estim}
C_{\lambda} := C_{YX}g_{\lambda}(C_{X}) \in S_2(\cH, \cY), \qquad F_{\lambda}(\cdot) := C_{\lambda}\phi(\cdot) \in \cG.
\end{equation}

The solution arising from standard regularization strategies leads to well-known statistical methodologies.
We refer to [Engl et al., 2000] for the background on filter functions in classical regularization theory.

Empirical solution: Given the dataset $D = \{(x_i, y_i)\}_{i=1}^n$, the empirical analogue of (<ref>) is

\begin{equation}
\label{eq:emp_estim}
\hat{C}_{\lambda} := \hat{C}_{YX}g_{\lambda}(\hat{C}_{X}) , \qquad \hat{F}_{\lambda}(\cdot) := \hat{C}_{\lambda}\phi(\cdot) \in \cG,
\end{equation}

where $\hat{C}_{YX}$, $\hat{C}_{X}$ are empirical covariance operators define as

\hat{C}_{X} := \frac{1}{n} \sum_{i=1}^n \phi(x_i) \otimes \phi(x_i) \qquad \hat{C}_{YX} := \frac{1}{n} \sum_{i=1}^n y_i \otimes \phi(x_i).

Note that  (<ref>) is the regularized solution of the empirical inverse problem

\hat{C}_{YX} = \hat{C}\hat{C}_{X}, \qquad \hat{C} \in S_2(\cH, \cY),

which arises as the optimality condition for minimizers on $\cG$ of the empirical analogue of (<ref>), given by
\mathcal{E}_n(F):= \frac{1}{n}\sum_{i=1}^{n}\|y_i - F(x_i)\|_{\mathcal{Y}}^2%\label{eqn:exp_risk_empirical}
$; see Proposition <ref> in the Appendix for a proof.
For the vector-valued kernel given in (<ref>), it is well-known that
$\hat{F}_{\lambda}$ can be computed in closed-form for the ridge regression estimator—even in infinite dimensions [Song et al., 2009].
For general filter functions, an extended representer theorem
is given by [Baldassarre et al., 2012] in the context
of finite-dimensional multitask learning: this approach works in infinite dimensions as well. We give
the closed form solution based on [Baldassarre et al., 2012] below
(we include the proof in Appendix <ref>).

Let $(\mathbf{K})_{ij} = k(x_i,x_j)$, $1 \leq i,j \leq n$ denote the Gram matrix associated to the scalar-valued kernel $k$. We have

\begin{equation} \label{eq:formula_dual}
\hat{F}_{\lambda}(x) = \sum_{i=1}^{n} y_i\alpha_i(x), \qquad \alpha(x) = \frac{1}{n}g_{\lambda}\left(\frac{\mathbf{K}}{n}\right)\mathbf{k}_x \in \mathbb{R}^n, \qquad (\mathbf{k}_x)_i = k(x,x_i), \quad 1 \leq i \leq n.
\end{equation}

[Conditional integration]
Consider now a random variable $Z$ taking values in a topological space $\cZ$ on which we define a second RKHS $\cH' \subseteq \R^{\cZ}$ with kernel $\ell: \cZ \times \cZ \to \R$ and canonical feature map $\psi: \cZ \to \cH', z \mapsto \ell(z,\cdot)$. The conditional mean embedding [Song et al., 2009, Grünewälder et al., 2012] is defined as

F_{*}(x) := \E[\psi(Z) \mid X=x], \qquad x \in \cX.

We immediately see the link with vector-valued regression with $Y = \psi(Z)$ and $\cY = \cH'$. The conditional mean embedding allows us to compute the conditional expectation of any element of $\cH'$. Indeed, using the reproducing property, for $f \in \cH'$, we have for all $x \in \cX$,

\E[f(Z) \mid X=x] = \langle f, \E[\psi(Z) \mid X=x] \rangle_{\cH'}.

Given a dataset $\{(x_i, z_i)\}_{i=1}^n$[Note that this induces a dataset $D = \{(x_i, \psi(z_i))\}_{i=1}^n$ where we identify $y_i = \psi(z_i)$.] and an estimate of the conditional mean embedding $F_*$ with a spectral algorithm $\hat{F}_{\lambda}$ as in Eq. (<ref>), and substituting the formula in Eq. (<ref>), we obtain
\E[f(Z) \mid X=x] \approx \langle f, \hat{F}_{\lambda}(x) \rangle_{\cH'} = \sum_{i=1}^n \langle f, \psi(z_i)\rangle_{\cH'}\alpha_i(x) = \mathbf{f}_z^{\top}\alpha(x),
where $(\mathbf{f}_z)_i = f(z_i)$,  $1 \leq i \leq n.$

Learning rates: We now give our main result, the learning rates for the difference between $[\hat{F}_{\lambda}]$ and $F_*$ in the interpolation norm, where $F_{\lambda}$ and $\hat{F}_{\lambda}$ are
given by (<ref>) and (<ref>)
based on a general spectral filter satisfying Definition <ref>. The proof is deferred to Section <ref> in the Appendix.

[Upper learning rates]

Let $\hat{F}_{\lambda}$ be an estimator based on a general spectral filter with qualification $\rho \geq 0$.
Furthermore, let the conditions (<ref>), (<ref>),  (<ref>) be satisfied with $0 < p \leq \alpha \leq 1$. With $0 \leq \gamma \leq 1$, if (<ref>) is satisfied with $\gamma < \beta \leq 2\rho$, we have

* in the case $\beta + p \leq \alpha$, let $\lambda_n = \Theta \left(\left(n/\log^{\theta}(n)\right)^{-\frac{1}{\alpha}}\right)$ for some $\theta > 1$, for all $\tau > \log(6)$ 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-6e^{-\tau}$.

* in the case $\beta + p > \alpha$, let $\lambda_n = \Theta \left(n^{-\frac{1}{\beta + p}}\right)$, for all $\tau > \log(6)$ 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-6e^{-\tau}$.

Theorem <ref> provides the upper rate for vector-valued spectral algorithms. In particular, in combination with the lower bound in Theorem <ref>, we see that vector-valued
spectral algorithms with qualification $\rho$ achieve an optimal learning rate when the smoothness $\beta$ of the regression function is in the range $(\alpha-p,2\rho]$. For algorithms with infinite $\rho$ such as gradient descent and principal component regression, we confirm that they can exploit smoothness of the target function just as in the real-valued setting [Bauer et al., 2007, Blanchard and Mücke, 2018, Li et al., 2022], while not suffering from saturation. For Tikhonov regularization, where $\rho=1$, the rates recover the state-of-the-art results from [Li et al., 2023]. Finally, we point out that obtaining minimax optimal learning rates for $\beta < \alpha -p$ still remains challenging even in the real-valued output scenario. Note however that for a large variety of RKHS, $\alpha$ is arbitrarily close to $p$ and we obtain optimal rates for the whole range $(0,2\rho]$: we refer to [Li et al., 2023, Zhang et al., 2023] for a detailed discussion.

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

[Baldassarre et al., 2012]
Luca Baldassarre, Lorenzo Rosasco, Annalisa Barla, and Alessandro Verri.
Multi-output learning via spectral filtering.
Machine Learning, 870 (3):0 259–301, 2012.

[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 Statistics.
Springer, 2011.

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

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

[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, 2007b.

[Caponnetto and Yao, 2010]
Andrea Caponnetto and Yuan Yao.
Cross-validation based adaptation for regularization operators in learning theory.
Analysis and Applications, 80 (02):0 161–183, 2010.

[Caponnetto et al., 2008]
Andrea Caponnetto, Charles A. Micchelli, Massimiliano Pontil, and Yiming Ying.
Universal multi-task kernels.
Journal of Machine Learning Research, 9:0 1615–1646, 2008.
ISSN 1532-4435.

[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, 2006.

[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, 2010.

[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, 2006.

[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.

[Engl et al., 2000]
Heinz Werner Engl, Martin Hanke, and A. Neubauer.
Regularization of Inverse Problems.
Kluwer, 2000.

[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, 2020.

[Fujii et al., 1993]
Jun Ichi Fujii, Masatoshi Fujii, Takayuki Furuta, and Ritsuo Nakamoto.
Norm inequalities equivalent to heinz inequality.
Proceedings of the American Mathematical Society, 1180 (3):0 827–830, 1993.

[Gerfo et al., 2008]
L Lo Gerfo, Lorenzo Rosasco, Francesca Odone, E De Vito, and Alessandro Verri.
Spectral algorithms for supervised learning.
Neural Computation, 200 (7):0 1873–1897, 2008a.

[Gerfo et al., 2008]
Lorenzo Lo Gerfo, Lorenzo Rosasco, Francesca Odone, Ernesto De Vito, and Alessandro Verri.
Spectral algorithms for supervised learning.
Neural Compututation, 20:0 1873–1897, 2008b.

[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, 2012a.

[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.

[Herdman et al., 2011]
Terry Herdman, Ruben D Spies, and Karina G Temperini.
Global saturation of regularization methods for inverse ill-posed problems.
Journal of optimization theory and applications, 1480 (1):0 164–196, 2011.

[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.

[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 eigenvalues.
arXiv preprint arXiv:2302.02004, 2023.

[Li et al., 2023]
Yicheng Li, Haobo Zhang, and Qian Lin.
On the saturation effect of kernel ridge regression.
In The Eleventh International Conference on Learning Representations, 2023a.

[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.

[Li et al., 2023]
Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton.
Towards optimal Sobolev norm rates for the vector-valued regularized least-squares algorithm.
arXiv preprint arXiv:2312.07186, 2023b.

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

[Lin and Cevher, 2020]
Junhong Lin and Volkan Cevher.
Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms.
Journal of Machine Learning Research, 210 (147):0 1–63, 2020.

[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, 2020a.

[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, 2020b.

[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 Mearning, pages 7512–7523. PMLR, 2021.

[Mathé, 2004]
Peter Mathé.
Saturation of regularization methods for linear ill-posed problems in hilbert spaces.
SIAM journal on numerical analysis, 420 (3):0 968–973, 2004.

[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.

[Mücke et al., 2019]
Nicole Mücke, Gergely Neu, and Lorenzo Rosasco.
Beating SGD saturation with tail-averaging and minibatching.
In Advances in Neural Information Processing Systems, volume 32, 2019.

[Neubauer, 1997]
Andreas Neubauer.
On converse and saturation results for Tikhonov regularization of linear ill-posed problems.
SIAM Journal On Numerical Analysis, 340 (2):0 517–527, 1997.

[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 approximations.
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 measures.
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 R Hush, Clint Scovel, et al.
Optimal rates for regularized least squares regression.
In COLT, pages 79–93, 2009.

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

[Yao et al., 2007]
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto.
On early stopping in gradient descent learning.
Constructive Approximation, 260 (2):0 289–315, 2007.

[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, 2023a.

[Zhang et al., 2023]
Haobo Zhang, Yicheng Li, Weihao Lu, and Qian Lin.
On the optimality of misspecified spectral algorithms.
arXiv preprint arXiv:2303.14942, 2023b.

§ APPENDICES

The appendix is organized as follows. In Section <ref>, we give additional mathematical background and notations. In Section <ref>, we give the proof of Theorem <ref> and provide a technical comparison of our proof with [Li et al., 2023]. In Section <ref>, we prove Theorem <ref>. Finally, in Section <ref>, we provide auxiliary results used in the main proofs.

§ ADDITIONAL BACKGROUND

§.§ Hilbert spaces and linear operators

Let $H$ be a separable Hilbert space and $\pi$ a probability measure on $\cX$. For $1 \leq q \leq \infty$, $L_q(\cX,\mathcal{F}_{\cX},\pi; H)$, abbreviated $L_q(\pi; H)$, is the space of strongly $\mathcal{F}_{\cX}-\mathcal{F}_H$ measurable and Bochner $q$-integrable functions from $\cX$ to $H$, with the norms

\[
\| f \|_{L_q(\pi;H)}^q
= \int_{\cX} \|f  \|_H^q \, \mathrm{d}\pi, \quad 1\leq q<\infty, \qquad \| f \|_{L_{\infty}(\pi;H)} = \inf\left\{C \geq 0: \pi\{\|f\|_{H}> C\}=0\right\}.
\]

Let $H,H'$ be separable Hilbert spaces. For $1 \leq q \leq \infty$, $S_p(H,H')$, abbreviated $S_p(H)$ if $H=H'$, is the Banach space of all compact operators $C$ from $H$ to $H'$ such that $\|C\|_{S_p(H,H')} := \left\|\left(\sigma_i(C)\right)_{i\in I}\right\|_{\ell_p}$ is finite. Here $\|\left(\sigma_i(C)\right)_{i\in I}\|_{\ell_p}$ is the $\ell_p-$sequence space norm of the sequence of the strictly positive singular values of $C$ indexed by the at most countable set $I$. For $p = 2$, we retrieve the space of Hilbert-Schmidt operators, for $p = 1$ we retrieve the space of Trace Class operators, and for $p=+\infty$, $\|\cdot\|_{S_\infty(H,H')}$ corresponds to the operator norm $\|\cdot\|_{H \to H'}$.

Let $H,H'$ be Hilbert spaces. 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. 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'$.

[Isometric Isomorphism between $L_2(\pi; \cY)$ and $S_2(L_2(\pi), \cY)$, Theorem 12.6.1 [Aubin, 2000]]  Let $H$ be a separable Hilbert space. The Bochner space $L_2(\pi;H)$ is isometrically isomorphic to $S_2(L_2(\pi), \cY)$ and the isometric isomorphism is realized by the map $\Psi:S_2(L_2(\pi), \cY) \to L_2(\pi;H)$ acting on elementary tensors as $\Psi(f \otimes y)  = (\omega \to f(\omega)y).$

§.§ RKHS embbedings into L2 and Well-specifiedness

Recall that $I_{\pi}: \cH \to L_2(\pi)$ is the embedding that maps every function in $\cH$ into its $\pi$-equivalence class in $L_2(\pi)$ and that we used the shorthand notation $[f] = I_{\pi}(f)$ for all $f \in \cH$. We define similarly $\mathcal{I}_{\pi}: \cG \to L_2(\pi; \cY)$ as the embedding that maps every function in $\cG$ into its $\pi$-equivalence class in $L_2(\pi; \cY)$.

Let $\mathcal{I}_{\pi}:= I_{\cY} \otimes I_{\pi}$ be the tensor product of the operator $\operatorname{Id}_{\mathcal{Y}}$ with the operator $I_{\pi}$ (see <cit.> for the definition of tensor product of operators). $\mathcal{I}_{\pi}$ maps every function in $\cG$ into its $\pi$-equivalence class in $L_2(\pi; \cY)$. We then use the shorthand notation $[F] = \mathcal{I}_{\pi}(F)$ for all $F \in \cG$.

Let $\{d_j\}_{j\in J}$ be an orthonormal basis of $\cY$ and recall that $\{\sqrt{\mu_i} [e_i]\}_{i \in I}$ forms an orthonormal basis of $[\cH]^1$. Let $F \in [\cG]^{1}$. Then $F$ can be represented as the element $C := \sum_{i \in I,j \in J} a_{ij} d_j \otimes \sqrt{\mu_i}[e_i]$ in $S_2([\cH]^1,\cY)$ by definition of $[\cG]^{1}$ with $\|C\|_{1}^2 = \sum_{i,j} a_{ij}^2$. Hence defining $\bar{F} := \sum_{i \in I,j \in J} a_{ij} d_j \otimes \sqrt{\mu_i}e_i$ we have $C = \bar{C}$ $\pi-$a.e. and

\begin{equation*}
\|\bar{C}\|_{\cG}^2 = \sum_{i \in I,j \in J} a_{i,j}^2 = \|C\|_{1}^2 < +\infty.
\end{equation*}

Taking the elements identifying $\bar{C}$ in $\cG$ gives a representer $\bar{F}$ of $F$ in $\cG$.

§.§ Additional Notations

In the following, we fix $\{d_j\}_{j\in J}$ an orthonormal basis of $\cY$, where $J$ is at most countable. Recall that $\left\{\mu_i^{1/2}e_i\right\}_{i\in I}$ is an ONB of $\left(\operatorname{ker} I_{\pi}\right)^{\perp}$ in $\cH$, and $\left\{[e_i]\right\}_{i \in I}$ is an ONB of $\overline{\text{ran}~I_{\pi}}$ in $L_2(\pi)$. Let $\{\tilde{e}_i\}_{i \in I'}$ be an ONB of $\operatorname{ker} I_{\pi}$ (with $I\cap I' = \emptyset$), then  $\left\{\mu_i^{1/2}e_i\right\}_{i\in I} \cup \{\tilde{e}_i\}_{i \in I'}$ forms an ONB of $\cH$, and $\left\{d_j \otimes \mu_i^{1/2}e_i\right\}_{i\in I, j \in J} \cup \{d_j \otimes \tilde{e}_i\}_{i \in I', j\in J}$ forms an ONB of $\cY \otimes \cH \simeq \cG$.

For any Hilbert space $H$, linear operator $T: H \to H$ and scalar $\lambda >0$, we define $T_{\lambda} := T + \lambda I_{H}$.

§ SATURATION EFFECT WITH TIKHONOV REGULARIZATION

In the following proofs a quantity $h_n \geq 0$ depending on $n \geq 1$, but independent of $\tau$ the confidence level, is equal to $o(1)$ if $h_n \to 0$ when $n \to +\infty$.

We will make extensive use of the following notation in the subsequent analysis.

Denoted by  $\langle \cdot, \cdot \rangle_{2,n}$, the empirical $L_2(\pi)-$norm associated to points $\{x_i\}_{i=1}^n$ independently and identically sampled from the distribution of $X$, is defined as, for any $f,g\in\cH$,

\begin{align*}
\langle f,g\rangle_{2,n} := \left\langle \hat{C}_{X},f\otimes g\right\rangle_{S_2(\cH)}
= \left\langle \hat{C}_{X}f,g\right\rangle_{\cH}= \left\langle \hat{C}_{X}^{\frac{1}{2}}f,\hat{C}_{X}^{\frac{1}{2}}g\right\rangle_{\cH} = \frac{1}{n} \sum_{i=1}^n f(x_i)g(x_i).
\end{align*}

This induces an inner product on $\cH$, with associated norm,

\|f\|_{2,n}^2 = \langle f,f\rangle_{2,n} = \frac{1}{n} \sum_{i=1}^n f(x_i)^2.

Fix $x\in \cX$. The regularized canonical feature map is defined as

\begin{equation*}
f_x(\cdot) = C_{X,\lambda}^{-1}k(x,\cdot) : \cX \to \cH.
\end{equation*}

Recall from Eq. (<ref>) that the ridge estimator $\hat{F}_{\lambda}$ defined in Eq. (<ref>) can be expressed as

\begin{equation*}
\hat{C}_{\lambda} = \hat{C}_{YX}g_{\lambda}(\hat{C}_{X}) , \qquad \hat{F}_{\lambda}(\cdot) = \hat{C}_{\lambda}\phi(\cdot) \in \cG,
\end{equation*}

where in Theorem <ref> we focus on Tikhonov regularization where $g_{\lambda}(x) = (x + \lambda)^{-1}$. In that setting we have

\begin{equation} \label{eq:r_l_tikhonov}
r_{\lambda}\left(x\right) := 1 - \frac{x}{x+\lambda} = -\frac{\lambda}{x+\lambda}.
\end{equation}

Since $\beta \geq 2$, $F_* \in [\cG]^{\beta} \subseteq [\cG]^{1}$, therefore $F_*$ has a representer $\bar{F}$ in $\cG$ such that $F_* = \bar{F}$ $\pi$-a.e., and by Theorem <ref>, $\bar{F}(\cdot) = \bar{C}\phi(\cdot)$, with $\bar{C} \in S_2(\cH, \cY)$. Define the errors $ \epsilon_i:= y_i - \bar{C}\phi(x_i)$, $i=1,\ldots,n$, that are i.i.d samples with the same distribution as $\epsilon:= Y - \bar{C}\phi(X)$. By assumption $\E\left[\|\epsilon\|_{\mathcal{Y}}^2 \mid X\right]  \geq \sigma^2$ and by definition $\E\left[\epsilon \mid X\right] = 0$. By Eq. (<ref>), we have

r_{\lambda}\left(\hat{C}_{X}\right) := I - \hat{C}_{X}\hat{C}_{X, \lambda}^{-1} = -\lambda\hat C_{X}.

The following bias-variance decomposition is the essence of the proof. In the following derivation we abbreviate $S_2(L_2(\pi),\mathcal{Y})$ to $S_2$ $L_,2(\pi; \cY)$ to $L_2$ and $x_{1}, \ldots, x_n$ to $\underline{x}_n$ to save space.

\begin{align*}
\mathbb{E}\left[\left\|[\hat{F}_{\lambda}]-F_{\ast}\right\|^2_{L_2} \mid  \underline{x}_n \right] &=
\mathbb{E}\left[\left\|\left[\hat{C}_{YX}\hat{C}_{X, \lambda}^{-1}-\bar{C}\right]\right\|^2_{S_2} \mid \underline{x}_n \right]\\
&= \mathbb{E}\left[\left\|\left[\left(\frac{1}{n}\sum_{i=1}^{n}y_i\otimes \phi(x_i)\right)\hat{C}_{X, \lambda}^{-1}-\bar{C}\right]\right\|^2_{S_2} \mid \underline{x}_n \right]\\
&= \mathbb{E}\left[\left\|\left[\frac{1}{n}\sum_{i=1}^{n}\left(\bar{C}\phi(x_i) + \epsilon_i\right)\otimes \phi(x_i)\hat{C}_{X, \lambda}^{-1}-\bar{C}\right]\right\|^2_{S_2} \mid\underline{x}_n \right]\\
&= \mathbb{E}\left[\left\|\left[-\bar{C}r_{\lambda}\left(\hat{C}_{X}\right) + \frac{1}{n}\sum_{i=1}^{n}\epsilon_i\otimes \left(\hat{C}_{X, \lambda}^{-1}\phi(x_i)\right)\right]\right\|^2_{S_2}\mid \underline{x}_n \right]\\
&= \left\|\left[\bar{C}r_{\lambda}\left(\hat{C}_{X}\right)\right]\right\|^2_{S_2} + \frac{1}{n^2}\sum_{i=1}^{n}\mathbb{E}\left[\|\epsilon_i\|^2_{\mathcal{Y}} \mid x_i\right]\left\|\left[\hat{C}_{X, \lambda}^{-1}\phi(x_i)\right]\right\|_{L_2(\pi)}^2\\
&\geq \lambda^2\left\|\left[\bar{C}\hat{C}_{X,\lambda}^{-1}\right]\right\|^2_{S_2} + \frac{\sigma^2}{n^2}\sum_{i=1}^{n}\left\|\left[\hat{C}_{X,\lambda}^{-1}\phi(x_i)\right]\right\|_{L_2(\pi)}^2.
\end{align*}

The second term is a lower bound on the variance while the first term is a lower bound on the bias.

Bounding the Bias term. The idea is to first show that the population analogue of $\left\|\left[\bar{C}\hat C_{X,\lambda}^{-1}\right]\right\|^2_{S_2(L_2(\pi),\cY)}$ can be bounded below by a non-zero constant. We can then bound the difference between the empirical and population version of $\left\|\left[\bar{C}\hat C_{X,\lambda}^{-1}\right]\right\|^2_{S_2(L_2(\pi),\cY)}$ using a concentration inequality.
By Lemma <ref>, for $\lambda > 0$, there is a constant $c>0$ (see Lemma <ref> for the exact value of $c$) such that

\begin{equation*}
\left\|\left[\bar{C}C_{X,\lambda}^{-1}\right]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2\geq c > 0.
\end{equation*}

Furthermore by Lemma <ref>, there is a constant $c_0 > 0$ (see Lemma <ref> for the exact value of $c_0$) such that for any $\tau \geq \log(4),$ with probability at least $1-4e^{-\tau}$, for $n\geq \left(c_0\tau\right)^{(4+2p)}$ and $ 1 \geq \lambda \geq n^{-\frac{1}{2+p}}$, we have

\begin{equation*}
\left|\left\|[\bar{C}C_{X,\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2 - \left\|[\bar{C}\hat{C}_{X,\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2\right| = \tau^2o(1).
\end{equation*}

Therefore, under the same high probability,

\begin{equation*}
\|[\bar{C}\hat{C}_{X,\lambda}^{-1}]\|_{S_2(L_2(\pi),\mathcal{Y})}^2\geq c - \tau^2 o(1).
\end{equation*}

It leads to our final bound on the bias term, for a constant $\rho_2 \geq 0$ and for sufficiently large $n\geq 1$, where the hidden index bound depends on $\tau$, we have

\begin{equation}\label{eq: bias_term_lower_bound_constant}
\lambda^2\left\|\left[\bar{C}\hat{C}_{X,\lambda}^{-1}\right]\right\|^2_{S_2(L_2(\pi),\mathcal{Y})} \geq \rho_1 \lambda ^2.
\end{equation}

Bounding the Variance Term.  Using the norm from Definition <ref>, we have the following chain of identities.

\begin{equation} \label{eq:variance_other_form}
\begin{aligned}
\frac{\sigma^2}{n^2}\sum_{i=1}^{n}\left\|\left[\hat{C}_{X,\lambda}^{-1}\phi(x_i)\right]\right\|_{L_2(\pi)}^2 &= \frac{\sigma^2}{n^2}\sum_{i=1}^{n}\int_{\cX}\left\langle \phi(X), \hat{C}_{X,\lambda}^{-1}\phi(x_i)\right\rangle^2_{\cH}d\pi(x)\\ &= \frac{\sigma^2}{n} \int_{\cX} \|\hat{C}_{X,\lambda}^{-1}\phi(X)\|_{2,n}^2 d\pi(x).
\end{aligned}
\end{equation}

Therefore it suffices to consider $\int_{\cX} \|\hat{C}_{X,\lambda}^{-1}k(x, \cdot)\|_{2,n}^2 d\pi(x)$.

Combining the result of Lemma <ref> and Lemma <ref> we obtain that for $1 \geq \lambda \geq n^{-\frac{1}{2+p}}$ with probability at least $1 - 6e^{-\tau},$ for $n \geq (c_0\tau)^{4+2p}$, the following bounds hold simultaneously for all $x\in \cX$:

\begin{align}
\left\|\hat{C}_{X}^{\frac{1}{2}}\left(\hat{C}_{X,\lambda}^{-1} - C_{X,\lambda}^{-1}\right)k(x,\cdot)\right\|_{\cH} &\leq \tau o(1) \nonumber\\
\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{2,n}^2 - \frac{1}{2}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 &\geq - \tau o(1) \nonumber\\
\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{2,n}^2 - \frac{3}{2}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 &\leq  \tau o(1).\nonumber
\end{align}

Fix $x \in \cX$. Using the algebraic identity $a^2-b^2 = (a-b)(2b+(a-b))$, and recalling that by Definition <ref>,

\begin{equation*}
\|f\|_{2,n}^2 = \left\|\hat{C}_{X}^{\frac{1}{2}}f\right\|_{\cH}^2,
\end{equation*}

we deduce

\begin{align*}
&\left| \left\|\hat{C}_{X}^{\frac{1}{2}}\hat{C}_{X,\lambda}^{-1}k(x,\cdot)\right\|_{\cH}^2- \left\|\hat{C}_{X}^{\frac{1}{2}}C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{\cH}^2\right|\\
\leq & \left\|\hat{C}_{X}^{\frac{1}{2}}\left(\hat{C}_{X,\lambda}^{-1} - C_{X,\lambda}^{-1}\right)k(x,\cdot)\right\|_{\cH} \cdot \left(\left\|\hat{C}_{X}^{\frac{1}{2}}\left(\hat{C}_{X,\lambda}^{-1} - C_{X,\lambda}^{-1}\right)k(x,\cdot)\right\|_{\cH} + 2\left\|C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{2,n}\right)\\
\leq  & \tau o(1)\left(\tau o(1) + 2\left\|C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{2,n}\right).
\end{align*}

Using Definition <ref> again, this reads

\begin{equation*}
\left\|\hat{C}_{X,\lambda}^{-1}k(x,\cdot)\right\|_{2,n}^2 \geq  \left\|C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{2,n}^2 - \tau o(1)\left(\tau o(1) + 2\left\|C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{2,n}\right).
\end{equation*}

We have

\begin{align*}
\|C_{X,\lambda}^{-1}k(x,\cdot)]\|_{2,n}^2 &\leq  \frac{3}{2}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2  +  \tau o(1) \leq \left(\sqrt{1.5}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)} + \sqrt{\tau} o(1)\right)^2.
\end{align*}

\begin{align*}
\left\|\hat{C}_{X,\lambda}^{-1}k(x,\cdot)\right\|_{2,n}^2 \geq& \left\|C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{2,n}^2 - \tau o(1)\left(\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)} + \sqrt{\tau}o(1) + \tau o(1)\right)\\
\geq &\frac{1}{2}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 - \tau o(1)\\ &- \tau o(1)\left(\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)} + \sqrt{\tau}o(1) + \tau o(1)\right)\\
\geq & \frac{1}{2}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 - \tau^2 o(1)-  \tau o(1)\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}.
\end{align*}

By Lemma <ref>,

\int_{\cX} \left\|[C_{X,\lambda}^{-1} k(x, \cdot)]\right\|_{L_2(\pi)}^2d\pi(x) = \mathcal{N}_{2}(\lambda).

Furthermore, by Jensen's inequality,

\begin{equation*}
\int_{\cX}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 \mathrm{d}\pi(x) \geq \left(\int_{\cX}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)} \mathrm{d}\pi(x) \right)^2.
\end{equation*}

Recall from Lemma <ref> that

\begin{equation*}
c_{1,2}\lambda^{-p}\leq \mathcal{N}_2(\lambda)\leq c_{2,2}\lambda^{-p}.
\end{equation*}

Therefore we have

\begin{align*}
\int_{\cX}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)} \mathrm{d}\pi(x)  & \leq \sqrt{c_{2,2}}\lambda^{-\frac{p}{2}}\\
\int_{\cX}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 \mathrm{d}\pi(x) & \geq c_{1,2}\lambda^{-p}.
\end{align*}

\begin{equation*}
\begin{aligned}
\int_{\cX}\|\hat{C}_{X,\lambda}^{-1}k(x,\cdot)\|_{2,n}^2d\pi(x) & \geq \frac{c_{1,2}}{2}\lambda^{-p}- \tau^2 o(1)-  \tau o(1)\sqrt{c_{2,2}}\lambda^{-\frac{p}{2}}\\
&\geq \left(\frac{c_{1,2}}{2} - \tau o(1)\sqrt{c_{2,2}}\right)\lambda^{-p} - \tau^2 o(1)\\
%&\geq \rho_2\lambda^{-p}.
\end{aligned}
\end{equation*}

Combined with Eq. (<ref>), it leads to our final bound on the variance term, for a constant $\rho_2 \geq 0$ and for sufficiently large $n\geq 1$, where the hidden index bound depends on $\tau$, we have

\begin{equation}\label{eq: variance_term_lower_bound_lambda_minus_p}
\frac{\sigma^2}{n^2}\sum_{i=1}^{n}\left\|\left[\hat{C}_{X,\lambda}^{-1}\phi(x_i)\right]\right\|_{L_2(\pi)}^2 \geq \frac{\rho_2}{n\lambda^{p}}.
\end{equation}

Putting it together. We are now ready to assemble the lower bounds on the variance and on the bias. For a fixed confidence parameter $\tau \geq \log(10)$, for sufficiently large $n>0$, where the hidden index bound depends on $\tau$, with probability at least $1-10e^{-\tau}$, we have by Eq. (<ref>) and
Eq. (<ref>), that for $\lambda = \lambda(n)$ satisfying $1 \geq \lambda > n^{-\frac{1-q}{2+p}}$ for some $q\in (0,\frac{1}{2})$,

\mathbb{E}\left[\left\|[\hat{F}_{\lambda}]-F_{\ast}\right\|^2_{L_2(\pi; \cY)} \mid x_1, \ldots, x_n\right] \geq \rho_1\lambda^2 + \rho_2n^{-1}\lambda^{-p}

where $\rho_1,\rho_2$ have no dependence on $n$. Recall Young's inequality, for $r,q>1$ satisfying $r^{-1} + q^{-1} = 1$, we have for all $a,b \geq 0$,

\[a+b\geq r^{\frac{1}{r}}q^{\frac{1}{q}}a^{\frac{1}{r}}b^{\frac{1}{q}}.\]

We apply Young's inequality with $r^{-1} = p/(2+p)$ and $q^{-1} = 2/(2+p)$, there exists a constant $c_1>0$ such that

\begin{align*}
\rho_1\lambda^2 + \rho_2n^{-1}\lambda^{-p} \geq c_1 \left(\lambda^2\right)^{\frac{p}{2+p}}\left(\lambda^{-p}n^{-1}\right)^{\frac{2}{2+p}} = c_1n^{-\frac{2}{2+p}}.
\end{align*}

To conclude the proof, let $\lambda = \lambda(n)$ be an arbitrary choice of regularization parameter satisfying $\lambda(n) \to 0$. We have just covered the case $1 \geq \lambda \geq n^{-\frac{1}{2+p}}$ and the case $0 < \lambda \leq n^{-\frac{1}{2+p}}$ is covered by <cit.>.

For any $\lambda \leq 1$ and $C \in S_2(\cH, \cY)$, with $C \nperp S_2(\overline{\text{ran}~S_{\pi}}, \cY)$[$\nperp$ is the notation for “not being orthogonal to”.], we have

\begin{equation*}
\left\|\left[CC_{X,\lambda}^{-1}\right]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2\geq \sum_{i\in I, j\in J}a_{ij}^2\frac{\mu_i}{(\mu_i+1)^2} > 0,
\end{equation*}

with $a_{ij}:= \langle d_j, C\sqrt{\mu_i}e_i \rangle_{\cY}$, $i\in I, j\in J$.

Define $\{a_{ij}\}_{i \in I \cap I', j \in J}$ such that $a_{ij}:= \langle d_j, C\sqrt{\mu_i}e_i \rangle_{\cY}$ for $i \in I, j \in J$ and $a_{ij}:= \langle d_j, C\tilde{e}_i \rangle_{\cY}$ for $i \in I', j \in J$. Then, on one hand, since $C \in S_2(\cH, \cY),$

C = \sum_{i \in I, j\in J} a_{ij}  d_j \otimes (\sqrt{\mu_i}e_i) + \sum_{i \in I', j\in J} a_{ij}  d_j \otimes \tilde{e}_i.

On the other hand,

C_{X,\lambda}^{-1} = \sum_{i \in I} (\mu_i + \lambda)^{-1}  (\sqrt{\mu_i}e_i) \otimes (\sqrt{\mu_i}e_i) + \lambda^{-1}\sum_{i \in I'} \tilde{e}_i \otimes \tilde{e}_i.

Therefore, noting that $\tilde{e}_i=0$ $\pi-$a.e. for all $i \in I'$, we have,

\begin{align*}
&= \left[\sum_{i\in I,j \in J}a_{ij}(\mu_i+\lambda)^{-1}d_j\otimes (\sqrt{\mu_i}e_i) + \sum_{i \in I', j\in J} \frac{a_{ij}}{\lambda}  d_j \otimes \tilde{e}_i \right] \\
&= \sum_{i\in I,j \in J} a_{ij}\frac{\sqrt{\mu_i}}{\mu_i+\lambda} d_j\otimes [e_i].
\end{align*}

Therefore the $S_2(L_2(\pi),\mathcal{Y})$-norm can be evaluated in closed form using Parseval's identity,

\begin{equation*}
\left\|\left[CC_{X,\lambda}^{-1}\right]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2 = \sum_{i\in I,j \in J}a_{ij}^2\frac{\mu_i}{(\mu_i+\lambda)^2} \geq \sum_{i\in I,j \in J}a_{ij}^2\frac{\mu_i}{(\mu_i+1)^2},
\end{equation*}

where we used that $\{d_j\}_{j \in J}$ is orthonormal in $\mathcal{Y}$, $\{[e_i\}_{i \in I})$ is orthonormal in $L_2(\pi)$, and $\lambda \leq 1$. The right hand side has no dependence on $\lambda$ or $n$. Furthermore, under assumption (<ref>), $\mu_i>0$ for all $i \in I$, therefore the right hand side term equals zero if and only if $a_{ij} = 0$ for all $i \in I,j \in J$. Since by assumption $C \nperp S_2(\overline{\text{ran}~S_{\pi}}, \cY)$, the right hand side is strictly positive.

Suppose Assumption (<ref>) holds with $p \in (0,1]$. Let $C \in S_2(\cH, \cY)$ such that $[C] \in S_2([\cH]^2, \cY)$. There is a constant $c_0 > 0$ such that for any $\delta \geq \log(4),$ with probability at least $1-4e^{-\tau}$, for $n\geq \left(c_0\tau\right)^{(4+2p)}$ and $1 \geq \lambda \geq n^{-\frac{1}{2+p}}$, we have

\begin{equation*}
\left|\left\|[CC_{X\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2 - \left\|[C\hat{C}_{X\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2\right| \leq \tau^2 o(1)
\end{equation*}

We have $c_0:= 8\kappa \max\{\sqrt{c_{2,1}},1\}$) where $c_{2,1}$ is defined in Lemma <ref>.

Using the identity $A^{-1}- B^{-1} = A^{-1}(B-A)B^{-1}$, we obtain

\begin{equation*}
C_{X,\lambda}^{-1} - \hat{C}_{X,\lambda}^{-1} = C_{X,\lambda}^{-1}(\hat{C}_{X}-C_{X})\hat{C}_{X,\lambda}^{-1}
\end{equation*}

We apply Lemma <ref> with $\gamma = 0$,

\begin{align}
\left\|\left[C\left(C_{X,\lambda}^{-1}-\hat{C}_{X,\lambda}^{-1}\right)\right]\right\|_
{S_2(L_2(\pi),\mathcal{Y})}\nonumber =& \left\|\left[C\hat{C}_{X,\lambda}^{-1}(\hat{C}_{X}-C_{X})C_{X,\lambda}^{-1}\right]\right\|_
=& \left\|C\hat{C}_{X,\lambda}^{-1}(\hat{C}_{X}-C_{X})C_{X,\lambda}^{-1}C_{X}^{\frac{1}{2}}\right\|_
\leq& \left\|C\hat{C}_{X,\lambda}^{-\frac{1}{2}}\right\|_{S_2(\cH,\mathcal{Y})}\left\|\hat{C}_{X,\lambda}^{-\frac{1}{2}}C_{X,\lambda}^{\frac{1}{2}}\right\|_{\cH \to \cH} \nonumber\\ &\cdot\left\|C_{X,\lambda}^{-\frac{1}{2}}(\hat{C}_{X}-C_{X})C_{X,\lambda}^{-\frac{1}{2}}\right\|_{\cH \to \cH}\left\|C_{X,\lambda}^{-\frac{1}{2}}C_{X}^{\frac{1}{2}}\right\|_{\cH \to \cH}\label{eqn: sat_eff_bias_decomposition_four_term_to_apply_steinwart_fischer}
\end{align}

We consider each of the four terms in line (<ref>). The last term is bounded above by $1$ and the first term is bounded above by $\lambda^{-\frac{1}{2}}\|C\|_{S_2(\cH,\mathcal{Y})}$.

By Lemma <ref> applied with $s = 1/2$, we have for the second term

\left\|\hat{C}_{X,\lambda}^{-\frac{1}{2}}C_{X,\lambda}^{\frac{1}{2}}\right\|_{\cH \to \cH} \leq \left\|\hat{C}_{X,\lambda}^{-1}C_{X,\lambda}\right\|_{\cH \to \cH}^{\frac{1}{2}}.

Then, by Lemma <ref>, for $\tau \geq \log(2)$,  with probability at least $1-2e^{-\tau}$, for $\sqrt{n\lambda} \geq 8\tau \kappa \sqrt{\max\{\cN(\lambda),1\}}$, we have

\begin{equation*}
\left\|\hat{C}_{X,\lambda}^{-1}C_{X,\lambda}\right\|_{\cH \to \cH} \leq 2.
\end{equation*}

Since $\mathcal{N}(\lambda)\leq c_{2,1}\lambda^{-p}$ by Lemma <ref>, and $\lambda \leq 1$, it suffices to verify that $\lambda$ satisfies

\begin{align*}
\sqrt{n\lambda} & \geq 8\tau \kappa \max\{\sqrt{c_{2,1}},1\}\lambda^{-\frac{p}{2}}.
\end{align*}

Since $\lambda\geq n^{-\frac{1}{2+p}}$ by assumption, we deduce the sufficient condition $n \geq (\tau c_0)^{2(2+p)}$, where $c_0:= 8\kappa \max\{\sqrt{c_{2,1}},1\}$.

We bound the third term using Lemma 16 [Lin and Cevher, 2020]. For $\tau \geq \log(2)$, with probability at least $1-2e^{-\tau}$, we have

\begin{equation*}
\lambda^{-\frac{1}{2}}\left\|C_{X,\lambda}^{-\frac{1}{2}}(C_{X}-\hat{C}_{X})C_{X,\lambda}^{-\frac{1}{2}}\right\|_{\cH \to \cH} \leq \frac{4\kappa^2\xi_{\delta}}{3n\lambda^{\frac{3}{2}}} + \sqrt{\frac{2\kappa^2\xi_{\delta}}{n\lambda^2}},
\end{equation*}

where we define

\begin{equation*}
\xi_{\delta}:= \log\frac{2\kappa^2(\mathcal{N}_1(\lambda)+1)}{e^{-\tau}\|C_{X}\|_{\cH \to \cH}}.
\end{equation*}

By assumption $\lambda\geq n^{-\frac{1}{2+p}}$. We thus have

\begin{align*}
n\lambda^{\frac{3}{2}} \geq n^{\frac{1+2p}{4+2p}} \qquad \text{ and } \qquad  n\lambda^{2} \geq n^{\frac{p}{2+p}}.
\end{align*}

On the other hand, since $1 \geq \lambda \geq n^{-\frac{1}{2+p}}$, using Lemma <ref>, we have

\begin{align*}
\xi_{\delta} \leq \log \frac{8
2(c_{2,1}\lambda^{-p}+1)}{e^{-\tau}\|C_{X}\|_{\cH \to \cH}} \leq \log \frac{2(c_{2,1}+1)n^{\frac{p}{2+p}}}{e^{-\tau}\|C_{X}\|_{\cH \to \cH}} \leq \log \frac{2(c_{2,l}+1)}{e^{-\tau}\|C_{X}\|_{\cH \to \cH}} + \frac{p}{2+p}\log n.
\end{align*}

The first term does not depend on $n$, and the second term is logarithmic in $n$. Putting everything together with a union bound, we get a bound on (<ref>). With probability at least $1-4e^{-\tau}$, for $n\geq \left(c_0\tau\right)^{(4+2p)}$, we have

\begin{equation*}
\left\|\left[C\left(C_{X,\lambda}^{-1}-\hat{C}_{X,\lambda}^{-1}\right)\right]\right\|_{S_2(L_2(\pi),\mathcal{Y})}\leq \|C\|_{S_2(\cH,\mathcal{Y})}\sqrt{2}\left(\frac{4\xi_{\delta}}{3n^{\frac{0.5+p}{2+p}}} + \sqrt{\frac{2\xi_{\delta}}{n^{\frac{p}{2+p}}}}\right) = \tau o(1)
\end{equation*}

The derivations in the proof of Lemma <ref> show that

[CC_{X,\lambda}^{-1}] = \sum_{i\in I,j \in J} a_{ij}\frac{\sqrt{\mu_i}}{\mu_i+\lambda} d_j\otimes [e_i],

with $a_{ij}:= \langle d_j, C\sqrt{\mu_i}e_i \rangle_{\cY}$, $i\in I, j\in J$. Note that since $[C] \in S_2([\cH]^2, \cY)$, we have

\|[C]\|_{S_2([\cH]^2, \cY)}^2 = \left\|
\sum_{i \in I, j\in J} a_{ij}  d_j \otimes (\sqrt{\mu_i}e_i) \right\|_{S_2([\cH]^2, \cY)}^2  = \sum_{i \in I, j\in J} \frac{a_{ij}^2}{\mu_i} < +\infty.

\begin{equation}
\label{eqn: sat_eff_interpolation_norm_2_agrees_with_L_2_norm}
\left\|[CC_{X,\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2 = \sum_{i\in I, j\in J }a_{ij}^2\frac{\mu_i}{(\mu_i+\lambda)^2} \leq \sum_{i\in I, j\in J}\frac{a_{ij}^2}{\mu_i} = \|[C]\|_{S_2([\cH]^2, \cY)}^2 < + \infty.
\end{equation}

Using the equality $a^2 - b^2 = (a-b)(a+b)$ and the reverse triangular inequality, we obtain the following bound, with probability at least $1-4e^{-\tau}$, for $n\geq \left(c_0 \tau \right)^{(4+2p)}$,

\begin{align*}
&\left|\left\|[CC_{X,\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2 - \left\|[C\hat{C}_{X,\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})}^2\right|\\ \leq& \left\|\left[C\left(C_{X,\lambda}^{-1}-\hat{C}_{X,\lambda}^{-1}\right)\right]\right\|_{S_2(L_2(\pi),\mathcal{Y})}\left(\left\|[CC_{X,\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})} + \left\|[C\hat{C}_{X,\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})}\right)\\
\leq & \tau o(1)\left(2\left\|[CC_{X,\lambda}^{-1}]\right\|_{S_2(L_2(\pi),\mathcal{Y})} + \left\|\left[C\left(C_{X,\lambda}^{-1}-\hat{C}_{X,\lambda}^{-1}\right)\right]\right\|_{S_2(L_2(\pi),\mathcal{Y})}\right)\\
\leq &\tau o(1)\left(2\|[C]\|_{S_2([\cH]^2, \cY)}^2 + \tau o(1)\right)\\
= & \tau^2 o(1),
\end{align*}

where in the second last line we used Equation (<ref>).

Fix $x\in \cX$ and $f_x$ as in Definition <ref>. For $\tau \geq \log(2)$, with probability at least $1-2e^{-\tau}$ (note that this event depends on $x$),

\begin{equation*}
\left|\|f_x\|_{2,n}^2 - \|[f_x]\|_{L_2(\pi)}^2\right|\leq \frac{1}{2}\|[f_x]\|_{L_2(\pi)}^2 + \frac{5\tau \kappa^2}{3\lambda^2 n}.
\end{equation*}

We start with

\begin{align*}
\|f_x\|_{\infty} \leq \kappa\|f_x\|_{\cH}  \leq \kappa^2 \lambda^{-1}.
\end{align*}

We apply Proposition <ref> to $f = f_x$, with $M=\kappa^2 \lambda^{-1}$. For $\tau \geq \log(2)$, with probability at least $1-2e^{-\tau}$,

\begin{equation*}
\left|\|f_x\|_{2,n}^2 - \|[f_x]\|_{L_2(\pi)}^2\right|\leq \frac{1}{2}\|[f_x]\|_{L_2(\pi)}^2 + \frac{5\tau \kappa^2}{3\lambda^2 n}.
\end{equation*}

Suppose that $\cX$ is a compact set in $\Rd$ and that $k \in C^{\theta}(\mathcal{X}\times \mathcal{X})$ for $\theta \in (0,1]$ (Definition <ref>). Assume that $1 \geq \lambda\geq n^{-\frac{1}{2+p}}$. With probability at least $1-2e^{-\tau}$, it holds for all $ x\in \cX$ simultaneously that

\begin{align*}
\|C_{X,\lambda}^{-1}k(x,\cdot)\|_{2,n}^2&\geq  \frac{1}{2}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 - \tau o(1),\\%\label{eq: lower_concentration_bound_f_2_n_lma_statement_union_bound}\\
\|C_{X,\lambda}^{-1}k(x,\cdot)\|_{2,n}^2&\leq  \frac{3}{2}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 +\tau o(1).%\label{eq: upper_concentration_bound_f_2_n_lma_statement_union_bound}
\end{align*}

The proof follows <cit.>. As we use different notations and tracking of constants, we provide a similar proof in our setting for completeness. By Lemma <ref>, there exists an $\epsilon$-net $\mathcal{F}\subseteq \mathcal{K}_{\lambda} \subseteq \cH$ with respect to $\|\cdot\|_{\infty}$ such that there exists a positive constant $c$ with

\begin{equation*}
|\mathcal{F}| \leq c(\lambda\epsilon)^{-\frac{2d}{\theta}},
\end{equation*}

for $\epsilon$ to be determined later. Using Lemma <ref> and a union bound over the finite set $\mathcal{F}$, with probability at least $1-2e^{-\tau}$, it holds simultaneously for all $f\in \mathcal{F}$ that

\begin{equation}
\left|\|f\|_{2,n}^2 - \|[f]\|_{L_2(\pi)}^2\right|\leq \frac{1}{2}\|[f]\|_{L_2(\pi)}^2 + \frac{5(\tau+\log(|\mathcal{F}|))\kappa^2}{3\lambda^2 n}.
\label{eqn: simultaneous_epsilon_net_union_bound_concentration}
\end{equation}

We work in the event where Equation (<ref>) holds for all $f\in \mathcal{F}$. By definition of an $\epsilon$-net and $\mathcal{K}_{\lambda}$, for any $x\in \cX$, there exists some $f\in \mathcal{F}$ such that

\begin{equation*}
\|C_{X,\lambda}^{-1}k(x,\cdot)-f\|_{\infty}\leq \epsilon,
\end{equation*}

which in particular implies that

\begin{align*}
|\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)} - \|[f]\|_{L_2(\pi)}|&\leq \epsilon\\
|\|C_{X,\lambda}^{-1}k(x,\cdot)\|_{2,n} - \|f\|_{2,n}|&\leq \epsilon.
\end{align*}

Since $\|C_{X,\lambda}^{-1}k(x,\cdot)\|_{\infty}\leq \kappa^2\lambda^{-1}$, using the algebraic identity $a^2 - b^2 = (a-b)(2b+(a-b))$, we obtain

\begin{align*}
|\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|^2_{L_2(\pi)} - \|[f]\|^2_{L_2(\pi)}|&\leq \epsilon(2\kappa^2\lambda^{-1}+\epsilon)\\
|\|C_{X,\lambda}^{-1}k(x,\cdot)\|^2_{2,n} - \|f\|^2_{2,n}|&\leq \epsilon(2\kappa^2\lambda^{-1} + \epsilon).
\end{align*}

We therefore have,

\begin{align*}
\|C_{X,\lambda}^{-1}k(x,\cdot)\|_{2,n}^2 &\leq \|f\|_{2,n}^2 + \epsilon(2\kappa^2\lambda^{-1} + \epsilon)\\
&\leq \frac{3}{2}\|[f]\|_{L_2(\pi)}^2 + \frac{5(\tau+\log(|\mathcal{F}|) \kappa^2}{3\lambda^2 n} + \epsilon(2\kappa^2\lambda^{-1} + \epsilon)\\
&\leq \frac{3}{2}\|[C_{X,\lambda}^{-1}k(x,\cdot)]\|_{L_2(\pi)}^2 + \frac{5(\tau+\log(|\mathcal{F}|) \kappa^2}{3\lambda^2 n} + 2\epsilon(2\kappa^2\lambda^{-1} + \epsilon).
\end{align*}

We now choose $\epsilon = \frac{1}{n}$ and bound the error term. Recall that $1 \geq \lambda \geq n^{-\frac{1}{2+p}}$, therefore,

\begin{align*}
\frac{5(\tau+\log(|\mathcal{F}|) \kappa^2}{3\lambda^2 n} + 2\epsilon(2\kappa^2\lambda^{-1} + \epsilon) &\leq \frac{5(\tau+\log(|\mathcal{F}|) \kappa^2}{3}n^{-\frac{p}{2+p}} + 2\left(2\kappa^2n^{\frac{-1-p}{2+p}}+\frac{1}{n^2}\right)\\
&\leq \frac{5\kappa^2}{3}\left(\tau + \log(c\lambda^{-\frac{2d}{\theta}}n^{\frac{2d}{\theta}})\right)n^{-\frac{p}{2+p}} + 2\left(2\kappa^2n^{\frac{-1-p}{2+p}}+\frac{1}{n^2}\right)\\
& = \tau o(1).
\end{align*}

For $1 \geq \lambda \geq n^{-\frac{1}{2+p}}$, with probability at least $1 - 4e^{-\tau},$ for $n \geq (c_0\tau)^{4+2p}$,
we have for all $x\in \cX$ simultaneously

\begin{equation}
\label{eqn: main_eq_lma: key_conc_inequality_app_steinwart_fischer_lemma_17}
\left\|\hat{C}_{X}^{\frac{1}{2}}\hat{C}_{X,\lambda}^{-1}(C_{X}-\hat{C}_{X})C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{\cH} = \tau o(1),
\end{equation}

where $c_0$ is the same constant as in Lemma <ref>.

\begin{align}
=& \left\|\hat{C}_{X}^{\frac{1}{2}}\hat{C}_{X,\lambda}^{-\frac{1}{2}}\hat{C}_{X,\lambda}^{-\frac{1}{2}}C_{X,\lambda}^{\frac{1}{2}}C_{X,\lambda}^{-\frac{1}{2}}(C_{X}-\hat{C}_{X})C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{\cH}\nonumber\\
&\leq \left\|\hat{C}_{X}^{\frac{1}{2}}\hat{C}_{X,\lambda}^{-\frac{1}{2}}\right\|_{\cH \to \cH}\left\|\hat{C}_{X,\lambda}^{-\frac{1}{2}}C_{X,\lambda}^{\frac{1}{2}}\right\|_{\cH \to \cH} \nonumber \\ &\cdot \left\|C_{X,\lambda}^{-\frac{1}{2}}(C_{X}-\hat{C}_{X})C_{X,\lambda}^{-\frac{1}{2}}\right\|_{\cH \to \cH}\left\|C_{X,\lambda}^{-\frac{1}{2}}k(x,\cdot)\right\|_{\cH}\nonumber
\end{align}

We already saw in the proof of Lemma <ref> that the first term is bounded by 1 and there is a constant $c_0>0$ such that for $\tau \geq \log(2)$, with probability at least $1-2e^{-\tau}$, for $n \geq (c_0\tau)^{4+2p}$, the second term is bounded by $\sqrt{2}$. For the third term we also saw in the proof of Lemma <ref> that for $\tau \geq \log(2)$, with probability at least $1-2e^{-\tau}$, we have

\begin{equation*}
\lambda^{-\frac{1}{2}}\left\|C_{X,\lambda}^{-\frac{1}{2}}(C_{X}-\hat{C}_{X})C_{X,\lambda}^{-\frac{1}{2}}\right\|_{\cH \to \cH} \leq \frac{4\kappa^2\xi_{\delta}}{3n\lambda^{\frac{3}{2}}} + \sqrt{\frac{2\kappa^2\xi_{\delta}}{n\lambda^2}},
\end{equation*}

where we defined

\begin{equation*}
\xi_{\delta}= \log\frac{2\kappa^2(\mathcal{N}_1(\lambda)+1)}{e^{-\tau}\|C_{X}\|_{\cH \to \cH}}.
\end{equation*}

Finally, the fourth term is bounded above by $\lambda^{-\frac{1}{2}}\kappa$. Note that the bound on the fourth term is independent of $x$, so it holds simultaneously for all $x\in \cX$. This is in  contrast with the setting of Lemma <ref> where for each fixed $x \in \cX$ corresponds an element in the $\epsilon$-net of $\mathcal{F}$ for which we have a high probability bound, and therefore we must use a union bound in order for the bound to hold simultaneously for all $x\in \cX$ in the proof of Lemma <ref>.
As in the proof of Lemma <ref> since  $1 \geq \lambda\geq n^{-\frac{1}{2+p}}$, we have

\begin{align*}
\xi_{\delta} \leq \log \frac{2(c_{2,l}+1)}{e^{-\tau}\|C_{X}\|_{\cH \to \cH}} + \frac{p}{2+p}\log n.
\end{align*}

In the bound on $\xi_{\delta}$ above, the first term does not depend on $n$, and the second term is logarithmic in $n$. Putting everything together by union bound, with probability at least $1-4e^{-\tau}$, for $n \geq (c_0\tau)^{4+2p}$, we have

\begin{equation*}
\left\|\hat{C}_{X}^{\frac{1}{2}}\hat{C}_{X,\lambda}^{-1}(C_{X}-\hat{C}_{X})C_{X,\lambda}^{-1}k(x,\cdot)\right\|_{\cH} = \tau o(1).
\end{equation*}

We explicit the differences between our proof strategy and the proof strategy of  [Li et al., 2023].

* Scalar versus vector-valued: lower bounding the bias in our case require us to accommodate for the vector-valued setting (see Lemma <ref>).

* New proof of the bias: we lower bound the bias through Lemma <ref>, while [Li et al., 2023] obtain the lower bound in Lemma C.7; however the proof of Lemma C.7 implicitly uses the equality $\|A^{-1}\| = \|A\|^{-1}$, with $\|\cdot\|$ the operator norm, see Eq. (69) [Li et al., 2023] and the preceding equations. It holds that $\|A^{-1}\| \geq \|A\|^{-1}$, but $\|A^{-1}\| \leq \|A\|^{-1}$ may not hold in general. We therefore develop a new proof for this step, leading to  Lemma <ref>.

* New proof of the variance: we lower bound the variance in Lemma <ref>, while [Li et al., 2023] lower bound the variance in Lemma C.12; to show Eq. (<ref>), [Li et al., 2023] use a covering argument involving $\mathcal{N}(\mathcal{K}_{\lambda},\|\cdot\|_{\mathcal{H}},\epsilon)$ (Lemma C.10). However, a close look at the proof of Lemma C.10 (last inequality of the proof) reveals that $\frac{\lambda_i}{\lambda + \lambda_i}$ was mistaken for $\frac{\lambda}{\lambda + \lambda_i}$ and plugging the correct term in the proof would lead to a vacuous bound. As explained in the proof of Lemma <ref>, we therefore develop a proof that is free of a covering number argument for this step.

§ LEARNING RATES FOR SPECTRAL ALGORITHMS

To upper bound the excess-risk, we use a decomposition involving the approximation error expressed as $F_{\lambda} - F_{*}$ and the estimation error expressed as $\hat{F}_{\lambda} - F_{\lambda}$.

\begin{align*}
\left\|[\hat{F}_{\lambda}] - F_{*}\right\|_{\gamma} &\leq \|[\hat{F}_{\lambda} - F_{\lambda}]\|_{\gamma} +\left\|[F_{\lambda}] - F_{*}\right\|_{\gamma},
\end{align*}

where $\hat{F}_{\lambda}$ is the empirical estimator based on general spectral regularization (Eq. (<ref>)) and $F_{\lambda}$ is its counterpart in population (Eq. (<ref>)). Note that this is a different decomposition than the bias-variance decomposition used in the proof of Theorem <ref>.

The proof structure is as follows:

* Fourier expansion <ref>.

* Approximation Error <ref>.

* Estimation error <ref>

§.§ Fourier expansion

Recall the notations defined in Appendix <ref>. The family $\{d_j\}_{j \in J}$ is an ONB of $\mathcal{Y}$, the family $\{\sqrt{\mu_i}e_i\}_{i\in I}$ is an ONB of $(\ker I_{\pi})^{\perp}$ and the family $\{\tilde{e}_i\}_{i \in I'}$ is an ONB of $\ker I_{\pi}$ such that $\left\{\mu_i^{1/2}e_i\right\}_{i\in I} \cup \{\tilde{e}_i\}_{i \in I'}$ forms an ONB of $\cH$. Furthermore, recall that $\{\mu_i^{\beta/2}[e_i]\}_{i\in I}$ is an ONB of $[\cH]^{\beta}$, $\beta \geq 0$.

[Fourier expansion]

Suppose Assumption (<ref>) holds with $\beta \geq 0$. By definition of the vector-valued interpolation space and by Theorem <ref>, we have

\begin{equation}
\label{eqn: F_ast_Fourier}
F_{\ast} = \sum_{i\in I, j \in J}a_{ij}d_j[e_i], \qquad a_{ij} = \left\langle F_*, d_j[e_i]  \right\rangle_{L_2(\pi, \mathcal{Y})}, \qquad \left\|F_{\ast}\right\|_{\beta}^2 = \sum_{i\in I, j \in J}\frac{a_{ij}^2}{\mu_i^{\beta}}.
\end{equation}

Then, we have the following equalities with respect to this Fourier decomposition.

* The Hilbert-Schmidt operator $C_{\lambda}\in S_2(\cH,\mathcal{Y})$, Eq. (<ref>), can be written as

\begin{equation}
\label{eq:C_lambda_decomposition}
C_{\lambda} = \sum_{i \in I, j \in J} a_{ij} g_{\lambda}(\mu_i)\sqrt{\mu_i} d_j\otimes \sqrt{\mu_i}e_i.
\end{equation}

* The Hilbert-Schmidt operator $\left(C_{YX} - C_{\lambda}C_{X}\right)C_{X,\lambda}^{-\frac{1}{2}}\in S_2(\cH,\mathcal{Y})$ can be written as

\begin{equation}
\left(C_{YX} - C_{\lambda}C_{X}\right)C_{X,\lambda}^{-\frac{1}{2}} = \sum_{ij}a_{ij}r_{\lambda}(\mu_i)(\mu_i+\lambda)^{-\frac{1}{2}}\sqrt{\mu_i}\left(d_j \otimes \sqrt{\mu_i} e_i\right)\label{eq:Fourier_expansion_subresult_2}
\end{equation}

* The Hilbert-Schmidt operator $C_{YX}\in S_2(\cH,\mathcal{Y})$ can be written as

\begin{equation}
C_{YX} = \left(\sum_{i \in I, j \in J}a_{ij}\mu_i^{-\frac{\beta}{2}}d_j\otimes \sqrt{\mu_i}e_i\right)C_{X}^{\frac{\beta+1}{2}}\label{eq:Fourier_expansion_subresult_3}
\end{equation}

We first derive the Fourier expansion of $C_{YX}$,

\begin{align}
C_{YX} &= \mathbb{E}_{X,Y}\left[Y\otimes \phi(X)\right]\nonumber\\
&= \mathbb{E}_X\left[F_{\ast}(X)\otimes \phi(X)\right]\label{eq:C_YX_Fourier_expansion_tower}\\
&= \mathbb{E}_X\left[\sum_{i \in I, j \in J}a_{i \in I, j \in J}e_i(X)d_j\otimes \phi(X)\right]\nonumber\\
&= \mathbb{E}_X\left[\sum_{i \in I, j \in J}a_{ij}d_j\otimes \left(\sum_{k \in I}\sqrt{\mu_k}e_k(X)\sqrt{\mu_k}e_k\right)e_i(X)\right]\nonumber\\
&= \sum_{ijk}a_{ij}\sqrt{\mu_k} \cdot \mathbb{E}_X[e_k(X)e_i(X)] \cdot d_j\otimes (\sqrt{\mu_k}e_k)\nonumber\\
&= \sum_{i \in I, j \in J}a_{ij}\sqrt{\mu_i}d_j\otimes (\sqrt{\mu_i}e_i),\label{eq:C_YX_Fourier_expansion_orthonormality}
\end{align}

where in Eq. (<ref>) we used the tower property of conditional expectation and in Eq. (<ref>) we used the fact that  $\{[e_i]\}_{i\in I}$ forms an orthonormal system in $L_2(\pi)$. We can manipulate Eq. (<ref>) to derive Eq. (<ref>),

\begin{align*}
&= \sum_{i \in I, j \in J}a_{ij}\mu_i^{\frac{1}{2}-\frac{\beta+1}{2}}d_j\otimes \left(C_{X}^{\frac{\beta+1}{2}}(\sqrt{\mu_i}e_i)\right)\\
&= \left(\sum_{i \in I, j \in J}a_{ij}\mu_i^{-\frac{\beta}{2}}d_j\otimes \sqrt{\mu_i}e_i\right)C_{X}^{\frac{\beta+1}{2}}.
\end{align*}

By the spectral decomposition of $C_X$ Eq. (<ref>) and spectral calculus (Definition <ref>), we have that

\begin{align}
g_{\lambda}(C_X) &= \sum_{i \in I} g_{\lambda}(\mu_i)\sqrt{\mu_i}e_i \otimes \sqrt{\mu_i}e_i +  g_{\lambda}(0)\sum_{i \in I'}\tilde{e}_i \otimes \tilde{e}_i,\label{eq:g_lambda_C_X_spectral_calculus_Fourier}\\
r_{\lambda}(C_X) &= \sum_{i \in I} r_{\lambda}(\mu_i)\sqrt{\mu_i}e_i \otimes \sqrt{\mu_i}e_i +  \sum_{i \in I'}\tilde{e}_i \otimes \tilde{e}_i.\label{eq:r_lambda_C_X_spectral_calculus_Fourier}
\end{align}

where we used $r_{\lambda}(0)=1$.

Proof of Eq. (<ref>). Using Eq. (<ref>) and (<ref>), we have
\begin{align}
&= \left(\sum_{i \in I, j \in J}a_{ij}\sqrt{\mu_i}d_j\otimes (\sqrt{\mu_i}e_i)\right) \left(\sum_{k\in I}g_{\lambda}(\mu_k)(\sqrt{\mu_k}e_k)\otimes (\sqrt{\mu_k}e_k) + g_{\lambda}(0)\sum_{l\in I'}\Tilde{e}_l\otimes \Tilde{e}_l\right)\nonumber\\
&= \sum_{ijk}a_{ij}\sqrt{\mu_i}g_{\lambda}(\mu_k)\delta_{ik}d_j\otimes(\sqrt{\mu_ke_k})\label{eq:C_lambda_Fourier_ONB}\\
&= \sum_{i \in I, j \in J}a_{ij}\sqrt{\mu_i}g_{\lambda}(\mu_i)d_j\otimes (\sqrt{\mu_i}e_i),\nonumber
\end{align}

where in Eq. (<ref>), we recall the fact that $\{\sqrt{\mu_i}e_i\}_{i\in I}$ forms an ONB of $(\ker I_{\pi})^{\perp}$ and $\{\Tilde{e_i}\}_{i\in I'}$ forms an ONB of $\ker I_{\pi}$.

Proof of Eq. (<ref>). Using Eq. (<ref>) and (<ref>), we have

\begin{align}
\big(C_{YX} - &C_{\lambda}C_{X}\big)C_{X,\lambda}^{-\frac{1}{2}} = C_{YX}r_{\lambda}(C_{X})C_{X,\lambda}^{-\frac{1}{2}}\nonumber\\
&= \left(\sum_{i \in I, j \in J}a_{ij}\sqrt{\mu_i}d_j\otimes (\sqrt{\mu_i}e_i)\right)\left(\sum_{k \in I} r_{\lambda}(\mu_k)\sqrt{\mu_k}e_k \otimes \sqrt{\mu_k}e_k +  \sum_{l \in I'}\tilde{e}_l \otimes \tilde{e}_l\right)C_{X,\lambda}^{-\frac{1}{2}}\nonumber\\
&= \left(\sum_{ijk}a_{ij}\sqrt{\mu_i}r_{\lambda}(\mu_k)d_j\otimes (\sqrt{\mu_k}e_k)\delta_{ik}\right)C_{X,\lambda}^{-\frac{1}{2}}\nonumber\\%\label{eq:r_lambda_C_X_Fourier_ONB}\\
&= \sum_{i \in I, j \in J}a_{ij}\sqrt{\mu_i}r_{\lambda}(\mu_i)d_j\otimes (C_{X,\lambda}^{-\frac{1}{2}}(\sqrt{\mu_i}e_i))\nonumber\\
&= \sum_{i \in I, j \in J}a_{ij}\sqrt{\mu_i}(\mu_i+\lambda)^{-\frac{1}{2}}r_{\lambda}(\mu_i)d_j\otimes (\sqrt{\mu_i}e_i),\nonumber
\end{align}

Suppose Assumption (<ref>) holds with $\beta \geq 0$, then the following bound is satisfied, for all $\lambda>0$ and $0\leq \gamma \leq 1$, we have

\begin{equation*}
\|[F_{\lambda}]\|_{\gamma}^2\leq E^2\|F_{\ast}\|_{\min\{\gamma,\beta\}}^2\lambda^{-(\gamma-\beta)_{+}}.
\end{equation*}

For the definition of $E$, see Eq. (<ref>).

We adopt the notation of Lemma <ref>. By Parseval's identity and Eq. (<ref>), we have

\begin{align*}
\|[F_{\lambda}]\|_{\gamma}^2 &= \|C_{\lambda}\|_{S_2([\mathcal{H}]^{\gamma},\mathcal{Y})}^2\\
&= \sum_{i \in I, j \in J} a_{ij}^2 g_{\lambda}(\mu_i)^2\mu_i^{2-\gamma}.
\end{align*}

In the case of $\gamma\leq \beta$, we bound $g_{\lambda}(\mu_i)\mu_i\leq E$ using Eq. (<ref>). Then, by Eq. (<ref>),

\begin{equation*}
\|[F_{\lambda}]\|_{\gamma}^2 \leq E^2\sum_{i \in I, j \in J}\frac{a_{ij}^2}{\mu_i^{\gamma}} = E^2\|F_{\ast}\|_{\gamma}^2.
\end{equation*}

In the case of $\gamma>\beta$, we apply Eq. (<ref>) to $g_{\lambda}(\mu_i)\mu_i^{1-\frac{\gamma-\beta}{2}} \leq E\lambda^{-\frac{\gamma-\beta}{2}}$ to obtain, using Eq. (<ref>) again,

\begin{align*}
\|[F_{\lambda}]\|_{\gamma}^2 &= \sum_{i \in I, j \in J}g_{\lambda}(\mu_i)^2\mu_i^{2-(\gamma-\beta)}\mu_i^{-\beta}a_{ij}^2\\
&\leq E^2\lambda^{-(\gamma-\beta)}\sum_{i \in I, j \in J}\mu_i^{-\beta}a_{ij}^2\\
\end{align*}

Suppose Assumption (<ref>) holds for $0 \leq \beta\leq 2\rho$, with $\rho$ the qualification. Then, the following bound is satisfied, for all $\lambda>0$, we have

\begin{equation*}
\left\|\left(C_{YX} - C_{\lambda}C_{X}\right)C_{X,\lambda}^{-\frac{1}{2}}\right\|_{S_2\left(\cH,\mathcal{Y}\right)}\leq \omega_{\rho}\|F_{\ast}\|_{\beta}\lambda^{\frac{\beta}{2}}.
\end{equation*}

For the definition of $\omega_\rho$, see Eq. (<ref>).

Recall that in Lemma <ref> we used the decomposition

\begin{equation*}%\label{eq:F_ast_genreg}
F_{\ast} = \sum_{i \in I, j \in J}a_{ij}d_j [e_i],
\end{equation*}

where Assumption (<ref>) implies that $\left\|F_{\ast}\right\|_{\beta}^2 = \sum_{ij}\frac{a_{ij}^2}{\mu_i^{\beta}}< \infty$.
Using Eq. (<ref>) in Lemma <ref> and Parseval’s identity w.r.t. the ONS $\{d_j\otimes \mu_i^{1/2}e_i\}_{i \in I, j \in J}$ in $S_2(\cH,\mathcal{Y})$, we have

\begin{align}
\left\|\left(C_{YX} - C_{\lambda}C_{X}\right)C_{X,\lambda}^{-\frac{1}{2}}\right\|_{S_2\left(\cH,\mathcal{Y}\right)} &= \left(\sum_{i \in I, j \in J}a_{ij}^2r_{\lambda}^2(\mu_i)(\mu_i+\lambda)^{-1}\mu_i\right)^{\frac{1}{2}}\nonumber\\
&\leq \left(\sum_{i \in I, j \in J}\frac{a_{ij}^2}{\mu_i^{\beta}}r_{\lambda}^2(\mu_i)\mu_i^{\beta}\right)^{\frac{1}{2}}\nonumber\\
&\leq \|F_{\ast}\|_{\beta}\sup_{i \in I} r_{\lambda}(\mu_i)\mu_i^{\frac{\beta}{2}}\nonumber\\
&\leq \|F_{\ast}\|_{\beta}\omega_{\rho}\lambda^{\frac{\beta}{2}}.\nonumber%\label{eq:bound_second_term}
\end{align}

Suppose Assumption (<ref>) holds with $\beta \geq 0$, then for all $\lambda > 0$, we have

\[\left\|C_{\lambda}r_{\lambda}\left(\hat{C}_{X}\right) {\hat{C}_{X,\lambda}}^{\frac{1}{2}}\right\|_{S_2(\cH,\mathcal{Y})} \leq B
\left\|\hat{C}_{X,\lambda}^{\frac{1}{2}}r_{\lambda}(\hat{C}_{X})g_{\lambda}(C_{X})C_{X}^{\frac{\beta+1}{2}}\right\|_{\cH\to\cH},\]

where $\|F_{\ast}\|_{\beta}=B<\infty$.

Recall that Lemma <ref> we used the decomposition

\begin{equation*}
F_{\ast} = \sum_{i\in I, j\in j}a_{ij}d_j [e_i],
\end{equation*}

where $\left\|F_{\ast}\right\|_{\beta}^2 = \sum_{ij}\frac{a_{ij}^2}{\mu_i^{\beta}} = B^2 < \infty$. Using Eq. (<ref>) in Lemma <ref> and $C_{\lambda} = C_{YX}g_{\lambda}(C_{X})$, we have

\begin{align*}
\left\|C_{\lambda}r_{\lambda}\left(\hat{C}_{X}\right) {\hat{C}_{X,\lambda}}^{\frac{1}{2}}\right\|_{S_2(\cH,\mathcal{Y})} &=  \left\| \left(\sum_{ij}a_{ij}\mu_i^{-\frac{\beta}{2}}d_j\otimes \sqrt{\mu_i}e_i\right)C_{X}^{\frac{\beta+1}{2}}g_{\lambda}(C_{X})r_{\lambda}(\hat{C}_{X})\hat{C}_{X,\lambda}^{\frac{1}{2}}\right\|_{S_2(\cH,\mathcal{Y})}\\
&\leq B\left\|C_{X}^{\frac{\beta+1}{2}}g_{\lambda}(C_{X})r_{\lambda}(\hat{C}_{X})\hat{C}_{X,\lambda}^{\frac{1}{2}}\right\|_{\cH\to\cH},
\end{align*}

where we notice that the ${S_2(\cH,\mathcal{Y})}$ norm of the first term is exactly the $\beta$ norm of $F_{\ast}$, which is given by $B$.  Recalling that $C_X,\hat{C}_X$ are self adjoint, we prove the final result by taking the adjoint and using that an operator has the same operator norm as its adjoint.

§.§ Approximation Error

Let $F_{\lambda}$
be given by Eq. (<ref>)
based on a general spectral filter satisfying Definition <ref> with qualification $\rho \geq 0$. Suppose Assumption (<ref>) holds with parameter $\beta \geq 0$ and define $\beta_{\rho} = \min\{\beta, 2\rho\}$, then the following bound is satisfied, for all $\lambda > 0$ and $0 \leq \gamma \leq \beta_{\rho}$,

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

In Eq. (<ref>), we defined $F_{\lambda}(\cdot) = C_{\lambda}\phi(\cdot)$. On the other hand, in Lemma <ref> we obtained the Fourier expansion of $C_{\lambda}$ leading to Eq. (<ref>). Thus we have for $\pi-$almost all $x \in \cX$,

\begin{equation*}
F_{\lambda}(x) = \sum_{i \in I, j\in J}a_{ij}\mu_ig_{\lambda}(\mu_i)d_je_i(x).
\end{equation*}

[F_{\lambda}] - F_{\ast} = \sum_{i \in I, j\in J}a_{ij}(1-\mu_ig_{\lambda}(\mu_i))d_j[e_i] = \sum_{i \in I, j\in J}a_{ij}r_{\lambda}(\mu_i)d_j[e_i].

Suppose $\beta \leq 2\rho$, using Parseval’s identity w.r.t. the ONB $\{d_j\mu_i^{\gamma/2}[e_i]\}_{i \in I, j \in J}$ of $[\cG]^{\gamma}$, we have

\begin{align*}
\|[F_{\lambda}] - F_{\ast}\|_{\gamma}^2
&= \left\|\sum_{i \in I, j\in J}\frac{a_{ij}}{\mu_i^{\gamma/2}}r_{\lambda}(\mu_i)d_j \mu_i^{\gamma/2}e_i\right\|_{\gamma}^2\\
&= \sum_{i \in I, j\in J}\frac{a_{ij}^2}{\mu_i^{\gamma}}r_{\lambda}^2(\mu_i)\\
&= \sum_{i \in I, j\in J}\frac{a_{ij}^2}{\mu_i^{\beta}}r_{\lambda}^2(\mu_i)\mu_i^{\beta-\gamma}\\
&\leq \omega_{\rho}^2\lambda^{\beta-\gamma}\sum_{i \in I, j\in J}\frac{a_{ij}^2}{\mu_i^{\beta}}\\
&= \|F_{\ast}\|_{\beta}^2\omega_{\rho}^2\lambda^{\beta-\gamma}
\end{align*}

where we used Eq. (<ref>) in the definition of a filter function, together with  $0\leq \beta\leq 2\rho$ and $0\leq \gamma\leq \beta$, which taken together implies that $0\leq \frac{\beta-\gamma}{2}\leq \rho$. Finally, if $\beta \geq 2\rho$, then since $[\cG]^{2\rho} \subseteq [\cG]^{2\beta}$, we can perform the last derivations again with $\beta=2\rho$ to obtain the final result.

§.§ Estimation error

Before proving the main results we recall two embedding properties for the vector-valued interpolation space $[\mathcal{G}]^{\beta}$ (Definition <ref>). The first embedding property lifts the property (<ref>) defined for the scalar-valued RKHS $[\cH]^{\alpha}$ to the vector-valued RKHS $[\cG]^{\alpha}$.
[$L_{\infty}$-embedding property - Lemma 4 [Li et al., 2023]]

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

[$L_q$-embedding property - Theorem 3 [Li et al., 2023]]

Let Assumption (<ref>) be satisfied with parameter $\alpha\in (0,1]$. For any $\beta\in [0,\alpha)$, the inclusion map

\begin{equation*}
\mathcal{I}_{\pi}^{q_{\alpha,\beta}}:[\mathcal{G}]^{\beta}\hookrightarrow L_{q_{\alpha,\beta}}(\pi;\mathcal{Y})
\end{equation*}

is bounded, where $q_{\alpha,\beta} := \frac{2\alpha}{\alpha-\beta}$.

The $L_q$-embedding property was first introduced in the scalar-valued setting in [Zhang et al., 2023] and then lifted to the vector-valued setting by [Li et al., 2023]. Its role is to replace a boundedness condition on the ground truth function $F_{\ast}$. We now explain how the $L_q$-embedding property can be combined with Assumption (<ref>) and a truncation technique.

Recall that $\pi$ is the marginal measure of $X$ on $\cX$. For $t \geq 0$, define the measurable set $\Omega_t$ as follows

\[\Omega_t:=\left\{x\in \cX:\|F_{\ast}(x)\|_{\mathcal{Y}}\leq t\right\}\]

Let $q>0$. Assume that $F_{\ast}\in L_q(\pi;\mathcal{Y})$. In other words, there exists some constant $c_q>0$ such that

\[\|F_{\ast}\|_{L_q(\pi;\mathcal{Y})} = \left(\int_{\cX}\|F_{\ast}(x)\|_{\mathcal{Y}}^q\mathrm{d}\pi(x)\right)^{\frac{1}{q}}= c_q < +\infty,\]

Then we have the following conclusions

* The $\pi$-measure of the complement of $\Omega$ can be bounded by

\begin{equation*}
\pi(\{x\notin\Omega_t\})\leq \frac{c_q^q}{t^q}.
\end{equation*}

* Recall that $\{x_i\}_{i=1}^n$ are i.i.d. samples distributed according to $\pi$. If $t = n^{\frac{1}{\Tilde{q}}}$ for $\Tilde{q}<q$, then we can conclude as follows. For a fixed parameter $\tau>0$, for all sufficiently large $n$, where the hidden index bound depends on $q\Tilde{q}^{-1}$ and $\tau$, we have

\begin{equation*}%\label{eqn:whp_allx_n_in_Omega}
\pi^{\otimes n}\left(\cap_{i=1}^{n}\{x_i\in\Omega_t\}\right) \geq 1 - e^{-\tau}.
\end{equation*}

The first claim is a straightforward application of Markov's inequality, as follows

\begin{equation*}
\pi(\{x\notin \Omega_t\}) = \pi\left(\|F_{\ast}(x)\|_{\mathcal{Y}}> t\right) \leq \frac{\mathbb{E}_{\pi}\left[\left\|F_{\ast}(X)\right\|_{\mathcal{Y}}^q\right]}{t^q} = \frac{c_q^q}{t^q}.
\end{equation*}

To show the second claim, we first evaluate the probability that there exists some $x_i$'s that lies outside $\Omega_t$,

\begin{align*}
\pi^{\otimes n}\left(\cup_{i=1}^{n}\{x_i\notin \Omega_t\}\right) &= 1 - \pi^{\otimes n}\left(\cap_{i=1}^{n}\{x_i\in \Omega_t\}\right)\\
&= 1 - \pi(\{x_i\in \Omega_t\})^n\\
&\leq 1 - \left(1 - \frac{c_q^q}{t^q}\right)^n\\
&\leq \frac{c_q^qn}{t^q},
\end{align*}

where in the last inequality we used Bernoulli's inequality, which states that for $r\geq 1$ and $0\leq x\leq 1$,

\[(1-x)^r\geq 1-rx.\]

By assumption $t = n^{\frac{1}{q_t}}$ for some fixed $q>q_t>0$. We thus have

\begin{align*}
\pi^{\otimes n}\left(\cup_{i=1}^{n}\{x_i\notin \Omega_t\}\right) &\leq c_q^qn^{1-\frac{q}{q_t}}  \leq e^{-\tau},
\end{align*}

for sufficiently large $n$, where the hidden index bound depends on $\frac{q}{q_t}$ and $\tau$.

We adapt <cit.> to the spectral algorithms setting.

Suppose Assumptions (<ref>) and (<ref>) hold for some $0\leq \beta\leq 2\rho$, with $\rho$ the qualification, then the following bounds are satisfied, for all $0<\lambda\leq 1,$

\begin{align}
\|[F_{\lambda}]-F_{\ast}\|_{L_{\infty}}^2&\leq \left(\|F_{\ast}\|_{L_{\infty}} + A\max\{E,\omega_{\rho}\}\|F_{\ast}\|_{\beta}\right)^2\lambda^{\beta-\alpha},\label{eq:lietal_Lemma_5_1}\\
\|[F_{\lambda}]\|_{L_{\infty}}^2&\leq A^2E^2\|F_{\ast}\|_{\min\{\alpha,\beta\}}^2\lambda^{-(\alpha-\beta)_{+}},\label{eq:lietal_Lemma_5_2}
\end{align}

We use Lemma <ref> and Lemma <ref> to write:

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

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

\begin{align*}
\|[F_{\lambda}] - F_{\ast}\|_{\infty} & \leq \|F_{\ast}\|_{\infty} + \|[F_{\lambda}]\|_{\infty}\\
&\leq (\|F_{\ast}\|_{\infty} + AE\|F_{\ast}\|_{\beta})\lambda^{-\frac{\alpha-\beta}{2}}.
\end{align*}

In the case $\beta>\alpha$, Eq. (<ref>) is a consequence of Lemma <ref> and Lemma <ref> with $\gamma = \alpha$ (here we use the assumption $0\leq \beta\leq 2\rho$),

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

We adapt <cit.> to the vector-valued setting.

Suppose that Assumptions (<ref>), (<ref>), (<ref>) and (<ref>) hold for $0\leq \beta \leq 2\rho$, where $\rho$ is the qualification, and $p\leq \alpha \leq 1$. Denote, for $i=1,\ldots,n$,

\[\xi_i = \xi(x_i,y_i) = \left(\left(y_i -C_{\lambda}\phi(x_i) \right) \otimes \phi(x_i)\right) C_{X,\lambda}^{-\frac{1}{2}},\]

and for $t\geq 0$,

\[\Omega_t = \left\{x\in \mathcal{X}: \|F_{\ast}(x)\|_{\mathcal{Y}}\leq t\right\}\]

Then for all $\tau \geq 1$, with probability at least $1-2e^{-\tau}$, we have

\begin{align*}
&\left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i \mathbbm{1}\{x_i \in \Omega_t\} - \mathbb{E}[\xi(X, Y)\mathbbm{1}\{X \in \Omega_t\}]\right\|_{S_2(\cH,\mathcal{Y})}\\ &\leq \tau\left(c_1\lambda^{\frac{\beta}{2}-\alpha}n^{-1} + c_2\lambda^{-\frac{\alpha}{2}}n^{-1}(t+R+A) + \frac{c_3 \sqrt{\mathcal{N}_1(\lambda)}}{\sqrt{n}} + \frac{c_4}{\sqrt{n} \lambda^{\frac{\alpha-\beta}{2}}}\right)
\end{align*}

where $R$ is the constant from Assumption (<ref>), and
\begin{align*}
c_1 &= 8\sqrt{2}A^2\max\{E,\omega_{\rho}\}\|F_{\ast}\|_{\beta}\\
c_2&= 8\sqrt{2}A\\
c_3&= 8\sqrt{2}\sigma\\
c_4&= 8\sqrt{2}A\|F_{\ast}\|_{\beta}\omega_{\rho}
\end{align*}

where $A$ is the constant from Assumption (<ref>), and $E,\omega_\rho$ are defined in Eq. (<ref>) and (<ref>) respectively.

We wish to apply vector-valued Bernstein's inequality, namely Theorem <ref>. We thus compute,

\begin{align}
\mathbb{E}\left[\|\xi(X,Y)\mathbbm{1}\{X\in\Omega_t\}\|_{S_2(\cH,\mathcal{Y})}^m\right] &= \mathbb{E}\left[\mathbbm{1}\{X\in\Omega_t\}\left\|(Y-C_{\lambda}\phi(X))\otimes \left(C_{X,\lambda}^{-\frac{1}{2}}\phi(X) \right)\right\|_{S_2(\cH,\mathcal{Y})}^m\right]\nonumber\\
&= \mathbb{E}\left[\mathbbm{1}\{X\in\Omega_t\}\left\|(Y-C_{\lambda}\phi(X))\right\|_{\mathcal{Y}}^m\left\|C_{X,\lambda}^{-\frac{1}{2}}\phi(X)\right\|_{\cH}^m\right]\nonumber\\
&= \int_{\Omega_t}\left\|C_{X,\lambda}^{-\frac{1}{2}}\phi(x)\right\|_{\cH}^m\int_{\mathcal{Y}}\left\|y-C_{\lambda}\phi(x)\right\|_{\mathcal{Y}}^m\mathrm{d}p(x,\mathrm{d}y)\mathrm{d}\pi(x).\label{eq:inner_outer_integral}
\end{align}

First we consider the inner integral, by Assumption (<ref>),

\begin{align*}
\int_{\mathcal{Y}}\left\|(y-C_{\lambda}\phi(x))\right\|_{\mathcal{Y}}^m\mathrm{d}p(x,\mathrm{d}y) &\leq 2^{m-1}\left(\int_{\mathcal{Y}}\left\|y-F_{\ast}(x)\right\|_{\mathcal{Y}}^m + \left\|F_{\lambda}(x)-F_{\ast}(x)\right\|_{\mathcal{Y}}^m\right)\mathrm{d}p(x,\mathrm{d}y)\\
&= m!\sigma^2(2R)^{m-2} + 2^{m-1}\left\|F_{\lambda}(x)-F_{\ast}(x)\right\|_{\mathcal{Y}}^m.
\end{align*}

Plugging the above inequality into Eq. (<ref>), as well as introducing the shorthand,

\[h_x:=C_{X,\lambda}^{-\frac{1}{2}}\phi(x),\]

we have

\begin{align}
\mathbb{E}\left[\|\xi(X,Y)\mathbbm{1}\{X\in\Omega_t\}\|_{S_2(\cH,\mathcal{Y})}^m\right] &\leq m!\sigma^2(2R)^{m-2}\int_{\Omega_t}\|h_x\|_{\cH}^m \mathrm{d}\pi(x)\label{eq:m_th_moment_term_one}\\ &+ 2^{m-1}\int_{\Omega_t}\|h_x\|_{\cH}^m\left\|F_{\lambda}(x)-F_{\ast}(x)\right\|_{\mathcal{Y}}^m\mathrm{d}\pi(x).\nonumber%\label{eq:m_th_moment_term_two}
\end{align}

We bound term (<ref>) using Lemma <ref> and Lemma <ref> with $l=1$. We have,

\begin{equation*}
\int_{\Omega_t}\|h_x\|_{\cH}^m\mathrm{d}\pi(x)  \leq (A\lambda^{-\frac{\alpha}{2}})^{m-2}\mathcal{N}_1(\lambda).
\end{equation*}

Therefore we bound term (<ref>) as follows,

\begin{equation*}
m!\sigma^2(2R)^{m-2}\int_{\Omega_t}\|h_x\|_{\cH}^m\mathrm{d}\pi(x) \leq m!\sigma^2\left(\frac{2AR}{\lambda^{\frac{\alpha}{2}}}\right)^{m-2}\mathcal{N}_1(\lambda).
\end{equation*}

If $\beta\geq \alpha$, by Assumption (<ref>),

\begin{equation*}
\|F_{\ast}\|_{\infty}\leq A\|F_{\ast}\|_{\alpha} \leq A\|F_{\ast}\|_{\beta}.
\end{equation*}

Hence by Lemma <ref>,

\begin{equation*}
\|[F_{\lambda}] - F_{\ast}\|_{\infty} \leq (\|F_{\ast}\|_{\infty} + A\max\{E,\omega_\rho\}\|F_{\ast}\|_{\beta})\lambda^{\frac{\beta-\alpha}{2}} \leq A(1+\max\{E,\omega_{\rho}\})\|F_{\ast}\|_{\beta}\lambda^{\frac{\beta-\alpha}{2}}.
\end{equation*}

If $\beta < \alpha$, by Lemma <ref>, we have for $\pi$-almost all $x\in \Omega_t$,

\begin{equation*}
\|F_{\ast}(x) - F_{\lambda}(x)\|_{\mathcal{Y}}\leq t + \|[F_{\lambda}]\|_{L_{\infty}(\pi;\mathcal{Y})}\leq t + AE\|F_{\ast}\|_{\beta}\lambda^{\frac{\beta-\alpha}{2}}.
\end{equation*}

Therefore, for all $\beta\in [0,2\rho]$,

\begin{equation*}
\left\|(F_{\ast} - [F_{\lambda}])\mathbbm{1}_{X\in \Omega_t}\right\|_{L_{\infty}(\pi;\mathcal{Y})} \leq t + A(1+ \max\{E,\omega_\rho\}\|F_{\ast}\|_{\beta}\lambda^{\frac{\beta-\alpha}{2}}) =: \chi(t,\lambda).
\end{equation*}

Using Lemma <ref> with $l=1$, we have,

\begin{align*}
&2^{m-1}\int_{\Omega_t}\|h_x\|_{\cH}^m\|F_{\ast}(x)-F_{\lambda}(x)\|_{\mathcal{Y}}^m\mathrm{d}\pi(x) \\
\leq & 2^{m-1}\chi(t,\lambda)^{m-2}(A\lambda^{-\frac{\alpha}{2}})^{m}\|F_{\ast} - [F_{\lambda}]\|_{L_2(\pi;\mathcal{Y})}^2\\
= & \left(\frac{2\chi(t,\lambda)A}{\lambda^{\frac{\alpha}{2}}}\right)^{m-2}\|F_{\ast}-[F_{\lambda}]\|_{L_2(\pi;\mathcal{Y})}^2\frac{2A^2}{\lambda^{\alpha}}\\
\leq & m!\left(\frac{2\chi(t,\lambda)A}{\lambda^{\frac{\alpha}{2}}}\right)^{m-2}\|F_{\ast}-[F_{\lambda}]\|_{L_2(\pi;\mathcal{Y})}^2\frac{2A^2}{\lambda^{\alpha}}.
\end{align*}

Putting everything together,

\begin{equation*}
\mathbb{E}\left[\|\xi(X,Y)\mathbbm{1}\{X\in\Omega_t\}\|_{S_2(\cH,\mathcal{Y})}^m\right]\leq  m!\left(\frac{2(R+\chi(t,\lambda))A}{\lambda^{\frac{\alpha}{2}}}\right)^{m-2}\left(\sigma^2\mathcal{N}_1(\lambda) + \|F_{\ast}-[F_{\lambda}]\|_{L_2(\pi;\mathcal{Y})}^2\frac{2A^2}{\lambda^{\alpha}}\right).
\end{equation*}

We now apply Theorem <ref> with

\begin{align*}
L&\leftarrow \frac{2(R+\chi(t,\lambda))A}{\lambda^{\frac{\alpha}{2}}}\\
\sigma &\leftarrow 2\sigma\sqrt{\mathcal{N}_1(\lambda)} + \|F_{\ast}-[F_{\lambda}]\|_{L_2(\pi;\mathcal{Y})}\frac{2A}{\lambda^{\frac{\alpha}{2}}}
\end{align*}

We bound $\|F_{\ast}-[F_{\lambda}]\|_{L_2(\pi;\mathcal{Y})}$ using Lemma <ref> with $\gamma = 0$,

\begin{equation*}
\|F_{\ast}-[F_{\lambda}]\|_{L_2(\pi;\mathcal{Y})} \leq \omega_{\rho}\|F_{\ast}\|_{\beta}\lambda^{\frac{\beta}{2}}.
\end{equation*}

The conclusion is, for all $\tau \geq 1$, with probability at least $1-2e^{-\tau}$, we have

\begin{align*}
&\left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i \mathbbm{1}\{x_i \in \Omega_t\} - \mathbb{E}[\xi(X, Y)\mathbbm{1}\{X \in \Omega_t\}]\right\|_{S_2(\cH,\mathcal{Y})}\\ &\leq 4\sqrt{2}\tau\left(\frac{2\sigma\sqrt{\mathcal{N}_1(\lambda)} + \|F_{\ast}-[F_{\lambda}]\|_{L_2(\pi;\mathcal{Y})}\frac{2A}{\lambda^{\frac{\alpha}{2}}}}{\sqrt{n}} + \frac{2(R+\chi(t,\lambda))A}{n\lambda^{\frac{\alpha}{2}}}\right) \\
& \leq 4\sqrt{2}\tau\left(\frac{2\sigma}{\sqrt{n}}\sqrt{\mathcal{N}_1(\lambda)} +
\frac{2A\|F_{\ast}\|_{\beta}\omega_{\rho}}{\sqrt{n}\lambda^{\frac{\alpha-\beta}{2}}} +
\frac{2(R+t+A)A}{n\lambda^{\frac{\alpha}{2}}} +
\frac{2A^2\max\{E,\omega_{\rho}\}\|F_{\ast}\|_{\beta}}{n\lambda^{\alpha-\frac{\beta}{2}}}\right).
\end{align*}

Suppose that the same assumptions and notations listed in Theorem <ref> hold.

* Suppose $\beta + p>\alpha$, and $\lambda \asymp n^{-\frac{1}{\beta+p}}$. For any fixed $\tau \geq 1$, with probability at least $1-2e^{-\tau}$, suppose that the truncation level $t$ satisfies

\begin{equation*}
t\leq n^{\frac{1}{2}\left(1+ \frac{p-\alpha}{p+\beta}\right)},
\end{equation*}

then there exists a constant $c>0$ such that

\begin{equation*}
\left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i \mathbbm{1}\{x_i \in \Omega_t\} - \mathbb{E}[\xi(X, Y)\mathbbm{1}\{X \in \Omega_t\}]\right\|_{S_2(\cH,\mathcal{Y})} \leq c \tau n^{-\frac{1}{2}\frac{\beta}{\beta+p}}.
\end{equation*}

* Suppose $\beta + p\leq \alpha$, and $\lambda \asymp \left(\frac{n}{\log^{\theta}(n)}\right)^{\frac{1}{\alpha}}$ for some $\theta>1$. For any fixed $\tau \geq 1$, with probability at least $1-2e^{-\tau}$, suppose that the truncation level $t$ satisfies

\begin{equation*}
t\leq n^{\frac{1}{2}\left(1-\frac{\beta}{\alpha}\right)},
\end{equation*}

then there exists a constant $c>0$ such that

\begin{equation*}
\left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i \mathbbm{1}\{x_i \in \Omega\} - \mathbb{E}[\xi(X, Y)\mathbbm{1}\{X \in \Omega\}]\right\|_{\mathcal{G}} \leq c \tau \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{\beta}{2\alpha}}
\end{equation*}

Note that Theorem <ref> yields the same conclusion as in the scalar-valued case proved in <cit.>. The Lemma then follows from the analysis for the scalar-valued case in the proof of <cit.>.

We adapt <cit.> to the vector-valued setting.

Suppose that Assumptions (<ref>), (<ref>), (<ref>) and (<ref>) hold for $0 \leq \beta \leq 2\rho$, where $\rho$ is the qualification, and $p\leq \alpha \leq 1$.

* In the case of $\beta + p > \alpha$, choosing $\lambda \asymp n^{-\frac{1}{\beta+p}}$, for any fixed $\tau \geq \log(4)$, when $n$ is sufficiently large, with probability at least $1-4e^{-\tau}$, we have

\begin{equation}
\label{eq:thm: upper_bound_adaptation_zhang_theorem_15_first_regime}
\left\|\left(\left(\hat{C}_{YX} - C_{\lambda}\hat{C}_{X}\right) - \left(C_{YX}-C_{\lambda}C_{X}\right)\right)C_{X,\lambda}^{-\frac{1}{2}}\right\|_{S_2\left(\cH,\mathcal{Y}\right)} \leq c \tau n^{-\frac{1}{2}\frac{\beta}{\beta+p}}
\end{equation}

where $c$ is a constant independent of $n,\tau, \lambda$.

* In the case of $\beta+p\leq \alpha$, choosing $\lambda\asymp \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{1}{\alpha}}$ for some $\theta>1$ . We make the additional assumption that there exists some $\alpha'<\alpha$ such that Assumption (<ref>) is satisfied for $\alpha'<\alpha$. Then, for any fixed $\tau \geq \log(4)$, when $n$ is sufficiently large, where the hidden index bound depends on $\alpha-\alpha'$, with probability at least $1-4e^{-\tau}$, we have

\begin{equation}
\label{eq:thm: upper_bound_adaptation_zhang_theorem_15_second_regime}
\left\|\left(\left(\hat{C}_{YX} - C_{\lambda}\hat{C}_{X}\right) - \left(C_{YX}-C_{\lambda}C_{X}\right)\right)C_{X,\lambda}^{-\frac{1}{2}}\right\|_{S_2\left(\cH,\mathcal{Y}\right)} \leq c\tau \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{\beta}{2\alpha}}
\end{equation}

where $c$ is a constant independent of $n,\tau, \lambda$.

By assumption (<ref>) and Theorem <ref>, if $\beta < \alpha$, then the inclusion map

\begin{equation*}
\mathcal{I}_{\pi}^{q_{\alpha,\beta}}:[\mathcal{G}]^{\beta}\hookrightarrow L_{q_{\alpha,\beta}}(\pi;\mathcal{Y})
\end{equation*}

is bounded, where $q_{\alpha,\beta} := \frac{2\alpha}{\alpha-\beta}$. If $\beta \geq \alpha$, then by Lemma <ref> the inclusion map

\begin{equation*}
\mathcal{I}_{\pi}^{\infty}: [\mathcal{G}]^{\beta}\hookrightarrow L_{\infty}(\pi;\mathcal{Y})
\end{equation*}

is bounded and therefore $[\mathcal{G}]^{\beta}$ is continuously embedded into $L_{q}(\pi;\mathcal{Y})$ for any $q \geq 1$. In the rest of the proof, we will use $q$ to denote $q_{\alpha,\beta}$, unless otherwise specified. Furthermore, we will use $c_q = \|F_{\ast}\|_{L_q(\pi;\mathcal{Y})}$.

We first consider the case $\beta+p>\alpha$.  We can easily verify using $\beta+p>\alpha$ that the following inequality holds

\[\frac{1}{2}\left(1 + \frac{p-\alpha}{p+\beta}\right) > \frac{1}{2}\left(\frac{p}{p+\beta}\right) > \frac{\alpha-\beta}{2\alpha} = \frac{1}{q_{\alpha,\beta}}.\]

Choose $t = n^{\Tilde{q}^{-1}}$, where

\[\frac{1}{\Tilde{q}} = \frac{1}{2}\left(\frac{1}{2}\left(1 + \frac{p-\alpha}{p+\beta}\right) + \frac{1}{q}\right).\]

We thus have

\begin{equation*}
n^{\frac{1}{2}\left(1 + \frac{p-\alpha}{p+\beta}\right)} > t = n^{\Tilde{q}^{-1}} > n^{\frac{1}{q_{\alpha,\beta}}}.
\end{equation*}

Thus the assumptions for both Lemma <ref> and Lemma <ref> are satisfied.

We then consider the case $\beta+p\leq \alpha$. We now apply Assumption (<ref>) and Theorem <ref> to $\alpha'$ instead of $\alpha$. We obtain that the inclusion map $I_{\pi}^{q_{\alpha',\beta}}$ is bounded, where we recall that $q_{\alpha',\beta}$ is defined to be $\frac{2\alpha'}{\alpha'-\beta}$. Since $x\mapsto \frac{2x}{x-\beta}$ is monotonically decreasing for $x> \beta$, we obtain the inequality

\[\frac{2\alpha'}{\alpha'-\beta} > \frac{2\alpha}{\alpha-\beta}.\]

We choose $t = n^{\frac{1}{q_{\alpha,\beta}}}$. By construction, $t$ satisfies the assumptions in Lemma <ref>. Furthermore, the assumptions of Lemma <ref> are satisfied, with $F_{\ast}\in L_{q'}(\pi,\mathcal{Y})$, and $t=n^{\frac{1}{q_{\alpha,\beta}}}$.

Having established the applicability of Lemma <ref> and Lemma <ref>, let us turn our attention to proving the results of the Theorem. Denote

\[\xi(x,y) = (y-C_{\lambda}\phi(x))\otimes \left(C_{X,\lambda}^{-\frac{1}{2}}\phi(x)\right)\]

We compute

\[\mathbb{E}[\xi(x,y)] = (C_{YX} - C_{\lambda}C_X)C_{X,\lambda}^{-\frac{1}{2}} \]

1. The $\beta+p>\alpha$ case. Have

\begin{align*}
\left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i - \mathbb{E}[\xi(x,y)]\right\|_{S_2(\cH,\mathcal{Y})} &\leq \left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i\mathbbm{1}\{x_i\in \Omega_t\} - \mathbb{E}[\xi(x,y)\mathbbm{1}\{x\in\Omega_t\}]\right\|_{S_2(\cH,\mathcal{Y})}\\
+& \left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i\mathbbm{1}\{x_i\in\Omega_t^c\}\right\|_{S_2(\cH,\mathcal{Y})}\\
+& \|\mathbb{E}[\xi(x,y) \mathbbm{1}\left\{x\in\Omega^{c}_t\right\}\|_{S_2(\cH,\mathcal{Y})}
\end{align*}

We can bound the first term with probability at least $1-2e^{-\tau}$ by $c\tau \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{\beta}{2\alpha}}$, according to Lemma <ref>. By Lemma <ref>, with probability at least $1-e^{-\tau}$, for sufficiently large $n$, $x_i\in \Omega_t$ for all $i\in [n]$, whereby the second term is zero. It remains to bound the third term, where our bound will be deterministic. Using Jensen's inequality, we have,

\begin{align*}
\|\mathbb{E}[\xi(x,y) \mathbbm{1}\left\{x\in\Omega_t^{c}\right\}]\|_{S_2(\cH,\mathcal{Y})} &\leq \mathbb{E}\left[\left\|\xi(x,y)\mathbbm{1}\{x\in\Omega_t^{c}\}\right\|_{S_2(\cH,\mathcal{Y})}\right]\\
&= \mathbb{E}\left[\|(y-C_{\lambda}\phi(x))\mathbbm{1}\{x\notin\Omega_t\}\|_{\mathcal{Y}}\cdot \left\|C_{X,\lambda}^{-\frac{1}{2}}\phi(x)\right\|_{\cH}\right]\\
&\leq A\lambda^{-\frac{\alpha}{2}}\mathbb{E}\left[\|(y-C_{\lambda}\phi(x))\mathbbm{1}\{x\notin\Omega_t\}\|_{\mathcal{Y}}\right]
\end{align*}

where in the third line we used Lemma <ref>. We first split the second term into an approximation error and a noise term using triangle inequality.

\begin{equation*}
\mathbb{E}\left[\|(y-C_{\lambda}\phi(x))\mathbbm{1}\{x\notin\Omega_t\}\|_{\mathcal{Y}}\right] \leq \mathbb{E}\left[\|(y-F_{\ast}(x))\mathbbm{1}\{x\notin\Omega_t\}\|_{\mathcal{Y}}\right] + \mathbb{E}\left[\|(F_{\ast}(x)-F_{\lambda}(x))\mathbbm{1}\{x\notin\Omega_t\}\|_{\mathcal{Y}}\right]
\end{equation*}

We bound the first term using the tower property of conditional expectation,

\begin{align*}
\mathbb{E}\left[\|(y-C_{\lambda}\phi(x))\mathbbm{1}\{x\notin\Omega_t\}\|_{\mathcal{Y}}\right]&\leq  \mathbb{E}_{\pi}\left[\mathbb{E}[\|y-C_{\lambda}\phi(x)\|_{\mathcal{Y}}\mid x]\mathbbm{1}\{x\notin\Omega_t\}\right]\\
&\leq \mathbb{E}_{\pi}\left[\mathbb{E}[\|y-C_{\lambda}\phi(x)\|_{\mathcal{Y}}^2\mid x]^{\frac{1}{2}}\mathbbm{1}\{x\notin\Omega_t\}\right]\\
&\leq \sigma \pi(x\notin\Omega_t)\\
&\leq \frac{\sigma c_q^q}{t^q}.
\end{align*}

where in the third inequality we used Assumption (<ref>) with $q=2$, and in the fourth inequality we used Lemma <ref>. We bound the second term using Cauchy-Schwarz inequality and Lemma <ref> with $\gamma = 0$,

\begin{equation*}
\mathbb{E}\left[\|(F_{\ast}(x)-F_{\lambda}(x))\mathbbm{1}\{x\notin\Omega_t\}\|_{\mathcal{Y}}\right] \leq \mathbb{P}(x\notin\Omega_t)^{\frac{1}{2}}\|F_{\ast}\|_{\beta}\omega_{\rho}\lambda^{\frac{\beta}{2}}
\end{equation*}

Therefore, using Lemma <ref>, we have,

\begin{equation}
\label{eqn:mai_22_third_part_bound}
\|\mathbb{E}[\xi(x,y) \mathbbm{1}\left\{x\in\Omega_t^{c}\right\}\|_{S_2(\cH,\mathcal{Y})} \leq A\lambda^{-\frac{\alpha}{2}}\left(\frac{\sigma c_q^q}{t^q} + \frac{c_q^{\frac{q}{2}}}{t^{\frac{q}{2}}}\|F_{\ast}\|_{\beta}\omega_{\rho}\lambda^{\frac{\beta}{2}}\right).
\end{equation}

We now plug in $\lambda\asymp n^{-\frac{1}{\beta+p}}$. Recall that by construction $t > n^{\frac{1}{q}}$. Thus,

\begin{align*}
\lambda^{-\frac{\alpha}{2}}t^{-q} &\lesssim n^{-1}n^{\frac{\alpha}{2(\beta+p)}} < n^{-1}n^{\frac{\beta+p}{2(\beta+p)}} = n^{-\frac{1}{2}} \leq n^{-\frac{1}{2}\frac{\beta}{\beta+p}}\\
\lambda^{\frac{\beta-\alpha}{2}}t^{-\frac{q}{2}} &\lesssim n^{-\frac{1}{2}}n^{\frac{-(\beta-\alpha)}{2(\beta+p)}} < n^{-\frac{1}{2}}n^{\frac{p}{2(\beta+p)}} = n^{-\frac{1}{2}\frac{\beta}{\beta+p}}
\end{align*}

We've therefore proved inequality (<ref>).

2. The $\beta+p\leq \alpha$ case. We proceed similarly to the $\beta+p>\alpha$ case. We have,

\begin{align*}
\left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i - \mathbb{E}[\xi(x,y)]\right\|_{S_2(\cH,\mathcal{Y})} &\leq \left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i\mathbbm{1}\{x_i\in \Omega_t\} - \mathbb{E}[\xi(x,y)\mathbbm{1}\{x\in\Omega_t\}]\right\|_{S_2(\cH,\mathcal{Y})}\\
&+ \left\|\frac{1}{n}\sum_{i=1}^{n}\xi_i\mathbbm{1}\{x_i\in\Omega_t^c\}\right\|_{S_2(\cH,\mathcal{Y})}\\
&+ \|\mathbb{E}[\xi(x,y) \mathbbm{1}\left\{x\in\Omega_t^{c}\right\}]\|_{S_2(\cH,\mathcal{Y})}
\end{align*}

We can bound the first term with probability at least $1-2e^{-\tau}$ by $c\tau\left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{\beta}{2\alpha}}$, according to Lemma <ref>. By Lemma <ref>, with probability at least $1-e^{-\tau}$, for sufficiently large $n$, $x_i\in \Omega_t$ for all $i\in [n]$, whereby the second term is zero. We bound the third term by Eq. (<ref>). We now plug in $\lambda\asymp \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{1}{\alpha}}$. Recall that by construction $t > n^{\frac{1}{q}}$.

\begin{align*}
\lambda^{-\frac{\alpha}{2}}t^{-q} &\lesssim n^{-1}\left(\frac{n}{\log^{\theta}(n)}\right)^{\frac{1}{2}} < \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{1}{2}} \leq  \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{\beta}{2\alpha}}\\
\lambda^{\frac{\beta-\alpha}{2}}t^{-\frac{q}{2}} &\lesssim n^{-\frac{1}{2}}\left(\frac{n}{\log^{\theta}(n)}\right)^{\frac{\alpha-\beta}{2\alpha}} < \left(\frac{n}{\log^{\theta}(n)}\right)^{\frac{-\beta}{2\alpha}}
\end{align*}

We have therefore proved inequality (<ref>).

We adapt <cit.> to the vector-valued setting.

[Bound of estimation error]

Suppose that assumptions (<ref>), (<ref>), (<ref>) and (<ref>) hold for $0 \leq \beta \leq 2\rho$, where $\rho$ is the qualification, and $p\leq \alpha < 1$. For $0\leq \gamma\leq 1$, with $\gamma\leq \beta$,

* In the case of $\beta + p > \alpha$, by choosing $\lambda \asymp n^{-\frac{1}{\beta+p}}$, for any fixed $\tau \geq \log(4)$, when $n$ is sufficiently large, with probability at least $1-4e^{-\tau}$, we have

\begin{equation*}
\|[\hat{C}_{\lambda} - C_{\lambda}]\|_{S_2([\mathcal{H}]^{\gamma},\mathcal{Y})}^2 \leq c\tau^2n^{-\frac{\beta-\gamma}{\beta+p}},
\end{equation*}

where $c$ is a constant independent of $n,\tau$.

* In the case of $\beta + p \leq \alpha$, by choosing $\lambda \asymp \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{1}{\alpha}}$, for any fixed $\tau \geq \log(4)$, when $n$ is sufficiently large, with probability at least $1-4e^{-\tau}$, we have

\begin{equation*}
\|[\hat{C}_{\lambda} - C_{\lambda}]\|_{S_2([\mathcal{H}]^{\gamma},\mathcal{Y})}^2 \leq c\tau^2\left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{\beta-\gamma}{\alpha}}
\end{equation*}

where $c$ is a constant independent of $n,\tau$.

Firstly, we establish the applicability of Lemma <ref>.

1. The $\beta+p>\alpha$ case. Have $\lambda\asymp n^{-\frac{1}{\beta+p}}$, hence

\begin{equation*}
n\lambda^{\alpha} \gtrsim n^{\frac{\beta+p-\alpha}{\beta+p}}
\end{equation*}

whereas using $\lambda\leq \|C_{X}\|_{\mathcal{H}\to\mathcal{H}}$ for sufficiently large $n$, as well as Lemma <ref>,

\begin{equation*}
8 A^{2} \tau  \log\left(2e\mathcal{N}(\lambda)\frac{\|C_{X}\|_{\cH \to \cH}+\lambda}{\|C_{X}\|_{\cH \to \cH}}\right) \leq 8A^2\tau\log(4ec_{2,1}\lambda^{-p})\lesssim 8A^2\tau\left(\log(4ec_{2,1}) + \frac{p}{\beta+p}\log(n)\right)
\end{equation*}

Therefore, for a fixed $\tau>0$,  for all sufficiently large $n$, Eq. (<ref>) in Lemma <ref> is satisfied.

2. The $\beta+p\leq\alpha$ case. Have $\lambda\asymp \left(\frac{n}{\log^{\theta}(n)}\right)^{-\frac{1}{\alpha}}$ for some $\theta>1$, hence

\begin{equation*}
n\lambda^{\alpha}\geq \log^{\theta}(n)
\end{equation*}

whereas similar to the $\beta+p>\alpha$ case, we ahve

\begin{equation*}