What Breaks The Curse of Dimensionality in Deep Learning?
Authors: Lechao Xiao
Jeffrey Pennington
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Locality
symmetries
Symmetry Breaking
NNGP
NTK
Spherical harmonic
Infinite Width

Abstract: Although learning in high dimensions is commonly believed to suffer from the curse of dimensionality, modern machine learning methods often exhibit an astonishing power to tackle a wide range of challenging real-world learning problems without using abundant amounts of data. How exactly these methods break this curse remains a fundamental open question in the theory of deep learning. While previous efforts have investigated this question by studying the data (D), model (M), and inference algorithm (I) as independent modules, in this paper we analyzes the triple (D, M, I) as an integrated system. We examine the basic symmetries of such systems associated to four of the main architectures in deep learning: fully-connected networks (FCN), locally-connected networks (LCN), and convolutional networks with and without pooling (GAP/VEC). By computing an eigen-decomposition of the infinite-width limits (aka Neural Kernels) of these architectures, we characterize how inductive biases (locality, weight-sharing, pooling, etc) and the breaking of spurious symmetries can affect the performance of these learning systems. Our theoretical analysis shows that for many real-world tasks it is locality rather than symmetry that provides the first-order remedy to the curse of dimensionality. Empirical results on state-of-the-art models on ImageNet corroborate our results.

What Breaks the Curse of Dimensionality in Deep Learning?
Anonymous Author(s)
Affiliation
Address email
Abstract
Although learning in high dimensions is commonly believed to suffer from the curse of dimensionality, modern machine learning methods often exhibit an as- tonishing power to tackle a wide range of challenging real-world learning prob- lems without using abundant amounts of data. How exactly these methods break this curse remains a fundamental open question in the theory of deep learning. While previous efforts have investigated this question by studying the data (D), model (M), and inference algorithm (I) as independent modules, in this paper we analyzes the triple (D, M, as an integrated system. We examine the basic symmetries of such systems, focusing on four of the main architectures in deep learning: fully-connected networks (FCN), locally-connected networks (LCN), and convolutional networks with and without pooling (GAP/VCC. By computing an eigen-decomposstton of the infinite-width limits (aka Neural Kernels) of these architectures, we characterize how inductive biases (locality, weight-sharing, pool- ing, etc) and the breaking of spurious symmetries can affect the performance these learning systems. Our theoretical analysis shows that for many real-world tasks it is locality rather than symmetry that provides the first-order remedy to the curse of dimensionality. Empirical results state-of- the-art models ImageNet corroborate our results.
10
11
12
14
16
18
Introduction
20 Statistical problems with high-dimensiona data are frequently plagued by the curse of dimensionality, in which the number of samples required solve the problem grows rapidly with the dimensionality of the input. Classical theory explains this phenomenon as the consequence of basic geometric and d
21
22
algebraic properties of high-dimensional spaces; for example, the number of e-cubes inside unit cube I grows exponentially like e- and the number of degree r polynomials in Rd grows like a plwer-law d'. Since for real-world problems d is typically in the hundreds or thousands, classical wisdom suggests that learning is likely to be infeasible. However, starting from the groundbreaking work AlexNet [1], practitioners in deep learning have tackled a wide range of difficult real-world learning problems ([2-6]) in high dimensions, once believed by many to be out-of-scope of current techniques. The astonishing success of modern machine learning methods clearly contradicts the curse of dimensinonality and therefore poses the fundamental question: mathematically, how do modern machine learning methods break the curse of dimensionality?
24
25
26
27
28
29
30
31
32 To answer this question, we must trace back to the most fundamental ingredients machine learning methods. They the data (D), the model (JM), and the inference algorithm (I).
33
34 Data (D) of course central machine learning. In the classical learning theory setting, the learning objective usually has power-law decay 3 as the function of the number of training samples
36 m. The theoretical bound on B is usually tiny, owing to the curse of dimensionality, and is of
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 limited practical utility for high- -igensiienii data. On the other hand, empirical measurements of
38 in state-of-the ahe deep learning models typically reveal values of that are not at all small (e.g.
39 G = 0.43 for ResNet in Fig.S2) even though d is quite large (e.g. d ~ 10 for ImageNet). This
40 example suggests that the learning curve must have important functional dependence on M and I.
41 Indeed, as we will observe later, many of the best performing methods exhibit learning curves for
42 which 3 = [m) actually increases as m becomes larger, i.c. data makes the usage of data more efficient. We call this phenomenon DIDE, for data improves data efficiency.
43
44
Designing machine learning models (M) that maximize data-efficiency is critical to the success of solving real-world tasks. Indeed, breakthroughs in machine learning are often driven by novel architectures LeNet [7], AlexNet[1]. Transformer [2), etc. While some of the inductive biases of these methods are clear (e.g. translation symmetries of CNNs), others tend to build off of prior empirical success and are less well-understood (e.g. the implicit bias of SGD). To build our understanding of these biases and how they affect learning. we conduct a theoretical analysis of them in the infinite- width setting [8-12], which preserves most salient aspects of the architecture while enabling tractable calculations. We classify all phenomena that could be explained by infinite networks alone as the consequences of inductive biases.
45
46
47
48
49
50
51
52
58
The inference procedure (Z) is what enables learning in machine learning methods. It is widely believed that modern inference methods, specifically gradient descent and variants, 'impicitlly' bias the solutions of the networks towards those that generalize well and away from those that generalize poorly [13-15]. The effects of the inference algorithm are intimately tied the specifics of the model (e.g. weight-sharing) and the data (e.g. augmentation), and might not be fully understood with a fixed-data, fixed-model analysis. Indeed, good performance may derive from interactions between (M. I), or (D, I). or even (D, M, Z). In Sec. 3.1, we demonstrate the DIDE effect for particular choice of MD and show that this effect disappears if any one of D, M, or is altered.
54
55
56
57
58
59
60
61
The above discussion highlights the insufficiency of treating D, .,, and I as separate non-interacting modules. They must be considered as an integrated system. Throughout this paper, we will refer to the triplet (D,M, M, as (machine) learning system and the tuple (M,Z) as the learning algorithm of the system that operates on D. We summarize our contributions below.
62
63
64
65
1. We surface the basic symmetries of various (D,M, T..M,,Jannn T)associated to four of the main ar- chitectures in deep learning FCN,, (fully-connected networks), LCN,, (locally-conneeted networks), VEC,, /GAP, (convolution networks with a flattening la global average pooling readout layer), their infinite width counterparts /c .o.LC.../VEE... /vCC /GAP......................... Treating FCN,, as the baseline model, we show that the locality from L LCN,, and the weight-sharing from VEC.,/GAP, break spurious symmetries and lead to better systems. Empirically, we examine the relation between the symmetries and the performance of the systems in the infinite width setting and finite width setting with various of interventions. Surprisingly, we observe that state-of-the-ar learning system (EfficientNet( 16)) on ImageNet can learn almost equally well even the coordinate of the data are transformed by the symmetry group defined by LCN..
66
67
68
69
70
71
72
73
74
76
2.
We show that although the weight-sharing from VEC,, provides coordinate information of the data to the system, as the width gets larger, it becomes harder for the learning algorithm explore such information and at infinite width, the system restores the symmetry group that is identical to LCN,,, and is completely unaware of the coordinate information. As a consequence, the performance of the network,
77
78
79
80
function of width, monotonically decays [12). This is in stark contrast to recent finding that the performance of network is positively correlated to its width. We show that this phenomenon continues to hold even with various interventions (larger learning rate and 12 regularization) to the training procedures. However, with more data (e.g. data augmentation) VEC,, can be on par with GAP... n.
81
83
84
85
3. The function space defined by LCN,, a super set of that defined by VEC,, We prove the opposite is true. Therefore, VEC, is able to express functions in the space with a stronger inductive bias GAP,, (translation invariance) and functions in a seemingly much larger class LCN,,- We hypothesize that as the dataset grows, the learned functions using VEC,, is transitioned away from those learned using LCN,, and become closer to those learned using GAP,, This suggests, even though the prior (provided by human) is not 100% correct, with the help of more data, gradient descent might be able to correct it, a possible explanation of DIDE.
86
87
88
89
90
91
2

---

93
4. When the input space is the product of hyperspheres, we eigendecompose the kernels associated to one-hidden layer infinite width network, FCNx vEC, = LCN,5 and GAP We treat >C as the baseline, whose order r eigenspace has dimension of order d' and eigenvalues of order d' for 2 0 [17]. We show that locality alone (i.e. VECx) dramatically reduces the dimension of the r-eigenspace for r 2 2 and the spectral gap between all r-eigenspaces but r = 0 and r = 1, making learning of higher order eigenspaces feasible with dramatically fewer samples and gradient steps. In addition, pooling (i.e. GAP.o) reduces the dimension of r-eigenspace for r Z 1 by a factor equal to the size of the pooling window, but it does not change the spectra in an essential way.
94
95
96
97
96
99
100
102
Our empirical and theoretical results surface the importance of locality which, we believe, provides the first-order remedy to the curse of dimensionality for many real-world tasks and which has been largely overlooked.
103
104
2
Preliminary and Notation
105
106
2.1
Neural Networks
107
We focus our presentation on the supervised learning setting and more concretely, on image
recognition. Let D S (Rd)$ I² = R 3d R denote the data set (training and test) and X' fx (z. v) E D} and y = {y: (z, y) E D} denote the input space (images) and label space, respectively. Here d is the spatial dimension (e.g. d = 32 x 32 for CIFAR-I0) of the images and
108
109
110
the total number of channels (i.e. RGB). We use FCN, to denote L-hidden layer fully-connected
112
network with identical hidden widths nn = n E N for I 1, ...., I. and with readout width #1++1 (the number of logits). For each x E Rdd- = ( we use h² (x)),, x' (x) E R to represent the pre- and post-activation functions at layer with input æ. The recurrence relation FCN is given by
118
114
(h4t x' W1+1
1 whyt VTu
11 = (I- and W!
~ ~ N(0,
115 where Ø is point-wise activation function, W E R are the weights and w/y are the trainable parameters, drawn i.i.d. from standard Gaussian ~ NN 1) at initialization. For simplicity of the presentation, the bias terms and the hyperparameters (the variances of the weights) are omitted. Adding them back won't 't affect the conclusion of the paper.
116
117
For convolutional networks locally-connected networks, the inputs are treated as tensors in (R:d3. The recurrent relation of convolutional networks can be written as
119
120
n
J a.j = (b()t)) and
h 1+1 a.j
= V(2k 1)m
x
j=1 B=
Here a E [d] denote the spatial location, i/j E [v] denotes the fanin/fanout channel indices. For notational convenience, we assume circular padding and stride equal to I for all layers. The features of the penultimate layer are 2D tensors and there are two commonly used approaches to map them
121
122
123
124
to the logit layer: stack dense layer after either vectorizing the 2D tensor to a ID vector or
125
applying a global average pooling layer to each channel. We use VEC,, /AAP, n to denote the network obtain from the former/latter, which are known to be equipped with the inductive biases translation equivarian//nvaaiint. The readout layer of VEC,, GAP,, could be written as
126
127
ddn
Σ x L+1
L+ zj
Vn
Σ iE(n)
d
Σ [E(
x
L+1 ij
(3)
aE(d]
128
We briefly remark the the key difference between the two. In VEC,, each pixel in the penultimate layer has its own (independent random) variable while pixels within the same channel shared the same (random) variable in GAP,. It is clear that the function space of VEC,, contains that of GAP,,, n- Locally Connected Networks LCN,, [18. 19] are convolutional network without weight sharing between spatial locations. LCN, preserve the connectivity pattern, and thus topology, of convnet. Mathematically, the current formula is defind as in Equation 2 with all the shared parameters w/y.
129
131
132
133
replaced by unshared W3s... NO( 1)
3

---

135 In this note, we assume that the LCN,, are always associated with a vectorization readout layer and it clear, as function space, LCN,, is super set of VEC,. Interestingly,the opposite is also true.
136
137
Theorem 2.1 (Sec. B). Let VEC.. / L.N.,//AP, denote the set of functions that can be represented by L-hidden layer VEC,/LCN,, GAP, networks with hidden width n. Then
138
GAP, S VEC, LLCN, S VECdn
(4)
139
The significance of this theorem is that if we consider the function space VEC,, as soft prior, gradient descent could move it closer to a better prior GAP,, n (translation invariance) if the average pooling is (approximately) learned in the readout layer or it might remain close LCN,,
140
141
142
2.2
Gradient Descent Training
143
We use f to denote any functions defined by the architectures above and 0 to denote the collection of all parameters. Denote by Og the time-dependence of the parameters and by On their initial values. We use fx(x) = I (I, 0+) E Ie* to denote the output (or logits) of the neural network at time t. Let y) : 12 x R + R denote the loss function where the first/second argument is the prediction/true label. By applying continuous time gradient descent to minimize the objective
144
145
146
147
L = E (a,))D ((f((z, f), y), the evolution of the parameters 0 and the logits f can be written as
148
0. = ( I
f((7)) Vefi 0, Ô, XT) V J (5)
where (x(( vec (Ife (x) (x)), the k|D| x vector of concatenated logits for all examples, and 5. (xt)) is the gradient of the loss with respect to the model's 's output, fe(()). ê, = O,(,r, Xr)
150
151
is the tangent kernel at time t, which is a k: (D x k|(D) kernel matrix
Vo Vof((()))))))
(6)
One can define the tangent kernel for general arguments, e.g. (,(1, where x is test input. At width, é will depend on the specific random draw of the parameters and evolve with time. As such, for a test point x the prediction (x) depends the random initalization and is also stochastic. Note that the parameters are initialized randomly and the randomness will be carried out through the training procedure. As a consequence, the prediction functions are stochastic.
152
153
155
156
157
2.3
Infinite Network: Gaussian Processes and the Neural Tangent Kernels
158
Neural Networks as Gaussian Processes (NNGP). As the width n - co, at initialization the output (X') forms Gaussian Process fo(X)) ~ GP(O, X)), known as the NNGP [8, 20, 21]. Here K is the GP kernel and can be computed in closed form for a variety architectures. By treating this infinite width network a Bayesian model (aka Bayesian Neural Networks) and applying Bayesian inference, the posterior is also a GP
159
160
162
N (CC,,,,))K (Nr, Nr WDr, K(XX, - KC
163
Neural Tangent Kernelss(NTK). Recent advance in global convergence theory of over- parameterized networks [22-25, 12] has shown that under certain assumptions, the tangent kernels is almost stationary over the course of training and is concentrated on its infinite width limit θ in the sense there a constant independent of and the network's width n such that
184
185
186
Xx)le (1 X.) O(Kr, X.)les C
sup [0,, 120
(8)
Vn
167
where is the infinite width limit of θ at initialization, whose existence has been proved in [22, 26). As such, when the loss the mean squared error (MSE), the mean prediction (marginarized over random initialization) has the following closed form
188
189
10 '(rr Xr) (1 (1- (1-e-18(2,) xx))) y.
f(X.) θ (r) θ
170 Letting + 0o, the above solution is the same as that of the kernel ridgeless regression using the infinite width tangent kernel O We use (r), (r)) VEC (x) and GAP,.. (2) to denote the infinite width solutions (either the GP inference or the NTK regression) for the corresponding architectures, where we have suppressed the dependence on the training data (/r,
172

---

174 3 Symmetries of Machine Learning Systems
175
Symmetry is fundamental in physical systems. So is it in machine learning systems. We explore symmetries of various machine learning systems in this section. Given 'D = (X))) and a transforma- tion on the input space T R + Rddd we set T(D) = (T))).))) Let O(3d) denote the orthogonal group on the flatten input space IR:dd The subgroup 0(3)² I ((d)) operates on the un-flattened input (1 whose element rotates each pixel Fa E R by an independent element Ta E 0(3). The all Ta for We use P(3d) to denote the permutation group on Rdd and P(3) and P(3) @ I, are defined similarly. Note that rotating X' by r is equivalent to transfer the original coordinate system by the adjoint tranformation 7"
176
177
178
179
180
smaller subgroup (3) @ Ia - 0(3)d applies the shared rotation (i.e. Ta
[d).
182
189
184 For a deterministic (stochastic) learning algorithm A = (M,I), we use A(Dr) denote the learned function (distribution of the learned functions) using training set Dr. We use A' (Dr) to denote the learned function(s) using T (DDr) and makes prediction on the transformed test point (x.)). In another word, the learning algorithm is conducted in the input space whose coordinate system is transformed by --
185
186
187
188
Definition 1. Let 9 be group of transformations Radd - Rd We say a deterministic (stochastic)
189
learning algorithm A (M,I) is g- g-invariant if A A (A =d A ). In this case, we say the system (D, is g-invariant and use the notation MD, M,D, If this holds for all
190
192 g E G. then we say the algorithm and the system are G-invariant.
199 If (M,I) I) is the algorithm of minimum norm linear regressor, then (D,MID) is (03))-invarian see Sec.G for more details. Note that the symmetry (invariance) in our definition is a property of system and is different from the notion of symmetry that are commonly used in the machine learning community, which is a property of function (e.g. translation invariance).
194
185
196
197
Theorem 3.1 (Sec.C). If the parameters of the networks are initialized with iid ( 1), then
198
FCN,/ are (33d)-invariant.
200
VEC,, is 0(3) & L--invrriant and VEC, is (3))
201
199
LCN are 0(3)* ((3)--invan) iivariiant.
202
GAP are 0(3) & Ia-invariant.
203
The O(3d))invariant of 5 is because the NTK/NNGP kernel is an inner product kernel, namely, there is a function i such that the kernels have the form x²)). The O(3d))invariant of finite width FCN, is due to the Gaussian initialization of the first layer which was first observed and
204
206
proved in [27]. Rotating the input by T E O(3d) is equivalent to rotating the weight matrix w of the first layer by r" Since for w E (0, 1)3d -"w =d w, at random initialization, the distribution of the output functions (the prior) are unchanged if all inputs are rotated by the same element in O(3d). This property continues to hold throughout the course of (continue/discrete) gradient descent training with/without l.=rreuuaarization and Bayesian posterior inference. For the same reason, L LCN,, ((3) -invarint because each patch of the image uses independent Gaussian random variables. However, weight-sharing in VEC, and GAP,, breaks the 0(3) symmetry, reducing it to 0(3) @ La-
207
208
209
211
212
213
For infinite networks, LCN = VEC.2 [28-31]. The kernels of VEC and GAP are of the forms OVEC(z, x') = k(((Ta, baat)))) and OGAP(x, = (((a d'd') )a,ee()))) resp. The former depends only on the inner product between pixels in the same spatial location, breaking the (3d) symmetry and reducing it to O(3) In addition, the latter depends also on the inner products of pixels across different spatial locations due to pooling, which breaks the O(3)d symmetry and reduces it to 0(3)= Ig.
(10)
214
216
217
Note that dim di3d) 3d(3d - 11)2,, dim() = 3d and (O(3) @ La) 3. /VE./VEC... dramatically reduces the dimension of the symmetry group. is worth mentioning that while
219
(3d)) many pairs of rotated and unrotated images are needed to recover the exact rotation in (3d), only 3 pairs are sufficient for 0(3)", same as that of 0(3) @ Lg. The results of the paper are presented in the most vanilla setting. Our methods can easily extend to more complicated architectures like ResNet[32], MLP-Mixer(33] and etc. The symmetry groups of such systems need to be computed case-by-case manner by identifying the invariant group of the random initialization and training procedures.
221
222
224
5

---

NIK
NN
NN+
Mi++
077
FON.
LAF4
FCN LAFE
6.3
VEC.
VEC..
GAP.
V.Cc
LON
096
Potell
097
105 Po0 1007
020
PORT P50
090
94
PS0
Psbaas
000
Figure 1: Performance vs Symmetry. Machine learning systems are equipped with various kinds of symmetries. Transforming the system by the associated symmetry does not affect the performance of the system. However, injecting spurious symmetries beyond the associated symmetries could dramatically degrade their performance for both finite and infinite networks.
Accuracy vs Strangth of Rotation
Distance betwoon VEC3 GAP,
Distanoa botween VECa and VEC.
0.015
0.80
128
IVEC| IVEC)--APPt
IVV VECJII
Jesuaey
0.75
512
0.010
0,010
0.70
0.65
0.005
0.0
0.2
0.4
0.8
0.8
1.0
0.0
0.2
0.4
0.6
0.0
1.0
0.0
0.2
0.4
0.8
0.8
1.0
Strength -roit-Rotaiion
Strength of RooytRRotaiion
Strength Oj3y-Rotation
Figure 2: Even in the NN+ setting, VEC,, is closer to GAP,, n for small n and moves towards VEC,c with more symmetries and/or larger n and accuracy drops.
226
3.1
Empirical Supports and Observations
227
Performance under Rotations. We examinate the performance of: FCN, VEC, LCN, GAP and
LAP4/8 when the coordinates of the data are transformed by six different groups (x-axis in 1ig.1) using the standard dataset CIFAR-10. Here LAP4/8 is the same GAP except the readout layer is replaced by the Local Average Pooling with window size 4 x 4/8 x 8. We consider 4 types of training methods: (1) NTK, i.c. infinite networks (2)NN, our baseline for finite width neural network which is trained with momemtum using a small lcarning rate and without L regularizer and the network centered (+-C) reduce the variance from random initialization (3)NN+= NN+LR using a larger learning rate (+L adding L regularization (+L))) and removing the centering (-C)
228
230
232
i.e.
234
(4) NN++=NN+ DA, adding Mix Mix44[34] data augmentation (+DA) to NN+. Overall, observe that, for most of the cases in NTK/NN/NN+, adding spurious symmetry to a system (D,M, degrades the performance towards that of the system invariant to that symmetry. Surprisingly, in the
236
237
baseline NN, performance of VEC,, + 0(3) @ La rotation is slightly worse than that of VEC, O(3)a and than that of LCN,,, indicating that the system with M VEC,, is likely operating closely on the 0(3) symmetry. The interventions LC in NN+ distinguishes the performance of VEC, + (3) & La from VEC,, + 0(3)d and +DA eventually closes the performance gap between VEC, + (3) La and GAP,, n + 0(3) & Ia, helping the system to be aware of the smaller symmetry (3)) @ La escaping from the 0(3) symmetry.
238
239
240
241
244
Symmetry Breaking VEC,.. Assuming Equation 8, namely, the network is in the NTK regime,
lim JEVEC, (x) VE) + lim LEVE,, (x) - EVEC, < On =-000
(11)
245
where the expectation E is over random initialization and (IC is the prediction of the test point I when [ = 00, i.e. training loss is 0. VEC, is the prediction of the 7-rotated system, - E 0(3)d
246
The 0(3)d symmeeryy is restored as n - xc. As such, for large n, the system is approximately 0(3)d_
247
invariant. We randomly sample 7 E O(3) and use the exponential map to construct a continuous interpolation 7, E O(3)d with T3 Id and 7: = T. We train the network as in NN++ (+LR+L2-C)
248
249
250
using different and and average the predictions over 10 random initialization as approximation of EVEC (x). Not surprisingly, as n increases and/or increases, (1) test performance decays
251
monotonically (left panel in F)g.2), (2) the distance to EGAP,, n increases monotonically (middle
253
panel) and (3) distance to VEC decrease monotonically (right panel). Clearly, the coordinate information from the data is utilized by smaller width VEC,,

---

Figure 3: Data Bends Learning Curve of VEC,. We study the effect of training set size to the network's perfor- mance for various models. In the small dataset regime, the slope of the learning curve (in the log-log plot) of VEC, is similar that of VEC.c and FCN,. However, as the dataset gets larger, the slope increases significantly. This is hinted by Theorem 2.1.
Unuggeett
CAP,
VEL.
VEC+
2:4
2
Training Set Szo
OdF Image
Cousa EiBogy
0.4.33
CD5
Behietc-
RenNettO Cleen Images
Hoskitte copp- rages
DeeNeeD Imggee
Mixemml Coun Images
Toiniin
Toining Set Bize
Figure 4: With coordinate of the input data rotated by 0(3) state of the art models learn good as without rotation. middle/right: slopes of the learning curves increases due to more data. DIDE
255
DIDE for VEC,, To understand the role of data, we vary the training set size of Cifar 0 from about 2 50k (the whole un-augmented training set) and 100k (adding left-right flip augmentation) and
258
257
plot the learning curves in Fig.3. We observe dramatic speedup of learning for VEC, in the larger
258
data set regime, which isn't the case for VEC,o. (kernel), LCN,,, GAP oc and even for GAP,, after
259
m 2 We argue that this is due to the prior (the function space defined by the model) is too large (and not optimal) for the task and the coupled effect of more data together with inference procedures
260
261
corrects the prior, as it is suggested by Theorem 2.1.
262
DIDE for SOTA models. In the middle and right panels of Sig. we provide additional evidence in larger scale setting. We generate learning curves of ImageNet using ResNet50 and MLP-Mixer, very recent architecture that contains no convolution layers except the first layer, which convolutionn with filter size and stride equal to (16, 16) (patches are disjoint). The symmetry group associated to ResNet is similar to that of GAP,, n. which is relatively small. However, the symmetry group induced by the first layer of the Mixer is O(3 x 162) @ [42, where 3 x 162 is number of entries in the (16, 16, 3) patch (RGB channels) and 142 224 /162 the number of patches. Although the dimension of O(3 162) @ I1 is quite large (about (3 x 2/2), it is still dramatically smaller than that of applying a fully-connected layer to the flatten images, which O(3 x 224a) (about
263
264
265
266
267
268
270
(3 x 2242)a )2/ /2). In the middle panel of Fig.S2, we observe an almost perfect power-law scaling for the learning curve for the ResNet50 system with unrotated images. When the images are rotated by ((3) (d 2242), the learning curve is relatively flat in the smaller data regime (green dashed line). However, the data set grows, it eventually catches up (purple dashed line) as that of the unrotated setting; see Sec.E for ResNet34/101. In the third panel, we see the learning curves are much flatter (red) for the Mixer and even more so for the rotated images (green). Again, these curves are bent towards that of ResNet50 with unrorated images data increases, indicating the prior was being corrected.
272
274
276
278
Finally, in the left panel of Fig.S2, we compare the accuracy of state-of-the-ar models trained on both unrotated and 0(3)d rotated images. Surprisingly, the gap between the two are not large and becomes smaller for better performant models. For EfficientNet B7 the top-1 accuracy of the rotated system is only 1.2% off from the unroated one.
280
282
4 Eigenecomposition of Neural Kernels
283
284 To get insights into the inductive biases, we eigendecompose the kernels using spherical harmon-
285 ics. We assume the input space X = {g = (fo.....p-1) E (Vdg8(d-1)yp S Rod, i.e.
Still under training
7

---

the p-product of (dg - 1) s-sheee with radius vdg. We call & E vdns(do-1) mini mini-patch and (5:, (ii.l........-111 E (vd ( 1))) patch for i E [p), where circular boundary condition is assumed. We consider the asymptotic limit when dg = d - = d'-a and d = pdo - oo and treat 0 < a < and 8 as fixed constant. The input space A' is associated with the product measure = daa where do is the normalized uniform measure on v The kernels associated to the one-hidden layer infinite networks (either NNGP or NTK) has the following general forms
296
287
288
289
290
291
A:
Σ P Elpp
Seen/// ns/do
1 P
Σ bE(N
E k LjE(pl
Σ bE(al
S (4tol1+b/dd
8
D
eE(p
(12)
although that exact form of the (positive definite) kernel function k: : IR depends on the kernel
293
types (NNGP vs NTK), activations, hyperparameters and etc. We assume the kernel is sufficiently
smooth in (-1, 1) and the Tayor expansion of k(r) converges uniformly in [-1, 1] for sufficiently
294
many N. We the notation that A B if there are positive constants and C such that
296
cA S B < CAA for sufficiently large. We use K. to represent any kernels above and consider it as a
Hilbert-Schmidt operator on L (X,
KCf(E) f
p(
(13)
which is well-defined since y is a probability measure and l is bounded. Fet (ro: ........... Tp-. pp11) NP,
299 7 the shifting operator TF = (rp-1, ro. "o.-,,"o...., T--2)) The s-banded subset of No is defined to be
B(NP, .) = (F E N": dist(argmax,r) # 0, argmin,r, * 0) S --1
(14)
which is quantifier used to restrict the support of function on patch. Here dist(i,)) = min
301
fl. p - 1 - ji}. a distance defined on the cyclic group [p] z/pZ. The quotient space B(N", S)/T
denotes subset of ( s) by identifying ő 5 as the same element if o T-7 for some a E [p]. Finally, Y,,,,(5) (E,) is used to denote the 1,-th spherical harmonic of degree Tj in the unit sphere
303
gido and has unit norm under the normalized measure on S(do-1), As such Yzdd, (55/ (oo) E 304
L (V dos(dd--)) odg)) has unit norm. Recall that the total number of spherical harmonic of degree
305
r in g(do-1) is N (do, r,) (2r, + do 2) (2 de' /ry! as do - co. We use N(do, F)
306
307
II |Eip) (do, and (do. F]] ]e [NV ry)], resp. Let
(x = II (E)) jE(P]
(15)
308
The following theorem shows that locality (VEC,)) dramatically reduces both the dimensions of
309
Figendecomposition r 2 eigenspaces and the spectral gap between them. In addition, pooling
310
(i.e. translation symmetry of GAP,,) reduces their dimensions by a factor of p. See Sec.E for the implication of this theorem to learning.
312
Theorem 4.1. (Sec.D) We have the following eigendecompoosition for the interra operator K.
H
U H U U
H(P)
(16)
rEN
rEN FEQ(K.))
where Q(K.r) is a quantifier defined below. Ifr= = O, ((O) is the space of constant functions and the 314 eigenvalue is k(O)). For r 2
313
315
| = r and the unit eigenfunctions are 1. if = KFCN, then Q(K,r) = E (FEE)
H =span span {Yrs) F m7)
(17)
~ dii((((r) ~ dr and ) -d--)((())
2. if = Kivec, Q(K, (FE B(NP, s): |F| = the unit eigenfunctions are 316
H span { (YrS) Te(B(do.F)
dim(H((2c) p(sdo)" snd aatra and X(H( - (sdo))
(18)
8

---

37
Figure 5: Eigenvalue Decay of Relu NTK of FCN VEC, and GAP oc. do = 3. The eigenvalues of GAP,o. decays faster because with m = 15k many samples, higher order eigenspace can be covered by GAP... but not FCN. /VEc. due to Theorem 4.1.
IM= = r), the unit eigenfunc- 3. and finally, if = KGAP, then Q(K,r) { B(NP, 8)T 1M tions are
318
( { GAP dim(H((1)) ~ (sdo)' = s" dra and A(H GAP) ~ "s
-span {
vD Er(( Y=A(TE)
(19)
Related Work
319
The study of infinite networks dates back to seminal work by Neal [8] who showed the convergence of single hidden-layer networks to Gaussian Processes (GPs). Recently, there has been renewed interest in studying random, infinite, networks starting with concurrent work on "conjugate kernels" [10, 35] and onean-field theory" [9, 36), taking a statistical learning and statistical physics view of points, resp. Since then this analysis has been extended to include wide range for architectures [20, 21, 37, 29, 26, 38]. The inducing kernel is often referred to as the Neural Network Gaussian Process (NNGP) kernel. The neural tangent kernel (NTK), first introduced in Jacot et al. [22], along with followup work [12, 39] showed that the distribution of functions induced by gradient descent for infinite- width networks is Gaussian Process with NTK the kernel.
321
323
325
327
329
The study of implicit bias (regularization) of gradient descent has received considerable interests. The work [15, 40-43 demonstrate the convergence of SGD to the maximal margin solution for logistic-type of losses during late time training. [44-50] study early-time SGD dynamics, spectral biases of neural networks. These results aim to explain the order of learning of neural networks: functions of less complexity are usually learned before more complex functions.
331
333
[27] is the first to show that the prediction functions obtained from training FCN depend, in addition on the labels, only on the covariance of the input data. This implies our result regarding the O(3)) invariance of FCN. By utilizing this symmetry, recent work [51] constructs particular task where second order polynomial of the inputs and show that orthogonal invariance algorithm requires sample size of order d² while there is convnet requires only O(1) samples. Their the dg = 8 and r = 2 case of Theorem 4.1, in which the dimension of this eigenspace (and indeed of all r-eigenspace by treating as finite constant as oo) of GAP oa O(1) while the dimension of the 2-eigenspace of FCN is of order d².
335
336
337
the label function
339
convnet essentially corresponds
341
6 Conclusion
342
343
In this paper, we consider machine learning methods as an integrated system of data, models and inference algorithms and study the basic symmetries of various machine learning systems. We surface the importance of locality in modern machine learning systems through large scale empirical study and through an eigendeconposition of one-layer infinite networks. However, we haven't addressed the two import questions (1) theoretical characterization of the effect of composing locality and (2)
344
345
346
348 the mathematical understanding of DIDE and how the prior is corrected by the coupled effect of data and gradient descent. We leave them to future work.

---

Checklist
350
351
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A]. . You are strongly encouraged to include justification to your answer. either by referencing the appropriate section of your paper or providing a brief inline description. For example:
352
353
354
355
Did you include the license to the code and datasets? [Yes] See Section ??.
358
Did you include the license the code and datasets? [No] The code and the data are proprietary.
357
358
Did you include the license to the code and datasets? [N/]]
359
Please do not modify the questions and only use the provided macros for your answers. Note that the
380
Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
361
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
364
365
(b) Did you descrihe the limitations of your work? [Yes]
386
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
368
389
2. If you are including theoretical results...
370
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
371
(b) Did you include complete proofs of all theoretical results? [Yes]
372
3. If you ran experiments..
379
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [No]
374
375
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [No]
376
377
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
378
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [No]
380
381
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
382
(a) If your work uses existing assets, did you cite the creators? [TODO]
383
(b) Did you mention the license of the assets? [TODO]
384
(c) Did you include any new assets either in the supplemental material or as a URL?
[TODO]
386
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [TODO]]
387
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [TODO]
389
380
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [TODO]
392
383
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [TODO]
394
395
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [TODO]
396
10

---

References
397
[1] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances neural information processing systems, pages 1097-1105, 2012.
389
400
[2] 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: 170600376, 2017.
402
[3] Jacob Devlin, Ming-Wei Chang, Kenton Lec, and Kristina Toutanova. Bert: Pre- Pre-training of deep bidirec- tional transformers for language understanding. arXiv preprint 1811:18800004805 2018.
404
[4] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go 2016.
with deep neural networks and tree search. Nature, 529(7587):4844
407
[5] Andrew W Senior, Richard Evans, John Jumper. James Kirkpatrick, Laurent Sifre, Tim Green, Chongli Qin, Augustin Zídek, Alexander WR Nelson, Alex Bridgland, et al. Improved protein structure prediction using potentials from deep learning. Nature, 57777792)7700--711,, 2020.
408
409
410
[6] 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 mmXiv:2001008300 2020.
411
412
415
[7] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
414
415
[8]
Radford M. Neal. Priors for infinite networks (tech. rep. no. 1rg-tr-94-1). University of Toronto, 1994.
[9]
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha expressivity in deep neural networks through transient chaos. In Advances In Neural Information Processing Systems, 2016.
and Surya Ganguli. Exponential
417
418
[10] Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances Neural Information Processing Systems, 2016.
420
421
422
[11] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv: /806, 07572, 2018.
423
[12] Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, 2019.
425
426
427
[13]
Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint arXiv:1709.0195: 2017.
428
[14] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Implicit bias of gradient descent on linear convolutional networks. arXiv preprint arXiv:1806.00 806.00468, 2018.
429
430
[15] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data, 2018
432
[16] Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning, pages
14. PMLR, 2019.
434
[17] Alex J Smola, Zoltan I. Ovari, Robert C Williamson, et al. Regularization with dot-product kernels. Advances in neural information processing systems, pages 308-314, 314,1,,,22 2001.
436
[18] Kunihiko Fukushima. Cognitron: A self-organizing multilayered neural network. Biological cybernetics,
437
20(3-4)1221-333 1975.
438
[19|
Yann Lecun. Generalization and network design strategics. In Connectionism in perspective. Elsevier, 1989.
439
440
[20] Jachoon Lee, Yasaman Bahri, Roman Novak, Sam Schoenholz, Jeffrey Pennington, and Jascha Sohl- dickstein. Deep neural networks as gaussian processes. In International Conference on Learning Repre- sentations, 2018
441
442
443
[21] Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, 2018
444
11

---

448
[22]
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, 2018.
448
[23] Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 11111111110000 1.03804, 2018.
450
[24) Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, 2018.
451
452
[25] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over-parameterized deep relu networks. Machine Learning, 109(3):467-492,2 2020.
453
454
[26] Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 1rXiv:190..047600 2019.
455
[27] Neha S. Wadia, Daniel Duckworth, Samuel S. Schoenholz, Ethan Dyer, and Jascha Sohl-Dickstein. Whitening and second order optimization both destroy information about the dataset, and can make generalization impossible. arxiv preprint arXiv22008.0744. 2020.
457
458
459
[28] Lechao Xiao, Yasaman Bahri, Jascha Sohl- Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dy- namical isometry and a mean field theory of cnns: How to train 1a,00r-layer vanilla convolutional neural networks. In International Conference on Machine Learning, pages 5393-5402, 2018
460
461
462
[29] Roman Novak. Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang. Jiri Hron, Daniel A. Abolafia, Jeffrey Pennington, and Jaseha Sohl-Dickstein Bayesian deep convolutional networks with many channels are gaussian processes. In International Conference on Learning Representations, 2019.
465
464
465
[30]
Adrià Garriga-Alone Alonso, I Laurence Aitchison, and Carl Edward Rasmussen. Deep convolutional networks as shallow gaussian processes. In International Conference on Learning Representations, 2019.
486
467
[31] Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander Alemi, Jascha Sohl- bohl-Dickstein, and Samuel S Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. arXiv preprint arXiv: 1912.0283,, 2019.
468
489
470
[32]
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
471
472
[33] Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung. Daniel Keysers, Jakob Uszkoreit, Mario Lucic, et al. Mlp-mixer: An all-mlp architecture for vision. arXiv preprint arXivv2105.01601, 2021.
473
474
475
[34] Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez- Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2018. URL https:// openreview. wwt/forrmmiidaaeeeeeeee
476
477
Rb.
478
[35] Amit Daniely. SGD learns the conjugate kernel class the network. In Advances in Neural Information Processing Systems 30. 2017.
479
480
[36] Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep information propagation. International Conference on Learning Representations, 2017.
481
[37] Lechao Xiao. Yasaman Bahri, Jascha bohl-Dickstein. Samuel Schoenholz, and Jeffrey Pennington. Dy- namical isometry and a mean field theory of CNNs: How to train 10, 10,000-layer vanilla convolutional neural networks. International Conference on Machine Learning, 2018
483
484
485
[38] Jiri Hron, Yasaman Bahri, Jascha Sohl-Diekstein, and Roman Novak. Infinite attention: Nngp and ntk for deep attention networks, 2020.
486
[39] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pages 2937-2947, 2019.
488
489
[40] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020. URL Id-SJOLIgKKPS.
491
[41] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference 492
Learning Theory, pages 1772-1798, 2019.
494
[42] Ziwei Ji and Matus Jan Telgarsky. Gradient descent aligns the layers of deep linear networks. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
12

---

498
[43] Lénaïc Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings Thirty Third Conference on Learning Theory. volume 125 of Proceedings of Machine Learning Research, pages 1305 1138-133,1111 PMLR, 09-12 Jul 2020, URL http://proceeddng mlr, ppwps//ees...... chizat20a. html.
498
499
500
[44] 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. arXiv preprint arXiv: 1905. 1604, 2019.
501
502
503
[45] Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. The surprising simplicity of the early-time learning dynamics of neural networks. arXiv preprint arXiv:2000.14333 2020.
504
505
[46] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, pages
506
PMLR, 2019.
508
[47] Zhiqin John Xu. Understanding training and generalization in deep learning by fourier analysis. arXiv preprint Xrviv: 808. 04295, 2018
510
[48] Zhi Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light deep neural networks. arXiv preprint arXiv:1901.06522 2019.
512
[49] Lili Su and Pengkun Yang. On learning over parameterized neural networks: A functional approximation perspective. arXiv preprint /905. 10826, 2019.
514
[50]
Greg Yang and Hadi Salman. A fine- fine-grained spectral perspective neural networks. arXiv preprint 2019.
516
[51] Zhiyuan Li, Yi Zhang, and Sanjeev Arora. Why are convolutional nets more sample-efficient than fully-connected nets? arXiv preprint arXiv:2010.085/5. 2020.
13


Reviews:
[{"review_id": "nJH78Yaf1aa", "reviewer": "Reviewer_V4rf", "summary": "The paper studies the implications of various architectural choices on the performance of neural networks, and how they may break the curse of dimensionality. The authors consider fully-connected, locally-connected, locally-connected + weight sharing, and locally connected + global average pooling architectures. They then show, both theoretically and experimentally, how symmetries in the data may affect these architectures differently, at infinite width or finite width (where weight sharing can play a bigger role) under standard initializations. The authors also observe how the learning rates / slopes of learning curves may improve when the amount of data is large enough, particularly for finite networks. Finally, the authors provide spherical harmonic decompositions of the kernels that arise from infinite-width networks with different architectures -- fully-connected, locally connected, or locally connected with global pooling --, observing that local connectivity provides exponential (in the dimension) reductions in the size of eigen spaces, while pooling provides an additional improvement factor of the number of patches.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The question of what allows deep learning to learn efficiently by breaking the curse of dimensionality is important for understanding its success, and the paper provides an interesting and comprehensive study of this with both theoretical and empirical findings. Thus, I think the quality and significance of the paper are quite clear, and it is well written, thus I recommend acceptance.\n\nBelow are a few minor comments:\n- When comparing LCN to VEC, the phrase \"the opposite is also true\" is a bit confusing, since this actually requires more parameters\n- The setting of Figure 1 was a bit difficult to grasp and could be better explained (in the text or caption). If I understand correctly, the same spurious transformation is applied to each example? Also, the y axis lacks a label.\n- For DIDE, do you have an idea/conjecture of what additional \"priors\" are being learnt by the networks at large data regimes for improving these slopes?\n- It would be helpful to add a paragraph after Theorem 4.1 explaining how the improvements in dimensionality/spectral gaps may improve learning efficiency (instead of simply pointing to the appendix)\n- Note that similar questions regarding benefits of locality and/or pooling in kernel regimes have been studied in a few recent papers, e.g., [here](https://arxiv.org/abs/2102.13219), [here](https://arxiv.org/abs/2102.10032), [here](https://arxiv.org/abs/2106.08619). It would be good to provide comparisons at least in the final version of the paper.\n- typos: L74 \"even\" -> \"even when\"?; L163 \"Kernelss\"; L277 \"unrorated\"; L305 \"harmonic\" -> \"harmonics\"\n\n\n-------- update after rebuttal ----------\nThanks for your response. The discussion raised some concerns regarding clarity, and I hope the authors can address these (see comments by reviewer XBfK). Nevertheless, I think these are minor issues which can be addressed for a final version, and the authors' last response to reviewer XBfK makes me confident that they will be properly addressed, thus I decided to raise my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "jZLI5aeb8A5", "reviewer": "Reviewer_dgpq", "summary": "The paper studies the symmetries of the the system (Arch, Data, Algorithm) and provides extensive empirical results. the paperis well-written and flows nicely.", "questions": "", "limitations": "", "rating": 6, "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": "\nAdvantages:\n\n- Understanding symmetry in Deep Learning is still a major open question. This paper introduces a new framework to characterize this symmetry by considering intergated (arch, data, alg) systems. \n\n- The empirical results support the claimed symmetries although (the symmetries) they're not very accurate in some scenarios.\n\n- The paper is well-written\n\n\nWeaknesses:\n\n- The bulk of the analysis relies on the NTK and NTK parameterization. It is now well known that the NTK regimes does not capture what happens in deep neural networks (see, e.g. Yang et al. Feature Learning in Infinite-Width Neural Networks). Does the analysis extend to the standard parameterization (i.e. without the 1/sqrt{n})?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "VwCtxP3cxv", "reviewer": "Reviewer_XBfK", "summary": "This paper tries to understand why a convolutional neural network and its variants with a proper training algorithm can learn to recognize images with only limited training data. Theoretically, by considering the data, model, and inference algorithm as a system, the authors study the symmetries of several different systems, and compute and analyze the eigendecomposition of their corresponding one-hidden-layer infinite-width kernels on spherical input space. The authors also did experiments to study how the symmetries affect the performance of different models on different data and validate their theoretical results on eigendecomposition.", "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": "Originality: It is interesting to study the data, model, and training algorithm as an entire system and analyze its symmetries, which differs from previous research. The related works appear to be adequately cited.\n\nQuality: The theoretical results in this paper seem to be correct, and they are supported by the experimental results.\n\nSignificance:\n\n- The justification for analyzing the symmetry of the data-model-algorithm system seems unclear. This is my major concern about this paper. The authors theoretically showed that different systems have different basic symmetries, and empirically demonstrated that changing the symmetries can affect the performances of the trained models. However, the reason why this change of symmetry is the cause for the change in performances is unclear. The authors did not seem to provide strong theoretical evidence or insights explaining the relationship between symmetry and performance. Besides, in the experiments, changing the symmetries implicitly changes a lot of other factors. For instance, an image with each pixel \"rotated\" on the channel space is no longer a valid image. It might be better if the authors could provide more theoretical insights about the relationship between symmetry and performance so the experimental results can be better justified.\n\n- Studying the data-model-algorithm system as a whole seems to make the analysis in this paper more complicated than directly analyzing the model structure or the data. The symmetry in this paper is defined on the entire system, but this property mainly comes from the symmetries in the model. It also depends on the distribution used for initialization and the training algorithm, but these are almost fixed in reality. Besides, when doing experiments, the authors are also changing one variable at a time. Therefore, it seems unclear why the authors want to analyze the entire system, which is a more complicated object than individual components.\n\n- The authors computed the eigendecomposition of different models' one-hidden-layer infinite-width kernels on a particular input space and validated their results by experiments, but this setting might be too specific, making the results somewhat restricted.\n\nClarity:\n\n- This paper might contain too many claims, and there seems to be a lack of focus. It seems from the abstract and the conclusion section that the authors want to emphasize the important role of locality in helping neural networks escape the curse of dimensionality. However, in the introduction section, especially the contribution part, the authors are making a lot of claims and listing many results, which may confuse the reader. It might be better to shorten the introduction and perhaps re-organize these parts to focus more on the main claim of the paper. Besides, at the end of section 3 where the title is about symmetries, the authors are talking about DIDE, which may be only related to the training data. Moving this part out as a separate section may improve the flow of this paper.\n\n- Some of the experimental details, e.g., the hyperparameter settings, are not mentioned in this paper, which makes their experimental results not convincing enough.\n\n- There are some other parts of the paper that may need minor improvements, and the details will be provided in the \"Minor Comments\" section below.\n\nMinor Comments:\n\n- In line 85, the authors claimed that \"we prove the opposite is true\". What they actually prove is that the function class of $LCN_n$ is a subset of that of $VEC_{dn}$, but the direct opposite seems to be $LCN_n$ versus $VEC_n$. Therefore, this claim may seem a bit misleading.\n\n- For section 2.1, the authors provide many formulas for different network models, and it might be better to also have some figures for the network models so the readers can better understand them.\n\n- In line 190, the notation \"$=^d$\" is not defined.\n\n- In Figure 1, the y-axis is not defined, and the second subfigure has no legend.\n\n- In the experiments in Figure 1 and Figure 3, the authors did not mention the stopping criteria for the training process and it is unclear whether they run each experiment multiple times. They also did not mention why they choose the experimental settings NN/NN+/NN++. These may make their empirical results less convincing.\n\n- Section 4 ends with a theorem and the implications of this theorem are in the appendix. It might be better to summarize the implications in the main text to improve the flow of this paper.\n\nTypos:\n\n- Equation 2: \"$\\sum_{j=1}^{n^l}$\" -> \"$\\sum_{i=1}^{n^l}$\"\n- Equation 3: \"$\\sum_{\\alpha\\in[d]}$\" -> \"$\\sum_{\\alpha\\in[d],i\\in[n]}$\"\n- Line 167: \"where is the infinite width limit of $\\Theta$\" -> \"where $\\Theta$ is the infinite width limit of $\\hat{\\Theta}$\"\n- Line 262, 271, 279: \"Fig. S2\" -> \"Fig. 4\"\n- Line 270: \"which\" -> \"which is\"\n- Line 274: \"the dataset grows, ...... as that of\" -> \"as the dataset grows, ...... that of\"\n\n---------------------Update--------------------------\n\nI have read all the other reviews and the authors' responses, and I have decided to increase my score by 1, i.e., I think it's on the borderline and slightly leaning towards rejection. The detailed reasons for this are provided below:\n\n- After reading the authors' response, the justification for analyzing the symmetries of the data-model-algorithm system becomes more clear to me. Thank the authors for providing examples explaining the role of symmetries in the system, and I agree with the authors that understanding these symmetries is an important step towards understanding the empirical success of convolutional neural networks. It might also be better if the authors could explain more about this in their paper to help the readers better understand the importance of this topic. \n\n- My current major concern is the clarity of this paper, which is the main reason why I am still tending to reject this paper. On the one hand, this paper seems to have a lack of focus. The authors included a lot of content in this paper, but the structure and organization of these contents might need some improvements so that the readers can better understand the core idea of this paper. As I suggested in my original review, a more concise and clear introduction might help a lot. On the other hand, as also suggested by the other reviewers, there are many things that need further clarifications, e.g., the insights and consequences of Theorem 4.1, the \"Conjecture/Ideas of DIDE\", more detailed experimental settings and explanations, and comparisons to some prior works. These modifications may require a major revision of this paper. Therefore, the current form of this paper is perhaps not ready for publication.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly discussed the limitations of their work at the end of this paper, and it may be better to talk more about them. I do not see any immediate negative societal impacts of this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "0fObe263OEe", "reviewer": "Reviewer_cNTz", "summary": "The paper proposed an viewpoint to analyze deep learning methods as an integrated system of data (D), models (M), and inference algorithms (I) by studying the symmetric of the triplet (D, M, I) (in terms of transformations) on specific network models for vision including fully/locally connected networks (F/LCN), convolutional network w/o pooling(VEC/GAP). The key result in symmetry is that when networks are initialized with i.i.d. standard Gaussian distribution, then the considered neural networks are invariant against orthogonal group on the flatten input space when networks are over-parameterized.  ", "questions": "", "limitations": "", "rating": 6, "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": "1. In the DIDE experiments for $VEC_n$, the authors claim that in Figure 3, the learning curve is dramatically speedup in the larger data set regime (# of samples $> 2^{12}$). However, the orange curve does not seem to have dramatic speedup from $2^{11}$ to $2^{15}$ comparing to the rest of the learning models. The authors then claim that it is because the model prior is too large (since $GAP_n \\subseteq VEC_n \\subseteq LCN_n \\subseteq VEC_{dn}$ in (4)). I am not sure if Theorem 2.1 is able to interpret this empirical results. A more thorough discussion is needed.\n\n2. The explanations on the experiment results in Figure 4 (middle) are not clear to me. Do you mean when the images are rotated, it is harder to learn but when as the number of the training samples increases, its become easier to learn (due to DIDE)? Why the red dots are not aligned with the orange dashed line then? How do you make sure the transition of the red dots is entirely due to DIDE? An ablation study is needed. It is possible to understand the benefit of DIDE in a more theoretical manner?\n\n3. The explanation on Theorem 4.1 is also not clear to me. Why there are drops of eigenvalues in Figure 5? Can these drop be explained by Theorem 4? How does the proposed analysis on pooling connect to some existing works on analysis of pooling, e.g., [1]?\n\n[1] Lee, C.Y., Gallagher, P.W. and Tu, Z., 2016, May. Generalizing pooling functions in convolutional neural networks: Mixed, gated, and tree. In Artificial intelligence and statistics (pp. 464-472). PMLR.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies how symmetries and biases associated to various architectural choices may alleviate the curse of dimensionality. The reviewers found the methodology employed by the authors interesting, and generally appreciated the various observations and experiments provided in the paper. That said, the reviewers raised several critical concerns pertaining to presentation (experimental details, in particular), clarity, and focus. Despite the considerable discussion this paper has generated among the reviewers, opinions remained divided whether a substantial revision is needed before the paper can be considered for publication.
Decision: Reject