Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper summarizes the generalization error of kernel ridge regression and Gaussian processes under a spectral decay assumption.
main_review: The paper uses the negative log marginal likelihood and its relationships to Bayesian generalization error to give interesting generalization bounds. The paper largely cites previous theorems for most of its theoretical distributions and under power decay assumption, they use the log likelihood formula to derive bounds. However, it is unclear how novel the contributions are, other than plugging the power decay assumption into the previously derived formula. Furthermore, the relationship to NTK is only briefly touched upon. 

Given that the paper is largely theoretical, I believe there should be more emphasis on the technical novelty and the difficulty of extracting an asymptotic expression for the loglikelihood formula given the strong assumptions made on the kernel spectrum. For example, what is the novel theoretical contribution for showing that 
? Doesn't it follow from a matrix concentration inequality? If it's an nontrivial application of matrix concentration, can you point out how it is nontrivial. I also saw that you applied a spectral truncation argument. Is this argument necessary and/or novel? Perhaps emphasizing such points in the main sections of the paper would significantly strengthen the paper since it seems like the reader would need to infer the non-triviality from the appendix.

**Update: The authors have significantly strengthened the theoretical understanding of the problem and the intuition/novelty of their techniques.
summary_of_the_review: Since this is largely a theoretical paper, it is unclear if these results are novel since it seems like just plugging the power decay assumption into the log likelihood formula.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper consider asymptotic properties of Gaussian process models where the eigenvalues from Mercer's theorem exhibit polynomial decay. Unlike the earlier analysis of Sollich, the authors do not assume that the model is correctly specified. The authors provide a short experiment to illustrate the theory.
main_review: ## Strengths
- The early sections of the paper are clear and motivate the paper well.
- The results appear to be interesting, the problem of characterizing learning curves for Gaussian processes under mis-specification is important.

## Weaknesses
- Parts of the main results feel like a bit of list of results. I think the exposition in these sections could be improved by providing more context for each result as well as how the results differ. I would like to see more examples of how they apply to concrete examples.
- It isn't entirely clear to me how to interpret the results. In particular, the rate of decay depends on the smoothness of the kernel (unsurprising), but also on how quickly the coefficients of the observed function decay with a decomposition with respect to the Mercer basis of the kernel. I suspect that they can only decay quickly if the function is smooth, but the converse is not at all clear to me. I realize you cite other papers for this result, but for the purposes of being self-contained.
- The connection to neural networks is interesting, but the result is really a result on Gaussian processes. The connection to neural nets seems a bit orthogonal to the results in the paper, and I am not convinced it should be emphasized so heavily.
 
## Questions/comments
- Make explicit if $f$ is assumed to be in $L^2(\Omega,\rho)$ (I assume this is needed for the decomposition in eqn 9).
- Does $\phi_0$ in general depend on $f$? If so, perhaps consider noting this for clarity. (My understanding is that it is the projection of $f$ onto the orthogonal complement of the $\phi_p$).
- The assumption that eigenfunctions are uniformly bounded seems quite restrictive. I realize it is present in at least several other works in the GP literature (e.g. Braun, 2006, Vakili et al 2020). However, I it seems somewhat restrictive (for example for a squared exponential kernel and Gaussian inputs, this condition doesn't hold, Zhu et al 1997 eqn 44, of course this also doesn't have polynomial decay, just an example where the bounded eigenfunction condition doesn't hold). The authors provide an example on the sphere where this condition holds. Are there examples on compact subsets of $\mathbb{R}^d$ where this condition holds? Alternatively, can the results be generalized to relax this condition? 
- If I understand correctly, Theorem 8 in some sense corresponds to the "unrealizable" setting, in which the target function is outside the span of the features. In this case, should the question be about how accurately the posterior approximate $f$, or how accurately the posterior approximates the projection of $f$ onto the span of the features? (Essentially, I am wondering if this result is in some sense vaccuous in a not terribly interesting way). Any insight the authors can provide would be helpful.
- I am concerned remark 10 is incorrect/misleading and I would appreciate clarification. If I understand correctly, the suggested conclusion is that a sample from the GP prior (almost surely?) satisfies the decay conditon with $\beta=\alpha/2$. I don't see why this would be the case. In particular, for this to be true, it seems we would need there to exist a constant $C$ such that $\sup_{p} \omega_p \leq C$ which is almost surely not the case. Perhaps this only contributes some log factors (see Boucheron et al, 2012, Section 2.5), which will end up hidden in the $\tilde{O}$ notation anyway, but I think some subtlety may have been lost here. If not, I would appreciate clarification.
- Can lower bounds on any of your results be established? I realize this may be beyond the scope of this paper, but it would be interesting to know if the upper bounds presented are optimal.

## Minor comments and questions:
- "For inputs distributed uniformly on the unit interval, Ritter et al. (1995) showed that $r$-times mean square differentiable processes feature an asymptotic power-law decay of the form $λ_p∝p^{−(2r+2)}$" --Does this not follow from the earlier work due to Widom? Is the difference that Ritter doesn't need to assume stationarity?
- Distributions and densities seem to be conflated slightly in the problem setup. In particular, at times $\mathcal{N}$ is used to refer to a distribution while at other times it is the density of the distribution.
- When citing a textbook, please provide a section or page number. 
- For Mercer's theorem to apply you need some assumptions on the kernel/input distribution. A relatively standard set of assumptions is compact support for the input distribution and a continuous kernel, though I believe there are more general formulations. 

### References for review
- Bucheron, Lugogsi, Massart. Concentration inequalities. 2012.
- Braun, 2006. Accurate Error Bounds for the Eigenvalues of the Kernel Matrix. https://jmlr.org/papers/volume7/braun06a/braun06a.pdf
- Vakili, Khezeli, Picheny. 2020. On Information Gain and Regret Bounds in Gaussian Process Bandits. 
-  Zhu,  Williams, Rohwer, Morciniec. 1997. Gaussian regression  and optimal finite  dimensional  linear  models.
summary_of_the_review: Overall, the result seems interesting. I have only minor concerns about the correctness, but I think these can be resolved (or it is possible I have misunderstood). I think the exposition could be improved to provide better context for the results, and tie them more concretely to real problems. Overall, I think the paper is above the threshold for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of fitting a target function corrupted by additive iid Gaussian noise using with a zero mean Gaussian Process (GP).

 It provides an asymptotic characterisation of the typical Bayesian and mean-squared generalisation errors under the assumption of power-law decay of the covariance eigenvalues and the target function coefficients when expressed in the covariance eigenbasis.
 
 The main result is to derive the exponents characterising the rate of decay of the aforementioned errors with the number of samples $n$, as a function of the spectrum and target function decays. The key technical step is to prove the concentration of $\Phi_{R}^{\top}\Phi_{R}\in\mathbb{R}^{R\times R}$ around $n I$ where $\Phi_{R}\in\mathbb{R}^{n\times R}$ the truncated matrix of eigenvectors evaluated at the data points, and $R=n^{\frac{2}{1+\alpha}-\kappa}$ with $0\leq \kappa < \frac{\alpha-1}{\alpha(\alpha+1)}$.

Finally, the authors provide one numerical experiment with the arc-cosine kernel and data uniformly distributed in the unit circle.
main_review: Studying the asymptotic decay of the generalisation error for power-law spectrum and target function decay is a classic subject in the Kernel ridge regression (KRR) literature, where these are known as capacity and source conditions. Indeed, the rate $n^{\max\left(\frac{1}{\alpha}-1, \frac{1-2\beta}{\alpha}\right)}$ reported in this work for the decay of the generalisation MSE is known in the KRR literature. The exponent $n^{\frac{1}{\alpha}-1}$ appears in Caponnetto and De Vito in 2007 [1] for optimally regularised KRR and a particular choice of target decay (eq. 19 of [1]), while the branch $n^{\frac{1-2\beta}{\alpha}}$ was reported more recently in [2,3]. The existence of a region with exponent $n^{\frac{1}{\alpha}-1}$ for other choices of regularisation and the cross-over between these two regimes is a particular case of the discussion in [4] (cross-over between blue and orange regions in Fig. 1, with purple point corresponding to [1]).

In my opinion the biggest contribution in this work is to put on rigorous footing some of the results appearing in [3,4] which were derived using semi-heuristic methods, and to extend them beyond the Gaussian design setting (note that [4] provides numerical evidence suggesting this decay holds more broadly) within the GP framework. 

I do believe this is a valuable contribution, but the way the authors present it with respect to previous literature - specially in the abstract and introduction - is misleading. For instance, the abstract suggests the rates and cross-over reported for the MSE are new, and fail to cite [2-4]. The introduction only superficially makes contact with what is known from the KRR literature, and would benefit from a discussion like the one sketched above. 

Specific comments / questions / suggestions:

1.  Top of page 5: *As mentioned in the introduction, this assumption is adopted in many recent works (Bahri et al., 2021;
Canatar et al., 2021; Nitanda and Suzuki, 2021). Velikanov and Yarotsky (2021)*. 
This is a classic assumption on the KRR literature, and to my knowledge were introduced by Caponnetto and De Vito in the mid 2000s, see [1]. They are commonly known in this context as source and capacity conditions.
2.  Proof sketch, top of page 6: is there any intuition behind the choice of truncation $R=n^{\frac{2}{1+\alpha}-\kappa}$? Can this be related to hypercontractivity property in the concentration results from [5]?
3. The notation for functions, vector and matrices is confusing. Explicitly writing the conventions used, or writing more often the dimensions of vectors and matrices could help clarify this. For example, $\Phi_{R}\in\mathbb{R}^{n\times R}$, $K_{n}\in\mathbb{R}^{n\times n}$, etc.  
4. Figure 1 is very hard to read, as one needs to zoom +300% to read the axis and caption. The matching of the power-laws would be easier to visualise in a log-log plot in terms of the slopes.   
5. Remark 14: As mentioned before, even though [4] derives the rates for Gaussian designs, they provide numerical evidence that this result works more broadly.
6. Is it possible to recover the other rates from [4] from the GP framework?

[1] Caponnetto, A., De Vito, E., *Optimal Rates for the Regularized Least-Squares Algorithm*. Found Comput Math 7, 331-368 (2007). https://doi.org/10.1007/s10208-006-0196-8

[2] Stefano Spigler, Mario Geiger, and Matthieu Wyart. *Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm*. Journal of Statistical Mechanics: Theory and Experiment, 2020(12):124001, 2020.

[3] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. *Spectrum dependent learning curves in kernel regression and wide neural networks*. In International Conference on Machine Learning, pages 1024-1034. PMLR, 2020

[4] Hugo Cui, Bruno Loureiro, Florent Krzakala, Lenka Zdeborová, *Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime*, arXiv: 2105.15004 [stat.ML]

[5] Song Mei, Theodor Misiakiewicz, Andrea Montanari, *Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration*, arXiv:2101.10588 [stat.ML]
summary_of_the_review: The results in this work are interesting, but in my opinion the discussion is largely misplaced with respect to existing literature. In particular the abstract and introduction. I am willing to raise my score in case the authors address these issues in a revision. 

------------------------------------------------------------------------
**Update after the discussion period**

During the discussion period the authors have addressed all my questions and have welcomed my suggestions. In particular, they have extended their GP treatment to include the "strongly regularised" regime, finding results which are consistent with the literature. Although the rates derived in this work are known, this work derives them under a different framework, and broadens the scope under which they can be rigorously established.

For these reasons, I am updating my score towards an accept.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Working under the nonparametric regression model, the authors established asymptotic rates for the Bayesian generalization error, normalized stochastic complexity and excess mean square error. The authors adopted the Bayesian approach by endowing the unknown regression function with a Gaussian process prior, and the covariance function is parameterized by a kernel function. By diagonalizing this kernel, the authors used the resulting eigenfunctions to represent the target function. They assumed that the kernel eigenvalues and the target basis coefficients decay according to the power-law, i.e., polynomial decay. Lastly, a simulation experiment was performed to verify the claims.
main_review: Overall the writing is clear. I found it helpful that the authors gave proof sketches and summary of the main steps detailed in the rather long appendix. The results improved upon those in the literature by being more widely applicable and with less stringent assumptions. Moreover, several rates derived by past authors are special cases of the general rates derived in this paper.

Here are some questions /comments:
1. The error variance $\sigma^2$ is assumed to be known which is rarely the case in practice. Also, the ReLU network mentioned in the paper is noiseless, i.e., there is no $\epsilon_i$. So how do the results presented in this paper reconcile with real-world practice?

2. Are the rates the best possible under power-law decay of the target and prior kernel? Is it possible to get better rates by using different kernel functions or eigenfunctions?

3. It can be seen that $\alpha$ encodes the prior smoothness, and it is related to the order of the kernel family used. In the experiments, the authors used the first-order arc-cosine kernel to yield $\alpha=4$. What is the rationale of choosing first-order and not higher orders? 

4. The interplay between $\beta$ and $\alpha$ is summarized in the second paragraph of the conclusion. However, how do we apply this conclusion in practice since we often do not know $\beta$? 

5. How did you compute the blue lines in Figure 1? In particular, where did $2.0795$ and $0.7875$ come from in $2.0795n^{-0.7875}$ for the excess mean square error of $f_1$?

############################################################################################################

TYPOS:
1. The line after (2), $K_{x\mathbf{X}}$ should be $(k(x,x_1),\dotsc,k(x,x_n))$ a row vector. Also to be clear, you need to assume that the kernel is symmetric in order for $K_{x\mathbf{X}}=K_{\mathbf{X}x}^T$ to be true.
2. In (3), I think $q(x,y)$ should be $q(y|x)$
3. The display after (17),  $\|(\mathbf{I}+\mathbf{\Phi\Lambda\Phi}^T/\sigma^2)^{-1}\|_2$
4. In (20), $F_0(D_n)$ should be $F^0(D_n)=T_1(D_n)+T_2(D_n)$ and not $\mathbb{E}_{\mathbf{\epsilon}}F^0(D_n)=T_1(D_n)+T_2(D_n)$ as defined in the line after (13).
5. In the Proof sketch of Theorem 9 the first step, I think you need to take expectations with respect to the errors in $G_{1,R}(D_n)$ and $G_{2,R}(D_n)$. See also the proofs.
6. In the Proof sketch of Theorem 9 the second step, what is $\delta$?
summary_of_the_review: I feel that some parts of the paper need more explanation and exposition. For example, discussion about the rates' optimality and modeling choices such as knowing $\sigma$ would significantly improve this paper.
review_title: null

Meta-review: The title of the paper nicely summarizes the main goal of the paper and the abstract does the same for the achieved results. For this reason I abstain from providing another summary. 

The initial reviews were somewhat mixed but during the discussion phase, a lot of questions have been resolved so that actually three reviewers updated (upgraded) their score. Remark 14 certainly needs to be updated according to the discussion in the final few days of the rebuttal phase. In addition, one reviewer pointed to a naive application of Mercer's theorem. This should be addressed as well, either by restricting to compact domains and continuous kernels as suggested by the reviewer, or by considering generalizations as done by e.g. the cited Fischer and Steinwart. Finally, the cited survey by Kanagawa et al also contains some information on learning curves and thus it should be cited more prominently, e.g. around Remark 14.

In any case, this paper is above the acceptance threshold.
Decision: Accept (Poster)