Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms

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.

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

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: 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$. Suppose $f^{\star}$ is the optimal regressor and $\hat{f}\_{\lambda}$ is the KRR estimator. Then, we have $$\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) . $$ Now, 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. [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.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

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.

Strengths

1. The manuscript is easier to follow as it provides enough detail for moving from scalar-valued RKHS to vector-valued RKHS. 2. 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. 3. 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? 2. 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]? [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. [2] Li, Yicheng, et al. "Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay." _arXiv preprint arXiv:2401.01599_ (2024).

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. 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). 2. Is the $Id_{\mathcal{Y}}$ in Equation (2) the identical element in $\mathcal{Y}$? If so, I think you should define it for completeness.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

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.

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.

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

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.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

N/A

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). The authors make several contributions: 1. Saturation Effect of Ridge Regression: The paper rigorously confirms the saturation effect in ridge regression for general Hilbert output spaces. 2. 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.

Strengths

1. The paper extends non-parametric regression results involving spectral regularization to a broader setting that includes potentially infinite-dimensional output spaces. 2. The authors mostly clearly explain their contributions, making the advancements in the field accessible. 2.They rigorously introduce the mathematical framework of vector-valued reproducing kernel Hilbert spaces (RKHSs) and regression, ensuring a solid theoretical foundation. 3. 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. 4. Rates of convergence are presented that are shown to be optimal in the well-specified case, effectively closing a gap in the literature. 5. 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. Overall, 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. 2. 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). 3. 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.

Questions

Q1: Is the machinery with introducing vvRKHSs really necessary when functions of Hilbert-Schmidt operators are learned? Q2: Theorem 2: Can "with high probability" be made more precise? minor: * some brackets for references are missing, e.g. p. 1, l.20, 33 and through out the manuscript * the references [33] and [34] are the same, also [6] and [7]

Rating

6

Confidence

5

Soundness

3

Presentation

3

Contribution

2

Limitations

yes

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.

Strengths

* The paper provides new theoretical results for vector-valued RKHS-based regression. * The paper is well written.

Weaknesses

* Contributions compared to previous work should be made more clear.

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]? [1] Li, Zhu, et al. "Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm." JMLR (2024). * 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? [2] Baldassarre, Luca, et al. "Multi-output learning via spectral filtering." Machine learning (2012). * Theorem 4 provides upper rates for vector-valued function learning with general spectral function. How optimality is maintained in this case? * Could the results be extended to other classes of operator-valued kernels (e.g., non-separable kernels)?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

A detailed discussion on limitations is missing.