Venue: NeurIPS 2022 Conference

Reviews:

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 paper studies the inductive bias of deep convolutional architectures by studying spectral properties of the corresponding NNGP/GPK and NTK kernels. More specifically, the authors provide decay rates of power series coefficients and eigenvalues of various CGPK/CNTK kernels ("equivariant" where only one location is considered at the output, "trace" which corresponds to a fully-connected last layer, and "GAP", for global average pooling at the last layer). These illustrate how these architectures are biased towards certain functions that depend on few pixels, with preference for neighboring pixels.
strengths_and_weaknesses: The paper is well written, and the problem studied is significant, as it provides new insight on the role of convolutional architectures in deep models. The theory is sound and the results are clearly positioned compared to other works in the area.

Certain results are not fully tight, for instance some lower and upper bounds on eigenvalues are non-matching, which suggests that a tighter theory might be developed. However, this might be difficult to achieve given the complicated form of the studied kernels, so I believe the current results are already good enough for acceptance.
questions: * Regarding the non-matching upper/lower bounds on eigenvalues (e.g. Theorem 3.5), could you elaborate more on which you think is tighter in which setting? It is mentioned that lower bounds may be tighter when only few pixels are considered, while upper bounds are tighter when more pixels are considered -- can this be formalized more precisely?

* In corollary 3.8, for the Tr and GAP kernels, isn't $p_i$ the same for all $i$, given the symmetry of the kernels? If so, is there a better way to illustrate positional biases w.r.t. relative positions?

* Can the arguments on number of GD iterations (paragraph starting at line 226) be made more formal? It would be good to have cleaner propositions for this, as it is not immediate from the statements on eigenvalues.

* [This paper](https://arxiv.org/abs/2112.05611) seems closely related to the present manuscript and the authors should compare to it.
limitations: n/a
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 paper studies the spectral properties of convolutional kernels that are derived from spherical kernels. The inputs are treated as multi-channel, where each channel $\zeta$ corresponds to a pixel from different patches $d$, such that the input space is the cartesian product of the $d$ hyper-spheres. The authors prove that the eigenfunctions of the studied kernels are either the product of spherical harmonics or the shift invariant sum of them, while the corresponding eigenvalue decay polynomially with the frequency of the eigenfunctions. Further, they prove that the lager eigenvalues are associated with the functions localised in the center of the receptive field of the patch. The authors conclude their analysis with evaluating the eigenvalues for the arc-cosine and the neural tangent convolutional kernels.
strengths_and_weaknesses: ### Originality
This is a highly theoretical paper. Spectral analysis of the kernel functions associated with deep neural network architecture with Relu activations has received a lot of attention over the past couple of years. This paper is explicitly focusing on the analysis of the behaviour of the convolutional spherical kernels. In that spirit, the authors extended the analysis from [31] to deep kernel structures with overlapping patches. They also have sufficiently covered the related work and commented on how their work improves upon the existing literature. In my opinion the analysis is novel and provides further insights on the behaviour of the deep neural networks.

### Quality
The theoretical analysis is really good. The authors have demonstrated a high skill on deriving the end result, which I believe is significant.
My concerns are mainly with the results depicted in the plots and the quality of them. I also have some concerns regarding the presentation of the paper in certain parts.

* To be honest I am really baffled with the extremely small values of the eigenvalues in Figure 3 to the point I am questioning my understanding. Coming from the result of Theorem 3.2, the eigenvalues should decay polynomially with the frequency and the degree of that polynomial is mainly determined by $\zeta$. Given that in the computations the patch size is rather small, i.e., $\zeta=2$, why is the value of the biggest eigenvalue at the order of 1e-11? I understand that the important quantity is the ratio of the eigenvalues, but still this is a remarkably small value. It cannot be that the $\tilde{c}$ is that small, right?

* Carrying on with the small values, I would also like to understand the reason behind the really small values of the $b_n$ coefficients in Figure 2. Yes, I expect that for the value of the $\exp(50)$th coefficient will be practically 0. But what happens to the first 5-10 coefficients? Is their value sufficiently large? Is this just a scaling artifact of the plot?

Regarding the presentation:
 
* First of all, I believe that the authors could have been more explicit in setting up the problem. In the beginning of Section 2 there should be explicitly mentioning of what $\zeta, d$ are. My understanding is that $\mathbf{x}$ is a $\zeta \times d$ matrix, where $\zeta$ is the pixels in the patch and $d$ the number of patches. Then the input space of product of $d$ spheres makes sense.
* Despite the effort, Figure 1 is not very helpful in understanding the architecture. I had to rely on the actual maths and the shapes of the involved matrices to be sure of what is going on.
* I do not understand the inline equation of the product of spherical harmonics in section 3.1 line 123. $\mathbf{k}$ is a vector of frequencies, yet we have a product of only the $k_i$ frequency for all the patches that come after $i$. Why don't we have interactions of different frequencies between patches?
* A short discussion right after Lemma 3.1 on the connection between the result and the one from [31] would be extremely valuable for solidifying the understanding.

### Clarity
As I have already said this is a highly theoretical paper. The nature of the topic is already complicated and the required notation, together with the study of convergence bounds, do not make any favours to the reader. Having said that, the authors have done a really good effort to write and explain the paper.

Few minor remarks:
* Last paragraph in page 1 looks like having a smaller fontsize than the rest of the manuscript, please fix that.
* Page 2, line 43, on the comment around intermediate pooling. I suggest you provide further discussion on that, as the introduction of intermediate polling, apart from requiring careful handling to keep the inputs to the next layer always normalised, it also changes considerably the geometry, since it messes with the receptive field at each layer.
* Page 2, line 47. It would be wise to elaborate on what is the shift invariant sum of the spherical harmonics, as these contents have not been introduced yet.

### Significance
The theoretical results presented in the manuscript are significant and a can potentially be a good addition to the literature.
questions: Please see my detailed questions above under the sections of Quality and Clarity
limitations: The authors sufficiently discuss their findings and compare it to similar theoretical results in the literature.
A nice point I would like to see is the computational requirements for evaluating the kernel. That would give the reader an estimate of how feasible would be to use such kernels in practice.
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 paper studies the spectral bias of convolutional neural networks using the neural tangent kernel (NTK) and the Gaussian process kernel. Specifically, the paper derives the eigenvalues and the speed of learning of the eigenfunctions and illustrates how this differs from the fully-connected networks that were studied previously. The kernels studied are not dot product kernels, e.g. as in the fully-connected network analysis.  
strengths_and_weaknesses: [+] Understanding the inductive bias of neural networks is an important topic and convolutional networks are definitely a critical component. 

[+] The paper is well-written overall, offering insights on the spectral bias and the analysis required to achieve this using NTK. 

[-] Despite the attempt to move towards practical networks, the current format of the paper ignores skip connections (that are widely used in most of the practical networks) and also operations such as normalization. The NTK analysis for residual networks (in the fully-connected case) has already been conducted, so it would be a more complete result to have such cases with residual skip as well. 

[-] Even though there is a thorough theoretical analysis, the results illustrate that the convolutional networks learn higher frequency functions more efficiently than fully-connected ones (under some cases). However, there is weak empirical validation of this phenomenon (only Fig. 3). A stronger empirical evidence would make the claims of this work much stronger. 

[-] Minor: The paper requires proof-reading, since there are few errors, especially with parenthesis. For instance, in line 80 there is a parenthesis closing without one opening before. 

Overall, the paper makes a contribution towards understanding the inductive bias of neural networks, which is an important topic. However, there are few structural limitations at the moment, e.g. lack of empirical evidence, or lack of skip connections that are used in practice. 

questions: Is there a typo in line 77 with the inequality? 
limitations: There are no limitations explicitly written in the paper.
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 studies over-parameters CNNs from the perspective of NTK and Gaussian process kernels. A concise analysis of the eigenvalues and eigenfunctions of these kernels are derived. In particular, bounds of the eigenvalues and localization properties of the eigenfunctions are given. They provide a better understanding of the inductive bias in CNNs. 
strengths_and_weaknesses: The strength of this paper is the derivation of the eigenvalue bounds for various kernels with different translation invariant properties (equivariant, non-invariant, invariant), by exploring multi-dot product structures in these kernels. What I find is not very clear is about the positional bias of eigenvalues in Section 3.3 (see questions next). Also the role of the hierarchy, as mentioned in the abstract, is not very clear. More discussions about them are welcome. 
questions: In the introduction, when you talk about inductive bias and spectral bias, do you mean the same thing (line 33-35)? 

As mentioned in the introduction, the eigenvalues are larger for functions that are localized in the center of the receptive field? Are you talking about the invariant kernel case as well (defined from f^GAP)? According to Corollary 3.8, it seems so. It seems to me strange that this could be true as the function f^GAP(x,theta) in invariant to the (cyclic) translation of x. Could you explain more in the text line 280? Also is k_{i+j} defined for i+j <=d in Corollary 3.8?

The function f^Eq is only keeping the first pixel in the output layer, am I right? It is thus not really equivariant if I understood, and this is why you got the previous localized eigenfunctions, am I right?

Could you be more precise on what it means ~ in Theorem 3.2? Does that mean for k-> infty?

What is SH product in line 226?

limitations: NA
review_title: null

Meta-review: metareview: The paper received positive and borderline reviews. A few technical concerns were raised but the rebuttal has addressed those convincingly. There is a clear consensus that the paper makes a valuable theoretical contribution and that it should be accepted. The AC agrees with the reviewer's assessment and follows their recommendation.
confidence: Certain
Decision: Accept