On the Saturation Effects of Spectral Algorithms in Large Dimensions

Summary

This paper concerns the convergence rate of spectral methods, particularly kernel ridge regression (KRR) and kernel gradient flow (KGF), in large-dimensional settings where the sample size $n$ is of the same magnitude as a power $\gamma$ of the input dimension $ d $, i.e., $ n \asymp d^\gamma $. It reveals a new phenomenon of the saturation effect in large dimensions, which is different from its fixed-dimensional counterpart. Specifically, it shows that in large dimensions, KRR still suffers from the saturation effect while KGF does not. The key techniques involve the use of analytic filter functions to characterize the regressors from different spectral algorithms, followed by standard concentration results on the bias-variance decomposition of the excess risk.

Strengths

This paper offers solid theoretical results which improve over previous literature or reveal novel phenomenon. It offers important insights on spectral algorithms in large input dimensional setting, for example the interpolation (with different qualification $\tau$) of the learning rate between KRR and KGF, the exact description of the phenomena *periodic plateau behaviour* and *polynomial approximation barrier*. This paper also offers numerical validations on their claim.

Weaknesses

There is no major weakness spotted in this paper.

Questions

I appreciate the result of this paper and hence look for any possible extension from the current result. This paper focuses on dot-product kernels $K=\Phi(\langle \cdot, \cdot \rangle)$ with inputs distributed uniformly on a hypersphere and with polynomial spectral decay. 1. By [Belkin2018] and [Haas2024], it simply seems the function $\Phi$ cannot be smooth but at least 1-differentiable, say $\Phi$ is induced by the ReLU-NTK. If $\Phi$ is smooth, for example $K$ is the Gaussian kernel, then the spectral decay is exponential. Can the result in this paper extend to this case? If yes, where is the adaptation? If no or not obvious, what would be the main technical difficulties? 2. In realistic setting, uniform input distribution on a hypersphere is too restrictive. Could one relax the condition to the distributions which have support on the whole sphere instead? I recall Lemma Lemma F.9 in [Haas2024] stating the spectral decay is still polynomial in this case. Could one extend the analysis in this case? Also, I have some technical questions concerning the appendix. 3. In Eq (62) in Lemma D.7, the left hand side (LHS) should be independent to the noise, but why is there a term with $\sigma^2$ on the right hand side (RHS)? 4. Less like a question but more like a comment: I think that there is a typo in Eq (42): it should be $... \phi\_j^2(x)\leq ...$ instead of $... \phi\_i^2(x)\leq ...$. Also, is Eq (44) actually redundant as a special case of Eq (43) given the notation mentioned in line 602 - 603? Reference: - Haas, Moritz, et al. "Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension." Advances in Neural Information Processing Systems 36 (2024). - Belkin, Mikhail. "Approximation beats concentration? An approximation view on inference with smooth radial kernels." Conference On Learning Theory. PMLR, 2018.

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

All assumptions and conditions are stated clearly in the paper.

Summary

In a large-dimension setting, i.e., the dimension $d$ of the input grows polynomially with respect to the sample size $n$, this manuscript rigorously proves upper and lower bounds for spectral algorithms and shows the dependence on the qualification and the interpolation index. Consequently, the manuscript proves the saturation effect in spectral algorithms for large-dimensional data.

Strengths

1. Identify several phenomena in large-dimensional spectral algorithms based on the derived rates. These phenomena are also illustrated by figures, making the explanations easy to follow. 2. Discovered the thresholding for igniting saturation effect is different for large-dimensional and fixed-dimensional settings. Specifically, in a large-dimensional setting, the saturation effect occurs when the interpolation index exceeds the qualification, whereas in a fixed-dimensional setting, it must be more than twice the qualification.

Weaknesses

1. By checking previous work [1,2] and the proofs in these works, it looks like Theorem 3.1 has been established in Section 4 of [1], while Theorem 4.1 and Theorem 4.2 are the direct extensions of partial results in Theorem 2 and Theorem 3 from [2]. For instance, the proofs of Theorems 4.1 and 4.2 are obtained by replacing the Tikhonov regularized filter function in the variance and bias decomposition of [2] with a general filter function satisfying specific conditions such as C1 and C2. Such a proof trick has been used in previous extend from KRR (Tikhonov regularization) to general spectral algorithms, i.e., [3] to [4]. However, unlike the extension from [3] to [4], the current manuscript seems to be a partial extension of [2] with a similar proof trick as I mentioned before. Therefore, I have concerns about the technical contribution and novelty of this manuscript as a submission to a conference. This work seems more like an extension to a journal like JMLR, etc. I am just not sure whether such a partial extension of a previous article with almost the same proof technique is suitable for conference publication or whether it would be better evaluated in a journal. I defer this justification to the AC. Please disregard this comment if the AC deems the current context appropriate for conference publication. 2. I noticed there are some simulation experiments to confirm the saturation effect in fixed dimension KRR; see [5]. Is it possible to confirm the results in this manuscript? I understand given the rates are asymptotic, it might be hard to have thorough investigations due to the extremely large $d$. But I'm still curious if any preliminary experiments can be done. [1] Lu, Weihao, et al. "Optimal rate of kernel regression in large dimensions." _arXiv preprint arXiv:2309.04268_ (2023). [2] Zhang, Haobo, et al. "Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensions." _arXiv preprint arXiv:2401.01270_ (2024). [3] Zhang, Haobo, et al. "On the optimality of misspecified kernel ridge regression." _International Conference on Machine Learning_. PMLR, 2023. [4] Zhang, Haobo, Yicheng Li, and Qian Lin. "On the optimality of misspecified spectral algorithms." _Journal of Machine Learning Research_ 25.188 (2024): 1-50. [5] Li, Yicheng, Haobo Zhang, and Qian Lin. "On the Saturation Effect of Kernel Ridge Regression." International Conference on Learning Representations. (2024)

Questions

1. I'm curious to know if it is possible to conduct a similar analysis under ultra-high-dimension settings like the dimension grows exponentially fast as the sample size $d = \exp\{n^{\gamma}\}$. Do we need additional techniques to conduct these analyses? 2. Based on the figure, it looks like even when $s> 2\tau$, as long as $d$ grows with $n$, the saturation effect will not happen, which is different from the fixed dimension setting. While this may be the consequence of the derived rate, can authors provide some intuition behind this? 3. Is there a particular reason that the authors concern $\gamma \in p(s+1),(p+1)(s+1))$ with $p$ as integer to derive the rates? Why is this ratio an integer?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes.

Summary

### Summary: The authors study the saturation of spectral algorithms (KRR & GF) in high-dimensions where $n,d$ are both large, meaning that when KRR can't achieve information theoretic lower bounds with over smooth the regression functions while kernel Gradient Flow (GF) can. Theorem 3.1 states the optimal convergence rate of kernel GF which matches the provided minimax lower bound in Theorem 3.3. Moreover, they find that KRR is unableto achieve this lower bound (being suboptimal) for interpolation spaces with $s >1$.

Strengths

### Pros: - very well-written - tightening previous results on the minimax rate of kernel GF in high dimensions - proving the saturation of KRR in high dimensions

Weaknesses

### Cons: - the main results of this paper are stated on page 7, the presentation of the results is slow

Questions

This is an interesting paper about the saturation of KRR in high dimensions. The authors provide several new results and the paper is well written and organized. - line 200 -- what does $f_\star$ mean? It is only defined in the next page.

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

N/A