A Kernel Perspective of Skip Connections in Convolutional Networks
Authors: Daniel Barzilai
Amnon Geifman
Meirav Galun
Ronen Basri
Venue: ICLR 2023 notable top 5% (2023)

Abstract: Over-parameterized residual networks (ResNets) are amongst the most successful convolutional neural architectures for image processing. Here we study their properties through their Gaussian Process and Neural Tangent kernels. We derive explicit formulas for these kernels, analyze their spectra, and provide bounds on their implied condition numbers. Our results indicate that (1) with ReLU activation, the eigenvalues of these residual kernels decay polynomially at a similar rate compared to the same kernels when skip connections are not used, thus maintaining a similar frequency bias; (2) however, residual kernels are more locally biased. Our analysis further shows that the matrices obtained by these residual kernels yield favorable condition numbers at finite depths than those obtained without the skip connections, enabling therefore faster convergence of training with gradient descent.

Published as a conference paper at ICLR 2023
A KERNEL PERSPECTIVE OF SKIP CONNECTIONS IN CONVOLUTIONAL NETWORKS
Daniel Barzilai, Amnon Geifman, Meirav Galun & Ronen Basri
Weizmann Institute of Science (daniel.ber la amnon. gei fman, me rav. -aau,,, ronen. coconnnbaatte basri @@wei zmann, ac i
ABSTRACT
Over-pat parameterized residual networks are amongst the most successful convo- lutional neural architectures for image processing. Here we study their proper- ties through their Gaussian Process and Neural Tangent kernels. We derive ex- plicit formulas for these kernels, analyze their spectra and provide bounds on their implied condition numbers. Our results indicate that (1) with ReLU activation, the eigenvalues of these residual kernels decay polynomially at a similar rate as the same kernels when skip connections are not used, thus maintaining similar fre- quency bias; (2) however, residual kernels are more locally biased. Our analysis further shows that the matrices obtained by these residual kernels yield favorable condition numbers at finite depths than those obtained without the skip connec- tions, enabling therefore faster convergence of training with gradient descent.
INTRODUCTION
In the past decade, deep convolutional neural network (CNN) architectures with hundreds and even thousands of layers have been utilized for various image processing tasks. Theoretical work has indicated that shallow networks may need exponentially more nodes than deep networks achieve the same expressive power (Telgarsky) 2016; Poggio et al., 2017). A critical contribution to the utilization of deeper networks has been the introduction of Residual Networks (He al. 2016).
To gain an understanding of these networks, we turn to a recent line of work that has made precise the connection between neural networks and kernel ridge regression (KRR) when the width of network (the number of channels in CNN) tends to infinity. In particular, for such a network f(x; 0), KRR with respect the corresponding Gaussian Process Kernel (GPK) K((x, z) Eg [ 0) f(z; 0)] (also called Conjugate Kernel or NNGP Kernel) is equivalent to training the final layer while keeping the weights of the other layers their initial values (Lee et al. (017). Furthermore, KRR with
is equivalent to training the entire network (Jacot et al. 2018). Here x and z represent input data items, @ are the network parameters, and expectation computed with respect the distribution of the initialization of the network parameters.
respect to the neural tangent kernel + (x, z) Es
0f(x:)) 88
(f(20)
We distinguish between four different models; Convolutional Gaussian Process Kernel (CGPK), Convolutional Neural Tangent Kernel (CNTK), and ResCGPK, ResCNTK for the same kernels with additional skip connections. [Yang] (2020): Yang & Littwin (202T) showed that for any architec- ture made up of convolutions, skip-connections, and ReLUs, in the infinite width limit the network converges almost surely to its NTK. This guarantees that sufficiently pver-parameterized ResNets converge to their ResCNTK.
Lee et al. 2011 2020) showed that these kernels are highly predictive of finite width networks as well. Therefore, by analyzing the spectrum and behavior of these kernels at various depths, we can better understand the role of skip connections. Thus the question of what we can leam about skip connections through the of these kernels begs be asked. In this work, we aim do precisely that. By analyzing the relevant kernels, we expect to gain information that is applicable to finite width networks. Our contributions include:

---

Published as a conference paper at ICLR 2023
1. A precise closed form recursive formula for the Gaussian Process and Neural Tangent Ker- nels of both equivariant and invariant convolutional ResNet architectures.
2. A spectral decomposition of these kernels with normalized input and ReLU activation, showing that the eigenvalues decay polynomially with the frequency of the eigenfunctions.
3. A comparison of eigenvalues with non-residual CNNs, showing that ResNets resemble a weighted ensemble of CNNs of different depths, and thus place larger emphasis on nearby pixels than CNNs.
4. An analysis of the condition number associated with the kernels by relating them the so called double-constant kernels. We use these tools to show that skip connections speed up the training of the GPK.
Derivations and proofs are given in the Appendix.
2 RELATED WORK
The equivalence between over parammettmttteeed neural networks and positive definite kernels was made
precise in (Lee et al. 2017 Jacot et al., 2018: Allen-Zhu et al. 2019; Lee et al.] 2019) Chizat
ct al. 2019; Yang 2020) amongst others. Arora et al. (2019a) derived NTK and GPK formulas for
convolutional architectures and trained these kernels on CIFAR-10 10. AAooa et al. (2019b) showed
subsequently that CNTKs can outperform standard CNNs on small data tasks.
A number of studies analyzed NTK for fully connected (FC) architectures and their associated Re- producing Kernel Hilbert Spaces (RKHS). These works showed for training data drawn from a uniform distribution over the hypersphere that the eigenvalues of NTK and GPK are the spherical harmonics and with ReLU activation the eigenvalues decay polynomially with frequency (Bietti & Bach, 2020). Bietti & Mairal (2019) further derived explicit feature maps for these kernels. Geif- man et al. (2220) and Chen & Xu (2020) showed that these kernels share the same functions in their RKHS with the Laplace Kernel, restricted the hypersphere.
Recent works applied spectral analysis to kernels associated with standard convolutional architec- tures that include no skip connections. (Geifmann et al. 2022) characterized the eigenfunctions and eigenvalues of CGPK and CNTK. Xiao] (2022): Cagnetta et al. (2022) studied CNTK with non- overlapped filters, while Xiao (2022) focused on high dimensional inputs.
Formulas for NTK for resiuual,fully connected networks were derived and analyzed in Huang et al. 2020 Tirer et al. (002)). They further showed that, in contrast with FC-NTK and with a particular choice of balancing parameter relating the skip and the residual connections, ResNTK does not become degenerate as the depth tends to infinity. As we mention later in this manuscript, this result critically depends on the assumption that the last layer is not trained. Belfer et al. (202T) showed that the eigenvalues of ResNTK for fully connected architectures decay polynomially at the same rate NTK for networks without skip connections, indicating that residual and conventional FC architectures are subject to the same frequency bias.
In related works, (Du al. 2019) proved that training over-parametrized convolutional ResNets converges to a global minimum. (Balduzzi et al. 2017, [Philipp et al.) 2018) Orhan & Pitkow] 2017) showed that deep residual networks better address the problems of vanishing and exploding gradients compared to standard networks, as well as singularities that are present in these models. Veit al. (0166) made the empirical observation that ResNets behave like an ensemble of networks. This result is echoed in our proofs. which indicate that the eigenvalues of ResCNTK are made of weighted sums of eigenvalues of CNTK for an ensemble of networks of different depths.
Below we derive explicit formulas and analyze kernels corresponding to residual, convolutional network architectures. We provide lower and upper bounds on the eigenvalues of ResCNTK and ResCGPK Our results indicate that these residual kernels are subject to the same frequency bias as their standard convolutional counterparts. However, they further indicate that residual kernels are significantly more locally biased than non-residual kernels. Indeed, locality has recently been attributed as a main reason for the success convolutional networks Favero et al., 20221) Morcover, we show that with the standard choice of constant balancing parame- ter used in practical residual networks, ResCGPK attains a better condition number than the standard CGPK, allowing to train significantly more efficiently. This result is motivated by the work Lfe
et al. 2020]
2

---

Published as a conference paper at ICLR 2023
et al. (2019); Xiao al. (2020) and Chen al. (2021), who related between the condition number of NTK and the trainability of corresponding finite width networks.
PRELIMINARIES
We consider quddi-hhaneel 1-D imput signals x E IR Coxd of length with Co channels. We use 1-D imput signals to simplify notations and note that all our results can naturally be extended to 2-D signals. Let MS (Co, d) = sCo-1 x... SCo-1 S vag"Co-1 be the multi-sphere, so
times
(x1, x.) E MS (Co: d) iff Vi E [d], |x||||==111 For our analysis, we assume that the input signals distributed uniformly on the multi-sphere.
The discrete convolution of a filter w E IR' with a vector v E Rd defined as [w * v]. 1-1 Σドー_" 2 ب [V]++ where 1 S i < d. We use circular padding, so indices [v], with j S 0 and j > are well defined.
We multi-inder notation denoted by bold letters, i.e. n. E No. where N is the set of natural numbers including zero. bn, A E R are scalars that depend on n, k, and for E Rd we let t" 12 ....... 12 As convention, we say that 2 k iff n4 k; for all [d]. Thus, the power series
Σnzol1 1nt should read En220.02200 Uys m2... 1 12
We further use the following notation to denote sub-vectors and sub-matrices. Vi E N, let D; = - o-1 so that [v]p, = [v],_ 2-- -4 Additionally, Vi,1 E N, let D,,'' = Di x D that for a matrix M we can write: MD, = 14 of We use (s.v), = Uj+i
(1 + 1)
to denote the cyclic shift of to the left by i pixels.
Finally, for every kernel IC: Rd x Rdd + I we define the normalized kernel to be K (x, 2) =
K(x.2) Note that K. (x, x) 1, Vx Rd, and K [-1,1.
3.1 CONVOLUTIONAL RESNET
We consider residual, convolutional neural network with L hidden layer (often just called ResNet).
Let x E &oxd and be the filter size. We define the hidden layers of the Network as:
Co w
(x)
1
(0) Lij
* *xj
9
(1) (x)
Lija * x
(1)
VC
VCu
j=1
1100 (x) = 1!(-1 (x) + a
Cv
(1) (1)
(9,0 (1) (x)((x)) 1= -,,,,,, L, i= I=....,
(2)
qpi=
Cr-1
9 (x)
Cu Σ qC-11
will .j و (x), 1= 2..,..,, L, i 1, Ct,
(3)
V
#=1
where Ci N is the number of channels in the l'th layer; is nonlinear activation function, which in our analysis below is the ReLU function; ( E R v E R W ( e BixCoxCi are the network parameters, where W(1), ( are convolution filters of size 1, and v()) is fixed throughout training; Co, Cu E R are normalizing factors set commonly as = 1/Em>> (w)] (for ReLU c, = 2) and 6, 1; a a balancing factor typically set in applica- tions to a 1, however previous analyses of non-coven conoolouulii kernels also considered a L-7 with 0 < > < 1. We will occasionally omit explicit reference to c, and and assume in such cases that G, = 2 and c.. = 1.
As in Geifman et al. (2022). we consider three options for the final layer of the network:
EEa (x;
Eg (L.) (x)
=
VCr
3

---

Published as a conference paper at ICLR 2023
f" (x: = vdVO.
(W"),
((O p(L) (x)
1
jeAP (x:0) = dvCr.
WGAP p(l) (x) I,
where WFa WGGP E ERIXCE WT RLxdd and i (1, E Rd.
ffg is fully convolutional. Therefore, applying it to all shifted versions of the input results in network that is shift-equivariant. f implements a linear layer in the last layer and /GAP imple- ments global average pooling (GAP) layer, resulting in shift invariant network. The three heads allow us to analyze kernels corresponding to (1) shift equivariant networks (c.g., image segmen- tation networks), (2) convolutional network followed by fully connected head, akin to AlexNet Krizhevsky et al. 2017) (but with additional skip connections), and (3) convnet followed by global average pooling, akin to ResNet (He et al. 2016).
Note that ( (x) Rixd and gD)) (x) E &RCi 0 denote all the network parameters, which we initialize from a standard Gaussian distribution as (Jacot et al. 2018).
3.2 MULTI-DOT PRODUCT KERNELS
Following (Geifman al. 2022), we call a kernel K. MS (Co, d)xMS MS (Co, d) - lK multi-dol prod- uct if KC (x, K. (t) where t = ((x"z),
(x" ......... (x" 2) d.d) E [1 (note the over-
load of notation which should be clear by context.) Under our uniform distribution assumption on the multi-sphere, multi-dot product kernels can be decomposed as K. (x, z) Enj Au Ykj (x) Ykj (z), where j.j E Nd. Yiu (x) (the eigenfunctions of KC) are products of spherical harmonies in SCo-1, YkJ (x) I Yk.... (x,) with h; 2 0. J: E [C, k,),, where NCC,, k;) denotes the num- ber of harmonics of frequency k; in SCo-1 For Co = 2 these are products of Fourier series in d-dimensional torus. Note that the eigenvalues 2 are non-negative and do not depend on j.
Using Mercer's Representation of RKHSs (Kanagawa et al. 2018), we have that the RKHS He of IC is
{ f Σ RakyYkJ ll
akj Ak
00 }.
Hx :=
kj
For multi-dot product kernels the normalized kernel simplifies (t K(()) x(I)'
where i
(1,..., 1)" Rdd K. and K. thus differ by a constant, and they share the same eigenfunctions and their cigenvalues differ by a multiplicative constant.
4 KERNEL DERIVATIONS
We next provide explicit formulas for ResCGPK and ResCNTK.
4.1 RESCGPK
Given a network f(x; 9), the corresponding Gaussian process kernel is defined as Eg [f f)); Below we consider the network in Sec. 3.1 which can have either one of three heads, the equivariant head, trace or GAP. We denote the corresponding ResCGPK by x x((L)
and (L) Definition 4.1. Let x, E xCox and f be residual network with L layers. For every S < L
GAP- where L denotes the number of layers. We proceed with the following definition.
(and is an arbitrary choice of channel) denote by
(!) 3.j
(x,z) Eg
9i
(1) (x)
9
(z)
(4)
Σ (x.x)
Σ (x,z)
A (1) 33
(x, z) =
(5)
(z,x)
x j' (z,z)
4

---

Published as a conference paper at ICLR 2023
KD (x.2)
3.j
CoCo
E (ww)) (o.4 Si (x,2)
(o (
K00) iá
(x, z)
Cycw
(ā (
(u,0)~
O.A 3,5 (xzz)
where ē is the derivative of the ReLU function expressed by the indicator 1=20-
Our first contribution is to give exact formula for the ResCGPK. We refer the reader to the appendix for the precise derivation and note here some of the key ideas. We give precise formulas for Σ, K and K and prove that
L
K (x, [1) (x, 2) +
Σ tr
(Kbi, (x,2))
qGe 1=1
This gives us the equivariant kernel, and by showing that K- (x, = Σ Eq 852
and K (x,2) 2 Eis'= K (s)x.8y2) obtain precise formulas for the trace and GAP kernels.
For clarity, we give here the case of the normalized ResCGPK with multi-sphere inputs, which we prove to simplify significantly. The full derivation for arbitrary inputs is given in Appendix AA.
Theorem 4.1. /Mulli-Spheree Case] For any x, E MS (Co, d) let = ((x2 1.1 ((xx2)
(x d.d)
V1-p² (x-006 (())) Then,
E [-1,1] 1j. Fixing Go = 2, Cw = and let Kı (w)
(1) Keg (t) 1 + a²
t1
a
Σ
Ki (+1+k)
km 1
R/0 (t)
R(t (t) + a
Σ
(K(t (Snnett))
K1
1+ a²
q²
k=
N==-"
4.2 RESCNTK
For x, 2 E RCoxdd and f(x;0) an I. layer ResNet, ResCNTK is defined as E ( [0(x00) 0z(z))) )
Considering the three heads Sec. 3.1 we denote the corresponding kernels by 11 O and
OLL) depending on the choice of last layer. Our second contribution is providing a formula for the ResCNTK for arbitrary inputs.
Theorem 4.2. Let x, Coxd and be residual network with L layers. Then, the ResCNTK for f has the form
L
d
xx 2) = K(L (x, + Eg
(L)
pli) (x, 2) (Ir (I=(K(b) (x,2) 1. (x,2) + Dr.o (x, (x.2)))
1=1 p=1
where V1 Sj s d, p(()) (x,z)
1:=1
for 1 -
cw
9-1
P/ 2x = pflt1)
(x, z) + a²
Σ
K
(1+1]
jtkjth (x,z)
p(++1)
(x, 2).
q²
j+b+8
k=-
9-
k k==
The Tr and GAP kernels are given by 0//) (x,z) 1/2 ش
o (s,x, and (L)) (x,z)
1. 2z Ejs'= =1 ((L) (5)x,8;22)
5

---

Published as a conference paper at ICLR 2023
5 SPECTRAL DECOMPOSITION
Ki and Eg are multi-dot product kernels, and therefore their eigenfunctions consist of spherical harmonic products. Next, we derive bounds on their eigenvalues. We subsequently use a result due to (Geifman et al. 2022) to extend these to their trace and GAP versions.
5.1 ASYMPTOTIC BOUNDS
The next theorem provides upper and lower bounds on the eigenvalues K((L) or (LL) Theorem 5.1. Let x,z z E MIS (Co, d), where d denotes the number of pixels and Co denotes the number of input channels for each pixel. The eigenvalues d of either K-LL) or @( satisfy
Eq
II iER
2v 2va -3) Ak S C2
II
Kg (Co+2x6-3)
C1
VER
where Vo 2.5 and Up is 1 +
3 for ResCGPK and 1 + Idl for ResCNTK. C1, 61,02 > are constants
2d
that depend on L. The set R denotes the receptive field, defined as the set of indices of input pixels that affect the kernel output.
We note that these bounds are identical, up to constants, to those obtained with convolutional net- works that do not include skip connections (Geifman et al. 2022), although the proof for the case of ResNet is more complex. Overall, the theorem shows that over-parameterized ResNets are biased toward low-frequency functions. In particular, with input distributed uniformly on the multi-sphere, the time required to train such a network to fit an eigenfunction with gradient descent (GD) is inversely proportional to the respective eigenvalue (Basri al. 2020 Consequently, training net- work to fit a high frequency function is polynomially slower than training the network to fit a low frequency function. Note, however, that the rate of decay of the eigenvalues depends the number of pixels over which the target function has high frequencies. Training a target function whose high frequencies are concentrated in few pixels much faster than if the same frequencies are spread over many pixels. This can be seen in Figure [ which shows for a target function of frequency k in m pixels, that the exponent (depicted by the slope of the lines) grows with m. The same behaviour is seen when the skip connections are removed. This is different from fully connected architectures, which the decay rate of the eigenvalues depends on the dimension of the input and is invariant to the pixel spread of frequencies, see (Geifman et al. 2022) for comparison of the eigenvalue decay for standard CNNs and FC architectures.
5.2 LOCALITY BIAS AND ENSEMBLE BEHAVIOR
To better understand the difference between ResNets and vanilla CNNs next turn to fine- grained analysis of the decay. Consider an l-layer CNN that is identical to our ResNet but with the skip connections removed. Let pi"' be the number of paths from input pixel i to the output in the corresponding CGPK, or equivalently, the number of paths in the same CNN but in which there is only one channel in each node..
Theorem 5.2. For both 0%% or ((L)) there exist scalars A > 1 and ct > O s.t. letting Ck.1 =
II m kz) for every 1 < S L and ck Σl= Ok,. it holds that
A Ck
k
Co-2
1=1
k2
The constant Ck differs significantly from that of CNTK (without skip connections) which takes the form CK (Geifman et al. 2022). In particular, notice that the constants in the ResCNTK are (up to scale factors) the sum of the constants of the CNTK at depths 1,..., L. Thus, a major contribution of the paper is providing theoretical justification for the following result, observed empirically in (Veit et al. 2016): over-parameterized ResNets act like weighted ensemble of CNNs of various depths. In particular, information from smaller receptive fields is propagated through the skip connections, resulting in larger eigenvalues for frequencies that correspond to smaller receptive fields.

---

Published as a conference paper at ICLR 2023
k
Frogaancy
kelkcckal
(l..0.
-5
log (4x
-10
-20
log (k1)
11
log(k2)
Figure 1: Left: The eigenvalues of ResCGPK (filled circles and solid lines) computed numerically for various eigenfunctions, compared to those of CGPK (empty circles and dashed lines). Here = 3. q = 2, d = 4 and the output head is the equivariant one. The slopes (respectively, -5.25, -6.8, -8.5, -9.8 for CGPK and -5.3, -6.84, -8.77, -9.85 for ResCGPK) approximate the exponent for each pattern. Notice that the slope increases for eigenfunctions involving more pixels. Right: Additional eigenvalues of ResCGPK. Notice that the eigenvalues for eigenfunction involving nearby pixels (in red) are larger compared to one involving farther pixels (in blue).
(a) ResCNTK
(b) CNTK
(c) ResNet
(d) CNN
Figure 2: The effective receptive field of ResCNTK (left) compared to that of actual ResNet and to CNTK and CNN (i.e., skip connections). We followed (Luo et al. 2016) in computing the ERF, where the networks are first trained on CIFAR-10. All values are re-scaled to the [0,1] interval. We used L in all cases.
Figure shows the eigenvalues computed numerically for various frequencies, for both the CGPK and ResCGPK. Consistent with our results, eigenfunctions with high frequencies concentrated in a few pixels. c.g., k (k, O, O, 0) have larger eigenvalues than those with frequencies spread over more pixels, e.g., k = (k:, k k, k). See appendix for implementation details.
Figure 2 shows the effective receptive field (ERF) induced by ResCNTK compared that of network and to the kernel and network with the skip connections removed. The ERF is defined be (x; 0)/0x for ResNet (Luo al. 2016) and Ob x)/0x for ResCNTK. A similar calculation applied to CNN and CNTK. We see that residual networks and their kernels give rise increased locality bias (more weight the center of the receptive field (for the equivariant architecture) or to nearby pixels (at the trace and GAP architectures).
5.3 EXTENSION TO TR AND fGAP
Using (Geifman et al. [Thm. Thm. 3.7], we can extend our analysis of equivariant kernels to trace and GAP kernels. In particular, for ResCNTK. the eigenfunctions of the trace kernel are a product of spherical barmonics. addition, A denote the eigenvalues of (L2) then the eigenvalues of off2 are X - >s,ki i.c., average over all shifts the frequency vector This implies that for the trace kernel, the eigenvalues (but not the eigenfunctions) are invariant to shift. For the GAP kernel, the cigenfunctions are J Σd=1 Yo.k.e.j. i.c., scaled shifted sums of spherical harmonic products. These eigenfunctions are shift invariant and generally span all shift invariant functions. The cigenvalues of the GAP kernel are identical to those of the Trace kernel. The cigenfunctions and eigenvalues of the trace and GAP ResCGPK are determined the eigenvalues for the trace and GAP kernels decay at the same rate their equivariant counterparts,
a similar way. Finally, we note that

---

Published as a conference paper at ICLR 2023
and likewise they are biased in frequency and in locality. Moreover, while the equivariant kernel is biased to prefer functions that depend on the center of the receptive field (position biased), the trace and GAP kernels are biased to prefer functions that depend on nearby pixels.
STABILITY AT LARGE DEPTHS
6.1 DECAYING BALANCING PARAMETER
We next investigate the effects of skip connections in very deep networks. Here the setting of balancing parameter a between the skip and residual connection (2) plays critical role. Previous work on residual, non-convolutional kernel Huang et al. (2020); Belfer et al. (00TT) proposed to use a balancing parameter of the form a = --> for 7 E (0.5, II, arguing that a decaying a contributes to the stability of the kernel for very deep architectures. However, below we prove that in this setting as the depth tends to infinity, ResCNTK converges to a simple dot-product, k(x, z) = 1-layer, linear neural network, which may be considered degenerate. We subsequently further elaborate on the connection between this result and previous work and provide more comprehensive discussion in Appendix [F]
x"z, corresponding
Theorem 6.1. Suppose
- with E (0.5, 1].
Then, for any t E [-1,1] it holds that (1, 14)
D1,1 (t) 11 and likewise Kety (t) L-000
Clearly, this limit kernel, which corresponds to linear network with no hierarchical features if undesired. A comparison to the previous work of Huang et al. (2020); [elferr et al.] (2021), which addressed residual kernels for fully connected architectures, is due here. This previous work proved that FC-ResNTK converges when tends to infinity to a two-layer FC-NTK. They however made the additional assumption that the top-most layer not trained. This assumption turned out to be critical to their result result-training the last layer yields a result analogous to ours, namely, that as L tends infinity FC-ResNTK converges which we do not train the last layer we will get that the limit kernel is the CNTK corresponding to a two-layer convolutional neural network. However, while a two-layer FC-NTK is universal, the set of functions produced by a two-layer CNTK is very limited; therefore, this limit kernel is also not desired. We conclude that the standard setting of a is preferable for convolutional architectures.
simple dot product. Similarly, if we consider ResCNTK in
6.2 THE CONDITION NUMBER OF THE RESCGPK MATRIX WITH a = 1
a 1. For ResCGPK and CGPK and any training distribution, we use double-constant matrices (O'Neill, 202T bound the condition numbers of their kernel matrices. We further show that with any depth, the lower bound for ResCGPK matrices is lower than that of CGPK matrices (and show em- pirically that these bounds are close to the actual condition numbers). [ee et al. (2019); Xiioo et al.) 2020); Chen et al. (202I) argued that smaller condition number of the NTK matrix implies that training the corresponding neural network with GD convergences faster. Our analysis therefore in- dicates that GD with ResCGPK should generally be faster than GD with CGPK. This phenomenon may partly explain the advantage of residual networks over standard convolutional architectures.
Next we investigate the properties of ResCGPK when the balancing factor
Recall that the condition number of matrix A > 0 is defined as p( : Amax/ Amin- Consider an X n double-consten matrix Bi,, that includes à in the diagonal entries and b in each off- diagonal entry. The eigenvalues of Bj,, are A = b b + nb and X2
An, - b. Suppose ; = 1,0 < b E 1, then B1, is positive semi-definite and its condition number is (B,,,) = + mb This condition number diverges when either = or n tends to infinity. The following lemma relates the condition numbers of kernel matrices with that of double-constant matrices.
1-8-
Lemma 6.1. Let A E 5ax= (n 2 2) be normalized kernel matrix with Σij, Aij 2 0. Let B(A)= = BI. with b = I Enjj Auj and e = sup, Ejti
Ais - B(A)g)) Then,
1. p (B(A)) S ((A).
2. Ifc < Amaa (B(A)) then p(A) < Aunia (B(A)) -E
Amaz! Bii))
8

---

Published as a conference paper at ICLR 2023
KesEUue Bourdss
5.-
05
Figure 3: The condition number of ResCGPK-Tr (solid blue) function of depth compared to that of CGPK- -r (solid red) and the corresponding lower and upper bounds (dashed lines) computed with 100.
where Amax and Amin denote the maximal and minimal eigenvalues of B(A).
The following theorem uses double-constant matrices to compare kernel matrices produced by ResCGPK and those produced by CGPK with no skip connections.
ResCUPK and KCGF respectively denote kernel matrices for the normalized trace kernels ResCGPK and CGPK of depth L. Let B (K)) be a double-constant matrix defined for matrix K as in Lemma 6.1 Then,
Theorem 6.2. Let K
R(L) Reicork
- -B (K (ReICGPKK
11,
0 and | - (Rear))
O.
L-000
+000
2. p B (Rheecopk)
oo and
p B (Keepx)
1-000 o0.
L+00
3. Bhe E E.s.V. VL Lo p (BB (KReccOP)
(B(Kuuccca (L) < (B (K(Oe))
L Kescorkk) and B kCOpk) diverge as 0o, the condition number of (Riti (RsCCPK)) is smaller than that of (RCEex) for all T.> Lo- (To is the minimal I, s.t. the entries of the double constant matrices non-negative. We notice in practice that Lo = 2.) We can therefore use Lemma 6.1 to derive approximate bounds for the condition numbers obtained with ResCGPK and CGPK. Figure 3 in- deed shows that the condition number of the CGPK matrix diverges faster than that of ResCGPK and is significantly larger at any finite depth L.. The approximate bounds, particularly the lower bounds, closely match the actual condition numbers produced by the kernels. (We note that with training sampled from a uniform distribution on the multi-sphere, the upper bound can be somewhat improved. In this case, the constant vector the eigenvector of maximal eigenvalue for both A and (A), and thus the rows of A sum to the same value, yielding p(A) <
The theorem establishes that, while the condition numbers of both B
k
Amaay (B(A)) with
Auiia (B()))-
A B( We used this upper bound in our plot in Figure
To the best of our knowledge, this is the first paper that establishes a relationship between skip connections and the condition number of the kernel matrix.
CONCLUSION
We derived formulas for the Gaussian process and neural tangent kernels associated with convo- lutional residual networks, analyzed their spectra, and provided bounds on their implied condition numbers. Our results indicate that over-parameterized residual networks are subject to both fre- quency and locality bias, and that they can be trained faster than standard convolutional networks. In future work, we hope to gain further insight by tightening bounds. We further intend to ap- ply our analysis of the condition number kernel matrices to characterize the speed of training in various other architectures.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This research was partially supported by the Israeli Council for Higher Education (CHE) via the Weizmann Data Science Research Center and by research grants from the Estate of Tully and Michele Plesser and the Anita James Rosen Foundation.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242 252. PMLR, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems, 32, 2019a.
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the power of infinitely wide deep nets on small-data tasks. arXiv preprint arXiv:1910.01663, 2019b.
David Balduzzi, Marcus Frean, Lennox Leary, JP Lewis, Kurt Wan-Duo Ma, and Brian McWilliams. The shattered gradients problem: If resnets are the answer, then what is the question? In Interna- tional Conference on Machine Learning, pp. 342-350 PMLR, 2017.
Ronen Basri, Meirav Galun, Amnon Geifmann David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for imput of non-uniform density. In International Conference on Machine Learning, pp. 685-694. PMLR, 2020.
Yuval Belfer, Amnon Geifman, Meirav Galun, and Ronen Basri. Spectral analysis of the neural tangent kernel for deep residual networks. arXiv preprint arXiv:2104.03093, 2021.
Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. arXiv preprint arXiv:2009. 143997 2020.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kemels. Advances in Neural Information Processing Systems, 32, 2019.
Francesco Cagnetta, Alessandro Favero. and Matthicu Wyart. How wide convolutional neural net- works learn hierarchical tasks. arXiv preprint arXiv:2208.01003, 2022.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. arXiv preprint arXiv:2009. 10683, 2020.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: theoretically inspired perspective. arXiv preprint 15Xiv:2102.11535, 2021.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. Advances in neural informa- lion processing systems, 22, 2009.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. Advances in neural information processing systems, 29, 2016.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675- 1685. PMLR, 2019.
Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse of dimen- sionality in convolutional teacher-student scenarios. Advances in Neural Information Processing Systems, 14:9456-9467,
2021. 2021
10

---

Published as a conference paper at ICLR 2023
Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. cambridge University press, 2009.
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the laplace and neural tangent kernels. Advances in Neural Information Processing Systems, 33:1451-1461, 2020.
Amnon Geifman, Meirav Galun, David Jacobs, and Ronen Basri. On the spectral bias of convolu- tional neural tangent and gaussian process kernels. arXiv preprint arXiv:2203.09255, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Kaixuan Huang, Yuqing Wang, Molei Tao, and Tuo Zhao. Why do deep residual networks generalize better than deep feedforward networks? neural tangent kernel perspective. Advances in neural information processing systems, 33:2698-2777 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- cralization in neural networks. Advances in neural information processing systems, 31, 2018.
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv:1807.02258. 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. Communications of the ACM, 60(6):84-90, 2017.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint 2017.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Jachoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: empirical study. Advances in Neural Information Processing Systems, 33:15156 13:15156-15172 15172, 2020.
Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard Zemel. Understanding the effective receptive field deep convolutional neural networks. Advances in neural information processing systems, 29, 2016.
Rachid Marsli. Bounds for the smallest and the largest cigenvalues of hermitian matrices. Int. J. Algebra, 98):379-394, 2015.
Ben O'Neill. The double-constant matrix, centering matrix and equicorrelation matrix: Theory and applications. arXiv preprint arXiv:2109.058/4 2021.
A Emin Orhan and Xaq Pitkow. Skip connections eliminate singularities. 1rXiv:1701.09115, 2017.
arXiv preprint
George Philipp, Dawn Song, and Jaime G Carbonell. Gradients explode-deep networks are shallow- resnet explained. 2018.
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can detp-but shallow-networks avoid the curse of dimensionality: a review. Inter- national Journal of Automation and Computing, 14(5):503-519, 2017.
Aidan Schumann. Multivariate bell polynomials and derivatives of composed functions. arXiv preprint arXiv:1903.03800 2019.
Shai Shalev-Shward et al. Computational separation between convolutional and fully-connected networks. In International Conference Learning Representations, 2020.

---

Published as a conference paper at ICLR 2023
Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pp- 1517-1539. PMLR, 2016.
Tom Tirer, Joan Bruna, and Raja Giryes. Kemel-based smoothness analysis of residual networks.
In Mathematical and Scientific Machine Learning, pp. 921-954. PMLR, 2022.
Andreas Veit, Michael J Wilber, and Serge Belongie. Residual networks behave like ensembles of
relatively shallow networks. Advances in neural information processing systems, 29, 2016.
Christopher S Withers and Saralees Nadarajah. Multivariate bell polynomials. International Journal of Computer Mathematics, 87(11))2607-2611, 2010.
Lechao Xiao. Eigenspace restructuring: a principle of space and frequency in neural networks. In Conference Learning Theory, pp. 498844 PMLR, 2022.
Lechao Xiao, Jeffrey Pennington, and Samuel Schoenholz. Disentangling trainability and general- ization in deep neural networks. In International Conference on Machine Learning, pp. 10462- 10472. PMLR, 2020.
Greg Yang. Tensor programs ii: Neural tangent kernel for any architecture. arXiv preprint arXiv:2006. 14548, 2020.
Greg Yang and Etai Littwin. Tensor programs iib: Architectural universality of neural tangent kernel training dynamics, In International Conference on Machine Learning, pp. 11762-11772. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2023
APPENDIX
Below provide derivations and proofs for our paper.
A DERIVATION OF RESCGPK
In this section, we derive explicit formulas for ResCGPK. We begin with a few preliminaries. As in (Jacot al. 2018), assume the network parameters 0 initialized with standard Gaussian distribution, N (0, T). Therefore, at initialization, for every pair of parameters, 0, 0z.
E [ 0g] = 6:j-
(8)
We note that Lee al. 2019) proved the convergence of network with this initialization to its NTK. For a vector V. we use the notation vs to denote an entry with arbitrary index.
A.1 A CLOSED FORMULA FOR K AND K
c and Ki VI-a++ (=--a la)))
For u [-,, let nu(u)
be the arc-cosine
kernels defined in Cho & Saul (2009).
Daniely et al. (2016) showed that
K( (x, z)
CoCu
E( (x, x) Σ(0 (z, z)r1 (Σ (x)
(9)
2
and
k( (x, 2)
CoCar
(5(!1) (x,2)).
(10)
2
where KO) and K00 are defined in 6 and 7 and Cu. Cu are defined in Sec. 3.1
A.2 RESCGPK DERIVATION
Theorem A.1. For an L-layer neural network f and x, z Coxd
(1) 3.5"
(x, (x,z) 2)
1
(x
(x"2)
Co
+ a²
(2) (x,z)
Cv
[x)) si3
(x,
Σ
k(())
jandt to (x)
tr
38
q
q2
k=
For 3 3515
1=1
33 (x, (x, + a²
x ( (x,2)
= (x,2)= x((-1)
Σ
ir
b (x,
K (1-1
k=- m
Finally, for the output layer
a
x(6)) (x,z) = I11l (x, z) +
Σ rr (000 (xxzz)
gCw
1=1
1 d
k2fl) (x,2)
(L)
(s x, s,z)
d
Eg
j=1
d Σ
xol (x,2)
k
8,
8s 8y
d
13

---

Published as a conference paper at ICLR 2023
Proof. We begin by deriving formula for _()(x,)) The case of = is shown in Lemma
A.1
For 2 < l S L, the strategy is to express E
Pi 9'y' (z) using E [eet f(l-1) (x) fer (z)
and vice versa (which we can do using Lemma
A.2
This way we derive an expression for
((l-1) (x) fll (z) in Lemma (A.3) and subsequently get:
E Sed
Ct-1
Pi (x)
(1)
(1) [2)
Cu
Σ
festh (x) 1ol- (2)
Lemma 2
qCi-1
k=
c=1
Ct-1
Cw
Σ
211-2) (x) sal + (z)
+
Lemma
4.3
gCz-1
o=l
k
Denote by A
Cl-1
1=1
agg ( 1
+ a² CyCw
Σ
E o (1---)) (x)
astk+x a (9a-2) (2)
C
k=
A + 2 CpCu
g (1)-1)(( (x)
*sth+h" o (gl-t)
E a
nnr -5'thtK
k,k'
9-1
= A +
tr [ 11
(x, (x)
+'
If / > 2 then using Lemma (A.2) we obtain A = E (1-1)
gij
(x) (1-1)
9 (z)
= (1(111)
(x, z). Other-
15
wise if = 2 then using Lemma A.1 we obtain A = Sw tr
D'y (x,
(())
a
We leave the three output layers to lemma A.4
Lemma A.I.
E
(0) (x) 5 (x) E 0
(x)
(1)
(2)
1
(xT 2) ir
Co
Proof. For ( we have:
Co Σ
[(I)
(x,z) 2) =
E
Dif (x)
(1) (1)
96g (z)
Co
w
xi,
1.1,
xi
w() (.
111=1
Σ
E
( (1) (()) L.1,
E
X1,
1
(x (xTzz 2) 338'
Co 1,1=1
Co
For f(2) the proof is analogous, by simply replacing W11) with (
Lemma A.2. v2 = L. s C₁ 1 S أ..ه S d, we have:
E
(1) Dig (x) (x)99)/ (2) 0, CC-1
Cu
Σ Σ
E
fefts (x) {(-
+k (2)]
Proof.
C1-1
Cl-1
E
(1)
(x)
(1)
(z)
Cw E
Σ
w
!1
((11)) (x)
Σ
w(l)
((--)) (z)
C
6=
5
14

---

Published as a conference paper at ICLR 2023
Cm
E
w
w
E
fasth (x)
f2 (z)
90l-1
o, =1
C1-1
Cu
E
(aith (x) 1 (z)
(I))
Equation
gCI-1
k=
Lemma A.3. v1 IISISLI 1, s0,1is Sd, we have:
E
1 (2) 1 (x)
E 5 (x) 11-1) (2)
ta 25 Σ 1 o (1
(000 (2)) +
*
Proof.
Using the definition for / (Def. 2.
we get the expression:
E
{ (x)
1 (z)
E
(1--1)
(x)
1/
p((-1) (z) +
C2
C₁
E
ij
(1 (1-1)
(x)
*
_ (z))
+E
Fig'
(z)
v(l) hor o (0 (xx)
+
Denote
Denote by B2
C₁
+a
2 Cu 1
E
v!I) Go,t
a (o." (x)
be * 9 (z)
(1)
q Ci
Denote by A
We will deal with this expression in parts. First, for B₁ we get:
C
B1 = Σ
ΣE
E
(1-1)
(9.)) (z)
0,
k+
2
c,j' +b
k= k=-
where the rightmost equality follows from 8 and the fact that E [ mean in expectation in
every index. Analogously, we also get BN = 0. Opening A and using Equation ( we get:
C
Σ
k+ o (90)
Vi+=gld of o (9 (z)
A
E
G
eoft
c d'
c=1
E
σ (x)
cott a +R
(2) (x)
o (g0
a
jithh
n.5 +
k=
Overall, we obtain
E Ji
( (x)
10 (2)]
E [ (x)
2c [1)
// (1-1) (z)
F
a (g
(z))
④ k= ديع
n -k
15

---

Published as a conference paper at ICLR 2023
Lemma A.4.
a²
1.
(()) KEg (x, = E1 (x, z) +
Σ 1r
(Ko,, (x,
gCm
Proof. We start by proving the case for x Observe that:
Eg [ (x: 0) fBe (z;
= CL
E
W
1,1
(x) (z)
1,==1
1 Ct
C₁
Σ o E
1 xx) [3) (z)
Σ
14 (x) 54 (2)
CL
C2
1,1=1
1=1
Applying Lemma A.3 recursively we obtain
Eo
[B (x; 0) (2)
Cl
o (0f (x)) 22th )
1 (((-11 (x) 1 (z)
+ 2
Cv
Σ
E o (x00(x)
CL
q k=
,,1+
i=1
Cz
a² tr (K(f) (x, .2
E
(()-
(x) ((b-1) (z))
CL i=l
gcw
Cz
E
(2-
(x)
(l (z)
+
Σ tr (KDr. (x, 2
Lemma
CL
gCw Intoll
Applying Lemma A.3
recursively for all layers we obtain
Eo B (x; Fa (2; = Cl
C2
E J. (x)
1. (2)) + a²
E
Etr(Kig
L
(K20)
K-l0
(xx 21)
D 1,2"
qew
a²
=ifl (x, z) +
Σ
tr (Kb),, (xx,)).
qew
1=1
Lemma A.S.
x/6 (x,
1
Σ
(L)
(5;
Eq
d
j=l
d
Kghe (x, 2) =
1
Σ
(5)
d²
3.
Proof. For f we have:
d
C₁
K(LD) (x, 2) = Egg (x;0)
Σ
Σ
W
(x) 149 (a)
Ctd
35 -1=1 =1
1 -
1 Σ
B
| トーン
Σ
Flll (s,x)
(6,z))
C₁
1=1
μ=1
where the part inside the parentheses was shown in the previous Lemma A.4 to equal X (s,x,
16

---

Published as a conference paper at ICLR 2023
For fGAP we analogously obtain
Cl
GAP
(x
Eg [SCAP (x: 0) jGAP (2:
Σ
E
W.GP
10 (x) W 1/3 (z)
Cr.
d2
jij =1 i,, =1
Σ
d
Cl
E
Σ
d
Σ
C2
f (s,x) 1. (1,²2
d
Cl
d
C
3²'=1
W³'=1
==
from which the claim follows.
A.3 FORMULAS FOR MULTISPHERE INPUT: PROOF OF THEOREM 4.1
Lemma A.6. For an L-layer ResNet f and x E MIS (Cu, d), and for every 1 S 1,5,,,
s
1 1=1 1
(x,x)
Co (1+a
oudu y1 (20m +a 2 )vew)
1 12 2.
20o
Proof. We prove this by induction using the formula in Theorem (. For l = 1, since by assump- tion ||x; = 1, for every i we get that x² x is the d matrix with in every entry. Therefore,
(!))
1 (x, x) = Co 35
(x"x) 3.5
(x
1
Co
Similarly, for I 2:
a²
(22)
(x, (x,x) x) 35
Cw
(DDDyy 25'
((1)) x)
(x,
tr
Hanste (x, x))
q2
We can plug in the induction hypothesis, and express K as in (9. obtaining
g-1
(x,x)
Cw
CoCuo
ki (1)
/ jthtK 3 +K+* (x, x) (1)
jtktH 3 +b*k' (x,x) x)
3.
Co
q2
2
k,k'
Cw
CyCar
Ni 2cw + a²cycw
+ a
Co
2
2Co
where we used the fact that Kı (1) 1. The proof for 1 2 3 is analogous:
a²
EX (x, x)
211-"11 (x.
+
Σ
(((l-))
Hitnae (x,x))
9²
k=-
a²
Co N 4- 165 (1) (1+ a² 2CCCue) CoCu
-N
+
N
2
k.
(1+ + a 2 2
1-2 (Cw + +a²cpcu)
2Cu
Lemma A.7. For any L E N let N2 be the value of I(1) (x, x) from Lemma A.6
Let x, z
MS (Co, d), then
a²co
L
K(L (x, = -E(, (x, +
Σ
Nitr (m (ED,, (x,22)
29
17

---

Published as a conference paper at ICLR 2023
Proof. Let L N. We know from Theorem A.1 that
a² L
X z) = [ (x. z) +
qew Σ
(K
Di, (x,
tr
By expressing K as in 9 and using Lemma A.6 we get
(x,z) = E (x, 2) +
a=co
Nitr Ki (D. (x, (x,2))
(5(L)
29
Corollary A.1. Fix Cy = 2, Cw
then
T2y (x, 2)
Co
x(l) (x,z).
(1 + a2+
Proof. Using the previous lemma and the fact that x(1) =1
Ktu xx = 1 (x,x) a
Σ
Ni
1
1+a2 [++1+aa) I
Co
1=1
1=0
1 1 1+a2 1+ (1+ Co
1 (1 +
1
1+a² I
(1 -1+3)4--11 )1+))))))
+ a2)
Co
a²
(1 (1+ Co
Proposition A.1. For any L N.
let x,z
MS (Co, d). and denote t
((x=x) 2) 111 (xT 2)....... (xfz) d.))
El 1|-1,114
Suppose that is fixed for all networks of differ-
ent depths, then:
a²
Niy (t) - ti +
Σ
Ki (t1+k)
Co
qe Co
k
k=-
and
x (t) K/4 ((.,-1)
(t) NL
Kg
(1-))
(s
Nu
k,k'
where Nr, be the value of 2010 (x, x) from Lemma
A.6
Proof. If a is fixed, then for all 1 S / < L the definition (1) (x, z) does not depend on L (just that < L)). Therefore, using Lemma A.7 obtain
xg (x,z) x x((-1) (x,z) +
a²c,
Nztr (R1 (ILL (x, (x.2)))
2q
To simplify this further, observe first that a direct consequence of Theorem A.l is that VL >
I14 (x,z)
Cue Σ
(L-1)) (S4X,
Kig
k=
We therefore get
x-hh (x, = X2h x((-1)
(x,z) +
a'cocw NL
Ki (xyy (((l-1)
(S Se4N
29
R.
18

---

Published as a conference paper at ICLR 2023
Corollary A.2. For any x, E MS (Co, d). let = ((x²2) 11 (x"2)22 (.....,("'2))))))) 2x)2) E [-1,1] Fix Co = 2, Cu = and some a for all neural networks. Then,
1
K (t)
1i +
K1 (t(+x)
1 a²
K (t) 1+a
E(l--1)
(t)
+
a²
Σ
K1 (Tey (sutett)
q²
k, =WW 1
B DERIVATION OF RESCNTK
B.I REWRITING THE NEURAL NETWORK
The convolution of w E R2 with a vector v E Rd can be rewritten as:
[w * v] = Σ
j=1
Therefore, let yp (v) E p2xd be |p (v]lij [V]++j zfب
Then we can rewrite the above as:
w*v= (w s (v)) T (v)" w.
Using this definition, if we instead have E 1R then:
A. = [ * vl, = (v) w:.s (v) w j8
A= = w (v))
(v).
Lastly, if we instead have w E Rexexd and E Re xd then:
Ay: W. vols
w W. (vx).
We can now rewrite the network architecture as:
f()) (x) VDn (vi10) x
1
(12)
② (x)
(w(")²
(13)
VCo
C
(00 (x) = 111 (x) a
Co
((())
x0 (0 (1,5)
00 (x)) 1= 1,...,
(14)
q
#=1
Ctu
900) (x) = V
Cw
Σ
(W!)))
)
)7 &0 (x)) 1= 2....,,,
(15)
q
j=1
and as before have output layer that corresponds to of: fT ,GAP.
B.2 NOTATIONS
We use a numerator layout notation, i.e., for E R, A E R we denote:
By
TA
8
By
By
Raxm Oy 0A
JAiz
JAx
JAAm
Oy
8A
BA....
Also, let Jij be the matrix with 1 in coordinate
(i, and elsewhere. write J. when
m, clear by context. Also, let Jo: = Em 8m D, Jm tiع
19

---

Published as a conference paper at ICLR 2023
B.3 CHAIN RULE REMINDER
Recall that by the chain rule we know that we can decompose the Jacobian of a composition of functions l v6 (v) as:
Joop (v) = Jn (vb (v)) Jo (v).
When h v are scalar functions we can write
Oh Oh Oup
Ōv Di dv
However, h is scalar valued and vb (v) is a matrix we have
a/ Oh
Ōh sb
Öh 0vp
( Oh Onb
Ov
Pipp Jv
Oup Zv
ij
P-q
As such, the following definitions will come in handy:
Definition B.1. L1 $IS j.J' S d, let
6 (x) = (OsEg (x: (x:
11 3.
(x,z)
-B [B000(00 (x) (x) (z) Cw
0f (x)
Notice that f(t) (x) Rixd = 609) (x) R.xdd
Remark. There a slight abuse of notation in the definition of 60) By Lemma B.4 blL+1) only depends on the weights of the last laver Therefore, by the recursive formula for b(0) in Lemma B.3 and plugging in Lemma B.S we get that b(t) can be written using only w ..... WLL), Wa,, V.,, V(L)
..... (g(() (x)). where the latter are indicator functions that are always multiplied by some of W!)) ...., WlO), WFF V(i,,.. ..... V(1),
..... V(L) and â (g
is easy to see now that for any I' S 1, EE
Dij
(x){2 (x) = 0 = E 10
(x)
E
Liz (x) and as
result, 10) is uncorrelated with f()) (1]) (1) (0) and
B.4 PROOF OF THEOREM 4.2 IN THE MAIN TEXT
We start with a lemma that relates the trace and GAP ResCNTK to the equivariant kernel. Lemma B.1. For an L layer ResNet,
1 d
( (x, z)
d
(L)
(s)x,8,2)
j=l
and
d
3 (1)
(x, 2)
d²
1
Σ
Eg
(1)
(8)x,8,2)
jd =1
Proof.
{
TT (x; 0)
0h (z'(2;;0
WW Ii S
(x)
OW
E
E
00
00
Ctd
00
00
1,'=11 1-1'=1 =1
E (sj-1x; 0)
f Ba (s, 12; 0)
E
d
00
30
j=1
Similarly for GAP:
a @GAAP
(x; 0)
GAPP (z; 0)
1|
C₁
d Σ
OWGAP (L)
(x)
8WGAP (L)
P
E
00
00
Ct
00
00
20

---

Published as a conference paper at ICLR 2023
d
① f
(s)- 0)
f (s)-1 0)
E
d
00
00
1-'=1
We now return to the main proof. Using the lemma above, it remains to prove the theorem for f
Proposition B.1. Theorem 4.2 holds for the case of f = f
Proof. By linearity of the derivative operation and expectation we can rewrite:
O (x: 0)
Of (z; 0)
+ O(L) Eq
(x, z) = E
00
00
Of (x: [ff(x))) 0) Of (z;0) <
K owO)
(x:0) of of(2)00) >) + EE Of 0) Of 0f(z0)
(200000)
)
E
E
(B))
OW(EET
1=1
We deal with each term separately, starting with the first term.
E
<
Of (x: 0) 0f (z: (2:0))
)}
1
E (
(x). (1) (x)) = - (x,z).
OW
OW
CL
Next, to handle IE (( ova (eerve af(x=:) av!l)
)(ve))) ) observe that A1 < 1 S 4, S sisc G. we can express
as follows:
O of(x;) 0)
C. Of (x:00 T
x7 (o (x))
@v!!)
Lemmi B2
yCi
0ltll (x)
Co 10) (x) x" (a (9. (x)) qei
Notice that Lemma B.7 implies that the conditions of Lemma B.6 are satisfied. Therefore,
(
ov!!) 05 (x;0) of (2; av(!) :if
)
a² Co
(x, 2) E (10 (o (0 (x)) 40 (o (0, (z))))
E
g0
p.n
2 Co
[T()) p.p
(x, z)
Σ
E (( (1 (x))t((())
(1
( [2))
901
p=
k=
a
T (x, 2) tr (K(p
q0
Note that this does not depend i. We therefore obtain
(x:00) 0) of (Z
0f (x:
Ci
(x(x)0) of Of
2
E
OV ovo
ΣE
E
( p.p
(x, 2) tr (KDpm)
ov())
( Of(x)))) 2f(x0)) )
The next term we deal with is E
Using Lemma B.9 we have
< (f (x: 0) of
a²
! pip (x, ur (Kb),, (x. z) o 2/2 (x,z))
@w!) aw
21

---

Published as a conference paper at ICLR 2023
Putting these together we obtain
Of (x: 0) of (2;00)
(L) Fq
X z)
E
09
00
< O0f (x: 8) Of (2:
L
(01(5500) (x: os 01
aw( ow!! ) + E (
(x)
(0f (x: 0) of 0f(z;0)
}
+ Σ
E
(W4)
(W))
(Vl)) oV())
I
K (x, z)
(1) (x,z)
z) (ir (I((k),, (x, 2) o Dpp (x, 2) +
(1))
(1) Dp. (x, 2))
p.p
q
[=1
Finally, we provide a formula for of Il to Lemma B.8 and denoting P3 1وg completes the proof.
Lemma B.2. Let to real valued function and X, A matrices. 1f (h (XT A)) is well defined then
(())) Bv
A)) 2. AT.
AT E s,t Oh( a+
8X
A)
(X*A)
Proof. First, by the linearity of derivatives we get that
0 0(x A)
AKiiAki Ans.
0X nm
2Xmm
Using the chain rule we get
1 ((xTA) A)
O
Σ
Σ a ( A)m
Anj
0x
d a A)is
0X
mn
aub
Os 0(XT)) A)
= Σ And
① ((xT A) jm
=
abb (( A)
T
0h. (XT )).a
AT= Σ Th (XT A) 8,t
AT
ax
(X* A)
Lemma B.3. 42 < 1 < L,
Cl-1 d
2 0 (x) 11 (x)
T
b(-1) (x) =
(1) mn
(x)
m. 72ml
Proof. By the definition of ((-1) (x) we have
0f [f(xx)) T
Ct-1
0f (x: 0) afth (x)
(0-1)(x] (x)
Σ
10f(-11(x))
ar (x) f (xx)
m=1
C
p() (x)
Σ
10 (x)
0f(1- 1) (xx)
m= n=1
Lemma B.4.
(BLST (x))000
E
= j=
35
22

---

Published as a conference paper at ICLR 2023
Proof.
612 (x)
W (x)
= 6/
W E.E..
VOr
0ff1 (x)
VCr.
Therefore,
(BLOT (x) (x)b(((2)) 555
C2
E
(x)
(77 kg
(z)
6 6
C2
E
W
Fa
w
= و5.1ر
OLd
b:
1=1
k=1
Lemma B.5. 42 < $ L,
0/mh (x) mu a
Ci
Cu
2
(o (x)) S --
(f
C
j=1k=1 k=1
Proof. by the definition of f()) we have
1 (x) = f(1-1) (x) +
CwCC
Σ
v(1)7
W: 1 (0,)
C
j=1
Taking a derivative of plth w.r.t. f(-11 we obtain
0 0 (1) (x) 0f 1) (x)
Jam
8 q V CC-11 0f(-1) (x)
Co
Σ
(x)
((V.)
T 4 o
9
(1)
(x)
ma
denote by 2j
To simplify this, notice first that the derivative can be expressed as
Pkn (o(15) 1 (x))
(
a kid. f (x)
(o (x))
0f (x)
kim D) (x)
Using the chain rule we can express the derivative of a
(0 2nd (x)) as follows:
jn+x-22
a 1) ( -- mfs (x)
w(())
'n's "s f(l-1)
Pntt- +fي (xx
(
= à
1 2t1 (x))
0f 1) (x)
I (ل((m)) (x)
m'n'
Cl-
(1) (g)
9 f mis (x)
Σ
8n' mmmmm
w(l)
ED ni at m'nn-
j'=1
(1 271 (x)
mm ED
w(() 943 m -
0g j. tiي (x)
= 0 10th
( (x)) Panz-
w!!)
0f 111-11 (x)
iidd
In summary obtain
a (x)
C
= jmm
a
CopCo
k.jmm (0 one (xx) Sd a- sf w!!
0f(11) (x)
C,C,-1
j=1k=1 k=1
23

---

Published as a conference paper at ICLR 2023
Lemma B.6. For any two matrices M, M' E R and N. N''
E if M is incorre-
lated with NN", and for every k + k either E [MM' then
M')
= 0 E
"VNN"<a] -0, Kk
kE
E (MN, = -E (M'M))
M')
E
(NTN))
= Ir M MMM'MN'
PiP
p.p.
Proof. Following the definition of an inner product we have
Σ M MingN
5
E (MN, M'
E
(MN),;
=
E
M Mi No.
ij
E
Mi M up
No.
Σ
E
(M'M
M')
E
(NN*")
uncerrelated
P-p
p'P
p
p'
E
(M''M)
M')
E
(NN"))
E
tr
(M'M
CAMMONE
ON'N)
O when p
p.p.
p.p.
Lemma B.7. 41 41 1, 1.1kk S Ct,1 S $.J5' S it holds that
P2. (xx ))
E
(2) Oz
B (1++ B (x)b,² b(t21) (z)
a'cw
((1) Ditnuto (xxz)
@
c
Proof. By Lemma B.3 we have
Ci
a (x)
C2
(z)
E kkj
(x)
E
((+1) (x)
(441) (z)
nn'
05ki
(1)
01
m=1 x=1
m 3'=1nn
C₁
2 afun (1+1) (x)
( (z)
E
batt1) (x)
m'm
(1+1
05
05
m=1
Now as b(++1) (x) is uncorrelated with (02 05
we get
1++1) (x)
0f (z)
E
(x) ((--1))
b(t m'n' n
(z)
E
af
of
=1==1
KJ
By induction (where the base case is Lemma B.4 we can assume that if m # m' or 4 ní' then (x) (2+1)
E but
((+1)
(x)
= 0. We therefore obtain
C₁ d
a arat"
(x)
a ( (z)
E
(x)
(x)
E ((++)
(x) b b1l+11 (z)
E
of
of
m=1
n=1
( (z) 81,
It remains to calculate E
Lemma B.5 states that
8527
0 mm
(x)
( (x) Of(I) (x)
=
xx)
C1s1 Co
Skm 6jm
a
v(++) à (0---)) p.s.m
p بيس (x)) LEED a- --n-pe
W (+1)
CiC
p=1
Demote by Agr
Denate by C
Bun (x)
24

---

Published as a conference paper at ICLR 2023
Using this notation we have:
0 ( (x)
af (z)
E
Agg Agy +C
(Ag]EE B
+ A E
[Bar"]
+ +C
B (x) Biy (z)
05k3
of
We will deal with each term separately, First, we consider the first term:
Aky Am
5km Sn m 6 6kk' m 33' n
{
k= = m and likewise for 8jy'n For the second term,
where we use the notation dyk'm
otherwise
since V, W are 0 meaned i..d Gaussians (Equation and ē is the indicator function we have 0. Therefore,
Bmn (x) E Bay
AmaE A
E
BWy
(2)
+
ML A
B (x)] = O.
For the last term, by definition
C1+1
BKg (x) =
v(+ o (o a_s (x)) 1jED uto o/ j-n-ptotkke
((11)
and
Cl-1
B (z)
(++)
à (0/ 2t (z)) 1 IEED
w(l+1
p'm mm
From
8 E
(1+1)
(++1)
Sp and since they are uncorrelated with W(+1) and
g ((++1
p.a.m
plaa'.m
then
E
B (x) Bry (z)
C1+1
C²)
( (1+1)
(x)) w w
L-n (geptn-ayl mfs (z) w w(1+ w LISED -4p-
(outt)
1=1 p=1
O
55 C
E b ( @ tfe (x)) o (outt)p (2)) 1 Ljj'ED mpp 2t
a² Σ
Oz q²Ci-
(1++1)
utp- 9+1 - or (x, 1,3'D nlv +
p=1
Overall,
U (x) 12 (z) =
a
E (x) b((t (z))
Oksmmdjnn S c²
k (++1)
uttp-ad (x,z) IyD -fي
m=1n=-
1=1
+ a²
E (ooTT (x) blct (z)
ΣΣ (411) (x, z) K (1++]
n-p- داع -tp- (x,z) L a0
m=1p=1
Now observe that
E D
So we can rewrite the above as
(x) b2 (2) =
kg
25

---

Published as a conference paper at ICLR 2023
c² y j-ptq
= =ogs-dg
[ (x) 0b3
114+1) (2)
Σ
Σ
I an
(x, 2) k((11)
n+D - -+p- 2 (x: 2)
CfCi
pem nnj j-p
a²
= E
E ((++1)
(x)
و5ن ( (2))
+
Σ tr
(+(+1)
(x,2) o k (x, 2))
qPC2
o
p=1
a a2cu tr q²Ci
= -5
E (--
(x) و2و (1+1) (z))
+
Ditnniy (x,z)
(++))
@
(i(lt)) Dj.s (x, z)
Lemma B.8. LA أزك S d
(b)
(x,z)
1
1 ==)==1
33
dew
and V1 S1S 1,1 $1.5" S d, it holds that:
11 Js (x, = =d/8 (nnj"") (x, +
1)
a² ir
Σ
Potnsto (x,z)
(+1)
@ k
(x, 2)
q²
Proof. First, from Lemma B 4 we know that:
1 E (RLO) Cw
1
(x) (x)(0) (z) 3.5
dew
Now let 1 SIS. L - 1. Using lemma
B.7 we get that
- E (B00 (x) (x))²)) (z)) (zi)),r)
1
E
(x)
b2g (z)
Cw
15'
Cw km
C2
83
1
(1+1)
(xx (x) 6/g (1+11) (z)) + O2
a² tr G²G
I1 11+1
Dytnito (x,
@ (k (xx (x, z) )
Cw
k=1
( (x, 2) + a² tr
@ {BBt)) (x, 2)) )
= Ezzr
I (1+1) Ditn.spp (x, 2)
g2
Lemma B.9. V1 V15LL
{ OS (0((x00) 0) Of 05(2:0)
(oww ww awi)) )
a² d
E
( an (x, 2) ir (KD., (x, 2) 2 E (x,2))
Proof. We first show the case for 2 < 1 < L. V2 111.,111 L. C- S C₁ we can express (x(x))
aw!
0 1 (x)
a aw!!)
Co ((-1)) (x) + V
vi!) :ii
4 (a (0)5) (x) (x))
aw
(1)
(I)
90
1=1
172
Since 93 (x) depends on ((() :1.e
iff c = j. we get
a (x)
Co V
(
a
zجع (x)
aw(()
a
qc 1=1
k.c.m
aw(!)
:1.
26

---

Published as a conference paper at ICLR 2023
CuCo C;Ci-1
v(0
hiam ( (x)) ow!!
a
(dis) 60 (5/(-1) (x)
T
V
k=1
c.ntk 2/
a
CuCo
Vil) kiam
d (ooRth- 27d (x)) (5"" (1(711
q
C
k=1
Now have
Os (x: 0)
Oʃ (x; 0) 2 0Sron (x)
Σ
aw!l)
0imn (x)
aw!!)
:,4,0
C1
a
Cw
Σ
k (x)
v((
( (x)) (0" (I!(11( (x))
9 CiCi-1
k.c.
n+h
m=1
n=
k=1
Taking the inner product we get the following expression:
Of (x: 0)
aw!! :ie
of 05())))
Ow(!)
920,C-11
Co
Σ
Ct C
Σ
E
bill (xx)
60)
mrnn"
(z)
.IE
vil
k.c.m ks' K.mmm
v-(2
m =1
EE
Ko (0.2) (1ontk (x)
T
( (x) ntk xfp ,
(9
(en''t" (2) (0" (154-1) n' +x' ( -4211
Note however that 8 implies that v.()
k.a. W.mm = 6x and Lemma B.7 implies that
vll)
E
bun (x) (1)
(z)
O when * n'. Therefore,
Of (x: 0)
Of (z(z;) 0)
E
ow!!)
ow())
Co
q
E onn (x) 6 (2)
=ew 11l
E
((o (0 (0 221 (x)) (187) (1/7-1) (xx))
,
9
@ontt (2)) (0T (I.--)
1
a |
athh
a'cw
Σn nn
(x, Z)
Bi (x, 2))
((-ام untk-يil+ (x) ((--)))
-ork--il++ ابل (z)
kk
n=1
A=1
N'
As a result, by linearity and the fact that this result does not depend on c we obtain
Os (xx0) os 2f(2))) }
E
awe
awe)
a² Cw
d
G
nn (x, z)
K Dunn (x, z)
E
2hd -k (x) ((2-1)
utt +k (2))
q2
C
inth
n=1
W=-
Using Lemma A.2 the last term simplifies follows:
C1-1
11111] p +x (x)
b 2t +k. (2)
gCr- E g gontth
q (ا())
2t7 (x) g ( 1tع (2)
n 2td - (x, 2)
Cup
Finally we obtain
K (00 (x: (z;
ww : 1/6100 )| = a² d
E
Σ
( nn (x, 2)
Σ
Hell)
Do,n (x, kk
Ebh.. (x, (x,2) kk
n=1
k=1
27

---

Published as a conference paper at ICLR 2023
nn (x, z) tr (K (x, 2) o LiBun (x, 2)).
The case of 7 = 1 is analogous, except that we replace x" (1!--1)(x)) with x? and similarly for z, (making minor adjustments accordingly). We therefore obtain
Of (x; Of of (2: 2
1|
E
-
OW()) OW())
022 (x,
d
Drin (x,
E
x x x 2in Till
gCn
k=
(1) 2x, tr Don (x, 2) @ 2i (x, z))
n=
C SPECTRAL DECOMPOSITION
C.I PROOF OF THEOREM 5.1 IN THE MAIN TEXT
Proof.
The strategy is to bound the Taylor expansion of the kernels. We use qualities of the Ordi-
nary Bell Polynomials for the lower bound, and use previous work singularity analysis (Flajolet
& Sedgewick 2009 Chen & Xu 2020 Bietti Bach 2020 Belfer et al. (02T) for the upper
bound. The details can be found in the lemmas that follow, resulting in that AC (b) be written as Σn 6nt with
2.5 < 6n S o2n -1
Cin
and By can similarly be written as Σnvo t with
2.5
s bn c2n -
Thus, applying Geifman et al. (2022 [heorems 3.3,3.4) completes the proof.
Lemma C.1. x(( can be written as k(()) (t) Enzo but" with
cin bn.
(L) where ej is constant if the receptive field of K includes n and 0 otherwise that depends on L.
Proof. Let (1) = En= !n be the power series expansion of (1))), where on ~m Xu 2020).
-25 2.5
Chen
We prove this by induction on L, starting with L. = 1:
a²
a²
x (t)
-b stt
Σ K1 (t14x) = -1 tlt
a, ant
Co
ConCo
Co
Co
n=0
By letting e; be the multi-index with 1 in the i index and 0 elsewhere, it is clear that write the above as Enzo t where
ag Go
n = 0
c.
bn =
+ Co &
ne, for 2-1 2
<j < 1-1
2 and E N
qea
otherwise.
28

---

Published as a conference paper at ICLR 2023
For L 2 2. by the induction hypothesis ((b-1) (t) Enzo bnt s.t. c.n S bnn Let Nr. be the
Tq
value of 2/ (x,x) from Lemma and Nu
and arc.
NL.
24-
Eq
(s,t)
00
On
Σ 6n (s,t)" n20
On
Σ b (t) n20
(t)*
in
K1
=
NL
NZ
NE
n=0
n==
Using the derivations for the multivariate ordinary Bell Polynomials in Withers & Nadarajah 2010);; Schumann (2019) we can rewrite the above as:
(.) (s,t) N₂
Σ n20
an Bun
(s t",
K1
No
where = (mm)
and Ban denotes the ordinary Bell Polynomials. Plugging this in to our
n20
formula for the ResCGPK from Proposition A. we get
2=1
K (I.-)
(s
x((L) Rig
(t)
(((-1) (t)+NN
K1
NL.
bn + No
Σ -=-9+1
19
jl
2 n=0
On Bun (s_) t".
Ny.
n20
Let this be Enzo t All the terms bn are positive so for lower bound, it suffices to sum up only specific n's and j's. We choose n = 1.j and since Withers & Nadarajah (2010) showed that Br.1 (b) bn we get that
01 NE in bn bn + 4
alarcrew
1
cin
24
where the last equality by the induction hypothesis.
Lemma C.2. The bound in Lemma (...) holds for (
Proof. Denote by bn (XC) the Taylor coefficients for some kernel IC. Theorem 4.2 implies that
Eq zx = =K(h 2x,
(1)
(x, z) ir DD,, (x,z) o
x Dr.p (x,2) z) - KDD. (x, z))
Denote by
Since for any positive definite kernel the Taylor coefficients are non negative, get that: bn (o(L) = bn Fo) + bn (x') 2 bn (ACFa).
Definition C.I. Let L(( the GPK and (L) the NTK of the bias free fully connected ResNet defined in Huang et al. 2020). For Forx, E SCo-1, xx following the derivation in Huang et (2020) and Belfer et al 202T) (in particular, Appendix B.I of the latter), the normalized version of these kernels will be:
E (u) =
1
(KHE (u) + a²xi (KFC (x(((())))))))
KFC (u)
1 az
L
(1)
1/ p(0 (u) Ki (xft_") (w)) + R(tl (w) No (Tec (w))
2L
1=1
where vi = (1 (1+ (2)) p== = and Pl (w) po+1 (n) (1+ 12x0z (xft (u)))
29

---

Published as a conference paper at ICLR 2023
Lemma C.3. For u E Rd, letting t1 = t2 ... = u we obtain Kfc (u) = Keg (t) and letting
k(L) -O(L) K we obtain 0/c (u) = k (t).
(L))
Proof. For the GPK, this is immediate from Corollary A.2
For the ResCNTK, first recall that
(L) a² ΣΣ p()) (x,z) 2) Eq (x.z) = KEE 2x,
+ (L)
(ir
k(0 Dp.
(x, 2) ② E (x, 2) + K (x, 2i 2)
Observe first that a direct consequence Theorem A.1 that 74 2 2
(b) (x,z)
21,1
Cw
Kiy
k(l-1)
(52),
k 27
and 11,1 (x, z) = C u.
Therefore, by choice of t, E0) K( and K((1) have constant diagonals, and so the terms in the trace do not depend on the index p. and get
k(() (t) a2 Σ
No+1 (NO (Kftc (u)) KtC (u) + (Kit (w)) Σ p( (t).
Note that for each S S L, definition. Now by induction we assume for + and now show for I.
L
pd (t) = pd (u). For they are both equal to by
p=1
d Σ p() (t) p=1
d = Σ
a² tr
@ KB (t) 1)
p(+1)) (t)
Σ
Dute (t)
qp
qp"
p=1
(6) )0)) Dask
Σ
p(l+1) p
(t) + a²
nio (k!tt))
Σ
p(++))
tr
p=1
Am 1=11
d Σ p(tt)) (t) p()ti(())) p=1
())
+ a²Ro (
Σ p(it2) (t) p=1
Plugging this in the induction hypothesis we prove the induction. So overall:
1LLD) (t) = a 2
N441 Fd (u) (NO (xflc (w)) Kxk (u) + mi (xfe (wi))
1=1
Since
N41 = N201-1
(16)
normalizing (4) completes the proof.
Lemma C.4 (Bittt & Bach 2020 Section 3.2). For small > 0,
2v2
-1 (1=t)=1-t- Ki
0 {8
3m
Lemma C.5. For all L 120 O, and small /. 1 0.
Rel (1-t)=1-t++
Remark. This lemma and its proof are a slightly modified version of Lemma B.4 from Belfer et al. 2027) where we tighten the bound.
30

---

Published as a conference paper at ICLR 2023
Proof. We prove this by induction. For / = 0, KFC (1 - f) = 1 - t, trivially satisfying the lemma.
Suppose the lemma holds for (- - 1, then using Lemma C.4
K (1 (1-t)- -)= = a+a xtt
(1 (1-t) t) + a
( (1-t))
I+ (1-++ (1))
+ ammm (1 (1-+ (+)
1- 1-1+6 18) (13)
a²
1 1 18) + 2/2 (1 - (
(1))
+ +0
+ a²
3x
1
(1 a (1 (1 t + 0 (13))
1+a2
=1-1+0 18
Lemma C.6. KFC (u) and 0/c (u) can be written as En On uh with an n.5 for (L) and On -13 for O/c-
Proof. Using Lemma C.5 we know that for / it holds that K/C (t) + f(t) where
f(1) θ ()- Using (Flajolet & Sedgewick [page 392 Thm. VI.1] get that
admits Taylor expansion Σn= a, around with a, n 2.5 Therefore, K/c (w) has Taylor expansion with coefficients that exhibit the same decay.
(L) For OFC (u), using (Belfer et al. 2021 [Lemma 4.5] we know that fort / 1, it holds that O (t) = 1 + c1 (1-t) t)$ + o (1 t)²
for some constant e1 0. Similarly the previous case, using | VI.I, page 392] get the desired bound.
Flajolet & Sedgewick
(L) Lemma C.7. Both k(l)) (t) and Eq (t) can be written Enzo bn th with
bn S c2n
where u = 2d for Kgy
(L)
and v == 2d + for (L) and 02 depends on L.
Proof. By Lemma C.6 KyC (u) Keg (L) (t)
m un " with an 2.5
Moreover, we have that
Enzo tn Together with lemma C.3 we get that
00 bau ml
Kgg
(t)
Σ
b
bn-
n>0
n=0
[n|=n
The uniqueness of the power series implies
Σ
a (m
pn m
Plugging in Lemma D.8 From GGiffman et al.
2/ -4 for some constant 2022) we get that bn S can
62 >
For the bound for ResCNTK, since by Lemma C.6
e (u) = En un
" with ā, ~ n 1.5 and
A (() (t) = Enzo th, we can analogously get that in < é - for some constant > 0. (The
difference from the different bound comes from the referenced lemma in (Geifman et al. 2022 .)
Since (D) 0 (()) by combining the two results we get that ((4) (t) can be written as Enzo 11,t" with in can -
31

---

Published as a conference paper at ICLR 2023
D POSITIONAL BIAS OF EIGENVALUES
D.1 PROOF OF THEOREM 5.2 IN THE MAIN TEXT
[- 22 02h (i.e a set that contains only the tuple 0 = (O.....0)) and for 2 let R == Q x (0)2(1-1)
We define "stride-q" version of the ResCGPK, Let
(i.e tuples where the first 2/ 1 elements are in Q and the last 2(1. 1) elements 0). We let [-1,1] be elements of the form ta which are [-1, 1] valued parameters indexed by tuples Ri.
Also, for every k and < 1 S L define 'N, [-1,1] [-1, by 4,, (t),
(aa.....0a--..b .at...)
We now define the kernel (11) [-1, + [-1, be
(i)
to + a²
Ki (L)).0...,)))
1 + a²
k=
k ( (8)
Also, for all < < L we let 100
1-1, 1] + [1-1,1] be
k: (
( a²
Σ
11 (k=-11) (F)
l+ a²
q²
=-k 27
k (6)
=b
We also define the change of variables S Rg - [d] by Sa(a) |a| + (reminder: on multi-index means sum of all entries).
We are now ready define correspondence between the stride-q ResCGPK and the standard one. Namely, for every E [-1, we let d(t) [-1,1] be o(t), := ts, claim that (o()) = K (L)
(t)
First observe that for E R it holds that le (o(t)) +1a/414444 o(s t)a (because E Rt so a2! 221 22 0). Also notice that d L, (Ø(t)) E Rl+1, Thus, we recursively get that for o o... 1 N (d(t))) a = ((8 o o... Sk2th' t)a-
a E R!, 1 k
Now, for I. = 1 we trivially have that ((b(t) Kell (t). So for R!!
(1)) (1) (1 ..... of K (o(()) = -((1) ( o... o skytki 1))
Kiy (S o.. .8 kk. t)
(1)
As such, we get that
(2)
o. o Hen (o(t)) = =K (s (Sp2 o... 8 8kutki ()
And continuing by induction we eventually get 1(6-1) (1t (1 (o(t)) Kg4 x(b--1) xil1-1)(s (8 which
implies that (e (=(()) - (t).
We now move towards better understanding their Taylor expansions. For function f(t that can be approximated by a Taylor series En a let [t"] f denote the coefficient of tt in its Taylor series (meaning on). Let (n) = ñ e R2 suppä S RG and E [d]. Ejes, (() ñ, = n. be the set of multi-indices which indexed by tuples in Rr with support in Rú that correspond to
32

---

Published as a conference paper at ICLR 2023
So i (n) get that for every t E [-1, 11" o(t) tt. We get correspondence between
the Taylor expansions of the kernel as follows:
Σ bnt E ( = Σ n20
nnt
Σ
ba t
n20
n20
ii (m)
By the uniqueness of the power series,
bn Σ bn
Σ
tt [
(L)
ta²
Σ
[E
1 I+ a²
(n)
nEMr-i(n)
(EM2(n)
Now k (b) Itax (/ (1 (t) + a²2hh (12
so we can continue apply this recursively and (t)
eventually get:
a
L-1+1
Σ
(1)
Σ
tt
(1)
(1 + o
1 a²
nEMo(n)
1=1
nEM((n)
1-1+1
Σ
|1 (1)
(1 + o2)L Ro
1 1 a²
(EMi(n)
Now let 2.5, via the proof in Lemma C.1
we know that for every <15 S L there is some
à > S.t.
1-1+1
Σ
tt
2
Σ n
1 1+a2
DE Mi(m)
nEM((n)
Let p;(() = [i) the number of paths from an input pixel to the output of an layer CGPK. Using Geifman et al. [2022]LLemm) C.4. C.5] we get that for A > 1, some a constants, and
L-1+1
Cn,/ I1 " .m) it holds that on <
(t
14a
Overall, obtain that
bn 2
Cnan
1=0
Now consider the kernel k000 (t) eigenvalues of this kernel satisfy
Envo Ca.in
then by Geifman al. 2022 [Lemma C.7], the
d (k())) 2 Ck. II
A Co-2
where CK, = & Amin(p! (2) As) for some constant ē. As for every I the eigenvectors that corre- spond to (k(0)) are the same (given by the spherical harmonics), get by linearity that
Ak
Ck.
k
Co-2
As in Lemma C.2 this also gives bound on the eigenvalues of !!L) Fig
E INFINITE DEPTH LIMIT
E.1 PROOF THEOREM 6.1 THE MAIN TEXT
Lemma E.1. Suppose that L- for y (0.5, 1] then for any t E [-1,1]
Eq (t) - (1) < 5 (1)-
(L)
(1L-21))
33

---

Published as a conference paper at ICLR 2023
Proof. First recall that
a² L
d
1 Ei (t) = x (t)
p())
(t) (1r (n((Ki) (K
Dpi (t) DD (t) + K
Dpp (t))
+
p
9 1=1p-1
Let (t) ae ( (L)
(t)
(t))
so that 1 (t) K (t) a² (t). Using our
calculations in (16) we know that k( =
2 Co
L
+ a² 02) Therefore.
2 Co
2 Co
2 Co
1
a² k²k(1)=
(a L)
a
(a ()++
L 1-22
1
1,24
1, 1,
< 1 12 24 (11+ 1,27
17
2 Co
I, 11-22 11-2 2 11-27 0 (1.-21))
Co
s a²k(1) S <0 (1(11-1) It therefore suffices to prove that Consequently, ( (t) - keq (t)
( 1.1 (t) I 0 (T)-
(t)
(م,0) To avoid confusion, we denote by kgg (t) the ResCGPK with a specific a (that may not necessar-
ily be () For all 2 s 1 S L as result of Corollary A.2 we get that
(1LL
x
(11
Eg
(t)
(t)
2
K Eq
(1-1,b
(t)
a²
Σ
x (smnrt))
KBq
KBg
(1-1 7) (t)
1+
2
G²
k,K'= egt
a
1
2
-((-1,b 7)
(B)+)tt)
K (21-1, 7) (())
a²
1
2
K1
Kny
a
k,k
(1-116-))
Where the last inequality follows because K Fg
E[-1, 1]
and so is n1. This implies that
(L.
(t) - (+t
= F
(L.
-
RTg (t)
(1,677)
(t) L 1 a
a
S <0(1'-2))
which completes the proof.
E.2 PROOF OF THEOREM 6.2 IN THE MAIN TEXT
Our goal of this subsections is to prove the following:
Theorem E.1. Let R-(L) RecGPK and K(()) CGPK respectively denote kernel matrices for the normalized matrix defined for
trace kernels ResCGPK and CGPK of depth L. Let B (K) be a matrix K as in Lemma 6.1 Then,
1. R( Recorr
- (KEECGGRK) 11, L+00
)l, O and | - B B( (R I1, L O.
2. p (B (Kileccor))
- oo and p (B (K((Px))
oc.
L+000
6-000
3. BL N.t. VL Lo. p B (Rleccoe))
< < B R
))
Proof.
We give here the main ideas and leave the dirty work to the lemmas.
By Lemmas
E.3 and
E.2 both
R(L) Relorr and KCuP tend towards B1, as - co. As such,
B (R(L)
ReSCOPK)
B1,1 and so we get (1).
100
34

---

Published as a conference paper at ICLR 2023
For (2), observe that Amin ( cGPK)) M(n-1] Eijj CGPK +-000
O.
For (3), let Lo E N be the minimal such that the entries of (K and B (
are non negative and let L 2 Lo- By lemma E.3 we get that m)n Eits KCOPK
(L)
1 1(n-1) Eigs R(L) ReSCUPK.
Since ((B1b)) 1 + n we get that p (B (K
(RROCOox) <p
(R(OP)) as desired,
Lemma E.2. Suppose that is constant that does not depend on Tu, then for any t [],, 1.11 / (t) + 1 as L + oc.
Proof. Denote by K (t) the vector that is Rgq (s)-1t) 1) in the j'th coordinate. Using Corollary
R(LL)
(()) (t) denote the mean of the vector (L) (t),, then by linearity we get:
A.2 let E
E
K
(t)
= a
(t)
Σ
E K1 (1(--1)
k,
where we let K1 act point-wise on vectors. Since we can permute without chaning the mean (i.e.,
for any E
K
(t)
E
(s,t)
get:
K
(1)
(t))
= 1 a²
1
E r (2-1)
(t)
2B [x] (x (t)
(17)
x (1-1) 1) (t)
a²
(E 1il
(x (4))] - EE (1-11 (t)
= E
+ 1 1 a²
E k
(t)
a²
[k) E
k () (6))
R (1(1) (t)
(18)
a²
where the last inequality is Jensen's inequality (since Ki is convex (Daniely 2016)). THerefore,
let ar. E xc (t)) can rewrite (18) as:
2 aL-1 1 a² (R1 (aL-1) aL-1).
We therefore need to show that az. + as T + co. Since az is monotonically increasing (x1 (u) > for all u [_ (Daniely et al. 2016)) and bounded in [-1, 1] it suffices to show that for all > 0 there exists some L E S.t.t az 2 1 6, Suppose not, then let e > S.t. for all L, ag < 1-c. As du (1) = (u) and ko(u)= E [o, 1] (Daniely al. 2016 then h(u)) := ni (u)
satisfics d h(u) = ko(u) < with equality iff u = Therefore, for any u E [-1,1-111 he], 2 du
h(1-c) (The: >> is because sn (u) u for u
[-1 1, 1 1- <)). Since assumed by contradiction
that for every E N. < 1 - e, we get that h(a))
2 h( <) and thus
a² Tp 1 h(aa-()))) az-1 T
a²
h( - +) 2 ao + L a
1 a 11 6) ax.
10000
However, since as [-1, this leads to contradiction.
Lemma E.3. Let (t) = 1/ Ej -== Ki o...or (tz), (an average of the entries of after compo-
times
(T)) sitions of 81), where (t(t)= (VI- 1 + (n (orccos(c(()) 1). Let (CCPk(()) be the correspond-
ing CGPK-Tr Tr without skip connections. Then
1000 (t)-
(L) KCGPK- (t)
K0 (t)
a1a02)L-14
1=1
where if of T this quantity is strictly positive.
35

---

Published as a conference paper at ICLR 2023
(1) Proof. Let Kiq (t) be the normalized CGPK-EENet and (t) be the matrix that is kiy (s1+gt)
in the j index. Similarly define the matrix (=(4) (t) using KEy (t). For convenience let K. (t)
k(0) (t) t. Note that E [A(LL (t)]
x(t) RcCok-Ir (t) and E K (t) Kr (t). By equation 17
we have that:
+ (E (1 (t)) + aB in (klL-1) (e)1=)((e)])
E
(t
and similarly it can be readily verified that
E k | (t)
= Ki (k(--1) (t))
(Note that the CGPK is naturally normalized so omit the bar.) We prove this by induction. For L = 1 we have:
E k (t) - IE [ (t)] I+ (1()) ((0))pp' (6(0--1'0) -10))
Now assume for L 1 E N, then
A (t)
K L) = E K1 (b(--1) (t) i+ az
(B (x (t)) - - ris (k(L-1) (6) (6)
Since Kn is increasing, using the induction hypothesis we know that =Q²B ii (Kl4- 2 -a 1s1 (k-(2-1) (t))]. and therefore
E [()) -E (t) R
2 E Mi (k(L-1) (6)) (b(L-1)(tt)]
I+a (x(x(L (t) + a² nn (bll-1)(t)) (t)
1
R |ka (b(LL11) (t)) E (x) (t)]) [M1
It a² ((1l))p(te
+ (E (( E (c)))
I+ a² Applying the induction hypothesis recursively provides the desired result.
Lemma E.4 (Lemma 6.1 in the main text). Let A E Raxn (n 2 2) be a normalized ker- nel matrix with EiØj Ag 2 O. Let B(A) = Bid with b = m(n-1) Eies Aij and e = sup; Eszi Aij B ((A))) Then,
1. p (B(A)) S P(A).
2. I < Amia (B(A)) then p(A) S Amaxi ((())t+ Aunia ((A))
where Amax and Amin denote the maximal and minimal eigenvalues of B(A).
Proof. For (1), using Marsli 2015 Theorem 4.4] we have
P(A) N (A(A)
711 (A)
where
(A) min(
A
Σ
Agi
Aij
n(n 1)
1=1
$$1
(A) max
1 a
Ai
1 n
Σ
A
1
A.j)
n E=1
n(n 1)
==
$41
36

---

Published as a conference paper at ICLR 2023
By the assumptions that the diagonal entries of A are 1 and that Σ
j Aij 2 0, we get that
(A = 1 m-- Eiys Asj = Amin Anin(Bie (B(A)) and 722 (A) = - 23 3 Aij = Amax (A)).
Therefore,
(A) Amax (B(A) (A) Amin (B()) p(B(A)).
p(A) 2
For (2), by the Gershgorin circle theorem, since A - (A) is a matrix with diagonal zero, every eigenvalue A of A (A) must satisfy |^] S E, Since A and A (AA) are symmetric, it holds that Amax(A < Amax (A)) + Amax (A - ((A) and Amin (A) 2 Amin (B + Amin (A- - (A))
from which the lemma follows.
F INFINITE DEPTH DISCUSSION
(1) Lemma C.3 states that for u. E Rdd, letting t = t2 = _... u, we obtain K (u) K (t), and
((L) we obtain (LL) (u) k (t). where the fully connected ResNTK and ResGPK are defined in Huang et al. (2020).
letting k(()
- =
(1)
(1)
Eq
(L) (t) and not @pc (u) 6 Eq. (t)? This is in fact a conse- quence Huang et al. (2020) not training the last layer (denoted by vn their paper.) If they were to
One may ask why does θ Ogc (u) = k: 1e
(L)
train the parameters v. the term E [f(xx))) af(x:0) would be added to their ResNTK expression.
But this term is exactly equal to the ResGPK. Therefore, training the last layer adds the ResCGPK to the ResNTK expression. This is indeed confirmed in (Tirer al. 2022). who derived ResNTK when the last layer is trained.
So if the last layer is trained, we would have 5 (w) o (L) (t), and thus Theorem 6.1 would (u) - w. Intuitively, this happens because the term u exists in the ResGPK, and is the only term that is not multiplies by a. So if a decays quickly enough, u becomes the dominant term.
imply that Ofc (L)
Instead, by eliminating the ResGPK from the ResNTK expression, all the terms are multiplies by a. So after normalizing, the two layer ResNTK becomes equivalent to the two layer FC-NTK (Belfer et al. 2021
If we were to not train the last layer, would have similar result, where the resulting kernel would correspond to 2 layer CNTK. We give here a sketch proof (the details are analogous to [Belfer et al. 2021 Theorem A.I states that
z tr
a²
(2) 5s
(t) = Cee tr
(1) DD nis'
(t)
+
Σ
(
11) +2 +h (t)
q
k=-
=
For SI L,
a²
2
())(() (t) (t) -
" (t)
Σ
(xfl-1
(t)
tr
qp
k=- s-1
So 7= L we have that for all / > 3,
[t)
x//--1 (0)))>()/-))/)) S a²
Σ
(Klf-
p (6)) saa
So () (t) - (t)
(t)))) (t)
5 L a² = 11 11
( 33 (t) K 53 (t) = 2 and k200 (t) - k: (t) = 1,1-21
In turn we also have
Furthermore, by Theorem 4.2 have:
37

---

Published as a conference paper at ICLR 2023
a
(t)
(t)
Σ
PDtp (t)
k (t)
q²
2
Σ
p(l+1)
(t)
S a² {22|p(tt)) p((+1) (i) s a² + a2)
q²
Dz+p
Now because it holds that:
a a² + a1+ (1+
1 ) (1+ | ) 1
S Eli
1
Since (t) i== we analogously get 1 - -f (t) s 1-1-21 el 12- 2112-21).
Now recall that
(t) R (t)
a p(l) (t) (Ir
(0()) Dp.p (t)
Dup (t)
K!l
(t)) Dap
9 1=1
Denote by ((t)
where by (16) we know that (1)
(1)=
Co L(1 -7)
Normalizing the kernel implies
h (1) (t)
1(0((t (t)
xo k (t)
1 ~ tt (K (t) @ op, (t) (t)+ (2) (t))
(1)
where C' is some normalizing constant (Note that after normalizing, (().)((t) becomes negligible.)
( (t) 1 (ED,,, (t)). As such, after normalizing, in the infinite depth limit, the
For such a, "J
10000
expression tr (1. (t) o 2n)) (t) + K. (t)) becomes the two layer CGPK (aka one hidden
layer, denoted by = 1) with inputs f where f, = 1 Σ Σ u tit
G EIGENVALUE DECAY EXPERIMENT
We use (Geffann al. 2022 Lemma A.6] to numerically compute the eigenvalues. Namely, for each frequency in Figure we compute the Gegenbaur polynomials and the kernel, and numerically integrate. Note that as this integration requires evaluating the kernel many times, we are limited to d = 4 and L = 3. To prevent the receptive field from being much larger than d, and in order to better match the CGPK expression from (Geifman et al., 2022). we slightly modify the ResCGPK to include one convolution in every layer instead of two, where the layer ends after the ReLU. Thus the kernel computed with d 4, q = 2, a 1 is:
1
kt(t))
+ (Bl, + K1 (1:)
1
Stg + K1 (t: + t(t1) t(tt))
k. (t)
1 1+1 8
where B = 0 is the CGPK from (Geifman et al. 2022 and B = 1 is the modified ResCGPK.
38


Reviews:
[{"review_id": "xY4O7ugd_w", "reviewer": "Reviewer_RWs1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n\nThe main results include\n1) 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.\n2) residual kernels are more locally biased.\n3) 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.\n4) A theoretical justification for the result that over-parameterized ResNets act like a weighted ensemble of CNNs of various depths.", "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.", "strength_and_weaknesses": "Strength:\n- 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.\n- 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.\n- The author justifies why ResNets converges faster than the normal CNN by utilizing the NTK technology.\n- 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.\n- The results of experiments match the conclusions derived from theoretical analysis exactly.\n\nWeakness or Questions:\n- 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?\n\n- 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_vRxoSv5Ztz", "reviewer": "Reviewer_ciS9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\nAs 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.", "summary_of_the_review": "I find the theoretical insights interesting, as they explain empirically observed phenomena. \nThey are of relevance for the ICLR community that tries to understand possible advantages of residual structures (in comparison with architectures without skip connections).", "strength_and_weaknesses": "Strengths:\n+ Explicit formulas or residual convolutional Gaussian Process Kernels (GPK) and Neural Tangent Kernels (NTKs) are provided.\n+ 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\net al. (2016): over-parameterized ResNets act like a weighted ensemble of CNNs of various depths.\n+ The experiments support the theory and provide some quantitative insights. \n+ 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.)\n+ Bounds on condition numbers: It is shown that the lower bound for ResCGPK matrices is lower than that of CGPK matrices.\n+ The authors claim that they are the first to establish a relationship between skip connections and the condition number of the kernel matrix.\n\nWeaknesses and open questions:\n- 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. \n- What is the additional challenge of considering convolutional residual kernels in comparison with the derivation of fully-connected ones?\n- What is the exact additional challenge in the derivation of the bounds on the eigenvalues in comparison with convolutional kernels?\n-> It sounds like a minor technical contribution to simply combine derivations for fully-connected ResNet kernels and convolutional kernels.\n- 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.)\n- How sharp is the bound in Thm. 5.2?\n- The experiments could be extended in support of Thm 5.2. An analysis of the dependence on the depth $L$ is missing.\n\nPoints of minor critique and open questions:\n- The need/advantage of considering three different heads could be better motivated on page 4.\n- How is the set $\\mathcal{R}$ defined in Theorem 5.1?\n- How is $C_0$ defined on page 6? Is it also just an existence statement? \n- How is the number of paths $p_i$ scaled in the infinite width limit? Is this quantity not diverging?\n- It could strengthen the last result on the condition number to discuss briefly why a slower diverging condition number could help in practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Wys50JR_ay", "reviewer": "Reviewer_zQoE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "strength_and_weaknesses": "Strengths\n- The effect of skip connection is rigorously analyzed in the language of kernels. \n- The eigenvalues of the kernels are evaluated.\n\nWeaknesses\n- There's no clear outcome for practitioners. It's not straightforward to utilize the theoretical results for new methods/algorithms/architectures.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Kw5lTHjjDN", "reviewer": "Reviewer_TKdt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "summary_of_the_review": "Good paper, interesting and significant contribution.", "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.\n\nThere are nonetheless a few questions which could deserve more discussion:\n\n* 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?\n\n* 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?\n\n* 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%