Year: 2021

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.

heading: 1 INTRODUCTION
text: Learning in high dimensions is commonly believed to 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 a wide range of highly complex and high-dimensional 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; Senior 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 (outof-distribution) generalization (Zhang et al., 2021), calibration (Ovadia et 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 algorithm. Among them, the models, a.k.a. architectures of neural networks are the most crucial innovation in deep learning that set it apart from classical machine learning methods. More importantly, the current revolution in machine learning is initialized by the (re-)introduction of convolution-based architectures (Krizhevsky et al., 2012; Lecun, 1989), and subsequent breakthroughs are often driven by the discovery or application of novel architectures (Vaswani et al. (2017); Devlin et al. (2018)). As such, identifying and understanding fundamental roles of architectures are 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. (2018); Jacot et al. (2018); Du et al. (2018); Novak et al. (2019a); Lee et al. (2019) and many others.) These developments have discovered an important connection between neural networks and kernel machines: the Neural Network Gaussian Process (NNGP) kernels and the neural tangent kernels (NTKs). Under certain scaling limits, the former describes the
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 & Hu, 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 connection between a network’s architecture and its learnability through a trade-off between space and frequency, providing novel insights behind the mystery power of deep CNNs (more generally, hierarchical locality (Deza et al., 2020; Vasilescu et al., 2021).) By frequency, we mean the degree (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. 1.
1. The learning order (see Green Arrow in Fig. 1) of eigen-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-Range-High-Frequency interactions. MLPs can model Long-Range-Low-Frequency (LRHF) interactions but fail to model Short-Range-HighFrequency (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-Frequency (MRMF).)
3. In addition, high-resolution CNNs (HS-CNNs, EfficientNet-type of model scaling) further broaden the class of learnable functions to contain (1) extrapolation: Ultra-Long-RangeUltra-Low-Frequency and the dual interactions and (2) finer interpolations interactions.
4. Finally, we verify the above claims empirically for neural kernel methods and finite-width networks using SGD + Momentum for dataset and networks of practical sizes.

heading: 2 LINEAR AND LINEARIZED MODELS
text: As a warm up exercise, we briefly go through the training dynamics of linear models. Let (X ,Y) denote the inputs and labels, where X ⊆ Rd and Y ⊆ R. Assume J : Rd → Rn is a feature map and the task is to learn a linear function f(x, θ) = J(x)θ to minimize the MSE objective 1 2 ∑ (x,y)∈(X ,Y) |f(x, θ)− y|2. Let ℛ(X , θ) = f(X , θ)−Y be the residual of the predictions of X . Then the gradient flow dynamics can be written as d
dt ℛ(X , θ) = −J(X )JT (X )ℛ(X , θ) ≡ −K(X ,X )ℛ(X , θ) (1)
Since the feature kernel K(X ,X ) = J(X )JT (X ) is constant in time, the above ODE can be solved in closed form. Let m = |X | the cardinality of X and K̂(j)/uj be the j-th eigenvalue/eigenvector of K(X ,X ) in descending order. By initializing θ = 0 at time t = 0 and denoting the projection by ηj = u T j ℛ(X , 0), the dynamics of the residual and the loss can be reduced to
ℛ(X , θt) = ∑ j∈[m] e−K̂(j)tηjuj , L(θt) = 1 2 ∑ j∈[m] e−2K̂(j)tη2j (2)
Therefore, to make the residual in uj smaller than some > 0, the amount of time needed is t ≥ K̂(j)−1 log 2
η2j /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.

heading: 2.1 LINEARIZED NEURAL NETWORKS: NNGP KERNELS AND NT KERNELS
text: Let f(θ, x) be a general function, e.g. f is neural network parameterized by θ. Similarly, d
dt ℛ(X , θ) = −J(X ; θ)JT (X ; θ)ℛ(X , θ) ≡ −K(X ,X ; θ)ℛ(X , θ) . (3)
However, the kernelK(X ,X ; θ) depends on θ via the Jacobian J(X ; θ) of f(X ; θ) 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),
K(X ,X ; θ)→ Θ(X ,X ) as width→∞. (4) The residual dynamics becomes a constant coefficient ODE again ℛ̇(X , θ) = −Θ(X ,X )ℛ(X , θ). To solve this system, we need the initial value of ℛ(X , θ). Since the parameters θ are often initialized using iid standard Gaussian variables, as the width approach infinity, the logits f(X ; θ) converge to a Gaussian process (GP), known as the neural network Gaussian process (NNGP). Specifically, f(X ; θ) ∼ N (0;K(X ,X )), where K is the NNGP kernel. Note that one can also treat infinite-width networks as 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 classification layer (Lee et 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 infinitewidth networks, whose training dynamics are governed by constant coefficient ODEs. To make progress, it is tempting to apply Mercer’s Theorem to eigendecompose Θ and K, e.g.,
K(x, x̄) = ∑ K̂(j)φj(x)φj(x̄) and Θ(x, x̄) = ∑ Θ̂(j)ψj(x)ψj(x̄) (5)
One advantage of applying this decomposition is that it has almost no constraint on the kernels and the inputs. However, this decomposition is too coarse to 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 a 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 to characterize the analytical dependence of the decomposition Eq. (5) on the network’s topology in the high-dimensional limit.

heading: 3 NEURAL COMPUTATIONS ON DAGS
text: 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. B, we provide a toy example to help understand the motivation. For a positive integer p, let Sp−1 denote the unit sphere in Rp and Sp−1 = √ pSp−1, the sphere of radius √ p in Rp. We introduce the normalized sum (integral) x∈X f(x) ≡ |X|−1 ∑ x∈X f(x) ( x∈X f(x) ≡ µ(X)−1 ˆ x∈X f(x)µ(dx) ) (6)
where X is a finite set (a measurable set with a finite positive measure µ).
We find it more convenient to express the computations in neural networks, and in neural kernels via DAGs (Daniely et al., 2016), as 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) to 1. Let G = (N , E) denote a DAG, where N and E 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 N0 ⊆ N the set of input nodes (leaves) of G, i.e., the collection nodes without a child. Each node u ∈ N is associated with a pointwise function φu : R → R, which is normalized in the sense Ez∈N (0,1)φ2u(z) = 1 . It induces a function φ∗u : I ≡ [−1, 1] → I defined to be φ∗u(t) = E(z1,z2)∈Ntφu(z1)φu(z2) . Here Nt denotes a pair of standard Gaussians with correlation t. We associate each u ∈ N a finite-dimensional Hilbert space Hu, and each uv ∈ E a bounded linear operator Luv : Hv → Hu. Let
X ≡ ∏ u∈N0 X u ≡ ∏ u∈N0 Sdim(Hu)−1 ⊆ ∏ u∈N0 Hu and I = I |N0|
be the input tensors and the input correlations to the graph G, resp. We associate two types of computations to a DAG: finite-width neural network computation and kernel computation,
NG : X → HoG and KG : I → I , (7) resp. They are defined recursively as follows
Nu(x) = φu ( ∑ v:uv∈E Luv(Nv(x)) ) if u /∈ N0 else Nu(x) = xu (8)
Ku(t) = φ∗u ( v:uv∈E Kv(t) )
if u /∈ N0 else Ku(t) = tu (9)
where x ∈ X and t ∈ I . The outputs of the computations are NG(x) = NoG(x) and KG(t) = KoG (t). Note that KG is indeed the NNGP kernel. The NTK can also be written recursively as
Θu(t) = φ̇ ∗ u ( v:uv∈E Kv(t) ) v:uv∈E (Kv(t) + Θv(t)) with ΘG = ΘoG . (10)
Here, Θu = 0 if u ∈ N0 and φ̇∗u is the derivative of φ∗u.

heading: 3.1 THREE EXAMPLES: MLPS, S-CNNS AND D-CNNS.
text: 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 a deep convolutional network (D-CNN) that contains (1 + L) convolutional layers. The architectures are
MLP: [Input]→ [Dense-Act]⊗L → [Dense] (11) S-CNN: [Input]→ [Conv(p)-Act]→ [Flatten-Dense] (12) D-CNN: [Input]→ [Conv(p)-Act]→ [Conv(k)-Act]⊗L → [Flatten-Dense-Act]→ [Dense] (13)
where p/k is the filter size of the first/hidden layers and Act means an 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. 2 (a, b, c) for the DAGs associated to a (1+3)-layer CNN (with p = k = d 1 4 ), a (1+1)-layer CNN (with p = k = d 1 2 ) and a 4-layer MLP.
MLPs. Let G be a linked list with (L + 2) nodes, including the input/output nodes. Let Luv ∈ Rnu×nv , where nu/v = dim(Hu/v) and the activations of the input/output nodes be the identity function. Then NG represents a L-hidden-layer MLP. In addition, let Luv be initialized iid as
Luv = 1 √ nv (ωuv,ij)i∈[nu],j∈[nv] , ωuv,ij ∼ N (0, 1) . (14)
Let tx,x′ = xTx′/nu for u ∈ N0 and nv → ∞ for all hidden nodes, then the outputs of N(X ) converge weakly to the GP GP(0,KG(tx,x′)x,x′∈X ) and ΘG(tx,x′)x,x′∈X is the NTK in the sense
ENG(x)NG(x′) in prob.−−−−→ KG(tx,x′) and 〈∇NG(x),∇NG(x′)〉 in prob.−−−−→ ΘG(tx,x′). (15)
Indeed, note that deg(u) = 1 for all u /∈ N0. Eq. (9) and Eq. (10) become
Ku(tx,x′) = φ∗u(Kv(tx,x′)) and Θu(tx,x′) = φ̇ ∗ u(Kv(tx,x′))(Kv(tx,x′) + Θv(tx,x′)) (16)
which are the recursive formulas for the NNGP kernel and NTK; see e.g. Sec.E in Lee et al. (2019).
S-CNN. The input X = (Sp−1)1×w ⊆ Rd, where p is the patch size, w is the number of patches, d = pw is the dimension of the inputs. Here, the inputs have been pre-processed by a patch extractor and then by a normalization operator. In words, the S-CNN has one convolutional layer with filter size p, followed by an activation function φ (e.g., Relu), and finally by a flatten-dense readout layer. Mathematically, by letting n ∈ N be the number of channels in the hidden layer, the output (i.e., logit) is given by
Convolution + Activation: zij(x) = φ p− 12 ∑ β∈[p] ω1,j,βxβ,i  for i ∈ [w], j ∈ [n] (17) Flatten + Dense: f(x) = (wn)− 1 2
∑ i∈[w],j∈[n] ω2,ijzij(x) , (18)
where ω1,i,β and ω2,ij are the parameters of the first and readout layers, resp.
We can associate a DAG G = (N , E) to the above S-CNN. Let the input, hidden and output nodes be N0 = [1] × [w], N1 = [w] and N2 = {oG} = {∅}, resp. and N = N0 ∪ N1 ∪ N2. Moreover, uv ∈ E if u = oG and v ∈ N1 or u = (i, ) ∈ N1 and v = (0, i) ∈ N0. Let Hv = Rp for v ∈ N0, Hu = Rn if u ∈ N1 and HoG = R. The associated linear operators are given by
Luv = p− 1 2 (ω1,j,β)j∈[n],β∈[p] ∈ Rn×p for (u, v) ∈ N1 ×N0 (19)
LoGv = (wn)− 1 2 (ω2,ij)j∈[n] ∈ Rn if v = (i, ) ∈ N1 (20)
Note that the weights are shared in the first layer but not in the readout layer (i.e., the network has no pooling layer). To compute the NNGP kernel and NTK, we initalize all parameters ω1,i,β and ω2,ij with iid GaussianN (0, 1). Letting n→∞ and denoting tv = xTv x′v/p and t = (tv)v∈N0 , we have
KG(t) = v∈N0 φ∗(tv) and ΘG(t) = v∈N0 φ∗(tv) + φ̇ ∗(tv) (21)
D-CNN. The input space is X = (Sp−1)k L×w ⊆ Rp×1×kL×w, where p is the patch size of the input convolutional layer, k 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 d = p · kL ·w, and the number of input nodes is |N0| = kL ·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, a factor of k by each hidden layer, and is reduced to 1 by the Flatten-Dense layer. Similar to S-CNNs, one can associate a DAG to a D-CNN. Briefly, the input layer has kL × 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.

heading: 4 MAIN RESULTS
text: The goal is to obtain a precise charaterization of the relation between the eigenstructures of K / Θ and the DAG associated to the network’s architectures in the large input dimension setting. As such we consider a sequence of graphs G = ( G(d) ) d∈N, where G
(d) = (N (d), E(d)). We associate a finite set of non-negative numbers ΛG to G, which is called the shape parameters of G,
0 ∈ ΛG ⊆ [0, 1] and |ΛG | <∞. (22)
We need several technical assumptions on G regarding the asymptotic shapes of G(d), which are summarized as Assumption-G in Sec.G of the appendix. We list two of them which are the most crucial ones. (1) For each non-input node u ∈ N (d), there is αu ∈ ΛG with deg(u) ∼ dαu .The weight associated to the edge uv ∈ E(d) is defined to be πuv ≡ αu. (2) For each input node v, there is 0 < αv ∈ ΛG so that the input dimension dv ∼ dαv . Here a ∼ b means a/b ∈ [1/C,C] 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 φ∗ is semi-admissible if, for all r ≥ 1, the r-th derivative of φ∗ at zero is non-vanishing, i.e., φ∗(r)(0) > 0. If, in addition, φ∗(0) = 0 (i.e., the activation is centered), then we say φ is admissible. An activation φ is (semi-)admissible if φ∗ is (semi-)admissible. Note that if φ∗ is (semi-)admissible, then φ̇∗ is semi-admissible.
Assumption-φ. We make the following assumptions on the activations. (a.) If u ∈ N (d)0 , φu is the identity function. (b.) If u /∈ N (d)0 ∪ {oG}, φu is admissible. (c.) If u = oG , φu semi-admissible. Next, we introduce the key concept which defines the spatial distance among nodes. It is the length of the minimum spanning tree (MST) of the nodes.
Definition 1 (Spatial Index of Nodes). Let n ⊆ N (d). The spatial index of n is defined to be
S(n) = min n⊆T ≤G(d) ∑ uv∈E(T ) πuv = min n⊆T ≤G(d) ∑ uv∈E(T ) deg(u; T )αu (23)
where n ⊆ T ≤ G(d) means T is a sub-graph containing n 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 tr : I |N (d) 0 | → I be a monomial, where r : N (d)0 → N|N (d) 0 |. We use n(r) = {v ∈ N (d)0 : rv 6= 0} to denote the support of r and n(r; oG) = n(r) ∪ {oG}.
Definition 2 (Spatial, Frequency and Learning Indices of tr). We say r ∈ N|N (d) 0 | is G(d)-learnable, or learnable for short, if there is a common ancestor node u of n(r) such that φu is semi-admissible. We use A(G(d)) ≡ {r ∈ NN (d) 0 : r is learnable}. For r ∈ A(G(d)), the spatial index, frequency index and the learning index are defined to be,
S(r) := S(n(r; oG)), ℱ(r) := ∑
v∈N (d)0
rvαv and ℒ(r) := S(r) + ℱ(r) , (24)
resp. If r /∈ A(G(d)), we set S(r) = ℱ(r) = ℒ(r) = +∞. Let ℒ(G(d)) denote the sequence of learning indices in non-descending order, i.e.
ℒ(G(d)) ≡ ( ℒ(r) : r ∈ A(G(d)) ) ≡ (· · · ≤ rj ≤ rj+1 ≤ . . . ) (25)
Finally, for each u ∈ N (d)0 , let {Y r,l}l∈[N(du,r)],r∈N be the family of normalized spherical harmonics in Sdu−1, where N(du, r) is the number of degree r spherical harmonics in Sdu−1. Define
Y r,l(ξ) = ∏
u∈N (d)0
Y ru,lu(ξu), l = (lu)u∈N (d)0 ∈ [N(d, r)] ≡ ∏ u∈N (d)0 [N(du, ru)] (26)
for ξ = (ξu) ∈ X . The following is our main theorem. It describes a connection between the architecture of a network and the eigenstructure of its inducing kernels. Theorem 1 (Eigenspace Restructuring). Assume Assumption-G and Assumption-φ. We have the following eigen-decomposition for K = KG(d) or ΘG(d) . For ξ,η ∈ X
K(ξ,η) = ∑
r∈N|N (d) 0 |
λK(r) ∑
l∈N(d,r)
Y r,l(ξ)Y r,l(η), where λK(r) ∼ d−ℒ(r) if r 6= 0 . (27)
Coupling with the observation in Eq. (2), Theorem 1 implies that within t ∼ dr amount of time for gradient flow, when d is sufficiently large, only the eigenfunctions Y r,l with L(r) ≤ r can be learned. By leveraging an analytical result from Mei et al. (2021a) (Sec. 3 Theorem 4), which says under certain regularity conditions on the eigenstructure, the corresponding kernel regression acts as a projection, Theorem 1 establishes a connection between architectures and generalization bounds of NNGP kernel/NTK.
Let σ be the uniform (product) probability measure on X and denote Lp(X ) ≡ Lp(X ,σ). For X ⊆ X and r /∈ L(G(d)), define the regressor and the projection operator to be
RX(f)(x) = K(x,X)K(X,X)−1f(X) and P>r(f) = ∑
r:L(r)>r ∑ l∈N(d,r) 〈f,Y r,l〉L2(X )Y r,l .
Theorem 2. Let G = {G(d)}d, where each G(d) is a DAG associated to the D-CNN in Eq. (13). Let r /∈ L(G(d)) be fixed. Let f ∈ L2(X ) with Eσf = 0. Then for > 0,∣∣∣‖RX(f)− f‖2L2(X ) − ‖P>r(f)‖2L2(X )∣∣∣ = cd, ‖f‖2L2+ (X ), (28) where cd, → 0 in probability as d→∞ over X ∼ σ[d r].
In words, with [dr] many training samples where r /∈ ℒ(G(d)), the NNGP kernel and the NTK are able to learn all Y r,l with L(r) < r but not any eigenfunctions with L(r) > r. In Sec. C, we show that the number of training samples can be reduced by a factor of w if the readout layer Fattening is replaced by the global average pooling.

heading: 5 INTERPRETATION OF THE MAIN RESULTS
text: We say r is the budget index if (1) (Finite Training Set) the training set size m ∼ dr, or (2) (Finite Compute Time) the training set X = X and the total number of training steps/time t ∼ dr.
MLPs and LRLF Interactions Fig. 1 (a). Each G(d) is a linked list. Let v be the input node. Clearly, we have dv = d, i.e., αv = 1 and αu = 0 (since deg(u) = 1) for all other nodes u. As such
A(G(d)) = N\{0} , ℱ(r) = |r|, S(r) = 0, ℒ(r) = |r| and ℒG(d) = (|r| : r ∈ N\{0}). (29) There isn’t any spatial structure since S(r) = 0. Given a budget index r, the kernels can only learn span{Y r,l : r < r , r ∈ N\{0}}. Therefore, MLPs are good at modeling LRLF interactions.
S-CNNs and SRHF Interactions Fig. 1 (b). For one-hidden layer convolutional networks, we have d = p × k0 × w, (i.e. L = 0). The number of input nodes is w ≡ dαw and for each input node v we have dv = p ≡ dαp . We have αp + αw = 1. Since the activation function of the last layer is the identity function, there is no non-linear interactions between different patches and A(G(d)) = {r ∈ N|N (d) 0 |\{0}, |n(r)| = 1}. Therefore for r ∈ A(G(d)),
S(r) = αw , ℱ(r) = |r|αp, ℒG = {αw + |r|αp, r ∈ A(G(d))} (30)
Given a budget index r, the learnable r are the ones r ∈ A(G(d)) with
r > αw + |r|αp = 1 + (|r| − 1)αp ⇒ |r| < 1 + (r − 1)/αp . (31)
When αp = 1 (and thus αw = 0), this S-CNN is essentially a shallow MLP and we have |r| < r. On the other hand, if αp is small (say αp = 0.1), this network can model interactions with much higher frequencies, at the cost of giving up long-range interactions. Therefore, there is 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. 1 (c). Recall that d = p× kL×w. Let p = dαp , k = dαk and w = dαw . Then we have the constraint αp + Lαk + αw = 1. The learnable terms are the ones with
r > S(r) + ℱ(r) = S(r) + |r|αp. (32)
D-CNNs can simultaneously model interpolations (including the two ends) between LRLF and SRHF, i.e. MRMF interactions. Consider two extreme cases. (i.) |n(r)| = 1, i.e. there is an input node v s.t. rv = |r| and thus the non-linear interaction happens within one patch. In this case, the length of the MST reaches its infimum S(r) = αw + Lαk = 1− αp and Eq. (32) implies |r| < (r − 1)/αp + 1, which is exactly Eq. (31). Thus D-CNNs can model SRHF interactions; see Fig. 6 Y∗5. (ii.) |n(r)| = |r|, i.e. rv = 0 or 1 for all v ∈ N (d) 0 . Then S(r) = |r|(1 − αp) and Eq. (32) implies |r| < r, which is the constraint for MLPs. In particular, D-CNNs can model LRLF interactions; see Y5. By varying |r| and then varying |n(r)| in [1, |r], D-CNNs can model various interpolating interactions between LRLF and SRHF.
HR-CNNs Extrapolations and Finer Interpolations Fig. 1 (d). The resolution of the learning indices ℒ(G(d)) can be improved by decreasing αk, αp and increasing L accordingly. E.g., changing αp → αp2 , αk → αk/2 and doubling the number of convolutional layers accordingly, then the resolution of the range of spatial/frequency/learning 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)/αp (almost doubles the upper bound of |r|) and the network can additionally model Ultra-Short-Range-Ultra-High-Frequency interactions (see Y∗5 in Fig. 3) without sacrificing its expressivity, which isn’t the case for S-CNNs due to the space-frequency trade-off. We refer to such networks as high-resolution CNNs (HR-CNNs). 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.

heading: 6 EXPERIMENTS
text: There are many practical consequences due to Theorem 1 and Theorem 2. We focus on two of them which are about the impact of architectures to learning / generalization:
1. Order of Learning (Fig. 1 Green Arrow.) The order of learning is restructured from frequency-based (MLPs) to space-and-frequency-based (CNNs).
2. Learnability (Fig. 1 Cells under the budget line.) With the same budget index, MLPLearnable ( D-CNN-Learnable ( HR-CNN-Learnable. Moreover, the set differences between these learnable sets are captured as in Sec.5.
Overall, we see excellent agreements between predictions from our theorems and experimental results 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 d = p4 and the input X = (Sp−1)p 3 ⊆ Rp4 , where p ∈ N. Note that αp = 1/4. The task is learning a function Y ∈ L2(X ) by minimizing the MSE, where
Y = Y1 + Y2 + Y3 + Y4 + Y5 + Y ∗ 5 + Y6 + Y7 (33)
and each eigenfunction Yi is normalized so that ‖Yi‖22 = ‖Y ‖22/8 = 1. The exact expressions of the functions can be found in Sec.D.
We optimize finite-width networks by SGD+Momentum and infinite-width networks (NNGP and NTK) by kernel regression. We investigate three types of architectures: (1) Dense⊗4, a four hidden layer MLP; (2) Conv(p2)⊗2, a “deep" CNN with filter size/stride k = p2, and (3) Conv(p)⊗4, a “HS"-CNN with filter size/stride k = p. See Fig. 2 and Fig. 6 for a visualization of the associated DAGs, and Sec. F for the code of the architectures. There is an activation φ in each hidden layer, which is chosen so that φ∗ is the Gaussian kernel. For the CNNs, the readout layer(s) is FlattenDense-Act-Dense. We carefully chose the eigenfunctions {Yi} so that they cover a wide range of space-frequency combinations (S(Yi),ℱ(Yi)) w.r.t. Conv(p)⊗4. Under Conv(p)⊗4, the corresponding learning indices are ℒ(Yi) = S(Yi) + ℱ(Yi) = 3αp + iαp = (3 + i)/4. For the learning indices of Yi under Conv(p2)⊗2 or Dense⊗4, see the legends in Fig.3. The purpose of doing so is to create a “separation of learning" under Conv(p)⊗4, since in the large p limit, learning Yi requires d(3+i)/4+ examples/SGD steps. The relation between architectures and learning indices can be “visualized" in Fig. 2 for Y2, which is short-range-low-frequency ( deg(Y2) = 2). Fig. 2 (d) plots the test residual of Y2 vs 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 mt = 32 × 10240 (mv = 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 NeuralTangents (Novak et al., 2020) which is based on JAX (Bradbury et al., 2018).
In Fig.3, for each eigenfunction Yi, we plot 12E|Ŷi(x, t) − Yi(x)| 2 2 against t, where Ŷi(x, t) is the projection of the prediction onto Yi and t is either the training steps (SGD) or training set size (kernels). The expectation is taken over the test set. The budget index r = log(mt)/ log(d) ≈ 2.28. As d = 256 (p = 4) is far from the asymptotic limit, we expect r = 2.28 being a soft cut-off between learnable and non-learnable indices. Although the theorems assume d, p→∞, they do provide good predictions even when d and p are far from∞. We summarize several key observations below.
1. Dense⊗4 (1nd Row.) This architecture can capture all low-frequency interactions (deg = 1, 2, Y1, Y2, Y3, Y5) but fail to learn deg ≥ 3 interactions, as expected. For MLPs, making the network deeper won’t improve its learnability much; see Fig. 7.
2. Conv(p2)⊗2 (2nd Row.) Learning curves of Y2/Y3 are separated from Y5 because the spatial indices of them are different. Higher-frequency (deg = 3, 4) shorter-range interactions (Y4, Y6) become (partially) learnable, as L(Y4) = 84 , L(Y6) = 10 4 < r ≈ 2.28. 3. Conv(p)⊗4 (3rd Row). We see L(Yi) capture the order of learning very/reasonably well in the kernel/SGD setting. To test the ability of Conv(p)⊗4 in modeling ultra-shortrange-ultra-high-frequency interactions, we trace the learning progress of Y∗5 (deg(Y ∗ 5) =
5,L(Y∗5) = 84 .) As expected, while other architectures completely fail to make progress, the NTK/NNGP of Conv(p)⊗4 makes good progress and the SGD even completes the learning process. Interestingly, Y51 is learned faster than Y∗5 in the kernel setting but slower in the SGD setting (even slower than L(Y6) = 104 ), which is unexpected. We suspect it might be due to certain “implicit" effect of SGD. Further investigation is needed to understand it.

heading: 7 CONCLUSION
text: We establish a precise relation among networks’ architectures, eigenstructures of the inducing kernels, 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 a dramatically 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
1Ultra-Long-Range-Low-Frequency under Conv(p)⊗4, with L(Y5) = 8/4 = L(Y∗5)
dynamics of SGD. In addition, it is of great interest and importance to study the combined effect of SGD and architectures in the future.

heading: A ADDITIONAL RELATED WORK
text: Bietti (2021) 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 accuracy on CIFAR-10, matching the performance of a 10-layer Myrtle kernel Shankar et al. (2020). Malach & Shalev-Shwartz (2020) and Li et al. (2020) study the algorithmic benefits of shallow CNNs and show that they outperform MLPs in certain tasks. Xiao & Pennington (2021) and Favero et al. (2021) study the benefits of locality in S-CNNs and argue that locality is the key ingredient to defeat the curse of dimensionality. Mei et al. (2021b) and several papers mentioned above study the benefits of pooling in (S-)CNNs in terms of data efficiency. Their conclusion is similar to that of Theorem 4 (b): pooling improves data efficiency by a factor of the pooling size. In addition, we show that (Theorem 4 (a)) pooling does not improve training efficiency for D-CNNs, extending a result from Xiao & Pennington (2021) which concerns S-CNNs. Finally, Scetbon & Harchaoui (2020) also study the eigenstructures of certain CNN kernels without pooling. Their kernels can be considered as a 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 a precise mathematical characterization of the fundamental role of architectures in (infinite-width) networks through a space-frequency analysis.

heading: B A TOY EXAMPLE AND MOTIVATION
text: In this section, we provide a toy example to help understand the motivation and ideas of the paper. Let’s consider learning the following polynomials in Sd−1 ≡ {x ∈ Rd : ‖x‖2 = 1} using (in)finitewidth neural networks and for concreteness we have set d = 10:
f1(x) = x9, f2(x) = x0x1, f3(x) = x0x8, f4(x) = x6x7(x 2 6 − x27), f5(x) = x2x3x5 (34)
Which architectures (e.g. MLPs, CNNs) can efficiently learn fi or the sum of fi? More precisely, (1) if we have sufficiently amount of training data, how much time (compute) is required to learn fi for a 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 a function fi under an architectureM. Denote this complexity associated to compute and to data by CC(fi;M) and CD(fi;M), resp. With such the complexity properly defined, the questions are reduced to solving the min-max problem minMmaxi{CC/D(fi;M)}, if the task is, e.g, to learn the sum of fi.
Let’s focus on the complexity. For infinite-width MLPs, aka, inner product kernels, it is wellknown that they have the inductive biases (Yang & Salman, 2020; Ghorbani et al., 2020) (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 ∼ dr many data points to learn any degree r polynomials in Rd. 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 our example, for MLP, the order of learning is f1/f2, f3/f5/f4 and it requires about 10/102, 102/104 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, we 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 consecutive terms x6 and x7, which are spatially close; (2) in contrast, f3(x) = x0x8 is of low frequency but the spatial distance between the two interaction terms x0 and x8 are “far" from each other; (3) the function f5(x) = x2x3x5 is somewhere in-between: the order of interaction is 3 (lower than that of f4) and the spatial distance (not yet defined) among interaction terms is conceptually “closer" than that of f3(x) = x0x8, but “farther" than that of f5. Using the terminologies from the introduction, the functions f2/f3/f5/f4 model interactions of types: Short-Range-Low-Frequency/Long-RangeLow-Frequency/Median-Range-Median-Frequency/Short-Range-High-Frequency. By Range we mean the distance among interaction terms and by Frequency we mean the order(=degree) of interactions. 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)
be able to precisely characterize the data and the computation efficiency of learning and their dependence 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=frequency) 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 on how the network organizes these patches hierarchically. Later we show that, in the high-dimensional setting, the learning index provides a sharp characterization for the learnability of eigenfunctions, and certain CNNs can perfectly balance the learning of f3 and f4, i.e., informally
CC/D(f3; CNN) ≈ CC/D(f4; CNN) ≈ CC/D(f2/3; MLP) << CC/D(f3; MLP) (35) See Fig. 3 in the experiment section for more details.

heading: C GLOBAL AVERAGE POOLING (GAP) VS FLATTENING
text: In this section, we compare two readout strategies for CNNs: GAP and Flatten
C.1 INFINITE-TRAINING DATA.
First, let’s state a theorem regarding training efficiency in the infinite-training-data-finite-trainingtime regime, which follows directly from the same arguments in Sec. 2. The theorem requires knowing only the eigenvalues of the kernels.
Let F : L2(X )→ L2(X ) be the solution operator to the kernel descent ḣ = −K(h−f) with initial value ht=0 = 0, i.e. ht ≡ F t(f) ≡ (Id− e−Kt)f . Then we have for t ∼ dr, F t ≈ P<r. Theorem 3. Assume Assumption-G and Assumption-φ andK = KG(d) or ΘG(d) . Let r /∈ L(G(d)) and t ∼ dr. Then for 0 < < inf{|r − r̄| : r̄ ∈ L(G(d))} and f ∈ L2(X ) with Eσf = 0 we have
‖F t(P<rf)− P<rf‖22 . e−d ‖P<rf‖22 and ‖F t(P>rf)− P>rf‖22 & e−d − ‖P>rf‖22
(36) for d sufficiently large.
In words, in the infinite-training-data-finite-training-time regime, within t ∼ dr amount of time only the eigenfunctions Y r,l with L(r) < r are learnable.
C.2 GAP VS FLATTENING.
Let a CNN with and without a global average pooling (GAP) be defined as
CNN+GAP [Input]→ [Conv(p)-Act]→ [Conv(k)-Act]⊗L → [GAP]→ [Dense] (37) CNN+Flatten [Input]→ [Conv(p)-Act]→ [Conv(k)-Act]⊗L → [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. K for 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 does not improve the training efficiency in the infinite-training-data-finite-training-time regime. 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.
Let KSym = KSym or ΘSym be the NNGP kernel or NTK associated to Eq. (37) and LpSym(X ) ≤ Lp(X ) be the subspace of “translation-invariant" functions, whose co-dimension is w. Let FSym, P Sym andRSym be the solution operator, projection operator and regressor associated to KSym, resp. Theorem 4 (Informal). For the architectures defined as in by Eq. (37), we have
(a) Theorem 3 holds with L2(X ), F and P replaced by L2Sym(X ), F Sym and P Sym, resp.
(b) Eq. (28) holds with Lp(X ), R and P replaced by LpSym(X ), RSym and P Sym, resp and with X ∼ σ[dr−αw ] under the assumptions that all activations in the hidden layers are poly-admissible.
Remark 1. Several remarks are in order.
1. In terms of order of learning, our results say that (infinite-width) neural networks progressively learn more complex functions, where complexity is defined to be the learning index L(r). This is consistent with the empirical observation from Nakkiran et al. (2019). Regardless of architectures (MLPs vs CNNs), linear functions have the smallest learning index2 L(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 to learn quadratic functions (L(r) = 2), then cubic functions (L(r) = 3) and so on. While for CNNs, L(r) can be fractional numbers (e.g. L(r) = 5/4, 6/4) and it is possible for the network to learn higher order functions before lower order functions. See Sec.D and Sec. 6 for more details.
2. By NTK-style convergent arguments (e.g., Du et al. (2019)), the above kernel regression results could be extended to the over-parameterized network setting as long as the learning rate of gradient descent is small and the number of channels is sufficiently large (polynomially in d (Huang et al., 2020)).
3. Theorem 4 states that CNN+GAP is better than CNN+Flatten in terms of data efficiency but not training efficiency. In particular, when the dataset size is sufficiently large, CNN+GAP and CNN+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)⊗3-Flatten and Conv(p)⊗3-GAP. 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 is that the architecture Conv(p)⊗3-Flatten ( Conv(p)⊗3-GAP) uses a Flatten-Dense ( GAP-Dense) to map the penultimate layer to the logit layer.
The experimental setup is almost the same as that of Sec. 6 except the eigenfunctions {Yi} are chosen to be in the RKHS of the NNGP kernel/NTK of Conv(p)⊗3-GAP and thus of Conv(p)⊗3-Flatten, i.e., they are shifting-invariant (the invariant group is of order p). Moreover, we still have ℒ(Yi) = (i+ 3)/4. For each Yi, 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 mt = 32 × 10240, the residuals of Yi for GAP and Flatten are almost indistinguishable from each other for i ≤ 6 (recall that ℒ(Y6) = 9/4 = 2.25 < r ≈ 2.28). However, when i = 7 the dataset size (r ≈ 2.28) is relatively small compared to the learning index (ℒ(Y7) = 2.5), GAP outperforms Flatten in learning Y7
To test the robustness of the prediction from Theorem 4 (a) on more practical datasets and models, we perform an additional experiment on ImageNet (Deng et al., 2009) using ResNet (He et al., 2016). We compare the performance of the original ResNet50, denoted by ResNet50-GAP, and a modified version ResNet50-Flatten, in which the GAP readout layer is replaced by Flatten. We use the ImageNet codebase from FLAX3(Heek et al., 2020). In order to 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 sizes4 mi = [m× 2−i/2] for i = 0, . . . , 11, where m = 1281167 is the total number of images in the training set of ImageNet. The networks 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 mi in Fig. 5. Overall, we see that the performance gap between ResNet50-GAP and ResNet50-Flatten shrink substantially as the training set size increases. E.g, using 1/8 of the training set (i.e. i = 6), the top 1 accuracy between the two is 19.3% (57.7% GAP vs 38.4% Flatten). However, with the whole training set (i.e., m0), 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. E.
2Ignoring the constant functions. 3https://github.com/google/flax/blob/main/examples/imagenet/README.md 4Standard data-augmentation is applied for each i; see input_pipeline.py.

heading: D DAGS, EIGENFUNCTIONS, SPATIAL INDEX, AND FREQUENCY INDEX.
text: 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 (Sp−1)p 3 ⊆ Rp4 be the input space, where d = p4 is the input dimension. We use x ≡ (xk)k∈[p]4 ∈ (Sp−1)p 3
to denote one input (an image), where k = [k1,k2,k3,k4] ∈ [p]4. In addition, we treat [p]4 as a group (i.e. with circular boundaries) and let e1 = [1, 0, 0, 0], e2 = [0, 1, 0, 0] , e3 = [0, 0, 1, 0] and e4 = [0, 0, 0, 1] be a set of generator/basis of the group. Note that each input xk is partitioned into p3 many patches: {xk1,k2,k3,: : k1,k2,k3 ∈ [p]}.
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(p2)⊗2 CNN(p)⊗4
Y1(x) = ∑
k∈[p−1]4 c (1) k xk 1 0/1
1 2 / 1 2
3 4 / 1 4
Y2(x) = ∑
k∈[p−1]4 c (2) k xkxk+e4 2 0/2
1 2 / 2 2
3 4 / 2 4
Y3(x) = ∑
k∈[p−1]4 c (3) k xk+e3xk+e4 2 0/2
1 2 / 2 2
4 4 / 2 4
Y4(x) = ∑
k∈[p−1]4 c (4) k xk+e3+e4xk+e4xk 3 0/3
1 2 / 3 2
4 4 / 3 4
Y∗5(x) = ∑
k∈[p−1]4 c (5∗) k xkxk+e4xk+2e4(x 2 k − x2k+e4) 5 0/5
1 2 / 5 2
3 4 / 5 4
Y5(x) = ∑
k∈[p−1]4 c (5) k xkxk+e1 2 0/2
2 2 / 2 2
6 4 / 2 4
Y6(x) = ∑
k∈[p−1]4 c (6) k xkxk+e3(3x 2 k−e3 − x 2 k) 4 0/4
1 2 / 4 2
5 4 / 4 4
Y7(x) = ∑
k∈[p−1]4 c (7) k xk−e3+e4xk+e2(3x 2 k − x2k−e3+e4) 4 0/4
1 2 / 4 2
6 4 / 4 4
Each (eigen)function Yi is a linear combination of basis eigenfunction of the same type, in the sense they have the same eigenvalue and the same spatial/frequency/learning indices. The coefficients c(i)k are first sampled from standard Gaussians iid and then multiplied by an i-dependent constant so that Yi has unit norm5. In the experiments, p is chosen to be 4 and the target is defined to be sum of them
Y = ∑ Yi (39)
Since they are orthogonal to each other, ‖Y ‖22/8 = ‖Yi‖22 = 1 where the L2-norm is taken over the uniform distribution on (Sp−1)p 3
. In the experiment when we compare Flatten and GAP ( Fig. 4), we set all c(i)k to be the same (note that we also remove Y5 from the target function), so that the functions are learnable by convolutional networks with a GAP readout layer.
We compare three architectures. Fig. 6 Column (a) MLP⊗4, a (four-layer) MLP, the most coarse architecture used in the paper. Fig. 6 Column (b), CNN(p2)⊗2, a“D"-CNN that contains two convolutional layers with filter size/stride equal to p2. Fig. 6 Column (c), CNN(p)⊗4, a “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. 4, 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/Flatten.
We show how to compute the frequency index, the spatial index and the learning index through three examples. We focus on Y2 / Y3 / Y∗5 which have degree 2 / 2 / 5, resp. The indices of other eigenfunctions can be computed using the same approach. We use Dashed Lines to represent either an edge connecting an input node to a node in the first-hidden layer or an edge associated to a dense layer. In either case, the corresponding output node of the edge has degreeO(1) and thus the weights (of the DAGs) of such edges are always 0. Only Solid Lines are relevant in computing the spatial index. Since each Yi 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 = 0 component, which corresponds to the
5In our experiments, they are normalized over the test set.
colored path in each DAG. Recall that p = 4, d = p4 = 256 andmt = 32×10240 ∼ d2.28 (training set size), i.e. the budget index is roughly r = 2.28.
(a.) MLP Column (a) Fig. 6. The NTK and NNGP kernels are inner product kernels and the associated DAGs are linked lists. The corresponding DAG has only one input node whose dimension is equal to d = p4. The spatial index is always 0 since the degree of each hidden node is 1 (since 1 = d0) and the frequency index is equal to the degree of the eigenfunctions. Thus ℒ(Y2) = ℒ(Y3) = 2 and ℒ(Y∗5) = 5. Changing the number of layers won’t change the learning indices. In sum, learning Y2/Y3/Y∗5 using infinitewidth MLP requires d2 + /d2 + /d5 +
many samples /SGD steps. Clearly, Y∗5 is completely unlearnable as r = 2.28 << 5. In the MSE plot Y∗5 (5-th row in Fig. 6), the Red Lines does not make any progress
(b.) CNN(p2)⊗2 Column (b) Fig. 6. The input image is partitioned into p2 patches and each patch has dimension p2. The second layer of the DAG has p2 many nodes, each node represents one pixel (with many channels) in the first hidden layer of a finite-width ConvNet. After one more convolutional layer with filter size/stride p2, 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 to 1, which corresponds to the Act-Dense layer. The frequency index ℱ(Y2) = 212 = 1. This is because the degree of Y2 is 2 and the input dimension of a node is p2 = d1/2. The spatial index is equal to 1/2, since the minimum tree containing xkxk+e4 has only one non-zero edge (Solid Lines) whose weight is equal to 1/2 (since the degree of the output node is p2 = d1/2); see the colored paths in Fig. 6 Column (b). Therefore the learning index of ℒ(Y2) = 1 + 1/2 = 3/2. Similarly ℒ(Y3) = 1 + 1/2 = 3/2, as the term xk+e3xk+e4 are lying in the same patch of size p2 for all k, and ℒ(Y∗5) = 5/2 + 1/2 = 3. In sum, learning Y2/Y3/Y ∗ 5 using
infinite-width CNN(p2)⊗2 requires d1.5 + /d1.5 + /d3 +
many samples /SGD steps. While neither infinite-width CNN(p2)⊗2 nor MLP⊗4 distinguishes Y2 from Y3, CNN(p2)⊗2 does improve the learning efficiency: d2 + → d1.5+ . Note that Y∗5 is still unlearnable as r = 2.28 < 3 = ℒ(Y∗5). In the MSE plot Y ∗ 5 (5-th row in Fig. 6), the Orange Line does
not make any progress. (c.) CNN(p)⊗4 Column (c) Fig. 6. The input image is partitioned into p3 patches and each
patch has dimension p. The second/third/fourth/output layer of the DAG has p3/p2/p/1 many nodes. The frequency indices are: ℱ(Y2) = ℱ(Y3) = 2 14 = 1/2 and ℱ(Y ∗ 5) = 5 14 = 5/4. This is because the size of input nodes is reduced to p = d 1/4. Unlike the above cases, the spatial indices become different. The two interacting terms in xkxk+e4 and the three interacting terms in xk+e4xk+2e4(x 2 k − x2k+e4) are in the same input node while the two interacting terms in xk+e3xk+e4 and are in two different input nodes. As a consequence, the minimum spanning tree (MST) that contains xk and xk+e4 and the one contains xk, xk+e4 and xk+2e4 are the same. They have 3 solid lines. However, the MST containing xk+e3 and xk+e4 has 4 solid lines. Therefore S(Y2) = S(Y∗5) = 3 × 14 and S(Y3) = 4 × 14 . As such, ℒ(Y2) = 5 4 , ℒ(Y3) = 6 4 and ℒ(Y ∗ 5) = 8 4 . In sum, learning Y2/Y3/Y∗5 using infinite-width CNN(p) ⊗4 requires d1.25 + / d1.5 + / d2 +
many samples /SGD steps, resp. Now ℒ(Y∗5) = 2. < 2.28 and in the MSE plot Y ∗ 5 (5-th row in Fig. 6), the Blue Line does make significant progress (the MSE is reduced to ∼ 0.2.)

heading: E FIGURE ZOO
text: E.1 MLPS: DEPTH 6= HIERARCHY
We compare a one hidden layer MLP and a four hidden layer MLP in Fig. 7. Unlike CNNs, increasing the number of layers does not improve the performance of MLPs much for both NTK regression and SGD. This is 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

heading: F ARCHITECTURE SPECIFICATIONS
text: In this section, we provide the details of the architectures used in the experiments.

heading: G ASSUMPTIONS
text: Assumption-G. Let G = (G(d))d. There are absolute constants c, C > 0 such that
(a.) For each non-input node u ∈ N (d), there is αu ∈ ΛG such that
cdαu ≤ deg(u) ≤ Cdαu . (40)
For each edge uv ∈ E(d), its weight is defined to be ωuv ≡ αu. (b.) For each input node v, there are dv ∈ N and 0 < αv ∈ ΛG such that
cdαv ≤ dv ≤ Cdαv and ∑
v∈N (d)0
αv = 1. (41)
(c.) Let N (d)1 ≡ {u : ∃v ∈ N (d) 0 s.t.uv ∈ E(d)} be the collection of nodes in the first hidden
layer. We assume that for every u ∈ N (d)1 , αu = 0 and all children of u are input nodes.
(d.) For every v ∈ N (d), |{u : uv ∈ E(d)}| ≤ C. Moreover, the number of layers is uniformly bounded, namely, for any node u, any path from u to oG contains at most C edges.
The first two assumptions help to create spectral gaps between eigenspaces. When d is not large, “finite-width" effect is no 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.
from neural_tangents import stax
def MLP(width=2048, depth=1, W_std=0.5, activation=stax.Rbf()):
layers = []
for _ in range(depth):
layers += [stax.Dense(width, W_std=W_std), activation]
layers += [stax.Dense(1)]
return stax.serial(*layers)
def CNN(width=512, ksize=4, depth=1, W_std=0.5, activation=stax.Rbf(), readout=stax.Flatten(),
act_after_readout=True):
layers = []
conv_op = stax.Conv(width, (ksize, 1), strides=(ksize, 1), W_std=W_std, padding='VALID')
for _ in range(depth):
layers += [conv_op, activation]
layers += [readout]
if act_after_readout:
layers += [stax.Dense(width * 4, W_std=W_std), activation]
layers += [stax.Dense(1)]
return stax.serial(*layers)
p = 4 # input shape: (-1, p**4, 1, 1)
S_MLP = MLP(depth=1) # Shallow MLP
D_MLP = MLP(depth=4) # Deep MLP
S_CNN = CNN(ksize=p, depth=1, act_after_readout=False) # Shallow CNN
# One layer CNN with an additional activation-dense layer
S_CNN_plus_Act = CNN(ksize=p, depth=1, act_after_readout=True)
D_CNN = CNN(ksize=p**2, depth=2) # Deep CNN
HR_CNN = CNN(ksize=p, depth=4) # High-resolution CNN
# High-resolution CNN with global average pooling readout
HR_CNN_GAP = CNN(ksize=p, depth=4, readout=stax.GlobalAvgPool(), act_after_readout=False)
# High-resolution CNN with flattening as readout
HR_CNN_Flatten = CNN(ksize=p, depth=4, act_after_readout=False)
Listing 1: Definitions of MLPs, S-CNN, D-CNN and HR-CNN used in the experiments. The architectures used in the experiments of Fig. 3 are defined as follows. Dense⊗4 = D_MLP, Conv(p2)⊗2 = D_CNN, Conv(p)⊗4 = HR_CNN. The one layer MLP and one layer CNN used in Fig. 7 are S_MLP and S_CNN_plus_Act, resp.

heading: H PROOF OF THE EIGENSPACE RESTRUCTURING THEOREM.
text: Lemma 1. Let r ∈ N (d)0 . Then
KG(0), ΘG(0) = 0 (42)
and for r 6= 0, for d large enough,
K(r)G (0), Θ (r) G (0) ∼ d −S(r) and ‖K(r)G ‖∞, ‖Θ (r) G ‖∞ . d −S(r) (43)
Proof. Recall that the recursion formulas for K and Θ are
Ku(t) = φ∗u ( v:uv∈E Kv(t) )
(44)
Θu(t) = φ̇ ∗ u ( v:uv∈E Kv(t) ) v:uv∈E (Kv(t) + Θv(t)) (45)
For convenience, define K, Θ, K̇ as follows
Ku(t) = v:uv∈E Kv(t) (46)
Θu(t) =
v:uv∈E
Θv(t) (47)
K̇u(t) = φ̇∗u ◦Ku(t) . (48)
Note that Ku(t) = φ∗u ◦Ku(t) and Θ(t) = K̇u(t)(Ku(t) + Θu(t)) .
The equalities Ku(0) = Θu(0) = 0 follow easily from recursion and the fact φ∗u(0) = 0 for all u ∈ N (d). We induct on the tuple (h, |r|), where h ≥ 0 is 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 I: |r| = 1 and h ≥ 0 is any integer. Let u ∈ N0 be such that r = eu, where {eu}u∈N (d)0 is the standard basis. Then
∂tuKG(t) = ∑
path∈P(u→oG)
∏ v∈path deg(v)−1φ̇∗v ◦Kv(t) ∼ ∑
path∈P(u→oG)
∏ v∈path d−αv φ̇∗v ◦Kv(t)
(49)
Here P(u→ u′) represents the set of paths from u to u′. By Assumption-G and Assumption-φ, |P(u→ oG)| is uniformly bounded and φ̇∗v(0) > 0 for all hidden nodes v. Therefore
∂tuKG(0) ∼ ∑
path∈P(u→oG)
d− ∑ v∈path αv φ̇∗v ◦Kv(0)
= ∑
path∈P(u→oG)
d− ∑ v∈path αv φ̇∗v(0)
∼ max path∈P(u→oG)
d− ∑ v∈path αv
= d−S(eu) = d−S(r)
In the above, we have used Kv(0) = 0 (which is due to φ∗(0) = 0.) The second estimate ‖∂tuKG‖∞ . d−S(r) follows from |φ̇∗v ◦Kv(t)| . 1.
Base Case II: h = 0 and |r| ≥ 1 is any number. Note that G(d) has no hidden layer and all input nodes are linked to the output node oG . The case when the activation φoG is the identity function is obvious and we assume φoG is admissible.
∂rtKG(t) = deg(oG) −|r|φ∗oG (|r|) ( u∈N (d)0 tu ) .
This implies Eq. (43) since S(r) = 0, deg(oG) . 1 by Assumption-G and φ∗oG (|r|)(0) > 0 by Assumption-φ.
Induction: |r| ≥ 2, h ≥ 1 and r ∈ A(G(d)). We only prove the first estimate in Eq. (43) since the other one can be proved similarly. WLOG, we assume φoG is not the identity function and hence is
semi-admissible. Let u ∈ N (d)0 be such that ru ≥ 1 and denote r̄ = r − eu. Then ∂rtKG(t) ∣∣∣ t=0 = ∂r̄t (∂ eu t KG(t)) ∣∣∣ t=0 = ∑ oGv∈E ∂eut Kv 6=0 deg(oG) −1∂r̄t ( K̇oG (t)∂ eu t Kv(t) ) ∣∣∣ t=0 (50)
= ∑ oGv∈E ∂eut Kv 6=0 ∑ r̄1+r̄2=r̄ deg(oG) −1 ( ∂r̄1t K̇oG (t) ∂ r̄2+eu t Kv(t) ) ∣∣∣ t=0
(51)
∼ ∑ oGv∈E ∂eut Kv 6=0 ∑ r̄1+r̄2=r̄ deg(oG) −1d−S(r̄1)d−S(n(r̄2+eu;v)) (52)
∼ ∑ oGv∈E ∂eut Kv 6=0 ∑ r̄1+r̄2=r̄ d−S(r̄1)d−(αoG+S(n(r̄2+eu;v))) (53)
∼ sup oGv∈E ∂eut Kv 6=0 sup r̄1+r̄2=r̄
d−(S(r̄1)+αoG+S(n(r̄2+eu;v))) (54)
We have applied induction twice in Eq. (52): one to obtain the estimate ∂r̄1t K̇ ∗ oG (0) ∼ d −S(r̄1) (with |r̄1| < |r| and φ̇∗oG semi-admissible) and one to ∂ r̄2+eu t Kv(t) ∼ d−S(n(r̄2+eu;v)), in which the subgraph with v as the output node has depth at most (h − 1). The last line follows from that both the cardinality of the tuple (r̄1, r̄2) with r̄1, r̄2 ≥ 0 and r̄1 + r̄2 = r̄ and the cardinality of v ∈ N (d)0 with oGv ∈ E and ∂eut Kv 6= 0 are finite and independent of d. From the definition of MST, it is clear that for all (r̄1, r̄2)
S(r̄1) + αoG + S(n(r̄2 + eu; v)) ≥ S(r̄1) + S(r̄2 + eu) ≥ S(r) (55) It remains to show that there exists at least one pair (r̄1, r̄2) such that the above can be an equality. Let T ⊆ G(d) be a MST containing all nodes in n(r). If oG has only one child v in T , then we choose r̄1 = 0 and notice that
S(r̄1) + αoG + S(n(r̄2 + eu; v)) = 0 + S(r2 + eu) = S(r) (56)
since S(r̄1) = 0 and r̄2 + eu = r. Else, T contains at least two children and therefore at least two disjoint branches split from oG . Let Tu ⊆ T be the branch that contains u and choose r̄2 ≤ r̄ be such that all the nodes of (r̄2 + eu) are contained in Tu and all the nodes of r̄1 ≡ r− (r̄2 + eu) are contained in T \Tu. Clearly
S(r) = S(r̄1) + S(r̄2 + eu) = S(r̄1) + S(n(r̄2 + eu; v)) + αoG , (57)
where v is the unique child of oG in Tu. 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 ≥ 1 and r ∈ A(G(d)). Recall that the formula of Θ is
Θu(t) = φ̇ ∗ u ( v:uv∈E Kv(t) ) v:uv∈E (Kv(t) + Θv(t)) (58)
For r ∈ N (d)0 ,
∂rtΘoG (t) = ∑
r̄1+r̄2=r
∂r̄1t φ̇ ∗ oG ( v:oGv∈E Kv(t) ) ∂r̄2t v:oGv∈E (Kv(t) + Θv(t)) (59)
Note that φ̇∗oG is semi-admissible. We apply the result of K to conclude that
∂r̄1t φ̇ ∗ oG ( v:oGv∈E Kv(t) ) ∣∣∣∣∣
t=0 ∼ d−S(r1) (60)∥∥∥∥∂r̄1t φ̇∗oG ( v:oGv∈E Kv(t) )∥∥∥∥ ∞ . d−S(r̄1) (61)
and the inductive step to conclude that
∂r̄2t
v:oGv∈E
(Kv(t) + Θv(t)) ∣∣∣∣∣ t=0 ∼ ∑
v:oGv∈E ∂ r̄2 t (Kv+Θv)6≡0
d−S(r̄2) if r̄2 6= 0 else 0 (62)
∂r̄2t
v:oGv∈E
(Kv(t) + Θv(t)) . ∑
v:oGv∈E ∂ r̄2 t (Kv+Θv)6≡0
d−S(r̄2) . (63)
Note that |{v : oGv ∈ E(d) and ∂r̄2t (Kv + Θv) 6≡ 0}| . 1 .
Thus
‖∂rtΘoG (t)‖∞ . ∑
r̄1+r̄2=r
d−S(r̄1)−S(r̄2) . d−S(r). (64)
To control the lower bound, let T be a MST containing n(r). If deg(oG ; T ) = 1, then we can choose r̄1 = 0 and r̄2 = r 6= 0. Notice that there is at least one child node v of oG with ∂r̄2t (Kv+Θv) 6≡ 0. Therefore ∑
v:∂ r̄2 t (Kv+Θv)6≡0
d−S(r̄2) & d−S(r̄2) = d−S(r) (65)
Combining with
φ̇∗oG ( v:oGv∈E Kv(0) ) = φ̇∗oG (0) > 0 (66)
we have
∂rtΘoG (0) & d −S(r)
It remains to handle the deg(oG ; T ) > 1 case. We choose (r̄1, r̄2) such that one branch of T is the MST that contains n(r̄2) and the oG and the remaining branch(es) is a MST that contains n(r̄1) and the oG . Then
∂rtΘoG (0) &∂ r̄1 t φ̇ ∗ oG ( v:oGv∈E Kv(t) ) ∂r̄2t v:oGv∈E (Kv(t) + Θv(t)) ∣∣∣∣∣ t=0
&d−S(r1)−S(r2) = d−S(r)
H.1 LEGENDRE POLYNOMIALS, SPHERICAL HARMONICS AND THEIR TENSOR PRODUCTS.
Our notation follows closely from (Frye & Efthimiou, 2012).
Legendre Polynomials. Let din ∈ N∗ and ωdin be the measure defined on the interval I = [−1, 1]
ωdin(t) = (1− t2)(din−3)/2 (67)
The Legendre polynomials6 {Pr(t) : r ∈ N} is an orthogonal basis for the Hilbert space L2(I, ωdin), i.e. ˆ
I Pr(t)Pr′(t)ωdin(t)dt = 0 if r 6= r′ else N(din, r)−1 ( |Sdin−1| |Sdin−2| ) (68)
Here Pr(t) is a degree r polynomials with Pr(1) = 1 that satisfies the formula below, N(din, r) is the cardinality of degree r spherical harmonics in Rdin and |Sdin−1| is the measure of Sdin−1.
6More accurate, this should be called Gegenbauer Polynomials. However, we decide to stick to the terminology in (Frye & Efthimiou, 2012)
Lemma 2 (Rodrigues Formula. Proposition 4.19 (Frye & Efthimiou, 2012)).
Pr(t) = crω −1 din (t)
( d
dt
)r (1− t2)r+(din−3)/2 , (69)
where
cr = (−1)r
2r(r + (din − 3)/2)r (70)
In the above lemma, (x)l denotes the falling factorial
(x)l ≡ x(x− 1) · · · (x− l + 1) (71) (x)0 ≡ 1 (72)
Spherical Harmonics. Let dSdin−1 define the (un-normalized) uniform measure on the unit sphere Sdin−1. Then
|Sdin−1| ≡ ˆ Sdin−1 dSdin−1 = 2πdin/2 Γ(din2 ) . (73)
The normalized measure on this sphere is defined to be
dσdin = 1
|Sdin−1| dSdin−1 and ˆ Sdin−1 dσdin = 1 . (74)
The spherical harmonics {Yr,l}r,l in Rdin are homogeneous harmonic polynomials that form an orthonormal basis in L2(Sdin−1, σdin)ˆ
ξ∈Sdin−1 Yr,l(ξ)Yr′,l′(ξ)dσdin = δ(r,l)=(r′,l′) . (75)
Here Yr,l denotes the l-th spherical harmonic whose degree is r, where r ∈ N, l ∈ [N(din, r)] and
N(din, r) = 2r + din − 2
r
( din + r − 3 r − 1 ) ∼ (din)r/r! as din →∞ . (76)
The Legendre polynomials and spherical harmonics are related through the addition theorem. Lemma 3 (Addition Theorem. Theorem 4.11 (Frye & Efthimiou, 2012)).
Pr(ξ T η) =
1
N(din, r) ∑ l∈[N(din,r)] Yr,l(ξ)Yr,l(η), ξ, η ∈ Sdin−1 . (77)
Tensor Products. Let p = |N (d)0 |, d = (du)|u∈N (d)0 |, r ∈ N |N (d)0 | ' Np, I |N (d) 0 | ' Ip = [−1, 1]p and ω = ⊗
u∈N (d)0 ωpdu be the product measure on I p. Then the (product of) Legendre polynomials
Pr(t) = ∏
u∈N (d)0
Pru(tu) , t = (tu)u∈N (d)0 ∈ Ip , (78)
which form an orthogonal basis for the Hilbert space L2(Ip,ω) = ⊗
u∈N (d)0 L2(I, ωdu). Similarly,
the tensor product of spherical harmonics Yr,l = ∏
u∈N (d)0
Yru,lu , l = (lu)u∈N (d)0 ∈ [N(d, r)] ≡ ∏ u∈N (d)0 [N(du, r)] (79)
form an orthonormal basis for the product space L2(X ,σ) ≡ ⊗
u∈N (d)0
L2(Sdu−1, σdu) (80)
Elements in the set {Yr,l}l∈[N(d,r)] are called degree (order) r spherical harmonics in L2(X ,σ) and also degree r spherical harmonics if |r| = r ∈ N.
Theorem 5. We have the following, for K = KG(d) or K = ΘG(d) K(t) = ∑
r∈NN (d) 0
K̂(r)Pr(t) with K̂(r) ∼ d−S(r) if r 6= 0 else 0. (81)
Note that Theorem 1 follows from this theorem and the addition theorem.
Proof of Theorem 1. Assume r 6= 0. Indeed, setting
ξ = (ξu)u∈N (d)0 ∈ X , η = (ηu)u∈N (d)0 ∈ X and t = (tu)u∈N (d)0 = (ξ T u ηu/du)u∈N (d)0 ,
we have Pr(t) = ∏
u∈N (d)0
Pru(tu) = ∏
u∈N (d)0
N(du, ru) −1 ∑ lu∈N(du,ru) Yru,lu(ξu/ √ du)Yru,lu(ηu/ √ du)
(82) = N(d, r)−1 ∑
l∈[N(d,r)]
Y r,l(ξ)Y r,l(η) . (83)
Then Theorem 1 follows by noticing
K(r)N(d, r)−1 ∼ d−S(r)d − ∑ u∈N(d)0 ruαu = d−ℒ(r) (84)
Proof of Theorem 5. From the orthogonality,
K̂(r) = 〈K,Pr〉/‖Pr‖L2(Ip,ω)2 (85) We begin with the denominator. Note that
‖Pr‖L2(Ip,σ)2 = ∏
u∈N (d)0
‖Pru‖2L2(I,ωdu ) = N(d; r) −1 ∏ u∈N (d)0 (|Sdu−1|/|Sdu−2|) (86)
By applying Lemma 2, integration by parts and continuity of K(r) on the boundary ∂Ip
〈K,Pr〉L2(Ip,ω) = cr ˆ Ip K(t)
( d
dt
)r ( 1− t2 )r+(d−3)/2 dt (87)
= (−1)rcr ˆ Ip K(r)(t) ( 1− t2 )r+(d−3)/2 dt (88) = (−1)rcr (M(K,d) + (K,d)) (89)
where K(r) is the r derivative of K, the coefficient cr is given by Lemma 2
cr = ∏
u∈N (d)0
cru = ∏
u∈N (d)0
(−1)ru 2ru(ru + (d− 3)/2)ru
∼ ∏
u∈N (d)0
(−1)rud−ruu = (−1)rd−r (90)
and the major and error terms are given by
M(K,d) ≡ K(r)(0) ˆ Ip ( 1− t2 )r+(d−3)/2 dt = K(r)(0) ∏ u∈N (d)0 |S2ru+du−1| |S2ru+du−2|
(91)
(K,d) ≡ ˆ Ip (K(r)(t)−K(r)(0)) ( 1− t2 )r+(d−3)/2 dt (92)
The mean value theorem gives |K(r)(t)−K(r)(0)| ≤ ∑
u∈N (d)0
‖K(r+eu)‖L∞(Ip)|tu| (93)
and the error term | (K,d)| is bounded above by ˆ Ip ( 1− t2 )r+(d−3)/2 dt ∑ u∈N (d)0 ‖K(r+eu)‖L∞(Ip) (´ I |tu| ( 1− t2u )ru+(du−3)/2 dtu´ I (1− t2u) ru+(ru−3)/2 dtu ) (94)
∼ ∏
u∈N (d)0
|S2ru+du−1| |S2ru+du−2| ∑ u∈N (d)0 ‖K(r+eu)‖L∞(Ip)d−1u ( |S2ru+du−1| |S2ru+du−2| )−1 . (95)
Since for any α ∈ N, as du →∞,
|Sα+du−1| |Sα+du−2| = π 1 2 Γ((α+ du − 1)/2)/Γ((α+ du)/2) ∼ π 1 2 (du/2) − 12 ∼ (du)− 1 2 , (96)
we have
| (K,d)| . ∑
u∈N (d)0
‖K(r+eu)‖L∞(Ip)d − 12 u ∏ u∈N (d)0 |S2ru+du−1| |S2ru+du−2| . (97)
We claim that (which will be proved later)∑ u∈N (d)0 ‖K(r+eu)‖L∞(Ip) . d−S(r) (98)
which implies
〈K,Pr〉L2(Ip,ωpdin ) = cr
( K(r)(0) +O ( d−S(r)( min
u∈N (d)0 du) − 12 )) ∏ u∈N (d)0 |S2ru+du−1| |S2ru+du−2| (99)
Plugging back to Eq. (85), we have
K̂(r) = (−1)rcrN(d, r) ( K(r)(0) +O ( d−S(r)( min
u∈N (d)0 du) − 12 )) ∏ u∈N (d)0 |S2ru+du−1| |S2ru+du−2| ( |Sdu−1| |Sdu−2| )−1 (100)
Since, for r fixed and as du →∞ for all u ∈ N (d)0
cr (−1)rd−r → 1 and N(d, r) dr/r! → 1 and  ∏ u∈N (d)0 |S2ru+du−1| |S2ru+du−2| ( |Sdu−1| |Sdu−2| )−1→ 1 (101)
and thus
K̂(r) ∼ r!−1 ( K(r)(0) +O ( d−S(r)( min
u∈N (d)0 du) − 12
)) (102)
It remains to verify Eq. (98). By Lemma 1, we only need to show that∑ u∈N (d)0 d−S(r+eu) . d−S(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 node of n(r). We split N (d)0 into two disjoint sets
Q(r) ≡ {u ∈ N (d)0 : ∃v ∈ C(r) s.t. P(u→ v) 6= ∅} and N (d) 0 \Q0(r) .
For u /∈ Q(r), we have S(r + eu) = S(r) + S(eu) and hence∑ u/∈Q(r) d−S(r+eu) = ∑ u/∈Q(r) d−S(r)−S(eu) = d−S(r) ∑ u/∈Q(r) d−S(eu) . d−S(r) . (104)
In the last inequality above, we have used∑ u/∈Q(r) d−S(eu) ≤ ∑
u∈N (d)0
d−S(eu) ∼ 1 . (105)
To estimate the remaining, we use induction. Note that |C(r)| is finite and independent of d. Then∑ u∈Q(r) d−S(r+eu) ≤ ∑ v∈C(r) ∑ u∈Q(r) d−αoG−S(n(r+eu;v)) (106)
= d−αoG ∑
v∈C(r) ∑ u∈Q(r) d−S(n(r+eu;v)) (107)
. |C(r)|d−αoG max v∈C(r) d−S(n(r;v)) ∼ d−S(r) (108)
We have used induction on the sub-graph with v as the output node.

heading: I PROOF OF THEOREM 2
text: Let G(d) be a DAG associated to the convolutional networks whose filter sizes in the l-th layer is kl = [d
αl ], for 0 ≤ l ≤ L+1, in which we treat the flatten-dense readout layer as a convolution with filter size [dαL+1 ]. Note that we have set αp = α0 and αw = αL+1. We also assume an 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 r ∈ L(G(d)). Then dim ( span { Y r,l : L(r) = r, l ∈N(d, r) }) ∼ dr (109)
To prove Theorem 2, we only need to verify the assumptions of Theorem 4 in Mei et al. (2021a). For convenience, we briefly recap the assumptions and results from Mei et al. (2021a) in Sec.L.
It is convenient to group the eigenspaces together according to the learning indices L(G(d)). Recall that L(G(d)) = (r1 ≤ r2 ≤ r3 . . . ). Let
Ei = span{Y r,l : L(r) = ri} (110) Then by Theorem 1 and Lemma 4,
dim(Ei) ∼ dri and λ(g) ∼ d−ri ∀g ∈ Ei, g 6= 0 , (111) where λ(g) denote the eigenvalue of g. We proceed to verify Assumptions 4 and 5 in Sec. L. They follow directly from Theorem 1, Lemma 4 and the hypercontractivity of spherical harmonics Beckner (1992).
I.1 VERIFYING Assumption 4
We need the following.
Proposition 1. For 0 < s ∈ R, let Ds = span{Y r,l : |L(r)| < s}. Then for f ∈ Ds,
‖f‖2q ≤ (q − 1)s/α0‖f‖22 (112)
Proof of Proposition 1. The lemma follows from the tensorization of hypercontractivity. Let f =∑ k≥0 Yk ∈ L2(Sn) where Yk is a degree k spherical harmonics in Sn. Define the Poisson semigroup operator
P f(x) = ∑ k≥0 kYk(x) (113)
Then we have the hypercontractivity inequality (Beckner, 1992), for 1 ≤ p ≤ q and ≤ √
p−1 q−1
‖P f‖Lq(Sn) ≤ ‖f‖Lp(Sn) (114)
One can then tensorize (Beckner, 1975) it to obtain the same bound in the tensor space. Lemma 5 (Corollary 11 Montanaro (2012)). Let f : (Sn)k → R. If 1 ≤ p ≤ q and ≤ √ p−1 q−1 , then
‖P⊗k f‖Lq((Sn)k) ≤ ‖f‖Lp((Sn)k) . (115)
Let f = ∑ r,l ar,lY r,l ∈ Ds. Choosing = √ 1 q−1 and p = 2 in the above lemma, we have
‖f‖2q = ‖ ∑ r,l ar,lY r,l‖2q (116)
= ‖P⊗|N (d) 0 | ∑ r,l ar,l −rY r,l‖2q (117)
≤ ‖ ∑ r,l ar,l −rY r,l‖22 (118)
= ∑ r,l a2r,l −2r‖Y r,l‖22 (119)
≤ −2 max |r| ∑ r,l a2r,l‖Y r,l‖22 (120)
= (q − 1)max |r|‖f‖22 ≤ (q − 1)s/α0‖f‖22 (121)
Since r /∈ ℒ(G(d)), there is a j such that rj < r < rj+1. Let n(d) = dr and
m(d) = dim ( span{Y r,l : ℒ(r) ≤ rj} ) = dim(span ⋃ i≤j Ei) (122)
Clearly, m(d) ∼ drj . We list all eigenvalues of K in non-ascending order as {λd,i}. In particular, we have
λd,m(d) ∼ d−rj > d−r > d−rj+1 ∼ λd,m(d)+1 . (123)
Assumption 4 (a). We choose u(d) to be
u(d) = dim span ⋃ i:ri≤2r+100 Ei  . (124) Assumption 4 (a) follows from Proposition 1.
Assumptions 4 (b). Let s = inf{r̄ ∈ ℒ(G(d)) : r̄ > 2r + 100}. For l > 1, we have∑ j=u(d)+1 λld,j ∼ ∑ ri:ri≥s (d−ri)l dim(Ei) ∼ d−s(l−1) (125)
which also holds for l = 1 since ∑ j=u(d)+1 λd,j ∼ 1 (126)
Thus ( ∑ j=u(d)+1 λ l d,j)
2∑ j=u(d)+1 λ 2l d,j ∼ d −2s(l−1) d−s(2l−1) = ds > d2r+100 > n(d)2+δ ∼ d(2+δ)r. (127)
as long as δ < 100/r.
Assumption 4 (c). Denote Kd,>m(d)(ξ,η) = ∑ r,l:L(r)>r λK(r)Y r,l(ξ)Y r,l(η) (128)
We have EηKd,>m(d)(ξ,η)2 =Eη ∑ r,l:L(r)>r λK(r) 2|Y r,l(ξ)Y r,l(η)|2 (129)
= ∑
r,l:L(r)>r
λK(r) 2|Y r,l(ξ)|2 (130)
= ∑
r:L(r)>r λK(r) 2 ∑ l |Y r,l(ξ)|2 (131)
= ∑
r:L(r)>r
λK(r) 2N(d, r)Pr(1) = ∑ r:L(r)>r λK(r) 2N(d, r) . (132)
Similarly,
Eξ,η ∑
r,l:L(r)>r
λK(r) 2|Y r,l(ξ)Y r,l(η)|2 = ∑ r:L(r)>r λK(r) 2N(d, r) . (133)
Thus Eη ∑ r,l:L(r)>r λK(r) 2|Y r,l(ξ)Y r,l(η)|2 − Eξ,η ∑ r,l:L(r)>r λK(r) 2|Y r,l(ξ)Y r,l(η)|2 = 0 . (134)
For the diagonal terms, Kd,>m(d)(ξ, ξ) = ∑
r,l:L(r)>r
λK(r)|Y r,l(ξ)|2 = ∑
r:L(r)>r
λK(r)N(d, r) = EξKd,>m(d)(ξ, ξ)
(135) which is deterministic.
I.2 VERIFYING Assumption 5.
Recall that n(d) ∼ dr and rj < r < rj+1 . Assumption 5(a) follows from Eq. (111). Indeed, for l > 1
λ−ld,m(d)+1 ∑ k=m(d)+1 λld,k ∼(d−rj+1)−l ∑ i:ri≥rj+1 dim(Ei)d −lri (136)
∼dlrj+1 ∑
i:ri≥rj+1
drid−lri (137)
=drj+1 > n(d)1+δ (138) for some δ > 0 since r < rj+1. Similarly, for l = 1, since∑
k=m(d)+1
λd,k ∼ 1 (139)
we have (d−rj+1)−1 ∑ k=m(d)+1 λd,k ∼ drj+1 > n(d)1+δ . (140)
Assumption 5(b) follows from r > rj . Assumption 5(c). Note that
λ−1d,m(d) ∑ k=m(d)+1 λd,k ∼ λ−1d,m(d) ∼ d rj < n(d)(1−δ) ∼ dr(1−δ) (141)
for some δ > 0 since rj < r.

heading: J PROOF OF LEMMA 4
text: Proof. The lemma can be proved by induction. Base case: L = 0. The network is a S-CNN. WLOG, assume α0 6= 0 and α1 6= 0. For r ∈ L(G(d)), we know that r can be written as a combination of α0 and α1, i.e. r = k0α0 + k1α1 for some k0, k1 ≥ 0. We say a tuple (k0, k1) is r-feasible if in addition, there exists r with S(r) = k1α1 and ℱ(r) = k0α0. Consider the set of all r-feasible tuple
F (r) ≡ {(k0, k1) : r-feasible} . (142)
Clearly, F (r) is finite. It suffices to prove that for each r-feasible tuple (k0, k1), dim ( span { Y r,l : ℱ(r) = k0α0 S(r) = k1α1, l ∈N(d, r) }) ∼ dr (143)
Note that there are ∼ (dα1)k1 many ways to choose k1 nodes in the penultimate layer. Then the dimension of the above set is about
(dα1)k1 ∑
(k0,1,...,k0,k1 ) k0,1+···+k0,k1=k0
k1∏ j=1 N(dα0 , k0,j) ∼ (dα1)k1 ∑
(k0,1,...,k0,k1 ) k0,1+···+k0,k1=k0
k1∏ j=1 (dα0)k0,j (144)
∼ dk0α0+k1α1 = dr , (145)
since the cardinality of the set
{(k0,1, . . . , k0,k1) : k0,1 + · · ·+ k0,k1 = k0, k0,j ≥ 1 k0,j ∈ N}
is finite.
Induction step: L ≥ 1. For r with L(r) = r, let k be the number of children of a MST of n(r; oG). Clearly, k ∈ [1, [r/αL+1]]. Then we can classify Y r,l into at most [r/αL+1] bins: {Ωk}k=1,...,[r/αL+1] depending on the number of children of oG in a MST. Let Ωk be non-empty. We only need to prove the number of Y r,l in Ωk is dr. Note that there are ∼ (dαL+1)k many ways to choose k children from oG . Let {uj}j=1,...,k be one fixed choice and {Gj} be the subgraphs with {uj} as the output nodes. Next, we partition (r − kαL+1) into k components,
r − kαL+1 = r1 + · · ·+ rk so that each rj is a combination of {αj}0≤j≤L. The cardinality of such partition is also finite. We fix one of such partition (r1, . . . , rk) so that each rj is a learning index of Gj . We can apply induction to each (Gj , rj) to conclude that the cardinality of Y rj ,lj with LGj (rj) = rj is ∼ drj , where LGj (rj) is the learning index of rj of Gj . Therefore, we have
dim ( span { Y r,l : L(r) = r, l ∈N(d, r) }) ∼ (dαL+1)k ∏ j∈[k] drj = dr . (146)

heading: K CNN-GAP: CNNS WITH GLOBAL AVERAGE POOLING
text: Consider convolutional networks whose readout layer is a global average pooling (GAP) and a flattening layer (namely, without pooling), resp.
CNN + GAP: [Conv(p)-Act]→ [Conv(k)-Act]⊗L → [GAP]→ [Dense] (147) CNN: [Conv(p)-Act]→ [Conv(k)-Act]⊗L → [Flatten]→ [Dense] (148)
Concretely, the input space is X = (Sp−1)k L×w ⊆ Rp×1×kL×w, where p is the patch size of the input convolutional layer, k 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 d = p · kL · w, and the number of input nodes is |N0| = kL · 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, a factor of k by each hidden layer. The penultimate layer (before pooling/flattening)
has spatial dimension w and is reduced to 1 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 n many channels and fpen : X → Rn×w is the mapping from the input layer to the penultimate layer, then the outputs of the CNN-GAP and CNN-Flatten are
fCNN-GAP(x) = n − 12 ∑ j∈[n] ωj i∈[w] fpen(x)j,i (149)
fCNN-Flatten(x) = (nw) − 12 ∑ j∈[n],i∈[w] ωjifpen(x)j,i , (150)
resp., where wj and wji are parameters of the last layer and are usually initialized with standard iid Guassian wj , wji ∼ N (0, 1). LetN−1 ⊆ N be the nodes in the penultimate layer, then |N−1| = w. Let ξ = (ξv)v∈N−1 ∈ X , where ξv ∈ (Sp−1)k L
. Thus, each ξv contains kL many input nodes {ξu,i}i∈[kL]. Define
tuv = (〈ξu,i,ηv,i〉/p)i∈[kL] ∈ [−1, 1] kL . (151)
Recall that in the case without pooling
Ku(t) = φ∗( uv∈E Kv(t)), KG = oGv∈E Kv(t) = v∈N−1 Kv(t) (152)
where t ∈ [−1, 1]kL×w, which is usually obtained by t = (〈ξu,i,ηu,i〉/p)u∈N−1,i∈[kL]. Indeed, for each v ∈ N−1, Kv depends only on the diagonal terms tvv = (〈ξv,i,ηv,i〉/p)i∈[kL] ∈ [−1, 1]k L
. We can find a function
Kpen : [−1, 1]k L → [−1, 1] s.t. Kv(t) = Kpen(tvv) ∀v ∈ N−1 (153)
Therefore, without pooling the NNGP kernel is
KCNN(t) = v∈N−1
Kpen(tvv) = 1
w ∑ v∈N−1 Kpen(tvv) (154)
Note that the kernel does not depend on any off-diagonal terms tuv with u 6= v because there isn’t weight-sharing in the last layer. Let dpen = (p, p, . . . , p) ∈ Nk L
. Then ‖dpen‖1 = pkL is the effective dimension of the input to any node u ∈ N−1. Assume k = dαk , p = dαp and w = dαw and αk, αp, αw > 0. Applying Theorem 1 to Kpen, we have
KCNN(t) = ∑ r∈NkL 1 w λKpen(r) ∑ v∈N−1 ∑ l∈N(dpen,r) Y r,l(ξv),Y r,l(ηv) (155)
Clearly, the eigenfunctions are {Y r,l(ξv)}r,l,v and the corresponding eigenvalues are { 1wλKpen(r)}r,l,v . Note that
1 w λKpen(r) = λKG (r) ∼ d−ℒ(r) (156)
Here and in what follows, we also consider r ∈ NkL as an element in NwkL When the readout layer is 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 corresponding to the CNN-GAP depends on both the diagonal and off-diagonal terms t = (tuv)u,v∈N−1 ∈ [−1, 1]kL×kL , which can be written as (Novak et al., 2019b)
KCNN-GAP(t) = u,v∈N−1
Kpen(tuv) = 1
w2 ∑ u,v∈N−1 Kpen(tuv) (157)
Applying Theorem 1 to Kpen, we have
KCNN-GAP(t) = 1
w2 ∑ r∈NkL λKpen(r) ∑ u,v∈N−1 ∑ l∈N(dpen,r) Y r,l(ξu),Y r,l(ηv) (158)
= ∑ r∈NkL 1 w λKpen(r) ∑ l∈N(dpen,r)
( w− 1 2
ˆ u∈N−1 Y r,l(ξu)
)( w− 1 2
ˆ u∈N−1 Y r,l(ηu) ) (159)
= ∑ r∈NkL 1 w λKpen(r) ∑ l∈N(dpen,r) Y Sym r,l (ξ)Y Sym r,l (η) (160)
where
Y Sym r,l (ξ) ≡ w− 1 2 ˆ u∈N−1 Y r,l(ξu) , r ∈ Nk L and l ∈N(dpen, r) (161)
That is the eigenfunctions and eigenvalues of KCNN-GAP are {Y Sym r,l (ξ)}r,l and { 1wλKpen(r)}r,l resp.
In sum, the eigenvalues of KCNN and KCNN-GAP are the same (up to the multiplicity factor w). Each eigenspace of KCNN-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 of w. Same arguments can also be applied to the NTKs
ΘCNN(t) =
v∈N−1
(Kpen(tvv) + Θpen(tvv)) (162)
= ∑ r∈NkL ( 1 w λKpen(r) + 1 w λΘpen(r) ) ∑ v∈N−1 ∑ l∈N(dpen,r) Y r,l(ξv),Y r,l(ηv)
(163)
ΘCNN-GAP(t) =
u,v∈N−1
(Kpen(tuv) + Θpen(tuv)) (164)
= ∑ r∈NkL ( 1 w λKpen(r) + 1 w λΘpen(r) ) ∑ v∈N−1 Y Sym r,l (ξ),Y Sym r,l (η) (165)
where Θpen is the NTK of the penultimate layer which is the same for all nodes in N−1. Since 1 wλΘpen ∼ d −ℒ(r), we have
1 w λKpen(r) + 1 w λΘpen(r) ∼ d−ℒ(r) (166)
K.1 GENERALIZATION BOUND OF CNN-GAP
We show that GAP improves the data efficiency of D-CNNs by a factor ofw ∼ dαw under a stronger assumptions on activations φ. Assumption Poly-φ: There is a sufficiently large J ∈ N such that for all hiddens nodes u
φ∗u (j)(0) 6= 0 for 1 ≤ j ≤ J and φ∗u (j)(0) = 0 otherwise (167)
This assumption implies that there are 0 < J1 < J2 ∈ R such that for all 0 6= r with |r| < J1 dr
dt Kpen(0) 6= 0 and
dr dt Θpen(0) 6= 0 (168)
and for all r with |r| > J2 dr
dt Kpen ≡ 0 and
dr dt Θpen ≡ 0 (169)
Moreover, J1 →∞ as J →∞.
Let LpSym(X ) ≤ Lp(X ) be the close subspace spanned by symmetric eigenfunctions Eq. (161). Let KSym = KCNN-GAP or ΘCNN-GAP.
For X ⊆ X and r /∈ L(G(d)), define the regressor and the projection operator to be
RSymX (f)(x) = KSym(x,X)KSym(X,X) −1f(X) P Sym>r (f) = ∑
r:L(r)>r ∑ l∈N(dpen,r) 〈f,Y Symr,l 〉L2(X )Y Sym r,l .
Theorem 6. Let G = {G(d)}d, where each G(d) is a DAG associated to the D-CNN in Eq. (147) with αk, αp, αw > 0. Let r /∈ L(G(d)) be fixed and the activations satisfy Assumption Poly-φ for J = J(r) sufficiently large. Let f ∈ L2Sym(X ) with Eσf = 0. Then for > 0,∣∣∣∣∥∥∥RSymX (f)− f∥∥∥2 L2Sym(X ) − ∥∥∥P Sym>r (f)∥∥∥2 L2Sym(X )
∣∣∣∣ = cd, ‖f‖2L2+ Sym (X ), (170) where cd, → 0 in probability as d→∞ over X ∼ σ[d r−αw ].
Proof of Theorem 6. We need the following dimension counting lemma, which follows directly from Lemma 4.
Lemma 6. Let r ∈ L(G(d)). Then dim ( span { Y Sym r,l : L(r) = r, l ∈N(d, r) }) ∼ dr−αw (171)
Recall that ℒ(G(d)) = {rj} in non-descending order. Similarly, let
ESymi = span{Y Sym r,l : ℒ(r) = ri} (172)
From the above lemma, we have
dim(ESymi ) ∼ d ri−αw (173)
Since r /∈ ℒ(G(d)), there is a j such that rj < r < rj+1. Let n(d) = dr−αw and m(d) = dim ( span{Y Symr,l : ℒ(r) ≤ rj} ) = dim(span ⋃ i≤j ESymi ) (174)
Clearly, m(d) ∼ drj−αw . We list all eigenvalues of KSym in non-ascending order as {λd,i}. In particular, we have
λd,m(d) ∼ d−rj > d−r > d−rj+1 ∼ λd,m(d)+1 . (175) We proceed to verify Assumptions 4 and 5 in Sec. L.
Assumptions 4 (a) We choose u(d) to be
u(d) = dim span ⋃ i:ri≤2r+100 ESymi  . (176) Let s = inf{r̄ ∈ ℒ(G(d)) : r̄ > 2r + 100}. Assumption 4 (a) follows from Proposition 1.
Assumptions 4 (b) For l > 1, we have∑ j=u(d)+1 λld,j ∼ ∑ ri:ri≥s (d−ri)l dim(ESymi ) ∼ d −s(l−1)−αw (177)
which also holds for l = 1 since
dαw ∑
j=u(d)+1
λd,j ∼ 1 (178)
Thus ( ∑ j=u(d)+1 λ l d,j)
2∑ j=u(d)+1 λ 2l d,j ∼ d −2s(l−1)−2αw d−s(2l−1)−αw = ds−αw > d2r+100−αw > n(d)2+δ ∼ d(2+δ)(r−αw).
(179)
Assumption 4 (c) This requires some work and is verified in Sec. K.2. Assumption 5 (a) Since m(d) = dim(span ⋃ i≤j Ei) and rj+1 > r > rj , we have
1
λd,m(d)+1 ∑ j≥m(d)+1 λld,j ∼ 1 (d−rj+1)l ∑ i>j (d−ri)l dim(ESymi ) (180)
∼ dim(ESymj+1) = d rj+1−αw (181)
> n(d)1+δ = d(r−αw)(1+δ) (182)
as long as δ < (rj+1 − αw)/(r − αw)− 1. Assumption 5 (b) This is obvious since m(d) ∼ drj−αw , n(d) ∼ dr−αw and r > rj . Assumption 5 (c) This follows from rj < r. Indeed,
1
λd,m(d) ∑ j≥m(d)+1 λd,j ∼ 1 (d−rj ) ∑ i>j (d−ri) dim(ESymi ) ∼ d rj−αw (183)
≤ n(d)1−δ = d(r−αw)(1−δ) (184)
as long as 0 < δ < 1− (rj − αw)/(r − αw).
K.2 VERIFICATION OF ASSUMPTIONS 4(C).
We begin with proving Eq. (227). Let Xi define the random variable
Xi ≡ Eξ∼σdKSym,>m(d)(ξi, ξ)2 and ∆i ≡ Xi − EXi (185)
We need to show that
supi∈[n(d)] |∆i| EXi in prob.−−−−→ d→∞ 0. (186)
By Markov’s inequality, it suffices to show that
(EXi)−1E sup i∈[n(d)] |∆i| −−−→ d→∞ 0 (187)
By orthogonality and treating r ∈ NkL as an element of NwkL , we have
EXi = Eξ,ξ̄∼σdKSym,>m(d)(ξ, ξ̄) 2 (188)
= Eξ,ξ̄∼σd ∣∣∣∣∣∣ ∑
r:ℒ(r)>r
K̂Sym(r) ∑
l∈N(dpen,r)
Y Sym r,l (ξ)Y Sym r,l (ξ̄) ∣∣∣∣∣∣ 2
(189)
= Eξ,ξ̄∼σd ∑
r:ℒ(r)>r
K̂2Sym(r) ∑
l∈N(dpen,r) ∣∣∣Y Symr,l (ξ)Y Symr,l (ξ̄)∣∣∣2 (190) =
∑ r:ℒ(r)>r K̂2Sym(r) ∑ l∈N(dpen,r) Eξ,ξ̄∼σd ∣∣∣Y Symr,l (ξ)Y Symr,l (ξ̄)∣∣∣2 (191)
= ∑
r:ℒ(r)>r
K̂2Sym(r) ∑
l∈N(dpen,r)
1 (192)
= ∑
r:ℒ(r)>r
K̂2Sym(r)|N(dpen, r)| (193)
and Xi = Eξ∼σdKSym,>m(d)(ξi, ξ)2 (194)
= Eξ∼σd ∣∣∣∣∣∣ ∑
r:ℒ(r)>r
K̂Sym(r) ∑
l∈N(dpen,r)
Y Sym r,l (ξi)Y Sym r,l (ξ) ∣∣∣∣∣∣ 2
(195)
= Eξ∼σd ∑
r:ℒ(r)>r
K̂2Sym(r) ∑
l∈N(dpen,r) ∣∣∣Y Symr,l (ξi)Y Symr,l (ξ)∣∣∣2 (196) =
∑ r:ℒ(r)>r K̂2Sym(r) ∑ l∈N(dpen,r) Eξ∼σd ∣∣∣Y Symr,l (ξi)Y Symr,l (ξ)∣∣∣2 (197)
= ∑
r:ℒ(r)>r
K̂2Sym(r) ∑
l∈N(dpen,r)
|Y Symr,l (ξi)|2 (198)
= ∑
r:ℒ(r)>r
K̂2Sym(r) ∑
l∈N(dpen,r)
 1 w ∑ u Y r,l(ξi,u) 2 + 1 w ∑ u 6=v Y r,l(ξi,u)Y r,l(ξi,v)  (199) = Eξ,ξ̄∼σdKSym,>m(d)(ξ, ξ̄) 2 + ∑
r:ℒ(r)>r
K̂2Sym(r) ∑
l∈N(dpen,r)
 1 w ∑ u 6=v Y r,l(ξi,u)Y r,l(ξi,v)  (200)
Let
Xr,i = ∑
l∈N(dpen,r)
 1 w ∑ u6=v Y r,l(ξi,u)Y r,l(ξi,v)  (201) then
∆i = ∑
r:ℒ(r)>r
K̂2Sym(r)Xr,i (202)
We replace the maximal function by the lq-norm for q ≥ 1,
E sup i∈[n(d)]
|∆i| ≤ E( ∑
i∈[n(d)]
|∆i|q) 1 q ≤ (E ∑ i∈[n(d)] |∆i|q) 1 q = n(d) 1 q (E|∆i|q) 1 q (203)
where the first three expectations are taken over ξ1, . . . , ξn(d) ∼ σd and the last one is taken over ξi ∼ σd. Then we replace the Lq-norm by the L2-norm via Hypercontractivity, in which we used Assumption Poly-φ which implies that ∆i is a polynomial of bounded degree
E sup i∈[n(d)]
|∆i| ≤ n(d) 1 q (E|∆i|q) 1 q ≤ Cqn(d) 1 q (E|∆i|2) 1 2 = Cqn(d) 1 q (E∆2i ) 1 2 (204)
We expand the L2-norm and use orthogonality to “erase" the off-diagonal terms twice: first for r 6= r̄
Eξi∼σdXr,iXr̄,i = 0 (205) and second for l 6= l′ or u 6= v
Eξi∼σdX2r,i = 1
w2 Eξi∼σd ∑ l∈N(dpen,r) ∑ u 6=v Y r,l(ξi,u)Y r,l(ξi,v) ∑ l′ ∑ u′ 6=v′ Y r,l′(ξi,u′)Y r,l′(ξi,v′)  (206)
= 2
w2 Eξi∼σd ∑ l∈N(dpen,r) ∑ u 6=v Y r,l(ξi,u) 2Y r,l(ξi,v) 2  = 2 w2 ∑ l∈N(dpen,r) w(w − 1)
(207)
= 2(w − 1)
w
∑ l 1 = 2(w − 1) w |N(dpen, r)| ≤ 2|N(dpen, r)| (208)
Combining this estimate with Eq. (193), Eq. (202) and Eq. (204) yields
(EXi)−1(E sup i∈[n(d)] |∆i|) ≤ Cqn(d) 1 q (2 ∑ r:ℒ(r)>r K̂4Sym(r)|N(dpen, r)|)1/2∑ r:ℒ(r)>r K̂2Sym(r)|N(dpen, r)|
(209)
≤ √ 2Cqn(d) 1 q ∑ r:ℒ(r)>r K̂2Sym(r)|N(dpen, r)|1/2∑ r:ℒ(r)>r K̂2Sym(r)|N(dpen, r)|
(210)
≤ √
2Cqn(d) 1 q sup r:ℒ(r)>r
K̂2Sym(r)|N(dpen, r)|1/2
K̂2Sym(r)|N(dpen, r)| (211)
∼ 2Cqd r q sup r:ℒ(r)>r |N(dpen, r)|− 1 2 (212)
∼ d r q sup r:ℒ(r)>r d−|r|αp −−−→ d→∞ 0 (213)
by choosing q (independent of d) sufficiently large.
The proof of Eq. (228) is similar. Let Xi denote the random variable
Xi ≡ KSym,>m(d)(ξi, ξi) and ∆i ≡ Xi − EXi (214)
and it suffices to prove
E supi∈[n(d)] |∆i| EXi −−−→ d→∞ 0 (215)
We have
EXi = Eξi∼σdKSym,>m(d)(ξi, ξi) (216) = Eξi∼σd ∑
r:ℒ(r)>r
K̂Sym(r) ∑
l∈N(dpen,r)
Y Sym r,l (ξi)Y Sym r,l (ξi) (217)
= ∑
r:ℒ(r)>r
K̂Sym(r)|N(dpen, r)| (218)
and ∆i = Xi − EXi = w−1 ∑
r:ℒ(r)>r
K̂Sym(r) ∑
l∈N(dpen,r)
∑ u 6=v Y r,l(ξi,u)Y r,l(ξi,v), . (219)
The remaining steps (replacing the maximal function by the lq-norm, and then the Lq-norm by the L2-norm using hypercontractivity) are similar to that of the proof of Eq. (227), which are omitted here.

heading: L KERNEL CONCENTRATION, HYPERCONTRACTIVITY AND GENERALIZATION OF MEI ET AL. (2021A)
text: For convenience, we briefly recap the analytical results regarding generalization bounds of kernel machines from Mei et al. (2021a) Sec 3.
Let (Xd,σd) be a probability space and ℋd be a compact self-adjoint positive definite operator from L2(Xd,σd)→ L2(Xd,σd). We assume ℋd ∈ L2(Xd ×Xd). Let {ψd,j} and {λd,j} be the eigenfunctions and eigenvalues associated to ℋd, i.e.
ℋdψd,j(x) ≡ ˆ y∈Xd ℋd(x, y)ψd,j(y)σd(y) = λd,jψd,j(x). (220)
We assume the eigenvalues are in non-ascending order, i.e. λd,j+1 ≥ λd,j ≥ 0. Note that∑ j λ2d,j = ‖ℋd‖2L2(Xd×Xd) <∞. (221)
The associated reproducing kernel Hilbert space (RKHS) is defined to be functions f ∈ L2(Xd,σd) with ‖ℋ− 1 2
d f‖L2(Xd,σd) < ∞. Given a finite training set X ⊆ Xd and observed labels f(X) ∈ R|X|, the regressor is an extension operator defined to be
ℛXf(x) = ℋd(x,X)ℋd(X,X)−1f(X) . (222)
Intuitively, when “X →Xd" in some sense, we expect the following ℛXf(x) = ℋd(x,X)ℋd(X,X)−1f(X)→ ℛXdf(x) = ℋd(ℋ −1 d f)(x) = f(x), (223)
namely, “ℛX → IXd" in some sense. Using tools from the non-asymptotic analysis of random matrices (Vershynin, 2010), the work Mei et al. (2021a) provides a very nice answer to the above question in terms of the decay property of the eigenvalues {λd,j} and the hypercontractivity property of the eigenfunctions {ψd,j}. They show that ℛX is essentially a projection operator onto the low eigenspace under certain regularity assumptions on the operator ℋd. These assumptions are stated via the relationship between the number of (training) samples n = n(d), the tail behavior of the eigenvalues with index≥ m = m(d) and the tail behavior of the operator ℋd
ℋd,>m(d)(x, x̄) ≡ ∑
j>m(d)
λjψj(x)ψj(x̄) (224)
as the "input dimension" d becomes sufficiently large.
Assumption 4. We say that the the sequence of operator {ℋd}d≥1 satiesfies the Kernel Concentration Property (KCP) with respect to the sequence {n(d),m(d)}d≥1 if there exsts a sequence of integers {u(d)}d≥1 with u(d) ≥ m(d) such that the following holds
(a) (Hypercontractivity.) Let Du(d) = span{ψj : 1 ≤ j ≤ u(d)}. Then for any fixed q ≥ 1, and C = C(q) such that for f ∈ Du(d)
‖f‖Lq(Xd,σd) ≤ C‖f‖L2(Xd,σd) (225)
(b) (Eigen-decay.) There exists δ > 0, such that, for all d large enough, for l = 1 and 2, n(d)2+δ ≤ ( ∑ j≥u(d)+1 λ l d,j)
2∑ j≥u(d)+1 λ 2l d,j
(226)
(c) (Concentration of Diagonals.) For {xi}i∈[n(d)] ∼ σ n(d) d , we have: supi∈[n(d)] ∣∣Ex∼σdℋd,>m(d)(xi, x)2 − Ex,x̄∼σdℋd,>m(d)(x, x̄)2∣∣
Ex,x̄∼σdℋd,>m(d)(x, x̄)2 in Prob.−−−−→ d→∞ 0 (227)
supi∈[n(d)] ∣∣ℋd,>m(d)(xi, xi)− Ex∼σdℋd,>m(d)(x, x)∣∣
Ex∼σdℋd,>m(d)(x, x) in Prob.−−−−→ d→∞ 0 (228)
where cd → 0 in probability as d→∞.
Assumption 5. Let ℋd and {m(d), n(d)}d≥1 be the same as above.
(a) For l = 1 and 2, there exists δ > 0 such that
n(d)1+δ ≤ 1 λld,m(d)+1 ∑ k=λm(d)+1 λld,k (229)
(b) There exists δ > 0 such that
m(d) ≤ n(d)1−δ (230)
(c) (Spectral Gap.) There exists δ > 0 such that
n(d)1−δ ≥ 1 λd,m(d) ∑ k≥m(d)+1 λd,k (231)
Let P>k (similarly for Pk, P≤k, etc.) denote the projection operator P>kf = ∑ j>k 〈f, ψj〉ψj (232)
Theorem 7 (Mei et al. (2021a)). Assume ℋd satisfy Assumptions 4 and 5. Let {fd}d≥1 be a sequence of functions and let X ∼ σn(d)d . Then for every > 0,
‖ℛX(fd)− fd‖2L2(Xd,σd) = ‖P>m(d)fd‖ 2 L2(Xd,σd) + cd, ‖fd‖2L2+ (Xd,σd) (233)
where cd, → 0 in probability as d→∞.
The theorem says, ℛX is essentially the projection operator P≤m(d) in the sense that when restricted to L2+ (Xd,σd),
ℛX = P≤m(d) + Errord, (234)

Review summaries:
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.