On the Saturation Effects of Spectral Algorithms in Large Dimensions

We sincerely thank you for taking the time to read our paper and for providing valuable feedback. We are pleased to see that you not only accurately described the contributions of our work but also gave it high praise. We would like to address the questions and comments you raised regarding possible extensions of our research.

Author's response to Question 1:

Thank you for suggesting checking our assumptions on two specific kernels. After a careful check on the paper [Belkin2018] and [Haas2024], we find that $\Phi$ for both ReLU-NTK and the Gaussian kernel are analytic, with all coefficients $a_j>0$, thus satisfying Assumption 1. Therefore, the results of this paper apply to both ReLU-NTK and the Gaussian kernel. Please let us clarify in detail:

• From the definition of ReLU-NTK in [Bietti2021], $\Phi$ for ReLU-NTK is analytic (see, e.g., page 6 in [Bietti2021]). Moreover, Corollary 3 of [Bietti2021] as well as Lemma B.2 of [Haas2024] both imply that we have all coefficients $a_j>0$. Notice that the proof for the positive-definiteness of the kernel in the above studies relies on [Gneiting2013], hence they also require that $\Phi$ is analytic.

• From the definition of the Gaussian kernel defined on the sphere, we can show that $\Phi$ for the Gaussian kernel is analytic, with all coefficients $a_j>0$.

Since both kernels satisfy Assumption 1, we have the following claims:

• You are right. When $d$ is fixed dimensions, [Bietti2021] showed that the eigenvalues of ReLU-NTK satisfy $\mu_k \asymp k^{-d}$ and $N(d, k) \asymp k^d$ for large $k$, leading to $\lambda_j \asymp j^{-\beta}$ with $\beta = (d+1)/d$; whereas it is known that the eigenvalues of the Gaussian kernel defined on sphere decay exponentially (see, e.g, [Amnon2020]). Therefore, we may need different tools to deal with the rate of the excess risk of fixed-dimensional spectral algorithms with ReLU-NTK and the one with the Gaussian kernel.

• In large dimensions, the spectra of both ReLU-NTK and the Gaussian kernel exhibit a strong block structure as follows: $\mu_k = \Theta(d^{-k})$ and $N(d, k) = \Theta(d^{k})$ for $k \leq p+1$ (see, e.g., Lemmas D.11 and D.13). Therefore, our results hold for both ReLU-NTK and the Gaussian kernel in large dimensions without any adaptation.

Author's response to Question 2:

We agree that a uniform input distribution on spheres is too restrictive. As noted in Remark 2.1, most studies analyzing spectral algorithms in large-dimensional settings concentrate on inner product kernels on spheres for two main reasons:

• Firstly, harmonic analysis on the sphere is clearer and more concise. For example, the properties of spherical harmonic polynomials are simpler than those of orthogonal series on general domains. This clarity makes Mercer’s decomposition of the inner product more explicit, avoiding several abstract assumptions.

• Secondly, there are few results available for Mercer’s decomposition of kernels on general domains, especially when considering the domain’s dimension. For example, no results determine the eigenvalues of Sobolev space in large dimensions.

Thus, if we believe that large-dimensional KRR and KGF exhibit some new phenomena, it would be prudent to start with a more tractable setting, and then extend the results to general domains.

Regarding your second question, thank you for bringing up the interesting work [Haas2024] and suggesting an extension of our analysis. We believe that the results in [Haas2024] can indeed be extended to large-dimensional settings, although we must carefully consider the constants that depend on $d$. For example, the density in Lemma D.7 of [Haas2024] is lower and upper bounded by two constants depending on $d$.

We appreciate your insightful suggestion. We will add the paper [Haas2024] to the discussion section of our manuscript, and we will consider extending our results to general domains in future work.

Author's response to Question 3: Thank you for pointing out the potential issue in Eq (62). We have revised our manuscript and updated Eq (62) to the following version :

Moreover, we followed your suggestion and added a rigorous definition of $o(1)$ in our manuscript: We say two (deterministic) quantities $U(d), V(d)$ satisfy $U(d) = o(V(d))$ if and only if for any $\varepsilon > 0$, there exists a constant $D_{\varepsilon}$ that only depends on $\varepsilon$ and the absolute positive constants $\sigma, \kappa, s, \gamma, c_0, c_1, c_2, C_1, \cdots, C_8 > 0$, such that for any $d > D_{\varepsilon}$, we have $U(d)< \varepsilon V(d)$.

We hope that the updated definitions clarify that Eq (62) is correct when $\sigma>0$ is an absolute constant defined in (1).

Author's response to Question 4:

Thank you for your careful reading of our proof and for pointing out the typo in Eq (42). We will correct it in the updated manuscript. Regarding your comment about Eq (44), we believe it is not redundant. In Eq (44), $\varphi_{\lambda}$ refers to the filter function of a specific spectral algorithm (not necessarily KRR), while $\varphi_{\lambda}^{\text{KRR}}$ in (43) specifically denotes the filter function for KRR.

Reference:

• Alberto Bietti and Francis Bach. "Deep equals shallow for ReLU networks in kernel regimes." In International Conference on Learning Representations (ICLR), 2021.
• Tilmann Gneiting. "Strictly and non-strictly positive definite functions on spheres." Bernoulli, 19(4): 1327–1349, 2013.
• Geifman, Amnon, et al. "On the similarity between the Laplace and neural tangent kernels." Advances in Neural Information Processing Systems 33 (2020): 1451-1461.

Thank you for your thorough review and valuable comments. Below, we address your concerns and questions in detail.

Concern 1: Please let us clarify our novelties and contributions below.

• Although the saturation effect has been observed for kernel ridge regression in a large-dimensional setting [2], its persistence for other spectral algorithms was unclear. We determine the exact rate of excess risk for analytic spectral algorithms with qualification $\tau$. Key outcomes include:
  • Kernel gradient flow is minimax optimal in large dimensions, with an excess risk rate of $d^{-\min(\gamma-p, s(p+1))}$.
  • We proved the saturation effect for large-dimensional KRR when $s>1$ and for spectral algorithms with $\tau$ when $s>\tau$.

Regarding your concerns on the technical contributions:

• [3][4] addressed the convergence rate for fixed-dimensional spectral algorithms when $0<s\leq 2\tau$, focusing on non-saturated cases where KRR and kernel gradient flow are rate-optimal. In contrast, they did not consider the saturation effect of spectral algorithms when $s > 2\tau$.
• [1] determined the minimax rate of kernel regression for $f \in [\mathcal{H}] ^ s$ where $s=1$. The proof in [1] relies heavily on empirical process theory, requiring bounds on the empirical loss and its difference from the expected loss (excess risk). This approach does not generalize to cases where $s \neq 1$.
• [2] provided a minimax lower bound for $s>0$ using integral operator techniques for KRR, hinting at a saturation effect but not generalizing to other spectral algorithms.

We extended results to general spectral algorithms in large dimensions using complex variable analysis (Appendix E.1 and [6]) to match upper and lower bounds. Large dimensions introduce unique challenges:

• The polynomial eigendecay assumption that $\lambda_j \asymp j^{-\beta}$ does not hold in large dimensions, since the hidden constant factors in the assumption vary with $d$.
• The embedding index assumption in [6] does not hold either. We develop a new condition in (63) and (74) to replace the embedding index assumption, and we verify this new condition in Appendix D.4.

We believe our contributions are novel and valuable for the machine learning community, meriting publication at NeurIPS.

Reference: [6] Li, Yicheng, et al. "Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay."

Concern 2: Thank you for your suggestion. We agree that conducting thorough numerical investigations can be challenging due to the extremely large dimensionality $d$. Following your recommendation, we conducted two preliminary experiments. We will follow your advice to conduct more comprehensive experiments later and report the results in the updated manuscript.

Question 1: In this paper, we consider the asymptotic framework $n \asymp d^\gamma$ with $\gamma>0$. As discussed in lines 97-115, many studies focus on the performance of spectral algorithms within this asymptotic framework. By comparing our work with these studies, we highlight the novelty and contributions of our results to the field. In contrast, we were not aware of similar studies under ultra-high-dimensional settings, hence we did not explore this scenario in our manuscript.

Your insightful suggestion implies that this could be an interesting avenue for future research. When $n \asymp d^{\gamma}$ and $\gamma$ is sufficiently small, the excess risk in our results is of rate $d^{-\gamma}$. If we consider $\log(d)$ as a limiting case of $d^{\gamma}$, we might conjecture that the correct rate of the excess risk when $n \asymp \log(d)$ is $\log^{-1}(d)$.

We believe your suggestion is promising, and we will consider conducting a similar analysis under ultra-high-dimension settings in future work.

Question 2: Thank you for your question. We guess that there might be some typos in your expression, and we guess that you wanted to state the distinction between our results and existing results in fixed-dimension settings as follows:

• Our results, Theorems 4.1 and 4.2, demonstrate that the saturation effect occurs in large-dimensional settings if and only if $s > \tau$. In Figure 2 (on page 13), we illustrate this with the spectral algorithm rate (blue line) and the minimax rate (orange line). The blue and orange lines exhibit non-overlapping regions if and only if $s > \tau$. Therefore, Figure 2 aligns with our claims.
• In contrast, in fixed dimension settings, the saturation effect occurs if and only if $s > 2\tau$.

Then let us provide you with some intuition behind the consequence of the derived rate. We highlight that the periodic behavior of the rates with respect to $\gamma$ in Theorem 4.1 and 4.2 is closely related to the spectral properties of inner product kernels for uniformly distributed data on a large-dimensional sphere. In Lemmas D.11 and D.13, we show that $\mu_k= \Theta(d^{-k})$ and $N(d, k) = \Theta(d^{k})$ for $k \leq p+1$. Moreover, recall that the leading terms for the bias and variance are given by $M_{2, \varphi}(\lambda) + \frac{\sigma^2}{n} N_{2,\varphi}(\lambda)$ (see Appendices D.1-D.3). Therefore, by comparing between $M_{2, \varphi}(\lambda)$ and $\frac{\sigma^2}{n} N_{2,\varphi}(\lambda)$ (with calculations detailed in Lemma D.14) under the strong block structure of the spectrum, we found that the rate of excess risk behaves periodically for each period $\gamma \in [p(s+1),(p+1)(s+1))$, $p = 0, 1, \cdots$, and that the saturation effect occurs when $s > \tau$.

Question 3: The intervals $[p(s+1),(p+1)(s+1))$, $p=0, 1, \cdots$ naturally from our derivation process. Thus, we may focus on $\gamma\in [p(s+1),(p+1)(s+1))$. Regarding your second question about why this ratio is an integer, we are not entirely certain whether you are referring to the constant $\gamma$ or the integer $p=\lfloor\frac{\gamma}{s+1} \rfloor$. For further clarification, please let us know.

We sincerely thank you for your detailed review and thoughtful comments. We are grateful that you found our paper well-written and technically solid. Below, we address your concerns and questions in detail.

Author's response to Concern 1: We appreciate your suggestion to present our results earlier in the paper. We agree that, in a 9-page conference paper, it is crucial to present the main results as early as possible. Therefore, we followed your recommendation and added a non-rigorous version of our main results (Theorem 4.1 and Theorem 4.2) in the contribution part (page 2 in our manuscript). For your convenience, we restate the non-rigorous version as follows:

Theorem (Restate Theorem 4.1 and 4.2, non-rigorous)

Let $s>0$, $\tau \geq 1$, and $\gamma>0$ be fixed real numbers. Denote $p$ as the integer satisfying $\gamma \in [p(s+1), (p+1)(s+1))$. Then under certain conditions, the excess risk of large-dimensional spectral algorithm with qualification $\tau$ is of order:

where $\tilde{s} = \min${$s, 2\tau$}.

We would greatly appreciate your further advice on how to better organize our paper.

Author's response to Question 1: Thank you for highlighting this point. We will clarify the definition of $f_{\star}(x) = x[1]x[2]\cdots x[L]$ in line 200. Here, $f_{\star}$ represents the regression function, where $x[i]$ denotes the $i$-th component of $x$. We will ensure this definition is included in the revised manuscript.

We thank you once again for your expertise and valuable feedback. Please let us know if you have any further questions.