What can be learnt with wide convolutional neural networks?
Authors: Francesco Cagnetta
Alessandro Favero
Matthieu Wyart
Venue: Submitted to ICLR 2023 (2023)
Keywords: hierarchical models
kernel learning
neural tangent kernel
theory of deep learning
generalization
convolutional neural networks

Abstract: Understanding how convolutional neural networks (CNNs) can efficiently learn high-dimensional functions remains a fundamental challenge. A popular belief is that these models harness the local and hierarchical structure of natural data such as images. Yet, we lack a quantitative understanding of how such structure affects performance, e.g. the rate of decay of the generalisation error with the number of training samples. In this paper, we study deep CNNs in the kernel regime. First, we show that the spectrum of the corresponding kernel inherits the hierarchical structure of the network, and we characterise its asymptotics. Then, we use this result together with generalisation bounds to prove that deep CNNs adapt to the spatial scale of the target function. In particular, we find that if the target function depends on low-dimensional subsets of adjacent input variables, then the rate of decay of the error is controlled by the effective dimensionality of these subsets. Conversely, if the teacher function depends on the full set of input variables, then the error rate is inversely proportional to the input dimension. We conclude by computing the rate when a deep CNN is trained on the output of another deep CNN with randomly-initialised parameters. Interestingly, we find that despite their hierarchical structure, the functions generated by deep CNNs are too rich to be efficiently learnable in high dimension.

Under review as a conference paper at ICLR 2023
WHAT CAN BE LEARNT WITH WIDE CONVOLUTIONAL NEURAL NETWORKS?
Anonymous authors Paper under double-blind review
ABSTRACT
Understanding how convolutional neural networks (CNNs) can efficiently learn high-dimensional functions remains a fundamental challenge. A popular belief is that these models harness the local and hierarchical structure of natural data such as images. Yet, we lack quantitative understanding of how such structure affects performance, c.g. the rate of decay of the generalisation error with the number of training samples. In this paper, we study deep CNNs in the kernel regime. First, we show that the spectrum of the corresponding kernel inherits the hierarchical structure of the network, and we characterise its asymptotics. Then, we use this result together with generalisation bounds to prove that deep CNNs adapt the spatial scale of the target function. In particular, we find that if the target function depends on cwwdiimeniional subsets of adjacent input variables, then the rate of decay of the eπror is controlled by the effective dimensionality of these subsets. Conversely, if the target function depends on the full set of input variables, then the error rate is inversely proportional to the input dimension. We conclude by computing the rate when a deep CNN is trained on the output another deep CNN with randomly-inttialised parameters. Interestingly, we find that, despite their hierarchical structure, the functions generated by deep CNNs are too rich to be efficiently learnable in high dimension.
INTRODUCTION
Deep convolutional neural networks (CNNs) are particularly successful in certain tasks such as im- age classification. Such tasks generally entail the approximation of functions of a large number of variables, for instance the number of pixels which determine the content of an image. Learning generic high-dimensional function is plagued by the curse of dimensionality: the rate which the generalisation error decays with the number of training samples n vanishes as the dimensionality of the input space grows, i.e. E(n) ~ n with 3 = ((1dd) (Wainwright, 2019). Therefore, the success of CNNs in classifying data whose dimension can be in the hundreds more (Hest- ness et al.) 2017 Spigler et al. (020) points to the existence of some underlying structure in the task that CNNs leverage. Understanding the structure of learnable tasks is arguably one of the most fundamental problems in deep learning, and also one of central practical importance- it determines how many examples are required learn up to a certain error. popular hypothesis is that learnable tasks are local and hicrarchical: features at any scale are made of sub-features of smaller scales, Although many works have investigated this hypothesis (Biederman) 1987 Poggio
et al. 2017 Kondor & Trivedi 2018 Zhou et al. 2018 Deza et al. 2020 Kohler et al. [0020 Pog gio al. [2020] Schmidt- Hieberr 2020; Finocchio & Schmidt Schmidt-Hieber 2021 2021]/GGaal Giordano et al. (022),
there are no available predictions for the exponent ,3 for deep CNNs trained on tasks with a varying
degree of locality or a truly hierarchical structure.
In this paper we perform such computation in the overparameterised regime, where the width of the hidden layer of the neural networks diverges and the network output rescaled so as to converge to that of kernel method (Jacot et al.) 2018 Lee et al. 2019), Although the deep networks deployed in real scenarios do not generally operate in such regime, the connection with the theory of kernel regression provides recipe for computing the decay of the generalisation error with the number of training examples. Namely, given an infinitely wide neural network, its generalisation abilities depend on the spectrum of the corresponding kernel (Caponnetto & De Vito 2007 Bordelon al.

---

Under review as a conference paper at ICLR 2023
2020): the main challenge is then to characterise this spectrum, especially for deep CNNs whose kernels are rather cumbersome and defined recursively (Arora et al. 2019). This characterisation is the main result of our paper, together with the ensuing study of generalisation in deep CNNs.
1.1 OUR CONTRIBUTIONS
More specifically, this paper studies the generalisation properties of deep CNNs with non- overlapping patches and no pooling (defined in Sec. 2 see Fig. 1 for an illustration), trained on a target function f by empirical minimisation of the mean squared loss. We consider the infinite- width limit (Sec. 3) where the model parameters change infinitesimally over training, thus the trained network coincides with the predictor of kernel regression with the Neural Tangent Kernel (NTK) of the network. Due to the equivalence with kernel methods, generalisation is fully characterised by the spectrum of the integral operator of the kernel: in simple terms, the projections on the eigenfunc- tions with larger eigenvalues can be learnt (up fixed generalisation error) with fewer training points (see, e.g., Bach (202I)).
Spectrum of deep hierarchical kernels (Tmm 3.1). Due to the network architecture, the hidden neurons of each layer depend only on a subset of the input variables, known as the receptive field of that neuron (highlighted by coloured boxes in Fig. I left panel). We find that the eigenfunctions of the NTK of a hierarchical CNN of depth L + can be organised into sectors (= I= L associated with the hidden layers of the network Thm. 3.1. The cigenfunctions of each sector depend only on the receptive fields of the neurons of the corresponding hidden layer: if we denote with der(()) the size of the receptive fields of neurons in the 1-th hidden layer, then the eigenfunctions of the I-th sector are effectively functions of dar(() variables. We characterise the asymptotic behaviour of the NTK eigenvalues with the degree of the corresponding eigenfunctions (Thm. 3.1) and find that it is controlled by dln( As a consequence, the eigenfunctions with the largest eigenvalues the easiest learn are those which depend on small subsets of the input variables and have low polynomial degree. This is our main technical contribution and all of our conclusions follow from it.
Adaptivity to the spatial structure of the target (Cor. 4.1). We use the above result to prove that deep CNNs can adapt to the spatial scale of the target function (Sec. 4p. More specifically, by using rigorous bounds from the theory of kernel ridge regression (Caponnetto & De Vitol 2007) (reviewed in the first paragraph SffSe 4), we show that when learning with the kernel of a CNN and optimal regularisation, the decay of the error depends on the effective dimensionality of the target f--i.e., if f only depends on der adjacent coordinates of the d-dimensional input, then c ~ n -8 with 3 2 O(1/der) (Cor. 4.1 see Fig. for pictorial representation). We find similar picture in ridgeless regression by using non-rigorous results derived with the replica method (Bordelon) al., [220 Loureiro et al. [021) (Sec. 5). Notice that for targets which are spatially localised (or sums of spatially localised functions), the rates achieved with deep CNNs are much closer to the Bayes-optimal aates-realise when the architecture fine-tuned to the structure of the target- than 3 = O(1/d) obtained with the kernel of fully-connected network. Moreover, we find that hierarchical functions generated by the output of deep CNNs are too rich to be efficiently learnable in high dimensions [Lemma 5.1) We confirm these results through extensive numerical studies and find them to hold even if the nonoverlapping patches assumption relaxed (Subsec. G.4).
1.2 RELATED WORK
The benefits of shallow CNNs in the kernel regime have been investigated by Bietti (002)); Favero
al. (202)) Misiakiewicz Mei (202I); Xiao Pennington (2022): Xiao (002); Geifman et al.
(2022) Favero et al. (2021), and later (Misiakiewicz & Mci 2021: Xiao & Pennington] 2022).
studied generalisation properties of shallow CNNs, finding that they are able to beat the curse of di-
mensionality on local target functions. However, these architectures can only approximate functions of single input patches or linear combinations thereof. Bietti (0022). in addition, includes generic pooling layers and begins considering the role of depth by studying the approximation properties of kernels which are integer powers of other kernels. We generalise this line work by studying CNNs of any depth with nonanalytic (ReLU) activations: we find that the depth and nonanalyticity of the sulting kernel are crucial for understanding the inductive bias of deep CNNs. This result should also be contrasted with the spectrum of the kernels of deep fully-connected networks, whose asymptotics
2

---

Under review as a conference paper at ICLR 2023
delf =12
(13)
n -((/aaa)
dest =6
(2)
0(1/4aa)
doft =3
log 5
f(1)
00/4,a)
311
32
37
210
log
01
12
3P21
JP22
222
Figure I: Left: Computational skeleton convolutional neural network of depth L+1=4 =L hidden layers). The leaves of the graph (squares) correspond to input coordinates, and the root (empty circle) to the output. All other nodes represent (infinitely wide layers of) hidden neurons. We define 'meta-pater ineta-patches' (i.e. patches of patches) the sets of input variables that share common ancestor node along the tree (such as the squares within each coloured rectangle). Each meta- patch coincides with the receptive field of the neuron represented by this common ancestor node, as indicated below the input coordinates. For each hidden layer 1 7= 1, 1,..... I,, there family of meta-patches having dimensionality der((). Right: Sketches of learning curves <(n) obtained by learning target functions of varying spatial scale with the network on the left. More specifically, the target function of 3-dimensional patch for the blue curve, 6-dimensional patch for the orange curve, and the full input for the green curve. We predict (and confirm empirically) that both the decay of e with n (full lines) and the rigorous upper bound (dashed lines) are controlled by the effective dimensionality of the target.
do not depend on depth (Bietti & Bach 202T). Furthermore, we extend the analysis of generalisation to target functions that have a hicrarchical structure similar to that the networks themselves.
Geifman et al. (2022) derive bounds on the spectrum of the kernels of deep CNNs. However, they consider only filters size one
first layer and do not include a theoretical analysis of gener- alisation. Instead, allow filters of general dimension and give tight estimates of the asymptotic behaviour of eigenvalues, which allow us to predict generalisation properties. Xiao (202)) is the closest
work, it also investigates the spectral bias of deep CNNs in the kernel regime. However, it considers a different limit where both the input dimension and the number of train- ing points diverge and does not characterise the asymptotic decay of generalisation error with the number of training samples.
Paccolat al. (202]); ); Malach Shalev-Shwartz 2021 Abbe et (0222) use sparse target func- tions which depend only on a few of the input varialees to prove sample complexity separation re- sults between networks operating in the kernel regime and in the feature regime-where where the change in parameters during training can be arbitrarily large. In this respect, our work shows that when the few relevant input variables are adjacent, i.e. the target function is spatially localised, deep CNNs achieve near-optimal performances even in the kernel regime.
2 NOTATION AND SETUP
Our work considers CNNs with nonoverlapping patches and no pooling layers. These networks are fully characterised by the depth I. + 1 (or number of hidden layers L) and a set of filters sizes (si) (one per hidden layer). We call such networks hierarchical CNNs.
Definition 2.1 (I-hidden-layers hierarchical CNN) Denote by the normalised ReLU function, (xx) /2 max(0, æ). For each input x E IRd (
[andd divisor of d, denote by æ; the i-th Notice that all our results can be readily extended to image-like input signals {ots his tensorial objects with arbitrary number of indices.

---

Under review as a conference paper at ICLR 2023
s-dimensional patch of x. 2, (X Tixe) for all i..,.., d/s. The output of L- hidden-layers hierarchical neural network can be defined recursively as follows.
Fn (ax) =
(w/ Di
vh E [1. H1], VA E [1..... pıl:
(1)
(SW-2)
1
w hihh'
(1)(())
44 w HJ), i E [1. pil, le [2.. D};
(HH-1
V
H1 PL (L+1)
Jha (L)((x))
f(x) = f((+1)(x) VHI. h=1i=1
Wha
(1)
VPL
H1 denotes the width of the 1-th layer, 81 the filter size (81= =), Pt the number of patches (pi pp=ppd//s wh E 12 Wh, R", whi R.
Hicrarchical CNNs are best visualised by considering their computational skeleton, i.c. the directed acyclic graph obtained by setting Hi --=1 A (example in Fig. 1 left, with ==3 hidden layers and filter sizes ($1, $2, 83) (3, 2)). Having nonoverlapping patches, the computational skeleton is an ordered tree, whose root is the output (empty circle at the top of the figure) and the leaves are the input coordinates (squares the bottom). All the other nodes represent neurons and all the neurons belonging to the same hidden layer have the same distance from the input nodes. The tree structure highlights that the post-activations ft of the I-th layer depend only on subset of the input variables, also known as the receptive field.
Since the first layer of a hierarchical CNN acts on $i siddienniional patches of the input, it is conve- nient to consider each d-dimensional input signal as the concatenation of s-dimensional patches, with s = $1 and p x = d. We assume that each patch normalised 1 so that the input space is product of s-dimensional unit spheres (called multisphere in Geifman et al. (2022)):
MPS = II ga C c
(2)
1=1
Notice that the s-dimensional patches are also the receptive fields of the first-hidden-layer neurons
(as in the blue rectangle in Fig. for s == 3). general, the receptive field of neuron in the 1-th hidden layer with /> is group of 2 adjacent patches (as in the orange rectangle of Fig. I for 1 2, $2 2 the green rectangle for 1= $3 82 2), which we refer meta-patch. Due to the correspondence with the receptive fields, each meta-patch is identified with one path the computational skeleton: the path which connects the output node to the hidden neuron whose receptive field coincides with the meta-patch. If such hidden neuron belongs to the 1-th hidden layer, the path is specified by a tuple of L /+ indices, i+11-++1 := i ... ut+1, where each index indicates which branch to select when descending from the root to the neuron node. With this notation, Fic+1-i14 denotes one of the pt meta- meta-patches of size II Sv. Because of the normalisation of the 8i siddimnnsional patches, each meta-patch has an effective dimensionality which is lower than its size:
(em(()) == dim (Zi, (2i = (81 -1),
Big-st11 E 8
(3)
dla(l) dim dim(: (1 (81 1)[T W (2.. L).
HIERARCHICAL KERNELS AND THEIR SPECTRA
We turn now to the wndthite-width limit H; - oo: because of the aforementioned equivalence with kernel methods, this limit allows us to deduce the generalisation properties of the network from the spectrum of a kernel. In this section, present the kernels corresponding to the hicrarchical models Def. 2. and characterise the spectra of the associated integral operators.
We consider specifically two kernels: the Neural Tangent Kernel (NTK), corresponding to training all the network parameters (Jacot et al.) 2018); and the Random Feature Kernel (RFK), correspond- ing to training only the weights of the linear output layer (Rahimi & Recht 2007 Daniely et al.
We show in Subsec. G.4 that our predictions remain true if the inputs are sampled uniformly in the d- dimensional hypercube [0, 1] from Gaussian distribution Rd
4

---

Under review as a conference paper at ICLR 2023
2016 In both cases, the kernel reads:
K(x1, y)
Dof 0ef(z)0of(3))
trained params
The NTK and RFK of deep CNNs have been derived previously by Arora et al. (2019). In App. B we report the functional forms these kernels in the case of hierarchical CNNs. These kernels inherit the hierarchical structure of the original architecture and their operations can be visualised again via the tree graph of Fig. I In this case, the leaves represent products between the corresponding elements of two inputs and y-, i.e. Z1y1 Falld, and the root the kernel output K( y)- The output can be built layer by layer by following the same recipe for each node: first sum the outputs of the previous layer which are connected to the present node, then apply some nonlinear function which depends on the activation function of the network. In particular, for each couple of inputs æ and y on the multisphere M hierarchical kemels depend on æ and y via the p dot products between corresponding s- s-dimensional patches of x and As comparison, Bietti & Bach (202T) showed that the NTK and RFK of a fully-connen mully-connected network of any depth depend on the full dot product ay whereas those of shallow CNN can be written as the sum of p kernels, each depending on only one of the patch dot products (Favero et al.) 202T).
Given the kernel, the associated integral operator reads
| -g--
(Tx (xx) (x)
((zz))f()ddpl
(5)
with dp(xr) denoting the uniform distribution of input points on the multisphere. The spectrum of this operator provides, via Mercer's theorem (Mereer 1909), an alternative representation of the kernel K( y) and a basis for the space of functions that the kernel can approximate. The asymptotic decay of the eigenvalues, in particular, is crucial for the generalisation properties of the kernel, as it will be clarified at in [Sec. 4 Since the input space is a product of s-dimensional unit spheres and the kernel depends on the p scalar products between corresponding s-dimensional patches of x and y. the eigenfunctions of Tx are products of spherical harmonics acting on the patches (see App. for definitions and the relevant background). For the sake of clarity, we limit the discussion in the main paper to the case s = 2. where, since each patch æ; is entirely determined by an angle 9,, the multisphere MPS reduces to the p-dimensional torus and the eigenfunctions to p-dimensional plane waves: e'k with 0 = (#1..... 8p) and label i: (ki,.... kpp. In this case the eigenvalues coincide with the p-dimensional Fourier transform of the kernel K. (cos 01. .1...................... cos 0p)
and the large-k asymptotics are controlled by the nonanalyticities of the kernel (Widom) 1963). The general case with patches of arbitrary dimension is presented in the appendix.
Theorem 3.1 (Spectrum of hierarchical kernels) Let Tr be the integral operator associated with a d-dimensional hierarchical kernel of depth L + 1, L>> 1 and filter sizes ($1...., .L) with $1 = 2. Eigenvalues and eigenfunctions of Tk: can be organised into L sectors associated with the hid- den layers of the kernel/network. For each 1 I T,, the 1-th sector consists of (IT sy) -local eigenfinctions: functions of a single meta patch- Pit-1-I-11 which cannot be written as linear com- binations of functions of smaller meta patta-patches The labels k of these eigenfunctions are such that there is a meta-patch kit1--141 of k with no vanishing sub-meta-patcher patches and all the ky 's outside of ki. are O (because the eigenfunction is constant outside of I2 The correspond- ing eigenvalue is degenerate with respect to the location of the mela-patch: we call it A
When | oc, with ls = |1
A (
1111 = =C2, 2--22-dat da + o (K- (k-2v-)a(())
with WNTK = 1/2, DRFK = 3/2 and dea the effective dimensionality of the veta-patches defined in Eq. 3 C2 is strictly positive constant for 1' 2 whereas for l 1= it can take two distinct strictly positive values depending on the parity of kig-
The proof in App. C. together with the extension to the 2 3 case Thm. C.T) It is useful to compare the spectrum in the theorem with the limiting cases of a deep fully-connected network and a shallow CNN. In the former case, the spectrum consists only of the L-th sector with pr, = 1-the global sector. The eigenvalues decay as ||||| -2-pp with // depending ultimately on the nonana- lyticity of the network activation function (see Bietti & Bach (2021) or App. C) and p den T.)
5

---

Under review as a conference paper at ICLR 2023
the effective dimensionality of the input. As result, all eigenfunctions with the same ||k]] have the same eigenvalue, even those depending on a subset of the imput coordinates. For example, as- sume that all the components of l are zero but k1, i.c. the eigenfunction depends only on the first 2- 2-dimensional patch: the eigenvalue is O(} 2v P) By contrast, for hierarchical kernel, the eigen- value is D(K-2v-)) much larger than the former as p 1.
In the case of a shallow CNN the spectrum consists only of the first sector, so that each eigenfunction depends only one of the input patches. In this case only and the eigenvalue is O(k; 2 2v-1). However, from (Favero et al. 2021). a kernel of this kind is only able to approximate functions which depend on one of the input patches or linear combinations of such functions. Instead, for hierarchical kernel with pt = 1, the eigenfunctions of the L-th sector are supported on the full input space. Then, if A& > for all k, hierarchical kernels are able to approximate any function on the multisphere, dispensing with the need for fine-tuning the kernel to the structure of the target function.
of the k can be non-zero, say k1,
Overall, given an eigenfunction of a hierarchical kernel, the asymptotic scaling of the correspond- ing eigenvalue depends on the spatial structure of the eigenfunction support. More specifically, the effective dimensionality of the smallest meta-patch which contains all the variables that the eigen- function depends on. In simple terms, the decay of an eigenvalue with is slower if the associated eigenfunction depends a few adjacent patches-but not if the patches are far apart! This is property of hierarchical architectures which use nonlinear activation functions at all layers. Such a feature disappears if all hidden layers apart from the first have polynomial (Bietti, (2022) or infinitely
smooth (Azevedo & Menegatto] 2015; Scetbon & Harchaoui 2021) activation functions or the kernels assumed factorise over patches in Geifman al. (2022)
4 GENERALISATION PROPERTIES AND ADAPTIVITY TO SPATIAL STRUCTURE
In this section, we study the implications of the peculiar spectra of hierarchical NTKs and RFKs on the generalisation properties of and prove a form of adaptivity to the spatial structure of the target function. We follow the classical analysis of Caponnetto & De Vito (2077) for kernel ridge regression (see Bach | Bietti (2022) for a modern treatment) and employ a spectral bias ansatz for the ridgeless limit (Bordelon et al. 2020 Spigler et al., 2020).
Theory of kernel ridge regression and source-capacity conditions. Given a set of n training points {( Mn)) ) ~ p(æ, u) for some probability density function (x, y) and regularisation parameter À >>>00 0, the kernel ridge regression estimate of the functional relation between x's and y's, or predictor,
(x) = argmin FEH
!
Σ (J(ae)) nn)² 111 1A=
where H. is the Reproducing Kernel Hilbert Space (RKHS) of (hierarchical) kernel K. If f(x) denotes the model from which the kernel was obtained via Eq. 4 the space H is contained in the span of the network features fxx)), } in the infinite-width limit. Alternatively, H can be defined via the kernel's s eigenvalues A& and eigenfunctions Yy: denoting with f& the projections of function f onto the kernel eigenfunctions, then belongs to H. it belongs to the span of the eigenfunctions and
If = Σ (AA))= 'fal +00. 220
The performance of the kernel is measured by the generalisation error and its expectation over training sets of fixed size n (denoted with E,,)
<(fT) = ddddy p(zz, v) (f(()) - y)². z(A.)) = E, [e(fR)..
(9)
or the excess generalisation error, obtained by subtracting from ε(A, n) the error of the optimal
predictor f (x) = f dy p(x, y)y. The decay of the error with n can be controlled via two exponents, depending on the details of the kernel and the target function. Specifically, if a 2 and r 2 1/a

---

Under review as a conference paper at ICLR 2023
satisfy the following conditions,
capacity: Tr
(Tk
[(Ax) < t00,
k20
source:
|Tk 1-r l*
= Σ
(An) < +00,
(10)
H
k20
then, by choosing a n-dependent regularisation parameter An ~ 12 a/ar 1) one gets the following
bound on generalisation (Caponnetto & De Vito 2007):
E(An, n) - e(f²)
artt
(11)
Spectral bias ansatz for ridgeless regression. The bound above is actually tight in the noisy setting, for instance when having labels Uı = (xx,) with εμ Gaussian. In a noiseless problem where y/ - (xx one expects to find the best performances in the ridgeless limit X - 0, so that the rate of Eq. IT is only an upper bound. the ridgeless case-where the correspondence between kernel methods and infinitely-wide neural networks actually wolds-there unfortunately no rigorous results for the decay of the generalisation error. Therefore, we provide a heuristic derivation of the error decay based on spectral bias ansatz. Consider the projections of the target function I on the eigenfunctions of the student kernel Yn ( and assume that kernel methods learn only the n projections corresponding to the highest eigenvalues. Then, if the decay of fiz with k is sufficiently slow, one has (recall that both À and e(f*) vanish in this setting)
{(n)
Σ 1521,
(12)
S.t. AAKA())
with A(n) the value of the n-th largest eigenvalue of the kernel. This result can be derived using the replica method of statistical physics (see Canatar et al. (2021); Loureiro et al. (202T); Tomasini al. (2022) and App. E] or by assuming that input points lie on a lattice (Spigler et al. 2020).
These two approaches rely on the very same features of the problem, namely the asymptotic decay of Ag and Ifāl also Cui et al. (002)). For instance, the capacity condition depends only on 2 since Tr (7x) is finite (Schölkopf et al. 2002); the specific value is determined by the decay of the ordered eigenvalues with their rank, which in turn depends on the scaling of Ag with k. Similarly, the power-law decay of the ordered eigenvalues with the rank deter- mines the scaling of the n-th largest eigenvalue, A(n) ~ n The source condition characterises the regularity of the target function relative to the kernel and depends explicitly of the decay of [ 1 with k, as does the right-hand side of Eq. 12 This condition was used by |Bach (202T) to prove that kernel methods are adaptive the smoothness of the target function: the projections of smoother targets on the eigenfunctions display a faster decay with k. thus allowing to choose a larger r and leading to better generalisation performances. The following corollary of Th.. 3.1] (proof and ex- tension to 2 3 presented in App. Cor. D.I] shows that, since the spectrum can be partitioned as in Thmm. 3.1 hierarchical kernels display adaptivity to targets which depend only on a subset of the input variables. Specific examples of bounds are considered explicitly in [Sec. 5)
the kernel spectrum:
Corollary 4.1 (Adaptivity spatial structure) Let Tk be the integral operator of the kernel of hierarchical deep CNN as in Thm. 3.7 with s =2 2. Then: i) the capacity exponent is controlled by the largest sector of the spectrum, i.e.
< < <
Tr 1/a
(13)
il) the source exponent r is controlled by the structure of the target function f i.e., if there is I L such that f depends only on some meta-patch Ti141-1441 then only the first sectors of the spectrum contribute to the source condition,
| 5 - E
Σ
(A T
(14)
The same holds if 8 is linear combination of such functions. As result, when dutt des((T) (L) is large and a + 1, the decay of the error is controlled by the effective dimensionality of the target den (l).
We are again limiting the presentation the case s =2 hut the extension the general is immediate.
7

---

Under review as a conference paper at ICLR 2023
5 EXAMPLES AND EXPERIMENTS
Source-capacity bound for functions of controlled smoothness and deff.
Consider a target func-
tion f which only depends the meta-patch F44111441 in Cor. 4.1
Combining the source
condition (Eq. 14) with the asymptotic scaling of eigenvalues (Eg. 6). we get
The
< +00 + Σ [1 A
|/211 < +00,
(15)
where V = 1/2 (3/2) for the NTK (RFK) and & denotes the meta-patch ki 1.+1 without the subscript to ease notation. Since the eigenvalues depend the norm of k. EEq 13 equivalent to finite-norm condition for all the derivatives of f up to order m < (2v- + dett (4)) 2, |2 < + oc with A denoting the Laplace operator. As a result, if f has derivatives of finite norm up to the m-th, then the source exponent can be tuned to 2m/ (2v + den(!), inversely proportional to the effective dimensionality of f" Since the exponent on the right-hand side of Fq. 11is is increasing function of r. the smaller the effective dimensionality of f the faster the decay of the error-hence hierarchical kernels are adaptive to the spatial structure of f In particular, from Eq. 11 with a + 2v/ (L),
En || f
2m (2v + (L))
{(n) C'n 8 with 3 2m (2u + deft (T.) + (2v + dett (1)) dest des
(16)
For instance, if pr. 1 then (Ltr(L) = p= d/2 (the number of 2-dim. patches). Even when p p>> 1, if fr depends only on imite-dimensional meta- peta-pptch (or is a sum of such functions) the exponent converges to the finite value 2m/(2 + v) + dett (4)). ). In stark contrast, using a fully-connected kernel to learn the same target results in r = 2m/ (2v + p), thus 3 = 2m/(2m - p) -aniiiiin as 1/p when p > 1, thus cursed by dimensionality.
Rates from spectral bias ansatz. The same picture emerges when estimating the actual de- cay of the error from Eq. 12, A(n) ~ n n= ", whereas Σn ff < + oo implies l < 2mm-dar(1) for a target supported on dett didmennsin meta-patch. Plugging such decays
|k]
Eq. 12 we obtain (details in Subsec. F.I)
2m
2v + detr(L)
{(n) ~ n with 8 = 2y + den(()
(17)
deH (L)
Again, with py, = and d (L)=p = p. the exponent remains finite for p>> 1. Notice that we recover the results of FFavero et al. (202T) by using a shallow local kernel if the target supported on 8- dimensional patches. These results show that hierarchical kernels play significantly better with the approximaiion-esimaateo trade-off than shallow local kernels, as they are able to approximate global functions of the input while not being cursed when the target function has a local structure.
Numerical experiments. We test our predictions by training a hierarchical kernel (student) on random Gaussian function with zero mean and covariance given by another hierarchical kernel (teacher). A learning problem is fully specified by the depths, sets of filter sizes, and smoothness exponents of teacher and student kernels. In particular, the depth and the set of filter sizes of the teacher kernel control the effective dimension of the target function. |Fig. shows the learning curves (solid lines) together with the predictions from Eq. (dashed lines), confirming the picture emerging from our calculations. Panel (a) of Fig. 2 shows a depth-four student learning depth- two, depth-three, and depth-four teachers. This student not cursed in the first two cases and is cursed in the third one, which corresponds to a global target function. Panel (b) illustrates the curse of dimensionality with the effective input dimension dea (L) by comparing the learning curves of depth-three students learning global target functions with increasing number of variables. All our simulations are in excellent agreement with the predictions of [Fq. 17, The bounds coming from Eq. 16 would display slightly slower decay, as sketched in Fig. right panel. All the details of numerical experiments are reported App. GJ together with a comparison between the ridgeless and petimally-regularinn
cases (Fig. S3) and additional results for: > 3 (Fig. S2): : kernels with overlapping patches (Fig. S5); different input spaces (Fig. S4 and the CIFAR- dataset (Fig. S6).
Notice that when the teacher kernel is hierarchical RFK, the target is equivalent to the output of a randomly-initee initialssdd,,,,, infinitely-wide CNN Novak et al. (2019). Although this target is highly structured, it leads to the same rate that we would have obtained for global non-hierarchical target:
8

---

Under review as a conference paper at ICLR 2023
b
10
T: (2). (2, 2)
10
10-1
5:
T: (2, 2), S: (2,
T, 12
T, S. (2.
T: (2, 2, 2)
T, (2, 5)
10
B- 1/duir
1/da7
10a
10
10a
10*
Figure 2: Learning curves for deep convolutional NTKs in teacher-student setting. Depth-four student learning depth-two, depth-three, and depth-four teachers. b. Depth-three models cursed by the effective input dimensionality dett (L) The numbers inside brackets are the sequence of filter sizes of the kernels. Solid lines are the results of experiments averaged over 16 realisations with the shaded areas representing the empirical standard deviations. The predicted asymptotic scaling e ~ n are reported as dashed lines. Details on the numerical experiments are reported in App. G
Lemma 5.1 (Curse of dimensionality for hierarchical targets) The problem of regression of the
output of a randomly- inittilliie and infinitely-wide hierarchical network suffers from the curse of dimensionality, in the sense that no methods using n examples can achieve a generalisation error decaying faster than n-B with 333/d.tt (T.).
This lemma simple consequence of the equivalence of the predictors of kernel ridgeless regres- sion and Bayesian inference, which implies that the rate achieved when learning Gaussian random function with kernel matching the covariance kernel the function is Bayes-optimal (Kanagawal al. 2018). The optimal rate -33/da((L) comes from Eq. 17 with I = L and m V 3/2. We conclude that, despite their intrinsically hierarchical structure, these targets cannot be good models of learnable tasks.
CONCLUSIONS AND OUTLOOK
We have proved that deep CNNs can adapt to the spatial scale of the target function, thus beating the curse of dimensionality the target depends only on local groups of variables. Yet, if considered as 'teachers', they generate functions that cannot be learnt efficiently in high dimensions, even in the Bayes-optimal setting where the student matched to the teacher. Thus, the architectures we con- sidered not good models of the hierarchical structure of real data which are efficiently learnable.
Enforcing a stronger notion of compositionality is an interesting endeavour for the future. Follow- ing Poggio al. (2017), one may consider a much smaller family of functions of the form
fu41-141 (411)41) fiur-zz (fim (Zi
fi ( (Zit)) )). (18)
From an information theory viewpoint, Senypoit,,Schmidii (Scmidt- (2020): Finocchio & Schmidt-Hieber (2021)
showed that possible to learn such functions efficiently. However, these arguments do not pro- vide guarantees for any practical algorithm such as stochastic gradient descent. Moreover, prelimi- nary results (not shown) assuming that the functions f's are random Gaussian functions suggest that these tasks are not learnable efficiently by a hierarchical CNN in the kernel regime- see also Gior- dano et al.) (022). It is unclear whether this remains true when the networks closely resemble the structure of Eq.. 18 as in Poggio et al.] (017)), or when the networks are trained in a regime where features can be learnt from data. Recently, for instance, [Ingrosso & Goldi (2022) have observed that under certain conditions locality can be learnt from scratch. It is not clear whether compositionality can also be learnt, beyond some very stylised settings (Abbe et al. 2022).
Finally, another direction to explore is the stability of the task toward smooth transformations or diffeomorphisms. This form of stability has been proposed as a key element to understanding how the curse of dimensionality is beaten for image datasets (Bruna & Mallat 2013 Petrini al.
2021
Such a property can be enforced with pooling operations (Bietti & Mairal 2019 Bietti et al. 202 therefore diagonalising the NTK in this case well would be of high interest.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neu- ral networks. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 4782 4782-4887. PMLR, 02 02-05 Jul 2022.
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 in Neural Information Processing Systems, 32, 2019.
Kendall Atkinson and Weimin Han. Spherical harmonics and approximations on the unit sphere: an introduction, volume 2044. Springer Science & Business Media, 2012.
Douglas Azevedo and Valdir Menegatto. Figenvalues of dot-product kernels on the sphere. Pro- ceeding Series of the Brazilian Society of Computational and Applied Mathematics, 3(1), 2015.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629 -812 2017.
Francis Bach. Learning theory from first principles. 2021.
Irving Biederman. wwwp:nitiion-yyooooeeeeee a theory of human image understanding. Psycho- logical review, 94(2):115, 1987.
Alberto Bietti. Approximation and learning with deep convolutional models: kernel perspective. In International Conference on Learning Representations, 2022.
Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. In ICLR Inttermaiio Conference on Learning Representations, pp. 1-22, 2021.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. Advances in Neural Information Processing Systems, 32, 2019.
Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity learning under geometric stability. Advances in Neural Information Processing Systems, 34:1 1.l11867-18688 2021.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1024-1034. PMLR, 2020.
Joan Bruna and Stéphane Mallat, Invariant scattering convolution networks. IEEE transactions on paltern analysis and machine intelligence, 35(8):1872-18888 2013.
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communi- cations, 12(1):1-12, 2021.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):311-368, 2007.
Youngmin Cho and Lawrence K. Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems 22, pp. 342-350, Curran Associates, Inc., 2009.
Hugo Cui. Bruno Loureiro, Florent Krzakala, and Lenka Zdeborova. Generalization enror rates in kernel regression: The crossover from the noiseless to noisy regime. In Advances in Neural Information Processing Systems, 2021.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. Advances In Neural Information Processing Systems, 29, 2016.
Arturo Deza, Qianli Liao, Andrzej Banburski, and Tomaso Poggio. Hierarchically compositional tasks and deep convolutional networks. arXiv preprint arXiv:2006. 139/5, 2020.
10

---

Under review as a conference paper at ICLR 2023
Costas Efthimiou and Christopher Frye. Spherical harmonics in p dimensions. World Scientific, 2014.
Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse of dimen- sionality in convolutional teacher-student scenarios. Advances in Neural Information Prucessing Systems, 34, 2021.
Gianluca Finocchio and Johannes Schmidt-Hieber. Posterior contraction for deep gaussian process priors. arXiv preprint WYX::2205.074100 2021.
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.
Matteo Giordano, Kolyan Ray, and Johannes Schmidt-Hieber. On the inability of gaussian process regression to optimally learn compositional functions. arXiv preprint arXiv:2205.07764, 2022.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv:1712.004008 2017.
Alessandro Ingrosso and Sebastian Goldt. Data-driven emergence of convolutional structure in neural networks. arXiv preprint arXiv:2202.00565. 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. Advances in neural information processing systems, 31, 2018.
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regularization of random feature models. In International Conference on Machine Learning, pp- 4631-4640. PMLR, 2020a.
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Kernll alignment risk estimator: Risk prediction from training data. Advances in Neural Information Processing Systems, 33, 2020b.
Motonobu Kanagawa, Philipp Hennig, Dino Sejdinovic, and Bharath Sriperumbudur. Gaus- sian processes and kernel methods: A review on connections and equivalences. arXiv preprint arxiv: 2018.
Michael Kohler, A Krzyzak, and Benjamin Walter. On the rate of convergence of image classifiers based on convolutional neural networks. arXiv preprint arXiv:2003.01522 2020.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups. In International Conference on Machine Learning. PMLR, 2018.
Jachoon 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.
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher- student model. Advances in Neural Information Processing Systems, 34:
2021.
Eran Malach and Shai Shalev-Shwartz. Computational separation between convolutional and fully- connected networks. In International Conference on Learning Representations, 2021.
James Mercer. Xvi. functions of positive and negative type, and their connection the theory of integral equations. Philosophical transactions of the royal society of London. Series A, containing papers of mathematical or physical character, 209(441-458::415 446, 1909.

---

Under review as a conference paper at ICLR 2023
Mare Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin glass theory and beyond: An In- troduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company, 1987.
Theodor Misiakiewicz and Song Mei. Learning with convolution and pooling operations in kernel methods. arXiv preprint arXiv:2111.0830 2021.
Roman Novak, Lechao Xiao, Yasaman Bahri. Jachoon Lcc, Greg Yang, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many chan- nels are gaussian processes. In International Conference on Learning Representations, 2019.
Jonas Paccolat, Stefano Spigler, and Matthicu Wyart. How isotropic kernels perform on simple invariants. Machine Learning: Science and Technology, 2(2):025020, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Leonardo Petrini, Alessandro Favero, Mario Geiger, and Matthieu Wyart. Relative stability toward diffeomorphisms indicates performance in deep nets. Advances in Neural Information Processing Systems, 34, 2021.
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: a review. Inter- national Journal of Automation and Computing, 14(5)5503-519 2017.
Tomaso Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks. Proceed- ings of the National Academy of Sciences, 11 117(45):3003933045 2020.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Meyer Scetbon and Zaid Harchaoui. A spectral analysis of dot-product kernels. In International Conference on Artificial Intelligence and Statistics, pp. 3394-3402 PMLR, 2021.
Johannes Schmidt-Hicbel Nouparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 48(4)) 2020.
Bernhard Schölkopf, Alexander J Smola, Francis Bach, al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Alex Smola, Zoltán Ovári, and Robert Williamson. Regularization with dot-product kernels. Advances in neural information processing systems, 13, 2000.
Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus seacher-student paradigm. Journal of Statistical Mechanics: Theory and Experiment, 2020(12): 2020.
Umberto M. Tomasini, Antonio Sclocchi, and Matthieu Wyart. Failure and success of the spectral bias prediction for laplace kernel ridge regression: the case low-dimensional data. In Proceed- ings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 21548-21583 PMLR, Jul 2022.
Martin Wainwright. High--dimensionl statistics: A non-asymptotic viewpoint, volume 48. Cam bridge University Press, 2019.
Harold Widom. Asymptotic behavior of the eigenvalues of certain integral equations. Transactions of the American Mathematical Sociery, 109(2):278-25) 295,, 1963.
Lechao Xiao. Eigenspace restructuring: a principle of space and frequency in neural networks. In Conference on Learning Theory, pp. 4888 4944. PMLR, 2022.
Lechao Xiao and Jeffrey Pennington. Synergy and symmetry in deep learning: Interactions between the data, model, and inference algorithm. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 24347-24369. PMLR, 17-23 Jul 2022.
12

---

Under review as a conference paper at ICLR 2023
Hao Henry Zhou, Yunyang Xiong, and Vikas Singh. Building bayesian neural networks with blocks: On structure, interpretability and uncertainty. arXiv preprint arXiv::806.035566 2018
13

---

Under review as a conference paper at ICLR 2023
SUPPLEMENTARY MATERIAL
Harmonic analysis on the sphere
14
A.1 Dot-product kernels on the sphere
15
A.2 Multi-dot-prouuc kernels on the multi-sphere
16
RFK and NTK of deep convolutional networks
17
Spectra of deep convolutional kernels
18
C.1 Singular expansion of hicrarchical kernels
18
Patches the ring
................................
Patches on the s-dimensional hypersphere
22
C.4 General depth
25
D Generalisation bounds for kernel regression and spatial adaptivity
25
Classical generalisation bounds
25
D.2 Extension of Cor. 4.1 to patches on the hypersphere
26
D.3 Decay of eigenvalues with the rank
27
Statistical mechanics of generalisation in kernel regression
28
Examples
29
Rates from spectral bias ansatz)
29
Numerical experiments
29
G.I
Experimental setup
29
G.2
Teacher-student learning curves
29
G.3
Illustration of different teacher-student scenarios
30
G.4
Extensions to different normalisations and overlapping patches
33
G.5
CIFAR-2 learning curves
34
A
HARMONIC ANALYSIS ON THE SPHERE
This appendix collects some introductory background spherical harmonics and dot-product ker- nels on the sphere Smola et 2000). See Efthimiou & Frye 20144; Attinson Han 2012); Bach 2 for complete description. Spherical harmonics are homogeneous polynomials on the sphere {a R- ||>|| = 1}. with ||-I| denoting the L2 norm. Given the polynomial degree k E N, there are Nr. linearly independent spherical harmonics of degree k on s=-1 with
2k + - 2 2 1 &
k (s+==3),
[No.d = Ad,
Nk.
(S1)
(Wad ~ kd-2 kd=2 for k: > 1.
Thus, we can introduce of Ni,. spherical harmonics YE.8 for each k, with ranging in 1,...,Ne No.. which are orthonormal with respect to the uniform measure on the sphere dr(x),
(YK,e, (a.e,Yee) Ne.e)g- == f dr(xx) Ve.e(x)) = -62
(S2)
14

---

Under review as a conference paper at ICLR 2023
Because of the orthogonality of homogeneous polynomials with different degree, the set {Ya,e T complete orthonormal basis for the space of qquare-integrabl functions the s-dimensional unit sphere. Furthermore, spherical harmonics are eigenfunctions of the haplce--Beltann operator A, which is nothing but the restriction of the standard Laplace operator to S*-1.
AYk,
k(k + -k(k
2)
(S3)
The Saplace-Beltrami operator A can also be used characterise the differentiability of functions I on the sphere via the L.2 norm of some power of A applied to ʃ.
By fixing direction y in gd-1 which is invariant for rotations that leave y unchanged. This particular spherical harmonic is, in fact, function y and called the Legendre polynomial of degree Px.a (x y) (also referred as Gegenbauer polynomial). Legendre polynomials can be written combination of the orthonormal spherical harmonics YE,E via the addition formula (Atkinson & Han 2012 Thm. 2.9),
select, for each k the only spherical harmonic of degree
NE. Σ
(m. . y) NE.
(x)
(S4)
Alternatively, Pa.a is given explicitly as a function of x E [-1,+]] via the Rodrigues for- mula (Atkinson Han 2012 Thm. 2.23),
(t) (-1)
r 2
3-a d dt (1 (1- (1-
(1 (1-1²²*
(S5)
T
P + 1
Legendre polynomials are orthogonal on 1-1,+1] with respect to the measure with density (1 ()-(2-3//2 which is the probability density function of the scalar product between two points on 8a-1.
[Tt dt (1-8) - (t.,())Pe,
(S6)
S N
with | denoting the surface area of the s-dimensional unit sphere.
To sum up. given æ, y Sa-1, functions of æ or y can be expressed as a sum of projections on the orthonormal spherical harmonics (Yr.)),,>> whereas functions of æ y can be expressed sum of projections on the Legendre polynomials (Pk. y)}.- The relationship between the two expansions is elucidated in the Funk-Hecke formula (Atkinson & Han 2012. Thm. 2.22).
(r_dr(w) dr(y) f(x y))),) Yu (x))( S
LT dt (1 12- (1))...
(S7)
If the function f has continuous derivatives up to the k-th order in [-1,+1], then one can plug Rodrigues' formula in the right-hand side of Funk-Hecke formula and get, after k integrations by parts,
Jomn dr(y) f(x (oee.))Yxx,)))) Yv, ex))
[" dt (1-)))1
S
2
9-1
(S8)
with f (t) denoting the k-th order derivative of ff in t. This trick also applies to functions which are not & times differentiable 11, provided the boundary terms due integration by parts vanish.
A.1 DOT-PRODUCT KERNELS ON THE SPHERE
Dot-product kernels kernels which depend the two inputs and y via their scalar product x y. When the inputs lie on the unit sphere S*-1, one can use the machinery introduced in the previous section arrive immediately at the Mercer's decomposition of the kemnel Smola et al.
15

---

Under review as a conference paper at ICLR 2023
2000
K(x y)
Σ
Na
S
di (1 ()) - x(())..0(() Phi Pa y)
(1)
S
120
No.
1
dt (1 (1-+) " ((t))s,.(t))
(S9)
Ni.
Σ Ak (=,
In the first line we have just decomposed into projections onto the Legendre polynomials, the second line follows immediately from the addition formula, and the third is just definition of the eigenvalues Åg. Notice that the eigenfunctions of the kernel are orthonormal spherical harmonics and the eigenvalues degenerate with respect to the index l. The Reproducing Kernel Hilbert Space (RKHS) of I can be characterised as follows.
No.
(f, Y(a))
H f: /::5-1 R.S.L. ||/
E
< +00 }
(S10)
120,A
A.2 MULTI-DOT- KERNELS THE MULTI-SPHERE
Mercer's 's decomposition of dot- not-product kernels extends naturally to the case considered in this paper, where the input space is the Cartesian product of p s-dimensional unit sphere,
M = {xx= = (x11 Fpp) at; E ES Sx-1 Vi
p)
X S
(S11)
which refer the multi-sphere following the notation of Geifman al. (202 After defining
a scalar product between functions on MPS*-1 by direct extension of lqq. S2 one can immediately
find of orthonormal polynomials by taking products of spherical harmonics. With the multi- index notation k (ki,... kp), l (li,.... lp), for all æ E MPS--1
Px.e(x) II (as), with K; 2 l, = I,...,,.. NK. 2k: + 2 ( k; 3) 3).
k - -
(S12)
These product spherical harmonics Va,e(x) span the space of square-integrable functions on MPS--1 Furthermore, as each spherical harmonic is an eigenfunction of the suplace-Beltramt operator, Yb.e is an eigenfunction of the sum of Laplace- Laplace-Beltrann Beltrami operators on the p unit spheres,
Σ A IIIT YK... = Σ
"
Ap.a e
+
Vn.e-
(S13)
We can thus characterise the differentiability of functions of the multi-sphere Xe., via finiteness in L2 norm of some power of Ap.s-
Similarly, we can consider products of Legendre polynomials obtain set orthogonal polynomi- als on 1-1, 11. (see Geifman et al. (2022), appendix A). Then, any function f on MPS*-1 x MPg which depends only on the scalar products between patches,
f(z, y) = g( V1...., F yp),
(S14)
can be written as a sum of projections on products of Legendre polynomials
(t) II Pr.. 1=1
(S15)
Following Geifman et al. 2022). we call such functions multi-doo--roodiee kernels. When fixing one of the two arguments of / (say x)), becomes function MP x MP5 and can be written
16

---

Under review as a conference paper at ICLR 2023
sum of projections on the Yk.e's. The two expansions are related by the following generalised Funk-Hecke formula,
p
[ [=1 83 dr(wn)) g( y1....,, up yp) Yo)
(S16)
Vk)e(1) ( |
II -1
dt, (1-1)) " Phin(tt)) s(tl.....,p))
Having introduced the product spherical harmonics Ye,e as basis of MPS and the product Leg- endre polynomials (t. as basis of [-1,+1j², the Mercer's decomposition of multi-dot-produet kernels follows immediately.
p
1
+1 dr, (1 -1)) 2 Pen.olta) K. (ftil)) Pk.s ((a; yi),)
X (fa; 9:le) = Σ
Ke.s
N
= Σ
AA
Yv,e())Yr,c1)))
420
8m1
(S17)
B RFK AND NTK OF DEEP CONVOLUTIONAL NETWORKS
This appendix gives the functional forms of the RFK and NTK of hierarchical CNNs. We refer the reader to Arora et al. (2019) for the derivation.
Definition B.1 (RFK and NTK of hierarchical CNNs) Let x, E = De-
note tuples of the kind i1 ... im with i1-m for m 2 l. For < it-mm denotes the empty tuple. For each tuple 12-1-11 denote with lig i2 the scalar product between the s-dimensional patches of x and y identified by the same tuple, i.e.
fig-141 Dig-- Vig-1-+1
(S18)
For 1SIS 1, denote with (teg-141 } is-: the sequence of t's obtained by letting the indices of the tuple i2-11 vary in their respective range. Consider hierarchical CNN with L hidden layers, filter sizes (s1,...,8L) PL 2 1 and all the weights wh, ( (I+1) random numbers with zero mean and unit variance.
h. W initialised as Gaussian
RFK. The corresponding RFK (or covariance kernel) function K of the P1 d/s1 scalar products tig... which can be obtained recursively as follows. With
B1 (t) = ((T - arccost) t) + v1- --) nx.
x (1i s41T) K5 11
xll (112)-2-))oo))
Σ
(1-1) RFK
(Htasentea..)) VlE if
Ki
81
P2
x(l) ((lonsetlia))))
(819)
Pt
1+tT=1
17

---

Under review as a conference paper at ICLR 2023
NTK. The NTK of the same hierarchical CNN is also function of the p1 =d/s1 scalar products be which can be obtained recursively as follows. With Ko(t) ( arccos t) n
KNTK (liz s211) Kil (lio s212) + (liz 12)1 No (ol 12125
xell) KRFK (1l2
Σ
KNTK
(( (l L] if
x Ko
RFK
x
1
KNTK
(fterettiionn)
(S20)
PL 1=+1=1
C SPECTRA OF DEEP CONVOLUTIONAL KERNELS
In this section we state and prove generalised version of Thm. 3.1 which includes non-binary patches. Our proof strategy is to relate the asymptotic decay of eigenvalues to the singular behaviour of the kernel, as it is customary in Fourier analysis and done in Biettt & Bach (2021) for standard dot-product kernel. In [Subsec. C.I we perform the singular expansion of hierarchical kernels, in Subseec. C.2 (patches on the ring), which we then generalise to general $1 in Subsec. C.3 and to general depth in Subsec. C.4
this expansion to prove Thm. 3.1 with L= (2 hidden layers) and = 2
Theorem C.1 (Spectrum of hierarchical kernels) Let Ty. be the integral operator associated with a d-dimensional hierarchical kernel of depth +++ 1, T.>> and filter sizes (81....,81.) Higenvalues and eigenfunctions of TTx can be organised into L sectors associated with the hidden layers of the kernel/network. For each 1 < L, the I-th sector consists of [II'= sy looca eigenfunctions: func- tions of single meta-patch 0441-444 which cannot be written as linear combinations of functions of smaller meta-patches. The labels k of these eigenfunctions are such that there is a meta-pate k of k with no vanishing sub-meta- -att--sttches and all the k2 ''s outside of kigh-141 are (be- cause the eigenfunction is constant outside of Dig sLI1 The corresponding eigenvalue is degener- ate with respect the location of the meta veta-patch: call it A
When [ +
-it-1
with ks = | 1-
if 81 = 2, then
A (
C2,1 22 der(()))) + 2--2-daae
-2-- 2w-der()).
(S21)
Buy 1112
with UNTK 1/2, VRFK 3/2 and dea the effective dimensionality of the meta-pan petah-s defined in Eq.. 3 C2. is strictly positive constant for 12 2 whereas for 1 = 1 it can take two distinct strictly positive values depending on the parity of king 1111
ii. if 2 3, then for fixed non-zero angles k//k
(1) M
Con.i (kiws 22w-deer()) + (K (K-2w-dar())
(S22)
k
where Coy is a positive function for 2 2, whereas b =1 it is strictly positive constant which depends the parity kiz 1111"
C.1 SINGULAR EXPANSION HIERARCHICAL KERNELS
Both the RFK and NTK of ReLU networks, whether deep shallow, are built by applying the two
functions Ki and Ks Cho Saul (009 (see also Def. B.
(t arccost)
(πr arccos t) + VI
K1 (t( =
(S23)
18

---

Under review as a conference paper at ICLR 2023
The functions Ky and Kj non-analytie in t = = 1, with the following singular expansion Bietti & Bach (2021). Near t= with u = 1-t
v2 --1_2 -_221//2 + (
Ko u)= =
(S24)
K1 u) = + 2/2 3/2 (n
3π
Near with a +
Kig - + u) = V2
122 + O(u212)
π
(S25)
2/2
Ki (1(-1+ + u)
23/2 3/2 0(1
3π
As result, hierarchical kernels have singular expansion when the t:2- are close to =1. In particular, the following expansions are relevant for computing the asymptotic scaling of eigenval- ues.
Proposition C.1 (RFK when = y) The RFK of hierarchical network of depth L + 1, filter sizes ($1...., and PL 2 has the following singular expansion when all tiz-141 - With U12-1.1111 = 1-21 c= 2/ (3T), and Ihe $t = 1 if I is the empry set,
x((At1) ((1 U / 11m1e
Σ
112-1+11
II
12-
Sy
PL
2
3/2
En Vig 1
Σ
+
PL
4111-1441
II 8p 251"E
8t"r
1'<1"LL
+ 0 5/2
(S26)
Proof. With L = 1 one has (recall that i2-11+1 i2-22 reduces to single index)
x(() (1 - "1iz) = 1 - Uig
3/2
5/2
+
cu
ig
RP
({1 wo2tte)) =1 1
Uia
Σ
di
3/2
+ O(1
(S27)
P1
P1 $2
With L=
KRFK ((1
Uin (in) 1il
Ui
Uizis
3/2
(1
3/2
82
82
3/2
1
Wig.ig
u
3/2
+
Σ
Uig
5/2
12.ts)
81
82
$2
f2
i2
(S28)
therefore
3/2
x(2+1) (f1-Wishh Wig.i l1g.t) =1
Σ
Wiziia +
C
3/2 Ezika
+
Σ
Uis
S2D2
P2
$2
P2
82
82.48
i2:29
5/2 ). O
(S29)
The proof of the general case follows by induction by applying the function Kj to the singular expansion of the kernel with I. hidden layers, then using lqq. S24
19

---

Under review as a conference paper at ICLR 2023
Proposition C.2 (RFK when = y) The RFK of hierarchical network of depth L + 1, filter sizes ($1...., 8L) and PL 2 1 has the following singular expansion when all 112-1 7 -1. With Miz-1141 =1 142- c= 2/2/ (3T) and Il 81 = 1 if is the empty set,
xH(tt) (1-1+ Viz-1441 (212211) by +
CL
Σ
3/2 u .11
5/2 ( 12
RPK
II
12-6-1
81
PL
(S30)
with by. = = (br-1)) b, =0; and ez. Cr.-IK( (br. C1 =c
Proof. This can be proved again by induction. For 1,=1,
x(1) RFFK (- Uzz) = cul
3/2
5/2
x(1+1) RFK
(1-1+ + uindiz)) Σ
U
3/2
+OU
5/2
(S31)
pl
Thus, for 2=
RFE
(1-1+ Winiiali)) 1i1
b2.55
3/2
+
0
(1
5/2
82 i2
= (0) + K² (0)
c
U
12
3/2
+ O1
5/2
(S32)
82
so that
K1 (0)c
(2+1) RFK
(1-1+ Wigida Uigdta) k0)
Σ
3/2 U12.3
+
5/2 (2.25))
(S33)
82P2
$2.ia
The proof is completed by applying the function to the singular expansion of the kernel with hidden layers.
Proposition C.3 (NTK when =y The NTK of hierarchical network of depth L. filter sizes ($1....,81) and PL 2 has the following singular expansion when all tiz-142 7 1. With
U12-1111 = 112-11117 c= 2Tx and Ihet 81 if I is the empty set.
(L++1 NTK
(11 112-211-11 122 L, +1
F
PL
8t"
PEM'L
1/2
Σ 1+
Σ 22ol
3/2 + Om .2 .)
X
Wig 11-1
Spr
(S34)
Proposition C.4 (NTK when x= == - y) The NTK of a hierarchical network of depth L + 1, filter sizes (81;...,81) and pt. 1 has the following singular expansion when all lig-stt1 -1. With Uig =1 1 lig s211 c= /2/m and lher 81 = 1 if is the empty set,
x(((+) (1-1 + Uia se12 )rame.)) = 0r. +
CL
3/2 2-14
5/2 + +0 )
II
ia 1013
Sy
Pr.
2
(S35)
20

---

Under review as a conference paper at ICLR 2023
with ao =by+ bu- bL-1ko(bb--)) by (bb--1)), b1 0: and ey = =CL-11((bb-1)) C1 Notice that
both Ki and Ky are positive and strictly increasing in [0, 1] and K1 (1)= Ko(1) = thus by E (0, and Cr. C1-11
The proofs of the two propositions above are omitted, they follow the exact same steps as the previous two proofs.
C.2 PATCHES ON THE RING
In this section, we prove a restricted version of 3.1 the case of 2-dimensional input patches, since the reduction of spherical harmonics to the Fourier basis simplifies the proof significantly. We also consider, for convenience, hierarchical kernels of depth with the filter size of the second hidden layer set to p= = d/2, the total number of 2-patches of the input. Once this case is understood, extension to arbitrary filter size and arbitrary depth is trivial.
Theorem C.2 (Spectrum of depth-3 kernels on 2-patches) Let Tr. be the integral operator as- sociated with d-dimensional hierarchical kernel of depth 3, (2 hidden layers). with filter sizes (81 2, 82) and P2 = 1, such that 282 = d and 82 = (the number of 2-patches). Eigenvalues and eigenfunctions of Tx. can be organised into 2 sectors associated with the hidden layers of the ker- nel/network.
The first sector consists of 81 -local eigenfunctions, which are functions of a single patch a; for i i= =,.,..... The labels k. l of local eigenfunctions are such that all the kj with j + are zero (because the eigenfunction is constant outside wi). The corresponding eigenvalue is degenerate with respect to the location of the patch: call it A When k; +
(1) CC2,1 k2 + o (k-2--)),
(S36)
with PNTK- 1/2, FRFK- 3/2. C2 can take two distinct strictly positive values depend- ing on the parity of kü;
ii The second sector consists of global eigenfunctions, which are functions of the whole imput æ. The labels k, l of global eigenfinctions are such that at least two of the k; are non- zero. We call the corresponding eigenvalue A22 When ||A + co, with k = ||]]]
= C2.2 k -2- + (k-
(S37)
Proof. we consider binary patches in the first layer, the input space becomes the Cartesian product of two-dimensional unit spheres, i.e. circles, X' = I[= S!. Then, each patch æ; corresponds to an angle 0; and the spherical harmonics equivalent Fourier atoms,
(0) 1, (0) cko (x) c ik0
Vk: 2 1.
(S38)
Therefore, solving the eigenvalue problem for dot-product kernel K(x y) = K. (cos(0z - 0y)) with x, y E S² reduces to computing its Fourier transform. With 1 and |S 2n,
2T [
[ d0 K. (cos tikd
d0 K. (cos((, By)) =ikl=
Agc
A
(S39)
2x
where we denoted with the difference between the two angles. Similarly, for a multi-dot totti-d kernel, the eigenvalues coincide with the p-dimensional Fourier transform of the kernel, where is the number of patches,
1
[[
P
dB, etiis (tehe K. (fcos
A
(2T)P
1
[" d'O Lik 0,)00
(S40)
(2T))
with & = (k.....,k,, kT) the vector the patch wavevectors and 0 = (0I...., the vector of the patch angle differences 0, Oz. 0y.
21

---

Under review as a conference paper at ICLR 2023
The nonanaliticity of the kernel t; =1 for all i moves 0₂ 0 for all whereas those in t, move to 82 = π and -n. The corresponding singular expansion is obtained from Eq. S26 after replacing t, with cos (0t) and expanding cos (0;) as 1 02/ /2, resulting in
3/2
P
2 3π
P
8
P
xCl2 ( = 2p 1m1
1
O (S41)
3xp
2
i=1
The first nonanalytic terms are Fourier transform of |10|2 with E I2 decays asymptotically as has (v ===33// 3/2)
Σ 10:13 and
2
6
3/2
After recalling that the
3mp
3x
1=
2
|k| 2 Widom (1963). one
2
d'O Like
10:18
óky,o,
for |||||| - x0
(S42)
(2
3rp
jzi
and
doa 0 110$s
||||||
-p-3
for |||||| oc.
(S43)
(2
All the other terms in the kernel expansion will result in subleading contributions in the Fourier transform. Therefore, the former of the two equations above yields the asymptotic scaling of eigen- values of the local sector, whereas the latter yields the asymptotic scaling of the global sector.
The proof for the NTK case is analogous to the RFK case, except that the singular expansion near 0: = 0 is given by
00
V2
1
P
00
1/2
x222 (fcos 0, (1)
Σ i=1
(S44)
2
π
P
i=1
C.3 PATCHES ON THE S-DIMENSIONAL HYPERSPHERE
In this section, we make an additional step towards Thm. 3.1 by extending Thm. C.2 to the case of s-dimensional input patches. We still consider hierarchical kernels of depth 3 with the filter size of the second hidden layer set to p d/s (the total number of s-patches of the input) so to ease the presentation. The extension to general depth and filter sizes is presented in (Sbseec C.4
Theorem C.3 (Spectrum of depth-3 kernels on s-patches) Let TK. be the integral operator as- sociated with a d-dimensional hierarchical kernel of depth 3, (2 hidden layers), with filter sizes (s) s, 82) and p2=11 such that 28 = d and 82 p (the number of s-patches). Eigenvalues and eigenfunctions of Tx: can be organised into 2 sectors associated with the hidden layers of the ker- nel/network.
The first sector consists of s -ocal eigenfinctions, which are functions of single patch æs for i= i.......p The labels k. l of local eigenfunctions are such that all the kj 's with j # i are zero (because the eigenfunction is constant outside of xz). The corresponding eigenvalue is degenerate with respect to the location of the patch: we call it Ao. When k; oc,
ki (1) = Ca,1 k: 2u 22 + (k- (k-20-(--1)
(S45)
with UNTK = 1/2, PRFK = 3/2. C.,1 can take two distinct strictly positive values depend- ing the parity of kei
ii The second sector consists of global eigenfunctions, which are functions of the whole imput x. The labels k. l of global eigenfunctions are such that at least two of the k; 's are non- zero. We call the corresponding eigenvalue 2)) When k = =|le|| - -0, for fixed non-zero
angles k/k,
A = C..2
bo 2v p( + 0 (6-20-p(o-1)).
(S46)
where C2 is positive function.
22

---

Under review as a conference paper at ICLR 2023
Proof. A hierarchical RFK/NTK is multi-dot- poooootttppoucttt kernel, therefore its cigenfunctions products of spherical harmonics Yι,e(x)) Ilp=1 ex,,e,6 (xx) and the eigenvalues of IC are given by Eq. S17
P. A8- II
S
di, (1 (.) (,)= Pk..o(h)) ((()))))
(S47)
The proof follows the following strategy: first, we show that the infinitely differentiable part of K. results in eigenvalues which decay faster than any polynomial of the degrees k; We then show that the decay is controlled by the most singular term of the singular expansion of the kernel and finally compute such decay by relating it to the number of derivatives of the kernel having finite 12 norm.
When IC is infinitely differentiable in [-1,+1] we can plug Rodrigues' formula Eq. S5 for each (t., and get
1- g+
1
(( r (k+ (k) S
) dt it (t)
P II
{?) h+ (1=+t)/ttg
A4 II
(1
(S48)
2
dt
with [_] dt denoting integration over the p-dimensional hypercube [-1, +1].. We can simplify the integral further via integration by parts, as obtain
P S
((
S dt ((k) (t)
P (1-))
II
A
2
[ + 1=1
(S49)
where (A)) denotes the partial derivative of order k with respect to 11, 12 with respect to tz and so on until Kp with respect to fp. Notice that the function (1 - = is proportional to the proba- bility measure of the scalar product between two points sampled uniformly at random on the unit sphere (Atkinson & Han 2012, Sec. 1.3),
/ de (1 (1- 4-3
Sd-1 Sd
[ dt (1 - 12) d-3 =1
S
d.d
(S50)
This probability measure converges weakly Dirac mass 8(L) when d + co. Recall, in addition, that [g--1] 2// (dd/2). where I' denotes the Gamma function ['xx) So dr ==== Thus, with converges weakly to Dirac measure 5(t) as c + oo, once properly rescaled. In particular, choosing k; such that k; (s 3)/2 = (d 3)/2, one has
r (ks 5)
(1 () -1- 8(t)).
lim 7,000
=
(S51)
VTl (ks (
As result, when 1C is infinitely differentiable, one has the following equivalence in the limit where all ky 's are large,
I1 S [is-
h r(
Ao
((()) (0),
(S52)
((
which implies that, when K. is infinitely differentiable, the eigenvalues decay exponentially or faster with the k.
Let us now consider the nonanalytic part of K. There are three kinds of terms appearing in the singular expansion of depth-3 kernels (cf. Subsee. C.T):
ia) c E, 4 near 4 = + 1;
ib) e_ (1 + 4:)* near 4; 1== 1;
ii all aml (1 - (1)pp)" near 4; = + 1 for all i;
where the exponent is 1/2 for the NTK and 3/2 for the RFK. We will not consider terms of the kind ib) explicitly, as the analysis equivalent to that of terms of the kind ia). After replacing t; with cOs( as in Subsee. C.2 we get again E, |0,12" and ||0] as leading nonanalytic terms. Therefore, we can rewrite the nonanalytic part of the kernel as follows,
Kna(()) Σ (10.)) + f2(( + (C())
(S53)
23

---

Under review as a conference paper at ICLR 2023
where f1, f2 are single-variable functions which behave 8 near and have compact support, whereas IC has a singular expansion near 0, 0 analogous to that of K. but with leading nonanalyt- icities controlled by an exponent 2リ 1.
Let us look at the contribution to the eigenvalue A& due to the term fi f(00))):
II
p
3
d0, (sin (0,))*= (co,s(cos(0))) (0;)) Si(10:))
(S54)
II jt
2 G
/ dl (sin (0))- Pki (cos (0))
To (fi)es Jiti
where we have introduced (fi)g as the projection of fi on the k-th Legendre polynomial. The asymptotic decay of (Si) is strictly related the differentiability of Si, which is in turn controlled by action of the haplace-Beltrane operator A fi. As function the sphere Se-1, fi depends only on one angle, therefore the Laplace- Beltrami operator acts as follows,
saplace-Beltrami
(0) sin (0) d0
sin (0) (0)=
dfi (0) (0) + (d - 2) d0
COS sin (1(
(S55)
In terms of singular behaviour near 0-0, (0) 1 implies ( 10 20-2 thus A Ji (0) [0]2(v-m), Given v, repeated applications of A eventually result in function whose 12 norm on the sphere diverges. On the one hand,
/ do sin 4-2 (0))((0)**)10))
(S56)
The integrand behaves as 10/ (0dd2--00 40 2m near thus the integral diverges for m 2 2v + (d 1)/2.
On the other hand, from Eq. S3
m/2
Nna (k(k + 2)
+ 1(1)) ((i))
(S57)
As NR. 2--2 and the sum must converge for < 2 (d-1)/2 and diverge otherwise, (fi) 2-- The projections of all the other terms in K. on Legendre polynomials of one of the p angles 0g display a faster decay with k therefore the above results imply the asymptotic scaling of local eigenvalues. Notice that such scaling matches with the result of Bietti & Bach (202T), which was obtained with different argument.
Finally, let look the contribution to the eigenvalue A& due the term f2(1)
II
P
S
de, (sin (0,))=-2 (cos (0,)) fa(1101)) = (f2)
(S58)
where we have introduced (/2), as the projection of f2(( on the multi-Leegnnrr polynomial with multi-degree k. The asymptotic decay of (ff)2 is again related to the differentiability of fa. controlled by action of the multi-sphere Laplace- BelttrBa operator Ap,s in Eq. S13 As f2 depends only on one angle per sphere,
Σ 02 + (s - 2) cos (0.)
0o /a((101)) sin (0,)
Ap,0/((101))
(S59)
Further simplifications oceur since fz depends only on the norm of 0. In terms of the singular behaviour near ||0|| 00 f2 |0||20 implies Am f2 ~ (10])201m)) thus
|| A m/2 p.4
fzll
/ dFo II
(sin - (0.)) fz A 02( < +o0
(S60)
10.m] i=1
24

---

Under review as a conference paper at ICLR 2023
requires 2v + p(s 1)/2 (compare with Therefore, one has
2v + (s 11/2 for the local contributions).
1 f1ll = Σ NR
Σ (4; + s ((2))al2 < too Vm < 2v+p(s-1)/2
(S61)
while the sum diverges for m 2 2y + p(s - 1)/2. In addition, since f2 is radial function of which homogeneous (or scale-invariant) near ||0|| = (f2) can be factorised in the large- ||||| limit into a power of the norm || and a finite angular part C(k/||&|l) By plugging the factorisation into Eq. S61. we get
(i10)/1))) C(R//1A11)))
(f2) ~ C(k/)//)//|| 22
Σ |.|
+00
(S62)
The projections of all the other terms in on multi-Legendre polynomials display a faster decay with ||]]], therefore the above results imply the asymptotic scaling of global eigenvalues.
C.4 GENERAL DEPTH
The generalisation to arbitrary depth is trivial once the depth-3 case is understood. For global and 81 s1-local eigenvalues, the analysis of the previous section carries over unaltered. All the other inter- mediate sectors correspond to the other terms singular expansion of the kernel: from Subsec. C.I these terms can written as
C
1
Σ f2
(1
(S63)
PL
II PCP'SLL
ip 11
II 251ES1
8y"
8to
for some 1' 2, 2,...,-- and fractional v. In practice, this term is sum over the Pr = PP I S1"" meta-pater meta-patches of t having size 82-2l' := I22<p< St". Each summand is the fractional power v of the average of the 1;'s within a meta-patch. When plugging such term into Eg. S47, the integrals over the t,'s 's which do not belong that meta-patch yield Kronecker deltas for the corresponding kj's. The integrals over the tt's within the meta- patta, instead, can be written in Eq. S58 with the product and the norm restricted over the elements of that meta-patch,
1/2
Therefore, the scaling of the eigenvalue with k is given again by Eq. S63 but with p replaced by the size of the meta-patch 12ggnge 81", so that the effective dimension of [gq. 3) alappears at the exponent.
i.e., ||0|| Eigno 02 (14))))
D GENERALISATION BOUNDS FOR KERNEL REGRESSION AND SPATIAL ADAPTIVITY
This appendix provides an introduction to classical generalisation bounds for kernel regression and extends Cor. 4.1 to patches the hypersphere.
D.1 CLASSICAL GENERALISATION BOUNDS
Consider the regression setting detailed in Sec. 4 of the main text. First, assume that the target function f belongs to the RKHS H of the kernel X. Then, without further assumptions on KG have the following dimension-fi free bound on the excess risk, based Rademacher complexity
[Bach] 2021 Chs. 4, 7), Bietti (2022).
<(A,)) c()) S SCI Tr(Tk) n
(S64)
25

---

Under review as a conference paper at ICLR 2023
where Ti is the integral operator associated to K. For hierarchical kernel, having target with more power in the local sectors can result in smaller | hence a smaller excess risk. However, this gain is only constant factor in terms of sample complexity and, more importantly, being in the RKHS requires an order of smoothness which typically is of the order of the dimension, which is a very-restrictive assumption in high-dimensional settings. This result can be extended by including more details about the kernel and the target function.
In particular, (Bach 2021 Prop. 7.2) states that, for f" in the closure of H. regularisation À and n 2 X (1 log 1/2]), one has
E(A, n) { S 16 o² Tr ((Tr A1) 16 inf
24
-15- + A
|1 Fix n2
SEN
(S65)
where x² bounds the conditional variance of the labels, i.e. ((yy))~ [VV- (f-
(x)) x
< o².
Then, let us consider the following standard assumptions in the kernel literature Caponnetto & De Vito (2077),
capacity: Tr (Te/
ΣΣ
(Ak) 1/0 < +00,
k20
source: |
fz
Σ 420
(At) "fiiee +00.
(S66)
In short, the first assumption characterises the 'size' of the RKHS (the larger a, the smaller the number functions in the RKHS), while the second assumption defines the regularity of the target function relative that of the kernel (when
f E H: when 1, f less smooth; when
r > 1, f is smoother). Combining these assumptions with Eq. S65 one gets
24 n2 ||
E(A, - -((") & 16 n
1/a-1/a + 1O
(S67)
Optimising for À results
CiO²
An
(S68)
ar
and the bound becomes
Cia²
a041
- -(({)) S Cr I
(S69)
11.
n
Finally, when > (ax - 1)/a, n
(1 + log(1/ (g((1)n)) An)) always satisfied for n large enough. 5 Am
D.2 EXTENSION OF COR. 4.1 TO PATCHES ON THE HYPERSPHERE
Corollary D.1 (Adaptivity to spatial structure) Let Tr. be the integral operator of the kernel of a hierarchical deep CNN in Thm. 3.1 Then: i) the capacity exponent is controlled by the largest sector of the spectrum, i.e.
Tr ( a< <1420<<eeee
(S70)
ii) the source exponent r is controlled by the structure of the target function f*, i.e. if there is I I L such that f depends only on some meta-patch T2411-141 then only the first sectors of the spectrum contribute to the source condition,
E
Σ Σ
Σ
(A
4 )² (S71)
2
1=1
11
Rap-1-
The same holds if f is a linear combination of such functions. As result, when dea (L) large and a + 1, the decay of the error is controlled by the effective dimensionality of the target den (l).
26

---

Under review as a conference paper at ICLR 2023
D.3 DECAY OF EIGENVALUES WITH THE RANK
Shallow kernels. Consider depth-rwo kernel with filters of size s. Our goal is to compute the scaling of the eigenvalues of the kernel A& with their rank p. The eigenvalues decay with & as
P
A
2vs (s 1)
I jzti
(S72)
In order to take into account their algebraic multiplicity, we introduce the eigenvalue density ( whose asymptotic form for small eigenvalues is
D(A) = Σ
8(A Ak)
k,
1 8
P
hi
(x-1)
II
1=1
ki-26 28 AA kig
2v--1())))
dk h 28 (A kー (2-2--0-1)
20-(x-1)
(S73)
Thus, the scaling of App) can be determined self-consistently,
A(1)
dAD(A) A(p) - A(p) ~ p -
(S74)
A(p)
Deep kernels. Consider kernel of depth + with filter sizes (81, 81.) and pr. 1. For each sector I, one can compute the density of eigenvalues (o) (A). Depending 81, there are two different cases.
If = 2,
(in(A) = Σ E (())
h
Σ Σ 6 (A- C2,1 C2, |
2v do-l)r(()
11141
dk hattt (1) 18 (A (A- (A-C2,
C221 k- (22-dditt())
(3)
(S75)
sf 2 3,
D()(A)= Σ 8(A A!1)
5(A
k.e
8(^ (A- A- C...
kinj 1211 [
Σ
Σ
8
[ 1-2
441-141
1
1441-1411
A
(S76)
When summing all layers I's, the asymptotic behaviour of the total density of eigenvalues D(A) = Σ, (A) is dictated by the density of the sector with the slowest decay, i.e. the last one.
Hence,
D(A) A 25 (
(S77)
27

---

Under review as a conference paper at ICLR 2023
Therefore, similarly to the shallow case, one finds self- ceaisssssittetlly that the p-th eigenvalue of the kernel decays as
(p) L2T
(S78)
E STATISTICAL MECHANICS OF GENERALISATION IN KERNEL REGRESSION
In Bordelon et al. (2020); Canatar et al. (021). the authors derived a heuristic expression for the average-case mean-squared error of kernel (ridge) regression with the replica method of sta- tistical physics Mézard et al. (1877). Denoting with {0)(2), Ap]p21 the eigenfunctions and
eigenvalues of the kernel and with Co the coefficients of the target function in this basis, i.e. (x)== = (p)p(x), one has
(AA(m) n
kA(
c(A,n) 0x
(nAp + xx)))) Blegl,
(S79)
where À is the ridge and x(n) satisfies the implicit equation
x
x 1 Σ Appx(n)/n
(S80)
In short, the replica calculation used to obtain these equations consists in defining energy func- tional E(f) related to the empirical MSE and assigning to the predictor / a Boltzmann measure, iee P(f) x e-BB()) When B + xc, the measure concentrates around the minimum of E()), which coincides with the minimiser of the empirical MSE. Then, since E(f) depends only quadrat- ically on the projections Cp. computing the average over data that appears in the definition of the generalisation error, reduces to computing Gaussian integrals. While non-rigorous, this method has been successfully used in physics to study disordered systems- and in machine learning theory. In particular, the predictions obtained with (eh. S79 and Eq. Sa0eaave been validated numerically for both synthetic and real datasets.
In Eq. S79 Hx (n)/n plays the role of threshold: the modal contributions to the error tend for & such that Ap >> (x(n)/n /n, and to E[c²] for P such that A, < (m)/nn. This is equivalent to saying that kernel regression can capture only the modes corresponding to the eigenvalues larger than (n)/n (see also Jacot et al. 22000a b)).
In the ridgeless limit À + 0+, this threshold asymptotically tends to the reth eigenvalue of the stu- dent, resulting in the intuitive picture presented in the main text. Namely, given training points, ridgeless regression learns the n projections corresponding to the highest cigenvalues. In particular, assume that the kernel spectrum and the target function projections decay as power laws. Namely, 1. Furthermore, we can approximate the summa-
Ap ~ p and E[c,'' 2] ~ م=b with 20 > tions over modes with integral by using the Fuler-MacLaauin formula. Hence, substitute the cigenvalues with their asymptotic limit A, Ap- Since, ko(n)/n + 0 as n + co, these two operations result in an error which asymptotically independent of In particular,
(n(n) n n (%. [o((n)
(n(n) 1
Ap
Ap + ko(n)/n dp+ 0(1)
(n) 1 n n n
a
Abb do + +0(1).
(S81)
1+0
Since the integration over is finite and independent of n, we obtain that (n(nn/n (nn-a). Similarly, we find that the mode-independent prefactor dy (mx(n)/n) IA-o 0(1)
As result, we have
72 2a
E(n2 ~ Σ
(Ap-a + n a) Elegl-
(S82)
Following the intuitive argument about the thresholding action of ko(n) //n ~ n-a we can split the summation in Eq. S82 into modes where Ap > Ko PP/n,, n,, Ap ko(n)) n and A, < ko (o(n//n.
<(n)
E + Σ B Σ El ap-aa
(S83)
pen (Ap
poum
28

---

Under review as a conference paper at ICLR 2023
Finally, Eq. 12 is obtained by noticing that, under the assumption the decay of E|c)), the tribution of the summation over p < n is subleading in n, whereas the other two can be merged together.
F EXAMPLES
F.1 RATES FROM SPECTRAL BIAS ANSATZ
Consider a target function f which only depends on the meta-patch Zi441-141 and with square- integrable derivatives up to order m, i.e. ||/m// f 1=1 < +o0, with denoting the Laplace operator. Moreover, consider hierarchical kernel of depth I. + with filter sizes ($1,-.., 81)) and pz 1. We want to compute the asymptotic scaling of the error by using Eq. 12 i.c.
((n)
Σ 1s
(S84)
k.Est. (A()
In the previous section, we showed that the n-th eigenvalue of the kernel A(n) decays as
2"
(n))
(2
(S85)
Since by construction the target function depends only on meta-patch of the I-th sector, the only non-zero projections will be the ones on eigenfunctions of the first / sectors. Thus, all the k's corresponding to the sectors of layers with is dominated by the k's of the largest sector and the set {k s.t. A < A(n)} is the set of -1-1-141 s
do contribute the sum. particular, the sum
2 I dem(()
with norm larger than n. (2veddaf (01) (dE(C)
Finally, we notice that the finite-norm condition on the derivatives,
P II Ni..
P
ki + (((k++s-2)) 2)) m
12
Σ
1fk.el < +00,
(S86)
implies 1/ < | 22m (see Subsec. C.3
Hence, plugging everything in Eq. S84 we find
deg(() (2)
E(n) 20
(S87)
G NUMERICAL EXPERIMENTS
G.1 EXPERIMENTAL SETUP
Experiments
high- high-performance computing cluster with nodes having Intel Xeon Gold processors with 20 cores and 192 GB of DDR4 RAM. All codes are written in PyTorch Paszke et al. 2019).
G.2 TEACHER-STUDENT LEARNING CURVES
In order obtain the learning curves, we generate n. + Thest random points uni- formly distributed on the product of hyperspheres over the patches. We use e (128, 256, 512, 1024, 2048, 4096, 8192) and nest 8192. For each value of n, we sam- ple a Gaussian random field with zero mean and covariance given by the teacher kernel. Then, we compute the kernel regression predictor of the student kernel, and we estimate the generalisation emoor as the mean squared error of the obtained predictor on the Rhest unseen example. The expecta- tion over the teacher randomness obtained by averaging over independent sets of random input the
points and realisations of the Gaussian random fields. As teacher and student kernels, analytical forms the neural tangent kernels of hierarchical convolutional networks, with different combinations of depths and filter sizes.
29

---

Under review as a conference paper at ICLR 2023
b
10
10
10-3
T: (2), S: (2)
10 2
(2), St (2,
B 41-1
1
T: (2), S: (2, 2)
T. (2. 2)
1+ B
B 1/dut?
10-3
10a
104
10a
10*
Figure S1: Learning curves for deep convolutional NTKs (v 1/2) in teacher-student setting. Depth-two teachers learned by depth-two (matched) and depth-three (mismatched) students. Both these students not cursed by the input dimension. b. Depth-three students learning depth-two and depth-three teachers. These students are cursed only in the second case. The numbers inside brackets the sequence of filter sizes of the kernels. Solid lines the results of experiments averaged over 16 realisations with the shaded areas representing the empirical standard deviations. are reported dashed lines.
The predicted asymptotic scaling
Depth-two and depth-three architectures. Fig. S] reports the learning curves of depth-two and depth-three kernels with binary filters at all layers. Depth-three students defeat the curse of dimen- sionality when learning depth-two teachers, achieving similar performance of depth-two students matched to the teacher's structure. However, as we predict, these students encounter the curse of dimensionality when learning depth-three teachers.
Ternary filters. Fig. S2 reports the learning curves for kernels with 3-dimensional filters and con- firms our predictions the $1 2 3 case.
Comparison with the noisy and optimaaly-regullrriee case. Panel (a) of Fig. S3 compares the learning curves obtained in the data, respectively. The first case corresponds to the setting studied in [aaonnetto & De Vito (007), in which the source-capacity formalism applies. In contrast with the second setting- which is the used in the teacher-student scenarios and where it holds the correspondence between kernel methods and neural networks-i) we add to the labels a Gaussian random noise with standard devi- ation 0.1, ii) for each n. select the ridge resulting in the best generalisation performance. We observe that the decay obtained in the bound derived from the source-capacity conditions is exactly the one found numerically, i.c. the rate of the bound is tight. As a further check, panel (b) shows that the optimal ridge decays as prescribed.
and ridgeless cases for noisy and noiseless
G.3 ILLUSTRATION OF DIFFERENT TEACHER-STUDER SCENARIOS
In this subsection, we comment on the results obtained in the different teacher-student scenarios of Fig. panel (a), and Fig. SI panel (a). To case notation, in the following we always consider the NTK for both teacher and student kernels, i.e. smoothness exponent Vr = Vg 1/2. However, point out that when the teacher kernel is hierarchical RFK (ur 3/2),, the target function corresponds to the output of an infinitel-wwide, deep hierarchical network at initialisationf] The
error rates are obtained from Eq. 17 after setting the smoothness exponent Pr (the smoothness exponent of the teacher covariance kernel).
'See, e.g, Lee al. (017)) for the equivalence between infinitelywwide networks and Gaussian random fields with covariance given by the RFK.
30

---

Under review as a conference paper at ICLR 2023
b
10a
10-1
(3), S: (3. 3)
(3), 3.
B de
T: 33,33,
10
(3,
5: (3, 3)
== 1/der
B (T-82008.01))
10a
10f
10a
10*
n
Figure S2: Learning curves for deep convolutional NTKs (v = 1/2) with filters of size 3 in teacher-student setting. a. Depth- tepphe students learning depth-two and depth-three teachers. These students are cursed only in the second case. b. Depth-three models are cursed by the effective input dimensionality. The numbers inside brackets are the sequence filter sizes of the kernels. Solid lines are the results of experiments averaged over 16 realisations with the shaded areas representing the empirical standard deviations. The predicted asymptotic scaling n-3 are reported as dashed lines.
b
Noisy
10
-lar
B 1/(1 dar)
Noiseless
10-1
3- 1/dair
< 10
10-6
10a
10
10a
Figure S3: Noisy (optimalllyregullarieee) noiseless (ridgeless) learning curves for depth-three deep convolutional NTKs (v 1/2) in a teacher-student setting. a. Comparison between the learning curves in the noisy and noiseless case. Dashed lines represent the rates predicted with source-capacity bounds and replica calculations, respectively. Shaded areas represent the empirical standard deviations. b. Decay of the optimal ridge with the number of training points.
31

---

Under review as a conference paper at ICLR 2023
The first case consider consists of one-hidden-layer convolutional teacher (left) and student (right) kernels.
((n) ~
As highlighted in blue, the output of the teacher linear combination (dashed lines indicate the linear output weights) of s -dimensionnll functions of the input patches. If the structure of the student matched to the one of the teacher, the learning problem becomes effectively (5) - 1)-dimensional and the error decays as n n11((=1>) instead n 1/datt, with deff the total imput dimension with the number of spherical constraints subtracted (one per patch). Notice that the role of the student's 's structure, i.c. the algorithm, is as crucial as the role the teacher, i.c. the task. Indeed, using a fully-connected student with prior the task's locality would result in error's 's decay cursed by dimensionality. However, contrast to fully-connected students, shallow convolutional students only able learn tasks with the same structure. In particular, any task entailing non-linear interactions between patches-which are arguably crucial in order to learn image data-belongg to their null space.
As we illustrated in the main text, to solve this strong constraint on the hypothesis space, one has consider deep convolutional architectures. In particular, consider the same shallow teacher of the previous paragraph (left) learnt by a depth-four convolutional student (right).
1 (3) derr(3)
E(n)
x
X3
Remarkably, this student is able to learn the teacher without being cursed by input dimensionality. Indeed, as the number of patches diverges, the error decay asymptotes to 11/e1, This rate is slightly worse than the one obtained by the student matched with the teacher, which proven to be the Bayes-optimal case, but far from being cursed. Intuitively, this fast rate is obtained because the student eigenfunctions of the first sector, i.e. constant outside single patch, correspond to large eigenvalues and bias the learning dynamics towards -local functions. Yet, this student is also able to represent functions which are considerably more complex.
Now consider depth-three teacher (left) learned by depth-four student (right).
(3 4aff
E(n) ~ n --1
%y
As highlighted in orange, the output of the teacher is linear combination of composition of non- linear functions acting on patches and coupling them. In this setting, the error decay controlled by the effective dimension of the second layer. In fact, when the number of patches diverges, the error
32

---

Under review as a conference paper at ICLR 2023
decay asymptotes to n (2) In general, this behaviour is result of what we called "adaptivity to the spatial structure' of the target.
Finally, consider both teacher and student with the complete hierarchy, i.c. the receptive fields of the neurons in the penultimate layers coincide with the full input.
Z(n) ~ 12 Featss
In this case, we show that the eπrоr decays as n 1/dar((3) i.. the rate is cursed by the input di- mension. The physical meaning of this result that the hierarchical structure we are considering still too complex and cannot be learnt efficiently. In other words, these hierarchical convolutional networks are excellent students, since they can adapt to the spatial structure of the task, but bad teachers, since they generate global functions which are too complex to be learnt efficiently.
G.4 EXTENSIONS TO DIFFERENT NORMALISATIONS AND OVERLAPPING PATCHES
This section investigates the robustness of our results to changes in the input distribution, i.c., for data outside the multisphere MPS*-1, and relaxes the non-overlapping patches assumption.
Inputs in Rd. While our analysis requires that each patch of the input data normalised to on a unit sphere, this normalisation is not the standard one used for neural networks. Therefore, in this section we investigate the robustness of our predictions to the data distribution. In particular, we consider data uniformly distributed in the unit hypercube, i.e., E [0, 1j4, and data with standard Gaussian distribution, i.e., x ~ (0, Ia). First, we extend the definition of the RFK and NTK to inputs in Rd
Definition G.1 (RFK and NTK of hierarchical CNNs for inputs in Rd) Let D. E RRd Denote tuples of the kind iii44 ... Am with ir-mm for m 2 For m <,,, it-m denotes the empty tuple. For each tuple 12-1411 and a divisor of d, denote with t22-241 the angle between the s-dimensional patches of x and y identified by the same tuple, i.e.
Dig
Vin-
1i2-111
(S88)
1ig--141 Vig-
For 1 1SISL+ 1, denote with { (Di Voa-n i2-st the sequence of patches obtained by letting the indices of the tuple i2--! vary in their respective range. Consider a hierarchical CNN with filter sizes (S1...., SL), PL 2 1 and all the weights Whis h,k' Wh, numbers with zero mean and unit variance.
(1) (1) (L+1) initialised as Gaussian random
RFK. The corresponding RFK (or covariance kernel) can be obtained recursively as follows. With ki (1) = ((T arccos 1) L /1 (2) /Tz,
(((1) ( 1i2- = Dig- 1+t1 Viz-o
161 (ttoona)):
Kill (f Vis-ctitianl
| ||2
1iieozz 12
V
81
1 Σ
KREK (Ziz 1011
Miz (ggmiin)
Ki
Ei | 112
V / Ei 13 1|2
Pz
KR (1riorets) Mia-et 12
x(L) (Artonees Pis-etilin (S89)
Pr.
#=+1=1
33

---

Under review as a conference paper at ICLR 2023
b
10a
10
10
10-1
T: (2,
4) 5: (2,
Ga. (2), S: 4)
MS.
4),
T: S: (2,
(2, 4), S: (2,
T: (2), (2, 4)
10
10a
10a
10a
Figure S4: Learning curves for deep convolutional NTKs (v NTKSs 1/2) in teacher-student setting with different input normalisations. In particular, we consider inputs on the multisphere MP5 (MS.), -iittiiuyyd in the unit d-hypercube [0, 1] (Cb.), and with standard Gaussian distribution (0, Ia) (Ga.). The numbers inside brackets are the sequence of filter sizes of the kernels. Solid lines the results of experiments averaged over 16 realisations with the shaded areas representing the empirical standard deviations. The asymptotic scaling ~ n - predicted for inputs on the multisphere are reported as dashed lines.
NTK. The NTK of the same hierarchical CNN can be obtained recursively follows. With ko(t)= = (π arccos t) /T,
KNTK (Zig Vi 2i2-z-1) 1ig 1ll////211 Il (4i2 + Bia-e-1 22 nollia KNTK (1 Via-eti F(
x-ll (Fig-14417 His-ztiiig sig
( (Zizmtire Viz ) Dimn
NTK
41
1 En, KHrk
(Dieeees Via-z Prmmen))
No
| 112 1I3 2 En, 11
Pc
x(L+1) (fzig-z1)
Vh2 211
KNTK
(frig.21a Via P (S90)
PL
f1+1=1
Fig. $4 reports the learning curve of different teacher-student scenarios with the kernels defined in Def. G.1 and inputs on the multisphere MPS--1, ii) uniformly-distributed the unit d-hypercube 00 1 and üii) with standard Gaussian distribution (0, La). Remarkably, our predictions are in excellent agreement with the different input normalisations.
Overlapping patches. Fig. $5 shows the comparison between convolutional kernels with non- overlapping patches, i.c., stride corresponding to the filter size, and overlapping patches, i.c., stride for inputs uniform in the d-dimensional hypercube. Despite theoretical analysis requires the patches to be non-overlapping, our predictions are still confirmed for architectures with overlapping patches.
G.5 CIFAR-2 LEARNING CURVES
Fig. shows the learning curves of the neural tangent kernels of different architectures applied to pairs of classes of the CIFAR-10 10 dataset. In particular, the task is built by selecting two CIFAR-16 10 classes, e.g. plane and car, and assigning label +1 to the elements belonging to one class and label -1 to the remaining ones. Learning is again achieved by minimising the empirical mean squared error using 'student' kernel. We find that the kernels with the worst performance corresponding to shallow fully-connected and convolutional architectures. Instead, for all the pairs of classes considered here, deep hierarchical convolutional kernels achieve the best performance.
the ones
34

---

Under review as a conference paper at ICLR 2023
10-1
10
NO. 12, 4) S: (2, 4)
4)
4)
NO.
(2), S:
(2,
Ov. T: (2), S: (2, 4)
10
10a
10
n
Figure S5: Learning curves for deep convolutional NTKs (v 1/2) with non-overlapping (NO.) and overlapping (Ov.) patches in a teacher-student setting with inputs normalised in d-hypercube. The numbers inside brackets are the sequence of filter sizes of the kernels. Solid lines are the results of experiments averaged over realisations with the shaded areas representing the empirical standard deviations. The asymptotic scaling - predicted for kernels with non-overlapping patches are reported as dashed lines.
a
b
0.60
0.50
0.80
C-NTK fsz=(8)
C-NTK fsz=
C-NTK fsz=(8,
0.70
C-NTK fsz= (8, 2)
C-NTK fsz=(8,
fsz= 2, 2)
F-NTK (L=2)
F-NTK (L=2)
0.30
F-NTK (L=3)
F-NTK (L=3)
10a
10
10a
10
n
Figure S6: Learning curves of the neural tangent kernels of fully-connected (F-NTK) and con- volutional (C-NTK) networks with various depths learning to classify CIFAR-10 classes in regression setting. Deep hierarchical convolutional kernels achieve the best performance. Shaded areas represent the empirical standard deviations obtained averaging over different training sets. a. Plane vs car. b. Cat vs bird.
35


Reviews:
[{"review_id": "li5QlHlqgb", "reviewer": "Reviewer_UzrZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 convolutional neural networks in the kernel regime. In particular, they show that the corresponding kernel's spectrum inherits the network's hierarchical structure.  Therefore, deep CNNs can beat the curse of dimensionality if the target depends only on local groups of variables.", "summary_of_the_review": "Overall, the results proved in this paper may be significant for people who study NTK. This paper feels complete, but I still have concerns about clarity. \n\nIn the abstract, the author gives the following claims. \"the rate of decay of the error is controlled by the effective dimensionality of these subsets,\" \"if the teacher function depends on the full set of input variables, then the error rate is inversely proportional to the input dimension,\" \"despite their hierarchical structure, the functions generated by deep CNNs are too rich to be efficiently learnable in high dimension.\"  Where can I find the support theorems of these claims? I tried my best to understand them, but I could only find some relevant explanations rather than solid theorems. \n\n", "strength_and_weaknesses": "Strength: \n1. The idea is novel.\n2. This paper is comprehensive, with the solid support of proof and experiment. \n\nWeakness: \n\n1. This paper is hard to follow since the claims are scattered in the paper, which is hard to find. \n\n2. This paper only cares about the NN kernel solution. So it doesn't have any optimization result or discussion of the width. \n\n3. This paper requires patch non-overlapping. It is unclear whether this paper can be extended to a more general setting. \n\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": "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": "ci-XZuZ2PqH", "reviewer": "Reviewer_gyaw", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 the generalization error decreases in multilayer CNNs. Using NTK, the authors theoretically show that the decay rate of the error is determined by the effective dimension of the data instead of the actual dimension. Here the effective dimension relates to how each hidden unit _sparsely_ depends on the output of the previous layer. The experiments also support the derived decay rate.", "summary_of_the_review": "The paper brings a neat analysis of CNN in terms of generalization error. My concern is that the assumption used in the analysis do not seem to match real problems. ", "strength_and_weaknesses": "Strengths\n1. The theoretical results are interesting. They clarify why CNNs are efficient in terms of learning theory. \n1. The experiments provide additional evidence that the decay rate is correct. \n\nWeaknesses\n1. The assumption of Eq 1 looks unrealistic. It poses that the input space should be the product of spheres, such as a torus. Images, a favorite data of CNNs, are not in that kind of space --- they are usually represented in a cube [0, 1]^{height x width x channel}. When an input is in a spherical space, it should be steerable and the same input should be obtained by steering 360 degrees. This property doesn't hold in the raw image space. I wonder how this assumption is critical in your analysis. Can we obtain the same result without the assumption? Also, does the assumption hold in the experiments?\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": "OaFr_JaDf7", "reviewer": "Reviewer_xmg3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 authors provide some generalization analysis for deep CNNs. Based on some spectral analysis, they prove that deep CNNs adapt to the spatial scale of the target function. They also show how the error rate depends on the input dimension. ", "summary_of_the_review": "The spectral and convergence analysis provided in the paper for deep CNNs is interesting. But the network structure in Equation (1) uses a special linear transformation. This restriction makes the mathematical analysis easier. More discussion on general networks would enhance the paper. ", "strength_and_weaknesses": "Deep CNNs have been studied theoretically recently and generalization error analysis has been carried out for CNNs of various types. The spectral and convergence analysis provided in the paper is interesting. But the network structure in Equation (1) uses a special linear transformation of a simply average over h', instead of a general linear combination, which is very special. This restriction makes the mathematical analysis easier. More discussion on networks with a general linear transformation would increase the scientific value of the paper. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject