Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the generalization properties of simple convolutional neural networks with a single convolutional layer, equipped with some non-linearity, followed by averaged pooling, and then a fully-connected linear layer. The paper builds on the idea of the Neural Tangent Kernel, and studies specifically the generalization properties of the kernels corresponding to the above CNN under various architectural choices (window size, pooling size, stride size) and under the assumption of inputs drawn from the uniform distribution on the hypercube $\\{-1,1\\}^d$. The main findings are that a network as above is suitable for learning "local" functions, i.e., functions that are sums of functions over patches. Specifically, the sample complexity depends on the window size $q$ rather than on input dimension $d$, overcoming the curse of dimensionality associated with learning general classes. Moreover, it is shown that when average pooling is introduced, it corresponds to a bias towards lower-frequency functions as manificested by eigendecomposition of the associated kernel.
main_review: Main strengths:
* Describes the kernel associated with "simplified" CNNs that allows for more precise descriptions of the roles of convolutional, pooling, and subsampling, and thus allows studying how these different operations affect the properties of the network.
* Gives a clear and intuitive characterization of various special cases of the proposed CNN kernel.
* Paper is well written, and places the results well relative to the prior works on the subject.

Main weaknesses:
* While the paper clearly contains novel results, they are more incremental in nature. The techniques used are similar to prior works on NTK, and the derived implications are close to previous results obtained under slightly different settings (as the authors clearly note where applicable).
* Some of the specific implications themselves are not that surprising. For example, in Mhaskar et. al (cited in the paper) where the approximation properties of deep "convolutional" networks is investigated, they also show these structures avoid the curse of dimensionality (in the approximation theory sense) when the target function and hypothesis class share the same structure of "local" functions.
summary_of_the_review: The paper is clearly written and has novel though a bit incremental results, which builds on previous works and contain results that are similar in nature. I am leaning towards marginally accepting the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the Convolutional Neural Tangent Kernel (CNTK) of depth one L=1 for the inputs that are distributed over the hypercube {-1,+1}^d. Under this setting, the paper presents the eigendecomposition of the kernel function. The paper also investigates the generalization properties of kernel regression using the depth one CNTK and bounds the risk for regression.
main_review: The paper uses Gegenbauer polynomial expansion of the kernel function to prove bounds on the sample complexity. In particular, since the CNTK is a dot product kernel, one can write it in terms of Gegenbauer polynomials and then use the eigendecomposition of such polynomials to prove the results of this paper.
I was wondering if one could prove the same bound by Taylor expansion instead. The benefit of using Taylor expansion is that the assumption that the inputs are on the hypercube would be unnecessary. In particular, a degree-p monomial <x,y>^p for x,y \in R^d can be decomposed as <x^{\otimes p}, y^{\otimes p}> where x^{\otimes p} is self tensor products of x. These vectors are in dimension d^p which is the same dimension as what you would get from Gegenbauer expansion. 
summary_of_the_review: I am wondering if one could prove the results of this paper by Taylor expanding the CNTK kernel. The benefit of using Taylor expansion is that the assumption that the inputs are on the hypercube would be unnecessary. In particular, a degree-p monomial <x,y>^p for x,y \in R^d can be decomposed as <x^{\otimes p}, y^{\otimes p}> where x^{\otimes p} is self tensor products of x. These vectors are in dimension d^p which is the same dimension as what you would get from Gegenbauer expansion.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes to study CKNs (defined via random features) which are defined via convolutions on “patches” (e.g., operators that writes (x,y)->\sum_k h(<x_k,y_k>) where $x_k,y_k$ are some patches of $x,y$), and to exploit the fact that those types of kernels are actually related to convolutions on this space, and that one can decompose them on an orthogonal basis of “zonal-like” Polynomials, h(<x,y>)=\sum_n P_n(<x,y>) where $\{P_n\}$ is an orthogonal basis s.t. P_n(<x,y>)=\sum_k Y_k(x)Y_k(y) are some “harmonics-like” functions. Then, one diagonalizes every kernel in this common basis, and all the next bounds exploit this linear structure and a fast decay of the eigen-values, which allows to derive Generalization errors based on this linear structure with a low-dimension. Overall, this is a standard framework (Bach, 2021, 2017) which has been well explained and cited across the text. The link with lazy training is done and the description of the space of L^2 patches(I prefer to phrase it this way rather than L^2 hypercube, I think it’s makes more clear what the authors try to achieve) is well-done, while very similar to L^2(S^{d-1}).
main_review: To be precise:

- I’m a bit curious about a couple of statements of this paper, as for instance pooling/down-sampling to be an important component of CNNs. I understand that for speed purposes, traditional CNNs tend to reduce the resolution of their signal progressively. However, in general, pooling or downsampling are not desirable because they imply a relative loss of information. If the motivation to use those operators is really to “bias the signal toward low-frequencies”, why don’t we apply a low-pass filtering before feeding a RKHS model with signals like images? I think the reason is obvious, because the loss of information is too important. While I could also understand why this could be(and not “requires to be”) progressively incorporated, this paper completely ignores this aspect and simply advocates that pooling/downsampling are important (without saying precisely why)
As a suggestion, one way to deal with the loss of info is to consider the lost-frequencies and to propagate them in the network (for instance, if P is the pooling, I-P could allow to propagate them). Also, note that downsampling can be combined with a high-pass filter (as with conjugate mirror filters, for a wavelet transform) - it seems not obvious to me that this paper is aware of this.

- I think there is a form of paradox in the aforementioned references of the paper, which implies depth and laziness(ie linearization in a neighbourhood of the initialization) are important. First of all, kernel methods which are make “deep” are not restricted to the study of random kernels, see for instance https://arxiv.org/pdf/2003.02237.pdf - Second, (Thiry et al, 2021) seems to be almost identical to (Coates et al, 2011), while obtaining results in the range of (Mairal, 2014; Shankar 2020), without being deep or restricting their model to a specific subspace (beyond learning a linear model). On the contrary, Lazy models (Chizat, 2019), even hierarchical, reach barely the accuracy of non-learned models. Thus, in my view, the simplest instance of CKNs is obtained via (Thiry et al, 2021) (accuracy above 87%), yet I’m not sure how this work brings any new intuitions or explains it. In other words, would it be possible that something simpler than deep CKNs fitted in their RKHS space would also get excellent accuracy while being explained only up to a limited extent by this framework? Would this framework shed some lights on those ideas?

- I’d be surprised that such linear structure is actually present in the data (e.g., the operators to exhibit a fast decay) - this should be numerically demonstrated in order to validate the approach. As this is a motivation of this work, I'd really appreciate to see that actual CNNs/lazy CKNs exhibit this type of behavior. I however understand that taking the data from Unif(Q^d) is a necessary simplifications to write a couple of equations.

[postrebuttal] My opinion, after reading others reviews, is that some claims of the paper are not well motivated or supported because the results are too specific. Also, I unfortunately was only partially convincing by authors' answers.
summary_of_the_review: Overall, I believe the paper is well written, technically correct as I checked most of the proofs or I’ve already seen/dones some sketches of similar ideas. I feel no classification experiment on CIFAR-10(or other dataset) is really needed as this algorithm doesn’t try to derive any optimization algorithms, yet rather try to describe the space of functions associated to this framework. I think however that given that this paper tries to explain deep neural networks, it'd be nice to validate this approach empirically. My further concerns are rather linked to the motivations of this study and the choice of locality and/or laziness and/or some modules.
review_title: null

Meta-review: The paper analyzes convolutional kernels and their sample complexity as compared to different architectures, and in particular the effect of pooling. The analysis proceeds by characterizing the RKHS in this setting (for a distribution on the cube) and using results by Mei and others to obtain separation between different architectures. 
The reviewers appreciated the fact that this is an example worked out in detail, resulting in a clear message about sample complexity gaps between architectures.
However, there was also concerns that some of the conclusions do appear in previous works, so that there is no surprising insight here. 
In future versions, the authors are encouraged to more clearly explain the novel aspects of the paper (as well as where the main technical novelties and tools are).
Decision: Reject