Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This is a paper that studies the theoretical properties of the convolution layer when used with the other common layers in the neural networks.

strengths_and_weaknesses: Strengths:
The authors are motivated to develop theories.

Weakness:

There is no clear intuition behind this paper.  Moreover, I do not find the theories to be of practical use -- the basic assumption of this paper is on something purely theoretical. And this assumption strongly violates the properties of real world data. The numbers reported in the paper are not convincing.

"This paper, we consider the stylized setting of covariates (image pixels) uniformly distributed on the hypercube, and characterize exactly the RKHS of kernels composed of single layers of convolution, pooling, and downsampling operations."

Note that the paper puts its foundation on something wrong. Natural images statistics strongly violates the condition. Figuring out and utilizing the correlation in the real world data is a critical aspect of learning. The following paper provides a discussion for a one layer convolution operation:  Ye, Chengxi, et al. "Network deconvolution." arXiv preprint arXiv:1905.11926 (2019). I wonder if the findings of this paper shares any connections with it?

1. Do not use the RKHS acronym in the abstract.
2. L31 nonlinear convolution?
questions: Can the authors provide a clear intuition of this paper?
limitations: The assumption of this theory is irrelevant to the nature of learning. If the data is uniform random then no learning should be done.
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 statistical and approximation properties of shallow convolutional architectures with varying patch sizes and pooling window sizes, using corresponding kernels. The authors provide both statistical rates in finite dimension, as well as exact asymptotics of the excess risk in high dimensional regimes. The theory is complemented with experiments that illustrate the different scalings.
strengths_and_weaknesses: Understanding the role of neural network architectures for learning specific classes of functions is an important problem, which makes this paper timely and relevant for the community.

This work is part of a series of recent papers (many of them concurrent to the present paper) studying statistical properties of convolutional kernels. The main strength of the present paper is that it provides exact asymptotic expressions of the risk in certain high-dimensional scalings, using the powerful machinery in [38], which ensures that the derived quantities are tight. I believe this by itself makes it worthy of publication.

In addition, it considers architectures with overlapping patches (like [22] but unlike [6,43,48]), with dot-product kernels (unlike [22] which considers less realistic translation-invariant kernels), and localized pooling (like [6] but unlike [22,48]). This makes the setting richer in a sense compared to these other works, although the data distribution considered (on the discrete hypercube) is less realistic. The comparison to these works could be made more precise in the manuscript. The recent work of [Geifman et al.](https://arxiv.org/abs/2203.09255) should also be cited.
questions: * Could you give more details on the difficulties overlapping local pooling? What do you mean by "mixing of eigenvalues," and what is causing this?

* Given that the main goal of the paper is to derive exact and rigorous asymptotics, why did you also include finite-dimensional bounds? I find this to make the paper unnecessarily longer and less focused. Parts of the appendix also seem somewhat superfluous, e.g. section B.1.

Minor points/typos:
- L140-142: do you mean that the uniform distribution on the torus $[0,1]^d$, as considered in [22], is not amenable to a high-dimensional analysis?
- L179: scaler -> scalar
- In Theorem 3, you are using the notation $\ll$ in contrast to Theorems 2 and 5 which use~$0 < \nu < 1$. It would be good to use a consistent notation in each of these results.
limitations: n/a
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: Under the assumption that inputs are from a distribution over the discrete hypercube in d dimensions, the work provides an explanation of why one-layer convolutional kernels outperform fully connected cases for fitting locally translation-invariant functions by showing that the sample complexity required by convolutional kernels is far less than the fully connected case (the degree of efficiency brought by the convolutional kernel is depending on the kernel size). Moreover, the work shows that by adding average pooling, this efficiency could be further improved. The work also shows that the average pooling/downsampling operations facilitate the learning of low-frequency functions.
strengths_and_weaknesses: Strengths:
The overall presentation of the work is clear. The technical contributions of the work and relationships with prior arts are discussed in detail. The numerical experiment provided in the paper is well-aligned with the theoretical results. Overall, the work provides a nice and intuitive way to understand the benefits of each individual component in modern neural networks. 

Weaknesses:
I feel the paper is lacking some practical implications. The data assumption made in the paper is very specific and not realistic. Since the work is dedicated to understanding general components in practical networks, results only on synthetic data and self-defined functions may not suffice.
questions: 1. Since the paper is majorly focused on image classification tasks, is it possible to add some numerical experiments on more realistic data (e.g., CIFAR-10)?

2. (A minor comment on writing) Some abbreviations used in the paper appear before the whole phrase, which makes reading the paper at the beginning a bit hard, for example, the term RKHS is used in the Abstract, Pages 1 and 2, but the full phrase of it first appears in page 3.
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: This paper analyzes the approximation and generalization performance of CNNs using kernel methods, with a focus on their tradeoff. By studying several convolution, pooling and down sampling operations, theoretical results on the sample complexity to achieve a certain approximation accuracy are presented, based on ideal assumptions on the input data distribution. The paper is well-written and the numerical results support theoretical results in some toy examples. 
strengths_and_weaknesses: This paper addresses theoretical problem using quite technical tools. The limitation is that it is not clear how to apply these tools to analyze more general CNNs, as indicated in the conclusion of the paper. 
questions: Below I have a few suggestions to improve the quality of the paper. 

Could you add a picture to introduction for a reader to understand what the CNN model you are considering? It is quite abstract and non-standard to write this model without the notation of the convolution. 

Are you analyzing the NTK kernel of CNNs (CNTK)? Maybe this could be made more clear in the abstract or introduction. 

In Section 1.2, it is unclear what is the difference between the fixed dimension regime and the high-dimension regime. I think the citation 47, Chap 13 is about high-dimension regime, isn’t it? In the latter case, do you mean that the dimension goes to infinity. 

What is the g in assumption A2? Should it be f_* instead of f in Theorem 1, line 229? When you mean q,d large in eq. 6 Theorem 2, would you write o_{q}(1) or o_{q,d}(1)? Shouldn’t the statement of Theorem 2 be probabilistic? 

limitations: NA
review_title: null

Meta-review: metareview: The reviewers appreciated the contributions. Several concerns were raised, and the authors addressed them in their submitted response. 

Accept.
confidence: Certain
Decision: Accept