A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression

The learning curves of kernel ridge regression have been extensively studied in recent literature... It is really hard for me to understand the difference between the current paper with the above papers.

Thank you for your feedback. The three papers you mentioned are cited in the paper as references [16, 31, 34]. As explained in the paper, references [16, 34] assume the feature vectors are distributed according to Gaussian random vectors. This is what we call the IF case in our paper. These papers do not discuss the general feature case (GF). They also do not differentiate between exponential and polynomial decays and do not discuss differences between weak and strong regularization. Reference [31] employs a different assumption on the features, we have summarized the difference between their results and ours in Table 1 in the paper’s main body and in Table 5 in the appendix. For instance, Table 1 shows that our bounds are tighter than the results of [31].

Since this is the only weakness noted by the reviewer, we would like to request further details on the reasoning behind the score of 3. Does our response above address your concerns? Are there any other questions or doubts we can address?

The writing style of this paper is quite challenging for me to engage with. I find the presentation could be improved in terms of clarity and readability. For instance, could the author make their own results and assumptions in a more clear way? There is not even a single explicit theorem provided for me to verify. It is quite unusual for a theoretical paper to be presented in this manner. I am uncertain if this document has been generated by an artificial intelligence.

We would like to clarify that this paper was not written using ChatGPT or any other language model. We would appreciate it if the reviewer could specify which aspects of the presentation need to be improved.

While we agree that some results are technical, we have tried to present them in the most reader-friendly way through Table 1 and Figure 1. For instance, Table 1 outlines the bounds we derived for three different scenarios:

1. polynomial vs. exponential eigendecay,
2. strong vs. weak regularization, and
3. independent vs. dependent features.

All formal theorems are provided in the appendix, with Table 1 summarizing the key results, which we believe is a clearer way than listing each theorem individually. Additionally, Figure 1 illustrates the improvements achieved by these bounds in a diagram.

Could the reviewer specify what aspects of the table and figure are unclear?

Regarding the assumptions, we have a dedicated section (Section 2.2: Assumptions and Settings, line 96) that thoroughly covers them. Could you please further clarify your concerns? We are eager to improve the paper’s accessibility.

In the introduction, the authors say their work addresses three questions. While Q1 and Q2 are precisely addressed by the results, I find that the answer to Q3 falls short. First, the assumption (GF) is surely weaker, but it is still constraining.

We refer to the Author's Rebuttal for a detailed answer.

...some of the results in Table 1 are only upper bounds. I understand that most of the excess rate results in the classical kernel literature are also upper bounds, and the authors explicitly discuss that under (GF) it is not possible to derive a matching lower bound, but there is nothing telling us that the picture is not richer in these regimes...

Thank you for raising this important question on a matching bound, which we did not have space to discuss in the main text. Previous literature which mentions GEP usually only focuses on the upper bound, however, we will put more discussion on the lower bound in a future edition. We refer to the Author's Rebuttal for a detailed answer.

I miss a discussion on the intuition behind the (GF) assumption... Do you have an intuitive understanding of the two conditions in L440?

Again thank you for your question. The intuition behind (GF) is that the random distribution of the feature $\mathbf{z}$ is concentrated. By a Bernstein-type concentration inequality, one can show that independent features enjoy some concentration properties. See remark A.2 for more details.

Why does strong regularization justify independence?

To be precise, strong regularization does not justify independence. Instead, we proved that the learning rates for the (GF) and (IF) cases are asymptotically identical under strong ridge, demonstrating a necessary condition for GEP.

... how (GF) differs from the concentration assumption in previous work, e.g. (a1, a2, b1) in [36]... This suggests (GF) is strictly weaker?

First, Assumption 1 in [36] requires the regularized tail rank to be bounded from below, in this paper’s notation, it is $\frac{\sum\_{l>k}\lambda\_l +\lambda}{\lambda\_{k+1}} \geq 2n$. Note that this cannot hold for exponential decay as LHS is bounded but not RHS. On the other hand, assumption (GF) does not have similar restrictions.

Now we try to show how assumptions in [36] “imply” (GF). As mentioned in Remark A.2 and A.3, the intuition of (GF) is the concentration of the truncated features at their expected value. Now suppose Assumption a2 in [36] holds, for any $\mathbf{x}\_{\leq k}=\Sigma\_{\leq k}^{1/2}\mathbf{z}\_{\leq k}$, pick $\mathbf{A}=\Sigma\_{\leq k}^{-1}$ and we have w.h.p. $| \mathbf{x}\_{\leq k}^\top\Sigma\_{\leq k}\\mathbf{x}\_{\leq k} - tr[\Sigma\_{\leq k}\mathbf{A}] | \leq t \phi\_1(k) \\|\Sigma_{\leq k}^{1/2}\mathbf{A}\Sigma\_{\leq k}^{1/2}\\|\_{F}$ And hence, w.h.p.: $| \\| \mathbf{x}\_{\leq k}\\|^2/k - 1 | \leq t \phi\_1(k),$ which implies the concentration of the first term in (GF).

Similarly, Assumption 2 in [36] implies the concentration of the second term in (GF). At the moment, we do not know if the concentration of the third term in (GF) can be derived from any assumptions in [36], but as mentioned in Section A.2, the kernels satisfying the assumptions made in [36] form a proper subset of those which satisfies (GF).

Hence, we believe our paper gives a more general result. If the reviewer could find any kernels which satisfies assumptions [36] but not (GF), please let us know as it would be of significant interest.

Since the main result in this work dialogues with previous literature, I suggest commenting and comparing the important notation (source, capacity, regularization decay, etc) in this work with the ones employed in the relevant Gaussian design literature...

Thank you for your suggestion. We will put this into our consideration in our future edition to enhance readability and comparison with previous literature.

Can you please elaborate on Remark A.5?

Suppose (IF) holds and each coordinate $z_l$ of the isotropic feature vector $\mathbf{z}$ is drawn i.i.d. from a random distribution with bounded support, hence there exists constants $a,b$ such that $z_l^2$ is a.s. In the interval $[a,b]$. By Hoeffding’s inequality, for any $t>0$, $\mathbb{P} \\{ | \\|\mathbf{z}\_{\leq k}\\|^2 - k | > t \\} \leq 2\exp(-2t^2/k(b-a))$ Let $t=\frac{k}{2}$, we have $\mathbb{P} \\{ \frac{3}{2} > \\|\mathbf{z}\_{\leq k}\\|^2/ k > \frac{1}{2} \\} \geq 1- 2\exp(-k/2(b-a))$ Then w.h.p., the fraction $\\|\mathbf{z}\_{\leq k}\\|^2/ k$ is concentrated at its expected value 1, similar argument holds for the other two fractions $\\| \mathbf{z}\_{> k}\\|\_{\Sigma\_{>k}}^2 / tr[\Sigma\_{>k}]$ and $\\| \mathbf{z}\_{> k}\\|\_{\Sigma\_{>k}^2}^2 / tr[\Sigma\_{>k}^2]$. By remark A.3, it suffices to show a weaker version of (GF). For technical simplicity, we require ess sup and ess inf in (GF) instead of a high probability bound.

minor points: ...

Thank you very much for your effort improving our manuscript. We will adjust the points mentioned accordingly in our revised version.

Thank you for your time and effort reviewing our paper. Regarding your questions,

The presented results seem to be based on a set of different assumptions while comparing with the current bounds... it is not clear how the differences in assumptions affect the comparison.

Section A.2 is dedicated to explaining and discussing the comparison between different assumptions from various papers. We kindly refer the reviewer to Section A.2 for more detailed information. We also refer to the Author's Rebuttal for a detailed answer.

The numerical studies demonstrate the validity of the bounds for a couple of constructed kernels. However, it would be beneficial to consider more general/practical kernels to assess the practical impact of this work.

An important contribution of this paper is to provide a unifying theory connecting all scattered results from previous literature. We have derived the same optimal upper bound with a more general assumption. Demonstrations on practical kernels can be seen in various previous literatures, including [12, 16, 31]. We will make this clear in the revision of the manuscript.

Does the result hold under the assumptions used in the related work, e.g., Embedding Condition?

Yes. There is a detailed discussion in Section A.2 page 15 - 16.

Thank you for your time and effort reviewing our paper. Regarding your questions,

In demosnstrating the GEP, the paper seems to only provide the upper bound for bias and variance under generic features while a matching lower bound is missing... I was wondering if the author could explain this a bit or can detail the challenges in obtaining the lower bound.

This is indeed a good question to ask for the lower bound in the (GF) case, which we did not have space to discuss in the main text. We refer to the Author's Rebuttal for a detailed answer.

Previous works that mention GEP typically focus on the upper bound; hence, our paper also demonstrates GEP on the upper bound. However, the lower bound is complex, our paper is a first step understanding it better, and we will explore it further in a future work dedicated to these questions.

We will update the paper to provide a detailed discussion of the aspects discussed in this answer as well as clarify the GEP claim, thank you for your comment.

Recently, there is a growing interest in studying the KRR when the output is infinite-dimensional... I am curious whether the results hold in the setting where the output is infinite-dimensional. Maybe the author could draw some link between their results and this setting.

Thank you for pointing out this interesting setting. We were not aware of it. We looked at the proof technique and it seems it relies on an assumption similar to the embedding condition and relies on similar proof techniques (spectral calculus and concentration inequalities). A direct comparison seems difficult, as we for instance do not see a way to establish a comparison between different eigendecay and regularization regimes.

That said, we do expect that many of these results could be extended to the infinite-dimensional setting, for instance, by projecting the target function to finite dimensions (via a Schauder basis truncation) then applying our results, and then (isometrically) embedding the learned (finite-rank) up be encoding it as weights to the chosen given Schauder basis. In effect, one can view the current results as doing precisely this using the standard orthonormal basis of Euclidean space $\mathbb{R}^D$ as the Schauder basis and “truncating” at the full-dimension $D$ (in which case the truncation reduces precisely to the identity map, and the embedding is also the identity map). This type of argument has successfully been used in the approximation-theory literature; see e.g. [1] for the Hilbert case (where the Schauder basis can be taken to be orthonormal) or [2] (in the Banach or even Fréchet case) where the basis is a genuine Schauder basis (eg a Wavelet basis when the target space is a Besov space over any E-thick domain with Lipschitz boundary (see Theorem Theorem 3.13 in [3] such as the Euclidean unit Euclidean ball).

[1] Lanthaler, Samuel. "Operator learning with PCA-Net: upper and lower complexity bounds." Journal of Machine Learning Research 24.318 (2023): 1-67.

[2] Galimberti, Luca, Anastasis Kratsios, and Giulia Livieri. "Designing universal causal deep learning models: The case of infinite-dimensional dynamical systems from the stochastic analysis." arXiv preprint arXiv:2210.13300 (2022).

[3] Triebel, Hans. Function spaces and wavelets on domains. No. 7. European Mathematical Society, 2008.