Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors provide explicit formulas or residual convolutional Gaussian Process Kernels (GPK) and Neural Tangent Kernels (NTKs), bounds on their eigenvalues, and their condition numbers.
As a highlight, they support an empirical observation by Veit et al. (2016) (i.e., that over-parameterized ResNets act like a weighted ensemble of CNNs of various depths). Furthermore, they claim to be the first to establish a relationship between skip connections and the condition number of the kernel matrix. Both derivations suggest possible advantages of residual architectures over vanilla convolutional layers without skip connections.
strength_and_weaknesses: Strengths:
+ Explicit formulas or residual convolutional Gaussian Process Kernels (GPK) and Neural Tangent Kernels (NTKs) are provided.
+ The main insight is provided by Thm. 5.2 and the comparison with the respective convolutional kernels. With their lower bound on the eigenvalues, the authors explain an empirical observation by Veit
et al. (2016): over-parameterized ResNets act like a weighted ensemble of CNNs of various depths.
+ The experiments support the theory and provide some quantitative insights. 
+ The importance of the scaling parameter $\alpha$ for large depth and some corrections to typical assumptions in the literature are discussed. (The authors make a case for $\alpha=1$ for convolutional kernels.)
+ Bounds on condition numbers: It is shown that the lower bound for ResCGPK matrices is lower than that of CGPK matrices.
+ The authors claim that they are the first to establish a relationship between skip connections and the condition number of the kernel matrix.

Weaknesses and open questions:
- The authors only study the NTK regime and thus no feature learning. This limits the practical relevance of their insights. However, this is a common challenge with the analytic approach, which still can provide an intuition for some observed phenomena in practice. 
- What is the additional challenge of considering convolutional residual kernels in comparison with the derivation of fully-connected ones?
- What is the exact additional challenge in the derivation of the bounds on the eigenvalues in comparison with convolutional kernels?
-> It sounds like a minor technical contribution to simply combine derivations for fully-connected ResNet kernels and convolutional kernels.
- What is the rough dependence of $c_1$ and $c_2$ on the depth in Thm. 5.1? This seems to be one of the most relevant questions. If this is not easily derived theoretically, also empirical results could shed light on that issue. (This question is only partially addressed by Thm. 5.2.)
- How sharp is the bound in Thm. 5.2?
- The experiments could be extended in support of Thm 5.2. An analysis of the dependence on the depth $L$ is missing.

Points of minor critique and open questions:
- The need/advantage of considering three different heads could be better motivated on page 4.
- How is the set $\mathcal{R}$ defined in Theorem 5.1?
- How is $C_0$ defined on page 6? Is it also just an existence statement? 
- How is the number of paths $p_i$ scaled in the infinite width limit? Is this quantity not diverging?
- It could strengthen the last result on the condition number to discuss briefly why a slower diverging condition number could help in practice.
clarity,_quality,_novelty_and_reproducibility: The exposition is quite clear overall. In some minor cases, the reader could use some more or repeated definitions of stated variables.
The theoretical support of the empirically observed phenomenon that over-parameterized ResNets act like a weighted ensemble of CNNs of various depths seems to be novel and also does not seem to follow trivially from past derivations of residual fully-connected or vanilla convolutional kernels.
However, the authors should make the technical challenges of their derivations more precise. Currently, it sounds like a minor technical contribution to combine ideas for convolutional and residual fully-connected kernels.
summary_of_the_review: I find the theoretical insights interesting, as they explain empirically observed phenomena. 
They are of relevance for the ICLR community that tries to understand possible advantages of residual structures (in comparison with architectures without skip connections).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper derives explicit formulas for kernels of ResNets' Gaussian Process and Neural Tangent kernels, and provide bounds on their implied condition numbers. 

The main results include
1) with ReLU activation, the eigenvalues of these residual kernels decay polynomially at a similar rate compared to the same kernel when skip connections are not used.
2) residual kernels are more locally biased.
3) the matrices obtained by the residual kernels have better condition numbers than the counterpart of without the skip connections, enabling therefore faster convergence of training.
4) A theoretical justification for the result that over-parameterized ResNets act like a weighted ensemble of CNNs of various depths.
strength_and_weaknesses: Strength:
- An asymptotic bound on the eigenvalues of the kernels of ResNets is given for the first time, which generalized the existing similar bound for that of convolutional networks.
- A new lower bound for the eigenvalues of the kernels of ResNets is given, which implies that the receptive field of ResCNTK is smaller than that of CNTK (without skip connections), thus the ResNet is supposed to be more local biased.
- The author justifies why ResNets converges faster than the normal CNN by utilizing the NTK technology.
- The overall structure and logistics of the paper are good. The formulation and writing of the theorem statements and proofs are well structured and organized.
- The results of experiments match the conclusions derived from theoretical analysis exactly.

Weakness or Questions:
- In Theorem 5.1, the author states that the bound matches the counterpart of the case without skip connections up to constants, and the experiments show that the eigenvalues of ResCGPK are quite close to that of CGPK for the same $k$. The given comparison is between CGPK and ResCGPK, I wonder whether there is any comparison between the eigenvalues of CNTK and ResCNTK ?  Also, this result is verified for some specific function, will the phenomenon that the ratio constants are close to 1 holds true for general functions?

- Theorem 5.2 provides a lower bound of the eigenvalues of ResCNTK. But it seems that there is no strict argument for $\lambda_k$ of ResCNTK being larger than that of CNTK because there is no upper bound for $\lambda_k$ of CNTK. I wonder that which factors would affect the order relationship between them. The author only posted one figure of experiments to qualitatively demonstrate this fact instead of comprehensive quantitive comparison either in numerical or theoretical way.
clarity,_quality,_novelty_and_reproducibility: The overall quality and clarity of the paper is good. The author proposed several spectrum bounds for the ResCGPK and ResCNTK and made a comprehensive comparison between them and the kernels of plain CNN. The technical writing for the theorems and proofs is good and well structured to follow. 

The paper devotes to justify some phenomenons regarding ResNet that are well known empirically but lack of theoretical explanations. This work makes effort to fill this gap using the NTK method, and the obtained some significant results based on spectrum analysis.
summary_of_the_review: The theorems proposed in this paper offer several new bounds for the spectrum of ResNets that is helpful for us to understand the practical behavior of ResNets. It is technically innovative to analyze the ResNet with NTK technology and derive some properties of ResNets like frequency-related behavior and locality bias.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies kernels (GP and NTK) arising from convolutional networks with skip connections, and provides a comparison with those without skip connections. Based on spectral decompositions on products of spheres, the authors make a few findings: (i) the spectral decays are the same as without skip connections, (ii) the skip connections promote a bias towards more localized functions, since the earlier layers play a more prominent role, (iii) when the depth grows, certain parameterizations should be preferred ($\alpha=1$), and the condition number of kernel matrices may be better for residual networks. The results are accompanied by numerical illustrations.
strength_and_weaknesses: Understanding skip connections in CNNs is an important question in the foundations of deep learning, and the present paper provides a comprehensive picture of what role they may play in the context of kernels. This is thus a significant contribution, and I support acceptance.

There are nonetheless a few questions which could deserve more discussion:

* Some of the bounds derived on eigenvalues are not tight, e.g., only lower bounds in Thm 5.2. While the experiments seem to confirm the findings, and suggest the bounds are relevant, is there a way to show upper bounds that also include the $c_k$ quantities?

* In practice, residual networks often involve pooling/downsampling operations in intermediate layers as well, which seem important for good performance (this is also true in convolutional kernels, e.g. in [these](https://arxiv.org/abs/2003.02237) [papers](https://arxiv.org/abs/2102.10032)). Do you have a sense of how these would affect the locality bias in the present paper? Should I interpret your analysis as focusing on a fixed intermediate residual block at a fixed resolution?

* Regarding condition numbers in Section 6.2, this seems to suggest that eigenvalues decay more slowly in the residual case, at least non-asymptotically. Do you have a sense of what could be causing this, and which eigenfunctions might be dominating the spectrum in the residual vs non-residual case? These questions seem important to discuss, since they would give insight on the kinds of target functions for which we can hope that "smaller condition number" => "faster learning" holds.

clarity,_quality,_novelty_and_reproducibility: The paper is well-written. Many of the proof techniques are similar to Geifman et al (2022), but all the findings about residual connections seem novel.
summary_of_the_review: Good paper, interesting and significant contribution.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies how skip connections affect CNNs in the sense of learning theory. The authors investigate this by approximating CNN with kernels based on NTK and the gaussian process. They derive the analytic forms of the kernel and analyze their eigenvalues. 
strength_and_weaknesses: Strengths
- The effect of skip connection is rigorously analyzed in the language of kernels. 
- The eigenvalues of the kernels are evaluated.

Weaknesses
- There's no clear outcome for practitioners. It's not straightforward to utilize the theoretical results for new methods/algorithms/architectures.

clarity,_quality,_novelty_and_reproducibility: The paper is mathematically clear. 

In terms of quality, the paper contains significant theoretical results. 

The topic that the paper addresses is a bit narrow. They only focus on the skip connections, which I feel somehow limits the novelty. 

Reproducibility is OK (There's a minimum experiment). 
summary_of_the_review: The paper provides a solid analysis of the role of skip connections in CNNs. The impact and the novelty, however, are limited.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors provide explicit formulas or residual convolutional Gaussian Process Kernels (GPK) and Neural Tangent Kernels (NTKs), bounds on their eigenvalues, and their condition numbers. As a highlight, they support an empirical observation that over-parameterized ResNets act like a weighted ensemble of CNNs of various depths. Furthermore, they are the first to establish a relationship between skip connections and the condition number of the kernel matrix. Both derivations suggest possible advantages of residual architectures over vanilla convolutional layers without skip connections.

The overall structure and logistics of the paper are good. The formulation and writing of the theorem statements and proofs are well structured and organized. The experiments support the theory and provide good quantitative insights. The paper has a high quality and no major concern. It is a significant contribution to the area of bridging GPs and neural networks.

justification_for_why_not_lower_score: The paper has a high quality and no major concern. It is a significant contribution to the area of bridging GPs and neural networks.
Decision: Accept: notable-top-5%