Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms

We thank the reviewer for their insightful and helpful feedback.

Weaknesses

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

Questions

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

Given 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,

$

\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}}.

$

By 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,

$

\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,

$

which 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

$

\int\left|\left\langle\hat{F}\_\lambda(x)-F\_{\star}(x), d\_j\right\rangle\right|^2 \pi(dx),

$

we must impose the assumption that for $\pi$-almost all $x\in \mathcal{X}$,

$

\mathbb{E}\_{X,Y}\left[\langle Y - F\_{\ast}(X), d\_j\rangle^2\mid X=x\right] \geq \overline{\sigma}^2,

$

for 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}$,

$

\mathbb{E}\_{X,Y}\left[\\| Y - F\_{\ast}(X)\\|\_{\mathcal{Y}}^2\mid X=x\right] \geq \overline{\sigma}^2,

$

We 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).

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

$

p(x,y) = p(y\mid x=0)\frac{1}{2} + p(y\mid x=1)\frac{1}{2}

$

where

$

p(y = (y_1, y_2) \mid x=0) = \frac{1}{2}\delta\_0(y\_1)1[y\_2\in \\{-1,1\\}]

$

and

$

p(y = (y_1, y_2) \mid x=1) = \frac{1}{2}\delta\_0(y\_2)1[y\_1\in \\{-1,1\\}]

$

We 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

$

&\mathbb{E}[Y\_1^2\mid X = 0] = 0,\quad \mathbb{E}[Y\_2^2\mid X = 0] = \frac{1}{3}\\
&\mathbb{E}[Y\_1^2\mid X = 0] = \frac{1}{3},\quad \mathbb{E}[Y\_2^2\mid X = 0] = 0\\

$

while for all $x\in \\{0,1\\}$, we have

$

\mathbb{E}[\\|Y \\|^2\mid X = x] = \frac{1}{3}

$

This provides the desired example where (2) holds but (1) does not.

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.

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$,

$D_1 i^{-\frac{1}{p}} \leq \mu_i \leq D_2i^{-\frac{1}{p}},$

and 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]).

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

We 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$. To 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

$$\\|\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) ,$$

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

An 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:

• Section 3 of S. Darolles, Y. Fan, et al.. Nonparametric Instrumental Regression, Econometrica
• Section 9 of Z. Li, H. Lan, et al. Regularized DeepIV with Model Selection, arXiv

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.

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.

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.

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.

Weaknesses

1. 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.
2. 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.

Questions

We 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

$\\|\hat F - F_*\\|_{\gamma}^2 = \Omega_P \left(n^{-\frac{\beta- \gamma}{\beta + p}}\right).$

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

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.

Weaknesses:

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

2. 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 and 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.

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

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

We will include these discussions in the camera ready version.

Questions

1. 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 as 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.

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

Finally, we thank the reviewer for spotting typos in the references. We will carefully proofread and correct all typos in the camera ready version.

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.

First of all, the reviewer highlighted that a comparison of our results to [1] and [2] should be made more thoroughly.

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.

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.

Overall, 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.

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])

$||\hat{F} - F_*||_{\gamma}^2 = \Omega_P \left(n^{-\frac{\beta- \gamma}{\beta + p}}\right).$

On 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$),

$||\hat F_{\lambda} - F_{*}||_{\gamma}^2 = O_P\left(n^{-\frac{\min(\beta, 2\rho)- \gamma}{\min(\beta, 2\rho) + p}}\right),$

if $\beta > \alpha - p$, and

$||\hat F_{\lambda} - F_*||_{\gamma}^2 = O_P\left(n^{-\frac{\beta- \gamma}{\alpha}}\right),$

if $\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.

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.

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

However, 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.

[3] Z. Haobo, et al. On the Optimality of Misspecified Spectral Algorithms [4] A. Caponnetto, E. De Vito. Optimal rates for the regularized least-squares algorithm [5] Rastogi, A, Sampath, S. Optimal rates for the regularized learning algorithms under general source condition