On the Spectral Bias of Convolutional Neural Tangent and Gaussian Process Kernels
Authors: Amnon Geifman
Meirav Galun
David Jacobs
Ronen Basri
Venue: NeurIPS 2022 Accept (2022)
Keywords: Convolutional Neural Tangent Kernel
Spectral Theory
Reproducing Kernel Hilbert Space

Abstract: We study the properties of various over-parameterized convolutional neural architectures through their respective Gaussian Process and Neural Tangent kernels. We prove that, with normalized multi-channel input and ReLU activation, the eigenfunctions of these kernels with the uniform measure are formed by products of spherical harmonics, defined over the channels of the different pixels. We next use hierarchical factorizable kernels to bound their respective eigenvalues. We show that the eigenvalues decay polynomially, quantify the rate of decay, and derive measures that reflect the composition of hierarchical features in these networks. Our theory provides a concrete quantitative characterization of the role of locality and hierarchy in the inductive bias of over-parameterized convolutional network architectures.


On the Spectral Bias of Convolutional Neural Tangent and Gaussian Process Kernels
Amnon Geifiann
Meirav Galun'
David Jacobs?
Ronen Basri'
Department of Computer Science, Weizmann Institute Science, Rehovot, Israel
(amnon. geifuan, meirav. meirav.galun, galun, ronen. baeri)
*Dpaarmeent Computer Science, University Maryland, College Park, MD
djacobsRes..
Abstract
We study the properties of various per-aaaratterzedd convolutional neural archi- tectures through their respective Gaussian Process and Neural Tangent kernels. We prove that, with normalized multi-channel input and ReLU activation, the eigen- functions of these kernels with the uniform measure are formed by products of spherical harmonics, defined over the channels of the different pixels. We next use hierarchical factorizable kernels to bound their respective eigenvalues. We show that the cigenvalues decay polynomially, quantify the rate of decay, and derive measures that reflect the composition hierarchical features these networks. Our theory provides concrete quantitative characterization of the role of locality and hierarchy in the inductive bias of over- pere-aaemteereeed convolutional network architectures.
Introduction
23 have produced dramatic improvements over past Two key properties that distinguish CNNs are their ability to encode geometric properties of the data, by incorporating multiscale analysis and invariance or equivariance. Shift invariant networks produce the same output when the input shifted, which can be valuable, for example, in classification tasks in which objects are not well aligned. Shift equivariant networks produce shifted output when the input is shifted, and are important in image- to-image networks that, for example, denoise segment the input (2 24 37.. Multiscale feature representations naturally arise in these networks as the receptive field size varies with depth.
Convolutional Neural Networks (CNNs)
machine learning approaches (22 35 18
However, still lack theoretical analysis of CNNs that quantitatively predict their behavior. Our analysis builds on the Gaussian Process and Neural Tangent kernels (resp. GPK and NTK). has been shown theoretically that massively overparameterized networks can be well approximated by a linearization about their initialization I 15, 20) With this linearization, neural networks become kernel regressors, with training dynamics and smoothness properties determined by the eigenfunctions and eigenvalues their kernel, which determine their Reproducing Kernel Hilbert Space (RKHS).
series of interesting works has derived the spectrum of NTK for fully connected networks (denoted FC-NTK). This rigen-analysis tells us which functions network learns most rapidly, since the speed of learning an cigenfunction with gradient descent (GD) inversely proportional to the corresponding eigenvalue 66) For example, it allows us to determine that FC-NTK learns low frequency components of function faster than high frequency components, and characterize the rates at which this happens 6 g 9 So this eigen-analysis allows to characterize the inductive bias of over-vvvamne per-parametrized neural networks. Convolutional GPKs and NTKs (resp. CGPKs and CNTKs) have been derived for
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

convolutional networks 2, but a characterization of their inductive bias is still missing, despite several recent works that provide only limited characterizations (see review in Sec. 3.
In this paper we investigate the Gaussian Process and Neural Tangent kernels associated with three deep convolutional architectures. In particular, we consider kernels associated with shift equivariant architecture, a convnet in which the last layer is fully connected, and a convnet with a final global average pooling step. The former network is applicable to various image processing tasks. The The latter network resembles a residual network [8], without skip connections. All models we consider use ReLU activation.
second network is similar in architecture to AlexNet and VGG 22 35
We assume our networks receive maaltichannell input signals, with the channels for each pixel normalized to unit norm. Our results establish that the eigenfunctions of the kernels include either products of spherical harmonics (SH-products) or sums of SH-products that are invariant to shifting the input. The eigenvalues of these kernels decay polynomially with the frequency of the eigenfunctions with a leading coefficient that is determined by the hierarchical architecture of the corresponding CNN. Consequently, for the equivariant network the eigenvalues are larger for functions that are localized in the center of the receptive field. For the other two networks the eigenvalues are larger for functions that are spatially localized (in any position in the input image). This spectral analysis implies that like FC-networks, CNNs are biased to learn low-frequency target functions more quickly, Unlike FC-networks, they can more quickly learn high frequency functions when these are variable in small neighborhood of pixels. (Note that high frequency reflects high variabilityy of the target function for similar input images and does not refer to the power spectrum individual images.)
2 Preliminaries and notations
We consider multi-channe' I-D input signal x of length d (referred to pixels), each with channels. We represent x by Ç x d matrix and denote the i'th pixel by x(*) E RS, E [d]. We further set D <d. We note that our results can readily be applied also to 2-D, multi-channel signals. We assume further that the entries of each pixel are normalized unit norm, i..., ||x[||| (1
= 1. The input space, therefore, a Cartesian product of spheres, which we call multisphere, i..., x E MS(C, d) = = x x gc-1 C v Dd (i.e., a sphere with radius v²).
We use multi-index notations, i.e., n = (ni.... na): k = (ki, ka) E N4, to denote vectors of polynomial orders or frequencies. N denotes the natural numbers including zero, and bn Ale scalars that depend on vectors of indices n or We denote monomials by t. 1 fiz
R are
la with t E Rdd and allow also for a scalar exponent, i.e., t" (41 Lt)". ". For u, E Rd we say that u v if ui 2 U; for all i E [d]. Therefore, the power series Enzo bnt should read
En, 20... Maa.ma..... "......"'1""" 12
We denote by 8,X (x (1+1) (d)) (1), (..)( the cyclic shift of x to the left by pixels. We denote the uniform distribution in domain Ω by UI). We write f(x) g(x) when limg-+x (x))/(()) = Throughout the paper we assume all kernels are differentiable at zero infinitely many times and their power series converge in the hypereube [-1, 1]d Our theorems and lemmas are proved in the supplementary material.
2.1 The network model
We consider convolutional neural network architectures (Figure I of the following form. Given multi-channel 1-D input signal x E MS((,, d) arranged in a Ç x d matrix, we use a shift equivariant backbone and three heads to produce scalar features. The network includes L > 2 layers. The first layer implements a x 1 convolution layer. This is followed by with filters of size q, producing at each layer the same number of feature channels in each of the d locations.
stride 1 convolutional layers
The [ head implements fully convolutional network; it produces one scalar entry for the shift equivariant network (i.e., the tuple (F [E (sa-1x.)) produces the shift-equivariant out- put). f corresponds to applying fully connected layer at the top layer. Finally, fGAP corresponds

---

(x, 01 = (w())))
f
(x, a (v me (2n= fite * 15
(x. (x..i)).
with {3, (3,...,
[on], theee hends
GAP
GGPP
(u ( 0) - (w ef ( (x,,)).
(N) (P)( 6) = tt (w (x)) A1)
() (GAT(xx j 8)1.
babbbenc
Figure 1: Left: Network architecture. An input signal E BCxd (left column) is fed into equivariant backbone (dashed box), producing m feature channels for each pixel, first using x convolution, followed by 7-11 convolution layers with filters of size (marked by blueish Pa pyramids), interleaved with ReI.U activation. The backbone is followed by one of three heads, f f and pGAP, Right: The corresponding formulas. Here W(L), W w.w.Gl GAP w wBB)
r()) mxd (1 [L]): 0 (w-1))
learnable parameters initialized with (OO, I). W(() E RRT w E Roxmxm (i.c., W:l)) a filter of size ②). W E Rmxd ((.-) denotes the standard inner product between matrices), wBa, w GAP <gixm and 1 (L.... 1)a E R.. "*" denotes eyclic convolution; is the ReLU function, and for ReLU, co = 1/ (E=)
Table I: CGPK and CNTK formulas. Given x, Z E MB(C, d), we denote respectively by X and Z their Ç X d matrix representations. Here denote by E. E., and Ô respectively Σ, 5 and @ whose rows and columns are extended with circular padding. Additionally, with ReLU activation (o(u) arccos(u)/rt and (u) uu) + v1 u²/m, [-1,
tar (x, (x) 2) x For! 6 (n)d,, [d],
CGPK-EENNe (cocrespands (aay (x,
(()) (x.x) (=l)) (x.
CGPK (corr. TT y 4 1 2/ (x.
$00 (x, x) (x (xx=))
CGPK-GAP (coer, (CAP,, Σ Eg 2! (x.
(ll) (x.x) 2/ Σi=0
()
CNTK-EqNet Bay, a1.11 (x,
i4
CNTK Tiy. 2 Ets ( (x, CNTK-GAP (oor to y to Dd. Ed o (x..))
((++)) (x, = m1 me=d (xx (x).
5. s((+)
(x,x) na Exnd s00
to applying global average pooling, resulting in a shift invariant network. With each of the heads, the network parameters are trained for regression with the mean square error (MSE) loss.
2.2 Derivation of CGPK and CNTK
Previous work showed that in the limit of infinite width and with small initialization, massively wverpparameterized neural networks become kernel regressors with family of kernels called Neural Tangent Kernels 20 Let f(x, 0) denote network, then for pair of inputs X,, the corresponding
NTK is defined as k(x,,x,) = Ee-p [8)(x.9)
#f(x,0)) a0 A related kernel, called the Gaussian Process (or random feature) kernel, is obtained the weights are kept in their initial random values,
80
and only the last layer of the network is optimized in training [B3]
2 derived expressions for CNTK and CGPK for convolutional networks and noted that they can be computed for a pair of inputs in ( The formulas in Table [ adapt these expressions to our convolutional architectures and to multisphere inputs. We note that with general input in R2D additional normalization steps are needed. We refer the reader to [2] for the full derivation.
Note that for a pair of inputs z, this definition produces two matrices of kernels, E (x, 2))
(
and (, (x, 2), i E [d]. and that x (x. x) >x(,1 (s; xx 1z) (and similarly for θ). With these définitions, we produce six different kernels Table - describe three different architectures for each of the Gaussian Process and the Neural Tangent kernels.
3

---

Below we refer to these six kernels as CGPKs and CNTKs. Note that CGPK-EqNEE and ENTK-EENet each produce a single output, corresponding to the first output of the equivariant network. The tuple (R(s0xx 80%), 1 -4-12/) - E IR (with & either CGPK-FqNet or CNTK-EqNet) produces the full response of the equivariant network.
3 The RKHS of CGPKs and CNTKs
Our objective is to derive the spectrum of Gaussian Process and Neural Tangent kernels associated with convolutional networks. We do so by forming bounds using products of kernels that apply to individual pixels and composed hierarchically. Prior work FC-NTK has benefited from the fact that they are dot product kernels, allowing the analysis to draw on a rich body of results. Our task is challenging since the kernels study are not dot product kernels; tools for spectral decomposition of these kernels on the sphere are scarcely available. We approach this problem by first proving general results for kernels that are functions of inner products between pixels (Sec. 3.1p. We next consider factorizable kernels and derive their spectrum (Sec. (32). Then, in Sec. 3.3 we refine our expressions to account for hierarchical kernels. We finally use these derivations in Sec. and 3.5 prove bounds for all six kernels.
3.1 Multi-dot product kernels
It can be readily shown that CNTK and CGPK associated with the shift equivariant network are functions dot products of corresponding pixels. We refer to such kernels as multi-dol product and prove in the supplementary material several new results regarding their spectral properties, briefly summarized here.
We call a kernel (xx, z) MS(S, d) x MIS(( d) - R. multi-dor dot product if k(x, z) k(t), where t = ((x(2), ) (1) .... (x z 2()))) E 1-1, (Note the overload of notation, which should be clear
by context.) Multi-dot product kernels can be written via Mercer's decomposition
R(x, = Σ A (x
(1)
kj
where (x) (k,j N the eigenfunctions of k. are products of spherical harmonics in g<-1, (x) = I Yuuj. (x with k 2 0, J: E [N(,, and N(C, k;) denotes the number of harmonics of frequency h; in S Such products are harmonic polynomials in SD-1, With (= 2, these are products of Fourier series in multi-dimensional torus. The eigenvalues Ak depend on the vector of frequencies, k, and are independent of the phases j. We note that a multi-dot product kernel is universal for MS(C, d) if all its eigenvalues are strictly positive. Non-universal kernels are obtained, e.g., when the eigenfunctions involve pixels outside of the receptive field of the respective network, in which case these eigenfunctions lie in the null space of the kernel.
Below we consider kernels that can be expressed using a multivariate power series of the form
E(t) = Σ by t n>0
Σ b. n20
I
with bn 2 for all n 2 0. It can be readily shown that our CGPKs and CNTKs are positive semidefinite (PSD) and their power series coefficients are non-negative; the kernels are obtained from the univariate PSD Ko and Kn (defined in Table whose coefficients are non-negative, by sequences of multiplication, addition and composition, resulting in PSD kernels with non-negative coefficients.
The eigenvalues of multi-dot product kernels can be deduced from their power series coefficients. This is established in the following lemma, which extends result by [3] 32) to multi-dot product kernels.
Lemma 3.1. Let k. be multi-dot product kernel with the power series given in 2 where x(1), 2(0) g respectively are pixels in x, z. Then, the eigenvalues >x of k are given by
(k)) = =|38 1
bk+22
Ak. (2/++20)))
620

---

where 3 is the surface area of and (t is the k 'th eigenvalue of t", given by
r c-1
r
n-
k+1
n!
(t (n - k-)2ktt
n
if nt - k is even and non-negative, while >x )- = 0 otherwise, and I' is the Gamma function.
Lemma 3.1 generalizes a result by (Thm. 4.1), which deals with the special case of kernel
made of single convolutional layer followed by L FC layers. Our result applies any multi-dot product kernel, including convolutional kernels arbitrary depths such as CNTK and CGPK.
3.2 Factorizable Kernels
Next, we consider multivariate kernels that factor into products of dot product kernels, ( 2)
IT ((x((), ))) The power series of & can be written as k(t) II
Zm=0
Un
Their
eigenvalues satisfy A (R) = -T X (A:) and can be calculated using Lemma 3.1 Below we are interested specifically in kernels whose power series decay polynomially with frequency. The next theorem shows that for such kernels, the eigenvalues too decay polynomially and derives their exact decay rate. For the theorem we further use the concept of a receptive field, which captures for multivariate kernel the subset of variables depends on. That is, the receptive field C [d] the set of indices for which there exists n (...,,Ti,, fli with nę 2 and bn j O. This condition ensures that there exists a term in the power series expansion that depends on pixel i.
Theorem 3.2. Let be a factorizable multi-dor product kernel with inputs x, MS(C, and ler R C [d] denote its receptive field, Suppose that k can be written as multivariate power series, k(t) = Σnzo bnt" with bn ~ c elliER, n:>0 n4 with constants > O, non-integer v > 1, and on = if for any & R. Then the eigenfunctions of w.r. the uniform measure are the SH-products. Moreover, let k E Nd be a vector of frequencies. Then, the eigenvalues >x(k) satisfy
Ak C.
II
k (c+2v-3)
iER, A.30
Finally. As- = 0 if > for any i R.
The theorem above significantly improves over previous results by 3 in various ways. Specifi- cally, these authors considered only dot product kernels (i.e., d = 1) and bounded the decay of their cigenvalues by a non-tight upper bound. Here we provide both tight upper and lower bounds, which identical up constant factor, for any d > 1.
3.3 Pusitional bias of eigenvalues
CNNs process signals by producing hierarchy of learned features that emerge via repeated con- volutions, interleaved with non-linear activations. It is natural to ask, therefore, to what extent this hierarchy is reflected the RKHS of the CGPKs and CNTKs. To answer this question we consider kemells formed by hierarchical composition of kernels. We are further interested in such kernels that are both factorizable and whose power series decay polynomially. For such kernels we prove that larger for eigenfunctions that depend pixels near the center of their receptive
their eigenvalues eigenfunctions that depend only on peripheral pixels. This in turn will allow us field and smaller for to derive similar bounds for the kernels associated with the equivariant network. For the trace and GAP kernels this will reveal bias to eigenfunction that depend on nearby pixels, compared to those that depend only on more distant pixels.
[-1,1] + R is called (stride-1) hierarchical of depth L > 1 and filter size if there exists a sequence of kemels ((1) .... ((() such that (0)(t) p(() (sot) (s,- with f()) Ra + R and k (t))t) = (()) e [-1,1]
Definition 3.3. A kernel (L)
Similar to feed-forward networks, hierarchical kernels induce a tree structure in which the leaf nodes represent the variables t,,... ta and parent nodes represent function applications f(),, Each variable
5

---

may be connected by multiple paths to the root node, which corresponds to the final kernel k (1))) The
number of paths from node i; to the root, denoted p; (Z) plays important role in the magnitude of the eigenvalues, In the next theorem we bound both the power series coefficients and the eigenvalues
of hierarchical kernels, showing that the bounds depend on the number of paths in the hierarchical tree, which in turn is determined by the position of the pixel within the receptive field.
Theorem 3.4. Let (L Enzo bat" be hierarchical and factorizable of depth L > 1 with filter size q so that bn = c cl "²" for non-integer v > Then there exists a scalar A > 1 s.t.:
1. The power series coefficients of (LL) satisfy bn 2 ct
i=1 Aminly! mn)
1220
2. The eigenvalues >ae (xe(k satisfy A 2 ET
Amiu(p!
! ki
1o0k-((tt) (5+2u-3)
where cL, čL are constants that depend on L, and pj pa") denotes the number of paths from pixel to the oulput of k(L)
The proof exploits relations between hierarchical stride-1 and stride-q kernels and relies on recursively combining power series, which are shown to maintain their polynomial decay. We note that although the number of paths can grow rapidly with depth, the kernels we consider are normalized so that they always produce values in [-1, 1]. As result, both the power series coefficients and the eigenvalues are bounded in [o, 1]. This normalization is reflected in the magnitudes of c, and ěμ.
In fact, for hierarchical, stride-1 1 kernel of depth L,, the (normalized) number of paths p; (1) of pixel, (0)), decays exponentially with its distance from the center of the receptive field, - The number of paths is determined by convolving a rectangular function of width q. the size of the convolution filter, (i.e., r(x) 1/g if 0 < x S q and O otherwise) with itself L. times. Note that such a repeated convolution is equal to the density function obtained by summing L random variables distributed uniformly, resulting in the Irwin-Hall distribution, whose support is stretched by the size of the convolution filter g. With sufficiently large L, using the central limit theorem and assuming the number of pixels d is greater than the receptive field size, the number of paths p²(4) approaches Gaussian centered at the central pixel with variance Va, L R Lq² i.e., p),²) xx exp(-(i i (2)2/(22,,t)) 25 Roughly speaking, we conclude that the position of pixel within the receptive field has an exponential effect on both the power series coefficients and the eigenvalues of the kernel.
Note that in the analysis above assumed that the number of pixels d is larger than the receptive field size. With a receptive field of size d and cyclic convolutions, the number of paths from all pixels approaches constant as T. grows. In practice, real CNNs use zero padding, which effectively ensures that d is always larger than the receptive field size.
3.4 Kernels associated with the equivariant network
The following theorem characterizes the spectrums of CGPK-EqNet and CNTK-EqNet, by proving lower and upper bounds on both their power series coefficients as well as their eigenvalues.
Theorem 3.5.
Let (L) denote either CGPK-EqNet or CNTK-EqNet of depth L whose input includes < channels, with receptive field R and with ReLU activation. Then,
1. R (L) can be written as power series, te (L(()(t) = =Enz0 bnt with
II
Amin(p! (1) mn 25 bn 0
II n
C1
:ER,n;50
iE iER.
2. The eigenvalues of (1) are bounded by
C3 II
Aminiy (1) (e)) k,
((S+2) < Av S C1 II
k
(4+2u-33
ER
1ER
R220

---

Power series conficiintaa cCPk-Eqlee
Power seriea contickrtss (ONTI-Egpee
Leading coefficients for Ra61
L:30
L=15
Logg
Weight 2 6
Q-11. LaB
9-7,
logg
9-10. L+6
Pixel distance
Figure 2: The power series coefficients of CGPK-EqNet (left, n S 50) and CNTK EqNeet (middle, S 20). Here d 2. g 2, I, and the receptive field size is 2. The coefficients, ba, marked with blue points, are shown as functions of n = (m)) Our bounds are depicted each graph by two planes whose slopes are determined by the exponents in Thcorrm 3.5 Right: The figure shows the relative magnitude of the eigenvalues of a hierarchical trace kernel for SH- HH--products involving two pixels as a function of the distance between the pixels. This is shown for various architectures with different depths L and convolution filter sizes g that results the same receptive field size of 61.
where for CGPK-EqNet v =1+3 (2d) and for CNTK-EqNet v = =1+ 1/(d). Also, th denotes the number of paths from pixel to the output of t kL),, À > 1 and C2, C3 and e4 depend on L.
The proof relies on the recursive formulation of the kernels, which gives rise to a multivariate version of the Faá di Bruno formula [4. involving Bell polynomials; those are exploited to bound the coefficients of the power series expansion of the kernels. The implication of Theorem 3.5 is that CGPK- Net and CNTK-Eq are bounded from above and below by factorizable kernels. The eigenvalues of these bounding kernels decay polynomially with the product of the frequency in each pixel, K; with an exponent that depends on S, the number of input channels. While this implies in general that with GD, low frequencies are learned faster than high frequencies, the theorem also states that it should be faster to learn target functions that vary (i.e., have high frequencies) in a small set of pixels compared to ones that vary many pixels.
Recall that learning an eigenfunction with eigenvalue À requires O(1/)) GD iterations (e.g.. (6). Therefore, for example, according the lower bound in Thm. 3.5 learning an SH-product of fre- quency k in one pixel and constant frequencies in the other pixels should require O(K5+2) GD itera- tions. Learning an SH-product of frequency le/ m in each of m pixels should require O((k (((kmm)mm m))(((+)) iterations. With & > m. this exponentially slower by factor of m. With m d, the speed of learning decays with an exponent that depends on the size of the entire signal. For such functions, over-parann werrpaaameeterized CNNs behave similarly to fully connected networks, for which the eigenvalues of their respective kernels, FC-GPK and FC-NTK, decay as resp. (D(++)) and kD for input in SD-1 17 Note that the exponent in the polynomial decay does not depend on q. the size of the convolutionn filter. We conclude that over pee-pparamtterieed CNNs can more efficiently learn target functions whose variation is restricted to subsets of the pixels. This is not true for fully connected networks. We further illustrate this difference between convolutional and FC kernels in Sec. 3.5 where we numerically compare the cigenvalues for the trace kernels.
While the form of the polynomial decay induces bias toward learning functions that depend on fewer pixels, according to the lower bound the multiplicative factors of these polynomials exhibit bias toward learning functions in which the variation is localized near the center of the receptive field, This bias is affected by the number of paths from a pixel node to the output and depends on the depth and the size of the convolution filter q.
Figure 2 provides a visualization of the power series coefficients of CGPK-EqNet and CNTK-EqNet for d = 2 and q 2. The upper and lower bounds, plotted as planes in these log-log plots. indicate the maximal and minimal asymptotic directions determined by the exponents in Theorem 335 The coefficients indeed appear to lie between the bounds, with coefficients of orders that vary along single axis (i.e., (n, 0)) lying close to the lower bound, while those of orders that vary simultaneously along both axes (i.e., (n, n)) lie close to the upper bound. In this example the number of paths equal for both pixels, so position does not affect the coefficients.
3.5 Trace and GAP kernels
Our next objective is to characterize the RKHS of CGPK and CNTK and their GAP versions.
7

---

Reporation doaay (COPH)
Digernalus decey (CSPI
Epeeaati doaay of FC-PPK
log.
los
Figure 3: Left: The eigenvalues of CGPK for frequency patterns that include either non frequency (blue dots), two (orange). three (green) or four (maroon) identical frequencies. The slopes (respectively. 5.18, -7.06, 88.24 and -9.64) indicate the exponent for each pattern. Middle: The eigenvalues CGPK two frequency patterns that include exactly two non zero frequency, either next to cach other (red dots) or separated by one zero frequency (blue). Consistent with our theory. the eigenvalues obtained with non-zero frequencies next to each other are larger than those obtained with the same frequencies but separated. Right: The eigenvalues FC-GPK on MIS(C, d) for frequency patterns that include either one non zero frequency (blue dots), two (orange), three (green) or four (maroon) identical frequencies. The slopes (respectively, -11.26, 10..22, 100.20 and 10.04) indicate the exponent for each pattern. We used d = 4. C = 3, 2, L = 3 in these plots.
Definition 3.6. Let R(x, z) be multi-dot product kernel. We define the respective trace kernel by "T 2) = Ei= k(s,x, s,z) and GAP kernel by k GAP (x, z) = - Di= Σ k(s;x, s,z).
Clearly, by their definition (Section 2.2). CGPK and CNTK respectively are the trace kernels of CGPK-EqNet and CNTK-EqNet, while CGPK-GAP and CNTK-GAP are their GAP versions.
The eigenvalues and eigenfunctions of trace and GAP kernels can be derived from their generating kernel, as is established in the following lemma.
Theorem 3.7. Let & be a multi-dor dot-product kernel with Mercer's decomposition as in ① and let Th and k GAP respectively be its trace and GAP versions. Then,
1. k (x, Ens X (x)(()))x(()) with X = 1ET Ao where Ak denotes an eigenvalue of k.
2. k: GAP (x, AR (x) with (x)(x)= Va EE Y (x).
According to this theorem, the eigenfunctions of a trace kernel are the SH-products. This is simply because the trace kernel itself multi-dot product. Its eigenvalues are obtained by averaging the eigenvalues of & for shifted frequencies s;k, making the eigenvalues Λ invariant to shifts of the index vector k. Note however that for trace kernel, the respective eigenfunctions are not shift invariant. The second part of the lemma establishes that GAP kernels share the same eigenvalues as their respective trace kernels. For these kernels, however, the eigenfunctions consist of sums of SH- tH-products that are shift invariant.
By combining Thms 3.7 and 3.5 we obtain the following bounds on the eigenvalues of these kernels.
Corollary 3.8. Let (L) denote either CGPK, CGPK-GAP, CNTK or CNTK-GAP of depth L whose input includes Ç channels, with receptive field R and with ReLU activation. Then, the eigenvalues of (LL) are bounded by
d-1
d-1
Ee3 J=D
II
(C+2) < Ak S Amiu(pb20 (n)k(pp ( kitt
Σ C4
II
(CC+2u-3)
C3
k
iER
j=0
iER Ki0
where for CGPK, CGPK-GAP 1//221) while for CNTK, CNTK-GAP 1 1/(2d). Also, Pi
(1) is defined in Theorem 3.5 i.e., the number of paths in the equivariant kernel, À > 1 and and
C4 depend on L. Here ketz is identified with + j i + d.
Overall, Corollary 3.8 indicates that the eigenvalues of the trace and GAP CGPK and CNTK decay polynomially with bounds that are similar to those the equivariant kernel. Here too, the exponent depends on the number of channels and forms bias toward learning target functions that depend
8

---

Eigenaaiue daday (CGPH) without fxi
E Eieensats decey (CGPH) Mihouu txt
Learning Eigntlnnciion With Real Network
Tropan
Log Murstee Moaeeetrrr
E-
log.
4
k
Figure 4: Left: The eigenvalues of CGPK without the x convolution. Eigenvalues for different frequency patterns that include either one nonzero frequency (blue dots), two (orange), three (green) or four (maroon) identical frequencies. The slopes (respectively, -7.32. -7.11, - 8.58, -9.89) indicate the exponent for each pattern. Middle: Figenvalues for two frequency patterns that include exactly two nonzero frequencies, either next to each other (red dots) separated by one zero frequency (blue). Black lines indicate differences from the values shown in Figure 3 (d = 4. < 2. q 2. L 3.) Right: Convergence times of real networks, CNN (solid dark and light blue curves) and a fully connected network (dashed black and dotted red). trained to fit various SH-prout 3H-products. (d 8, Ç = 2, q = 2, L = 4.)
on few pixels. The multiplicative coefficients depend on the number of paths from each pixel the output in the corresponding equivariant kernel. In contrast to the equivariant kernels, the eigenvalues of the trace and GAP kernels are averages over shifted indices, and therefore they depend on the relative positions of pixels. For example, the eigenvalues of SH-products involving only two pixels with large frequencies, k; and k large when 8 is small, and is smaller when d large. This is illustrated in the graph in Figure (right), which shows the relative magnitude of the eigenvalues, according to the lower bound, involving exactly two pixels as function of their distance. It can be seen that the coefficients decay exponentially with the distance between the two pixels. Moreover, for a fixed receptive field size, a more rapid decay is obtained with a smaller filter and deeper architecture, compared to a larger filter and shallower network.
The graphs in Figure Ieff and middle) show the eigenvalues of the CGPK kernel evaluated numeri- cally for three-layer network. The figure shows the cigenvalues for fiequeeniess & in 1-4 pixels. The slope of these lines, which depicts the exponent of the decay of the corresponding eigenvalues, is in good correspondence with our theory. Moreover, consistent with our discussion in Sec. 634. the decay rate is higher for frequencies spread over more pixels. This can be contrasted with the eigenvalues for the Gaussian Process Kernel for a fully connected network (FC-GPK) shown in Figure rrgght) For that kernel, the decay rate is the same regardless of the pixel spread of frequencies, as is indicated by the parallel lines in the graph, and is similar to the maximal decay rate obtained for CGPK with d == 4 pixels. Figure midddle further shows the eigenvalues of CGPK obtained with two frequency patterns. (k1, f2, 0, O..). and (k1, O, k2, ...). As is predicted by our theory, while the decay rate for both patterns is similar, the cigenvalues for high frequencics in two adjacent pixels are larger (by a multiplicative constant) than for the same frequencies in two non-adjacent ones. This is of course not the case with FC-NTK, in which the spatial location of pixels makes no difference.
Removing the 1 X 1 convolution: Our analysis uses network models which include a 1 1x 1 convolution in the first layer. This simplifies our derivations and appears to have only limited effect on the analysis. In particular, it can be readily shown that for data distributed uniformly on the multisphere, the eigenfunctions of CGPK and CNTK without the x 1 convolution are the SH-products (or their shift invariant sums in the case of GAP kernels). Figure left and middle) shows the eigenvalues of CGPK under the same conditions as in Figure 3 with the 1 x convolution removed. Overall, similar decay patterns are observed, except that with 2 in the case of high frequency in one pixel (denoted "(k, O, O, 0)') the eigenvalues decay faster than with the 1 x convolution.
Real networks: We further tested our predictions on two real networks, CNN and fully connected architecture. We trained the networks fit various SH-products in which the higher frequencies (k = 1,.., 4) are positioned at either two neighboring or two distant pixels and measured the number of iterations to convergence. Figure right) shows that, consistent with our predictions, the CNN learned each function faster than the FC network. Moreover, the CNN learned the localized functions faster than those in which the high frequencies are spread in distant pixels. The FC network, in contrast, required the same number of iterations to converge for both types of functions.

---

4 Related Work
A number of papers analyze the spectral properties and generalization bounds for convolutional kernels, including CNTK. [9] derived explicit feature maps for CNTK. 29 developed spectral decomposition and generalization bounds for CNTK with only one convolution layer and pooling with input in the nodes of the hyper-cube 1-1,1] [16] considered CNTK with just one convolutional layer that is applied to input comprising of non-overlapping patches. Such input is equivalent to applying only a 1 X 1 convolution layer in our setup. They showed that the cigenvalues decay for this kernel is dictated by the patch size (corresponding to the number of channels in our setup). Their limited setup yields Mercer's s decomposition similar to that obtained with NTK for a two-layer FC network.
[8 considered a network with one convolution layer with patches of full image size and inputs drawn from the uniform distribution on either the sphere or the hypercube. Their work focuses on the benefits of group invariance in reducing the sample size. [10] considered general kernels that
incorporate group invariance and derived generalization bound based on counting the number of cigenfunctions of the kernel. [38] studied the spectral properties of CNTK in a setting in which the frequency is held constant, while the input dimension tends to infinity. Subsequent to our work, MII] derived asymptotic decay rates of the eigenvalues of CNTK and further used these to derive a new generalization bound. Both of these recent works, however, are restricted to networks that involve convolutions with non-overlapping patches.
proposed convolutional kernel network (CKN) that involves layers of patch extraction, convolution, and pooling. Pooling in this model is implemented by a convolution with fixed filter such as a Gaussian, possibly followed by subsampling. We note that without subsampling. such pooling operation can effectively result a fully connected layer. [32 proved that the set of functions produced by the CKN network that applies convolution with non-overlapping patches is contained in the RKHS of a kernel that includes just one convolution layer. Similar to our work, their work used inputs drawn from multisphere, yielding eigenfunctions that are SH-products. Their spectral analysis however was applied to CKNs with only one convolution layer followed by a sequence of polynomial activations. M extended this setup to enable convolution with overlapping patches and further derive generalization bounds. In contrast to these works, our work shows that the SH- SH-pruducts are the eigenfunctions of all multi-dot product kernels and further provides spectral bounds for CGPK and CNTK for multilayer CNNs.
27 26
19 investigated the speed of convergence of GD for equivariant networks with fully connected layer followed by a fixed convolution layer in the context of image denoising. In a related work, [36] used NTK for two-layer network to relate denoising with CNNs to denoising with non-local filters. Existing work also investigates CNNs from a non-kernel perspective, for example, by showing that multi-layer CNNs (and related networks) can efficiently learn compositional functions 14]
5 Conclusion
Our paper has derived the eigenfunctions and corresponding eigenvalues of Neural Tangent Kernels that describe overparameterized CNNs. This provides us with a clear and specific understanding of these networks, just as much prior work has done for fully connected networks. Of particular interest, our work provides concrete understanding of the inductive bias produced by the hierarchical structure of deep CNNs. We see that CNNs can efficiently learn higher frequency functions than FC networks when these functions are spatially localized. We provide formulas that can show the trade-off points between higher frequency functions and spatial localization. and also show how architectural variations can affect these biases. We believe that this is significant step towards understanding which features CNNs will learn, and how this depend on network architecture. In future work we hope to provide tighter bounds for the eigenvalues, extend our analysis to residual networks, and further test our predictions on real convolutional networks.
Acknowledgement. This research was partially supported by the Israeli Council for Higher Education (CHE) via the Weizmann Data Science Research Center, by research grants from the Estate of Tully and Michele Plesser and the Anita James Rosen Foundation, and by the U.S. Binational Science Foundation, grant no. 2018680. DJ is further supported by the National Science Foundation, grant no. 19S-1910132 and DARPA's Guarantecing AI Robustness Against Deception (GARD).
10

---

References
[1] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over-parameterizatoo.. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 242-252, 2019,
[2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: /901. 1955, 2019.
[3] Douglas Azevedo and Valdir A Menegatto. Eigenvalues of dot-product kernels on the sphere. Proceeding Series of the Bruzilian Society of Compulational and Applied Mathematics, 3(1), 2015.
[4] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research,
6819,66822288 2017.
[5] Ronen Basri, Mcirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density. International Conference on Machine Learning, 2020.
[6] Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems, pages 4763-4772, 2019.
[7] Alberto Bietti. Approximation and learning with deep convolutional models: a kernel perspec- tive. arXiv preprint arXiv:2102.10032, 2021.
[8] Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. arXiv preprint arXiv:2009. 14397, 2020.
[9] Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. arXiv preprint a90iv: / 1233, 2019.
[10] Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning with geometric stability. arXiv preprint arXiv:2106.07148, 2021.
[11] Francesco Cagnetta, Alessandro Favero, and Matthieu Wyart. How wide convolutional neural networks learn hierarchical tasks. arXiv preprint arXiv:2208.01000 2022.
[12] Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. International Conference on Learning Representations, 2020.
[13] Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Y. Bengio, D. Schu- urmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
[14] Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: tensor analysis. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 698-728, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
[15) Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, Califormia, USA, volume 97, pages 1675-1685, 2019.
[16) Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse of dimensionality in convolutional teacher-student scenarios. arXiv preprint 2021.
[17] Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri. On the similarity between the laplace and neural tangent kemness. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 6-1 2020, virtual, 2020.

---

[18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[19] Reinhard Heckel and Mahdi Soltanolkotabi. Denoising and regularization via exploiting the structural bias of convolutional generators. arXiv preprint urxiv://100 (91.::/991..14444.. 2019.
[20] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems
31. pages 8571-8580. 2018.
[21] Jiwon Kim, Jung Kwon Lee, and Kyoung Mu Lee. Accurate image super-resolution using very deep convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1646-1654, 2016.
[22] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[23] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (0:211))277223333 1998.
[24] Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, al. realsssea single image resortienol using a generative adversarial network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4681-4690, 2017.
[25] Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard Zemel. Understanding the effective receptive field in deep convolutional neural networks. Advances in neural information processing systems, 29, 2016.
[26] Julien Mairal. End-to-end kernll learning with supervised convolutional kernel networks. Advances in neural information processing systems, 29:1399-1407, 2016.
[27] Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks. In Z. Ghahramani, M. Welling, Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[28] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. arXiv preprint
2021.
[29] Theodor Misiakiewicz and Song Mei. Learning with convolution and pooling operations in kernel methods. arXiv preprint arXiv:2111.0888 2021.
[30] Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. arXiv preprint arXiv:1810.05148. 2018
[31] Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but not shallow-networks avoid the curse of dimensionality: review. International Journal of Automation and Computing, 14(5):503-511 2017.
[32] Meyer Scethon and Zaid Harchaoui. Harmonic decompositions of convolutional networks. In International Conference on Machine Learning, pages 8522-8553 8532. PMLR, 2020.
[33] Meyer Scetbon and Zaid Harchaoui. A spectral analysis of dot-product kernels. In International Conference Artificial Intelligence and Statistics, pages 3394 3402. PMLR, 2021.
[34] Aidan Schumann. Multivariate bell polynomials and derivatives of composed functions. arXiv preprint arXiv: 2019.
12

---

[35] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
[36] Julian Tachella, Junqi Tang, and Mike Davies. The neural tangent link between enn denoisers and non-local filters. In Proceedings of the IEEE/CVE Conference Computer Vision and Pattem Recognition (CVPR), pages 8618-8627, June 2021.
[37] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Deep image prior. In Proceedings of the IEEE conference computer vision and pattern recognition, pages
2018.
[38] Lechao Xiao. Eigenspace restructuring: a principle of space and frequency neural networks. In Conference on Learning Theory, pages 4888-4944, PMLR, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is a theoretical work that has direct societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/relcusing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "eNkiteZbse", "reviewer": "Reviewer_sRWF", "summary": "The paper studies the spectral properties of convolutional kernels that are derived from spherical kernels. The inputs are treated as multi-channel, where each channel $\\zeta$ corresponds to a pixel from different patches $d$, such that the input space is the cartesian product of the $d$ hyper-spheres. The authors prove that the eigenfunctions of the studied kernels are either the product of spherical harmonics or the shift invariant sum of them, while the corresponding eigenvalue decay polynomially with the frequency of the eigenfunctions. Further, they prove that the lager eigenvalues are associated with the functions localised in the center of the receptive field of the patch. The authors conclude their analysis with evaluating the eigenvalues for the arc-cosine and the neural tangent convolutional kernels.", "questions": "Please see my detailed questions above under the sections of Quality and Clarity", "limitations": "The authors sufficiently discuss their findings and compare it to similar theoretical results in the literature.\nA nice point I would like to see is the computational requirements for evaluating the kernel. That would give the reader an estimate of how feasible would be to use such kernels in practice.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Originality\nThis is a highly theoretical paper. Spectral analysis of the kernel functions associated with deep neural network architecture with Relu activations has received a lot of attention over the past couple of years. This paper is explicitly focusing on the analysis of the behaviour of the convolutional spherical kernels. In that spirit, the authors extended the analysis from [31] to deep kernel structures with overlapping patches. They also have sufficiently covered the related work and commented on how their work improves upon the existing literature. In my opinion the analysis is novel and provides further insights on the behaviour of the deep neural networks.\n\n### Quality\nThe theoretical analysis is really good. The authors have demonstrated a high skill on deriving the end result, which I believe is significant.\nMy concerns are mainly with the results depicted in the plots and the quality of them. I also have some concerns regarding the presentation of the paper in certain parts.\n\n* To be honest I am really baffled with the extremely small values of the eigenvalues in Figure 3 to the point I am questioning my understanding. Coming from the result of Theorem 3.2, the eigenvalues should decay polynomially with the frequency and the degree of that polynomial is mainly determined by $\\zeta$. Given that in the computations the patch size is rather small, i.e., $\\zeta=2$, why is the value of the biggest eigenvalue at the order of 1e-11? I understand that the important quantity is the ratio of the eigenvalues, but still this is a remarkably small value. It cannot be that the $\\tilde{c}$ is that small, right?\n\n* Carrying on with the small values, I would also like to understand the reason behind the really small values of the $b_n$ coefficients in Figure 2. Yes, I expect that for the value of the $\\exp(50)$th coefficient will be practically 0. But what happens to the first 5-10 coefficients? Is their value sufficiently large? Is this just a scaling artifact of the plot?\n\nRegarding the presentation:\n \n* First of all, I believe that the authors could have been more explicit in setting up the problem. In the beginning of Section 2 there should be explicitly mentioning of what $\\zeta, d$ are. My understanding is that $\\mathbf{x}$ is a $\\zeta \\times d$ matrix, where $\\zeta$ is the pixels in the patch and $d$ the number of patches. Then the input space of product of $d$ spheres makes sense.\n* Despite the effort, Figure 1 is not very helpful in understanding the architecture. I had to rely on the actual maths and the shapes of the involved matrices to be sure of what is going on.\n* I do not understand the inline equation of the product of spherical harmonics in section 3.1 line 123. $\\mathbf{k}$ is a vector of frequencies, yet we have a product of only the $k_i$ frequency for all the patches that come after $i$. Why don't we have interactions of different frequencies between patches?\n* A short discussion right after Lemma 3.1 on the connection between the result and the one from [31] would be extremely valuable for solidifying the understanding.\n\n### Clarity\nAs I have already said this is a highly theoretical paper. The nature of the topic is already complicated and the required notation, together with the study of convergence bounds, do not make any favours to the reader. Having said that, the authors have done a really good effort to write and explain the paper.\n\nFew minor remarks:\n* Last paragraph in page 1 looks like having a smaller fontsize than the rest of the manuscript, please fix that.\n* Page 2, line 43, on the comment around intermediate pooling. I suggest you provide further discussion on that, as the introduction of intermediate polling, apart from requiring careful handling to keep the inputs to the next layer always normalised, it also changes considerably the geometry, since it messes with the receptive field at each layer.\n* Page 2, line 47. It would be wise to elaborate on what is the shift invariant sum of the spherical harmonics, as these contents have not been introduced yet.\n\n### Significance\nThe theoretical results presented in the manuscript are significant and a can potentially be a good addition to the literature.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_EL8jQzEZXI", "reviewer": "Reviewer_KKbC", "summary": "This paper studies over-parameters CNNs from the perspective of NTK and Gaussian process kernels. A concise analysis of the eigenvalues and eigenfunctions of these kernels are derived. In particular, bounds of the eigenvalues and localization properties of the eigenfunctions are given. They provide a better understanding of the inductive bias in CNNs. ", "questions": "In the introduction, when you talk about inductive bias and spectral bias, do you mean the same thing (line 33-35)? \n\nAs mentioned in the introduction, the eigenvalues are larger for functions that are localized in the center of the receptive field? Are you talking about the invariant kernel case as well (defined from f^GAP)? According to Corollary 3.8, it seems so. It seems to me strange that this could be true as the function f^GAP(x,theta) in invariant to the (cyclic) translation of x. Could you explain more in the text line 280? Also is k_{i+j} defined for i+j <=d in Corollary 3.8?\n\nThe function f^Eq is only keeping the first pixel in the output layer, am I right? It is thus not really equivariant if I understood, and this is why you got the previous localized eigenfunctions, am I right?\n\nCould you be more precise on what it means ~ in Theorem 3.2? Does that mean for k-> infty?\n\nWhat is SH product in line 226?\n", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is the derivation of the eigenvalue bounds for various kernels with different translation invariant properties (equivariant, non-invariant, invariant), by exploring multi-dot product structures in these kernels. What I find is not very clear is about the positional bias of eigenvalues in Section 3.3 (see questions next). Also the role of the hierarchy, as mentioned in the abstract, is not very clear. More discussions about them are welcome. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "RnT1Hvvu4KI", "reviewer": "Reviewer_uuHF", "summary": "The paper studies the inductive bias of deep convolutional architectures by studying spectral properties of the corresponding NNGP/GPK and NTK kernels. More specifically, the authors provide decay rates of power series coefficients and eigenvalues of various CGPK/CNTK kernels (\"equivariant\" where only one location is considered at the output, \"trace\" which corresponds to a fully-connected last layer, and \"GAP\", for global average pooling at the last layer). These illustrate how these architectures are biased towards certain functions that depend on few pixels, with preference for neighboring pixels.", "questions": "* Regarding the non-matching upper/lower bounds on eigenvalues (e.g. Theorem 3.5), could you elaborate more on which you think is tighter in which setting? It is mentioned that lower bounds may be tighter when only few pixels are considered, while upper bounds are tighter when more pixels are considered -- can this be formalized more precisely?\n\n* In corollary 3.8, for the Tr and GAP kernels, isn't $p_i$ the same for all $i$, given the symmetry of the kernels? If so, is there a better way to illustrate positional biases w.r.t. relative positions?\n\n* Can the arguments on number of GD iterations (paragraph starting at line 226) be made more formal? It would be good to have cleaner propositions for this, as it is not immediate from the statements on eigenvalues.\n\n* [This paper](https://arxiv.org/abs/2112.05611) seems closely related to the present manuscript and the authors should compare to it.", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written, and the problem studied is significant, as it provides new insight on the role of convolutional architectures in deep models. The theory is sound and the results are clearly positioned compared to other works in the area.\n\nCertain results are not fully tight, for instance some lower and upper bounds on eigenvalues are non-matching, which suggests that a tighter theory might be developed. However, this might be difficult to achieve given the complicated form of the studied kernels, so I believe the current results are already good enough for acceptance.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-K0EnMxnz0T", "reviewer": "Reviewer_Q2dg", "summary": "The paper studies the spectral bias of convolutional neural networks using the neural tangent kernel (NTK) and the Gaussian process kernel. Specifically, the paper derives the eigenvalues and the speed of learning of the eigenfunctions and illustrates how this differs from the fully-connected networks that were studied previously. The kernels studied are not dot product kernels, e.g. as in the fully-connected network analysis.  ", "questions": "Is there a typo in line 77 with the inequality? ", "limitations": "There are no limitations explicitly written in the paper. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[+] Understanding the inductive bias of neural networks is an important topic and convolutional networks are definitely a critical component. \n\n[+] The paper is well-written overall, offering insights on the spectral bias and the analysis required to achieve this using NTK. \n\n[-] Despite the attempt to move towards practical networks, the current format of the paper ignores skip connections (that are widely used in most of the practical networks) and also operations such as normalization. The NTK analysis for residual networks (in the fully-connected case) has already been conducted, so it would be a more complete result to have such cases with residual skip as well. \n\n[-] Even though there is a thorough theoretical analysis, the results illustrate that the convolutional networks learn higher frequency functions more efficiently than fully-connected ones (under some cases). However, there is weak empirical validation of this phenomenon (only Fig. 3). A stronger empirical evidence would make the claims of this work much stronger. \n\n[-] Minor: The paper requires proof-reading, since there are few errors, especially with parenthesis. For instance, in line 80 there is a parenthesis closing without one opening before. \n\nOverall, the paper makes a contribution towards understanding the inductive bias of neural networks, which is an important topic. However, there are few structural limitations at the moment, e.g. lack of empirical evidence, or lack of skip connections that are used in practice. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept