Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Summary.

The paper studies the kernel ridge regression and provides close form characterization on the loss curve in the finite sample regime of $m \propto d^{r}$, where $m$ is the sample size, d is the input dimension and $r \geq 1$ is arbitrary integer. The paper also proves the results hold broadly to the neural tangent kernel (NTK) of one-layer convolutional net.

Model. 
The paper studies the classical kernel ridge regression under the assumption that input data draws from d-dimensional sphere and certain isotropic/independence assumption of higher order Fourier coefficients. While previous work of [Mei and Montanari 2021] considers mostly of linear regime, i.e., $m \propto d$, the paper extends the result to $m \propto d^{r}$ to arbitrary integer $r$.


Result.
The paper provides a close form characterization of the population loss. It is hard to describe in non-mathematical way, the close form characterization consists of Bias and Variance terms, where both terms are certain integral of Marchenko-Pastur distribution (limiting spectral distribution for random matrix) and exhibits the double descent phenomenon (bias always decay, but variance first goes up and then down)


Method 

The method extends from the previous work of [Mei and Montanari 2021]. They use Legendre polynomial decomposition to the kernel and by standard concentration, argue one only needs to look at the $r$-th order decomposition. Then perform standard bias-variance decomposition and use random matrix theory to argue about the spectral. Some technical complications come out along the proof.

strengths_and_weaknesses: Strength. The paper provides close form characterization of loss curve for kernel regression and offers some insight on the double descent phenomenon. The technique follows largely from [Mei and Montanari 2021] but also turns out to be very interesting and non-trivial to me.

Weakness. There are no significant weaknesses but the writing could be significantly improved.  (See below)

1. Line 72. It is better to use $x^{\top}$ instead of $x^{T}$ for transpose. This applies to other matrix/vector transpose.
2. Line 46. “Extending these result “ - - > “Extending these results “
3. Line 40. “Large text corpora can contain trillions of tokens, wheares” I don't quite get it, the input dimension of language model might not be that large, but the entire models could still be quite large.
4. Eq. (5) what is $\delta_{0}(t)$.
5. Eq. (11) typo: need to add transpose for the variance and covariance.
6. Figure 3. Might be good to make bias and variance more clear.
7. Line 190. Would be good to make a separate paragraph for low frequencies and critical frequencies
8. The experiments are all simulations that should be emphasized somewhere.
9. The reference format seems wrong.
10. typo: Line 258 $y_k(\mathbf x)$ should be the summation over $j\in[d]$

questions: 1. Why the kernel result only apply to convolutional kernel but not other neural tangent kernel (say one-layer ReLU)?
2. I have difficulty understanding the setup. Line 76, why is $P_k$ a k-th order Legendre polynomial in 'd dimensions'? Isn't $P_k$ from $[-1,1]\to \mathbb R$? The equivalence between the Legendre polynomial and spherical harmonic representation looks non-travail to me, can you provide a reference for this?



limitations: .
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors aim to theoretically analyze the relationship between number of samples ($m$) and test error (learning curve) in the case of Kernel regression for dot product kernels when the $m \sim d^r$ where $d$ is the dimensionality of data and $r$ is a natural number. Their analysis shows that when the input distribution and labeling function follow some regulatory conditions, under some asymptotics, a closed form formula precisely characterizes the learning curve for the mentioned set of kernels, and their experiments support this claim. Moreover, they asymptotically derive a closed-form distribution for the gram matrix of some dot product kernels, which seems valuable for future works.
Although the work indeed does have some limitations (mentioned in greater detail in the limitations section), both on the theoretical and experimental aspects, I find the contribution to be impactful in the direction of understanding/characterizing generalization error in modern machine learning.
strengths_and_weaknesses: **Strengths:**

* The theoretical results of the work are sound and fills a gap in the study of learning curves for the case of non-linear relationship between the number of samples and dimensionality of the data.

* The predicted distribution for the spectral distribution of the mentioned dot product kernels seems very accurate and can potentially benefit future work. 

* The conducted experiments, although with some limitations, strongly support the theoretical results.

**Weaknesses:**

* Some parts of the text are hard to follow. For instance, the notation section brings up the whole decomposition of the function of the dot product kernel without motivating it. This kind of introduction to some topic without motivating it beforehands happens a lot in the paper, and for me was generally confusing. Moreover, sometimes some equations or results are being referred to before being obtained or described. For instance, in line 171 there's a reference to Eq 29, which is undefined at this point for the reader. Likewise, $\chi_B$ and $\chi_V$ are introduced without much motivation. 


* Various assumptions are not justified nor analyzed, and their importance could be better explained. As an example, the assumption of having according decomposable labeling function could be better explained in a sense that how close is it to the practical datasets that one might expect, at least for some toy examples. 

* I believe the writing could enjoy more description about motivations, intuitions, the why of different assumptions and the relativity of them (how often do they hold in practical settings? why do we need them and what goes wrong if we don't have them?) instead of some extra formulas in the main text, such that the main text would give an overall intuition about the problem and the approach to solve it along with the derived theorems, and the proof sketchs could be delayed to the appendix instead. However, this is just my opinion. 

* Although the experiments strongly support the theoretical results, the range of values used for $m, r, d$ seem a bit limited to me. In particular, there are some asymptotics in the theoretical results (high frequency and low frequency decompositions of the kernel value that converge or diverge asymptotically as $d \to \infty$) that I expected to result in very noisy experimental results, specially for the range of tested values, but surprisingly this doesn't happen in the provided experiments. I would be curious to know why this is the case. Moreover, experiments involving noise and ridge regularization could also benefit the paper.

* I believe more insights could be provided based on the solid theoretical results that are achieved. Having a closed formula for determining the precise learning curve in the mentioned context unlocks a lot of analyses. For instance, how does $r$ in $m \sim d^r$ affect the number of descents in the curve or the slope of the curve? How does the labeling function or the data affect the slope and/or the number of descents? The dependence on the spectral gap is mentioned, but when does one expect large or small spectral gap? 

* Some more detailed concerns and questions:
  * What is the definition of a "fat" or "tall" matrix? 
  * Why would one expect the coefficients of the legendre polynomials to be non-zero up to a large index in the decomposition of $h$, and why does it have to be independent of $d$?
  *  Could you please shed more light on the decomposition of the labeling function and the specific assumptions like the fact that $\hat f_k$ should be isotropic? How likely is it that practical datasets follow such decompositions?



questions: My questions have been mentioned in the weaknesses section.
limitations: I have mentioned unaddressed limitations as part of the weaknesses.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors explicitly characterize the learning curve for kernel ridge regression under poly scaling regimes $m \sim d^r$, both theoretically and empirically. Despite the strict restrictions on the distribution and the setting, this interesting multiple-descent behavior in the sample-wise learning curve could help the understanding of neural networks.
strengths_and_weaknesses: Strength:
Theoretical results seem to be solid (did not check step by step though). 
Experiments serve as good illustration of the key ideas.

Weakness: 
1. (minor) readability could be improved by adding more details (could be placed at the beginning of the appendix in a separate (sub-)section):
(1) explicit definitions of asymptotic notations, e.g., $\sim$, $O(\cdot)$.
(2) background on decomposition via spherical harmonics 

Moreover, are there (commonly seen) examples for the kernel function that eq. (1) is satisfied?

2. (major)The contribution/impact of the current finding should be more carefully articulated, instead of several lines in the intro (lines 54-56). Also a better summary of the existing works on both linear/non-linear scaling regimes would be better. 

What is the connection (in terms of the empirical/theoretical behavior, technique in obtaining the theoretical results, etc.)?

3. (major)More experiments would be better: I would not say d=60 is very large (though I am not expert in this field). Since the goal is to demonstrate the (asymptotic) theoretical findings using numerical evidence, I would expect more extensive results (in terms of settings, such as dimensionality, distribution parameters, etc.). 

For example, with larger dimension, would you observe better empirical scaling? To be precise, the authors state peak appears at $m \approx d^r/r!$, then I would expect experiments indicating as $d \rightarrow \infty$, the different between $m_{peak}$ and $d^r/r!$ shrinks to zero.

questions: See above in weakness. 

Update: the authors reasonably address my concerns and I have changed the scores.
limitations: Yes. As the authors pointed out in section 7, this works only focus on kernel ridge regression with uniformly distributed data, the generalization of the results is a very important topic. The impact of this work, beyond the interesting phenomena, should be more carefully explored.  

I do not see what is the potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper characterizes the prediction error for kernel ridge regression with dot-product kernels. Different from the previous work that focus on the linear scaling regime (sample size $m$ $\propto$ data dimension $d$), this work focuses on the higher-order scaling regimes ($m\propto d^r$). To establish this theoretical result, the author first study the limiting distribution (MP distribution) of the spectral density of the gram matrix under this scaling regime [Theorem 1]. With the help of this theorem, the author can express the testing error in terms of the MP distribution [Theorem 2]. Experimental results match their theoretical result. Extensions to convolutional kernels are also included. 
strengths_and_weaknesses: **Originality**: Main theoretical result [Theorem 2] itself gives us an understanding of the learning curve of kernel regression for higher-order scaling regimes, extending previous analysis in literature. The intermediate theoretical result [Theorem 1] and supporting proof are also interesting. From my perspective, the key step is to view kernel function as harmonic series and then study the empirical spectral distribution of the non-trivial term from this series. Previous literature [Tao, 2012] only gives similar result for the case $r=1$, but the auhor shows that it holds for all degrees.

**Quality/Clarity**: Presentations of notations, theorem statements, and proofs are crystally clear. Theoretical results are highly non-trivial. Experimental results match their theory surprisingly well. 

**Significance**: Their theory on learning curves applies for dot-product kernel and NNGP/NT kernel with one-layer convolution, which covers many scenarios in machine learning literature.

**Weakness**: 
1. The author commented that it is promising to extend the theory for deep convolutional kernels, but due to the complicated structure of this type of kernel, it is left for future work. I agree on this point but I am looking forward to seeing some updates on deep convolutional kernels in the future.
2. As the author have commented in Section 7, the strong assumption on distributions of input data and the focus on kernel regression setting makes this work less popular. However, I believe similar technique can be used to handle more general settings, which can be finished in the future.
questions: - The uniform distribution on the spherical type of data seems restrictive and existing literature also made similar assumptions. Could the author provide the literature review to compare assumptions on the data distributions for this problem? 
limitations: See weakness part in previous section.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Derive the precise generalization error of kernel ridge regression in the polynomial regime $n=\Theta(d^r)$ for dot-product kernels on unit sphere. The analysis generalizes [Mei et al. 2021] to the case where $r$ takes integer value. The key observation is that the degree-$r$ decomposition of the kernel matrix has a Marchenko-Pastur spectrum, which, together with a random label function assumption, gives a simple description of the generalization error similar to the case of linear regression. Theoretical predictions align with empirical findings.
strengths_and_weaknesses: The generalization error of kernel methods in high dimensions is an important research problem. This submission considers the challenging polynomial scaling setting and completes the picture in [Mei et al. 2021] by covering the $r\in\mathbb{N}$ case. The asymptotic formulae provide a precise description of the multiple descent risk curve (without manipulating the spectrum of the input matrix). I feel that this is an interesting submission that is relevant to the NeurIPS community. 

On the other hand, the current results are also a bit limited for the following reasons: 
1. The analysis is based on the decomposition of kernel matrix into convenient orthogonal bases, which seems to work only for restricted input data (e.g. sphere or hypercube). It is not clear if the similar results can be shown for general settings. 
2. To reduce the bias term to the Stieltjes transform of the decomposed kernel, the high-degree components of the label function is assumed to be random and isotropic. The authors should highlight this limitation in the abstract / introduction. 

[Minor] the reference list for precise learning curves / Gaussian equivalence principle is incomplete. Please update the citations and include more relevant papers (e.g. see related work section of [Loureiro et al. 2021]).  
Loureiro et al. 2021. Learning curves of generic features maps for realistic datasets with a teacher-student model. 
questions: 1. In the experiments, are the coefficients of the label function randomly sampled at each run? Do the theory still provide a good match if the coefficients are fixed? 

2. Can the authors comment on the possibility of extending this analysis to other data distributions such as Gaussian?
limitations: N/A
review_title: null

Meta-review: metareview: The paper studies kernel ridge regression and characterizes its performance theoretically, which are interesting and highly relevant to machine learning venues. The paper is technically sound and the authors have done a good job in the rebuttal period. The paper is worth publishing in NeurIPS.

confidence: Certain
Decision: Accept