Eigenspace Restructuring:  a Principle of Space and Frequency in Neural Networks
Authors: Lechao Xiao
Venue: ICLR 2022 Submitted (2022)
Keywords: neural network gaussian process
neural tangent kernels
eigenstructure
space and frequency
convolutional networks
spherical harmonics
hierarchical locality
over-parameterized networks

Abstract: Understanding the fundamental principles behind the massive success of neural networks is one of the most important open questions in deep learning. However, due to the highly complex nature of the problem, progress has been relatively slow.In this note, through the lens of infinite-width networks, a.k.a. neural kernels, we present one such principle resulting from hierarchical locality. It is well-known that the eigenstructure of infinite-width multilayer perceptrons (MLPs) depends solely on the concept frequency, which measures the order of interactions.  We show that the topologies from convolutional networks (CNNs) restructure the associated eigenspaces into finer subspaces. In addition to frequency, the new structure also depends on the concept space— the distance among interaction terms, defined via the length of a minimum spanning tree containing them.  The resulting fine-grained eigenstructure dramatically improves the network’s learnability, empowering them to simultaneously model a much richer class of interactions, including long-range-low-frequency interactions, short-range-high-frequency interactions, and various interpolations and extrapolations in-between.  Finally, we show that increasing the depth of a CNN can improve the inter/extrapolation resolution and, therefore, the network’s learnability.

Under review as a conference paper at ICLR 2022
EIGENSPACE RESTRUCTURING: A PRINCIPLE OF SPACE AND FREQUENCY IN NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Understanding the fundamental principles behind the massive success of neural networks is one of the most important open questions in deep learning. However, due to the highly complex nature of the problem, progress has been relatively slow. In this note, through the lens of infinite-width networks, a.k.a. neural kernels, we present one such principle resulting from hierarchical locality. is well-known that the eigenstructure of indihite-width multilayer perceptrons (MLPs) depends solely on the concept frequency. which measures the order of interactions. We show that the topologies from convolutional networks (CNNs) restructure the as- sociated eigenspaces into finer subspaces. In addition to frequency, the new struc- ture also depends the concept space the distance among interaction terms, defined via the length of a minimum spanning tree containing them. The result- ing aine-grained eigenstructure dramatically improves the network's lcarnability, empowering them to simultaneously model a much richer class of interactions, including Long-range-low-free wewfrruuunncy interactions, short-range-hige raage-highh-eeee high-freyuency in- teractions, and various interpolations and extrapolations in-between. Finally, we show that increasing the depth of CNN can improve the inter/extrapolation res- olution and, therefore, the network's 's learnability.
INTRODUCTION
Learning in high dimensions is commonly believed suffer from the curse of dimensionality. in which the number of samples required to solve the problem grows rapidly (often polynomially) with the dimensionality of the input. Nevertheless, modern neural networks often exhibit an astonishing power to tackle wide range of highly complex and nigh-dimensions real-world problems. many of which were thought to be out-of-scope of known methods (Krizhevsky et al.) 2012 Vaswani et al.) 2017 Devlin et al. 2018 Silver et al. 2016; [enior et al. 2020 Kaplan et al. 2020). What are the mathematical principles that govern the astonishing power of neural networks? This question perhaps is the most crucial research question in the theory of deep learning because such principles are also the keys to resolve fundamental questions in the practice of machine learning such as (out- of-distribution) generalization (Zhang et al. [202T), calibration (Ovadia al., 2019), interpretability (Montavon et al. 2018), robustness (Goodfellow et al. 2014).
Unarguably, there can be more than one of such principles. They are related to one or more of the three basic ingredients of machine learning methods: the data, the model and the inference algo- rithm. Among them, the models, a.k.a. architectures of neural networks are the most crucial inno- vation in deep learning that set it apart from classical machine learning methods. More importantly, the current revolution in machine learning initialized by the (re-)introduction of convolution-bast architectures (Krizhevsky et al., 2012 Lecun 1989), and subsequent breakthroughs are often driven by the discovery or application of novel architectures (Vaswani al. (2017); [Delii et al.) (2018)) As such, identifying and understanding fundamental roles of architectures of great importance.
In this paper, we take a step forwards by leveraging recent developments in overparameterized networks (Poole et al. (2016); Daniely et al. (2016); Schoenholz et al.) (2017): Lee et al. (2018); Matthews et al. (2018): Xiao et al. Lee et al. (2019) and many others.) These developments have discovered
et al. 2018); Du et al. (2018); Novak et al. (2019a);
important connection
between neural networks and kernel machines: the Neural Network Gaussian Process (NNGP) ker-
nels and the neural tangent kernels (NTKs). Under certain scaling limits, the former describes the

---

Under review as a conference paper at ICLR 2022
Shallow CNN
Deep CNN
High wigherraannyy
Spara Fredjancy- Busgel
Shoet Ran----nggeyyy Frequenry
Rarinn www.ertdaaaaaai wara---rrggge an
Orsar of Lealting
Finet trAepplicion
Froquenc
Long intpur/eeeoeeeeeuurrryy
Beyond Bucget
Firet traerpdacion
waggeooeeeeee Trequency
(8)
(b)
[d)
Figure 1: Architectural Inductive Biases. An demonstration of learnable functions vs archi- tectures for four families of architectures. Each shaded box indicates the maximum learnable eigenspaces within given compute budget (Dashed Line.) From left to right: (a) MLPs can model
Low--requeeeyy interactions; (b) S-CNNs can model Short-Range-Hiin Frequency interactions; (c) Additionally, D-CNNs can also model interactions between LRLF and SRHF, a.k.a., Median- -aant---annn--i-i-e Frruianny interactions. (d) Finally, HS-CNNs can ad- Ultra-Long-aann Ranng-
ditionally model interactions of Ultra-Short-Ranme Saeert--Rane-Ulee HeirraHiig-Frequeeee Ultra-Low-B Frequency,,,, and finer interpolations in-between. The Green Arrow indicates the di- rection of expansion of learnable functions when increasing the compute budget.
distribution of the outputs of a randomly initialized network (a.k.a. prior), and the latter can describe the network's ' gradient descent dynamics. Although recent work (Ghorbani et al. 2019 Yang & Hul 2020) has identified several limitations of using them in studying the feature learning dynamics of practical networks, we show that they do capture several crucial aspects of the architectural inductive biases.
Our main contribution is an eigenspace restructuring theorem. It characterizes a mathematical con- nection between a network's architecture and its learnability through trade-off between space and frequency, providing novel insights behind the mystery power of deep CNNs (more generally, hi- erarchical locality (Deza et al., 2020; Vasilescu (order) of the eigenfunction and by space, we mean the spatial distance among the eigenfunction's interaction terms. We summarize our main contribution below; see Fig.
al.] (02T).) By frequency, we mean the degree
1. The learning order (see Green Arrow in Fig. T of cigen-functions is governed by the learning index (LI), the sum of the frequency index (FI) and the spatial index (SI), which can be characterized precisely by the network's topology.
2. There is a trade-off between space and frequency: within a fixed (compute/data) budget, it is impossible to model generic Long- -aigg-Rnge-Haae High-Frequenn
interactions. MLPs can model Long-Range- -awaaaannn---reeeeeeeeee oow-Fregy (LRHF) interactions but fail to model SahoortRange-Higee Frequency (SRHF), while shallow CNNs (S-CNNs) are the opposite. Remarkably, deep CNNs (D-CNNs) can simultaneously model both and various interpolating interactions between them (e.g., Median- Range-Median-
(MRMF).)
3. In addition, high-resolution CNNs (HS-CNM EfficientNet-tyree of model scaling) further broaden the class learnable functions to contain (1) extrapolation: Ultra-Long- Lorra-Lon--ange- Ultra-Low- Frequency and the dual interactions and (2) finer interpolations interactions.
4. Finally, we verify the above claims empirically for neural kernel methods and winttewwithh networks using SGD Momentum for dataset and networks of practical sizes.
2 LINEAR AND LINEARIZED MODELS
As a warm up exercise, we briefly go through the training dynamics of linear models. Let (X,)) denote the inputs and labels, where X' C Rd and y C R. Assume RRd -> R is feature map and the task is to learn a linear function f(x 0) = J(x)0 to minimize the MSE objective (( [f 0) - 212. Let R(X,0) f(X, y be the residual of the predictions of X. Then the gradient flow dynamics can be written as
-x)x - -K(X, di
(1)
2

---

Under review as a conference paper at ICLR 2022
Since the feature kernel (() is constant in time, the above ODE can be solved in closed form. Let m | the cardinality of X and K(j)/u, be the j-th eigenvalue/eeigenvecoor of K( 2¹) in descending order. By initializing 0 = 0 at time & = 0 and denoting the projection by My u3 ((,,0) the dynamies of the residual and the loss can be reduced to
9KX 0²)
Σ
[(0.) - Σ
jEim]
]c(mm]
Therefore, to make the residual in uj smaller than some > O, the amount of time needed is
t 2 R 24 /2. The larger K(j) is, the shorter amount of time it takes to learn uj-
Although simple, linear models provide us with the most useful intuition behind the relation between "eigenstructures" and learning dynamics.
2.1 LINEARIZED NEURAL NETWORKS: NNGP KERNELS AND NT KERNELS
Let x0) be a general function, e.g. / is neural network parameterized by 0. Similarly,
d dt (x, 0)
(x; 0) Xx;
(3)
However, the kernel K(X,, X; depends via the Jacobian 0(x;0) of f(X;; 0) and evolves with time. The above system is unsolvable in general. However, under certain parameterization methods (e.g. (Sohl-Dickstein et al. (2020)) and when the network is sufficient wide, this kernel does not change much during training and converges to a deterministic kernel called the NTK (Jacot et al. 2018).
<(X,x;0)) + (x) as width + 00.
(4)
The residual dynamics becomes constant coefficient ODE again OxXX (XX X) 0). To solve this system, we need the initial value of RX' 0). Since the parameters 0 are often initial- ized using iid standard Gaussian variables, as the width approach infinity, the logits f(X'; 0) converge to Gaussian process (GP), known as the neural network Gaussian process (NNGP). Specifically, f(X; 0) ~ (0;3E X)), where K the NNGP kernel. Note that one can also treat infinite-widde networks Bayesian models, a.k.a. Bayesian Neural Networks, and apply Bayesian inference to compute the posteriors. This approach is equivalent to training only the network's s classification layer (eee al. 2019) and the gradient descent dynamics is described by the kernel K.
As such, there are two natural kernels, the NTK θ and the NNGP kernel K, associated to infinite- width networks, whose training dynamics are governed by constant coefficient ODEs. To make progress, it is tempting to apply Mercer's Theorem to eigendecompose ② and H, e.g..
K(z, Σ (1))) and ((x Σ (()))
(5)
One advantage of applying this decomposition that it has almost no constraint on the kernels and the inputs. However, this decomposition is too coarse be useful since it can hardly provide fine-grained information about the eigenstructures. E.g, it is not clear what are the corrections to Eq. (5) when changing the architecture from a 2-layer CNN to 4-layer CNNs. For this reason, we choose to work on the product space of hyperspheres, which has richer mathematical structures. Our primary goal is characterize the analytical dependence of the decomposition Eq. (5) on the network's ' topology in the high-dimensional limit.
3 NEURAL COMPUTATIONS ON DAGS
Notations will become heavier starting from this section. In particular, we rely crucially on the directed acyclic graphs (DAGs) and minimal spanning trees (MSTs) to define the spatial complexity of eigenfunctions. In Sec. we provide a toy example to help understand the motivation.
For positive integer p. let Sp-1 denote the unit sphere in Rp and S SpSp-1, the sphere of radius vp in TRP. We introduce the normalized sum (integral)
f ZEX
f(x)=|x|
Σ f(x) ZEX
(for
f(x) [xx)())=)))) ((X)- f(x))
[(x)==(x)11
/ f()))(dz))
(6)
ZEX
3

---

Under review as a conference paper at ICLR 2022
where X is finite set (a measurable set with finite positive measure 11).
We find it more convenient to express the computations in neural networks, and in neural kernels via DAGs (Daniely et al.) 2016), both computations are of recursive nature. The associated DAG of a network can be thought of as the same network by setting all its widths (or the number of channels for CNNs) 1. Let g (N, denote DAG, where N and & are the nodes and edges, resp. We always assume the graph to have a unique output node Og and is an ancestor of all other nodes. Denote No " the set of input nodes (leaves) of G, i.e., the collection nodes without child. Each node u E N is associated with pointwise function &.. + R, which is normalized in the sense E (2(
[-1,1] + I defined to be (1) S,),, Pu (21 (=2). Here N₂ denotes a pair of standard Gaussians with correlation t. We associate each u E N unite-dimensions Hilbert space Hu, and each uv & bounded linear operator Luv Hy, H,, Let
1. induces function o
X
II X
II NENo
(dim(H.))1 )-1 S II H. and I 1|N6l
N.No
meN
be the input tensors and the input correlations to the graph 9, resp. We associate two types of computations to DAG: finite-width neural network computation and kernel computation,
Ng X Hog and Kg I
resp. They are defined recursively as follows
(x) =du
&u
Σ
Law (No
if u $ No else Nu((x))
(8)
K.(t) 0%
(frwwes
(t)()
if a # No
else Kt(t) tu
(9)
where æ E X and t E The outputs of the computations are (x (x)( and Kg(t) Hog (t). Note that Kg is indeed the NNGP kernel. The NTK can also be written recursively as
On((I== = dú (f
(ho((1) S (1), + O,)))
with OG = Oog.
(10)
Here, O - a E No and di the derivative of di.
3.1 THREE EXAMPLES: MIPs, S-CNNS AND D-CNNS.
To unpack the notation, we consider three concrete examples: an L-hidden layer MLP, a shallow convolutional network (S-CNN) that contains only one convolutional layer and deep convolutional network (D-CNN) that contains (1 + L)) convolutional layers. The architectures are
MIP:
[mpud] + [Dense-Ac]] 60 [Dense]
(11)
S-CNN:
Inpua] + [Conv(p)-Act) + FFlatten-Dense
(12)
D-CNN:
[Inpt]] + [Conv(p)-Aci] + [Conv(k)) + Delstten-Dense-Add [ensee]
(13)
where p/k is the filter size of the first/hidden layers and Act means activation layer. We choose the stride to be the same as the size of the filter for all convolutional layers and choose flattening as the readout strategy rather than pooling, See Fig. [ (a. b, c) for the DAGs associated to (1+3)-layer d (1+1)-layer CNN (with p k ddt and 4-layer MI.P
CNN (with
MLPs. Let G be a linked list with (L + 2) nodes, including the input/output nodes. Let Luv E m X where nu/o = dim(H,, and the activations of the input/output nodes be the identity function. Then Ng represents a L-hidden-layer MLP. In addition, let L... be initialized iid as
Luv
(Win.t)) (Wmn.s)) (efe...j) The
Wan,ij 1),
(14)
Let tr xx x' /m. for E No and n, oo for all hidden nodes, then the outputs of ((()) converge weakly to the GP (0, ) and (t )a, is the NTK in the sense
(.Ng(x)Ngg(2))
prob,
Heg (t and (VNg(w)) Vog(x()) proo Og(ta,ar).
(15)
4

---

Under review as a conference paper at ICLR 2022
Uha Ston-Rangg----- oeeFrequacyy 055--11-4
hupe
Tregunncy O
MLP
(b) (NN )02
(c) CNN 94
(d) MSE Residual
Figure 2: Architectures/DAGs.. vs Eigenfunctions vs Learning Indices. Left to right: DAGs as- sociated (a) four-layer MLP; (b) CNN a"D"-CNNI that has two convolutional layer (c) CNN(p) 01 "HR"-CNN that has four convolutional layers; and (d) MSE (Y-axis) training set size (X-axis) for Y2 obtained by NTK-regression for architectures. Here Y2 is linear combina- tion of cigenfunctions of the expression. The DAGs are generated with p = 4. each DAG, the Dashed Lines represent the edges with zero weights. The Solid Lines have weights 0, 1/ and 1 in (a), (b) and (c), resp. The col- ored path represents the minimum spanning tree used to compute the spatial indices of Y2. Under architectures (a), (b) and (c), the spatial indices are 0, and 1 resp. Each input node represents input patch of dimension p² = d. p² = d' and p = d' and the frequency indices are 2, 2 x and 2 x 1/2 in (a), (b) and (c), resp.
Range-Lon-
interactions (deg( 22) 2); see Sec. D for
Indeed, note that deg(u) = 1 for all u & No. Eq. (9) and Eq. 10 become
Hy (t (tx,,))) 0. (Kx (tx,,)) and Ou(tm, o (H, (tx, )) (3C, (tx, O ()
(16)
which are the recursive formulas for the NNGP kernel and NTK; see e.g. Sec.E in Lee et al. (2119)
The input X' = 1 Ixw C Rdd where p is the patch size, w is the number of patches, = pw is the dimension of the inputs. Here, the inputs have been pre-processed by a patch extractor and then by normalization operator. In words, the S-CNN has one convolutional layer with filter
S-CNN.
size p. followed by an activation function ø (e.g.. Relu), and finally by a flatten- dente readout layer. Mathematically. by letting E N be the number of channels in the hidden layer, the output (i.e., logit) is given by
Convolution + Activation:
<x)(x) =
2
for i [w]. E [n]] (17)
pE(N]
Flatten Dense:
((x) = (wn)- -
W2,1g Zi,i
(18)
ve kE(M].jE[m]
where wi,i and W2,sý are the parameters of the first and readout layers, resp.
(N, 3 to the above S-CNN. Let the input, hidden and output nodes be No [1] [w]] Mi = [w]] and N22 {oo] {0). resp. and N = No U., U.2. Moreover, uo E E if u og and v E N₁ or u = (i, E M1 and v = (0, E No. Let HH = R2 for No. H., = R if u N and Tl TR. The associated linear operators are given by
We can associate a DAG
Lue p (wI. E IRRP for (u,v) E N
(19)
Loge = (wn) (w2 )5 E if v v= EL
(20)
Note that the weights are shared in the first layer but not in the readout layer (i.c., the network has no pooling layer). To compute the NNGP kernel and NTK, we initalize all parameters W1,1,8 and W2,1j with iid Gaussian (00,, 1). Letting n - oc and denoting L, x x// and (tu)veNo. we have
f kt(t) = JUENO (t.). and Og(t) = f (t.),) + (t.))t
(21)
vEVo
D-CNN.
The input space is X (6p-1) t C RPx xxxxxx xm where p is the patch size of the input convolutional layer, & is the filter size in hidden layers, I is the number of hidden convolution
5

---

Under review as a conference paper at ICLR 2022
layers and w is the spatial dimension of the penultimate layer. The total dimension of the input is == p k w, and the number of input nodes is |No| = k" w. Since the stride is equal to the filter size for all convolutional layers, the spatial dimension is reduced by factor of p in the first layer, factor of & by each hidden layer, and is reduced to 1 by the Flatten-Dense layer. Similar to S-CNNs, one can associate DAG to D-CNN. Briefly, the input layer has k- x w nodes and is reduced by a factor of k by each convolutional layer. The penultimate and output layers have w and 1 nodes, resp.
4 MAIN RESULTS
The goal is to obtain a precise charaterization of the relation between the eigenstructures of K / e and the DAG associated to the network's 's architectures in the large input dimension setting. As such we consider sequence of graphs G (g(4) deN where G(d) (Ni()) g(4)). We associate finite set of non-negative numbers Ag to G, which is called the shape parameters of g,
0 E Ag S [0 and |Agl < co.
(22)
We need several technical assumptions on 9 regarding the asymptotic shapes of G(4), which are summarized Assumption-g in Sec of the appendix. We list two of them which are the most crucial ones. (1) For each non-input node E AV44), there is au E Ag with deg(u)
d The
weight associated to the edge wv E g(d) is defined to be Tue = Qu (2) For each input node v, there is < ay E Ag so that the input dimension de ~ d=t Here a b means a/b E [1/C, CJ for some C' > 0 independent of d. The main purpose of making these two assumptions is to remove non-leading terms when computing the spectra.
We say 6 is semi-admissibe if, for all 2 1, the r-th derivative of ø= at zero is non-vanishing, i.e., (r(() (0) O. If, in addition, o² (0) (i.e., the activation is centered), then we say & is admissible. if 6² is (semi-)admissible. Note that if 6 is
An activation @ is
then Ø' is semi-admissible.
Assumption-0. We make the following assumptions on the activations. (a.) If u E And o. is the identity function. (b.) If u & No U {og)) ou is admissible. (c.) If u = og. du semi-admissible.
Next, we introduce the key concept which detines the spatial distance among nodes. It is the length of the minimum spanning tree (MST) of the nodes.
Definition (Spatial Index of Nodes). Let n. C CN((d) The spatial index of n. is defined to be
8(n) = min SCT))(
Σ Tuv
min gCTC
Σ
dog(u; T)a
(23)
WTEE(T)
MVEE(T)
where T < (d)) means T is sub- graph containing and deg(u; T) is the degree of u in T. By default, S(n) = 0 if n. contains only one or zero node.
Let t": " + I be a monomial, where r :N(aa) + NI We use n(r) = ENE : r # 0} to denote the support of and n((:og)) n((r U fog].
Definition (Spatial, Frequency and Learning Indices of t²). We say NIN is learmabee or learnable for short, if there is a common ancestor node u of n(r) such that &u is semii We use ((((d) = (r E NV1 r learnable). For r E slg(d)), the spatial index, frequency index and the learning index are defined to be,
8(r) = (==(((;));)))
F(r): =
Σ ToOk and B(r) = --(()-r--- ((r)+F(1 +(r), DEAD
(24)
resp. r & A(G(d)), we set 8(r) = F() 2(r) toc Let L(((d)) denote the sequence of learning indices in non-descending order, i.e.
() = (g(r) r e((())) ( =....Sr S
(25)

---

Under review as a conference paper at ICLR 2022
Finally, for each u E No let {Yr, (YraheNN (d..)) be the family of normalized spherical harmon- ics in Sx__ where N (duir) r) is the number of degree r spherical harmonics in Sd Define
(r,(E)= = II V vr.). 1= [LW))eEN E [N r)] = II [N(d,, rw)] aEAA%
(26)
for & (Ew) E X. The following is our main theorem. It describes connection between the architecture of network and the cigenstructure of its inducing kernels.
Theorem 1 (Eigenspace Restructuring). Assume Assumption-g and Assumption-ol We have the following eigen-decomposition for K Kighs or gia; For E, E X
K(E.n)
Σ Xc(r)
Σ (EN(dr)
Y (r,(E)Y,,1()) where >x(r) ~ 2(r)) if #0. (27)
1
Coupling with the observation in Eq. 2) Theorem implies that within t ~ d' amount of time for gradient flow, when d is sufficiently large, only the eigenfunctions Y with [(r) S r can be learned. By leveraging an analytical result from Mei al. (2021a) (Sec. Theorem 4), which says under certain regularity conditions on the eigenstructure, the corresponding kernel regression acts as a projection, Theorem
[ establishes connection between architectures and generalization bounds of NNGP kernel/NTK.
Let a be the uniform (product) probability measure on X' and denote IP(X) I o). For X C X and r & (()()), define the regressor and the projection operator to be
(x())(=)= = K(x,, x)) and Pzr(f)= = Σ Σ
(2)
r:(())>rEE((dr)
Theorem 2. Letg (g(4)) Jd, where each g(d) is DAG associated the D-CNN in Eq. 13 Let & ((g(t) be fixed. Let f E (x)) with Eof Then 0,
|Prr 1 = ca.e =dd,ellfll f1112t1
(28)
where ca. + 0 in probability as d + oc over X ~ old",
In words, with [d"] many training samples where & I(g("),, the NNGP kernel and the NTK are able to learn all Yr. with [(r) < r but not any eigenfunctions with C(r) > In Sec. C we show that the number of training samples can be reduced by factor of w if the readout layer Fattening is replaced by the global average pooling.
5 INTERPRETATION OF THE MAIN RESULTS
We say r' is the budget index if (1) (Finite Training Set) the training set size m ~ d', or (2) (Finite Compute Time) the training set X = X and the total number of training steps/time t &~ d".
MLPs and LRLF Interactions Fig. 1 (a). Each g(d) is linked list. Let be the input node. Clearly, we have d, = d, i.e., 02 and oa. = (since dog(u) u) = 1) for all other nodes u. As such
NY(()). (29) There isn't 't any spatial structure since 8(r) = Given a budget index r, the kernels can only learn span(Y Y r. r < , r NY(O)) Therefore, MLPs are good at modeling LRLF interactions.
alg(4)) N (()) (rr) |r|. S(r) 0. L(r) |r| and Lg = (Irl
S-CNNs and SRHF Interactions Fig. (b). For one-hidden layer convolutional networks, have d = p x 10 x w. (i.e. -= 0). The number of input nodes w = ddw and for each input node have d, = p ddp. We have Op + On 1. Since the activation function of the last layer is the identity function, there is no non-linear interactions between different patches and (g())) = (r I1
[((0), [n(r)]
1}. Therefore for (l(g()))
8(r) ase F(r) |r|ap,
Eg faw |rlap, E alg(())
(30)

---

Under review as a conference paper at ICLR 2022
Given budget index r, the learnable r are the ones (l((()) with
Ow + |r/p 1 + ((r) - 1) = |rl < (r-1)/a;
(31)
When Cpp (and thus Ow = 0), this S-CNN is essentially a shallow MLP and we have |r| < r. On the other hand, if ap is small (say Op 0.1), this network can model interactions with much higher frequencies, at the cost of giving up long-range interactions. Therefore, there a trade-off between space and frequency, and S-CNNs with small patch size are good at modeling SRHF interactions.
D-CNNs and Interterpolation Fig.
I (c). Recall that d = p kf x w. Let d d and W = d Then we have the constraint Op + Lax + Ohe 1. The learnable terms are the ones with
(()) (r)) S(r) |rlap.
(32)
D-CNNs simultaneously model interpolations (including the two ends) between LRLF and SRHE, i.e. MRMF interactions. Consider two extreme cases. (i.) |n(r)] = 1, i.e. there is an input node s.t. Yy = ||rl and thus the non-linear interaction happens within one patch. In this case, the length of the MST reaches its infimum S(r) au + Lay = 1 ap and Eq. (32) implies |r| (r apppp + which is exactly Eq. d31p. Thus D-CNNs can model SRHF interactions; see
Fig. (ii.) [n((r) = |r]. i.e. Tr 0 or 1 for all E -N6 Then 8(r) = [r| ap)) and Eq. implies []] < r, which is the constraint for MI.ps. particular, D-CNNs can model LRLFF
interactions; see Yg. By varying rr and then varying [n(r)] in [r) D-CNNs can model various
interpolating interactions between LRLF and SRHF.
HR-CNNs Extrapolations and Finer Interpolations Fig. (d). The resolution of the learning indices (() can be improved by decreasing Ctg. ap and increasing L accordingly. E.g., changing 2 Cg - 02/2 and doubling the number of convolutional layers accordingly, then the resolution of the range of gpatal/freqeencyllaanngg indices is doubled. This empowers the network to model finer-grained interpolating modes, and extrapolating modes. E.g.. the last equation in Eq. (31 becomes |r| < 1 2(r 1)/a, (almost doubles the upper bound of [r]) and the network can additionally model Ultra-Short-Ke Strra-SorttRaang-Uttte
Op + Oy
interactions (see Y; in Fig, 3 without sacrificing its expressivity, which isn't the case for S-CNNs due to the space-frequengy trade-off. We refer to such networks as high-resolution CNNs (HR-CM (NNs), For practical networks, e.g. ResNet (He et al., 2016), the filters/patches are already quite small and there isn't much room to reduce them. Equivalently, one increases the resolution of the input images instead, i.e. increasing d. From this point of view, HR-CNNs and, therefore, our theorems justify the additional performance gain from EfficientNet-type (Tan & Le 2019) of model scaling.
For more details regarding computing the learning index, see Sec. D
EXPERIMENTS
There are many practical consequences due to Theorem and Theorem 2 which are about the impact of architectures to learning generalization:
We focus on two of them
1. Order of Learning (Fig. D Green Arrow.) The order of learning is restructured from frequency- (MLPs) to suuce-and-freuuency--bee
(CNNs).
2. Learnability (Fig. I Cells under the budget line.) With the same budget index, MLP- Learnble ç DD-CNN-LLerrnalle &. HIR-CNN-Learnall Moreover, the set differences be- tween these learnable sets are captured as See 5
Overall, we excellent agreements between predictions from our theorems and experimental re- sults from both practical-size networks and kernel methods using NNGP/NT kernels, even when d 256 is moderate-size. We detail the setup, results, corrections, etc. for the experiments below.
Setup. Set dl = pd and the input X = ) C Re where p E N. Note that ap = 1/4. The task learning function Y E (x) by minimizing the MSE, where
Y=Y, + Y2 + Y +
(33)
8

---

Under review as a conference paper at ICLR 2022
and each eigenfunction Y; is normalized so that ||Y|l2 = ||X1///8= 1. The exact expressions of the functions can be found in Sec[D]
We optimize finite-width networks by SGD+MMomentun and infinite-width networks (NNGP and NTK) by kernel regression. We investigate three types of architectures: (1) Dense $4 a four hidden layer MIP; (2) Conv(p²)62, a "'dee" CNN with filter size/stride k p² and (3) Conv(p) (p) "HS"-CNI with filter size/stride k = p. See Fig. and Fig. 6 for a visualization of the associated DAGs, and Sec. [ for the code of the architectures. There an activation & in each hidden layer, which is chosen so that 6= is the Gaussian kernel. For the CNNs, the readout layer(s) is Flatten- Dense-Act-Dense We carefully chose the eigenfunctions {Y;} so that they cover wide range of space-frequency combinations (8(Y)) F(Y)) w.r.t. Conv(p) 04 Under (pnv(p) 04 the correspond- ing learning indices are S(YY,) 8(Y.) + SVY)) = 30p + iap = (3 + i)/4. For the learning indices of Y, under Conv(p²) or Dense 04 see the legends in Fig The purpose of doing so is to create "separation of learning" under Conv(p)** since in the large limit, learning Y; re- quires d(3+5)/4++ examples/SGDD steps. The relation between architectures and learning indices can be "visualized" in Fig. 2 for Y2, which is short-range-lowe frrane-low-freuuencyy ( (deg(Y2) = 2). Fig. (d) plots the test residual of Y2 training set size for NTK regression, as one example to showcase the relation among architectures, learning indices and generalization. See Fig. 6 in the appendix for other eigenfunctions.
In the experiments, the width/number of channels is set to 512 for all networks. We sample m, = 32 x 10240 (m. 10240) data points randomly from X as training (test) set with p = 4 and d 256. The SGD training configurations (batch size (=10240), learning rate (=1.), momentum (=0.9) etc.) are identical across architectures. To compute the kernels, we rely crucially on Neuralfangents NNvak et al. 2020) which is based on JAX (Bradbury et al. (018).
In Fig 3 for each eigenfunction Y., we plot (x, - Yx(x) 222 against I, where Yx () is the projection of the prediction onto Y; and L is either the training steps (SGD) training set size (kernels). The expectation is taken over the test set. The budget index = log(m;)/ log((d) = 2.28. As 256 (p- = far from the asymptotic limit, we expect r 2.28 being a soff cut-off between learnable and non- nea-leare indices. Although the theorems assume d. p - co, they do provide good predictions even when d and p are far from oc. We summarize several key observations below.
1. Dense 244 (Ind Row.) This architecture can capture all fow-frequ interactions (deg = 1, 1,2, Y1, Y2, Ys. Ys) but fail to learn deg 2 3 interactions, expected. For MLPs, making the network deeper won't 't improve its learnability much; see Fig. 7
2. Conv(p?) (2nd Row.) Learning curves of Y2/Y3s are separated from Y, because the spatial indices of them are different. Higher-frequency (deg = 3, 4) shorter-range interac-
tions (Y., Ys) become (partially) learnable, as L(Y)) = 4. L(Ye) 10
< r x 2.28.
3. (onv(p)* 04 (3rd Row). We see L(Y)) capture the order of learning very/reasonably well in the kernel/SGD setting. To test the ability of Conv(p) @4 in modeling ultra-short- hagg-uulra-high--feqeeee
interactions, we trace the learning progress of Y (deg( (Y;) = 5, L(Y:) = 2.) As expected, while other architectures completely fail to make progress, the NTK/NNGP of Conv(p) makes good progress and the SGD even completes the learn- ing process. Interestingly, Y Y learned faster than Y; in the kernel setting but slower in the SGD setting (even slower than L(Ys) 10), ). which is unexpected. We suspect it might be due to certain "implicit" effect of SGD. Further investigation is needed to understand it.
7 CONCLUSION
We establish precise relation among networks' architectures, eigenstructures of the inducing ker- nels, and generalization of the corresponding kernel machines. We show that deep convolutional networks restructure the eigenspaces of the inducing kernels, which empowers them to learn dra- matically broader class of functions, covering a wide range of space-frequency combinations. We believe our framework can be extended to study architectural inductive biases for other families of topologies, such as RNNs, GNNs, and self-attention. However, we have not covered the learning
www.:oooogRagg-ooowooorreee under Conv(p) 84 with L(Ys) 8/4 C(Y))

---

Under review as a conference paper at ICLR 2022
Pog ossion
Mupal: Rog ossion
MLP*)
SGD
0.4
0.5
15
05
1.5
0.5
15
0.5
Se/Traking SetS (eald
TugTTraning BerrannngSeBBae///aaa Sk58iea/
1st500 Stpps/oggt
3es Steps) (hggd
CNNpP) Regression
CNNip) NIK Regression
ONNip SGD
CHNIgry Tran
0.4
0.5
155
05
0.5
15
0.5
Be/Traking SotS
Aus/Tranin ng (e15l
Iaa8GD Steps/Maat0
Steps) (hoa
CN00gg NNGP Heggessiar
ChiNlPPM waggosson
ChiNa)"
ChMipj SGD Tran
0.5
620)
0.5
155
0.5
1.5
0.5
1.5
0.5
1.5
kal9GD Sleps)/lcatd)
3ay35D Stopo) (kog/))
Figure 3: Learning Dynamics vs Architectures vs Learning Indices. We plot the learning/training dynamics of each eigenfunction Y, From top to bottom: a 4ayer MLP, 2-layer CNN and a 4-layer CNN. From left to right: residual MSE (per eigenfunction) of NNGP/NTK regression, test/training MSE of SGD. The learning indices of Y, in each architecture is shown in the legends.
dynamics of SGD. In addition, it is of great interest and importance to study the combined effect of SGD and architectures the future.
REFERENCES
William Beckner. Inequalities in fourier analysis. Annals of Mathematics, 102(():159-182, 1975.
William Beckner. Sobolev incqualities, the poisson semigroup, and analysis on the sphere sn. Pro- ceedings of the National Academy of Sciences, 89(1 1):4816-4819, 1992.
Alberto Bietti. Approximation and learning with deep convolutional models: kernel perspective, 2021.
Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. arXiv preprint arXiv:2009.14397 2020.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman-Milne. JAX: composable transformations of Python+NumPy programs, 2018. URL/http://github httptp/://gggtuub..oommoggo////e
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances In Neural Information Processing Systems, 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10.1V 522066888.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1 180.00405 2018.
10

---

Under review as a conference paper at ICLR 2022
Arturo Deza, Qianli Liao, Andrzej Banburski, and Tomaso Poggio. Hierarchically compositional tasks and deep convolutional networks. arXiv preprint axXv:20006.33115 2020.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprini arXiv: 110:021810.02054, 2018.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizeed neural networks. In International Conference on Learning Representations, 2019.
Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse of dimen- sionality in convolutional teacher-student scenarios, 2021.
Christopher Frye and Costas J. Efthimiou. Spherical harmonics in p dimensions. 2012.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural networks. arXiv preprint arXiv: SXKi::906608899 2019.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension, 2020.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 1rXiv:1412.6572, 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Mare van Zee. Flax: A neural network library and ecosystem for JAX, 2020. URL http://github.. com wwt./////og///a//ooooo/////////e
Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. The surprising simplicity of the early- time learning dynamics of neural networks. arXiv preprint arXiv:2006. 140::9999..4999 2020.
Wei Huang, Weitao Du, and Richard Yi Da Xu. On the neural tangent kernel of deep networks with orthogonal initialization. arXiv preprint arXiv:2004.08667 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. arXiv preprint arXiv:1806.07577 2018.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836) 2020.
Alex Krizhevsky, Ilya Sutskever, and Geoffre E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yann Lecun. Generalization and network design strategies. In Connectionism in perspective. Else- vier, 1989.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Sam Schoenholz, Jeffrey Pennington, and Jascha Sohl- dickstein. Deep neural networks gaussian processes. In International Conference on Learning Representations, 2018
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. In Advances in Neural Information Processing Systems, 2019.
Zhiyuan Li. Yi Zhang, and Sanjeev Arora. Why convolutional nets more sample-efficient than fully-connected nets? CoRR, abs/2010.08515, 2020. URL https: http://aaaxxi...or/b///0000 08515

---

Under review as a conference paper at ICLR 2022
Eran Malach and Shai Shalev-Shwartz Computational separation between convolutional and fully- connected networks. CoRR, abs/2010.01369, 2020. URL
01369
Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018.
Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Generalization error of random fea- tures and kernel methods: hypercontractivity and kernel matrix concentration. arXiv preprint arXiv:2101. 10588, 2021a.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. arXiv preprint arXiv:2102.13219 2021b.
Ashley Montanaro. Some applications of hypercontractive inequalities in quantum information the- ory. Journal of Mathematical Physics, 53(12): 1222066,, 2012.
Grégoire Montavon, Wojciech Samek, and Klaus-Robert Müller. Methods for interpreting and un- derstanding deep neural networks. Digital Signal Processing, 73:1-15, 2018
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L. Edelman, Fred Zhang, and Boaz Barak. SGD on neural networks learns functions of increasing complexity. CoRR, abs/1905, 1604, 2019. URL
11604
Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang, Daniel Abolafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many chan- nels are gaussian processes. In International Conference on Learning Representations, 2019a.
URL
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A. Abo- lafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. In International Conference on Learning Representations, 2019b.
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks python. In International Conference on Learning Representations, 2020. URL httpps:/giii //tpthbggttbbbt..// com/ google/neural--ann tangents
Yaniv Ovadia, Emily Fertig, J. Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua V. Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. In NeurlPS, 2019.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Expo- nential expressivity deep neural networks through transient chaos. Advances In Neural Information Processing Systems, 2016.
Meyer Scetbon and Zaid Harchaoui. Harmonic decompositions of convolutional networks. In Inter- national Conference Machine Learning, pp. 5522-8532. PMLR, 2020.
Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep information propagation. International Conference on Learning Representations, 2017.
Andrew W Senior, Richard Evans, John Jumper, James Kirkpatrick, Laurent Sifree, Tim Green, Chongli Qin. Augustin Židek, Alexander WR Nelson, Alex Bridgland, et al. Improved protein structure prediction using potentials from deep learning. Nature, 577(7792):70--710, 2020.
Vaishaal Shankar, Alex Chengyu Fang, Wenshuo Guo, Sara Fridovich-Keit Ludwig Schmidt, and Benjamin Recht. Neural kernels without tangents. In International Conference Machine Learning, 2020.
Jonathan
12

---

Under review as a conference paper at ICLR 2022
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489-489, 489, 2016.
Jascha Sohl-Dickstein, Roman Novak, Samuel S. Schoenholz, and Jachoon Lee. On the infinite width limit of neural networks with a standard parameterization, 2020.
Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural net- works. In International Conference on Machine Learning, pp. 6105-6114, PMLR, 2019.
M. Alex O. Vasilescu, Eric Kim, and Xiao S. Zeng. Causalx: Causal explanations and block multi- linear factor analysis, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arXiv:1906003762, 2017.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1r1iv:101..302,, 2010.
Lechao Xiao and Jeffrey Pennington. What breaks the curse of dimensionality in deep learning?,
hwtp://wwww///../////////////// 2021. URL /ttpo///w..///////e///////////ee
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffiey Pennington. Dynamical isometry and mean field theory of cnns: How train 10,000-layer vanilla con- volutional neural networks. In International Conference on Machine Learning, pp. 5393-5402, 2018.
Greg Yang and Edward J Hu. Feature learning in infinite-width neural networks. arXiv preprint 1rX1v:2011.14522, 2020.
Greg Yang and Hadi Salman. A fine-grained spectral perspective neural networks, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
13

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL RELATED WORK
Biett (021) studies the approximation and learning properties of CNN kernels via the lens of RKHS. Impressively, they demonstrate that a 2-layer CNN kernel can reach 88.3% validation ac-
curacy on CIFAR-IO, matching the performance of 10-layer Myrtle kernel Shankar et al. (2020).
Malach & Shalev-Shwartz (2020) and Li al. (2020) study the algorithmic benefits of shallow
CNNs and show that they outperform MLPs in certain tasks. Xiao & Pennington (202T) and Favero al. (202T) study the benefits of locality in S-CNNs and argue that locality is the key ingredient to defeat the curse of dimensionality. MMi et al. (2021b) and several papers mentioned above study the benefits of pooling in (S-)CNNS terms of data efficiency. Their conclusion is similar to that of Theorem 4 (b): pooling improves data efficiency by factor of the pooling size. In addition, we show that (Theorem 4 (a)) pooling does not improve training efficiency for D-CNNs, extending result from Xiao & Pennington (22TI) which concerns S-CNNs. Finally, Scetbon & Harchaoui (2220) also study the eigenstructures of certain CNN kernels without pooling. Their kernels can be considered particular case of the NNGP kernels, where the associated networks have only one convolutional layer and multiple dense layers. The key contribution that sets the current work apart from existing work is precise mathematical characterization of the fundamental role of architec- tures in (infinite-width) networks through space- freeuniyyy analysis.
B A TOY EXAMPLE AND MOTIVATION
In this section, we provide toy example to help understand the motivation and ideas of the paper. Let's consider learning the following polynomials in S fo E Rd, ||0||| = 1} using (in finfiinie- width neural networks and for concreteness we have set d = 10:
(x) = xg, (2 = Tg fa(x) = Io [1(x) = x6 , [b(x) = x22332 (34)
Which architectures (e.g. MLPs, CNNs) can efficiently learn fa or the sum of f.? More precisely, (I) we have sufficiently amount of training data, how much time (compute) is required to learn fi for given architecture? (2) Alternatively, if we have sufficiently amount of compute, how much data is needed to learn fi? To answer these questions, one crucial step is to provide a meaningful definition of "learning complexity" of function fi under an architecture M. Denote this complexity associ- ated to compute and to data by (c(fi and CD(f:: M). resp. With such the complexity properly defined, the questions are reduced solving the min-max problem min,y max; (Ca if the task is, e.g, to learn the sum of fi-
Let's focus on the complexity. For fihnite-widthh MLPs, aka, inner product kernels, it well- known that they have the inductive biases (Yang & Salman (220)] Ghorbani et al.) (020) (known as the frequency biases) that the model prioritizes learning low-frequency modes (i.e., low degree polynomials) over high-frequency modes. In addition, the models require ~ d" many data points to learn any degree r polynomials in Rdd The frequency biases of MLPs are the consequence of the fact that the eigenspaces of inner product kernels are structured based only on frequencies. Specific to example, for MLP, the order of learning is fı/ f2. fa/fs/ fa and it requires about 10/ 10/10?, 10 110 many data points to learn the functions. Clearly, the model is very inefficient in learning f4, the high-frequency modes.
To improve the learning efficiency, must take the modality of the task into account, which is overlooked by MLPs. We observe that: (1) although of high frequency, f4 depends only on two con- secutive terms mhg and 17, which are spatially close; (2) in contrast, fa(x) = Wo2r is of low frequency but the spatial distance between the two interaction terms 2i and 2g are "far" from each other; (3) the function fs (xx) Z233345 is somewhere in-between: the order of interaction is 3 (lower than that of fa) and the spatial distance (not yet defined) among interaction terms is conceptually "closer" than that of fx) Tg but "farther" than that of fs- Using the terminologies from the introduction, the functions f2/ fa/ fa/fs//////////// fa model interactions of types: Short- Seagguuenny/SSoot-R-------iieeee
Range By Range we mean the distance among interaction terms and by Frequency we mean the order(=degree) of in- teractions. Clearly, the MLPs are inefficient since they totally ignore the "spatial structure" of the functions. As such, a good architecture must balance the "spatial structure" and the "frequency structure" of the functions. For the same reason, a good complexity measure must (1) be able to capture both the frequency of the functions and the spatial distance among interaction terms; (2)
www-Frequency/Median--PR
14

---

Under review as a conference paper at ICLR 2022
be able to precisely characterize the data and the computation efficiency of learning and their de- pendence on architectures. The learning index mentioned in the introduction satisfies these two conditions. It is the sum of the frequency index and the spatial index. The former measures the order (=degree=frequenccy) of interactions, which depends on how the network partitions the input into patches. The latter measures the spatial distance among the interaction terms, which depends how the network organizes these patches hierarchically. Later we show that, in the high-dimensional setting, the learning index provides sharp characterization for the learnability of cigenfunctions, and certain CNNs can perfectly balance the learning of fs and fa, i.e., informally
CcyD CNN) (fa CNN) R CC/D(f222 MLP) << Cc/p(fs: MLP)
(35)
See Fig. in the experiment section for more details.
C GLOBAL AVERAGE POOLING (GAP) VS FLATTENING
In this section, we compare two readout strategies for CNNs: GAP and Flatten
C.I
DATA.
First, let's state a theorem regarding training efficiency in the sanniie-rrriiin-g--------------- time regime, which follows directly from the same arguments in Sec. _ The theorem requires knowing only the cigenvalues of the kernels.
Let FF: (x( (x) be the solution operator to the kernel descent h K(h f) with initial value 0 0, i.e. hr FJ) = (Id )- Then we have for ( ~ d' F, R0 Per
Theorem 3. Assume Assumption-G and Assumption- and K. Kgun or θ gin. Letr & ((g()) and d". Then for 0 < < inf(/r Fl : F (()())) and f (x) with Eg f = 0 we have
(F.(Pe))) P Per 1Peelll and [FF((s - P3rSI 2 e -d" P (36)
for d sufficiently large.
In words, in the fraiite-training-iee maaniing-dtt--iiee Mata--inite-trainin time regime, within d" amount of time only the eigenfunctions Y r
Yr with L(r) < r are learnable.
C.2 GAP VS FLATTENING.
Let a CNN with and without global average pooling (GAP) be defined as [Ippr]] > [Conv(p)-Aci] > [Conv(k)-Acrt] + [GAP] - [Dense]
CNN+GAP
(37)
CNN+Flatten
[mppr]] - [Com(p))-ca > [Comv(k)) (t)-Acr] - [Flatten] - [Dense]
(38)
resp. Note that there isn't any activation after the GAP/Flatten layer. The DAGs associated to CNN+ GAP and CNN+Flatten are identical, and the associated kernel and network computations in each layer are also identical but the last layer, see Sec. [or more details. Our last theorem states that the GAP improves the data efficiency by a factor of w, the window size of the pooling, but trrraiiinn-dat--iiie--rrainntti
does not improve the training efficiency in the former is due to the dimension reduction effect of GAP in the eigenspaces and the latter is due to the fact that the GAP layer does not change the eigenvalues of the associated eigenspaces.
regime. The
Let Ksym = Kym or Osym be the NNGP kernel or NTK associated to Eq. (37 and (X') S (P()) be the subspace of "translation-invariaa" functions, whose co-dimension is w. Let Sym pSym and Rym be the solution operator, projection operator and regressor associated to KSym resp. Theorem (Informal). For the architectures defined as in by Eq. (37). we have
(a) Theorem 3 holds with L (2)), IF and P replaced by L3ym (X'), Sym and Sym resp.
(b) Eq. 28 holds with IP))). R and P replaced by (X), RSm and pSym, resp and with X la [a] under the assumptions that all activations in the hidden layers are poly-admissible.
15

---

Under review as a conference paper at ICLR 2022
Remark 1. Several remarks are in order.
1. In terms of order of learning, our results say that (infinite-width) neural networks pro- gressively learn more complex functions, where complexity is defined to be the learning index C(r). This is consistent with the empirical observation from Nakkiran et al. 2019) Regardless of architectures (MLPs vs CNNs), linear functions have the smallest learn- ing i C(r) 1 and are always learned first, which was first proved in Hu et al. (2020) for MLPs. After learning the linear functions, the learning dynamics of MLPs and CNNs diverge. MLPs will start learn quadratic functions (L(r) = 2). then cu- bic bic functions (L(r) = 3) and so on. While for CNNs, L(r) can be fractional numbers (e.g. C(r) = 5/4, 6/4) and possible for the network to learn higher order functions before lower order functions. See Sec SecDaand Sec. ofor more details.
2. By NTK-style convergent arguments (e.g.. Du et al. (219)), the above kernel regression results could be extended to the ever-parameterized network setting as long the learning rate of gradient descent is small and the number of channels is sufficiently large (polyno- mially in d (Huang et al. (0200).
3. Theorem 4 states that CNN+GAP better than CNN+ in terms of data efficiency but not training efficiency. In particular, when the dataset size is sufficiently large, CNN+GA and CNN+ MNN++llaten Flatten perform equally well. Therefore, in the large (infinite) data set regime, CNN+Flatten may be preferable since the associated function class is less restricted.
C.3 EXPERIMENTAL RESULTS: GAP VS FLATTEN.
We compare the SGD learning dynamics of two convolutional architectures: Conv(p) 83 -Flttenn and Conv(p) 19333,383.3 -GA.. Both networks have three convolutional layers with filter size and stride equal to p. The spatial dimension is reduced to p after the convolutional layers. The only difference that the architecture Conv(p) (an Flatten ( Conv(p) -GAP) uses Flatten-Dense (GAP-Dense) to map the penultimate layer to the logit layer.
The experimental setup is almost the same as that of Sec. except the eigenfunctions {Y:} are chosen to be in the RKHS of the NNGP kemel/NTK of Conv (p) 23 -GAP and thus of Conv @3_ -Flateen i.e., they are shifting-invariant (the invariant group is of order p). Moreover, we still have (YY))
(i + 3)/4. For each Y, we plot the validation MSE of the residual vs SGD steps in Fig, 4 Overall, the predictions from Theorem 4 gives excellent agreement with the empirical result. With training set size m = 32 x 10240, the residuals of Y; for GAP and Flatten are almost indistinguishable from each other for S (recall that SYYa)) = 9/4 2.25 < r R 2.28). However, when the dataset size (r ~ 2.28) is relatively small compared to the learning index (L((Y>) 2.5), GAP outperforms Flatten in learning Y?
To test the robustness of the prediction from Theorem 4 (a) more practical datasets and models. we perform an additional experiment on ImageNet (Deng et al. 2009) using ResNet (He et all 2016). We compare the performance of the original ResNet50, denoted by ResNet50-GAP, and modified version CosNet50-Flatteen in which the GAP readout layer is replaced by Flatten. We use the ImageNet codebase from FLAXX2 Heek et al. 2020 In order see how the performance difference between ResNet50-GAP and ResNet50-Flatten evolves as the training set size increases, we make a scaling plot, namely, we vary the training set sizes m, = [m x 2/1 for i = O...., 11, where
1281167 is the total number of images in the training are trained for 150 epochs with batch size 128. We plot the validation accuracy and loss (averaged over 3 runs) as a function of training set size my in Fig. Overall, we that the performance gap between Nes00-AGG and ResNet50-Flatten shrink substantially as the training set size increases. E.g, using 1/8 of the training set (i.e. = 6). the top accuracy between the two is 19.3% (57.7% GAP vs 38.4% Flatten). However, with the whole training set (i.c., mo), this gap is reduced to 2% (76.5% GAP vs 74.5% Flatten). To demonstrate the robustness of this trend, we additionally generate the same plots for ResNet34 and ResNet101; see Fig. 8 in Sec.
of ImageNet. The networks
Ignoring the constant functions. https://githubb. www.uuub.com///g/ hwtp:/ooooooooiiiioooooo http:///wwoooooooaaa//a//eeeaaee
Standard data- auttemttmmentiionn is applied for each i; see ipput_pppplll,
16

---

Under review as a conference paper at ICLR 2022
Valid Loss: GAP vs Flatten
Y1:GAP
Y1:Flatian
MSE
0.2
0.0
1.25
2.25
log(SGD Steps) /log(d)
Figure 4: Learning Dynamics: GAP vs Flatten. We plot the validation MSE of residual of each Y, (left > right: i 7) for GAP (Solid lines) and Flatten (Dashed lines). The mean/std in each curve is obtained by 5 random initializations. Clearly, the residual dynamics of GAP and Flatten almost indistinguishable for Y, with i S 6. However, GAP outperforms Flatten when learning Y-.
Accuracy: GAP Flatten
Loss: GAP Flatten
ResNet50-GAP
ResNet50
Top Acc ImageNet
ResNel800Flatten
Validation Cross-Entropy
ResNet500Flatlen
0.2
Training Set Size
Training Set Size
Figure 5: ResNet50-GAP ResNet50-Flatten As the training size increases the performance
(accuracy and loss) gap between the two shrinks.
D DAGS, EIGENFUNCTIONS, SPATIAL INDEX, AND FREQUENCY INDEX.
In this section, we provide more details regarding the DAGs and the eigenfunctions used in the experiments, and how the spatial, frequency and learning indices are computed.
Let (zp-1)"* C R² the input space, where d = p* is the input dimension. We use æ (xn)kE(p" E (Sp-1)²" to denote input (an image), where & = [K k2, Ka, ka] E [p] In addition, treat [p]*
group (i.e. with circular boundaries) and let e₁ [1,0, 0, 0], eq [0, 1,0,0, Eg = [0. 0, 1, and e₁ = [0, O, O, 1] be a set of generator/basis of the group. Note that each input mg is partitioned into pd many patches: (rr As.: k1, Kz kig E [p])-
17

---

Under review as a conference paper at ICLR 2022
The eigenfunctions used in the experiments and the associated space/frequency indices (will be explained momentarily) are given as follow
Eigenfunction
degree
Space/Freq Index
MLP
CNN(p²)
CNN
Y1(x)= = Σ
(1) *
0/1
1
1
3 1
2 2
4 4
1e(p-11*
Y2(x) Σ
Ck
(2) Dkte
2
0/2
1 2
3
3,2
2 2
4
kc(p-114
Ys(x) = Σ
k
(3)
T ek Iktes
2
0/2
2 2
1 2
4 2
4 4
kE(p-1]"
Ya(x)= Σ
(4)
2h t
3
0/3
2 2
1 3
4 3
4
kE(p-114
Yz(a) Σ
Ck
(5")
2 xkee)
0/5
2 2
1 5
3 3,5
4
kE(p-114
Ys(x)= =
Σ
k Tgtktes
2
0/2
2 2
4 4
6 2
2 2
kc(p-11'
Yo(æ) Σ
Ck T2 (30k x1))
(6)
0/4
1 4
5 4
2 2
1c(p-111
Yr(x)= =
Σ
(7) Ck Tk oo- Tktes - w estte)
0/4
1 4
7
7/4
6 4
2
2
kJ(p-1]4
Each (eigen)function Y; is linear combination of basis eigenfunction of the same type, in the sense they have the same eigenvalue and the same spatialftequencyllamiin indices. The coefficients aB are first sampled from standard Gaussians iid and then multiplied by an i-dependent constant so that Y; has unit norm In the experiments, p chosen to be and the target defined to be sum of them
Y Σ Yi
(39)
Since they are orthogonal each other, ||||//8 || 1 where the L-2norm is taken over the uniform distribution on (Sp-1)²², In the experiment when we compare Flatten and GAP Fig., set all ck to be the same (note that also remove Ys from the target function), so that the functions are learnable by convolutional networks with a GAP readout layer.
(i)
We compare three architectures. Fig. 6 Column (a) MLP@4 (four-layer) MLP, the most coarse architecture used in the paper. Fig. 6 volutional layers with filter size/stride equal y²a Fig. 6 Column (c), CNN(p) "HR"-CNN, the finest architecture used in the experiments, that contains four convolutional layers with filter size/stride equal to p. In all experiments except the one in Fig. we use Flatten as the readout layer for the convolutional networks and add a Act-Dense layer after Flatten to improve the expressivity of the function class. However, in the Flatten vs GAP experiments, Fig. 4 we have only one dense layer after GAP//latten.
Column (b), CNN 2NN(22) a D"D"-CNN that contains two con-
We show how compute the frequency index, the spatial index and the learning index through three examples. We focus Yo Y Yī which have degree 2 / 5, resp. The indices of other eigenfunctions can be computed using the same approach. We use Dashed Lines to represent either input node node in the first-hidden layer or edge associated to dense
an edge connecting layer. In either case, the corresponding output node of the edge has degree O(1) and thus the weights always O. Only Solid Lines relevant in computing the spatial
(of the DAGs) of such edges index. Since each Y; is a linear combination of basis eigenfunctions of the same type, we only need to compute the indices of one component. We use the k O component, which corresponds to the
'In experiments, they normalized over the test
18

---

Under review as a conference paper at ICLR 2022
colored path in each DAG. Recall that p 4, d p² 256 and m. = 32 x 10240 ~ d2.28 (training set size), ie. the budget index is roughly r = 2.28.
(a.) MLP Column (a) Fig.
The NTK and NNGP kernels are inner product kernels and the associated DAGS linked lists. The corresponding DAG has only one input node whose dimension is equal to d = p². The spatial index is always 0 since the degree of each hidden node is (since 1 d') and the frequency index is equal to the degree of the eigenfunctions. Thus 2(Y2) -{Yss)
2 and E(Y;) = 5. Changing the number of layers won't change the learning indices. In sum, learning Y2/Y g using infinite- width MLP requires d² /d2 /d many samples /SGD steps. Clearly, Yg is completely unlearnable as 2.28 << 5. In the MSE plot Y; (5-th row in Fig. 6). the Red Lines does not make any progress
(b.) CNN(p2) 282 Column (b) Fig. 6 The input image is partitioned into p² patches and each patch has dimension p². The second layer of the DAG has p² many nodes, each node represents one pixel (with many channels) in the first hidden layer of a finite-width Con- vNet. After one more convolutional layer with filter size/stride p². the number of node (pixel) is reduced to one. The remaining part of the DAG is essentially a linked list (Dashed Line) with length equal
which corresponds to the Act-Dense layer. The frequency index (Y2)) = 2 = 1. This is because the degree of Y2 is 2 and the input dimension of node is p² d!/2 The spatial index is equal to 1/2, since the mini- mum tree containing FgEk+e has only one non-zero edge (Solid Lines) whose weight is equal to 1/2 (since the degree of the output node is p² = dd/2); see the colored paths in Fig. Column (b). Therefore the learning index of ((Y2) = 1 1/2 3/2. Sim- ilarly S (Ya)) = 1 + 1/2 3/2, as the term Tk+ez are lying in the same patch of size p² for all k. and I(Y;) 5/2 + 1/2 = 3. In sum, learning "2/Ya/Y; using indinite-width C requires d=.5* /dl.5 /dst many samples /SGD steps. While neither infinite-width CNN(p") nor MLP distinguishes Y2 from Ya, CNN(p2)62 does improve the learning efficiency: de + d Note that Yg is still unlearnable as r = 2.28 < 3 = SY(Y)). In the MSE plot Yg (5-th row in Fig. 6). the Orange Line does not make any progress.
(c.) CN 04 Column (c) Fig. 6 The input image is partitioned into pd patches and each
patch has dimension p. The recond/tard/fouurt//ouuuu layer of the DAG has p² /p2 122//// /p/1 many nodes. The frequency indices are: F(Y²) = :(Ys) 2 = 1122 and (Y;))
54 5/4. This is because the size of input nodes is reduced to p d//4, Unlike the above cases, the spatial indices become different. The two interacting terms in Fg and the three interacting terms in Tk+ 2k+2c ( = are in the same input node while the two interacting terms in Tk+e, Tk+e, and are in two different input nodes. As consequence, the minimum spanning tree (MST) that contains 3& and Tx+e, and the one contains Ik. Ekte, and Ik+ze, are the same. They have 3 solid lines. However, the MST containing Tk+ey and Økte; has 4 solid lines. Therefore 8(Y,) 8(Y;) = 3 1 and s(Ys) = }. As such, 2(Y2) = 3. I(Ys) = J and I(Y;) = 8 In sum, learning /Yy using infinite-width CNN(p) @1 requires d1.25 / dd..5 / da many samples /SGD steps, resp. Now L(Y;) = 2. < 2.28 and in the MSE plot Yg (5-th row in Fig. 6) the Blue Line does make significant progress (the MSE reduced to 0.2.)
4
4.
19

---

Under review as a conference paper at ICLR 2022
2010- Se deghrjal
Uni Frequancy 2211-21--5 1
Oupu
Nostal myod
Ore can
flange 21
ure Hoccual Tearing
2010 4 destrisu
Shott stange Love Prequenay 211o-q--0
Oupu
Spacil
Spatil
- drgff
Rardual Thaning
Spakaal
UR Gioc Hange Hig--igh Fraguroy (YC
US2 Bardual Thaning
Reequnog
deghtquu
Unissoog Ranges 2112
Proguenge
Spaiaal
Spalial ou!
1 degivpss
Long Ranges hwwpee---i----aaaeeeeeeee Fae-uaaan 02%)-
Ust Paridal Thenno Dee
Oupanass 2204
USi Range High- Erqqunoy 42r
Prequeney 8--0
Spalil
Spatal oud
Spalil o-1
(a) MLP
(b) CNN(p2) 02
(c) CNN 94
(d) MSE Residual
Figure 6: Eigenfunction vs Learning Index Architecture/DAG. Rows: cigenfunctions Y; with various space- frequency combinations. Columns: DAGs associated to (I) a four-layer MLP: (b) CNN(p2)62 D"DD--CN; (c) CNN(p)*4 "HR"-CNN. Column (d) is the MSE, function of training set size (X-axis), of the residual the corresponding eigenfunction Y, obtained by NTK- regression. The colored path in each DAG corresponds the minimum spanning that contains all interacting terms in the & = 0 component of Y.
20

---

Under review as a conference paper at ICLR 2022
MLP: vs Layers (NTK)
CNN: vs 4 Layers (NTK)
0.8
0.8
0.6
0.6
MSE
0.4
0.2
0.2
Layor
Layay
4 Layer
4 Layer
0.0
0.0
1.5
1.5
log (Taainigg Set Sizee) /lo(d)
log( logaTninng Set Sizz))/oo(((
MLP: Layers (SGD)
CNN: 1 Layers (SGD)
0.8
0.8
Layer
4 Layer
0.6
0.6
MSE/8
MSE
0.4
0.4
LLyyer
0.2
4- -Layer
MSE/8
0.0
0.0
0.5
1.5
0.5
1.5
IoG Steps)/log(d)
log(SGD Steps)/log((
Figure 7: MIPs do not benefits from having more layers. We plot the learning dynamics vs training size / SGD steps for each eigenfunction Y.. Top: NTK regression and bottom: SGD + Momentum. Left: MLP; right: CNN. Dashed lines Solid lines correspond to one-hidden/four- hidden layer networks. For both finite-width SGD training and infnnit-wiidh kernel regression, having more layers does not essentially improve performance of a MLP. This is in stark contrast to CNNs (right). By having more layers, the eigenstuctures the kernels are refined.
E FIGURE ZoO
E. MLPs: DEPTH & HIERARCHY
We compare a one hidden layer MLP and a four hidden layer MLP in Fig. 7 Unlike CNNs, increas- ing the number of layers does not improve the performance of MLPs much for both NTK regression and SGD. This consistent with a theoretical result from Bietti & Bach (2020), which says the NTKs of Relu MLPs are essentially the same for any depth.
E.2 IMAGENET PLOTS
21

---

Under review as a conference paper at ICLR 2022
Accuracy: GAP Flatten
Loss: GAP Flatten
ResNet34-GAP
ReaNet34-GAP ResNat34- Flattinn
Validation Cross-Entropy
Top Aco ImageNet
Reshiel34-Faatenn
0.6
0.2
Training Set Size
Training Set Size
Accuracy: GAP Flatten
Loss: GAP Flatten
0.8
ResNett01-GAA
Validation Cross-Entropy EessEEnropy
ReaNet101-GAF
Top Acc ImageNet
101-Fatto
0.6
0.4
2-
0.2
Training Set Size
Training Set Size
Figure 8: ResNet-GAP vs ResNet-Flatten. As the training set size increases the performance (accuracy and loss) gap between the two shrinks substantially. Top/bottom ResNet34/esNet1011
F ARCHITECTURE SPECIFICATIONS
In this section, we provide the details of the architectures used in the experiments.
G ASSUMPTIONS
Assumption-G. Let (g(d))a. There are absolute constants c, C > 0 such that
(a.) For each non-input node u E Add), there is a, E Ag such that od < deg(u) & Cd
(40)
For each edge g(d), its weight is defined to be Wav au.
(b.) For each inpul node there are d, E N and O < Or E Ag such that
dd S d, S Cd and Σ a a,=1.
(41)
eEAC!
(c.) Let A/ fu Eo vo(d) layer. We assume that for every u E ((()) Oa = 0 and all children of u are input nodes.
g(d)} be the collection of nodes in the first hidden
(d.) For every v E AVd Hu: wo E ((d)) S C. Moreover, the number of layers uniformly bounded, namely, for any node u, any path from u to contains at most C' edges.
The first two assumptions help to create spectral gaps between eigenspaces. When d is not large, "finite-widee effect is longer negligible and we expect that the spectra decay more smoothly. Assumption (c.) says there is no "skip" connections from the input layer to other layers except to the first hidden layer.
22

---

Under review as a conference paper at ICLR 2022
from neural_tangents import stax
MLP(width=2048, depth=1, W_std=0.5, activation=stax.Bb layers
for in range(depth):
layers += [stax (wisthwidth, W_std=W_std), activation]
layers += [stax. [stax. Dense(1)]
return stax. (*lyer(*l
def cNN(width=512, ksize=4, depth=1, W_std=0.5, activation=sta Rbf(), readout=stax (albbut-stxx.Flateenn))
roc_aftee_readouttttue):
layers
conv_op stax. Convivih,,, (ksize, 1), strides=(ksize, 1), W_std=W_std, Bodding="VALID" for in range(depth):
layers += [conv_op, activation]
layers [readout]
if act_after_readout:
layers [stax. (widh W_stdoW_std), activation]
layers += [stax. Dense(1)]
return stax. serial()layers)
p 4 input shape: (-1, p**4, 1, 1)
S_MLP MLP(depth=1) t Shallow MLP
D_MLP MLP(depth=4) Deep
S_CNN CNN(ksize=p, depth=1, act_after_readotteallss. Shallow CNN
# One layer CNN with additional activation-dense layer
J_CNN_plus_Act oW(ksizo=p, depth=1, act__atter_readuttti
D_CNN C. depth=2) Deep CNN
HR_CNN CNN(ksize-p, depth#4) a High-resolution CNN
* High-resolution with global average pooling readout
IR_CNN_GAP= CNN(ksize=p, depth=4, readout=stax Glw.allvgooolll), readutsstax..oobllyyoo00),,
act_aette_reddoutfalll
# High-resolution with flattening readout
IR__CN_Flatten CNN(ksizerp, depth=4, act_after_readout-ie
Listing 1: Definitions of MIPs, S-CNN, D-CNN and HR-CNN used in the experiments. The ar-
chitectures used in the experiments of Fig. are defined as follows. De = MLP, Conv (p" 2) 82 D CNN, Conv(p) 04 HR CNN. The one layer MLP and one layer CNN used in Fig. S_MLP and BL_CN__pluss Acct, resp.
H PROOF OF THE EIGENSPACE RESTRUCTURING THEOREM.
Lemma 1. Let Nod Then
Kg(O), Og(0)=
(42)
for + for large enough,
(0), 0/77 (0) 8(()) and ||<]11| b0: 110 $ 8(
(43)
23

---

Under review as a conference paper at ICLR 2022
Proof. Recall that the recursion formulas for H and è are
(t(() = 6% (FrAEEE H.,(t)
(44)
(t) = 3%. (f JeuuvE Hhr(t)
(Ho(()) + (t())
(45)
For convenience, define H. θ, H as follows
(t) = of JONIEE (t)
(46)
(t) = f (t
(47)
(t, Pu (t).
(48)
Note that
(t) = 07 (t) and @ =
The equalities HC, (0) = .., (0) = 0 follow easily from recursion and the fact (0) = for all E NVO.
We induct the tuple (h, |r]), where h the number of hidden layers in g(d) and |r| is the total degree of r. We begin with the proof of the NNGP kernel K.
Base Case 1: |r| 1 and h 2 0 is any integer. Let E No be such that r eu, where Lew
the standard basis. Then
ie., Kg(t)=
Σ
II
deg(v) (t)
Σ
II
d Hx
Pathe((u-oog #Epath
pahe #Epath
(49)
Here P(u + u') represents the set of paths from u to u'. By Assumption-G and Assumption- [P(u + ag)l is uniformly bounded and (0) > 0 for all hidden nodes v. Therefore
Üt. Kg(
Σ PathEP(u-to))
d Ee oz K. (0)
Σ
d Eeeach (0
pathe((u-to))
d' Enepph ay
max PathEP(u-tog)
d 8(c.) d-B1e B(m)
In the above, we have used (0) (which due to (0( 0.) The second estimate ||O,,, koo I 8()( follows from j3; (1)) I.
Base Case II: h and |r| nodes are linked to the output node og. The case when the activation dog is the identity function is obvious and we assume Dog admissible.
any number. Note that g(d) has no hidden layer and all input
(freNce
Kt)
deg(og) ((rl)
t
This implies Eq. (43 since 8(r) = 0, deg(og) S by Assumption-G and &%g (rD( > 0 by Assumption-o.
Induction: |r| 2 2, 2 and r E (l())))). We only prove the first estimate in Eq. 43 since the
other one be proved similarly. WI.GG, assume oog not the identity function and hence is
24

---

Under review as a conference paper at ICLR 2022
semi-admissible.
Let E ~/x0 be such that ru 2 1 and denote ev. Then
37 1-
(E( 1- = Σ deg(og)) (Koo
(50)
oGVEE T0
deg(og)
Hoog (t) tu (t) t=
(51)
OGNER
of ("xx,11
Σ
(52)
OGUEE P1+PE=
0e" Xx
Σ
d (0n
(53)
AGUER FI+F==F
0g 30
sup aguEg
sup P1
d (8o + +8(((f++ew:v1)
(54)
P1
0 % 20
We have applied induction twice in Eq. 52 one obtain the estimate 0. (0) d 6(+)) (with |P/| < |r| and d% semi-admissible) and one to 0. =e (t) ~ d d=8(n(Fate..:))) in which the sub- graph with v as the output node has depth at most (/ - 1). The last line follows from that both the cardinality of the tuple (P1, (2) with F1, F22 0 and #1 f22 and the cardinality of (N1 with 0gu E & and OfHH, + O are finite and independent of d. From the definition of MST, it is clear that for all F2)
8(F1) + aag + 8(n(F2 e.; 2 8(r1) + 8(F2 e..) 2 8(r)
(55)
remains to show that there exists at least one pair (F1, F2) such that the above can be an equality.
Let T S g(d) be a MST containing all nodes in n(r). If og has only one child u in T, then we choose and notice that
8(fi) + ang + 8(n(F22 E.; 0 S(r2 e..) 8(r)
(56)
since 8(F,) = and 12 + en = r. Else, T contains at least two children and therefore at least two disjoint branches split from og. Let Tv. C. T be the branch that contains u and choose 122 S F be such that all the nodes of (F-2 + ew) are contained in Tu and all the nodes of r = a-- (F2 + e.)) are contained in T TT. Clearly
8(r) 8(7)) 8(F2 + e.) 8(F1) 8(n(F22 + v)) + Olags
(57)
where e the unique child of og in T..
This completes the proof of the NNGP kernel K. As the proof of the NTK part is quite similar, we will be brief and focus only on the induction step.
Induction Step of @: |r| 2 h 2 and ((()) Recall that the formula of θ is
Ot(()) = = (frrncee (K,(()) ff JTEEEE + ++.()))))))))))))
(58)
For r E EN
Σ of (f {o,(t) 052
oggg(()
(X, (t) + (t)
(59)
F
Note that o. is adnissdmissi We apply the result of H to conclude that
0f 0i (freuree
(6.(())
S(ri) 8(ri)
(60)
0=
1f di (froggre
Hy
S 8(ri)
(61)
25

---

Under review as a conference paper at ICLR 2022
and the inductive step conclude that
2 ff Jerogue
(t) +.()))
Σ
d 8(F2)
if
$2 o 0 else
(62)
vogvEE 0e +x.)
2 ff VOoOUEE
(x.(t)++,,(1))
Σ 8(F2)
(63)
eoggeE of 00.
Note that
K :gv E g(d) and Of + 0,) # 0H 2
Thus
o (t)ll
Σ
(()) dd
(64)
FitPiEr
To control the lower bound, let be MST containing r(r). If deg(og) og: T) 1, then we can choose
71 and T2 = r * Notice that there is least one child node og with 0 (x, + θ,) + 0. Therefore
Σ
d 8((())) 2 d 8(P2) d(
(65)
(3.
Combining with
dog
[o( b (0) > 0
(66)
we have
0 (0) dd
remains handle the deg(og; T) 1 case. We choose (F1, 12) such that one branch of T the MST that contains re(2)) and the og and the remaining branch(es) is MST that contains (FF.) and the og. Then
0 (0) 120
3k.(1))07 05²²
Kn((t)
(t)
t==
2d 8(m)) 8(m1)-8((r) = d d((()
H.1 LEGENDRE POLYNOMIALS, SPHERICAL HARMONICS AND THEIR TENSOR PRODUCTS.
Our notation follows closely from (Frye & Efthimiou 2012
Legendre Polynomials. Let dn E No and Wa,, be the measure defined on the interval / = [-1, 1]
Wa, (t) (1 (d 33/2
(67)
The Legendre polynomial 1 (P.(1) r E N) an orthogonal basis for the Hilbert space I.2(T, Wa.)) i.e.
J. P.(0P= (t)dt 0 if r x r'
[d
else N r1
(68)
Here (t) is degree polynomials with P-(1) that satisfies the formula below, N(dn, r) is the cardinality of degree spherical harmonics in de and |St,-l is the measure of Sd,-1
'More accurate, this should be called Gegenbauer Polynomials However, decide to stick to the termi-
nology in (Frye & Efthimiou 2012
26

---

Under review as a conference paper at ICLR 2022
Lemma 2 (Rodrigues Formula. Proposition 4.19 (Frye & Efthimiou 2012
(r(1) C. (t)
(1 12)rt -3/22
(69)
dt
where
(-1)
Cr 2" + (dm - 3)/2),
(70)
In the above lemma, (x); denotes the falling factorial
(x)) = x(x - 1) 1+
(71)
(z)
(72)
Spherical Harmonies. Sd Then
Let ds define the (un-normalized) uniform measure the unit sphere
2T/2
Sd =
dSd,
(73)
r
(m))
The normalized measure on this sphere is defined to be
do
dSdu 1 and
do =1
(74)
Bda-1
The spherical harmonics (Yra in Rd are homogeneous harmonic polynomials that form an orthonormal basis in L (3 Adn))
[
Y (r = (r(.))
(75)
JESA,
Here I denotes the 1-th spherical harmonic whose degree is where E EN,L [N r)] and
2r + dnn - 2 din + r - 3) ~ (din) /r! as d + 00.
((dm. r)
(76)
--1
The Legendre polynomials and spherical harmonics are related through the addition theorem.
Lemma (Addition Theorem. Theorem 4.11 (Frye & Elthimiou 2012)).
Ye,(E)rr,1)), PG N(dm::)) (e(N(du.))
Σ
E, E Sd.-1.
(77)
Tensor Products. Let (N6 d (du) p T E N Nº, 1lN 12= [- 1 and w (ue w be the product measure IP, Then the (product of) Legendre polynomials
(t(t) = II (tu), t= ==(tw) E (EAg)
(78)
which form orthogonal basis for the Hilbert space L2(IP,W) 2 BuEN L (a,)).). Similarly, the tensor product of spherical harmonics
Y
II Yruder 1 - (1) E [N((rr))
II [N(du,
(79)
mEA!!
form an orthonormal basis for the product space
L (2) =
(S(
(80)
uEAr(d)
Elements in the set (Yr.)e((((.r)) are called degree (order) spherical harmonics in L a) and also degree spherical harmonics if |r| =r|=n = F N.
27

---

Under review as a conference paper at ICLR 2022
Theorem 5. We have the following, for K Koga or K gx
x((t) = Σ
(r()),
with R(r) ~ d 8(r) if r 0 else 0. (81)
PENNO (4)
Note that Theorem Thcorem[followw from this theorem and the addition theorem.
Proof of Theorem 7 Assume r + 0. Indeed, setting
& = =5(5) E X, 77 = (7w) (7w) wEN! E X and t = (tu) (tw) = (5" Ma.nu/da wEN
we have
(t(t) = II
Pr. (tn)
II
N(da; Pu)
Σ
Yruda (Ea/ Vool////u//a d (nv/V d
L.EN(d..T.)
(82)
= -
E vr.(E)Er.(1)))
(83)
[d())
Then Theorem ffoloos by noticing
((r))N(d,r)- d dlrl)) -uex! ruau =d-2(r)
(84)
Proof of Theorem
From the orthogonality,
K(rr= (K., P.)/
(85)
We begin with the denominator. Note that
[PPlLcu = II
| = (d:
II (Sd,,
(86)
MEN())
MENT)
By applying Lemma 2 integration by parts and continuity of ((r)) on the boundary 0TP
(C,, (x) = or f K((t) dt )
(1 (1-th (1- ())
3)/2 dt
(87)
= =-11" / k(r) (1 11-)) +)) 33/2 dt
(88)
=-1) (M((,, + + d))
(89)
where (C() is the derivative of K., the coefficient o, is given by Lemma
(-1)r=
G = II Gr =
II aEAd!
II
(-11dd
(90)
2 (ru + (d - 3)/2)r
MEN ())
and the major and error terms are given by
() / (1- (1-(2)r+(( (d-3)) 3)/2 dt = (0)
II
2r. d
(91)
Sgr. +d.
wEN(()
e(K, d) = / (x(r)))))))(())
(+(333 ()- dt (()) (1-t)
(92)
The mean value theorem gives
(t) (0))
Σ (((r+ew))
[
(93)
WEA
28

---

Under review as a conference paper at ICLR 2022
and the error term |e(K, d) is bounded above by
[ |ul (1 1g rrat (d ad.-d-33// 33/2 dt.,
J, (1 - (1- p)
Σ
(94)
S (1 (2))
12))
(rr 3312 dtu
WEN
S2r, d
S2rutdu-11
II MEND
1r=
(95)
32r, +
B2rutdu-21
MEND
Since for any a E N, as du - 00,
Batd.
n r((a + du - 1)/22//(((a d.)/2) d (dm,/2) (du)-
(96)
2 Batd
we have
le(K,,)
Σ
|
II
S2r, +d d.
(97)
S2r. +d.
MEND
MEND
We claim that (which will be proved later)
Σ [[((tttw))
( (10 S d b(r)
(98)
which implies
(K,, PP) or or (0)) + +0 (d min du)
2r,, + d
(99)
uEND
+2
Plugging back to Eq. 85 we have
k(r) = --1)', (x((0)) (0 d (d-((r)
32n, + d
Sd.
min dm)-
II MEN
uEN!
32 + -2
Sd_ -2
(100)
Since, for fixed and as du + co for all E Edd
(-1)-d-r and N(d,r)
1 and
II uEA(())
Ser, + dn
S -1 Sd
+1
dr dr/rr
S2r. th, -2
(101)
and thus
(c)))(() + d- dd
))
R(r) ~ r!
min du)
(102)
It remains to verify Eq.
98
By Lemma
we only need to show that
Σ d s(r+ew) < d B(r)
(103)
We prove this by induction on the number of hidden layers of G(d), The base case is obvious. Now suppose the depth of g(d) is h. Let C(r) be the set of children of og that are ancestors of at least one ((d) node of nr)). We split Adda into two disjoint sets
((r) {u E Agda Fv C(r) P(u v) 0) and Add (o(r))
29

---

Under review as a conference paper at ICLR 2022
For Q(r), we have 8(r + eu) = S()) + 8(e.) and hence
Σ d b(rtew)
Σ d 8(r) d 8(r) Σ d d(ea) 2 b(r))
(104)
(
(xQ(r)
In the last inequality above, have used
Σ
d b(ew)
Σ B(ew) 1.
(105)
(E
WEN1
To estimate the remaining, use induction. Note that (C(r) finite and independent of d. Then
Σ d c(r+
d -(((tteu;))
(106)
(EQ(r)
vEC(r) (E
= =do
E
d- (((((++mm))))
(107)
VEC(m) (EQ(T)
(c(r)ld Dog d d-8(((r==)) ~ 8())
(108)
vEC(r)
We have used induction on the sub- sub-graph with as the output node.
PROOF OF THEOREM 2
Let ((d)) be DAG associated to the convolutional networks whose filter sizes in the 1-th layer is k = =.d"), for < / < L++, in which we treat the flatten-dense readout layer as a convolution with filter size [d Note that have Op on and Ohr 01++1 We also assume activation layer after the flatten-dense layer, which does not essentially alter the topology of the DAG.
We need the following dimension counting lemma.
Lemma 4, Let L(g(d)). Then
dim (span (Y.I: C(r) E ((d,r))) d"
(109)
To prove Theorem we only need to verify the assumptions of Theorem 4 in Mei et al. (202 la For convenience, we briefly recap the assumptions and results from Mei et al. (2021a) aa) in See
is convenient group the eigenspaces together according to the learning indices L(g(4). Recall that ((G(d)) (ri < S rr...) ). Let
E. = span r.2 (Y [(r) = r
(110)
Then by Theorem I and Lemma dim(E.) d and X(g) r Vg E,, 9 0
(111)
where X(g) denote the eigenvalue of g. We proceed to verify Assumptions 4 and 5 in Sec. They follow directly from Theorem [ Lemma and the hypercontractivity of spherical harmonics Beckner (992).
I.1 VERIFYING Assumption 4
We need the following.
Proposition 1. For O < RR let D. = span (Y (Yr. [[(r) < <s). Then for f E Drr
If < ( /
(112)
Proof of Proposition 7 The lemma follows from the tensorization of hypercontractivity. Let f = Enzo Ys E ((,(s)) where Yş is degree A spherical harmonics in S,,. Define the Poisson semi- group operator
P.f(x) = Σ (Ya(T)
(113)
k20
30

---

Under review as a conference paper at ICLR 2022
Then we have the hypercontractivity inequality (Beckner 1992), for p and é S
V --
|PPfll S (l
(114)
One can then tensorize
(Beckner 1975 it to obtain the same bound in the tensor space.
Lemma 5 (Corollary
Montanaro
(012)). Let f (s,) - R. If S S q and $
V
9--1"
p-1
then
s fll2a(18.))) S (l..)))(()))))))
(115)
Let f == Er. IY,YY 1 Dr. Choosing V q- and 2 in the above lemma, we have
|
Σ r.
ard Y rilli
(116)
= =
ar "Y r.ell3
(117)
r.l
C "Y "Yr.113
(118)
r,l
1 -2r I r.1112
(119)
S 6
Ir] Σ a Y r.113
(120)
r.t
(q 1)
max
|r|
f $ (q 1)
(121)
Since & L(G(()), there is j such that rÿ <r < Tj+1- Let n(d) d' and
m(d) dim (span 14 3(r) S r2,)) dim(span U Ex)
(122)
Clearly, m(d) ~ d'; We list all eigenvalues of IC in non-ascending order as (Aa.). In particular, we have
Ad.m(d) ~ d' > d " THE dd.m(d)+1
(123)
Assumption 4 (a). We choose u(d) to be
w(d) = dim
span
U fro$2r+100
E,
(124)
Assumption (a) follows from Proposition 1
Assumptions 4 (b). Let inf(r ((g(d)): 2r 100). For ( >
we have
Σ
Nuy Σ (d ( dim d s(1-1)
(125)
j=u(d)+1
re
which also holds for / since
Σ Aa ~
(126)
j=u(d)+1
31

---

Under review as a conference paper at ICLR 2022
Thus
C )==(d))+3 Naa52 d 2-20(1-1)
Σ Ej=u(d)+1 X2, d-2(21-1) = =d- d2r+100 > =n(d2+t ~ d(2+ōrr
(127)
as long as 8 < 100/r.
Assumption (c). Denote
(E)
Σ Ac(r)),.(EEY,,.0)
(128)
r.1.((r)rr
We have
E, (E, n)) =
Σ rd:C(r)sr
(129)
E
xx))))
(130)
Σ )c(r))
Σ Y (E)(
(131)
rCC()>r
Σ
E Ac(r)=N(d,r)
(132)
r:C(r)sr
r:D(r)>r
Similarly,
Eg. Σ (r15)() 11))) r.l((r)>rr
E \c(r)
(133)
r:((r)>r
Thus E
Σ >c(r) ( (.)))= -Bei-----ppp
EE, Σ
(,,))) = (134)
(1(((r)> For the diagonal terms,
r.(:(())3))
Kd, (E.
Σ xc(r)) E (c(r) = IEe.d, (E,E)
r.lc(r)ssr
r:((rsr
(135)
which is deterministic.
1.2 VERIFYING Assumption
Recall that n(d) ~ d" and rj <r < 11+1
Assumption 5(a) follows from Eq. 111
Indeed, for
1
dm(d))11 kmm(d)+1
Σ
Nax (td Σ
dim
Ed
(136)
for Err2r
d' ddidii tra
(137)
=d'111 n(d) 1+8
(138)
for some
since r < Tz-1- Similarly, for = 1, since
Σ dda ~
(139)
k=)(d)+1
we have
(d (11)-
Σ
dd d'ii > n(d)
(140)
k=m(d)+1
Assumption 5(b) follows from
> Tz-
Assumption 5(c). Note that
d
Σ
dd. A ~ d' < (1-((1-0) (1-6)
(141)
k=m(d)+1
for some > 0 since ry <r.
32

---

Under review as a conference paper at ICLR 2022
J PROOF OF LEMMA 4
Proof. The lemma can be proved by induction. Base case: L = O. The network is a S-CNN. WLOG, assume oo + 0 and 01 + For r E L(g()), we know that r can be written as combination of Ou and 0r,, ie. r-feasible if in addition, there exists r with 8(r) = k101 and ((r) = kydg. Consider the set of all r-feasible tuple
kyda + Aia for some ko, k 2 O. We say tuple (Au, k1) is
F(r) = (ko, kn) r-feasible).
(142)
Clearly, F(r) is finite. It suffices prove that for each r-feasible tuple (ko, ki),
dim (span { (Yr,, (()) kgo
8(r) kj0,, Le ((d,r))) d'
(143)
Note that there are (d many ways choose 1 nodes in the penultimate layer. Then the dimension of the above set is about
(dat yku
Σ
II j=1
N koos)) (dat)
Σ
(144)
(No, No.
(No, I Ko ko, +... =kg
j=1
No, =ko
t d'
(145)
since the cardinality of the set
[kko .o, ko,1 4... ko,b1 ko:
ko.i ko.j E EN
is finite.
Induction step: 1. For with C(r) r. let & be the number of children of a MST of og); Clearly, k E [r/ Then we can classify Y, into most [r/ar-1] bins: (S.)/=I....I//aa... depending on the number of children of og in a MST. Let 22 be non-empty. r in Og is d". Note that there to choose children from og- Let {u, j=i,..... be one fixed choice and {9,} be the subgraphs with {uj} as the output nodes. Next, we partition (r kor.+1) into & components.
We only need to prove the number of Yr,1
(d many ways
r r- r- = r1 +... Tk
so that each ry a combination of {agJosisL. The cardinality of such partition is also finite. We fix one of such partition (ri,..., r*) so that each is learning index of Gj. We can apply induction to each (g).ry) to conclude that the cardinality of Y 1, with La, (r,) = ry is ~ d"s, where La, (T)) the learning index of r, of Gy. Therefore, we have
dim (span (Y,1: L(r) ((r)=r, =r, I ((d,r))) ~ (11
II SE[K]
d d"
(146)
K CNN-GAP: CNNS WITH GLOBAL AVERAGE POOLING
Consider convolutional networks whose readout layer is global average pooling (GAP) and flattening layer (namely, without pooling), resp.
CNN + GAP:
[Conv(p)-Aci] + [Conv (A)c + [GAP] + [Dense] [Conv(p)-Act + [Conv (A)) + [Flatten] - [Dense]
(147)
CNN:
(148)
Concretely, the input space is = (Sp-1)~~xw C I xw where p is the patch size of the input convolutional layer, & is the filter size in hidden layers, L is the number of hidden convolution layers and w is the spatial dimension of the penultimate layer. The total dimension of the input is = k. w, and the number of input nodes is [No = k w. Since the stride is equal to the filter size for all convolutional layers, the spatial dimension is reduced by a factor of p in the first layer, factor of I by each hidden layer. The penultimate layer (before pooling/flattening))
33

---

Under review as a conference paper at ICLR 2022
has spatial dimension and is reduced to by the GAP-dense layer or the Flatten-dense layer. The DAGs associated to these two architectures are identical which is denoted by G. However, the kernel/neural network computations are slightly different. If the penultimate layer has many channels and pee X - Raxw is the mapping from the input layer to the penultimate layer, then the outputs of the CNN-GAP and CNN-Flatted are
Σ W/ of jE(n]
(CPN = =n
Spen (ar)
(149)
iE(w]
fCNN-Flamen (x) (nw)
WysSpen (2))
(150)
jE(m),ie(w)
resp., where wy and y are parameters of the last layer and are usually initialized with standard iid Guassian W/. Wis ~ (0, 1). --t S W be the nodes in the penultimate layer, then [W-1] = w.
Let (Ee)vEN=, X, where & (8p-1)** Thus, each & contains k many input nodes (Eu,i Define
tu = ((Eu,i no.)) Mos)/ E E[-1,1]
(151)
Recall that in the case without pooling
(t,() = 6" if LvEE
(t),, Kg = =f Jogues
H.(() ff H.(()
(152)
VEN-
where t E [-1, - which is usually obtained by t = ((Eu,i, (u,i, hacl://)eeNcC (P))E) Indeed, for
each v E 1N H. depends only on the diagonal terms tvo = (1Ev,i / E [[1,1]* We can find function
Kpen [-1, 11kt + 1-11] s.t. H.o() 3 Kopen Vo E
(153)
Therefore, without pooling the NNGP kernel is
HCNN (t) = =f
H Mpen (trv) =
H Heen (tvv)
(154)
JIEN_,
vEN-1
Note that the kernel does not depend any off-diagonal terms tup with weight-sharing in the last layer. Let dpen (p. (p.p.....pP p)) E No Then dpenllz pk" is the effective dimension of the input to any node u E N-1. Assume k = d p da and wr = daw
because there isn't
and Oik Opp Ogp > Applying Theorem to Kpens we have
(t) = Σ
Aaeyeen (r) Σ
Σ Pro(E,), (7()))
(155)
PENU
VEN (EN(dp)..))
Clearly, the eigenfunctions are (Yr:(E)))rd. and the corresponding eigenvalues are ( Axxee (r) Note that
>xxoen (r) Axg (r) d 2(r)
(156)
Here and in what follows, we also consider No as an element in Nock When the readout layer a GAP, the weights of the penultimate layer are shared across different spatial locations, namely, all nodes in N_1 use the same weight. As such, the kernel correspond- ing to the CNN-GAP depends on both the diagonal and off-diagonal terms (fur)u.eNN.
[-1, " x which can be written (Nvvak et al. 2019b
HeNN = JU
Hepn (tuv)
Σ
H Kpen (fav)
(157)
M.VEN
34

---

Under review as a conference paper at ICLR 2022
Applying Theorem
I
to Hpens we have
KCNNCCA((t)
Σ
Axppen (r)
Σ
E
(Eu( Y Fra(mn)
(158)
w²
rENuL
W.NEN
(dpen)))))
Σ
Xrpee (r)
Σ
w
Y Vrultw))
w JuEN.,
(r.((Tu))
WEN-1
rENUL
(dpen.)))))
(159)
XXpen (r)
Σ
rr (
Sym Sym (m)
(160)
PENEL
(dN(epe
where
Y (E) = =5)===b
Yr.(E.) EEN and E (ddpen r)
(161)
uENL
That is the eigenfunctions and eigenvalues of KENN-GAP are (Y (E)),, and wt Nx (r) resp.
In sum, the cigenvalues of KCNN and KCNN-GAP are the same (up to the multiplicity factor w). Each eigenspace of KANN-GAP is given by symmetric polynomials of the form Eq. (161). We can see that the GAP reduces the dimension of each eigenspace by a factor w. Same arguments can also be applied to the NTKs
OCNN (t) = -f
(Kpen (tov) + ① (pen(tev))
(162)
VEN-1
Σ MEVAL
1 Xxxpe (r) + -d0ppn W
(r)
Σ
Σ
Yr,(E,); Y..G).Yrriii (nv)))
w
VEN
LEN((dpen.))
(163)
OCNN-GAP(t) = U.VEN_1
(Kpen + Open (tue))
(164)
Σ
1
Xxxpe (r) de (r)
Σ
A (E), Y (n)
(165)
W
w
PENAL
WEN-1
where Open is the NTK of the penultimate layer which is the same for all nodes in A-1. Since ur >2pmm (r)) we have
1
1
XX (r)
>dpmn (r) 2(r)
(166)
w
w
K.1 GENERALIZATION BOUND OF CNN-GAP
We show that GAP improves the data efficiency of D-CNNs by a factor of w d under stronger assumptions on activations Φ. Assumption Poly-o: There is a sufficiently large E N such that for all hiddens nodes u
(0) 0 for 15j J and 0n ( (0)
0 otherwise
(167)
This assumption implies that there 0 < J1 J2 E
R such that for all 0 *f r with |r| < J1
d"
d"
K
(0) * 0
and
θ pen
(0) + 0
(168)
dt
pen
dt
and for all with |r| > Jz
d"
d"
K
pen
0
and
θ pen
0
(169)
dt
dt
Moreover, Jn as J
35

---

Under review as a conference paper at ICLR 2022
Let Sym (X) 1 (*') be the close subspace spanned by symmetric eigenfunctions Eq. 161 Ksym= KCNN-GAP OCNN-GAP.
Let
For X C X and r & [(g(")), define the regressor and the projection operator be
Rx (f)))) KSym (x, X Kym (X, (Xx
Py (ʃ)
Σ E
(
Sym ( ( V r.
Sym
Theorem 6. Let {g where each g(d) DAG associated the D-CNN in Eq. (147) with ax, ap, aw O. Let & ((g(d)) ) be fixed and the activations satisfy Assumption Poly-o for J (() sufficiently large. Let f E (2) with E, = O. Then for 0.
S (1) -
11
(x)) - p (1)
Ca.e Ca..ll./11. 12 1 (x) Spe
(170)
1. (2))
where Cd.e -> in probability d over X
Proof of Theorem 6
We need the following dimension counting lemma, which follows directly
from Lemma 4
Lemma 6. Let E L(G(()). Then
dim (span {
r. ((r) =,, 1 E (((d.)))) ~ dr
(171)
Recall that L(g(()) = {ry} in non-descending order. Similarly, let
E span Sym: g(r) = ri)
(172)
From the above lemma, have
dim(L, d
(173)
Since & (E((()), there is j such that ry <r <r< Let n(d) do and
m(d) dim (span Y Sym ((()) $ rj)) dim(span U E
(174)
Clearly, m(d) ~ dr: We list all eigenvalues of Ksym in non-ascending order as {dd,1)- In particular, we have
Adm(()) ~ d > d= d Adm(d)+1-
(175)
We proceed to verify Assumptions and in Sec. Assumptions (a)
We choose u(d) to be
u(d) dim span
E
(176)
Let s if B(g()): F>> 2r 100). Assumption (a) follows from Proposition
Assumptions 4 (b) For 1 > 1, we have
Σ Nag
Σ
(d
dim (ESy))) d-1(1-1)-a
(177)
+=u(d)+1
which also holds for 1 = since
d
Σ Xas
~1
(178)
f=uld)+1
36

---

Under review as a conference paper at ICLR 2022
Thus
(j=u(d)) N2532 Σj Σ)=((0)+1 Ad. d-o(21-1)-aw do > prr1100-a > n(d)2+0 ~ d(2t8)(r-aw),
d d-2s(1-1)-20 20
(179)
Assumption (c) This requires some work and is verified in Sec. K.2
Assumption 5 (a) Since m(d) = dimmmspaa Uisi Ei) and rj+1 > r > ry, we have
Nas
Σ (d dim(E,
(180)
(d-r
Ad,m(d)+1 J2m(d)+1
121
dim E - dr diit1-a
(181)
> n(d) 1-6 = d dr>as))1tt)
(182)
as long as 8 < (1z+1 0w))((r (rw))
Assumption 5 (b) This is obvious since m(d) ~ dm n(d) ~ a= and r > Tj.
Assumption (c) This follows from rj r. Indeed,
1
Σ
Ad.j (d (d-rs) Σ dim(E, ~ d" aw
(183)
Ad,m(d) f2m(d)+1
121
In(d)=- d(r-aw)(1-6)
(184)
as long as 0 < 8 < 1- (r- (rr
K.2 VERIFICATION OF ASSUMPTIONS 4(C).
We begin with proving Eq.
227). Let X, define the random variable
X; = Lg K (aa E and A = -
(185)
We need to show that
suPiE(n(d))
A,l prob, 0. EX,, d-+00
(186)
By Markov's inequality, it suffices to show that
(EX,)_BE
E sup sE(n(d)
|
0
(187)
d-+00
By orthogonality and treating r E N as an element of Nuk we have
E.X; Ee, Ksym.
(188)
= Beg r:((r)>r
Σ
(sym(r)
Σ
S
Sym nn (E) r.1 (E)
(189)
(dN(n))
=REE-au
Σ
R3ym (r)
Σ
PSTT(E) Y Sym 1. (E)
(190)
(dN(d))
Kyy (r)
E
Y
(E)Y Sym
r.1 (E)
(191)
(d
Σ
R2 (r)
(192)
LEN (dpen))))))
Σ
Sym (T) N (dpen: r)]
(193)
~r(()>r
37

---

Under review as a conference paper at ICLR 2022
and
X; = Sg Kmy (E: E)²
(194)
= Be
Σ (sym(r)
E
Sym Sym Y rd (E:) r. (E)
(195)
r-(r)>r
(EN(dnen
Eg
Σ
(r)
Σ
Y Sym
r.1 (E:) Y Sym
r.t (E)
(196)
rit(r))
(dN(d)))
E
(r)
Σ
BEWOS
Yr. (E:) 1, (E)
Sym
(197)
LEN(dpen.t)
(m)())
(T)
Σ
Pr (E:)
Sym
(198)
(:)())>)
LEN(d)en.r)
E
Sym
E
Σ
Y (E,
2²+ E YYr,(EE,, 1 Fr.((s..))
(199)
w
w
r:S(r))n
(dN(dpen)))
uFe
1 (ri(E..))
E
Sym (r)
W
IdN(dpeniP)
uFF
(200)
Let
X
Σ
1 usEe
(201)
(dp()))
then
A = Σ (ym(r)
(202)
(:2())>r
We replace the maximal function by the 19-norm for q 2
E sup JA Σ 1
< E Σ
1 = n(d) (BIA))))))))))
(203)
:E(n(d)
xEIn(d)]
vE(n(d)
where the first three expectations are taken over Ei...., En(d) . ~ oa and the last one is taken over &; ~ σg. Then we replace the - by the L2-norm via Hypercontractivity, in which we used Assumption Poly-ć which implies that A; is polynomial of bounded degree
E sup | < (dd) (?)) < Can(d) (BIA,))) Can(d) : (EA))) (E(n(d))
(204)
We expand the n.2-norm and use orthogonality to "erase" the off-diagonal terms twice: first for +
E Xr, =0
(205)
and second for l # l' or u #
Eg
x²_ r.
Eg
Σ
EVr.(Ei, (o..(Ess
Σ
Σ
Y ( D (..((Ei))))
~ow
LE (dN(d))
(206)
2 E
Σ
w(w 1)
2
w2
(dN(d))n.r)
LEN(dpen.r)
(207)
2(w
1)
2(w 1)
N (dpenn r) S 2. (dpeee r)
(208)
1
38

---

Under review as a conference paper at ICLR 2022
Combining this estimate with Eq. (93), Eq. 202 and Eq. 204 yields
|A - Con(d) (2 m())s> Sym (r) (d pen: 1)))
(E
sup sE[n(d)]
(209)
Eng(r)>> Sym (r)[N (d (dpen, r)
S v2d))(d) 1 Σm Sym (r) N (d (dpen: r-) )1//2
(210)
En End(rierr Sym (r) N (dper: m)
Sym (r) N (dpens r) 11/2
S v2C,m(d)
sup rr(r)>r
(211)
Sym (r) (dpenn r)]
2Cqd
sup r((r)>r
N r) 1-
(212)
drla sup <()(>>>
(213)
d-+00
by choosing g (independent of d) sufficiently large. The proof of Eq. (28) similar. Let X; denote the random variable
X; KSym. (E.,Et) and A; X; EX,
(214)
and it suffices to prove
As 0
(215)
E.,,
d=+00
We have
E.;- = Eg Kym mm()) (5:,
(216)
= Reiros
Σ
Rsym( (r)
Σ
Y (E:) (E:) Sym
r.l (E:)
(217)
(dN(d)))))))
Σ
Esym(1) (r)) r)]
(218)
r:)(r)>r
and
A, X, EX, w-
Σ (T)
Σ
(219)
(:)()>>r
LEN .P) ughin
The remaining steps (replacing the maximal function by the 19-norm, and then the Lo-norm by the L²-norm using hypercontracttvity) are similar to that of the proof Eq. (27 which are omitted here.
L KERNEL CONCENTRATION, HYPERCONTRACTVITY AND GENERALIZATION OF MEI ET AL. (2021A)
For convenience, we briefly recap the analytical results regarding generalization bounds of kernel machines from Mei al. 2021a) Sec 3.
Let (X,,, a.) be a probability space and H. be a compact self-adjoint positive definite operator from 1,2 (22 a.) - (X,, a.). We assume H. E 12 x Xa). Let (way) and (da,j) be the eigenfunctions and eigenvalues associated to H,,, i.e.
(x)a = / yex,
)e.bas(x).
(220)
We assume the eigenvalues are in non-ascending order, i.e. Ad.it1 2 Ad. 2 0. Note that
Σ
Xa. = 196 1 6000
(221)
3
39

---

Under review as a conference paper at ICLR 2022
The associated reproducing kernel Hilbert space (RKHS) is defined to be functions f L (Xx, σa)
with 136 fll oo. Given a finite training set X C Xa and observed labels ((X
R the regressor an extension operator defined be
fx) = Ha( X) (), f(X). Intuitively, when "X X," in some sense, expect the following
(222)
(x) = Ha( X) (x, x)x)) + (x) = Ha( (())= f(x),
(223)
namely, "Axx Ix," in
Using tools from the non-asymptotic analysis random matrices (Vershynin, 2010),, the work Mei al. (2221a) provides very nice answer the above question in terms of the decay property of the eigenvalues {Aa.j} and the hypercontractivityy property of the eigenfunctions {wai)- They show that Rx is essentially projection operator onto the low eigenspace under certain regularity assumptions on the operator Hy. These assumptions are stated via the relationship between the number of (training) samples n r((d). the tail behavior of the eigenvalues with index 2 m m(d)
and the tail behavior of the operator Hd
He (1,
Σ (x
(224)
)>m(()
as the "input dimension" d becomes sufficiently large.
Assumption 4. We say that the the sequence of operator (NaJa>1 satiesfies the Kernel Concen- tration Property (KCP) with respect to the sequence (n(d), m(d) (22))2221 1 if there exsts a sequence of integers (u(d) )221 with u(d) 2 m(d) such that the following holds
(a) (Hypercontractiiity) Let Du(d) = spant byy 115 S u(d)). Then for any fixed 2 1, and C = (g)) such that for f E Dunad)
( I ClIffl1:
(225)
(b) (Eigen-decay.) There exists > 0, such that, for all large enough, for = 1 and 2,
(z N2,1)²
n(d)2+5
(226)
Σzza(d)+2 X21
(c) (Concentration of Diagonals.) For (2,) )e(((()) o n(d) have:
suPzein(d) Ex He, (m (2i, x22 Ey a Hed (2,
(227)
E En Hd. mm() (z, 2)2
d
suPsein(d)
Wd. md(d (Ii v.) E Exnos mid (2x Prob,
(228)
Exno, (d,>m(a) (I,
d
where ca + in probability as d + oo.
Assumption 5. Let Ht2 and ((()) be the same as above.
(a) For / = 1 and 2, there exists 5 > 0 such that
n(d) 1+6 <
1
Σ
NaR
(229)
X
Nammddy41 km
(b) There exists 8 > 0 such that
m(d) < 1(d)2-8
(230)
(c) (Spectral Gap.) There exists 8 >> O such that
n(d)2 1-8 2
Σ d
(231)
Ad. k2m(d))1
40

---

Under review as a conference paper at ICLR 2022
Let T>* (similarly for Pa. Sk etc.) denote the projection operator
POks= = (S.
(232)
j>k
Theorem 7
Mei et al. 202la)). Assume Ha satisfy Assumptions 4 and 5. Let {fala21 be
sequence of functions and let X do n(d) Then for every O.
[[ - fall (x
(ddd)]alll + ca.e faalIlaall
(233)
where Ca.e - in probability as d + oc.
The theorem says, Rx essentially the projection operator P sm(d) in the sense that when restricted to L 2 ( oa).
R I' sm(d) + Errord,
(234)
41


Reviews:
[{"review_id": "u37nI8RjL3", "reviewer": "Reviewer_V5xU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: The paper sounds very interesting! As far as I know, it proposes a unique perspective to capture architectural biases finely. \n\nWeaknesses: The paper is very hard to follow partially because it is non-standard. Some parts lack rigor. Figures need a much better explanation.\n\nIn my opinion, the biggest issue is the interpretation of the main results (Section 5). I cannot follow how the authors created the DAG of the s-CNN network for example and from there arrived at the equation (30). \n\nExperiments are only made for a particular and somehow peculiar type of synthetic data. \n\nI would also appreciate some explanation on what Conv(p^2)^2 (and so on) corresponds to in terms of standard ConvNet architectures. \n\nDetailed feedback:\n- In figure 1, it was not clear to me what the black line represents. Can you study what kind of architectural changes make the family of learnable functions bigger (for example making the network wider or deeper in the case of MLPs)?\n- \"The amount of time needed to learn the j-th eigenfunction is about 1/K(j)\" (page 3) -- can the authors elaborate on this point? \n- Figure 2 is not comprehensible as it stands. Why not include a nice & explanatory caption?  \n- Page 5, at the beginning of the main results: \"the goal is ... non-asymptotic characterization as the input dimension $d \\to \\infty$\": here I'm confused about what does non-asymptotic refer to. \n- Why is the spatial index defined twice both in Def 1 and Def 2? \n\nMinor feedback/typos:\n- Although I liked the color code in general, I found the color code for finer interpolations confusing. (In Figure 1 caption and bullet point 3 the color codes do not match). \n- At the end of page 2, where the MSE is defined, it seems that the index for the summation should be (x, y) \\in (X, Y)\n- Page 2, .... the gradient dynamics is describe'd' ('d' is missing) \n- It is not clear what \"concrete\" input spaces refer to on page 3. \n- Page 6, It describe's' a connection .... ('s' is missing) ", "summary_of_the_paper": "The paper categorizes architectural biases from a frequency point of view through the lens of NTKs and NNGPs. The two main quantities are the frequency index (FI) and the spatial index (SI) which are calculated from the DAGs. The authors claim that these two quantities capture what type of functions (in terms of frequency and space) can be learned by specific architectures: i.e., MLPs learn LRLF functions, s-CNNs learn SRHF functions, and so on. The main theoretical contribution is Theorem 1: the authors give an architecture-dependent spectral decomposition formula for the NTK and NNGP Kernels using DAGs. ", "summary_of_the_review": "Although the paper looks very interesting, I found it very hard to follow. I think there is substantial room for making the paper more accessible (see the detailed comments above). But also, my lack of familiarity with the tools used in the paper (i.e., graph computations) may have made it difficult to read for me. I could not follow how the authors arrived at the LRLF-SRHF- and similar interpretations. Therefore, I can not recommend acceptance. ", "strength_and_weaknesses": "", "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": "n7A08sd4dKO", "reviewer": "Reviewer_aE2B", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe theorem statements are simple and clear. \n\nWeakness:\nIt is hard to decipher what is happening with just the theorem statements alone. \n\nClarity: The paper is clear till Section 3, then most part of Section 4 is confusing. The theorem statements are simple and clear. However, it is hard to decipher what is happening with just the theorem statements alone. \n\n\nThe following are not clear and need to be discussed explicitly:\n\n* How is the cardinality of $\\Lambda_{\\mathcal{G}}$ related to the architecture?\n\n* Does condition (1) on Assumption-G place a restriction?\n\n* Is the weight $w_{uv}$associated to the edge $uv\\in\\varepsilon^{(d)}$ a constant, since it is said that $w_{uv}\\equiv \\alpha_u$. Looks like $w_{uv}= \\alpha_u$ is used in Definition 1. However, it is confusing because $w_{uv}$ is also being used in Section 3.1 equations (14), (17-20). Please clarify, i.e, are the $w_{uv}$ in Section 3.1 and Section 4 the same, if not is it possible to use a different notation?\n\n* Is $\\sum_{v\\in\\mathcal{N}_0} d_v =d$?\n\n* What is the intuition behind spatial distance?\n\n* What are the activations that satisfy Assumption-$\\phi$?\n\n* $\\mathbf{t}^{\\mathbf{r}}$ is defined, but it is not clear where it is used.\n\n* Is ${n(\\mathbf{r})}$ equal to the set of input nodes for all $\\mathbf{r}$ such that $\\mathbf{r}>0$? Or put differently what happens if one of the $r_v$ is equal to zero and one of the input nodes get left out?\n\n* Is there an example of $n(\\mathbf{r})$ without a common ancestor $u$ such that $\\phi_u$ is admissible?\n\n* Is there an example of an $\\mathbf{r}\\notin\\mathcal{A}(\\mathcal{G}^{(d)})$, i.e., an $\\mathbf{r}$ that is not learnable?\n\n* In Section 5, (S-CNNs and SRHF Interactions), \n\n   + it is said that since the activation function of the last layer is identity we have $\\mathcal{A}(\\mathcal{G}^{(d)})=\\{\\mathbf{r}\\in \\mathbb{N}^{|\\mathcal{N}_0^{(d)}|}, n(\\mathbf{r}) = 0 \\text{ or } 1\\}$. However, it seems that the same argument applies to MLPs as well (page 4, last paragraph mentions \"the activations of the input/output nodes be the identity function\"), yet, in equation (29) $\\mathcal{A}(\\mathcal{G}^{(d)})=\\mathbb{N}^d$. It is not clear why there is a difference.\n   + How can $|n(\\mathbf{r})|$ be $1$ or $0$? Given that there are $w$ input nodes, which node gets chosen for $|n(\\mathbf{r})|=1$?\n   \n* How is $|\\mathbf{r}|$ defined?\n\n\n* What is the meaning of short (long) range interaction?\n\n* It is not clear what the dotted lines in Figure 2 mean. Especially, what is the point of highlighting the left most branches alone. Same goes with the Figure 4 (Figure Zoo) in the appendix.\n\nOverall: \n1. It is not clear what is meant by space and the space frequency trade off?\n\n2. Given that there are too many constants, $\\alpha_u$, $\\alpha_v$, $\\alpha_w$, $\\alpha_p$, it might be great to give some template networks to illustrate. While the paper indeed talks about, MLP, S-CNN, D-CNN etc, the discussion about how the specific constant were arrived at in equations (29-31) is very rushed and is the major cause of confusion.\n\n", "summary_of_the_paper": "The paper shows how the topological of convolutional neural network restructures the eigenspace of the neural kernel. ", "summary_of_the_review": "The current score is mainly due to the issues related to clarity.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "S-3iwOzGDi", "reviewer": "Reviewer_JW33", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides solid foundations to understand the mechanism behind neural networks, including deep neural networks. This is done thanks to recent theoretical advances of neural network Gaussian process and neural tangent kernels. This work seems very interesting. However, this work only explore the architecture of neural networks to understand their behaviors. While the conducted analysis is carried on the model of the neural network, we find that it is missing some in-depth analysis on the other two basic ingredients of machine learning methods, namely the data and the optimization algorithm. It is worth noting that different optimization algorithms are used in the paper, namely SGD+ Momentum (used for finite-width networks) and kernel regression (used for infinite-width networks), but nothing is said about the influence of the algorithms. This is also the case about missing analysis on the influence of the training dataset.\nThere are some spelling and grammatical errors in the paper, such as “An demonstration”, “It describe a”, “our theorem justify”, “spherial harmonics”...\n-------------------------------------------------------\nRebuttal\nThe authors reply is off the mark, as they did not tackle our concerns, neither address comments from the other reviews. After reading all the reviews and the authors' replies, I have downgraded my score.", "summary_of_the_paper": "This paper provides new insights to understanding the mechanism behind neural networks, thanks to a space-frequency through the so-called eigenspace restructuring.\n", "summary_of_the_review": "The paper provides solid foundations to understand the mechanism behind (deep) neural networks.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ByYX-qk3BPa", "reviewer": "Reviewer_nazU", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThis paper evaluates the success of deep neural networks by running extensive experiments that show the tradeoff between space and frequency. \n\nWeakness:\n\nThe meaning of the word frequency is unclear in the context of this paper.\n\nThe main idea behind theorem \"eigenspace restructuring\" which replaces one eigenvector/value computation with a set of part based eigenvalue/eigenvectors  has limited novelty.  The novelty is in its use in neural network architecture analysis.\n\nThe authors might want to consider evaluating the performance of a system based on the amount of data employed and based on how data was acquired (observational vs experimental studies).  Systems that employ data from observational studies are known to be susceptible to selection bias and spurious correlations, as opposed to data from experimental studies that are employed in objective causal inference.  \n\n\nMissing reference:\nAs the authors might recall, Vasilescu etal. in their ICPR 2020 paper have advocated replacing the SVD computation with a set of part based SVDs for which they provided a closed form mathematical derivation.  Based on this mathematical derivation, they developed  the Incremental Hierarchical M-mode Block SVD which was demonstrated experimentally. \n\n@inproceedings{Vasilescu20,\n\nauthor={Vasilescu, M. Alex O. and Kim, Eric and Zeng, Xiao S.}, booktitle={2020 25th International Conference of Pattern Recognition (ICPR 2020)}, title={Causal{X}: {C}ausal e{X}planations and {B}lock {M}ultilinear {F}actor {A}nalysis}, year={2021}, location={Milan, Italy}, month={Jan}, pages={10736--10743} }\n\n\n\n", "summary_of_the_paper": "The authors show that deep convolutional networks restructure the eigenspaces of the inducing kernels,\nwhich empowers them to learn a dramatically broader class of functions, covering a wide range\nof space-frequency combinations.", "summary_of_the_review": "The authors evaluate deep convolutional networks through the lens of hierarchical locality. The paper evaluates the performance of deep neural networks by performing extensive experiments that show the tradeoff between space versus frequency.  The eigenspace restructuring theorem has a well-chosen name.  However, eigenspace restructuring is a well-known concept and the novelty of the theorem is limited. \n\nClarity of the writing and its overall organization needs improvement.  The word frequency needs to be better defined.  It is not clear if there are any novel insights.  \n\n\n----\nUpdate:  My original score was too generous and it was in anticipation that any mathematical inconsistencies or ambiguities would be addressed.  \n\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that deep convolutional neural networks in the kernel regime restructure the eigenspaces of the inducing kernels, which leads to some insights regarding the range of space-frequency combinations learned by such networks.

The reviewers identified a number of problems with the current submission. For instance, they found that the paper is hard to follow, it lacks clarity and the theorem statements are hard to understand. The authors also use a somewhat non-standard experimental setup.

Despite an extensive discussion with the authors which cleared out a few minor problems, the bulk of the concerns of the reviewers were not successfully adressed. I am therefore not able to recommend acceptance. The authors need to improve the clarity of the paper and provide more discussions of the theorems in a resubmission, as well as potentially reconsider their experimental setup.
Decision: Reject