Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, the authors study some simple convolutional kernels. They show that two or three layers convolutional kernels with polynomial kernels on the higher level and Gaussian pooling provide similar performance as the much more complicated state-of-the-art convolutional kernels (e.g., Myrtle kernel). Motivated by these good performance, they proceed to characterize the RKHS of these kernels, and describe how extra layers and pooling allows to capture interaction between patches with more or less spatial dependency. They then use the RKHS norm and some standard bound on the generalization error to show how choosing an architecture adapted to the target function can improve the statistical efficiency.
main_review: The paper is very well written, with detailed and interesting discussions, which makes it a very pleasant read. I really appreciated that 1) the kernel models studied in this paper are motivated by simulation, showing that they match state-of-the-art performance for kernel methods; and 2) ‘good practice’ (patch whitening, Gaussian filters…) does improve a lot the performance of kernel methods (here, by providing a kernel architecture much simpler than the state-of-the-art kernel), which motivates a theoretical analysis to understand the reason, and hopefully give some clues on the properties of image function classes. 
Here are a few comments and questions:

The approximation results are somewhat difficult to understand, but a lot of discussion is provided to parse them. However, some of the decompositions (1D or 2D discrete Fourier transforms) would gain at being worked out in more details (e.g., writing the computations etc more explicitly). For example, I think the independent regularization for 1-layer CKN, from $T$ (RKHS regularization of the patch function) + from $A$ (spatial regularization from pooling) to be quite nice. Similarly for the 2-layers case. I think those are really good intuitions on the type of regularization expected from pooling + kernels.

Why are the kernel methods so computationally expensive? I understand that one need to invert a $n$ by $n$ matrix, but for $n \approx 50000$ this should still be reasonable. What is the expensive step? Computing the feature map of the exponential kernel on the first layer? In that case, would it not be better to choose a (non-linear) feature map that is easy to compute, instead of the kernel? In general, what approach could help improve the computation of these hierarchical convolutional kernels?

In the examples provided in this work, no architecture achieves better performance than the Myrtle kernel. Do you believe that kernel methods already hit the wall of what data independent methods can achieve? From this work, is there any clue on what to do to improve kernel methods? (This is more open-ended and do not require a response).

From the experiments of this paper, and the characterization of the RKHS, can we understand the interactions etc. that are important to capture in CIFAR10 to get good accuracy. How is it relying on spatial regularities etc?

summary_of_the_review: I think it is a very thorough work, with both lengthy discussions, experiments and theoretical analysis. The question of what accuracy can be achieved by kernel methods is important in its own right, and can potentially inform us on the performance of other methods (CNNs). Also we can hope that understanding theoretically the RKHS of good performing kernels can give us some clue on the properties of the image function classes. For these reasons, I recommend the paper to be accepted.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the RKHS and generalization properties of convolutional kernel networks, the NNGP corresponding to CNNs and the class of kernels that achieve state of the art performance on image classification. Among the theoretical contributions are analysis of the regularization induced by pooling, and interactions between patches captured with iterated convolutions. The paper also includes experimental results on CIFAR10 matching the prior state of the art for a kernel method while using a shallower architecture, as well as some ablations on the size of the convolutional kernels, the size of the pooling filters, and the number of layers.

main_review: Overall, I think the paper makes a valuable contribution towards understanding the ingredients necessary for good kernel performance for image classification. My comments are directed primarily towards improving the presentation of the results for clarity and readability. Comments are roughly in paper order.
- Nit: In the first paragraph of the introduction the authors claim that convolution and pooling operations are “known to be crucial.” This would seem to imply that these operations are necessary for good performance; however, empirical successes indicate only that they are sufficient (perhaps some other totally different architecture could also be effective).
- The last paragraph on the first page discusses NTK and NNGP kernels jointly, without drawing a distinction between the two. This may confuse some readers given that the kernels considered in the paper are purely NNGP kernels (unless I am mistaken here).
- In the bulleted list of contributions, there is some tension between the first two bullets regarding the benefits of depth. The first bullet shows that even a relatively shallow architecture can perform well, whereas the second argues the benefits of increasing depth. After reading the full paper these bullets both make sense (given the size of the pooling filters), but on a first read they seem at odds and might benefit from a brief explanation.
- The third bullet in the list of contributions mentions “certain invariances” which are then not specified until several pages later. It would be helpful to briefly describe the invariances (e.g. spatial smoothness) early on.
- In section 3, I appreciate the periodic interpretations of the results; even more of these high-level “what the result means and why it matters” descriptions would be great. For example, a discussion of the assumption that patches lie on the sphere and the regularization operator T would be helpful. Also, proposition 2 is particularly difficult to parse given the chain of definitions embedded in the proposition statement. Perhaps defining the notation before using it might be easier to read?
- Figure 2 is a bit confusing to parse. What are p and q in this illustration? What are the axes in the illustration? [I think these questions answer each other, but the figure shouldn’t leave me guessing.]
- The last paragraph in section 3 mentions Table 4, but based on the surrounding text I suspect this should reference Table 2 instead.
- The experimental setup in section 5 specifies a one-versus-all classification approach with an exponential kernel with sigma=0.6. How were these design choices made?
- Figure 3: why is this only considering one class? Also, please add x-axis labels and a “takeaway” sentence to the caption. In the main text Figure 3 (left) is described as “learning curves”, but the x-axis is the number of training examples (usually I’ve seen learning curves refer to a plot of MSE vs training time, which wouldn’t make sense for a kernel method.)
- There are a few typos, e.g. “a a one-versus-all approach” in the experimental setup paragraph on page 8, “comparable comparable decays for various depths” in the role of pooling paragraph on page 9, and “patches to captures interactions” at the bottom of page 15.

summary_of_the_review: The paper makes a valuable contribution to our understanding of convolutional networks for image classification, via expanding the theoretical characterization and generalization guarantees of their associated GP kernels, and offering experiments with simple architectures that match the state of the art for a kernel method on CIFAR10. In the main review I offer some suggestions for improving the clarity of the presentation.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyzed convolutional kernels. Experimentally, the authors showed that convolutional kernel formed by shallow convolutional neural networks (2 - 3 layers) performs as well as the state of art deep convolutional kernels (e.g., Shankar et. al.). The authors also provide an exact description of the RKHS functions and their norm, of the one layer convolutional kernel and two layer convolutional kernel with low degree polynomial activation function on the top layer. Finally, assuming that the target function has a specific form, then theoretical results can give the generalization upper bound of kernel ridge regression in terms of the sample complexity; this shows that using a proper architecture can same the sample complexity by a polynomial factor of the input size. 

main_review: Theoretical results on the approximation and generalization of convolutional kernels are limited in the literature. The reason why the convolutional kernel works well for image dataset is an interesting question. This paper made some progress in this direction by analyzing the RKHS of the 1 and 2 layers convolutional kernels. Furthermore, the experimental results are also interesting: a shallow convolutional kernel shares the same performance of deep convolutional kernels on CIFAR10 dataset. 


However, many notations in this paper are not stated clearly, and the presentation is not in a clean way, which makes the paper hard to read. For example, I feel that Proposition 4 would be a very interesting result, but it is not very easy to understand. First, it is hard to find in the paper where h1 and h2 are defined, and what are their dimensions. Second, the proposition didn't state the relationship of rho_X with E[k_1(...)k_1(...)] (I can infer it from Proposition 3, but a Proposition should be more or less self-contained). Finally, it is not very easy to understand the proof of Proposition 4, especially the second part. 

Some other confusing notations: 
1. In Proposition 1, should f(x) = <G, Phi(x)> = \sum_{u \in \Omega} G[u] \phi(x_u) ? (I have similar question in proposition 2) I don't understand the meaning of notation \sum_u G[u](x_u). What is the nature of G? Is it a matrix (what is the dimension) or a function (from where to where)? 
2. Page 5, below the line "Two-layers with a quadratic kernel.", there is a Phi which should be Psi? 


Overall, I feel this paper is very interesting. However, I don't feel that this paper is written clearly. I will only recommend a weak acceptance. 


summary_of_the_review: The results are interesting, but not clearly written.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper aims to study properties of deep convolutional models via the surrogate of simple hierarchical kernels with convolution and pooling layers.
The authors characterise the underlying RKHS and their norms, and provide generalization bounds.
The results imply that convolution operations such as pooling and patches, if present in the data, lead to improve guarantees.
An empirical study both justifies studying these simple kernels in the first place, and illustrates the obtained theoretical results.

main_review: Caveat: the paper is slightly over my head. I made efforts to dig into the high level ideas and proof strategies, but I probably cannot judge many of the aspects the paper contains.

Strengths:

* The paper studies the important question of why, from a theoretical perspective, CNNs are a good inductive bias.
* The idea of using simple kernels and the efficient learning algorithms as a surrogate is very neat, as it allows to employ RKHS theory (characterizing the space, generalization bounds).
* Well written throughout.


Weak points:
* The paper is hard to read if not very familiar with the discussed topics. A few high level "so what" discussions after Prop1/2 might help less familiar readers.
* Little context is provided in Sec 2, maybe move some context from Appendix into main paper?
* Error bars in would be useful as many results are close to each other.
summary_of_the_review: The paper addresses an important question, is well motivated, and carried out very thoroughly.
review_title: null

Meta-review: The paper addresses hierarchical kernels and provides an analysis of their RKHS along with generalization bounds and cases where improved generalization can be obtained. The reviewers appreciated the analysis and its implications. There were multiple concerns regarding presentation clarity, which the authors should address in the camera ready version.
Decision: Accept (Poster)