Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: # Post Rebuttal:

I partly accept the claims of the authors in the rebuttal and have decided to raise my score a little bit to reflect that. I still believe the paper would benefit greatly from clarifications. In particular, I advise the authors to incorporate the changes mentioned in their response to Remarks 1-2 in the rebuttal, as these strengthen the paper in my opinion. As for Remarks 3-4, I disagree with the authors' claim; my point that convolutional neural networks do not provide any benefit over other simpler hypothesis classes in the regime of lazy training still stands and I strongly encourage the authors to omit any reference to neural networks as motivation for studying the problem. I find this reference to be too artificial and somewhat forced.

Lastly, I would like to wish the authors the best of luck in the future.



# Original Review:

The paper studies the expected generalization error when learning in a teacher-student setting where the teacher is a Gaussian random field and the student is a kernel exhibiting a certain convolutional structure. It is shown that under strong assumptions the expected generalization error decays at a rate which does not depend on the input dimension but rather on the filter size of the student. Additionally, experiments are performed to corroborate the theoretical findings in the paper.
main_review: While the results in the paper provide an interesting example of a learning problem that does not suffer from the curse of dimensionality under certain assumptions, I find the assumptions required to be very specific and highly-stylized. Specifically the results hold for either a data distribution that is uniform on a torus or Gaussian, and the required structure of the teacher further limits the setting. Additionally, the results might only hold when taking the sample size and the regularization parameter in their limit. One motivation for studying the problem as presented by the authors is the connection to neural networks trained in the lazy regime. I find this connection to be weak as neural networks trained in the lazy regime are known to essentially train a linear predictor in high-dimensional space where the features are random and depend on the initialization of the weights of the network (e.g. [1]). In light of this, the results in the paper seem to me to stem from an effective dimensionality reduction provided by the teacher's structure. I don't think this explains why convolutional neural networks are more fit to learn this problem than other types of hypothesis classes and therefore does not address the phenomenon discussed in the beginning of the introduction of image classification on ImageNet.



Moreover, I think the paper would benefit from further clarification as detailed below:

- In line 86 it is written that "the measure p(d^dx)" despite the measure not being previously defined, and no discussion on the nature of this choice is made.
- Eq. (9) lacks explanation. What do the expressions in Eq. (9) represent and why are those relevant?



Typos:

Line 87: rigde -> ridge



Citations used:

[1] Yehudai and Shamir, "On the Power and Limitations of Random Features for Understanding Neural Networks".
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors proved that the generalization error for a CNN can be made independent of the data dimension under certain assumptions. They study the problem in a teacher-student framework and the test error proportional to $P^{-\beta}$ with P to be the training set and $\beta$ to be only dependent on the local kernel size of student network. The authors empirically validate this finding. Furthermore they showed that similar learning curve exponent achieved in the ridgeless case can be achieved in kernel ridge regression with decreasing ridge coefficient.
main_review: The main contribution in Theorem 4.1 is super interesting and solid contribution for this community. I went through most parts of the proofs and it checks out. My main concern is readability of this paper in the current form. With a better readability for the ML audience, I can see this work as a excellent contribution. Please see my detailed comments below.

(a) Change the notation $d^dx$ to $\Pi dx$ for better consistency with literature.
(b) In 1.2, missing reference of "Building Bayesian Neural Networks with Blocks: On Structure, Interpretability and Uncertainty", and some early work of Kondor et al..
(c) The replica method in line 101 should be briefly explained for better readability.
(d) Eq. (8)-(9) are completely without context and makes the reader go check [17, 18]. It needs to be better explained.
(e) what is $c_\rho$ in line 106?
(f) In line 112, how to construct a lattice and sample?
(g) Cite NTK in line 119.
(h)  The sketch of proof for theorem 4.1 is appreciated but it is not clear to be why translation invariant kernel is needed? Insight?
(i) I am not sure the necessity of section 6? Motivation?

Overall it is a excellent contribution but needs rewriting for better readability. 
limitations_and_societal_impact: The authors mentioned there is no negative societal impact which I agree with.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the two elements of CNNS, 1. local patch; 2. translation-invariant. Under a teacher-student framework for kernel regression, the authors conclude that (under reasonable assumptions), it is the locality of CNNs that defeats the curse of dimensionality. The exponent $\beta$ in the learning curve (with respect to the sample size) is studied theoretically and empirically verified.
main_review: ** Pros **
1. This paper is very well-written and well-organized. Even though the content addressed is dense, it is still easy to read.
2. The problem studied by the authors is very interesting. The conclusion, i.e., in a teacher-student setting it is the filter locality instead of translation-invariance of convolution that defeats COD, is also significant.
3. The study provides a clearer picture to explain CNN (and in particular, what element of CNN) if the target function can be expressed as a sum of constituent functions depending on locally on the data.

** Cons **
1. Some of the notation in section 2 needs explanation: line 106, what is $c_p$.
2. Equation (5), what is the distribution of the target function $f^*$
3. In line 96, the authors mentioned that "an approximation of $\epsilon$" is derived. Does that mean that (8) and subsequently all the results in the paper (under more general settings) are approximately correct? If that is the case, up to what order?
4. It is interesting to see that weight sharing does not effect the exponent $\beta$. Is there any clue that how weight sharing is going to affect the asymptotic coefficient?

**Review after author response**
The authors have clearly addressed my concerns. My rating remains.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study the generalization error of kernel regression in a teacher-student scenario where the kernels are obtained as NTK of either one-hidden layer locally-connected NNs or convolutional NNs. They consider the teacher as a Gaussian random field of covariance the same kernel as the student kernel but with different parameters, and proceed to characterize the learning curve exponents. Based on a decomposition of the two kernels in orthonormal basis functions, they use recent (non-rigorous) statistical physics predictions to deduce an exponent that can be shown rigorously to be an upper bound in some cases. This exponent does not depend on the ambient dimension d, only on the patch size, and is the same for the two kernels. The authors deduce that locality is the important property that breaks the curse of dimensionality and notice that adding the invariance by translation only lower the prefactor. 
Finally, using a Gaussian universality assumption and a recent framework, they prove a lower bound on the learning curve exponent.  They further check their predictions in numerical experiments on synthetic data.
main_review: Network architecture is believed to play a major role in the good performance of deep neural networks. Yet, theoretical results are severely lacking. In this paper, the authors consider the performance of simple one layer architectures in the kernel regime and show that it beats the curse of dimensionality. I think this is a first concrete step towards understanding the statistical advantages of convolutional neural networks. The paper is well written and the results are discussed. However, I have a few concerns and comments:

(1) While non-trivial, the fact that locality is the important mechanism breaking the curse of dimensionality is not surprising, especially in kernel methods (the learning curve exponent will depend on the eigenvalue decay, which will be set by the local kernels). Given this, it is a bit disappointing that the results are stated for a simplified architecture (non-overlapping patches which makes the RKHS particularly simple, why not use the architecture in the appendix?) and are using non-rigorous arguments. In particular, for these simplified architectures, I believe some classical bounds on KRR will work straightforwardly. 

(2) I believe the predictions of Canatar, Bordelon, Pehlevan (2021) matches pretty well numerical simulations in their papers. Is it the case with convolutional kernels in this setting? Also, it would be interesting to test these kernels on real data: for example, with increasing number of samples, showing how the convergence is much faster (while having larger asymptotic error because of smaller RKHS).

(3) Could you explain more why when the student and the teacher are the same, the statistical physics prediction is an upper bound on $\beta$? 

Overall, I think the paper is interesting, but (while I understand the appeal of statistical physics proofs) the work would be much more convincing with rigorous bounds.


--- After-rebuttal ---

Thank you for the authors for their detailed response. I think this is a very interesting and timely paper, and for that reason I am raising my rating to 7. 
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper addresses a topic which has drawn a fair amount of attention recently, namely: if and how do locality and translation-invariance aid convnets in easing the curse of dimensionality. The paper does so by studying a teacher-student framework for kernel regression (see [4]). The reviewers found the implications of the analysis (i.e., 'locality is important') very interesting, and generally appreciated the analytic technique employed in the paper (modulo standard caveats of the replica methods). That said, the paper provoked considerable discussion among the reviewers regarding the acceptable extent to which conclusions drawn based on the kernel ('lazy') regime should be regarded as valid for ReLU networks, and raised several concerns in terms of presentation, clarity. All in all, I think this is a reasonable paper to accept if there is room.
Decision: Accept (Poster)