Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms
Authors: Dimitri Meunier
Zikai Shen
Mattes Mollenhauer
Arthur Gretton
Zhu Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Kernel methods
nonparametric regression
spectral algorithms
Primary area: learning_theory

Abstract: 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 and various implementations of gradient descent.  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 an upper bound on the finite sample risk for general vector-valued spectral algorithms, applicable to both well-specified and misspecified scenarios (where the true regression function lies outside of the hypothesis space), and show that this bound 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.

Optimal Rates for Valued Spectral Regularization Learning Algorithms
Dimitri Meunier'
Zikai Shen"
Gatsby Computational Neuroscience Unit University College London dimitri meunier 21@ucl.... ac
Department of Statistical Science University College London zikai shen 22@uc1 ac uk
Mattes Mollenhauer Merantix Momentum
mattes wtw..e.le.iiiierrreeeaaaaaaaaroa
Arthur Gretton
Zhu Li Department of Mathematics Imperial College London zli120ic ac uk
Gatsby Computational Neuroscience Unit University College London
arthur arthur.grevt crw.urrgrettotgma....... com
Abstract
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 and various implementations of gradient descent. 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 be suboptimal when the smoothness of the regression function exceeds certain level. Second, we present an upper bound on the finite sample risk for general vector-valued spectral algorithms, applicable to both well-specified and misspecified scenarios (where the true regression function lies outside of the hypothesis space), and show that this bound is minimax optimal in various regimes. All of our results explicitly allow the case of ciinite-dimessioal output variables, proving consistency recent practical applications.
Introduction
We investigate fundamental topic in modern machine learning behavior and efficiency of learning algorithms for regression in high-dimensional and potentially infinte-dimeesionall output spaces V. Given two random variables X and Y, we seek to empirically minimize the squared expected risk
E(F) = E [||Y [3)
(I)
over functions F in a reproducing kernel Hilbert space consisting of vector-valued functions from a topological space X Hilbert space y The study of this setting an ill-posed statistical inverse
problem is well established: see e.g. 46 6 53
5 17 In this work, we study the setting when y
is high-
since it has been less well covered by the literature, yet has many learning problems, including
applications in multitask regression
2 and
Equal Contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the conditional mean embedding [20
21 41,, structured prediction 12]. causal inference 43
regression with instrumental and proximal variables 42 351. the estimation of linear operators
and dynamical systems 47
and functional regression [24]. Interestingly, the aforementioned unfnite-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.
37
26
38
25
Classically, the ill-posed problem T is solved via regularization strategies, which are often imple- mented in terms of so-called spectral filter functions in the context of inverse problems in Hilbert spaces [6).. When applied to the learning problem given by (I), these filter functions correspond to learning algorithms including ridge regression, a variety of different implementations of gradient descent, principal component regression, and other related methods (we refer the reader to 19 and 2 for overviews of the real-valuee and vector-valued output variable case, respectively). Algorithms based on spectral filter functions when y R are studied extensively, see e.g. (5] 34 To the best of our knowledge, the detailed behavior of this general class of algorithms has remained unknown when ) is general Hilbert space, with the exception of few results for special cases in the setting of ridge regression
6 311.
Overview of our contributions. In this manuscript, we aim to theoretically understand vector-valued spectral learning algorithms. The contribution of our work twofold: (i) we rigorously confirm the saturation effect of ridge regression for general Hilbert spaces y (see paragraph below) in the context of lower bounds on rates for the learning problem (T) and (ii) we cover gap the existing literature by providing upper rates for general spectral algorithms in high- and difinte-dimmnsionall spaces. Our results explicitly allow the misspecified learning case which the true regression function not contained in the hypothesis space. We base our analysis on the concept of vector-valued interpolation spaces introduced by [30] 31I. 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 selling for rector-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 certain threshold. This effect has been thoroughly investigated the context of Tikhonov regularization in inverse problems 16 Chapter 5], but is generally reflected only in upper rates in
Interestingly, existing lower bounds 6 5 31 are usually formulated in more general setting and do not reflect this saturation effect, leaving 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.
the learning literature, see e.g. 34 5)
Learning rates of vector-valued spectral algorithms. Motivated by the fact that the saturation effect is technically unavoidable with vector- 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 5 34 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-an upper rates for misspecified vector-valued ridge regression recently obtained by [1]. 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 [2), allowing for the numerical evaluation based on empirical data-even even in the dimensionnl case.
The saturation effect of regularization techniques in deterministic inverse problems well-known. For example, [40 36, 22 study the saturation effect for Tikhonov regularization and general spectral algorithms. In the kernel statistical learning framework, the general phenomenon
Related Work.
of saturation is discussed by e.g. 3 19 Recent work by (29 investigates saturation effect in the learning context by providing lower bound on the learning rate. To the best of our knowledge, however, all studies the statistical learning context focus on the case when Y is real-valued. General upper bounds of kernel ridge regression with real-valued or inite-dimensional Y have
been extensively studied in the literature (see c.g., (6 50 g [7]), where minimax optimal learning
2

---

rates are derived. Recent work [30 31 studies the Tikhonov regularization and obtains analogous minimax optimal learning rates. [23] later study a setting where both the input and output space is the infinite dimensional Sobolev RKHS and establish the minimax optimal rate. For kernel learning with spectral algorithms, existing work (see e.g..
output space setting with
35 32 34 54 (8) ) focuses real-valued output space setting and obtains optimal upper learning
rates depending on the qualification number of the spectral algorithms, where only [54] [8] consider the misspecified learning scenario where the target regression function does not lie in the hypothesis space. For vector-valued output spaces, [27] considers learning with rector-valued random features. 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 2 we introduce mathematical preliminaries related to reproducing kernel Hilbert spaces, vector-valued regression as well as contains
the concept of vector-valued interpolation spaces. Section Sectaon a brief review the so-called saturation effect and a corresponding novel lower bound for vector-valued kernel ridge regression. In Section 4 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.
2 Background and Preliminaries
Throughout the paper, we consider a random variable X (the covariate) defined on a second countable locally compact Hausdorff ppacefIx' endowed with its Borel a-field Fxx and the random variable Y (the output) defined on a potentially infinite dimensional separable real Hilbert space (V, (s-)) endowed with its Borel o-field Fy. We let FF, IP) be the underlying probability space with expectation operator E. Let P be the push-forward of IP under (X,Y) and π and y be the marginal distributions X' and V. respectively; i.e., X π and Y v. We use the Markov kernel p : X' x Fy- + R, to express the distribution of Y conditioned on X as
P E A|X xx]= f plz,, dy).
for all x é X' and events A E Fy, see e.g. 15 We introduce some notation related to linear operators
on Hilbert spaces and vector-valued integration; formal definitions can be found in Appendix A for completeness, or we refer the reader to [52 14. The spaces of Bochner gguurr-inteerabbe functions with respect to and taking values in y are written as L2 (X, .: V)), abbreviated as L2(T:)) We obtain the classical Lebesgue spaces as (T) = T,2 π: TR.. Throughout the paper, we write [F] or more explicitly [F]z for the r-equivalence class of (potentially pointwise defined) measurable functions from X' to V/ which we naturally interpret as elements in (=; whenever they are square-integrable. Let H be a separable real Hilbert space with inner product (-.) We write C(H, HH' as the Banach space of bounded linear operators from H to another Hilbert space H', equipped with the operator norm ||- HP When H H', we simply write L(H) instead. We write S2HH,H)) as the Hilbert space of Hilbert-Schmict operators from H to H' and S₁ (H, H') as the Banach space of trace class operators (see Appendix A for complete definition). For two Hilbert spaces H, H', we say that H is (continuously) embedded in H' and denote it as H + H' if H can be interpreted
vector subspace of H' and the inclusion operator i: H H' performing the change of norms with ix = x for x E H is continuous; and we say that H is isometrically isomorphic to H' and denote it as H = H' if there is a linear isomorphism between H and H' which is an isometry.
Tensor Product of Hilbert Spaces: Denote H @ H' the tensor product of Hilbert spaces H, H'. The element @ x' E H @ H' is treated as the linear rank-one operator @ x' HH' + H defined by y' + 24) H for y' H'. Based on this identification, the tensor product space H @ H' is isometrically isomorphic to the space of -Shbbitt- operators from H' to H. i.e. H @ H' = S2(H', H). . We will hereafter not make the distinction between these two spaces, and treat them as being identical.
Remark (I) Theorem 12.6.1). Consider the Bochner space L2(T;; H) where H is a separable Hilbert space. One can show that L2(T;; H){ is isometrically identified with the tensor product space H @ (T) and we denote as V the isometric isomorphism between the two spaces. See Appendix for more details on tensor product spuces and the explicit definition of V.
Under additional technical assumptions, the results in this paper can also be formulated when X' is a more general topological space. However, some properties of kernels defined on X' such as the so so-called co co-uiversality [10] simplify the exposition when X' is a second countable locally compact Hausdorff space.
3

---

Scalar-valued Reproducing Kernel Hilbert Space (RKHS), let x R be symmetric and positive definite kernel function and H. be vector space of functions from to R. endowed with a Hilbert space structure via an inner product (+, (r. We say that k is reproducing kernel of H if and only if for all a we have k(,,)) E H and for all x X' and f H. we have f(x) = (ʃ. k(x,)) )ar A space H. which possesses a reproducing kernel is called reproducing kernel Hilbert space (RKHS; see e.g. 4). We denote the canonical feature map of H as <(x) k(.,z).
We require some technical assumptions on the previously defined RKHS and kernel, which we assume to be satisfied throughout the text:
1. H. is separable: this is satisfied k is continuous, given that X' is separable }
2. ((),x) is measurable for n-almost all x E X;
3. k(x,.)) & x² for r-llmost all æ X'.
The above assumptions are not restrictive in practice, as well-known kernels such as the Gaussian, Laplace, and Matérn kernels satisfy them on S R.d 488] We now introduce some facts about the interplay between H. and L2(T), which has been extensively studied by [44 45), [3 and [51]. We first define the (not necessarily injective) embedding Lx : 7 L2( mapping a function f ε H its r-equivalence class [.]. The embedding is well-defined compact operator as long as its -chbett- norm is finite. In fact, this requirement is satisfied since its -ccbert-Schhittt norm can be computed as [51 Lemma 2.2 & 2.3] ( |k] ra(T)) & K. The adjoint operator
S := 12 L2 ④ H. is an integral operator with respect to the kernel k. i.. for f (z( and
X we have 49 Theorem 4.27]
(s)) fx (x, (()
Next, we define the self- addf-ndjoint, positive semi-definite and trace class integral operators
Ix == S. (T) I2( and Cx S. H H.
Vector-valued Reproducing Kernel Hilbert Space (vRKHS), Let K : Xxx -f()) be an operator valued positive-semidefnnit (psd) kernel. Fix K, x X, and V, then (Krh) (+) K(:x)h defines a function from X' to y. The completion of
Spe := span (K_hl x x
with inner product on Spre defined on the elementary elements as Karh' (h, K valued reproducing kernel Hilhert space, we refer the reader to 19) 10 and [31 Section 2). In the following, will denote G the vRKHS induced by the kernel K X X L()) with
defines vRKHS denoted G. For more complete overview of the vector-
K K(x, x') (xx, x' Idy,
x, e X.
We emphasize that this family kernels is the facto standard for high- and infinite-dimensional applications 220 21
24 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
2
35
43 37 26
38
25
Remark 2 (General multiplicative kernel). Without loss of generality, we provide our results for the vRKIS & induced by the operator-valued kernel given by K (x,x')= k(x, Idy. However, with suitably adjusted constants in the assumptions, our results transfer directly to the more general RKKS & induced by the more general operator-valued kernel
k(I,2')= == k(z,z'yF
where T:y + is any posirive-semidefnit self-adjoint operator. The precise characterization of the adjusted constants is given by (37) Section 4.
An important property of G is that it is isometrically isomorphic to the space of Hilbert-Schmidt operators between H and ) [3] Corollary 1]. Similarly to the scalar case we can map every element in G into its ग eeuuivlleneee class in (z( and we use the shorthand notation [F] [F], (see Definition 6 in Appendix A for more details).
'This follows from [49 Lemma 4.33]. Note that the Lemma requires separability of X, which is satisfied since assume that X' is second countable locally compact Hausdorff space.

---

Theorem 1 (vRKHS isomorphism), For every function F e g there exists a unique operator C' E (2(H.)) such that F(.) Cé(+) y with (C))s,(H.))) |Fllg and vice versa. Hence == (2H,)) and we denote the isometric isomorphism between S2HH,)) and G as follows that G can be written as G (F F Co()), C' S2HH)))).
2.1 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-valuce regression is
E(F) E [ JEnylu-- 1o)
for measurable functions F y. The analytical minimizer of the risk over measurable functions the regression function or the conditional mean function F, (z(x)))) given by
F.(x) E[Y |X= = Ss y x x
Throughout the paper, assume that B[[|]])] +00, i.e., the random variable Y is square- integrable. Note that this implies F. (²) 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 y of high infinite dimension. We pick G a hypothesis space of functions in which to estimate F.. Note that by Theorem [ minimizing the functional & on G is equivalent to minimizing the following functional on (2H.))).
E(C) E B[IY= CX)()
It is shown in 38 Proposition 3.5 and Section 3.4] that the optimality condition be written
C. S2(H,))),
where Cyx == F[Y @ o(X)) is the cross-covariance operator. As discussed in full detail by [3)] the problem (5) can be formulated as a potentially ill-posed inverse problem on the space of Hilbert- Schmidt operators. As such, regularization is required; introduce regularized solutions of this problem in Section through the classical concept of spectral filter functions.
2.2 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, G) and the misspecified setting (F, & G). We review the results of [51] and [17] in constructing scalar-valued interpolation spaces, and [30] in defining vector-valued interpolation spaces.
By the spectral theorem for self-adjoint compact operators, there exists an at most countable index set I, a non- non-increasing sequence (J4) O, and family (es)ser e H. such that ([ea))se) se/ is an orthonormal basis (ONB) of ran 1,- S L2(T) and (H, 1/2 es) is an ONB of (ker x+ _ H. and we have
Real-valued Interpolation Space:
Lx Eutsseillaanlee
Cx =
Ex=Eule
Emd Eudisreemmn ief
(6)
For 0, the a-interpolation space [51] defined by
a/2 [ei] (ar) e E2(1)= s L2(T))
[H]
Σ kef
a.p;
equipped with the inner product
Σ
Ea,b,
3E1
Tel
[7H]
*We recall that the bracket [.] denotes the embedding that maps f its equivalence class (+() L2(T).
5

---

for (at)ier: (b)) E (I). The a-interpolation space defines a Hilbert space. Moreover, (ng
forms an ONB of [M] and consequently [H]] is a separable Hilbert space. In ( [e.] tel
the following, we use the abbreviation || laa == [[7)
Vector-valued Interpolation Space: Introduced [30], vector-valued interpolation spaces generalize the notion of scalar-valued interpolation spaces vRKHS with kernel of the form (
Definition 1 (Vector-valued interpolation space). Let k be real-valued kernel with associated RKHS and let [H] be the real-valued interpolation space associated to H with some a O. The vector-valued interpolation space [g] is defined (refer to Remark for the definition of Nb
[g] == v (S2([H)) ,3)) F= (CC, Ce S2 (2((())))))
The space [g] a Hilbert space equipped with the inner product
(F (C, S.(((()))))))
(
where C= (F) For a 0, we retrieve [F = [F | [[]sss((t(((())))))))
Remark (Interpolation space inclusions). Note that we have F. L2(x:)) since Y L2(P:))
by assumption. Furthermore. for a, 117 Eq. (7)] imply the inclusions
[g] [ [9] L2(x:)).
Under assumptions Iho andd with X being second-countable locally compact Hausdorff space, [9] = ()( if and only if H is dense in the space of continuous functions vanishing at infinity, equipped with the uniform norm [31 Remark 4].
Remark 4 (Well-specified versus misspecified setting). We say that we are in the well-specified
setting if F- [g] In this case, there exists F such that F. F a-almost surely and |F.]| || = =I i.e. F. admits a representer in G (see Remark in Appendix When F. e [[]} for B 1, F. may admit such representation and are in the misspecified setting, as [9] s [9]
Definition I and Remarks and motivate the use of following assumption on the smoothness the target function: there exists > and constant B 0 such that F. [g] and
|| F. ||
B.
(SRC)
We let C. := (F.) S2
SRC directly generalizes the notion of so-called Hölder- 34 and allows to characterize the misspeci-
type source condition the learning literature 66 fied learning scenario.
2.3 Further Assumptions
In addition SRC
we require standard assumptions to obtain the precise learning rates for kernel learning al algorithms. We list them below. For constants D2 0 and p (0, 1] and for all i T,
#4 S Dzi-1/p
(EVD)
For constants D1, D2 O and e (0, 1) and for all i 7,
D S μ4 S D2
(EVD+)
EVD) and (ED++) are standard assumptions on the eigenvalue decay of the integral operator: they describe the interplay between the marginal distribution π and the RKHS H (see more details in (7). (EV++) is needed in order establish lower bounds on the excess risk. Note that have excluded the value p= from (EVD+); 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 77).
For a E [p. 1]. the inclusion 10.00 [H]] - Toxe (T)) is continuous, and 3.4 > 0 such that
- I14jo=La S A.
(EMB)
Property (EMB) is referred to as the embedding property in 17 It can be shown that it holds if and only if there exists a constant A 2 0 with Σiel (x) Theorem 9]. Since assume & to be bounded, the embedding property always hold true when a =
A2 for r-almost all x e X [7

---

Furthermore, EMB implies a polynomial eigenvalue decay of order 1/a, which is why we take 2 p. (EMB) IS not needed when we deal with the well-specified setting, but is crucial bound the excess risk in the misspecified setting.
Finally, we assume that there constants o, R> 0 such that
11lu- B3p(e dy) -glo2
(MOM)
satisfied for r-almost all x E X' and all q 2. The (MOM) condition on the Markov kernel p(2, dy) is Bernstein moment condition used to control the noise of the observations (see 6 17 for more details). If Y is almost surely bounded, for example || yy s You almost surely, then (MOM) is satisfied with a R 2Y. It is possible prove that the Bernstein condition is equivalent to sub-exponentialiyy. see 38 Remark 4.9].
3 Saturation Effect of Kernel Ridge Regression
The most established way of learning F. is by kernel ridge regression (KRR), which can be formu- lated as the following optimization problem: given a dataset D {(2,, 9:)) independently and identically sampled from the joint distribution of X and Y.
F == arg min
I - F(a:) + Σ 1-1
FeB
TI
where > the regularization parameter. The generalization error of vector-valued KRR is expressed as Fx F.,, and controlled in different norms: see [1] for an extensive study. We recall here simplified special case of the key results obtained in this work. In the next Theorem, S, are inequality up to positive multiplicative constants that are independent of n.
Theorem 2 (Upper and lower bounds for KRR in the well-specified regime). Let Fx be the KRR estimator from (7). Furthermore, let the conditions (EVD+), (SRC) and (MOM) be satisfied for some O<p5 and 2 1. Then, with high probability we have
1 La(m:)) S. n
minlP.21i
min(3.2)
for a choice Xn 0 Rto):
and furthermore for all learning methods (i.e., measurable maps) of the form D FD.
[[[Fb] F0 2 n n Pीr.
Theorem 2 shows the minimax optimal learning rate for vector vector-valued valued KRR for 3 [1,2]. However, when / 2, the obtained upper bound saturates 34p creating gap with the lower bound. This phenomenon referred to as the saturation effect of Tikhonov regularization, and has been well investigated in deterministic inverse problems [40] In the case where ) is real-valued, [2) prove that the saturation effect cannot be avoided with Tikhonov regularization. Below, we give a similar but generalized bound on lower rates for the assume that X' is a compact subset of R.d We give the proof in Appendix [B]
that ) is Hilbert space. For this result only,
Theorem 3 (Saturation of KRR). Let X be a compact subset of Rd Let X = M(n) be an arbitrary choice of regularization parameter satisfying Mn)) - 0 as n from We assume that the noise is non-zero and bounded below, iee. there exists a > O, such that
and let Fx be the KRR estimator
dy) 2 2
satisfied for alamosst all x e X. assume in addition and for this result only that is Hölder continuous (see Definition 11 in the appendix), i.e., k e C (X x X) for O e (0, Suppose that Assumptions (VD++) and (SRC) hold with p e (0, 1) and 2 2. For 2 0, for sufficiently large O, where the hidden index bound depends T, with probability greater than 1 - there exists some constant e₁ > such that
E
[[[[
EI [II...,
In 2 nnn 22.
7

---

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 3 clearly demonstrates that the learning rate from vector-valued KRR cannot reach the information theoretic lower rate given in Theorem
As discussed above, (2 propose a similar lower bound in the real-valued case, and we now highlight two fundamental differences with [29] 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 output our setting. Second, we adopt different and simpler approach in proving the lower bound, since there are a number of issues with the proof of [29], both in the treatment of the bias and of the variance. For detailed comparison with the earlier work, and an explanation of the differences in our approach, please refer to Remark in the Appendix.
4 Consistency and optimal rates for general spectral algorithms
Regularized population solution: Our goal is to regularize (5) in such way that we get a unique and well-defined solution that provides good approximation to F.. We first recall the concept of a filter function (i.c., a function on an interval which is applied on self-adjoint operators to each individual cigenvalue via the spectral calculus, see (16), that will allow to define regularization strategy. One may think of the following definition as a class of functions approximating the inversion map 1/2 while still being defined for 0 in reasonable way. We use the definition given by 34 but equivalent definitions can be found throughout the literature.
Definition 2 (Filter function). Let s R* A family of functions gx : [0) [0, oo) indexed by A E A is called filter with qualification 2 0 if it satisfies the following two conditions:
1. There exists a positive constant E such that, for all X E
sup sup 2 x "esxxgxxi (x()) ae[0,]] ==0x=")
(8)
2. There exists a positive constant up such that
sup sup sup Irx(z)l=">~" s Sup.
with
rx(x) == 1- 119)(x)
(9)
ae[0.p] ArA xe(
Below, we give some standard examples which are discussed by e.g. 19 5 in the context of kernel regression with scalar output variables, and in 2 for the vector-valued case. variety of additional algorithms can be expressed in terms of a filter function.
Ridge regression. From the Tikhonov filter function gx(x) (x A)-1, we obtain the known ridge regression algorithm. In this case, we have E = p Wp 1.
2. Gradient Descent. From the Landweber iteration filter function given by
gu (z) = (1- for k 1/2, &
i=0
we obtain the gradient descent scheme with constant step size т > O, which corresponds to the
population gradient iteration given by FE.1 := Ps- - -VE Fx) for l E N. In this case, we have E 1 and arbitrary qualification with wp = whenever 0 < p S and wp = p otherwise. Gradient schemes with more complex update rules can be expressed in terms of filter functions as well (39 32 34]
Kernel principal component regression. The truncation filter function (x(x) -1 2 A] yields kernel principal component regression, corresponding to hard thresholding of eigenvalues at truncation level X. In this case we have E wip 1 for arbitrary qualification p.
Population solution:
Given filter function 9Λ. we call gx (Cx the regularized inverse of Cx. We may think of the regularized inverse as approximating the pseudoinverse of Cx (see e.g. 16 when X 0. We define the regularized population solution to
Cx == Cy (HH,)),,
= CxO())
(10)
"Cx) ) is defined with the rules of spectral calculus, Definition 9 in the Appendix.

---

The solution arising from standard regularization strategies leads to well-known statistical method- ologies. We refer [66] for the background on filter functions in classical regularization theory.
Empirical solution: Given the dataset D = {(ri, U:) the empirical analogue of (10) is
Cx== = (xx))(xx);
Fx == C2+())
(11)
where Cyx, Ox are empirical covariance operators define as
xx = Σ Σ o(x;) =1
Oyx == 1 = y 8 o(x;).
@ d(z))
Note that 11 is the regularized solution of the empirical inverse problem
Čxx= =Õx,
Ö (2H,,)),
which arises as the optimality condition for minimizers on 9 of the empirical analogue of (3) given by (F) : Σx l1y: F(x:) [3: see Proposition in the Appendix for proof. For the vector-valued kernel given in (2) is well-known that Fx can be computed in closed-form for the ridge regression estimator-even in infinite dimensions [47]. For general filter functions, extended representer theorem is given by [2] the context of finite-dimensional multitask learning: this approach works in infinite dimensions well. We give the closed form solution based on 2 below (we include the proof Appendix D.I.
Proposition 1 (Representer theorem for general spectral filter). Let (K)i, xx),, isj i denote the Grum matrix associated to the scalar-valued kernel k. We huve
1 K K2 ER"
(x)x) Σ (x),
a(x)= = 9 72
(k.)
1sisn. (12)
Example 1 (Conditional integration). Consider now random variable 7. taking values in a topolog-
ical space 2 on which define second RKHS H'' s R2 with kernel 8: 2 2 R and canonical
feature map vb : + H', 2 r E(z,)). The conditional mean embedding [47 20 is defined as
= E[v))] X-
x X.
We immediately see the link with vector-vane vector-valued valued regression with (Z) and y H'. The conditional mean embedding allows us compute the conditional expectation of any element of H'. Indeed, using the reproducing property, for f e H'' we have for all x X,
R[S(Z) | X x] (S. X ==))e
6 and an estimate of the conditional mean embedding F, with a spectral algorithm Fx as in Eq. (TI. and substituting the formula in Eq. (12), we obtain IE X = x] (J. (x())
Given a dataset {(x,, 242)))) )
f[](x), where (fz); 1sisn.
Learning rates: We now give our main result, the learning rates for the difference between [Fx] and F, in the interpolation norm, where Fx and Fx given by (TOp and (IT) based gen- eral spectral filter satisfying Definition?? [ The proof is deferred to Section C in the Appendix.
Theorem 4 (Upper learning rates). Let Fx be an estimator based a general spectral filter filter with qualification p 2 O. Furthermore, let the conditions (EVD). (MMB), (MOM) be satisfied with 0 p 1. With 0 2 S 1, if (SRC) is satisfied with y 2p, have
1. in the case 3 p S a, let An - ((m)) log" (m) for some > 1, for all T > log(6) and sufficiently large n 2 1, there is a constant J independent of n and T such that
[[
2
log"
is satisfied with P" -roobbbbiility not less than 1
TT
'Note that this induces dataset D {(xi, (z where identify 31 (22))

---

2. in the case p+ a, let X, =n(n for all (6g(6) and sufficiently large 1, there a constant > independent of n. and T such that
[[ - P. s Jn 3
is satisfied with p pproobbbailitty not less than 1 6
Theorem 4 provides the upper rate for rector-valued spectral algorithms. In particular, in combination with the lower bound in Theorem P we see that vector-valued spectral algorithms with qualification @ achieve an optimal learning rate when the smoothness /3 of the regression function is in the range (a-p. 2p]. For algorithms with infinite p 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 35 30J, while not suffering from saturation. For Tikhonov regularization, where p L, the rates recover the state-of-the-art results from [31]. Finally, we point out that obtaining minimax optimal learning rates for 3 < a p still remains challenging even the real-valued output scenario. Note however that for large variety of RKHS, is arbitrarily close and obtain optimal rates for the whole range (0, 2p]: we refer to 31 54 for a detailed discussion.
We provide proof sketch for Theorem The key technical challenge in extending the results of 31 to spectral filter functions lies in the analysis of the estimation error. The estimation error in
n-norm is bounded as ||[Cx - -X]I sa(tm]).>> s 3 (Cx - -Cx)
-x) C X.A
(see Eq. 37 in
(.H3))
Appendix C.3 We rely on the fact that IdH = (xx)((x) +x) +rx(Ox) +
(see Definition 2 to obtain
the decomposition Ō₁- Cx= - (x(x)> -Caa((xx) which yields two terms be controlled,
(a) s,,))) $ 16x (ss (S(
(arx(Ox)
X.A (2(H.))
(1)
(in)
To control term (I), we use the definition of the filter function an (Definition (Xx))(((x))xx==) $ 1. Thus it suffices to control the term [ Oxxx)
2 to obtain that
S2(HD)
E {(x,, vi) (Is. where E(x; y) = (y Cxé(x)) @ C (xx). We proceed by bounding E[l X) (HH)))) for 1, and then Bernstein's 's inequality to derive the upper bound
on [ ((xxx-Cxxx) (II) | (ttrr
To control term (II), Lemma in Appendix C.1
shows that
The term the right side is bounded in prior work on H-H
scalar-valued spectral method, and we refer the reader [54] Theorem 16). The results of Theorem are then obtained by choosing regularization parameter À = >(n) to optimally trade off approximation and estimation errors.
Conclusion
In this work, we have rigorously explored the theoretical properties of vector-valued spectral learning algorithms, focusing on their performance infinitediimensional output spaces. We first proved the saturation effect observed in vector-valued kernel ridge regression, highlighting its limitations in exploiting additional smoothness in regression functions. We then presented upper bounds on the finite sample risk for general class of spectral learning algorithms, demonstrating their minimax optimality across various scenarios, including misspecified learning settings.
Our results open avenues for further research, particularly in developing more efficient implementa- tions for practical use high-dimensional machine learning problems such as causal inference and functional data analysis.
Acknovledgement: Dimitri Meunier, Arthur Gretton and Zhu Li were supported by the Gatsby Charitable Foundation.
10

---

References
[T] J.PP. Aubin. Applied Functional Analysis. John Wiley & Sons, Inc., 2nd edition, 2000.
[2] L.. Baldassarre, L.. Rosasco, A. Barla, and A. Verri. Multi-output learning via spectral filtering. Machine Learning, 87(3):259-301, 2012.
[3] F. Bauer, S. Pereverzev, and L.. Rosasco. On regularization algorithms in learning theory. Journal of Complexity 23(1):22-7,, 2007.
[4] A. Berlinet and C. TThmas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Springer, 2011.
[5] G. Blanchard and N. Mücke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18(4):971-1013, 2018.
[6] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
[7] A. Caponnetto, C. A. Micchelli, M. Pontil, and Y. Ying. Universal multi-task kernels. Journal of Machine Learning Research, 9:1615-1646, 2008.
[8] A. Caponnetto and Y. Yao. Cross-validation based adaptation for regularization operators in learning theory. Analysis and Applications, 6(02):161-188) 2010.
[9] C. Carmeli, E. De Vito, and Toigo. Vector valued reproducing kernel Hilbert spaces of integrable functions and Mercer theorem. Analysis and Applications, 4(04))377-408, 2006.
[10] C. Carmeli, E. De Vito, A. Toigo, and V. Umanitá. Vector valued reproducing kernel Hilbert spaces and universality. Analysis and Applications, 8(01):19-61, 2010.
[11] C. Ciliberto, L. Rosasco, and A. Rudi. A consistent regularization approach for structured prediction. Advances in Neural Information Processing Systems, 29, 2016.
[12] C. Ciliberto, L. Rosasco, and A. Rudi. A general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research, 21(1):3852-3918 2020.
[13] E. De Vito, L. Rosasco, and Caponnetto. Discretization error analysis for tikhonov regular- ization. Analysis and Applications, 4(01):81-99, 2006.
[14] Diestel and Uhl. Vector Measures. American Mathematical Society, 1977.
[15] R. Dudley, Real Analysis and Probability. Cambridge University Press, 2nd edition edition, 2002.
[16] H. W. Engl. M. Hanke, and A. Neubauer. Regularization of Inverse Problems. Kluwer, 2000.
[17] Fischer and I. Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal Of Machine Learning Research, 21:205-1 2020.
[18] J. Fujii, M. Fujii, T. Furuta, and Nakamoto. Norm inequalities equivalent heinz inequality. Proceedings of the American Mathematical Society, 1 118(3):827-830, 1993.
[19] L. L. Gerfo, L. Rosasco, Odone, E. Vito, and A. Verri. Spectral algorithms for supervised learning. Neural Computation, 2877):1833-1897, 2008.
[20] Grünewälder, G. Lever, L. Baldassarre, S. Patterson, A. Gretton, and M. Pontil. Conditional mean embeddings regressors. In International Conference on Machine Mearning, pages 1003--18100 2012.
[21] S. Grünewälder, G. Lever, L. Baldassarre, M. Pontil, and A. Gretton. Modelling transition dynamics in MDPs with RKHS embeddings. International Conference on Machine Mearning, pages 535-542, 2012.

---

[22] T. Herdman, R. D. Spies, and K. G. Temperini. Global saturation of regularization methods for inverse ill-posed problems. Journal of optimization theory and applications. 1481))1164-19 2011.
[23] J. Jin, Y. Lu, J. Blanchet, and L. Ying. Minimax optimal kernel operator learning via multilevel training. In The Eleventh International Conference on Learning Representations, 2023. 20233
[24] H. Kadri, E. Duflos, P. Preux, S. Canu, A. Rakotomamonjy. and J. Audiffren. Operator-valued kernels for learning from functional response data. Journal of Machine Learning Research, 17(20):1-54, 2016.
[25] V. Kostic, K. Lounici, P. Novelli, and M. Pontil. Sharp spectral rates for koopman operator learning, Advances in Neural Information Processing Systems, 36, 2024.
[26] V. Kostic, P. Novelli, A. Maurer, C. Ciliberto, L.. Rosasco, and M. Pontil. Learning dynamical systems via Koopman operator regression in reproducing kernel Hilbert spaces. Advances in Neural Information Processing Systems, 35:4017-4031, 2022.
[27] S. Lanthaler and N. H. Nelsen. Error bounds for learning with vector-valued random features. Advances in Neural Information Processing Systems, 36, 2024.
[28] Y. Li, W. Gan, Z. Shi, and Q. Lin. Generalization error curves for analytic spectral algorithms under power-law decay. arXiv preprint urXiv:2401.01599 2024.
[29] Y. Li, H. Zhang, and Q. Lin. On the saturation effect of kernel ridge regression. In The Eleventh International Conference on Learning Representations, 2023.
[30] Z. Li, D. Meunier, M. Mollenhauer, and A. Gretton. Optimal rates for regularized conditional mean embedding learning. In Advances in Neural Information Processing Systems, volume 35, pages 4433-4445, 2022.
[31] Z. Li, D. Meunier, M. Mollenhauer, and A. Gretton. Towards optimal sobolev norm rates for the vector-valued regularized least-squares algorithm. Journal of Machine Learning Research, 25(181):1-51, 2024.
[32] Lin and V. Cevher. Optimal distributed learning with multi-pass stochastic gradient methods. In International Conference on Machine Learning, pages 3092-3101. PMLR, 2018.
[33] J. Lin and V. Cevher. Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms. Journal of Machine Learning Research, 21((47):1-63, 2020.
[34] J. Lin, A. Rudi, L. Rosasco, and V. Cevher. Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces. Applied and Computational Harmonic Anal- ysis, 48(3):868-899) 2020.
[35] A. Mastouri, Y. Zhu, L. Gultchin, A. Korba, R. Silva, M. Kusner, A. Gretton, and K. Muandet. Proximal causal learning with kernels: Two-stage estimation and moment restriction. In International Conference Machine Mearning, pages 7512-7523. PMLR. 2021.
[36] Mathé. Saturation of regularization methods for linear ill-posed problems in Hilbert spaces. SIAM journal on numerical analysis, 42(3):968-973, 2004.
[37] M. Mollenhauer and P. Koltai. Nonparametric approximation of conditional expectation opera- tors. arXiv preprint arXiv:2012. 12917, 2020.
[38] M. Mollenhauer, N. Mücke, and T. Sullivan. Learning linear operators: Infinite-dimenss
regression well-behaved non-compact inverse problem. arXiv preprint arXiv:2211.08885, 2022.
[39] N. Mücke, G. Neu, and L. Rosasco. Beating SGD saturation with tail-averaging and minibatch- ing. In Advances in Neural Information Processing Systems, volume 32, 2019.
[40] A. Neubauer. On converse and saturation results for Tikhonov regularization of linear ill- posed problems. SIAM Journal On Numerical Analysis, 34(2):517-527, 1997.
12

---

[41] J. Park and K. Muandet. A theoreic approach to kernel conditional mean embeddings. Advances Neural Information Processing Systems, 33:21247-21259, 2020.
[42] R. Singh, M. Sahani, and A. Gretton. Kernel instrumental variable regression. Advances in Neural Information Processing Systems, 32, 2019.
[43] R. Singh, L. Xu, and A. Gretton. Kemel methods for causal functions: dose, heterogeneous and incremental response curves. Biometrika, 11 111(2):99-516, 2024.
[44] S. Smale and D.-X. Zhou. Shannon sampling and function reconstruction from point values. Bulletin of the American Mathematical Society, 41(3)279-305,, 2004.
[45] S. Smale and D.-X. Zhou, Shannon sampling Connections to learning theory. Applied and Computational Harmonic Analysis, 19(3):285-302, 2005.
[46] S. Smale and D.-X. Zhou. Learning theory estimates via integral operators and their approxima- tions. Constructive Approximation, 26(2):133-172, 2007.
[47] L. Song, J. Huang, A. Smola, and K. Fukumizu. Hilbert space embeddings of conditional distributions with applications to dynamical systems. In International Conference Machine Mearning, pages 961-968, 2009.
[48] B. K. Sriperumbudur, K. Fukumizu, and G. R. Lanckriet. Universality, characteristic kernels and RKHS embedding of measures. Journal of Machine Learning Research, 12(Jul)2389-24410, 2011.
[49] I. Steinwart and A. Christmann. Support Vector Machines. Springer, 2008
[50] I. Steinwart, D. R. Hush, and C. Scovel. Optimal rates for regularized least squares regression. In COLT, pages 79-93, 2009.
[51] I. Steinwart and C. Scovel. Mercer's theorem on general domains: On the interaction between measures, kernels, and RKHSs. Constructive Approximation, 35(3):363 417. 2012.
[52] Weidmann. Linear Operators in Hilbert Spaces. Springer, 1980.
[53] Y. Yao, L. Rosasco, and Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26(2):289-3155 0005)2289-1110077777 2007.
[54] H. Zhang, Y. Li, and Q Lin. On the optimality of misspecified spectral algorithms. Journal of Machine Learning Research, 25(188):1-50 2024.
[55] H. Zhang, Li, W. Lu, and Q. Lin. On the optimality of misspecified kernel ridge regression.
In International Conference Machine Learning, pages 41331-4133 PMLR, 2023.
13

---

Appendices
The appendix is organized as follows. In Section A we give additional mathematical background and notations. In Section B we give the proof of Theorem and provide technical comparison of our proof with [29]. In Section C we prove Theorem Finally, in Section D we provide auxiliary results used the main proofs.
A
Additional Background
A.1 Hilbert spaces and linear operators
Definition 3 (Bochner Spaces, [4). Let H be a separable Hilbert space and probability measure on X. For S & co, (X, n; H), abbreviated Lg(T;; H). is the space of strongly Fx - Fn measurable and Bochner q- q-integruble functions from X to H, with the norms
If (x(11) S11. 1.1 du, 159000
Ifll = inf (C =0 -}-
Definition 4 (p-Schatten class, e.g. (521). Let H, H' be separable Hilbert spaces. For 1 S co, H H', is the Banach space of all compact operators C from H to H' such that [C'Is,(H..)) := (C)) is finite. Here (ax(C)) sel lle, is the sequence space norm of the sequence of the strictly positive singular values of C indexed by the at most countable set For p= 2, we retrieve the space of Hilbert-Schmidd operators, for p = we retrieve the space of Trace Class operators, and for p +00, 1. 1.1ls (H. corresponds to the operator norm IH-H*
(H, H'), H'),,, abbreviated S,
Definition 5 (Tensor Product of Hilbert Spaces, M.. Let H, H' be Hilbert spaces. The Hilbert space H @ H' is the completion of the algebraic tensor product with respect to the norm induced by the inner product (x1 @ 22113, @ x'2) H (I1, ( (21, x2) h for Fı, 22.22 & H and x4, 4,222 H' defined on the elementary tensors of H 8 H'. This definition extends to span x @ x'|r
H HH) and finally its completion. The space H @ H' is separable whenever both H and H' are separable. If (es)ier jer and [e are orthonormal basis in H and H', {er @ e, hel is an orthonormal basis in H @ H'
Theorem 5 (Isometric Isomorphism between L2(T; and S2 (,) Theorem 12.6.1 M.. Let H. be a separable Hilbert space. The Bochner space L2(;; H) is isometrically isomorphic to S2 S2(L2(T),)) and the isometric isomorphism is realized by the map & ()((L(T)))) + L2(T: acting on elementary tensors as (f y) (w fw))g).
A.2 RKHS embbedings into L and Well-speciffedness
Recall that J : H - (T( is the embedding that maps every function 7 into its m-equivalence class L2 (π) and that we used the shorthand notation [f]= = (f) for all f E H. We define similarly I. G + (2T:) as the embedding that maps every function in G into its r-equivalence class in )))
Definition (Embedding 9 into L)(T))))) Let I := Iy @ I be the tensor product of the operator Idy with the operator In (see il Definition 12.4.1.] for the definition of tensor product of operators). Ix maps every function in G into its v-equivalence class in L2( ((; y). We then use the shorthand notation [F] = (F), for all F G.
Remark 5. Let {di}jes be an orthonormal basis of y and recall that {VPi(e:])ie forms an orthonormal basis of [H]]. Let F [g] Then F can be represented as the element C= Eiet.jje aijd, @ /FLlei] in S2([H] .) by definition of [g]' with |C Eis az.. Hence defining C == EierJeJ dizd, @ Vine we huve C= C TT-e.e and
1C12
Σ oi = ||C|] +00. iejeeJ
Taking the elements identifying C in G gives representer F of F in G.
14

---

A.3 Additional Notations
In the following, we fix {dj an orthonormal basis of V, where is at most countable. Recall that {1: (1//0e
(t) sel is ONB of (ker Ix²² in H. and {[e,])ser ser is ONB of ran I in (T((T). Let (es)ar forms ONB of H. and {dr @ u 1/2 es (et.e. {dg @ Je. forms an ONB of y @ H =.
(er be ONB of ker In (with In = Ø), then 1/2 ej ial
For any Hilbert space H, linear operator T: - and scalar > 0, we define TĄ == T Alg.
B Saturation Effect with Tikhonov Regularization Proof of Theorem 3
In the following proofs quantity h, 0 depending n 1, but independent of the confidence level, is equal to o(1) if h, when n - +000
We will make extensive use of the following notation in the subsequent analysis.
Definition 7 (Empirical (zomm)) Denoted by (:,-)2,as the empirical La( norm associated
to points (x=)=-1 independently and identically sampled from the distribution of X, defined as, for any f.ge H.
(f.g)2. = (xx s -0xx - -
This induces an inner product on H. with associated norm,
1112,, = ff:f)2, n f(z))
1-1
Definition 8. Fix a E X and X > 0. The regularized canonical map is defined as
= Ox)))))) H.
Recall from Eq. 11 that the ridge estimator Fx defined Eq. 77 can be expressed as
Ć2 (Cx)
where in Theorem we focus on Tikhonov regularization where ga ga(x) (x) (xr + A)-1. In that setting
have
A
(z) ==
(13)
Proof of Theorem Since 3 2 2, F. [g] [g]] therefore F, has representer F in G such that F, F æ-a.e. (see Remark 5). and by Theorem [ F(.) C.(-), with C (2,,))).. Define the eπrors E; 3/ C) 1,.... that are i..d samples with the same distribution as Y (x)). By assumption E [|e| |x] o² and by definition E [e XJ = 0. By Eq. (13 we have
(Õx) == - Cx -XCx
15

---

The following bias-variance decomposition is the essence of the proof. In the following derivation we abbreviate S₂ (L22(T)))) S (2()::)) to L2 and ;1:...;J to In save space.
E [[[[A]] F.
En -x
I
Σ 31 e ((x)))
Ox -
12
Σ (C((1.) ((x())) -
1
-Cra (cx)+
Σ 40 (CxAA(())))
1
[[rr (0x)]]ss,
1 n
Σ
[ /3 0i ] ((:
x2 [x0|[0xx>)]]
-[[(xx)aa))) (xx) 2 (2(m))
The second term is a lower bound on the variance while the first term is lower bound on the bias. Bounding the Bias term. The idea is to first show that the population analogue of (rCCxxllss
can be bounded below by non-zero constant. We can then bound the difference between the empirical and population version of [[[Cxx x.
[[CCxt)]ls (((L()))))) using concen- tration inequality. By Lemma 1 for X 0, there is a constant e> (see Lemma for the exact value of e) such that
[[[Cx*)]]] (L(L(())))) 2 cc>00 0. )
Furthermore by Lemma] 2 there a constant Co > (see Lemma 2 for the exact value of co) such that for any 2 log(4), with probability at least - -e for n (CoT) (4+2p) and 1 2 À 2-p, have
||
|[( MI ( = =7)
Therefore, under the same high probability,
[[COr) leads to our final bound on the bias term, for a constant p2 2 and for sufficiently large n 2 1, where the hidden index bound depends on have
2 cc- (0))
[[Cxxxa]l
) 212
(14)
Bounding the Variance Term. Using the norm from Definition 7 we have the following chain of identities.
[(x10(1))) (e) = o²
Σ
fe (x)(()))))))))))) dT(x)
n² m
(15)
= Sx (x)) (z)
o²
Therefore it suffices to consider fx 10 x,,, (2,
4 and Lemma 5 we obtain that for 1 2 À n 2** with probability at
Combining the result of Lemma
least 1 - 6e for 2 (co7)*** 4+2p the following bounds hold simultaneously for all x e X:
| (Oxt -x M ||| $ sTo(1)
[[,
2 | 11 2 -T((1)
3 | (1) S sTO(1).
(1,
16

---

Fix x é X. Definition
Using the algebraic identity - = (a (2b (a (a b)), and recalling that by
If c
we deduce
11
$1 (Oxt) - k(1,)((r))) >/ -10 (Oxa - -xX)) + +2110xak(r;))
(ro(1)(T(()) + 2 112m,)
Using Definition
lggain, this reads
|(xx)k(a,))) -10x (,.KKa.>12222/033MM: - -To(1) + ( 112m.))
We have
1 MC,
)1E,, (110x, +o(1)) (V)())(V)L[CC))MM (
Hence,
|(xx)(<>)))1 2,x (CC + ro(1)
MC -TO()
-r((1) /
By Lemma
fxx (1ll =
Furthermore, by Jensen's 's inequality,
2 (ICCAAM))))))())))d((aaa
Recall from Lemma 16 that
C12 & S S22X
Therefore we have
fx (1. /22221
fx k(z, M1l dT()) c1.27
Hence
1122 x- - To -T(()) fx 11xx dx())
C1.2 (0 A -700(1)
2
Combined with Eq. 115 it leads to final bound the variance term, for constant P2 0 and for sufficiently large n 2 1, where the hidden index bound depends on T, we have
o² Σ E[
P2 (m)) ndP
(16)
n?
Putting it together. We are now ready to assemble the lower bounds on the variance and on the bias. For fixed confidence parameter log(10), for sufficiently large n O, where the hidden index
17

---

bound depends on r. with probability at least 1 - 10e", we have by Eq. 14 and Eq. (6), that for X(n) satisfying A 215
B
[ F. (n (in...,, pi p2n 12p
where Pl. P2 have no dependence Recall Young's inequality, for 9 satisfying r +9 =1 we have for all a, b 0,
a a+b2riquat
We apply Young's s inequality with --1 pp p) and q 2/(2+ + p), there exists a constant C1 > such that
pi + P2n x 2 ci (A7) (A cIn पंン
To conclude the proof, let À = X(n) be an arbitrary choice of regularization parameter satisfying
X(n) O. We have just covered the case 29 Section B.4].
n z4p and the case X S
z is covered by
Lemma 1, For any À s and Ce S2H,H,,), with C + S2(ran S S y we have
[[coxt]]ls
E dy klEj
Hi (ms + 1)2
0.
with auj (dj, CyTres) ie I,jeJ.
Proof. Recell the notations of Section A.3 Define {asz (ein f jeJ such that 0zy == (dj, C CyTreily for 1,j and aij == (dj, Cê:ly for 1', jj fj J. Then, on one hand, since C' S2 (H,.)),
C= Σ andd @ (Viies) iET,jEJ
Σ andd Z. iel'
On the other hand,
OX = E(u + X) @ (VPies) + +--1 Σ
é &
se1
tel
Therefore, noting that = T-a.. for all i I', we have,
[CC
Σ
ais(m + 1) @ (VHre,++ +
Σ
Cgj dy aē
X
ieT.jeJ
ieJ
Σ ag
d [e.].
teT.jeJ
p4
Therefore the (2(Iz(T).)) -norm can be evaluated in closed form using Parseval's identity,
[[cor\alss,
Σ JEL,EJJ
Σ teT.jeJ
2
A4
(p= A)2
dg
(1=+1)2'
where we used that (dy & (eiJ)jettae is orthonormal in y & (T), and s 1. The right hand side has no dependence on À n. Furthermore, under assumption (EVD+), pu for all e I, therefore the right hand side term equals zero if and only if a, = 0 for all i I,j e J. Since by assumption C' + S2 (ran V,), the right hand side is strictly positive.
Lemma 2. Suppose Assumption (ED)) holds with E (0,1). Let C S2(H,)) such that [C] e {2(({]],))) There constant co O such that for any log( (4), with probability at least (4+2p)
1 1 4e. n 2 (CoT) (4+2)( and 1 2 A2n n 21,, we have
||I {,(()())))))))) 3
||CC 1 s
s1))(1)
We have co := Sn m
/2, 13) where C, defined in Lemma 16
i is the notation for "not being orthogonal to".
18

---

Proof. Using the identity - -B- we obtain
Cx,- - -xxx-xx)xxx
We apply Lemma 22 with 7 =0
-
(Cx- Cx) So (a(L)(F)))))
((x
S2(H.))
c
cxt
S2(H.))
H-#
1 (xx
|
(17)
H-H
H-
We consider each of the four terms in line (17). The last term is bounded above by and the first bounded above by X [C))s,(H.))) By Lemma 20 applied with 8 1/2, we have for the second term
box
C
s $1(cx, Cx
#-H
Then, by Lemma 18 for log(2), with probability at least 1 - 2e for Vnd
(Tx/max(JV)))))) 1), we have
Cx, H-# $2
Since Since.N(A)) S S c2,1 by Lemma and À 1, suffices to verify that À satisfies
Vnλ 8TH max ( 132-
Since n Tom by assumption, we deduce the sufficient condition n 2 (T+0)2(2+)), where op i= 8K max
2T, ( 1}.
We bound the third term using Lemma 16 33 For T 2 log(2), with probability at least 1 2e-T, we have
- Ox 1
(xx-
4n Es
2x
76-7
3n
n,2
where we define
2x (N2 + 1)
Ea == log
Cx H--H
By assumption À A2n sip. We thus have
142p nd 2 n 4+2p
and
nd² 2 n nair.
On the other hand, since 12 A2n bo using Lemma 16 we have
Es s log 82(02IA*+11)
C H-H z log 2(02,1 + 1) thc
2(221+
P_ logn.
s log
+ 2 2+p
1x
The first term does not depend on n, and the second term is logarithmic in n. Putting everything together with union bound, we get bound on [17). With probability least 4e for n 2 (Co7) (4+7)(4+2p)
(4+ we have
46 0.5eg 3n 21p
2 P n. 2+p
[[c(Oxa--C - -xM & I[CIIs.c..))
To(1)
The derivations in the proof of Lemma I show that
4s X
[COX
= Σ
d 2 [e:],
sel jel
19

---

with asy == Ciiesy. I.J J. Note that since [C] (((()))))) we have
[[ |[CTI3,.((N))))
Σ jttjeJ
andd @ (Vite)
Σ
+00.
16 JeTjeJ Ps
(2())))))
Hence,
e [[C]] ((MP))))) < +00. (18)
||
Σ
di
# (1s X)2
S
Σ
iel jeJ
sel ieljjeJ
14
Using the equality a² - == = (a- () b) and the reverse triangular inequality, we obtain the following bound, with probability at least 4e for (CUT) (4+2p)
(cuT)(
||[CC - ||C <|[[((x'x - -x (IIccx(a]lsstaannn ((Ccs)alsssc)))))))))))))
sTO(1) (2|lcc
- -
STO(1) ( +o(()) =7²o(1),
where in the second last line we used Equation 18
Lemma 3. Fix x E X and fa,> as in Definition For r 2 llo(()), with probability at least 1 2e (note that this event depends x),
11, I[ s 1 1[
5TK²
322n'
Proof. We start with
1f S skIfa,xlx $ x²xー1
We apply Proposition 3 to fa. with M = x For 2 log(2), with probability at least
1
TT
11L - I1 s 1 I1laa)ll
57k²
3X2n
Lemma 4. Suppose that X is a compact set in R.d and that k CX x X) for O (0, 1] (Defi- nition 11 Assume that 2 2 n 2ip. With probability at least 2e it holds for all x X simultaneously that
bo 112,
3 M(x )122, (m) ro(1))
|oxt,((a,)) )
||[ [
Proof. The proof follows (29 Lemma C.11]. As we use different notations and tracking of constants, provide similar proof in our setting for completeness. By Lemma 24 there exists e-net F g K.A 5 H with respect to || Joo such that there exists a positive constant with
F s c(Xe)=
for to be determined later. Using Lemma and union bound over the finite set F, with probability at least 1 -e_7, it holds simultancously for all f F that
5(7 log log((
Ilfl,,, - I[[
[[f
(19)
312n
20

---

We work in the event where Equation (19) holds for all f F. By definition of an e-net and Xxx, for any x X, there exists some f F such that
1C - s,
which in particular implies that
x kxx )lllz(m))))))))))))))))))))))))) (1)
Since ||xx ((, S 2-1 using the algebraic identity d² 62 (a-b) (a ()), we obtain
- - (2x22)++
(xx) - <(2x 21= E).
We therefore have,
ICx1>((Z))) 12, 1fll + 222x2
3
5( S( (o)()))(F))
$ [[]
+
2
3r2n
3
5( + log(1 nm
$
(I,
+ -2(22x2> +c).
3X2n
We now choose
and bound the error term. Recall that 12 1
24, therefore,
n
5( log(
5( + Fog((
22<22 + +)
n
pラp 2 2k 200
3X2n
3
n
$
5k?
(r log(ct-
* 24 )
- +
-hz 2 2
2p
1 1
3
n2
= ro()).
Lemma S. For 1 X2 n 24,, with probability at least 1 - Te (co we have for all x E X simultaneously
| (xx
To(())
(20)
where co is the same constant as in Lemma
Proof.
7
|
(Cx (Cx -x (Cx
s c
#
O (Cx -x)
I kz
H-H
We already saw in the proof of Lemma 2 that the first term is bounded by and there is a constant co 0 such that for 2 log(2), with probability at least 1 2 for 2 (Cor) < the second term is bounded by /2. For the third term also saw in the proof of Lemma that for log(2), with probability at least 1 2e T, we have
x- |
-
An?C8
2n?Es
-
X.A
3nd
nd²
21

---

where we defined
2x (N) +1) e- e C
Es log
Finally, the fourth term is bounded above by A k. Note that the bound on the fourth term is independent of I, so it holds simultancously for all æ X. This is in contrast with the setting of Lemma 4 where for each fixed x: X corresponds 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 the proof of Lemma As in the proof of Lemma since
element in the 6-net of JF for which
1 12A À 2 n 2tp, we have
E6 log 2(02,1+1)
P_ logn.
H-H Cx C
2 p
In the bound on Es above, the first term does not depend on n. and the second term is logarithmic in Putting everything together by union bound, with probability at least 4e" for (cor) 4-22p
we have
| O -Cx
To(().
L
Remark 6 (Comparison to (29). We explicit the differences between proof strategy and the proof strategy of [29].
Scalar versus vector-valued: lower bounding the bias in our case require us to accommodate for the vector-valued setting (see Lemma
New proof of the bias: we lower bound the bias through Lemma 2 while 29 obtain the lower bound in Lemma C.7; however the proof of Lemma C.7 implicitly uses the equality the operator norm, see Eq. (69) (29) and the preceding equations.
|A~ ||| -1, with |
It holds that |A-'l ||||- but |A I ||A|1 may not hold in general. We therefore develop new proof for this step, leading to Lemma
New proof of the variance: we lower bound the variance in Lemma 5 while (29] lower bound the variance in Lemma C.12; show Eq. (20). [29] use covering argument involving NKC,, 1- Iu, c) (Lemma C.10). However, close look at the proof of Lemma C.10 (last inequality of the proof) reveals that X+>;
Ai_ was mistaken for h+h,
_ and plugging the correct
term in the proof would lead to a vacuous bound. As explained in the proof of Lemma we
therefore develop a proof that is free of a covering number argument for this step.
C Learning rates for spectral algorithms
To upper bound the excess-risk, we use decomposition involving the approximation error expressed as Fx and the estimation error expressed as Fx- Fx.
[[ - F.I1, s [1[ Fx]ly + [[FA] - F.ll,,
where Fg the empirical estimator based on general spectral regularization (Eq. (II) and FA, is its counterpart in population (Eq. (1)). Note that this is different decomposition than the Dias-variance decomposition used in the proof of Theorem
The proof structure is as follows:
1. Fourier expansion C.I
2. Approximation Error
3. Estimation error
22

---

C.1 Fourier expansion
Recall the notations defined in Appendix A.3 The family {dz]jeu is an ONB of V, the fam- ily (u hieer is an ONB of (ker + and the family (ereer is an ONB of ker I such that u (rr)ier forms an ONB of H. Furthermore, recall that {14 9/2 [ex]]a an ONB of
(1: 112 e)) iel
[H] B 220. 0.
Lemma 6 (Fourier expansion). Suppose Assumption (SRC) holds with B 0. By definition of the vector-valued interpolation space and by Theorem 5
we have
F. agdlee, Then, we have the following equalities with respect to this Fourier decomposition.
Oej = (Fe, dF
|
(21)
Vel.jEJ
iel.jeJ Pi
1. The Hilbert-Schmid. operator Cx S2(H,)), Eq. TO), can be written
Cx
Σ agjax (1:) /r,d3
(p:)
(22)
ieT.et
2. The Hilbert-Schmidt operator (Cyx - Ox0x) S2(H,)) can written as
(Cvx-CCCx) Σ aisra(us) + /
/na @ vutes)
(23)
ieT,eJJ
3. The Hilbert-Schmine operator Cyx S2(H))) can be written as
Cyx
Σ
anjii dg /use Cx
(24)
jEI,EEJ
Proof. We first derive the Fourier expansion of Cyx.
Cyx Ex,y [Y s (X)]
Ex (F) ((X)
(25)
Ex
Σ dsfe:(X)d e
jET,jEJ
Ex
Σ a:ddy 2
Σ
(X) Vise je((x)
iEI,JEJ
Vi Ex Ex(ex d, (VTTEe))
ijk
Σ
anj/Hid @ (Vpres)
(26)
it.jaJ
where in Eq. 25 used the tower property of conditional expectation and in Eq. 26 used
the fact that {[e hier forms an orthonormal system in (T)). We can manipulate Eq. 26 to derive
Eq. [4
Eaght - 2 = d, @ (cx (VTTes)
Cyx= iel,jeJ
Σ jeJ
Girl4 d2 @ /pces CX
By the spectral decomposition of Cx Eq.
O and spectral calculus (Definition 9 we have that
9x(Cx)= Σ (x() /uc @ Vuee (x) Σ 2 e,
(27)
rx(Cx) Σ (A(p)) @ V Σ E, ee. ief
(28)
23

---

where we used (0)== =1
Proof of Eq. 22 Using Eq. 26) and (27). have
C2
Σ
Oij Widy @ (Vitee))
Σ hel
(V((ee)( @ (Vikes) 91 Σ él Ø
iel,jeJ
lel'
Σ (ai (odd @ (vPReR)
(29)
8jk
Σ (1) @ (Vires) dei,eeJ
where in Eq.
29
we recall the fact that (yAreieir forms an ONB of (ker 1=) and (a) forms
ONB of ker m.
Proof Eq.
Using Eq. 26 and 28 we have
(Cxx Mxx-CxCx)
CYXPA
Σ oijy anjyVidd @ (VTice) jel,jeJ
Σ Kel
(r(lE) VPECk + Σ 0 Cx.
iel
Ean (VpRes)0sH OX. bgk
Σ
aij anj/ (C (Viree))
iel,jed
Σ A) @ (Vpse:)
iel.
Lemma 7. Suppose Assumption A and S 7 $ 1, we have
SRC
holds with 3 2 O, then the following bound is satisfied, for all
[FJII s F2 12 (n. (7-8).
For the definition of E,, see Eq.
Proof. We adopt the notations Lemma 6 By Parseval's identity and Eq. 22 we have
[FX]I |Cx
(A(TT)))) 2-7
Σ
(u)))))))) p4
sel,jeJ
In the case of y s 8, we bound gx(x:) E using Eq.
Then, by Eq. 21
[[AJ]]
s E
F..1?
ilTjjeJ 1
I-I-
In the case of > 3, we apply Eq.
to (x:))
$ E. T
obtain, using Eq. 21
again,
|[FA]I|
Σ (x)))
2- 2-(7-8)
p. n. 3
keTjee
$ (x--))
Σ p d KeljelJ
E2X
24

---

Lemma 8. Suppose Assumption (SRC) holds for 0 S 3 s 2p, with the qualification. Then, the following bound satisfied. for all X we have
(CCx- (
swp F.ls2
S2(H.))
For the definition of wp. see Eq. 99)
Proof. Recall that in Lemma 6 we used the decomposition
F.
Σ asddgLei,,
VeI.jeJ
a where Assumption (SC) implies that |F= Eng
0o. Using Eq. (23) in Lemma and
Parseval's identity w.r.t. the ONS (d, 14 1/2 deteee in S2(H.)), we have
|cox- S2(H)))
Σ (1) 2)
jel
Σ iel.jeJ 14
((x))
|| I. |l sup (ui)
iel
F. au
Lemma 9. Suppose Assumption (RC) holds with B 2 O, then for all X> O, have
| (Cxx (HH.))
sB BB @
H-H
where [Fa1|3 B < co.
Proof. Recall that Lemma 0 we used the decomposition
F.
Σ
set seljef
where |FF1133 -Eij
< B² co. Using Eq. 24 Lemma 6 and C2 = Cxxxx(Cx), we have
Cara (cx) x.1
Σ Eanpi dj 2 Vases Ox ((x)
(2(H.))
(s(H.)))
B c 9nl OX
(Cx))
H-
where we notice that the S2 )) norm of the first term is exactly the 3 norm of F,, which is given by B. Recalling that Cx, Cx self adjoint, we prove the final result by taking the adjoint and using that an operator has the same operator norm as its adjoint.
C.2 Approximation Error
Lemma 10. Let Fy, be given by Eq. 100 based on general spectral filter satisfying Definition
with qualification p 2 O. Suppose Assumption (SRC) holds with parameter B 2 0 and define
3, = m8n 2p), then the following bound is satisfied, for all X and 0 S 7 8p-
[[F}] - F.1,, - S 3 1E 800
25

---

Proof. In Eq. 10 we defined Fx(-) = Cxo(+). On the other hand. in Lemma 6 we obtained the
Fourier expansion of Cx leading Eq. 22 Thus we have for π alalmost all æ
Fx(x) = Σ (x)(s)())d)))()))))
ie ieT.eeJ
Therefore,
F. Σ
- (10))1a0(14))d
Σ (ggx(14)d
ieI,jEJ
iel,jeJ
Suppose 3 2p, using Parseval's identity w.r.t. the ONB {djun [ of [g]", have
[FX]-F.l F.1
Σ
'2 (
1/2
ieI,jeJ
2
Σ
(14)
iel jed p.
Σ
(2) 7
is jaJ 14
w x 8->
Σ
iel jeJ P
F. 12 2
9-7
where we used Eq. 9 in the definition of filter functtin, together with 0 s 8 s 2p and s Y s B which taken together implies that 0 s A-1 $ p. Finally, if 3 2p, then since [g] s [G] we can perform the last derivations again with 8 2p obtain the final result.
C.3 Estimation error
Before proving the main results we recall two embedding properties for the vector-valued interpolation space [ (Definition 1.. The first embedding property lifts the property (EMB) defined for the scalar- valued RKHS [H] to the vector-valued RKHS [g]
Lemma 11 (Low-embett embedding property Lemma 4 (3I). Under
EMB the inclusion operator To...
[9] + Lo y) is bounded with operator norm A.
Theorem 6 (L.g-embeddin property Theorem 3 (31). Let Assumption EMB
be satisfied with
parameter (0, 1]. For any E (0, the inclusion map
Ism [ + L (T;))
is bounded, where qa,8 == 20 a-B
The Lo-embedding property was first introduced in the scalar-valued setting in [55] and then lifted to the vector-valued setting by (3I) Its role to replace a boundedness condition on the ground truth function F,. We now explain how the Ly embeddinnn property can be combined with Assump- tion (EMB) and truncation technique.
Lemma 12. Recall that is the marginal measure of X on X. For 2 O, define the measurable set Or as follows
Ω4 (x & X: [IF. $1)
Let g O. Assume that F. e (T;)), In other words, there exists some constant e2 > such that
| [L (Jx (4. = =c +00,
Then we have the following conclusions
1. The n r-measure of the complement of can be bounded by
((x let) < c
26

---

2. Recall that { are ii.d. samples distributed uccording to n. If nā for q < then we can conclude as follows. For a fixed parameter T > O, for all sufficiently large n, where the hidden index bound depends qq and T. we have
Ten (Nt-ff (2)) 2012216 1-
Proof. The first claim straightforward application of Markov's inequality, follows
Ex
[1F,(1))
({ (2)) (1) > ()
ta
t
To show the second claim, first evaluate the probability that there exists some z; 's that lies outside 2z
.n (0 f2 $ (21) = =1 x (2 l4))
π [a, E 22))
$ -
1
t
c n
S
where in the last inequality we used Bernoulli's inequality, which states that for 2 1 and 0 S x $
(1 x rz.
By assumption t n for some fixed g q: 0. We thus have
T (u" (xx 24)) s egn "n SET for sufficiently large where the hidden index bound depends and
We adapt 31 Lemma 5] to the spectral algorithms setting.
Lemma 13. Suppose Assumptions (SRC) and (EMB) hold for some O S.S B s 2p, with the qualifica- tion, then the following bounds are satisfied, for all 0 1
[[Fx] - F.12, 12 A max E, wp
F X0-
(30)
[[FA]]| s 22 [F min (0-1),
(31)
Proof. We use Lemma 11 and Lemma to write:
[[F)]] s A [F[[[F S A² Fa.Fllanaoo oy X (a-1).
This proves Eq. 33 To show Eq. (30. the case 3 s a we use the triangle inequality, Eq. and À S 1 to obtain
31
[[F]] F. x 1o [[[FJll 00
( AF F. 1A)x 3
In the case 3> a, Eq. 330 is consequence of Lemma the assumption 0 s s 2p).
and Lemma 10 with 7 = a (here we use
[[ - 1. < [3] - F.1l3 s A' 12x-a s F/ Aw F. 22 x-00
We adapt [54] Theorem 13] to the vector-valued setting.
27

---

Theorem 7. Suppose that Assumptions (EMB). where p the qualification, and p S 1. Denote, for I.....7.
EVD.
MOM and SRC
hold for 0 s 3 s 2p,
& = (( Ue) ((v: - -(o(()))))))) ((x))) X X
for t 0,
Ω {x e X | (x) $t}
Then for all T 2 with probability at least 1 2e",, we have
Σ f, e (
(2(HL)
c3 ())
S c c2 n + + R+
C4
Vn
where the constant from Assumption (MOM). and
4 = 2 max( op
0 8/2A
C3 8 2a
C4 8/ F. 1
where A is the constant from Assumption EMB) and E, are defined in Eq. 8 and respectively.
Proof.
We wish to apply vector-valued Bernstein's 's inequality, namely Theorem 10 We thus compute,
E [[K((X, 24) ( E 1 1(x (or @
S2(H.,)
E 24 1o c oxx)
(x -fo | (V- dy(eedd))))
(32)
First we consider the inner integral, by Assumption MOM
f dp(a, dy) 2- (, ly F. (z) (x) + || (x) - 11)) dp(r,dy)
mlo m2R2(2 m- 2 [F)()) F.(x)
Plugging the above inequality into Eq. 32 as well as introducing the shorthand,
h CZ)))
we have
( S (2R2 m-2 f( 1 dTT(())
E
(33)
m-
hh mm [x(x)) (x)) (x)
ja.
We bound term
33
using Lemma and Lemmal
with 1 1. We have,
s (AX-3)))
Therefore we bound term 33 as follows,
mlo²(2 ( (1al(idd(()) s mlo²
12AR m-2
Ay AG
28

---

If B 2 a, by Assumption EMB
|F s Al la s F.ls.
Hence by Lemma
13
[[ - Foll s () oooo Amax(F,u,)) |1a)1 3 $ SA(1 max(maxaaaaaa (F,up))) 1. 1
1lad
If 3 < a, by Lemma
13 we have for x-almost all r 9
F.. (z) - st+ |[ +t+
st+ AE
Therefore, for all 8 [0,
((F. [Fx]) Xen, ( st+ A(1 Ma "=) x(t,)).
Using Lemma
with 1, we have,
2
T -
(AX (AX+)) I. [F (2())))
(x, A)A
m-2
2A²
F.. [.-[FA]l 2at
2x(1, A)A
m--
2A²
Sm!
| [F.-[FA]122 2a
A
Putting everything together,
m 2(R+ x(1, (4.A1)4))
24a
[[I5(X, (2 sm!
(2)
1IF (2 aa
A
We now apply Theorem 10 with
L 2(R x(t,A))
A=
2A
a 20 (A) + F. - [FX]] (FF)] x
We bound (FXx(]]]))))))) using Lemma 10 with =
F. [ 12(1)))) (F
The conclusion is, for all 7 2 1, with probability at least 1 - -T_ we have
1 Σ (1 24) E[g 2
n
(HH.))
24 20 No |F. (FX]]
L2(x:))
2(R + x(t,
s 2T
Vn
n\#
20
(T)()+++ + 2 F. lawa
2(R+t+ A)A
2A max wp
<4V2T
V =
nd#
nda
Lemma 14. Suppose that the same assumptions and notations listed in Theorem hoold.
1. Suppose p > a, and = मो.. For any fixed T 2 1, with probability at least 1 - suppose that the truncation level satisfies
Eo pid
then there exists constant > 0 such that
n Σ
(1 E 0.) - (XIX
sen 2
S2(H)))
29

---

2. Suppose 3+ps a,, and X at least 1 2e" suppose that the truncation level t satisfies
for some For any fixed 1, with probability
log log"(a)
I.S (2-))
then there exists a constant > O such that
E f2 e 2)- (LE(X, [xx]]
CT
log (n)
Proof. Note that Theorem yields the same conclusion as in the scalar-valued case proved [4 Theorem 13]. The Lemma then follows from the analysis for the scalar-valued case in the proof of
54 Theorem 15].
We adapt [55] Theorem 15] to the vector-valued setting.
Theorem 8. Suppose that Assumptions (EMB). (EVD) MOM and SRC where p the qualification, and p S 11.
hold for 0 S 8 s 2p.
1. In the case of B a, choosing À n 7-p for any fixed log(4). when is sufficiently large, with probability at least - -e, we have
((0xx-CA(x)- GG
S sen b
(34)
82(H)))
where e is constant independent of n, T, X.
2. In the case of B + S+pS S a, choosing X log"(n)
for some > 1. We make the additional assumption that there exists some a' a such that Assumption (MOM) satisfied for
a' < a. Then, for any fixed t log(4), when n is sufficiently large, where the hidden index bound depends on a', with probability least -e we have
12
CT
(35)
(2(H.))
log l
(n)
where is constant independent of n, T,
Proof. By assumption
EMB and Theorem 6 if a, then the inclusion map
Ia. [g] Tiga. (T:)/
is bounded, where la.9 == If B a, then by Lemma 11 the inclusion map
2n a-
I. : Tooo (T;
bounded and therefore [ is continuously embedded into (T: for any 9 1. the rest of the proof, we will use q denote go,p, unless otherwise specified. Furthermore, we will use Cn = F |F,1,,,
We first consider the case B+p> a. We can easily verify using 3 p a that the following inequality holds
1+ p p-a p+ 3
P
a-
1
2a
a,.3
Choose n where
1+ p-
+
q
2
+
We thus have
(1+ p-o p+a
Ro.8 Thus the assumptions for both Lemma 12 and Lemma 14 are satisfied.
30

---

We then consider the case p a. We now apply Assumption (EMB) and Theorem 6 to a' instead of a. We obtain that the inclusion map 1 i is bounded, where we recall that Ja is defined to be is monotonically decreasing for x 3, we obtain the inequality
20' Since z-B o'-B"
20'
2a
a a-
We choose t n Ra.0 By construction, satisfies the assumptions in Lemma 14 Furthermore, the assumptions of Lemma 12 are satisfied, with F, Ly (T,,)) and t "
Having established the applicability of Lemma 14 and Lemmal 12] let us turn our attention to proving the results of the Theorem. Denote
= (g-C(((()) (
We compute
= (C(c,:))--CGxx-xcA))bb
The + p> a case. Have
1
Σ ([{(,,))]
n1 Σ f 24 E[E(2, v) (2(H.)
n 1=1
S2(H.))
Σ (as < 22
[B[E(>, y) 1 far E 277 (ls,
We can bound the first term with probability least - by CT Iog)(n)
according to Lemma 14 By Lemma 12 with probability at least 1 e for sufficiently large n. Qg for all i [n:]. whereby the second term is zero. It remains to bound the third term, where our bound will be deterministie. Using Jensen's inequality, we have,
[[[[(z, y) (x (H,))) E
[k[ ((
E
[(v - Cid(x))
s AA * - 24)
where in the third line we used Lemma and noise term using triangle inequality.
17
We first split the second term into an approximation error
[[I - Cxx())) & 9blssss
(x (x)
We bound the first term using the tower property of conditional expectation,
E [[I(v Cxd(x)) fx 1,] E, [E[lly Cxo(x) (x] 2.)
s Ex E - 1 0.)
σ (I (2)
oct
19
where in the third inequality we used Assumption (MOM) with y 2, and in the fourth inequality we
used Lemma [2 We bound the second term using Stuchy-Schwer inequality and Lemma I0 with y= 0,
P(x & 22) | MaM 2
F
Therefore, using Lemma 12 we have,
oc
c t
[ y) fa 2 (SND) $ -
| |
(36)
19
31

---

We now plug in Axn 1251571 34p, Recall that by construction 1>> nē. Thus,
A 1-4 4 $ ni in ( < n " 2t n2 s
X | sn 2 atrp <n 2 कककक -
We've therefore proved inequality (34)
2. The 3 x+ps s a case. We proceed similarly to the [3 + ++p> case. We have,
n Σ & ([E(<,,))] 1=
n
Σ 1:
(o l2) B[E(E, V)(
$2(H.)))
P1 m-
(2(H()
1
Σ
f,1 22
n
S2(H.))
B[((x,)) 1 fo 0
We can bound the first term with probability least 1 2 by log" (m)
according to Lemma 14 By Lemma 12 with probability at least 1 e for sufficiently large n. e Ug for all i [n]. whereby the second term zero. We bound the third term by Eq. (36). We now plug in
A x
Recall that by construction t nē. Thus,
log (m)
A 29 $ n
n
n
n
2m
log"
<
(ogg(n)
S
log"(n) (n)
-8 3c
8-a 2 t c S Sn
n log"(n)
20
n
log (og)(n)
We have therefore proved inequality (35).
We adapt
[54
Theorem 16] to the vector-valued setting.
Theorem 9 (Bound of estimation error). Suppose that assumptions (EMB). EVD), MOM and
SRC) hold for s 3 $ 2p. where p is the qualification, and a For S S S 1, with y S 3,
1. In the case of B + p > a, by choosing À x n Ztp, for any fixed t 2 log(4), when n is sufficiently large, with probability least 1- -e we have
[[C' - -X]I S ST 82
74p
where is constant independent of n, T.
2. In the case of 3 + P o, by choosing À x log sufficiently large, with probability least 4e we have
for any fixed T 2 log( 4), when n is
S-y
[[Ć - [ -1 $ cT2
n log (n)
where e is constant independent of n,
Proof. Firstly, establish the applicability of Lemma 19
The 3+ + p> case. Have n der, hence
Sep-o
nd n Pey
whereas using s ||Cx IH- for sufficiently large n, well Lemma 16
8 log (2) |xx |2 + CC H-
8842 log(oog((eee.1 PP) s 8 [log( ()0(4))221) P
log(n)
8+p
32

---

Therefore, for a fixed T > O, for all sufficiently large n, Eq. (40) in Lemma 19 is satisfied.
The S+ps a case. Have x
log"(n) (n) for some 0 > I, hence
nx 2 log (n)
whereas similar to the p> > case, we ahve
Bo"Tlog (A) CCx 1 +
$ SA*T 1og(44c2.1) log log o
[Cx CCIIN- M-H
(n)
Therefore, for a fixed T > 0, for all sufficiently large n. Eq. (40) in Lemma
19 is satisfied.
We thus conclude for all (0,1), with probability 1 2e_T, Eq. simultaneously.
and are satisfied
We exploit the following decomposition
|[['x -5xx-sclllsssso -C]llss((H))))) ((x-c2)
((HH)
(c. -0 (2) (()
C2.
x
| 71-31
XA
(2(H.))
$ (c. C)) C)
14: 14 +
..p (2(H.))
ieN
(c. - -.)
31-
(37)
X,
(HH.)))
where in the first inequality used Lemma 22 in the third inequality used Eq. 442 and in the last inequality we used Lemma 21 We consider the following decomposition
O - C2 - č2 Cx (Cx9x + (Ōx))
(exx-Cxxx)pp (Cx) Cara (êx).
Hence
[[O: - cx CIlIss((H)) $ 1187" ((T)² + (IT)2),
where
(1) - -xxx R. (6x)
S2(H.))
(IT) Cara (Cx) (S,(H))))
Term (I). The high level idea is to bound (I) by exploiting the first axiom of the filter function 8 where gx (Cx) intuitively regularized inverse of Öx, by grouping it with Čx,
(T) < - Cxxx) c X
(Crx-cxxx)
c C 7
||0xa0
m
(.(H))
$ (Orx- - -xxxx
V3 sup (1+ (1 =[0.a]]
(5(H))))
<(( - -xxxx S3(H4)))
22.E.
where the second inequality follows from Eq.
We consider the following decomposition
(xxx==cxx))33)/ sa(H))
22
((Orx- (axxx)-(Crx-xo) (Cyx-
(a
(Cxx (2(H.)
+2
33

---

We bound the first term by Theorem 8 and the second term by Lemma This yields, for 7 log 4),
with probability at least 4e for some constant which does depend on n, T, A,
[(xxx- S2(H.))
F2
CT P+p
8+p2a
+
log"
(c+ 2/
13 )n
p+p2a
(c 2 13302
p+pca
log" (n)
where we used that > 1. So collecting all the relevant constants together, we can write the upper bound of term (I) as follows: with probability at least 1 4e " for some constant c' > 0 (different from the e before) which does not depend on 72, T, A, we have
2 dtp
B p a
(T) (
2a
8 p <a a.
lng
Term (II). Using Lemma 9 we have
(IT) s Ca
H
The second term is the same as the scalar-valued case, which is bounded in Step 3 of the proof of [34] Theorem 16]. We define
3 13-1 { 2 .1) Fasp 8-1 1-1 min(2.3) 9-11
A := 32 max
By the proof of [54 Theorem 16], we have, with probability at least 1 6
(11) s 6Bw,EX BT
1. Case 3+p2 In this case À x n 3... We note that for B > 2, A function of n can be written
min(0.9)
A x n 2pry))
Note that
min(3,3)
3
1/ P
min(3,3) -1
>
2)
4
2(3+ p)
2
B+
2
Hence
A $ 20/4p
Therefore have shown that there exists some constant c 0, independent of n, X, such that with probability at least TT for sufficiently large n,
[[[Ca - CX]I sd" Tn 2
We have also shown that there exists some constant 0, independent of n, X, T, such that with probability at least - Ge_7, for sufficiently large n.
S a. In this case B s 1, and X log" (x) 2. Case s+ps
[[ C Callssa(Hm) SC'T
log"(n))
Putting together Lemma and Theorem 9 have proved Theorem 4
34

---

D Auxiliary Results
D.1 Spectral Calculus, Proof of Proposition lnn Empirical Solution
Definition 9 (Spectral Calculus; see 16 Chapter 2.3). Let H be Hilbert space. Consider R. - R and a self-adjoint compact operator A H H admitting a spectral decomposition written as
A Σ Aph4 @ hy
We then define g(A): as
((A) Eg(A:) @ h4
SE1
whenever this series converges in operator norm.
Proof of Proposition 7
We define the sampling operator S: IR" H and it dual S H + E",
S R H,
S H R f f (f(x:))
a
a Σ ((((2;)
We can verify that Ox = n 55 and K = S. Let Y = (w:) R We have, for all x X,
Fx(x) Exx(X)
1 Σ y 8 (1x)) ga (xx))(((
Σ yi ((x;)) (n
H - (n (S)))
S
(38)
YT -9 -9 S (X)
(39)
Y -9x(n 'K) (X)
y gg KK)k.-
To go from 38 to 339
make the following observation. Consider the singular value decomposi- tion of the compact operator S, there is m & n such that
m $
Σ
oifi 0e
where (ex)i (fi); are orthonormal sequences in R and H respectively, We then have
SS
Σ o.li St. SS= o 0e,
Therefore, deduce
01 13 & E (
S5
S* ga
Σ
Σg
71
Vose. fslfosi)
8
m
ΣΦ 91
0 Vole, 8
35

---

Similarly.
S
6 (EVors))))
9N
S =
Σ 91
71
5
9 9x
Voe f(lenee)R.
4.
= Σ9 94
Voe @ fi
Hence we have proved
SS*
S S
S 9X
=
S*
as desired.
Proposition 2. Any minimizer F of
1 n
(F)
- Σ
11y F(x:)
n2 i-1
on 9 must satisfy
Ōxx= ÖÕx,
C SxH.)).)..
where F(.) Co(-).
Proof. By Corollary it is equivalent to solve the following optimization problem S2(H,)),,
1 Σ y C n Recall for a Hilbert-Schmidt operator L S2(H, we have
min C+82(H.))
(L, a b) (HH)) = (a, Lb)y.
Using this, we re-write the objective as an inner product in S2HH,
1u Co(x:)) _ Σ (())) (()))s)) (C, (Co(x;)) @ ((2;))s,(H))> (C.((.))
constant
n1
n
-C Cyx)s, + (C, (C,CCx)s.(H..))
Taking the Fréchet derivative with respect to C and setting in to zero, we obtain the following first order condition
Čyx= COx
D.2 Properties Related to Assumptions EMB) and EVD
Lemma 15 (Lemma 13 17). Under T-almost all x e X,
EMB the following inequality is satisfied, for X > 0 and
[[xx ATdx) k(x, >)
SAX
Definition 10 (l-effective dimension). For 2 1, the leffeective dimension Mi : (0, 00) [0,00) oo) is defined by
M(A)= = Tr Tr Σ
The 1-effective dimension is widely considered in the statistical analysis of kernel ridge regression (see (6).
[32 (34], [77). The following lemma provides upper and lower bounds for the
|-effective dimension.
36

---

Lemma 16. Suppose Assumption EVD) holds with parameter p (0, 1], for any X e (0, 1], there exists a constant C221 O independent of such that
N((A) c2,1X
furthermore, Assumption (EV+)) holds with parameter pe (0, fo for any A (0, 1), there exists constant C1,2 > independent of X such that
C &N(A) C2,12
The proof can be found in (99 (Proposition D.I). but as the proof is incomplete we provide a full proof for completeness. This allows us detect that the value p 1 in Assumption (EVD+) is compatible with the assumption of bounded kernel (see Remark below).
Proof.
D2
M(A
Σ
(I
is monotonically increasing)
121
D2
Ai
x+
D2
D2 positive and decreasing)
$
dx
(i++
D2 Ait/D
D2 + Ax
D2
dy
(y 1e
D2 + y
XP
D2
$ X
+
dy
D2 + y
Let us now consider the integral. Let us first consider s 1 <,,
J,
D2
dy s D2 S Myyte ddy
D2 + y
D22 p p
Therefore, using S 1, we can take 02 = 1+ D22 P. The remaining edge case = 1, covered by 117 Lemma 11] with C, = ||xx (and therefore p l),
(10)) [[Cx1s For the lower bound, we proceed similarly. For p (0, 1)
Ni(A) 2 Σ 21
D
(x+ x+ X
x
is monotonically increasing)
D1 Xir
D
D
dx
(i+
is positive and decreasing)
D1 + Ax
Di + Ael/o
D1
dy
(1 2x
Dj +
D1
P
y
dy
D
=
D1
p
D1+
+1
l-p
Therefore, take C1,1
Di
Remark 7. We note that Assumption k is bounded (Assumption 3). Indeed, suppose that μ4 D all i 2 1. Recall that {[e4]]a forms an orthonormal set in (T( ..).... By Mercer's theorem,
(ED++ with p = is not compatible with the assumption that
x²2 S Mc, Em. S (e(x))
Σn; 2 D Σ 5 = 400,
i21
12
12
which leads to contradiction.
37

---

Lemma 17. For any E [1,2], the following equality holds,
fx | x.
k(z,
dx())=
2-1
In particular for I 1,
fxl (x3M(2)))) dr(x) -N(x))N(()))
H
for 2,
fx |Ixx Mll dx(x)= N2)
Proof. Fix X. Since k(x,,)) E H. and (1 (). ies everywhere
(1
is an ONB of (ker I=)* " we have that -lmmsst
k(x,)) (k(2,,) 1, 1/2 ? Euce(ree
sel
This is Mercer's Theorem [51] On the other hand, alammsst everywhere,
Cx X.X
E(u + A) (Vpree) @ (vite;).
sel
Therefore,
((,,K( [C 1/2 X.X
Σ Pi tel
(M+ Ayr (x)(e,
and by Parseval's 's identity, using that (mg (m(²-0) [es]lier is ONB of [H]]-]
||[ |[ Σ
E( Mi
[(1 e)(x)²
Gel
M4
Therefore,
Sx (12 Σ Me x Jx (()))dd(())= -MO),,
where we used that ([e;))se forms orthonormal set in (2)))).
D.3
Concentration Inequalities
The following Theorem is from 17 Theorem 26].
Theorem 10 (Bernstein's 's inequality). Ler (Ω,, B, P) be probability space, H be separable Hilbert space, and & Ω + H be a random variable with
E[[ & mmlaa m-
for all m 2 2. Then, T and n 2 1, the following concentration inequality is satisfied
1 Σ (wx) Epp
T2
L
pd (wI....,wh) s
32
0²
27
7 i=1
H
n
n
In particular, for T 2 and n 22
pr (WI)..., e 9²"
1 Σ E (w:)
EpE
24V2 T
L
)
S2E
Vn
0+
Vnl
Lemma 18. Let 2 log(2), with probability at least 1 TT for Vnd (Tx/mmxx( we have
C (x Cx #-H 22
The proof is identical to Proposition 5.4] with the only difference that in their setting K= 1.
Proof.
38

---

Proposition (Proposition C.9[29). Let iT be a probability measure on X, E Lz(T)) and If s M. Suppose we have 21......; In sampled i..dd from и. Then, for any T 2 log(2), the following holds with probability at least - -e
1
5T
3 ( S
5T
| (g))
$ 11
2
3n
2
where || 12.n was defined Definition 7
Lemma 19 (Lemma 14).
Let Assumptions
EMB
SRC and (OMM) be satisfied. For T if
and n satisfy that
Cx Iu- +
n 2 8A log
(x
(40)
|Cx IH-
then the following operator norm bounds satisfied with probability not less than -e
C X
22
(41)
0
33
(42)
HH-H
D.4 Miscellaneous results
Lemma 20 (Cordes inequality 18 Let A, be two positive bounded linear operators on separable Hilbert space H and [0, 1]. Then
||A 3" H-H $ |AAl Bl
Lemma 21 (Lemma 25
17 For X > and & e [0, 1]. we have
1" x-1
sup 120 t
We recall the following basic Lemma from Lemma 22. For 0 $ s and F e G, the inequality
30 Lemma 2].
| (,(H.))
[[F]]l,
holds, where C= (F) (2H,)) If. in addition, 7 or C 1 @ ker La is satisfied, then the result an equality.
Definition 11. X Rd be a compact set and 0 e (0, 1]. For a fanction f : X R. we introduce the Hölder semi-norm
1f(x) f(v)
[f
sup a,yye arey
| y/1
where ||
represents the usual Euclidean norm. Then, we define the Hölder space
(xx) = (f: IR [f]o,x <0o0}
which is equipped with the norm
= == x
[
[f]o.x
The next lemma is used to prove Lemma 24 below. It appears in 29 Lemma A.3], albeit the of
an erroneous equality in their proof: [lk(x,)) k(y, = k( x ky,, kkx,y)? We therefore provide our own proof of this result.
compact X Rd associated with kernel k C (X x X) for 0 (0, 1). Then, we have C (x) and
Lemma 23. Assume that H. is RKHS
[f] 10).x= & 2
39

---

Proof. For all (I.y) X and f H. by the reproducing property and Cauchy-Schwarz Schwarz inequality, If(x) f(v) = (((x,)) k(v,)),
I [[][ k(y,
Then, using &e ( x x),, we obtain
|k(x,-) k(y, li k(x,2) + k(v.9) 2k(2,)) s 2[ |x- vll" which concludes the proof.
We derive as corollary a quantitative upper bound on the e-covering number of the the set of (spectral) regularized kernel basis function with respect to the - norm.
Lemma 24 (Lemma C.10 by 29). Assume that H is RKHS with a kernel l E C (X x X) for 0 E (0, 1]. Assume that k<x,x) s x² for all x M. Then, we have that for all 0,
compact set X Rd associated
I lm. =
where K2, = depends and max' and c is a positive constant which does not depend on X, E and only NKxx, ll () denotes the c-covering number of the set K. in the norm -1loo (see 149 Definition 6. 69] for the definition of covering numbers).
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We specifically point the settings and detailed contributions of our work in both abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In describing our assumptions well as discussing our theoretical results, we specifically list our limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
41

---

Answer: [Yes]
Justification: We provide our assumptions in Section 2.3 The complete proof of our works are listed in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper does not contain experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
42

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttde//guuddeeeeeSouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
43

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics http:///wwrrppp.cppppp//////iaaa
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our paper mainly focuses on investigating the learning efficiency of spectral algorithms. We therefore believe our paper does not have any negative societal impacts. We explain how our theory can improve our understanding of various learning algorithms in the introduction which could be potential positive societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
44

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
45

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "IISvBpEF6l", "reviewer": "Reviewer_f39z", "summary": "This papers focuses on learning vector-valued functions in reproducing kernel Hilbert spaces (RKHS). The kernel in this case is an operator-valued function instead of a scalar-valued function. The papers considers kernel-based vector-valued regression with spectral regularization, which include ridge regression and kernel PCR. The contribution of the paper is theoretical: learning rates for vector-valued and spectral regularization-based regression are derived. In the case of kernel ridge regression upper and lower rates are provided. In the general case of spectral filter function only upper rates are given.", "questions": "* Section 3 focuses on kernel ridge regression (KRR). Learning rates and results on the saturation effect of vector-valued KRR have been reported in [1]. Could you make clear what are the contribution compared to [1] here? What are the main technical challenges compared to [1]?\n\n[1] Li, Zhu, et al. \"Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm.\" JMLR (2024).\n\n* Excess risk bounds for vector-valued learning with spectral filtering are provided in [2]. How these bounds can be compared to those obtained in this work?\n\n[2] Baldassarre, Luca, et al. \"Multi-output learning via spectral filtering.\" Machine learning (2012).\n\n* Theorem 4 provides upper rates for vector-valued function learning with general spectral function. How optimality is maintained in this case?\n\n* Could the results be extended to other classes of operator-valued kernels (e.g., non-separable kernels)?", "limitations": "A detailed discussion on limitations is missing.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper provides new theoretical results for vector-valued RKHS-based regression.\n* The paper is well written.", "weaknesses": "* Contributions compared to previous work should be made more clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we thank the reviewer for their encouraging review of our work. We have done our best to respond to the reviewer's questions. If we have done so, we would be grateful if the reviewer might consider increasing their score.\n\nFirst of all, the reviewer highlighted that a comparison of our results to [1] and [2] should be made more thoroughly.\n\n*Comparison to [1].* [1] only considers Tikhonov regularisation, while the present work handles arbitrary spectral regularisation. The main difficulty is applying the machinery of vector-valued interpolation spaces developed in [1] to arbitrary filter functions. We will add a proof sketch at the beginning of the appendix to highlight the terms in the bound that require new analysis.\n\n*Comparison to [2].* We highlight the differences in the assumptions that are made to obtain excess risk bounds. 1) [2] focuses on vector-valued learning where the output space is $\\mathcal{Y} = \\mathbb{R}^d$, while we handle the more general case where $\\mathcal{Y}$ is a potentially infinite-dimensional Hilbert space. This generalisation is important to study conditional mean embedding learning, a crucial step in nonparametric causal inference. 2) [2] focuses on the well-specified setting where the target function is assumed to belong to the hypothesis space, while we also handle the mis-specified setting. 3) [2] does not consider the effective dimension in their rate which corresponds to setting $p=1$ in assumption (EVD). 4) [2] works with bounded outputs, which is a stronger assumption than our (MOM) assumption.\n\nOverall, their excess risk bounds are obtained under more stringent assumptions than ours, and they focus in most of the paper on applications. In the well-specified setting, when $\\mathcal{Y} = \\mathbb{R}^d$, with bounded outputs and ignoring the effective dimension ($p=1)$, our rates are identical. Obtaining excess risk bounds under our more general assumptions requires very different proof techniques. We will add this discussion in the camera ready version of the manuscript.\n\n**Question on optimality after Theorem 4:** We realise that the conversation around optimality has been overshadowed by the fact that we did not clearly state what the information-theoretic lower bound is. Given assumption (EVD+) with parameter $p \\in (0,1]$, assumption (MOM), assumption (SRC) with parameter $\\beta > 0$, and any $\\gamma \\in [0,\\beta)$, any learning algorithm $\\hat {F}$, will satisfy (see Theorem 5 [1])\n\n$||\\hat{F} -  F_*||_{\\gamma}^2 = \\Omega_P \\left(n^{-\\frac{\\beta- \\gamma}{\\beta + p}}\\right).$\n\nOn the other hand, for an estimator $\\hat F_{\\lambda}$ with qualification $\\rho$ (Eq.~(11) in our manuscript), upper rates given in Theorem 4 of our submission satisfy the following upper bound (with the correct choice of $\\lambda$), \n\n$||\\hat F_{\\lambda} - F_{*}||_{\\gamma}^2 = O_P\\left(n^{-\\frac{\\min(\\beta, 2\\rho)- \\gamma}{\\min(\\beta, 2\\rho) + p}}\\right),$\n\nif $\\beta > \\alpha - p$, and \n\n$||\\hat F_{\\lambda} - F_*||_{\\gamma}^2 = O_P\\left(n^{-\\frac{\\beta- \\gamma}{\\alpha}}\\right),$ \n\nif $\\beta \\leq \\alpha - p$. Optimality is therefore maintained for the smoothness parameter $\\beta$ in the interval $(\\alpha - p, 2\\rho]$. In the scalar-valued setting, this recovers the state-of-the-art rates of [3]. We hope this answer clarifies the question around optimality in Theorem 4, and we will make sure to include this detailed discussion in the camera ready version.\n\n**Question on more general vector-valued kernels:** While one could consider operator-valued kernels that do not have the multiplicative structure $K = k \\operatorname{Id}$ (with $k$ a scalar-valued kernel), it seems to us that it is currently the only relevant kernel in the infinite-dimensional setting to be found in the literature (see references with applications in the introduction). We hypothesise that this has two main reasons. Firstly, such a kernel allows for the numerical computation and evaluation of the finite-sample estimators via a vector-valued representer theorem analogously to the real-valued setting, as highlighted by Proposition 1 in our manuscript. We are not aware of such results for other types of kernels. Secondly, the available technical investigations of vRKHS induced by such kernels show that critical properties like *universality* are already achieved by this type of kernel (this is addressed in Remark 3 in our manuscript), allowing for universal consistency when used in supervised learning. In theory, one may argue that such kernels are in a sense *sufficient* for vector-valued learning problems.\n\nThat being said, we believe it is possible to generalise the result to different families of operator-valued kernels. For example, in the context of vector-valued learning with Tikhonov regularisation [4] or with general spectral regularisation [5], the cited works study vector-valued regression with kernel $K:\\mathcal{X} \\times \\mathcal{X} \\to \\mathcal{L}(\\mathcal{Y})$ such that $K_x$ is Hilbert-Schmidt (hence compact). In infinite dimension, this rules out the kernel $K = k \\operatorname{Id}$ due to the non compactness of $\\operatorname{Id}$. Note that the lower bound they obtain in both works requires $\\operatorname{dim}(\\mathcal{Y}) < + \\infty$ while we do not impose such a restriction. \n\nHowever, we note that there is a technical caveat to directly transferring our results to more general kernels: we exploit the tensor product trick (vvRKHS is isomorphic to HS-operators) in order to apply real-valued arguments. For different kernels, such an isomorphism does generally not apply and it is not entirely clear if and how real-valued arguments can be used straightforwardly. This may require a new approach and  additional work.\n\n[3] Z. Haobo, et al. On the Optimality of Misspecified Spectral Algorithms\n[4] A. Caponnetto, E. De Vito. Optimal rates for the regularized least-squares algorithm\n[5] Rastogi, A, Sampath, S. Optimal rates for the regularized learning algorithms under general source condition", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ObaWXPkDkC", "reviewer": "Reviewer_U1CH", "summary": "The  submission explores a class of spectral learning algorithms for regression within the context of supervised learning using random design. The focus is on high-dimensional and potentially infinite-dimensional output spaces. The problem is framed as minimizing the risk associated with the least squares loss, over vector-valued reproducing kernel Hilbert spaces (RKHS).\n\nThe authors make several contributions: \n\n1. Saturation Effect of Ridge Regression: The paper rigorously confirms the saturation effect in ridge regression for general Hilbert output spaces. \n\n2. Convergence Rates for Spectral Algorithms: The paper provides upper bounds on the rates of convergence for a broad range of spectral algorithms even in the misspecified learning case where the target function might not be contained within the RKHS. The smoothness of the target function is characterized using interpolation spaces.", "questions": "Q1: Is the machinery with introducing vvRKHSs really necessary when functions of Hilbert-Schmidt operators are learned?  \n\nQ2: Theorem 2: Can \"with high probability\" be made more precise?\n\nminor: \n* some brackets for references are missing, e.g. p. 1, l.20, 33 and through out the manuscript \n* the references [33] and [34] are the same, also [6] and [7]", "limitations": "yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper extends non-parametric regression results involving spectral regularization to a broader setting that includes potentially infinite-dimensional output spaces. \n\n2. The authors mostly clearly explain their contributions, making the advancements in the field accessible. \n\n2.They rigorously introduce the mathematical framework of vector-valued reproducing kernel Hilbert spaces (RKHSs) and regression, ensuring a solid theoretical foundation.\n\n3. One particularly commendable aspect of the approach is the expression of the smoothness of the target function in terms of vector-valued interpolation spaces, which appears to be a natural and effective strategy. \n\n4. Rates of convergence are presented that are shown to be optimal in the well-specified case, effectively closing a gap in the literature.\n\n5. Additionally, the paper demonstrates tight lower bounds for Tikhonov regularization with a Hölder continuous kernel, proving that saturation is an unavoidable phenomenon in this context. The authors extend the results from [28] from real-valued output spaces to infinite dimensional output spaces using the same bias-variance decomposition, however with a simpler approach. \n\nOverall, the research provides valuable insights into spectral learning algorithms and their application in high-dimensional settings.", "weaknesses": "1. While the paper does close a gap in the literature, it follows the usual lines in non-parametric regression over RKHSs. The results are somewhat expected, and the approach is not actually new. \n\n2. The setting seems rather restrictive: The maps that are learned with classical regularization approaches are basically linear operators (Thm. 1) . Perhaps, the authors can state this more clearly to better distinguish between other current streams of operator learning research (in particular non-linear operator learning). \n\n3. The difference between this work and previous work [38], particularly in the well-specified case, could be explained in more detail to highlight the novel contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging feedback and their helpful comments. We have done our best to address all the questions. If we have done so, we would be grateful if the reviewer might consider increasing their score.\n\n**Weaknesses:**\n\n1. We agree, we base our investigation on the typical integral operator approach [6], making use of a variety of arguments based on available literature. In that sense, the structure of the rates is not surprising. We argue, however, that *our contribution is precisely the insight that known arguments can be transferred to vector-valued learning in a dimension-free manner* by refining a tensor product trick first used by [38,29]. This was not clear in the initial line of work going back to [6], as a trace condition ruled out infinite-dimensional product kernels. In a practical context, based on the representer theorem in Proposition 1, our work provides the first theoretical foundation for learning the conditional mean embedding with general spectral algorithms. Furthermore, it unifies the theory for kernel-based functional regression [25], which is novel in that degree of generality to the best of our knowledge.\n\n2. Thank you for pointing this out. We agree that in light of the recent interest in operator learning, we should comment on our results in this context. We note that our work can be directly interpreted as regularised (nonlinear) nonparametric operator learning: Bochner-universality shows that the vvRKHS is *sufficient* to learn all Bochner square integrable nonlinear operators. We hypothesise that, analogously to how scalar kernel regression is used to understand generalisation\nand early stopping in deep learning (for example via the NTK), our work could be a starting point for a theory of neural operator learning; although there is much theory that is still missing in the bigger picture. This seems to be a very interesting direction for future research.\n\nOur work also contains *linear* operator learning (related to [38]): in particular, when $X$ takes values in a Hilbert space $\\mathcal{X}$ we choose the scalar kernel $k(x,x') = \\langle x, x'\\rangle_\\mathcal{X}$, we recover precisely the linear setting of [38] via the vector-valued kernel $K = k \\\\times \\\\operatorname{Id}\\_{\\\\mathcal{Y}} $. The assumptions in the linear and nonlinear settings require caution, however. The standard assumption that $k$ is bounded guarantees the crucial embedding property (EMB), which only holds for almost surely bounded $X$ in the linear case. However, with the kernel $k(x,x') = \\\\langle x,x'\\\\rangle_{\\\\mathcal{X}} $ and when $X$ is bounded, *our rates apply in the linear operator learning setting without modification, and appear to be novel for this field.*\n\n3. We note that the authors of [38] work directly in the operator regression setting and do not assume boundedness of the covariate $X$, but subgaussianity. In our work, boundedness of the embedded covariates is assumed implicitly  through boundedness of the kernel $k$. In this sense, [38] is more general. On the other hand, in [38], the authors consider exclusively the well-specified setting and show rates up to $O(1/\\sqrt{n})$, as no decay of eigenvalues of the integral operator is assumed and rate optimality under these assumptions is not addressed. In contrast, our assumptions allow for optimal rates up to  $O(1/n)$ by exploiting the aforementioned eigenvalue decay, in which sense our results are more general.\n\nWe will include these discussions in the camera ready version.\n\n**Questions**\n\n1. We see the reviewer's point and argue that the vvRKHS framework is fairly general: it allows both linear and nonlinear operator learning on Hilbert spaces\nas highlighted in W2 above, but also contains more general settings where one observes covariates $X$ on a general topological space without linear structure. We agree that generally, details about the machinery of vvRKHSs could be ignored when purely focusing on the operator learning setting. Nonetheless, interpreting HS-operators as vvRKHS functions allows convenient discussions based on the existing vvRKHS literature. One may also argue that our presentation may be practical for readers with an RKHS background and applications such as conditional mean embeddings are formulated in this setting; although this is likely up to personal preference and background.\n\n2. We agree with the reviewer that Theorem 2 was introduced in an informal way. The formal version of the theorem can be found in [30] (Theorem 5). We will update Theorem 2 in that spirit in the camera ready version to make sure that what is hidden behind \"with high probability\" is correctly specified. For completeness we will add Theorem 5 from [30] in the appendix of our current submission so that the reader can have the theorem in full details. \n\nFinally, we thank the reviewer for spotting typos in the references. We will carefully proofread and correct all typos in the camera ready version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uwfpOm7gss", "reviewer": "Reviewer_R42A", "summary": "This paper considers the regression task of learning a mapping where both the input space and the output space can potentially be infinite dimensional. The authors formulate the problem setting by proposing a number of assumptions that can be thought of as the vector-valued counterparts of the standard assumptions in (real-valued) kernel regression. In the well-specified regime, the authors show that a saturation effect exists i.e. the Tikhonov regularized regression estimator is provably suboptimal. The same phenomenon is known to exist in the real-valued setting, but extension to vector-valued output is a novel contribution. Finally, the authors show that for estimators based on a class of filter functions, one can establish error rates that match the best-known upper bounds even in the real-valued setting.", "questions": "Does the lower bound for real-valued output ($n^{-\\frac{\\max\\{\\alpha,\\beta\\}-\\gamma}{\\max\\{\\alpha,\\beta\\}+p}}$) directly imply a lower bound in the vector-valued setting? If this is the case, it would be nice to state it as a theorem after Theorem 4.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written. Though the authors consider an extension of previous works where the output space is R, all relevant notions and assumptions in the current setting are rigorously defined.\n\n2. The main result of this paper addresses the optimality (at least for some set of smoothness parameters) of a class of regression estimators based on filter functions, going beyond Tikhonov regularization that most often appears in existing literature.", "weaknesses": "1. While the mathematical parts of this paper look sound, and the results appear to be novel, both the error rates and the proof techniques seem to have no difference with the finite-dimensional output setting. I haven't gone through all the proof details and it might be the case that additional challenges arise in the vector-valued setting. If this is the case, then it would be great if the authors can point to the most challenging parts of the proof with several sentences in the main part of the paper.\n\n2. The main part of the paper ends a little abruptly -- it would be better to write a final section summarizing the contributions of the paper and discussing potential future directions. The problem setting and necessary assumptions may be introduced in a more concise way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging review of our work. We have done our best to respond to the reviewer's questions. If we have done so, we would be grateful if the reviewer might consider increasing their score.\n\n**Weaknesses**\n1. The additional difficulty with respect to the scalar-valued setting is to handling the vector-valued interpolation spaces. Under the right decomposition, the vector-valued interpolation spaces allow us to reduce some terms to the the scalar-valued case while other terms require new analysis. We will add a proof sketch in the appendix to highlight the additional difficulties. \n2. We fully agree with the reviewer that a conclusion should be added. We will use the extra page given for the camera ready version to add a concluding discussion and perspective on future works. \n\n**Questions**\n\nWe believe the lower bound $n^{-\\frac{\\max\\\\{\\alpha,\\beta\\\\}-\\gamma}{\\max\\\\{\\alpha,\\beta\\\\}+p}}$ mentioned by the reviewer comes from [18]. We would first like to mention that this lower bound is obtained under the assumption that the target function is **bounded**. It was shown in [55] that this assumption is not needed. The correct information-theoretic lower bound is therefore the following. Given assumption (EVD+) with parameter $p \\in (0,1]$, assumption (MOM), assumption (SRC) with parameter $\\beta > 0$, and any $\\gamma \\in [0,\\beta)$, any learning algorithm $\\hat {F}$, will satisfy\n\n$\\\\|\\hat F - F_*\\\\|_{\\gamma}^2 = \\Omega_P \\left(n^{-\\frac{\\beta- \\gamma}{\\beta + p}}\\right).$\n\nThis result can be found in Remark 3 of [18] in the scalar-valued setting and in Theorem 5 of [30] in the vector-valued setting. The  insight of the reviewer is correct: the vector-valued lower bound can be obtained using a reduction to the scalar-valued setting. We will make sure to include this remark in the camera ready version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kqTCXfeE7T", "reviewer": "Reviewer_bQuY", "summary": "This manuscript presents the excess risk upper bound for spectral regularized algorithms whose output might belong to potential infinite-dimensional Hilbert space. Additionally, the saturation effect for a special case of vector-valued spectral algorithms, KRR, is rigorously confirmed.", "questions": "1. Just of independent interest. Consider spectral algorithms with finite qualification context (like KRR). Since there is a gap between the upper and lower bound when the interpolation index $\\beta$ is greater than $2\\rho$, we can consider the following approach to avoid this gap. Based on your misspecification results, one might consider imposing a kernel whose induced space RKHS is much 'smoother' than the RKHS to which the true function belongs. However, without the prior of the true RKHS, it is hard to pick the imposed kernel to make it 'smooth' enough. \n   \n   So, I'm wondering if there are some general approaches to avoid the saturation effect. In practical applications, when one needs to use a specific general algorithm with finite $\\rho$, this seems to be an important issue. (I understand this is a theoretical paper, but this just popped up in my head when I read the theorems).\n   \n2. Is the $Id_{\\mathcal{Y}}$ in Equation (2) the identical element in $\\mathcal{Y}$? If so, I think you should define it for completeness.", "limitations": "While the authors claim they discussed the limitation in terms of assumptions in the checklist. I don't clearly see them. But, to my knowledge, these assumptions are almost standard in the literature, except the one I raise in W2.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The manuscript is easier to follow as it provides enough detail for moving from scalar-valued RKHS to vector-valued RKHS.\n2. The manuscript established a series of well-studied properties/results for spectral algorithms and saturation effect to vector-valued output scenarios, which, to the best of my knowledge, is less concerned and studied in the community.\n3. Identify some issues for proving the lower bound in previous work [1] and provide new techniques to handle the bias and variance.", "weaknesses": "1. I find that the saturation effect, or more exactly, the lower bounds for real-valued spectral algorithms, is proved in [2], seemingly a following work of [1]. Is there any specific obstacle the authors are facing to prove the lower bounds for the vector-valued spectral algorithms?\n2. The (EVD+) condition looks weird to me. The authors state that the lower bound for the eigenvalue depends not only on $p$ but also on the running index $i$, and this is needed for the lower-bound proof. Can authors elaborate more on this? I especially note that [1], who considered the real-valued case, does not have such a requirement of dependence on $i$ in the lower bound. Is this a unique challenge present by the vector-valued setting? Or is this due to your correction for the proof issues in [1]?\n\n[1] Y. Li, H. Zhang, and Q. Lin. On the saturation effect of kernel ridge regression. In The Eleventh International Conference on Learning Representations, 2023.\n\n[2] Li, Yicheng, et al. \"Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay.\" _arXiv preprint arXiv:2401.01599_ (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1.** We thank the reviewer for their encouraging feedback and for providing the reference [Li et al. (2024)]. We were not aware of this work. We think that it may be possible to generalise the techniques in [Li et al. (2024)] to the more challenging vector-valued setting. However, the assumptions and techniques in [Li et al. (2024)] are quite different from our work. In particular, [Li et al. (2024)] Assumption 2 introduced the notion of a \"regular RKHS\", which is not a standard assumption in the literature. The examples they provide where this assumption holds are restricted to simple compact covariate spaces such as the d-dimensional torus or the d-dimensional unit ball. Hence, we would need to carefully check whether the results in [Li et al. (2024)] can be generalised to work under our weaker assumptions. If it turns out that we can generalise the results of [Li et al. (2024)] to our setting with some simple modifications, we will implement the changes in the camera ready version. If it turns out that it requires substantial technical analysis to harmonise [Li et al. (2024)] and our manuscript, we will include a citation to the approach of [Li et al. (2024)] in our work, and defer the analysis of the saturation effect of spectral algorithms in the vector-valued setting to future work. \n\n**W2.** We thank the reviewer for carefully proofreading our manuscript and bringing this to our attention. The (EVD+) condition as stated in the manuscript contained a typo. It should read instead: For $D_1,D_2>0$ and $p\\in (0,1)$ and for all $i\\in I$, \n\n$D_1 i^{-\\frac{1}{p}} \\leq \\mu_i \\leq D_2i^{-\\frac{1}{p}},$\n\nand this is the version we use in the proofs in the appendix. We will make sure to proofread the manuscript and correct the typos in the camera ready version. After correcting the typo, (EVD+) is a standard assumption used in the literature to obtain lower bounds (see for example [6]  or [18]).\n\n**Q1.** We thank the reviewer for their insightful question. In the following discussion we work under strong assumptions that allow us to precisely define what we mean by 'smoothness'. We stress that these assumptions do not likely hold in practice and therefore one needs to be careful when using the concept of 'smoothness'. We consider the setting of [30] (Corollary 2) where `smoothness' takes a formal meaning in terms of weak derivatives: $\\mathcal{X}$ is a compact subset of $\\mathbb{R}^d$, and $X$ follows a distribution equivalent to the Lebesgue measure on $\\mathcal{X}$. Let $W^{s,2}(\\mathcal{X};\\mathcal{Y})$ denote the vector-valued Sobolev space (see [30] (Definition 3)). If $F \\in W^{s,2}(\\mathcal{X};\\mathcal{Y})$, then all weak derivatives of $F$ of orders up to $r := (r_1,\\ldots, r_d) \\in \\mathbb{N}^d$ where $\\|r\\|_1\\leq s$ exist and are square-integrable. Thus, the larger $s$, the smoother the function $F$. \n\nWe emphasize that the smoothness of the function $F_{\\ast}$ as measured by the interpolation index $\\beta$ depends on the vRKHS $\\mathcal{G}$, whereas the smoothness of $F_{\\ast}$ as measured by the vSobolev space to which it belongs simply depends on the smoothness index $s$. It is shown in [30] that both notions of smoothness are linked. Let the vRKHS be a Sobolev space: $\\mathcal{G} = W^{m,2}(\\mathcal{X};\\mathcal{Y})$ (this is a vRKHS if $m > d/2$); and let $F_* \\in W^{s,2}(\\mathcal{X};\\mathcal{Y})$ for $s \\geq 0$. Then $F_* \\in [\\mathcal{G}]^{\\beta}$ with $\\beta = s/m$. Furthermore, it is also shown in [30] that the parameters of (EVD) and (EMB) are $\\alpha = p = d/(2m)$. Finally, since $\\beta = s/m$, given a qualification $\\rho$, the saturation level is $s = 2m\\rho$.\nTo simplify the discussion, we focus on the $L_2-$error rate ($\\gamma=0$). Plugging the values of $\\beta$ and $p$ in our rate in Theorem 4, we obtain\n$$\n\\\\|\\hat F_{\\lambda} - F_*\\\\|_{L_2}^2 = O_P\\left(n^{-\\frac{\\min \\\\{\\beta, 2\\rho\\\\}}{\\min\\\\{\\beta, 2\\rho\\\\} + p}}\\right) = O_P\\left(n^{-\\frac{\\min\\\\{s, 2\\rho m\\\\}}{\\min\\\\{s, 2\\rho m\\\\} + d/2}}\\right) ,\n$$\nThis confirms the comment raised by the reviewer: we should impose a kernel whose induced vRKHS is as smooth as possible, as measured by $m$. We note, however, that this reasoning would only be implementable in practice if we could actually control the smoothness of the vRKHS through the kernel. As illustrated above, this is possible if $\\mathcal{X}$ is a compact subset of $\\mathbb{R}^d$, the input data distribution is equivalent to the Lebesgue measure on $\\mathcal{X}$ and for kernels whose induced vRKHS is a Sobolev space, such as the Matérn kernel. Outside this restrictive setting, it is unclear how to interpret 'smoothness' and how we can precisely control the 'smoothness' of the vRKHS through the kernel.\n\nAn alternative approach to avoid the saturation effect when learning with a finite qualification spectral algorithm is to increase the qualification $\\rho$. This can be achieved by using iterated ridge regression [20] (Section 5.4). The qualification of iterated ridge learner is exactly the number of iterations. As a special case, we recover the fact that vanilla ridge regression has qualification $1$. This approach is popular in the econometrics literature and inverse problem literature. For example, see:\n- Section 3 of S. Darolles, Y. Fan, et al.. Nonparametric Instrumental Regression, Econometrica\n- Section 9 of Z. Li, H. Lan, et al. Regularized DeepIV with Model Selection, arXiv\n\n**Q2.** We thank the reviewer for their question. $\\mathrm{Id}_{\\mathcal{Y}}$ is indeed the identity map on $\\mathcal{Y}$. We will define all relevant notations in the camera ready version.\n\n**Limitations.** We agree with the reviewer that the assumptions we made are standard assumptions in non-parametric kernel regression. As mentioned previously, the one raised in W2 is a typo and the corrected version is standard.\n\nWe have done our best to respond to the reviewer's questions. If we have done so, we would be grateful if the reviewer might consider increasing their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l7skqhYoJK", "reviewer": "Reviewer_48mf", "summary": "The paper considers the vector-valued regression problem. Given $n $ iid samples $\\{(x\\_i,y\\_i)\\}\\_{i=1}^n$ from a distribution $\\mathcal{D}$ on $\\mathcal{X} \\times \\mathcal{Y}$, the goal is to output the estimator $\\hat{f}$ such that $\\mathbb{E}[||\\hat{f}(x)-f^{\\star}(x)||\\_{\\mathcal{Y}}^2]$ is small. Here, $f^{\\star}$ is the optimal regressor, that is $\\mathbb{E}[y \\mid x]$. In this work, the authors consider the case where the estimator $\\hat{f} $ is obtained through spectral regularization methods such as Tikhonov, hard-thresholding, and iteration filters.", "questions": "If the proof in [1] were correct or can be readily fixed, can't Theorem 3 be inferred immediately through the result in the scalar-valued case? Here is a sketch of the argument:\n\n Let $\\\\{d\\_j\\\\}\\_{j \\in \\mathbb{N}}$ be the ONB of $\\mathcal{Y}$, and $\\mathcal{Y}\\_1 = \\\\{ \\langle y, d_1 \\rangle \\quad |\\quad  y \\in \\mathcal{Y} \\\\}$ to be the subspace along the direction $d\\_1$.  Consider the probability distribution such that $y \\mid x$ is only supported over $\\mathcal{Y}\\_1$.  \nSuppose $f^{\\star}$ is the optimal regressor and $\\hat{f}\\_{\\lambda}$ is the KRR estimator. Then, we have\n\n$$\\mathbb{E}[||\\hat{f}\\_{\\lambda}-f^{\\star}||\\_{\\mathcal{Y}}^2] = \\int ||\\hat{f}\\_{\\lambda}(x)-f^{\\star}(x) ||\\_{\\mathcal{Y}}^2   p(x, dy)  \\pi(dx) \\geq \\int | \\langle \\hat{f}\\_{\\lambda}(x)-f^{\\star}(x) ,d_1\\rangle |^2  p(x, dy)  \\pi(dx) . $$\n\nNow, this is effectively lower bounding the risk for scalar-valued regression. I believe that this argument can be formalized by defining a one-to-one mapping between $\\mathcal{Y}\\_1 $ and $\\mathbb{R}$. I might be missing something here, so please correct me if I am wrong.\n\n\n\n[1] Y. Li, H. Zhang, and Q. Lin. On the saturation effect of kernel ridge regression. In The Eleventh 390 International Conference on Learning Representations, 2023.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- In the RKHS framework, the ridge estimator obtained by Tikhonov regularization is a canonical estimator. However, in Theorem 3, the authors show that the ridge estimator cannot exploit the higher-order smoothness of the optimal regressor  $f^{\\star}$ . \n\n- In Theorem 4, the authors show that other spectrally regularized estimators (for example, one based on hard-thresholding) can exploit the higher-order smoothness of the functions. \n\n- The paper also points out some inaccuracies in earlier work. I did not verify the validity of these claims, but if true, this is also an important contribution to the literature.\n\n- Overall, the paper is well-written and is easy to follow.", "weaknesses": "The proof of Theorem 4 is fully deferred to the Appendix. Given that the proof is highly technical, it would be helpful for the reader to include a high-level proof sketch in the main text of the paper. For example, some discussion of key challenges in generalizing the proof of scalar-valued to general $\\mathcal{Y}$ would be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful and helpful feedback.\n\n**Weaknesses**\n\nThe key challenge in generalising the proof from the scalar-valued case to the general vector-valued case lies in finding the right way to harmonize the technical definition of vector-valued interpolation space, and using Fourier series computations (see section C.1 in the Appendix) in order to control terms in the vector-valued setting by corresponding terms in the scalar-valued setting. Furthermore, it is essential to find the right decomposition of the learning risk. We appreciate the reviewer's suggestion to include a high-level overview of the proof. For the camera ready version, we will use the extra page allowed to include a proof sketch. \n\n**Questions**\n\nAssuming the proof of [1] was true, we agree with the reviewer that this would be a particularly elegant way to obtain our results through the result in the scalar-valued case. Below, we confirm this by providing the full argument, and discuss a subtle point regarding the noise assumption that we must consider. \n\nGiven the vector-valued problem with random variables $(X,Y) \\in \\mathcal{X} \\times \\mathcal{Y}$ and Bayes function $F\\_* (X) := \\mathbb{E}[Y \\mid X]$, we consider a modified setting where the target variable is projected along the direction $d\\_j$: $\\tilde{Y} := \\langle Y, d\\_j \\rangle\\_{\\mathcal{Y}} \\in \\mathbb{R}$. We readily see that the Bayes function associated to this setting is $f\\_* (X) := \\mathbb{E}[\\tilde{Y} \\mid X] = \\langle F\\_{\\ast},d\\_j\\rangle\\_{\\mathcal{Y}}.$ Given our vector-valued estimator $\\hat F\\_{\\lambda}$ (Eq. (7) in the submission), we can verify that $\\hat{f}\\_{\\lambda}(\\cdot) := \\langle \\hat{F}\\_{\\lambda}(\\cdot), d\\_j\\rangle\\_{\\mathcal{Y}}$ is the scalar-valued ridge estimator associated to the dataset $\\{(x\\_i, \\tilde{y}\\_i)\\}\\_{i=1}^n \\in (\\mathcal{X} \\times \\mathbb{R})^n$ with $\\tilde{y}\\_i := \\langle y\\_i, d\\_j \\rangle\\_{\\mathcal{Y}}.$ To see this, using that $\\hat{F}\\_{\\lambda}(\\cdot) = \\hat{C}\\_{\\lambda}\\phi(\\cdot)$, with $\\hat{C}\\_{\\lambda}\\in S\\_2(\\mathcal{H},\\mathcal{Y})$, we obtain, \n\\begin{equation*}\n    \\hat{f}\\_{\\lambda}(\\cdot) = \\langle \\hat{F}\\_{\\lambda}(\\cdot), d\\_j\\rangle\\_{\\mathcal{Y}} = \\langle \\phi(\\cdot), \\hat{C}\\_{\\lambda}^{\\ast}d\\_j\\rangle\\_{\\mathcal{Y}}.\n\\end{equation*}\nBy Eq. (11) in the current submission, $\\hat{C}\\_{\\lambda} = \\frac{1}{n}\\sum\\_{i=1}^{n}y\\_i \\otimes \\phi(x\\_i)\\left(\\hat{C}\\_{XX}+\\lambda\\right)^{-1}$, therefore,\n\\begin{equation*}\n    \\hat{C}\\_{\\lambda}^{\\ast}d\\_j = \\left(\\hat{C}\\_{XX}+\\lambda\\right)^{-1}\\frac{1}{n}\\sum\\_{i=1}^{n}\\phi(x\\_i)\\langle y\\_i,d\\_j\\rangle = \\left(\\hat{C}\\_{XX}+\\lambda\\right)^{-1}\\frac{1}{n}\\sum\\_{i=1}^{n}\\phi(x\\_i)\\tilde{y}\\_i,\n\\end{equation*}\nwhich shows exactly that $\\langle \\hat{f}\\_{\\lambda}(\\cdot),d\\_j\\rangle$ is the desired scalar-valued ridge estimator. A slightly subtle point is that in order to apply the results of [1] to control the following term\n\\begin{equation*}\n    \\int\\left|\\left\\langle\\hat{F}\\_\\lambda(x)-F\\_{\\star}(x), d\\_j\\right\\rangle\\right|^2 \\pi(dx),\n\\end{equation*}\nwe must impose the assumption that for $\\pi$-almost all $x\\in \\mathcal{X}$,\n\\begin{equation*}\n    \\mathbb{E}\\_{X,Y}\\left[\\langle Y - F\\_{\\ast}(X), d\\_j\\rangle^2\\mid X=x\\right] \\geq \\overline{\\sigma}^2,\n\\end{equation*}\nfor some $\\overline{\\sigma}>0$. We refer to it as assumption (1). In contrast, the assumption we currently adopt in our paper states that for $\\pi$-almost all $x\\in \\mathcal{X}$,\n\\begin{equation*}\n    \\mathbb{E}\\_{X,Y}\\left[\\\\| Y - F\\_{\\ast}(X)\\\\|\\_{\\mathcal{Y}}^2\\mid X=x\\right] \\geq \\overline{\\sigma}^2,\n\\end{equation*}\nWe refer to it as assumption (2). It is clear that (1) implies (2). We now provide an example to show that (2) does not imply (1). \n\n*Example.* Let $\\mathcal{Y} = \\mathbb{R}^2$ and $\\mathcal{X} = \\\\{0,1\\\\}$. Let $\\pi$ denote the uniform distribution over $\\mathcal{X}$.  We define the joint distribution $p(x,y)$ as \n\\begin{equation*}\n    p(x,y) = p(y\\mid x=0)\\frac{1}{2} + p(y\\mid x=1)\\frac{1}{2}\n\\end{equation*}\nwhere\n\\begin{equation*}\n    p(y = (y_1, y_2) \\mid x=0) = \\frac{1}{2}\\delta\\_0(y\\_1)1[y\\_2\\in \\\\{-1,1\\\\}]\n\\end{equation*}\nand\n\\begin{equation*}\n    p(y = (y_1, y_2) \\mid x=1) = \\frac{1}{2}\\delta\\_0(y\\_2)1[y\\_1\\in \\\\{-1,1\\\\}]\n\\end{equation*}\nWe note that $\\mathbb{E}[Y \\mid X=0] = \\mathbb{E}[Y \\mid X=1] = (0, 0)^{T}$. Thus, $F\\_{\\ast}(x) = \\mathbb{E}[Y\\mid X=x] =(0, 0)^{T}$ for $x \\\\in \\\\{0,1\\\\}$. On the other hand, writing $Y = (Y\\_1,Y\\_2)^{T}$, we have\n\\begin{align*}\n    &\\mathbb{E}[Y\\_1^2\\mid X = 0] = 0,\\quad \\mathbb{E}[Y\\_2^2\\mid X = 0] = \\frac{1}{3}\\\\\n    &\\mathbb{E}[Y\\_1^2\\mid X = 0] = \\frac{1}{3},\\quad \\mathbb{E}[Y\\_2^2\\mid X = 0] = 0\\\\\n\\end{align*}\nwhile for all $x\\in \\\\{0,1\\\\}$, we have\n\\begin{equation*}\n    \\mathbb{E}[\\\\|Y \\\\|^2\\mid X = x] = \\frac{1}{3}\n\\end{equation*}\nThis provides the desired example where (2) holds but (1) does not.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for their encouraging and positive feedback. They sparked very interesting discussions that we will use to improve our manuscript in the camera ready version. 

As a summary here are the main points that were brought up by the reviewers:

1. As the proof for the upper rates is quite lengthy, it was mentioned that it is not straightforward to understand the technical novelties with respect to previous works in the proof techniques. To address this, we will incorporate a proof sketch at the beginning of the appendix in the camera ready version.

2. Two reviewers wondered if our results could be extended to more general vector-valued kernels. We refer to our answer to reviewers f39z and U1CH.

3. One reviewer noticed that a conclusion should be added. We will use the extra page in the camera ready version to add it and address the points raised by the reviewers.

Meta-review: A theory paper on optimal learning rates for vector-valued regression using spectral regularization methods. All reviews are positive, underlining the fact that the paper is well-written, and the contribution clear, including upper and lower bounds, the treatment of the ill-specified setting and possible saturation effects. Some concern was raised as to the technical novelty with respect to the significant body of previous work in the real-valued case, but the reviewers were satisfied by the author's rebuttal pointing out in particular new technical insights in vector-valued function approximation, these points will be highlighted more prominently in the camera-ready version.
Decision: Accept (poster)