Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?
Authors: Zhiyuan Li
Yi Zhang
Sanjeev Arora
Venue: ICLR 2021 Oral (2021)
Keywords: sample complexity separation
equivariance
convolutional neural networks
fully-connected

Abstract: Convolutional neural networks often dominate fully-connected counterparts in generalization performance, especially on image classification tasks. This is often explained in terms of \textquotedblleft better inductive bias.\textquotedblright\  However, this has not been made mathematically rigorous, and the hurdle is that the sufficiently wide fully-connected net can always simulate the convolutional net. Thus the training algorithm plays a role. The current work describes a natural task on which a provable sample complexity gap can be shown, for standard training algorithms. We construct a single natural distribution on $\mathbb{R}^d\times\{\pm 1\}$ on which any orthogonal-invariant algorithm (i.e. fully-connected networks trained with most gradient-based methods from gaussian initialization) requires $\Omega(d^2)$ samples to generalize while $O(1)$ samples suffice for convolutional architectures. Furthermore, we demonstrate a single target function, learning which on all possible distributions leads to an $O(1)$ vs $\Omega(d^2/\varepsilon)$ gap. The proof relies on the fact that SGD on fully-connected network is orthogonal equivariant. Similar results are achieved for $\ell_2$ regression and adaptive training algorithms, e.g. Adam and AdaGrad, which are only permutation equivariant.

Published as a conference paper at ICLR 2021
WHY ARE CONVOLUTIONAL NETS MORE SAMPLE- EFFICIENT THAN FULLY-CONNECTEN NETS?
Zhiyuan Li, Yi Zhang
Sanjeev Arora Princeton University & IAS a aroraêcs. www.ccstr..nn.ooo.cmmm edu
Princeton University
zh i thiyuan1i, y zhanglcs wrw.seeccss.iinnoooommm edu
ABSTRACT
Convolutional neural networks often dominate fully- fully-connected counterparts generalization performance, especially on image classification tasks. This is often explained in terms of "better inductive bias." " However, this has not been made mathematically rigorous, and the hurdle is that the sufficiently wide fully-connected net can always simulate the convolutional net. Thus the training algorithm plays role. The current work describes natural task which provable sample complexity gap can be shown, for standard training algorithms. We construct single natural distribution Rd x {+1} which any orthogonal-invaree invariant algorithm (i.e. fully-connected networks trained with most gradient-based methods from gaussian initialization) requires (2(d²) samples to generalize while O(1) samples suffice for convolutional architectures. Furthermore, we demonstrate a single target function, learning which on all possible distributions leads an 0(1) vs (2d2/E) gap. The proof relies on the fact that SGD on fully-connected network is orthogonal equivariant. Similar results are achieved for l2 regression and adaptive training algorithms, e.g. Adam and AdaGrad, which are only permutation equivariant.
INTRODUCTION
Deep convolutional nets ("ConvNets"") are at the center of the deep learning revolution (Krizhevsky et al., 2012; He et al., 2016; Huang et al., 2017). For many tasks, especially in vision, convolutional architectures perform significantly better their fully-connected ("FC"" counterparts, at least given the same amount of training data. Practitioners explain this phenomenon at an intuitive level by pointing out that convolutional architectures have better "inductive bias", which intuitively means the following: (i) ConvNet is better match to the underlying structure of image data, and thus are able to achieve low training loss with far fewer parameters (ii) models withfewer total number of parameters generalize better.
Surprisingly, the above intuition about the better inductive bias of ConvNets over FC nets has never been made mathematically rigorous. The natural way make it rigorous would be show explicit learning tasks that require far more training samples on FC nets than for ConvNets. (Here mmenns, as usual in learning theory, distribution on data points, and binary labels for them generated given using fixed labeling function.) Surprisingly, the standard repertoire of lower bound techniques in ML theory does not seem capable of demonstrating such a separation. The reason is that any ConvNet can be simulated by an FC net of sufficient width, since a training algorithm can just zero out unneeded connections and do weight sharing as needed. Thus the key issue is not an expressiveness per se, but the combination of architecture plus the training algorithm. But if the training algorithm must be accounted for, the usual hurdle arises that we lack good mathematical understanding of the dynamics of deep net training (whether FC ConvNet). How then one establish the limitations of "FC nets + current training algorithms"" (Indeed, many lower bound techniques in PAC learning theory are information theoretic and ignore the training algorithm.)
The current paper makes significant progress on the above problem by exhibiting simple tasks that require 2)d²) factor more training samples for FC nets than for ConvNets, where d is the data dimension. (In fact this is shown even for I I-dimensional ConvNets: the lowerbound easily extends to 2-D ConyNets.) The lower bound holds for FC nets trained with any of the popular algorithms

---

Published as a conference paper at ICLR 2021
Gauss
cilar-10
0.9
0.8
0.8
300
tesl 800
2-Kayer onn wi quadratic
3-kyer onn wi relu
0.7
resnet14
hybrid w/ quadralic
hybrid
2-kyyr wi quadralic
3-byer quadratic
3-kyye wl rell
3-kyer ralu
0.5
10" 10" 0.5
10'
10"
10" training data
10"
10'
10"
10*
training data
Figure 1: Comparison of generalization performance of convolutional versus fullycconnected models trained by SGD. The grey dotted lines indicate separation, and we can see convolutional networks consistently outperform fully-connected networks. Here the input data are 3 x 32 x 32 RGB images and the binary label indicates for each image whether the first channel has larger Eg norm than the second one. The input images are drawn from entry-wise independent Gaussian (left) and CIFAR-10 (right). In both cases, the 3-layer convolutional networks consist of two 3 convolutions with 10 hidden channels, and a 3 3 convolution with a single output channel followed by global average pooling. The 3-layer fully culle-connected networks consist of two fully- fully-connected layers with 10000 hidden channels and another cully-connected layer with a single output. The 2-layer versions have one less intermediate layer and have only 3072 hidden channels for each layer. The hybrid networks consist of single fully-connected layer with 3072 channels followed by two convolutional layers with 10 channels each. bn stands for aach-normalizztion Ioffe & Szegedy (2015).
listed in Table 1. (The reader can concretely think of vanilla SGD with Gaussian initialization of network weights, though the proof allows use of momentum, l2 regularization, and various learning rate schedules.) Our proof relies on the fact that these popular algorithms lead to an orthogonal- equivariance property on the trained FC nets, which says that at the end of training the FC net -no matter how deep or how wide- will make the same predictions even if we apply orthogonal transformation on all datapoints (i.e., both training and test). This notion is inspired by Ng (2004) (where it is named "orthogonal invariant"), which showed the power of logistic regression with & regularization versus other learners. For variety of learners (including kernels and FC nets) that paper described explicit tasks where the learner has (dd) higher sample complexity than logistic regression with & regularization. The lower bound example and technique can also be extended to show a (weak) separation between FC nets and ConvNets. (See Section 4.2)
Our separation is quantitatively stronger than the result one gets using Ng (2004) because the sample complexity gap is (dd2 vs O(1), and not (d) vs 0(1). But in a more subtle way our result is conceptually far stronger: the technique of Ng (2004) seems incapable of exhibiting a sample gap of more than O(1) between Convnets and FC nets in our framework. The reason is that the technique of Ng (2004) can exhibit hard task for FC nets only after fixing the training algorithm. But there are infinitely many training algorithms once we account for hyperparameters associated in various epochs with L.R schedules, lz regularizer and momentum. Thus Ng (2004)'s ss technique cannot exclude the possibility that the hard task for "FC net Algorithm 1" is easy for "FC net + Algorithm 2". Note that we do not claim any issues with the results claimed in Ng (2004); merely that the technique cannot lead to a proper separation between ConvNets and FC nets, when the FC nets are allowed to be trained with any of the infinitely many training algorithms. (Section 4.2 spells out in more detail the technical difference between our technique and Ng's ' idea.)
The reader may now be wondering what is the single task that is casy for ConvNets but hard for FC nets trained with any standard algorithm? A simple example is the following: data distribution in Rd is standard Gaussian, and target labeling function the sign of E x - Σi Ei=d/2+1 x?. Figure shows that this task indeed much more difficult for FC nets. Furthermore, the task is also hard in practice for data distributions other than Gaussian; the figure shows that a sizeable performance gap exists even on CIFAR images with such a target label.
Extension to broader class of algorithms. The orthogonal-equuivrrirne property holds for many types of practical training algorithms, but not all. Notable exceptions are adaptive gradient methods (e.g. Adam and AdaGrad), l regularizer, and initialization methods that are not spherically symmetric. To prove a lower bound against FC nets with these algorithms, we identify a property, permutation- invariance, which is satisfied by nets trained using such algorithms. We then demonstrate a single
2

---

Published as a conference paper at ICLR 2021
and natural task on R x {=1} that resembles real-life image texture classification, on which prove any while Empirical Risk Minimization with (11 examples can learn a convolutional net.
learning algorithm requires ((()) training examples to generalize,
Paper structure. In Section 2 we discuss about related works. In section 3, we define the notation and terminologies. In Section 4, we give two warmup examples and overview for the proof technique for the main theorem. In Section 5, we present our main results on the lower bound of orthogonal and permutation equivariant algorithms.
2 RELATED WORKS
Du et al. (2018) attempted to investigate the reason why convolutional nets are more sample efficient. Specifically they prove (1) samples suffice for learning convolutional filter and also proved a (d) min-max lower bound for learning the class of linear classifiers. Their lower bound is against learning a class of distributions, and their work fails to serve as a sample complexity separation, because their upper and lower bounds are proved on different classes of tasks.
Arjevani & Shamir (2016) also considered the notion of distributiinnsseciffcc hardness of learning neural nets. They focused on proving running time complexity lower bounds against so-called "orthogonally invariant" and "linearly invariant" algorithms. However, here we focus on sample complexity.
Recently, there has been progress in showing lower bounds against learning with kernels. Wei et al. (2019) constructed single task which they proved sample complexity separation between learning with neural networks vs. with neural tangent kernels. Notably the lower bound is specific to neural tangent kernels (Jacot al., 2018). Relatedly, Allen-Zhu & Li (2019) showed sample complexity lower bound against all kernels for a family of tasks, i.e., learning k-XOR on the hypercube.
3 NOTATION AND PRELIMINARIES
We will use X' = =-1,) to denote the domain of the data and label and H. = {h : X' + }/ to denote the hypothesis class. Formally, given a joint distribution P, the error of hypothesis h E H is defined as e == Px [h(x) # v]. If la is a random hypothesis, we define erry(h)= == Px [h(x) + y) for convenience. class of joint distributions supported on X' x )' is referred as problem, P.
We use |1-1|2 to denote the spectrum norm and ||-||,- denote the Frobenius norm of a matrix. We use A < B to denote that B- A is a semi-definite positive matrix. We also use (ld) and GL)d) denote the d-dimensional orthogonal group and general linear group respectively. We use Bdd to denote the unit Schatten-p norm ball in Rdxd
We use N (M, 2) to denote Gaussian distribution with mean and covariance Σ. For random variables X and Y. we denote X is equal to Y in distribution by X L Y. In this work, we also always use Px to denote the distributions on X' and P to denote the distributions supported jointly on X' x ). Given an input distribution Px and a hypothesis h, we define Px o h as the joint distribution on X x V, such that (Px o h)(S) = P((x((x, hx))) E S}), VS C X x y. In other words, to sample (X,Y)= Px o h means to first sample X ~ Px. and then set Y = h(X). For a family of input distributions Px and a hypothesis class H. we define Px o H = {Px o Px E Px, h E H}. In this work all joint distribution P can be written Px o h for some h, i.c. Py₁x is deterministic.
For set S C X and 1-1 map g X + X, we define g(S) = {g(x)) E S). We use to denote function composition. o ()) is defined as f(g(z)), and for function classes F, G. F o G {ʃ g f FF E G). For any distribution Px supported on X' we define Px og as the distribution such that (Pxog) = Px(g(S)). In other words, if X Px = g (X) ~ Px og.
because
SS X
P XxPx
(x)
E S
P X
[X s(S) = PPx gS))
3

---

Published as a conference paper at ICLR 2021
Algorithm Iterative algorithm A
Require: Initial parameter distribution P Piit supported in W R", total iterations T, training
dataset {xt, V= parametric model M W + H. iterative update rule F(W, MM, (x11))))1))
Ensure: Hypothesis h X >.
Sample W ~ Pinit-
for 1 =
do
W F( F(W()) .M, (x, 31 1
return h sign [T]]
For any joint distribution P of form P Px h, we define Pog= (Px o g) o (h o g). In other words, (X, Y) P = (g- (X), Y) P Pog, g. For any distribution class P and group 9 acting on X. we define P o G (Pog P
Definition 3.1. A deterministic supervised Learning Algorithm A is mapping from sequence of training data, {xx -- E (X' x 2))", to hypothesis A({(x, Hi))))) E H. C y The algorithm A could also be randomized, in which case the output AA (x,, 34 (=))= 1) is distribution on hypotheses. Two randomized algorithms A and A' are the same if for any input, their outputs have
(x(xx,
the same distribution in function space, which denoted by A((x,, y4 Mi = ((xx
Definition 3.2 (Equivariant Algorithms). A learning algorithm is equivariant under group Gx (or "x-equivariant) and only if for any dataset (x,,3:1=: E (X x ))" and vig E 9x. x E N, A({g(x;), 91 )>)=)))>>> ) g = A((x,, yi }==z), or Definition 3.3 (Sample Complexity). Given problem P and randomized learning algorithm A. 5,8 E [o, 1), we define the (s, J-sample complexity, denoted (,, as the smallest number N such that /P P. w.p. 1 ö over the randomness of {x,, yt ) j1=1- erry(A( (x;, 9:)) We also define the e-expected sample complexity for a problem P. denoted N (A,, as the smallest number
= [A([x, yi [
such that VP P. E
[errp(A((x) Xx 3=)==)))) S s. By definition, we S (A,,,)E)) Ve, [0, 1].
(N
have (A, S N(A, &
3.1 PARAMETRIC MODELS AND ITERATIVE ALGORITHMS
A parametric model M W + H is functional mapping from weight W to hypothesis M(-) : X + V. Given a specific parametric model M, a general iterative algorithm is defined as Algorithm 1. In this work, we will only use the two parametric models below, FC-NN and CNN.
FC Nets: A L-layer Fully-connected Neural Network parameterized by its weights W
(W1, W2. .... WL) is function FC-NN[-] Ed IR where We Rdi-1xd; do d, and dp = 1:
FC-NN[W]xx) = WW ... o (Wix)))
Here, 0 RR + R can be any function, and abuse the notation such that is also defined for vector inputs, in the sense that [x))] = (zz)).
ConvNets (CNN): In this paper will only use two layer Convolutional Neural Networks with one channel. Suppose d = d'r for some integer d', r, a 2-layer CNN parameterized by its weights W (w, a, b) R R" x R is function CNN(:
Rdd R:
CNN(W](x) = Σ a,o([
+ b,
where : x Rd Rdd is the convolution operator, defined [w+x]: Σイ= 1 d|1 and σ Rd R is the composition of pooling and element-wise non-linearity.
3.2 EQUIVARIANCE AND TRAINING ALGORITHMS
This section gives an informal sketch of why FC nets trained with standard algorithms have certain equivariance properties. The high level idea here is if update rule of the network, more generally,
For randomized algorithms, the condition becomes A(fg(x:), v. o & A((xi, ye y )in)) which is stronger than A((g(x;), vo yo (x()) [A(xx, y1 Ho (xx), Vx X.
4

---

Published as a conference paper at ICLR 2021
Symmetry
Sign Flip
Permutation Permutation
Orthogonal
Linear
Matrix Group
Diagonal, Ma =
Orthogonal
Invertible
Algorithms
AdaGrad, Adam
AdaGrad, Adam
SGD Momentum
Newton's 's method All zero
Initialization
Symmetric distribution
i.i.d.
i.i.d. Gaussian
Regularization
Ep norm
6 norm
& norm
None
Table I: Examples of gradient-based equivariant training algorithms for FC networks. The initializa- tion requirement is only for the first layer of the network.
the parametrized model, exhibits certain symmetry per step, i.c., property Theorem C.I, then by induction it will hold till the last iteration.
Taking linear regression as an example, let X; R i [n|] be the data and y E R" be the labels, the GD update for [(w) = (x] w - 31)2 = X w -yll would be Wa+1 = F(W,, x) Wt- - - Wt -y). Now suppose there's 's another person trying to solve the same problem using GD with the same initial linear function, but he observes everything in a different basis, i.e., X' = UX and w/ Uwo for some orthogonal matrix U. Not surprisingly, he would get the same solution for just in different basis. Mathematically, this is because w/ = Uww = U In other words, he would make the same
W'+1 = F'(w', UX, y) U F(w,, y) prediction for unseen data. Thus if the initial distribution of Wo is the same under all basis (i.e., under rotations), c.g., gaussian .V (0, Ia), then we = Uw =
("Wo UX. = U U (wo. X. y), for any iteration f, which means GD for linear regression is orthogonal invariant.
d
To show orthogonal equivariance for gradient descent on general deep FC nets, suffices to apply the above argument each neuron in the first layer of the FC nets. Equivariance for other training algorithms (see Table 1) can be derived in the exact same method. The rigorous statement and the proofs are deferred into Appendix C.
4 WARM-UP EXAMPLES AND PROOF OVERVIEW
4.1 EXAMPLE 1: M(d) LOWER BOUND AGAINST ORTHOGONAL EQUIVARIANT METHODS
We start with a simple but insightful example to how equivariance alone could suffice for some non-trivial lower bounds.
We consider task on I {+1} which is uniform distribution on the set ((e.y, u) E (1. d).y y = +1}, denoted by P. Each sample from is a one-hot vector in Rd and the sign of the non-zero coordinate determines its label. Now imagine our goal is to learn this task using an algorithm A. After observing a training set n labeled points S ;= {(x,, yi) y/)) the algorithm is asked to make prediction on an unseen test data x, i.e., (()) Here we concerned with orthogonal equivariant algorithms
the prediction of the algorithm on the test point remains the same even if we rotate every z; and the test point by any orthogonal matrix R, i.e.,
A((, y: () d A(((x, 3:) H+)))))
Now we show this algorithm fails generalize on task P. if observes only d/2 training examples. The main idea here is that, for fixed training set S, the prediction A({ v1) } (x) is determined solely by the inner products between x and x; 's due to orthogonal equivariance, i.e., there exists a random function f (which may depend on S) such that?
A(f(x;, y.) () _ f(x" ((xx"x..... ,I.,,,,,"'' x,,)
But the input distribution for this task is supported time the probability is at least 1/2 that the new data point (x, ~ P, is such that x has zero inner product with all n points seen the training set S. This fact alone fixes the prediction of A to the value f(O..... O) whereas is independently and randomly chosen to be +1. We conclude that A outputs the wrong answer with probability at least 1/4.
1-hot vectors. Suppose d/2. Then at test
"this can he made formal using the fact that Gram matrix determine set of vectors up to orthogonal transformation.
5

---

Published as a conference paper at ICLR 2021
4.2 EXAMPLE 2: (2(d)) LOWER BOUND IN THE WEAK SENSE
The warm up example illustrates the main insight of (Ng, 2004), namely, that when an orthogonal equivariant algorithm is used do learning on certain task, it actually being forced to simulta- neously learn all orthogonal transformations of this task. Intuitively, this should make the learning much more sample-hunge compared to even Simple SGD on ConvNets, which is not orthogonal cquivariant. Now we sketch why the obvious way to make this intuition precise using VC dimension (Theorem B. does not give a proper separation between ConvNets and FC nets, as mentioned the Introduction.
Algorithm A is orthogonal equivariant (Definition 3.2) means that for any task P Px o h", where Px is the imput distribution and h' is the labeling function, A must have the same performance on P and its rotated version P o U = (Px o U) o (h* o U), where U can be any orthogonal matrix. Therefore if there's an orthogonal equivariant learning algorithm A that learns h" on all distributions, then A will also learn every the rotated copy of h", h² U, on every distribution Px. simply because A learns h' on distribution Px U-1 Thus A learns the class of labeling functions h" (dd) == {x(x) = (x)( U E { on all distributions. (See formal statement in Theorem 5.1) By the standard lower bounds with VC dimension (See Theorem B.1), takes at samples for to guarantee 1 - E accuracy. Thus it suffices to show the VC dimension VCdim (H/ (d)) = (dd)), ) towards a (dd²) sample complexity lower bound. (Ng (2004) picks a linear thresholding function h², and thus VCdim(h* O(d)) is only O(d).)
We first fix the ground truth labeling function h" = sign E ot - Ei 2i
least ! (d)))))
Formally, we have the following theorem, whose proof is deferred into Appendix D.2: Theorem 4.1 (All distributions, single hypothesis). Let p {all distributions} {h*}. For any orthogonal equivariant algorithms A, (A,, P,e, 6) = (dd + In f))s), while there's 2-layer ConvNet architecture, such that (EEMMNNN P. = O (1 (log _ + log 1))
As noted in the introduction, this doesn't t imply there is some task hard for every training algorithm for the FC net. The VC dimension based lower bound implies for each algorithm the existence of a fixed distribution Px E P and some orthogonal matrix UA such that the task (Px o Uă²) ) h" is hard for it. However, this does not preclude (Px o U² }) h² being easy for some other algorithm A'.
4.3 PROOF OVERVIEW FOR FIXED DISTRIBUTION LOWER BOUNDS
At first sight, the issue highlighted above (and in the Introduction) seems difficult to get around. One possible avenue is if the hard input distribution Px in the task were invariant under all orthogonal transformations, i.e., Px = Px o U for all orthogonal matrices U. Unfortunately, the distribution constructed in the proof of lower bound with VC dimension is inherently discrete and cannot be made invariant to orthogonal transformations.
Our proof uses fixed Px. the standard Gaussian distribution, which is indeed invariant under orthogonal transformations. The proof also uses the Benedek- Itai's lower bound, Theorem 4.2, and the main technical part of our proof is the lower bound for the the packing number D(H, p. defined below (also see Equation (2)).
For function class H. we use (n)) to denote the growth function of H. i.e. ln) sup (((((1)), M(z2).... ,((x)) h HH]. Denote the VC-Dimension of H by VC)im(H(.
B E.......EE.. EX
VCdim('H)
by Sauer-Shelah Lemma, we know (1x(()) <
for > VCdim(H).
VCdim[FF
Let p be a metric on H. We define N(H,P,e) as the e-covering number of H w.r.t. P. and D(H. p, as the E-packing number of H. w.r.t. P. For distribution Px, we use px px h²) == Px~Px [h(X) # h')X) to denote the discrepancy between hypothesis h and h' w.r.t Px. Theorem 4.2. [Benedek- Itai's lower bound] For any algorithm A that (e, 8)-lamms H with n i.i.d. samples from a fixed distribution Px, it must hold for every
Tx (n) 2 (1 (H, 2s) 2x)
Since 11 2", we have (NA, o H. )) 2 log, D(H. px. 2x) + log 6), which the original bound from Benedek & Itai (1991). Later Long (1995) improved this bound for the regime

---

Published as a conference paper at ICLR 2021
VCdim((H) using Sauer-Shelah lemma, i.e.,
M(A, Px,5,0) N VCdim(H) (11-)D(HH, px: 22)) veamery
(2)
Intuition behind Benedek-Itai's lower bound. We first fix the data distribution as Px. Suppose the 2 2e-packing is labeled as fhi..... ........,(((L..)) (P..x.x))2)) and ground truth is chosen from this 2c 2e-packing. (eean- the hypothesis H. means the algorithm is able to recover the index of the ground truth w.p. 1- 6. Thus one can think this learning process as noisy channel which delivers log, D(H, Pxx 2τ) bits of information. Since the data distribution is fixed, unlabeled data independent of the ground truth, and the only information source is the labels. With some information- -hhoorett inequalities,
we can show the number of labels, or samples (i.e., bits of information) (M,, Px o H,E. 8) Z log, (H, px, 2s) 21)+ (1-6). A more closer look yields Equation (2), because when VCdim(H) oo, then only log, 12 (n1 instead of bits information can be delivered.
5 LOWER BOUNDS
Below we first present reduction from special subclass of PAC learning to equivariant learning (Theorem 5.1), based on which we prove our main separation results, Theorem 4.1, 5.2, 5.3 and 5.4.
Theorem 5.1. If Px is a set of data distributions that is invariant under group 9x. i.e., PxoGx = Px, then the following inequality holds. (Furthermore it becomes equality when Gx is compact group.)
inf N (A, Px o oH, inf N' (H o 9x), AEAax
AEA
Remark 5.1. The sample complexity in standard PAC learning is usually defined again hypothesis class H only, i.e., Px is the set of all the possible input distributions. In that case, Px is always invariant under group 9x, and thus Theorem 5.1 says that Gx-equivariant learning against hypothesis class H. is as hard as learning against hypothesis H Gx without equivariance constraint.
5.1 (dle) LOWER BOUND FOR ORTHOGONAL EQUIVARIANCE WITH A FIXED DISTRIBUTION
In this subsection we show l(d)) vs O(1) separation a single task in our main theorem (Theo- rem 5.2). With the same proof technique, we further show we can get correct dependency on e for the lower bound, i.e., (((E)) ). by considering slightly larger function class, which can be learnt by ConvNets with ((d) samples. We also generalize this (dd)) vs (d) separation to the case of l regression with a different proof technique.
Theorem 5.2. There's a single task, Px o lt,,, where h = sign Σ x² - Ei 25 and
Px = (O, I2a) and a constant Eo > O, independent of d, such that for any orthogonal equivariant algorithm A, we have
(A 2ldd))
(4)
while there's a 2-layer ConvNet, such that N (ERMONN Px o h = O (log + log ))) Moreover, ERMcNN could be realized by gradient descent (on the second layer only).
Proof of Theorem 5.2. Upper bound: implied by upper bound in Theorem 4.1. Lower bound:
Note that the Px (O, T2a) invariant under ((d). by Theorem 5.1, suffices to show that there's constant Eo > 0 (independent of d), for any algorithm A, it takes !(d?) samples to learn the augmented function class h² (2d) w.r.t. Px = NO, I2a). Define ho = sign [x[aU x241:2d]. VU e dx and by Lemma D.2, have H {hy U O(d)} C h- o O(d)). Thus it suffices to a ((d)) sample complexity lower bound for the sub function class H. i.c.
(A, N (0, 12a) o {sign [x]_aU 1.2 50) = 12dd)). By &Itase lower bound, (Benedek & Itai, 1991) (Equation (1)), we know W(A, P.6.& 8) 2 log, ((1 - (H,, pxx 25o)).
(5)
(6)
By Lemma D.4, there's some constant C, such that DxH, e) (9)
--- did-1)
Ve 0.
7

---

Published as a conference paper at ICLR 2021
The high-level idea for Lemma D.4 is first show that px(he, (vv 2 S2( 11111 [1-- ) and then we va
show the packing number of orthogonal matrices in a small neighborhood of la w.r.t. lille is roughly vd
the same that in the tangent space of orthogonal manifold at La, i.e., the set of skew matrices, which is of dimension did-1) and has packing number ( d(4-12 The advantage of working in the 2
tangent space is that we can apply the standard volume argument.
Setting 8 -/2 we have N (A, 2 (A, 250) 2 -'d log2
C = S2(d)).
TEo
Indeed, we can improve the above lower bound by applying Equation (2), and get
1 e 2
d²
+ /CC -
N MAP.P, 2
Note that the dependency in E in Equation (7) is E 2 is not optimal, as opposed to e in upper bounds and other lower bounds. A possible reason for this might be that Theorem 4.2 (Long's s improved version) is still not tight and it might require a tighter probabilistic upper bound for the growth number (n), at least taking Px into consideration, as opposed to the current upper bound using VC dimension only. We left it as an open problem to show a single task P with 2 sample complexity for all orthogonal equivariant algorithms.
However, if the hypothesis is of VC dimension (dd) using a similar idea, we can prove a M(d /s) sample complexity lower bound for equivariant algorithms,, and ((d) upper bounds for ConyNets. Theorem 5.3 (Single distribution, multiple functions). There is a problem with single input distribu- tion, = {Px} o H = {0 Ia)} {sign Di= a,2;] ag E IR), such that for any orthogonal equivariant algorithms AA and E > 0, (A, = ((dP///)) while there's a 2-layer ConvNets architecture, such that ((EMMcNN e, 8) 0 dlog + $).
Interestingly, can show analog of Theorem 5.3 for &g regression, i.e., the algorithm not only observes the signs but also the values labels y;- Here we define the E, loss of function h Bdd - R as (h) = E [(h(x) ") and the sample complexity N² (A, A,P,)) for Eg loss similarly as
(x,y)~p
the smallest number n E N such that VP EP,
E
E
[v"] The
(x..
(a,y)~p
last term
[y²] is added for normalization to avoid the scaling issue and thus any could (P
E
be achieved trivially by predicting 0 for all data.
Theorem 5,4 (Single distribution, multiple functions, l regression). There is problem with single
input distribution, P {Px} H {0, 1a)} {Ei d
ax, a; E R}. such that for any orthogonal equivariant algorithms A and æ > O* (A, P,E) > did+3) (1 E) - 1, while there's a 2-layer ConvNet architecture, such that ~\* (ERMcNN, P. E) I d for any >> 0.
5.2 (dd LOWER BOUND FOR PERMUTATION EQUIVARIANCE
In this subsection will present R(d) lower bound for permutation equivariance via different proof technique - direct coupling. The high-level idea of direct coupling is to show with constant probability over (X,, x). we can find a g E Gx. such that (X,,,) X,, but x and g(x) has different labels, in which case no equivariant algorithm could make the correct prediction.
Theorem 5.5. Let t; = e, + e;+1 and s; = e; + e.42² and P. be the uniform distribution on {(s;, 1) [[tt,, 1)) which is the classification problem for local textures in a I-dimensional image with d pixels. Then for any permutation equivariant algorithm A, M(A, $. > (AA.P, 2 10- Meanwhile, A/(ERMENN: P,0, 5) log, 2, where ERMONN stands for ERMONN for function class of 2-layer ConvNets.
Remark 5.2. The task could be understood as detecting there are two consecutive white pixels in the black background. For proof simplicity, we take texture of length 2 as an illustrative example. It
For vector E R. define x; [ mod d.
8

---

Published as a conference paper at ICLR 2021
is straightforward to extend the same proof to more sophisticated local pattern detection problem of any constant length and to 2-dimensional images.
6 CONCLUSION
We rigorously justify the common intuition that ConvNets can have better inductive bias than FC nets, by constructing single natural distribution on which any FC net requires Mdd²) samples to generalize if trained with most gradient-based methods starting with gaussian initialization. On the same task, O(1) samples suffice for convolutional architectures. We further extend our results to permutation equivariant algorithms, including adaptive training algorithms like Adam and AdaGrad, & regularization, etc. The separation becomes ((d) vs O(1) in this case.
REFERENCES
Zeyuan Allen-Zhn and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems. pp. 9015-9025, 2019.
Yossi Arjevani and Ohad Shamir. On the iteration complexity of oblivious first-order optimization algorithms. In International Conference on Machine Learning, pp. 908-916, 2016.
Gyora M Benedek and Alon Itai. Learnability with respect to fixed distributions. Computer Science, 86(2):377-38, 1991.
Theoretical
Anselm Blumer, Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the vapmik-chervonenkis dimension. J. ACM, 36(4):929-965, October 1989. ISSN 0004-5411, doi: 10.1145776399.63771. URL http:: /ooi 1rg//...114///1333 76371.
Simon S Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Russ R Salakhutdinov, and Aarti Singh. How many samples are needed estimate convolutional neural network? In Advances in Neural Information Processing Systems, pp. 373-383, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708. 2017.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint 1rXiv:1502.03167, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances neural information processing systems, pp. 8571-8580, 2018
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1 105, 2012.
Philip M. Long. On the sample complexity of PAC learning half-spaces against the uniform distribu- tion. IEEE Transactions on Neural Networks, 6(6):1556-1559) 1995.
Zongming Ma and Yihong Wu. Volume ratio. sparsity, and minimaxity under unitarily invariant norms. IEEE Transactions on Information Theory, 61(12):6939-693 6956, 2015.
Andrew Y Ng. Feature selection, 1 1 1 regularization, and rotational invariance. In Proceedings of the twenty-first international conference on Machine learning, pp. 78, 2004.
Stanislaw J Szarek. Metric entropy of homogeneous spaces. arXiv preprint math/9701213, 1997.

---

Published as a conference paper at ICLR 2021
Michel Talagrand. Upper and lower bounds for stochastic processes: modern methods and classical problems, volume 60. Springer Science & Business Media, 2014.
Roman Vershynin. High-Dimensionel Probability; An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2018 doi: 10.1017/978 108231596.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems, pp. 9709-9721, 2019.
10

---

Published as a conference paper at ICLR 2021
A
SOME BASIC INEQUALITIES
Lemma A.1.
Vx E [-1,1],
arccOs
2 V2.
v1 - 1
Proof. Let x cos(t), E [- n], we have (r)cos(x)
cos(t) v2sin(1/2) 2 2/2.
---
Lemma A.2. 3C' 0, PA E N M Rdxd
C M /Vd//
E
|||x|||]]
|M /vd.
(8)
X
Proof of Lemma A.2.
Upper Bound: By Cauchy-Schwarz inequality, we have
tr[MMT]
||
E Sa-1
[1
I
|
2
M
xx
MT
Sa-1
8a-1-1
d
Vd
Lower Bound: Let M U.VT be the singular value decomposition of M, where U, V are orthog- onal matrices and Σ is diagonal. Since || = ||>|| p. and
X~ [||x = E
E
[| 2
x
w.l.o.g.. we only need to prove the lower bound for all diagonal matrices.
By Proposition 2.5.1 in (Talagrand, 2014), there's 's some constant C, such that
C ||
Σ
E ((..aa
[||
x~N(0.1a)
By Cauchy-Schwar Inequality, we have
[|x|||] 5
||x
Vd. Therefore,
x~N(0..1)
V N()
we have
CI F
E
[|
E
M&
E
[||[|]]
S~aa-1
x (1..
18
[||]|]
vd,
8~
which completes the proof.
Lemma A.1. For any have
2 V o
Pr (| < S
M(0,0)
Proof.
(- x²
z
Pr (|x) 2) (0,
exp
202 -200
S
V2T
11

---

Published as a conference paper at ICLR 2021
B UPPERAND LOWER BOUND FOR SAMPLE COMPLEXITY WITH VC DIMENSION
Theorem B.1. [Blumer er al. (1989)] If learning algorithm A is consistent and ranged in H. i.e.
A( (-)) E H. and ())=))()) = Vi E [n], then for any distribution Px and 0 E, < L, we have
N(A. H, VCdim H) In
(10)
E
Meanwhile, there's distribution Px supported any subsets {xo, ; Td-1) 1) which be shat- tered by H. such that for any O < e, < and any algorithm A, it holds
((A, Px o 0,, VCdim In
(11)
C EQUIVARIANCE IN ALGORITHMS
In this section, we give sufficient conditions for an iterative algorithm to be equivariant (as defined in Algorithm 1).
Theorem C.1. Suppose Gx is group acting on X' = Rd the iterative algorithm A is Ex-equivariant (as defined Algorithm 1) if the following conditions are met: (proof in appendix)
1. There's group Sw acting on W and group isomorphism M[T(g)(()) (W)](((x) = M[W][() Vx E X, W E W.g E G. (One can think as the rotation U applied on data linear regression and r(U) as the rotation U applied on w.)
Gx Gw, such that
2. Update rule F invariant under any joint group action (g. T(g)), Vg E G. In other words, (FW))) (xi w)==))) (([(())(())) (x(), Vi).=1).
3. The initialization Panis is invariant under group Gw. i.. Vgg E Gw, Panit = Pinit o og
Here we want address that the three conditions in Theorem C.1 are natural and almost necessary. Condition is the minimal expressiveness requirement for model M to allow equivariance. Condition 3 is required for equivariance at initialization. Condition necessary for induction.
Proof of Theorem C.I. Vg Gx, we sample ())), Pinits and ( +(()(((())
By property (3), W d (()) Pinit- Let W(+11) = = (W .M, {xi, v1) and W(+1) show W(O -(g) (()) by induction
F (1)), MM, (9(x;), ) for 0 < T - 1.
using property (2), By definition of Algorithm 1, we have
Afx, W 4 MW(()
and
M[ - Alfo(z)), og.
By property (I), we have M((())(((()) ( M[W(T((x). There- fore, A(Ix;, (()x, & M[W(?) M[WeO] o = Allg(x)), v. o g. meaning A is Gx-equivariant.
Remark C.1. Theorem C.1 can be extended to the stochastic case and the adaptive case which allows the algorithm to use information of the whole trajectory. i.e., the update rule could be generalized
as (+++1) Fi(( (((((())) y= M, {x,, 34 )=)))) as long as (the distribution of) each F, is invariant under joint transformations.
Below are two example applications of Theorem C.I. Other results in Table could be achieved in the same way.
12

---

Published as a conference paper at ICLR 2021
For classification tasks, optimization algorithms often work with differentiable surrogate loss 8 IR - IR instead the 0-1 loss, such that ((gh(x)) 2 1 [yg(x) S 0), and the total loss for hypothesis h and training, ((M(W); (x,, Vi )==1 is defined as > E(y M(W)[(x;)) It's also denoted by L(W) when there's no confusion.
Definition C.1 (Gradient Descent for FC nets). We call Algorithm Gradient Descent if M FC-NN and F = GD where GD (W) = W (VL is called the one-step Gradient Descent update and ?) > is the learning rate.
Algorithm 2 Gradient Descent for FC-NN (FC networks)
Require: Initial parameter distribution Pinst total iterations T, training dataset (xi, y/ W: loss
function &
Ensure: Hypothesis h : X' V. Sample (0)) P Pmna-
for & 0 to T do
(IFC-NN(((()(x...)))) return h sign [FC-NN[W(T]].
W(++)) (())
Corollary C.2. Fully-connected networks trained with (stochastic) gradient descent from i.idd. Gaussian initialization is equivariant under the orthogonal group.
Proof of Corollary C.2. We will verify the three conditions required in Theorem C.1 one by one.
The only place we use the FC structure for the first condition.
Lemma C.3. There's s subgroup Gw of (m)) and a group isomorphism T : Gx = O(d) + Gw. such that FC-NN(=(R) R FC], VW E W, R Gx.
Proof of Lemma C.3. By definition, FC-NN[W] could be written FC-NN|W2:.(oo(M)
which implies FC-NN W (x) = FC-NN[ R W2.L] VR E Od), and thus we can pick T(R) O (m), where O(W) [W W2.L), and Gw (O)))).
O
A notable property of Gradient Descent is that it is invariant under orthogonal re-parametrization. For- mally, given loss function C Rm E and parameters W E R" an orthogonal ee-parmmetrization of the problem is to replace (c, W) by (C o o OWW, where O E mm is an orthogonal matrix.
Lemma C.4 (Gradient Descent invariant under orthogonal p--arametizzaion). For any C, W and orthogonal matrix O E Rmxm, we have OGD,(W) = GD (OW).
Proof of Lemma C.4. By definition, suffices to show that for each i e [n]. and every W and W' OW.
OV (FW(FFCNN(W))(xx.uk = w (FC-NNN(O (x).)))
which holds by chain rule.
For any RE E Old), and set O = T(R) by Lemma C.3, (C o (-) EE (W = - ((.FCC-NN([((Xx)) The second condition in Theo- rem C.I is satisfied by plugging above equality into Lemma C.4.
The third condition is also satisfied since the initialization distribution i.i.d. Gaussian, which is known to be orthogonal invariant. In fact, from the proof. it suffices to have the initialization of the first layer invariant under Gx-
Corollary C.5. FC nets trained with newton's method from zero initialization for the first layer and any initialization for the rest parameters is euuiivrquiaari or equivariant under the group of invertible linear transformations.
Here, Netwon's 's method means to use NT(W) = W (VV'C(W))-IC((W)) and we assume V2L(W) is invertible. Proof is deferred into Appendix,
(V((W) as the update rule
13

---

Published as a conference paper at ICLR 2021
Proof of Corollary C.5. The proof is almost the same that of Corollary C.2, except the following modifications.
Condition 1: If we replace the O(d), ((m) by G in the statement and proof Lemma C.3, the lemma still holds.
Condition 2: chain rule, invertible linear re- pa-aammtizzaiin, i.e. (G) = NT NTcco-((OW) for all invertible matrix O.
verify the update rule Newton's method is invariant under
Condition 3: Since the first layer is initialized to be 0, it is invariant under any linear transformation.
Remark C.2. The above results can be easily extended the case of momentum and Lp reg- ularization. For momentum, we only need to ensure that the following update rule, W(++1) GDM(W(1)) ((t-1), M,, {xx, )=)==1) (1 + 7) W()) (W(+-1) T)VL()())) also satisfies the property in Lemma C.4. For Lp regularization, because || [|]], independent of {xi, Mi we only need to ensure || [[)]l)) VR 9x, which is easy to check when Gx only
contains permutation or sign-flip.
C.1 EXAMPLES OF EQUIVARIANCE FOR NON-ITERATIVE ALGORITHMS
To demonstrate the wide application of our lower bounds, we give two more examples of algorithmic cquivariance where the algorithm is not iterative. The proof's are folklore.
Definition C.2. Given a positive semi-definite kernel K, the Kernel Regression algorithm REG is defined as:
K(NN REG (xx, 3e 3ell-1) (x)) := [K(xxX)) X M(XN,NN)'> 2 20]
where K(XN: XN) E RT [K XN)lss = K(x,,x)), y = 121, y2. 9N! UN] and K(x, XN)
K (X, x1),
xxx,
Kernel Regression: kernel is Gx-equivariant, i... Vg E 9x,x,y E X, K(g(x).g(y)) = K(x,y) y). then algorithm REG is Gx-equivariant. ERM: = F o Gx. and argmin 1 [h(x,) + ysl is unique, then ERM, is Gx- equivariant.
D OMITTED PROOFS
D.1 PROOFS OF SAMPLE COMPLEXITY REDUCTION FOR GENERAL EQUIVARIANCE
Given Ex-equivariant algorithm A, by definition, d (A), - ,e), Vg Gx. Consequently, we have
=
(12)
Lemma D.1. Let & be the set of all algorithms and Agx be the set of all Gx-equivarian algorithms, the following inequality holds. The equality is attained when Ex compact group
inf (A 2 inf (A, Gx AEEOX
(13)
AEA
Proof of Lemma D.1. Take infimum over Aggx over the both side of Equation 12, and note that Agx A. Incquality 13 immediate.
Suppose the group 9x is compact and let be the Haar measure on it, i.c vS c Gx.g E Gx, ((S) = (go We claim for each algorithm A, the sample complexity of the following equivariant algorithm A' is no higher than that of A on P Gx:
A' A'((x, (x, ye ) A(lg(x;), ) og where g ~ p.
By the definition of Haar measure, A' is Gx-equivariant. Moreover, for any fixed n 2 0, we have [errp (A' ".) PEP grvu (x..:t)~Po
inf
inf E. E
[errp(A([xx) w)
PEP (
14

---

Published as a conference paper at ICLR 2021
inf inf PEP ge9x (x.,))~aag-- [errp(A((x;)))))) V/ [=)l=
inf
E
[etTp(A(fx: Vi ())=,)))
PEPoGx (x..8))
which implies inf AEAGY N (A, (A, 9x,
Proof of Theorem 5.1. Simply note that (PxoH)oGx = Uyee (Px (Pxog)o(Hog) = UpERr Pxo (Ho Px o (H o 9x), the theorem is immediate from Lemma D.I.
D.2 PROOF OF THEOREM 4.1
Lemma D.2. Define hy sign XTTal x2+1:2d) VU E RRd we have H = {bu UU E O(d)) S
sign
Σ 2i=1 o7
2i-d41 2ē O(dd).
Proof. Note that
0
U
la
0
0
Ia 0
Ia
0 U
UT
=
0
U
Ia
and
0
la]
v2 Ia
22 la
la
0
22
L 1a
2
2
La
0
/
Ta
2
Td
0
- -P
1/2 Ia
Ta
2
thus for any U E (d), Vx E R2dd
U
hx(x) = sign [x U x4+1:20]
= sign
x
UT
x
(14)
La
sign (x) T
g0 (x)
E h" o ((dd),
0
-ld
Ta
0 U
V2 Is
v2 Ia
where gu (x)
2
2
x an orthogonal transformation on 2ddd
Is
y
1a
2
Lemma D.3. Define hy sign [x x441:20] YU Rdxd and H (ho U E O(d)), have
VCdim (H) > d(d ((d-1)
Proof. Now we claim H shatters (e: + ea-jhsiessa iee O(d) can shatter {e,e] hissssa, or for any sign pattern {ois) Iisigig there exists U E O(d), such that sign (U,,,e]) oij. which implies VCdim(HL 2 d(d-1)
Let so(d) = {M M - MT, .M E Rddxd,, we know
exp(u) La +
+... e... SOO(d) Vu E so(d).
2
Thus for any sign pattern {arg 1siissdd let ===
Σ oiy(c,0] c,c,) and À + 0+,
Isicjsd
sign (exp(Au)) ) sign (0 + Aay + 0(2)) = sign (o + 0()) = Gij.
Theorem 4.1 (All distributions, single hypothesis). Let {all distributions) + {h*}. For any orthogonal equivariant algorithms A, [AA,, P, 6) (df + In f)/s), while there's 2-layer ConvNet architecture, such that (EEMMNNN. P.e,ō) O (log ! + +og 1
15

---

Published as a conference paper at ICLR 2021
Proof of Theorem 4.1. Lower bound: Suppose d 2d' for some integer d', construct
P Px H. where Px is the set of all possible distributions on X' = R and H. =
{sign
Σ 1 E - 2 }. By Lemma D.2, H² {sign "T x4+1:2d|
| E O(d)) S
H. (d). By Theorem 5.1, we have
inf (' inf (A, (H gx),e) inf N" (A. H (15)
AEAox
AEk
AE
By the lower bound in Theorem B.I, we have inf AEA N (A, H) Lemma D.3 VCdim(Hl' 2 d' 1) (2d
vCdim + By
2
Upper Bound:
Take CNN as defined in Section 3.1 with 2d",r = 2, =
1.
Rd Rx,
Σ o (square activation + average pooling), have Σ ai Dj=1 L ((-1))+++ w + b laı, 02 w1,6E IR
d'
FONN sign
Note that min (hr = 0, vP E P. and the VC dimension of F is 3, by Theorem B.I, we have AEFON
vP E P, w.p. 1 - 6, errp (ERM (x) S e, if = Ω (2 (log 1 + log )))
Convergence guarantee for Gradient Descent: We initialize all the parameters by i.i.d. standard gaussian and train the second layer by gradient descent only, i.e. set the LR of w1 as O. (Note training the second layer only is still orthogonal-equivarian algorithm for FC nets, thus it's valid separation.)
For any convex non- non-increasing surrogate loss of 0-1 loss satisfying ((0) > 1, lim (xx) 0 e.g. logistic loss, we define the loss the weight W as (Ik,r is the kth coordinate of xf)
" Σ'
((W)= Σ I(FoNN (x.))))
(k 1)d +5, of +
a
yi
which is convex in Og and b. Note + 0 with probability 1, which means the data are separable even with fixed first layer, i.e. mina,6 L(W) L(W) "==a"b=ur 0, where a* is the ground truth. Thus with sufficiently small step size, GD converges to 0 loss solution. By the definition of surrogate loss, L(W) < implies for x,, 1( (xx3t) < and thus the training error is O.
D.3 PROOFS OF LEMMAS FOR THEOREM 5.2
Lemma D.4. Define ho sign [x]] [xT.uU xa+1:2d. H = (hr U E O(d), and p(U V) =
Px (ho, hy) Px~N((011a)) [bu (x) + hy (x)). There exists constant C, such that the packing number D(H, D(O(d), > (9) dia
16

---

Published as a conference paper at ICLR 2021
Proof of Lemma D.4. The key idea here is to first lower bound px (U, V) by IIU Vil /vd and apply volume argument in the tangent space of La in (dd). We have
h(h
P (x) # hv (x)]
(x)
x~N(0,12a)
[xxTaU U x.+1:2a) (xIaV x4+1:20) < <0]
x~N(00l2a))
x UV X1:d
E ((a.a
arccos
||x1:a|| ||
U.V Xidd
(16)
2 2
(by Lemma A.1)
||x1=|l*
V22 - 2x 2xTUX UUTV
E
π x
- - -VT)x
* x~SS-1
20 IU Vll /vd (by Lemma A.2)
Below we show it suffices to pack in the 0.4 f.x neighborhood of Ia. Let so(d) be the Lie algebra of (d)),, i.e., {M Rddd M -M We also define the matrix exponential mapping exp A
Rdxd + pdxd, where exp(A) = A 2T + अ.. +.... It holds that exp(so(d) = SO(d) C O(d). The benefit of covering in such neighborhood that allows us translate the problem into the tangent space of Id by the following lemma.
4
Lemma D.5 (Implication of Lemma 4 in (Szarek, 1997)). For any matrix A, B E so(d), satisfying
that ||A|| S 4. |B] < _ we have
0.4 A BlI, s ||ex((A) exp(B))l S ||A BlIF
(17)
Therefore, we have
" D(H, 2 D(O(d), CHlle /Vd,e) 2 D(so(d)
Bee C. 11 /Vd22.5s. (18)
4
Note that sd()) is a d(d-1) dimensional subspace of " by Inverse Santalo's inequality (Lemma 3, (Ma & Wu, 2015)), we have
B Bd) vol(so(d) 132
V ddm(
2 C2
(G)o
where vol(.) is the d(d-1) volume defined in the space of so and ITo(d)) (G) = G-G" 2 projection operator onto the subspace sold). We further have
2 is the
G- G
[||]|a Cavd,
(~ where the last inequality is by Theorem 4.4.5, Vershynin (2018).
2
G~N(0.1,))
17

---

Published as a conference paper at ICLR 2021
Finally, we have
D(so(d) n T Bet C1 11 /Vd,2.5)
10
= =D(so(d) n B |1-11
Cl
vol(so(d) n B
Ci
A(d-1)
vol(so(d) n B
10
(19)
a(d-1)
1(d-1) 2 10ds
C
1(d-1)
D.4 PROOF OF THBOREM 5.3
Theorem 5.3 (Single distribution, multiple functions). There is a problem with single input distribu- tion, p = [Px] H = {N Ia)} {sign Σ | ag E RR, such that for any orthogonal equivariant algorithms AA and E > O.. = (dd /E), while there's s a 2-layer ConvNets architecture, such that (V(EMMNNN P,,,8) 0 dlog log +log
Proof of Theorem 5.3. Lower bound: Note p (N Ia)) H. where H {sign E ama
ai R}. Since (0, La) is invariant under all orthogonal transformations, by Theorem 5.1, inf (A, (0, Ta) H. E0) = inf in NO, Ia) (H O(d)), Furthermore, it can equivariant... A
A
be show that H (d) {sign [E. Byyaz Biy R). the sign functions of all quadratics in Rd
Thus it suffices to show learning quadratic functions on Gaussian distribution needs ((d /s) samples for any algorithm (see Lemma D.6, where we assume the dimension can be divided by 4).
Upper bound:Take CNN as defined in Section 3.1 with =d' = 1, 1, x² (square activation no pooling), we have FONN { siig _ a,wpa? + b) la;, wi, b E R
R, o
<iign Ee ax?? + b] Ja,, R
Note that min ( vP P, and the VC dimension of F d 1, by Theorem B. S if S2 (d log )))
he Foun
have VP P. w.p. 1 8, erry ERMM (1x,, (1x,,,1) vi)()))
Convergence guarantee for Gradient Descent: We initialize all the parameters by i.i.d. standard gaussian and train the second layer by gradient descent only, i.e. set the LR of wi as O. (Note training the second layer only is still orthogonal orthogonal-equiivrraat algorithm for FC nets, thus it's valid separation.)
For any convex non- con-increasing surrogate loss of 0-1 loss satisfying ((0) > 1, lim ((x) e.g. logistic loss, we define the loss of the weight W as (#t, is the kth coordinate of x;)
L(W)= Σ
Σ 1=1
wia + b)
1=1
which is convex in a; and b. Note wi # 0 with probability 1, which means the data are separable with fixed first layer, i.e. mina,6 L(W)= L(W) ==== 0, where a' is the ground truth.
18

---

Published as a conference paper at ICLR 2021
Thus with sufficiently small step size, GD converges to 0 loss solution. By the definition of surrogate loss, L(W) < implies for x, (xx,)) < 1 and thus the training error is O.
D.5 PROOF OF LEMMA D.6
[ 0 and ha
Lemma D.6. For A E Raxdd define MA E Rddx2d MA
0 Ia]
Rdd f-1, 13 (x(x) sign 2x
Then for H {hΛ AA E Raxd]
{sign [x Ax|IVA ]ddxdd], satisfies that holds that for any d, algorithm and 0. d2 (A, (N Laa)3 o H.s) = 12( ()(-).
8
Proof of Lemma D.6. Below we will prove (2((2) de lower bound for packing number, i.e. apply Long's
D(H, Px, 25o) DIRddd p, 2εp), where p(U, V) = Px (hy, hv). Then improved version Equation (2) of Benedek-Itai 's lower bound and get a (dd /E) sample complexity lower bound. The reason that we can get the correct rate of that the VCdim(H) exactly equal to the exponent of the packing number. (cf. the proof of Theorem 5.2)
Similar to the proof of Theorem 5.2, the key idea here is to first lower bound p(U, V) by /dd and apply volume argument. Recall for Rdxd, we define MA E 2dxx2d A
I F
as MA 0
and hA Rdd {-1,1} as hx(x) sign [AX Then for Taj
H (ha AA E Raxd] Below we will see it suffices to lower bound the packing num- ber of subset of Raxdd i.. b7 + 0.1 where Bal is the unit spectral norm ball. Clearly
Vx, ||x||2 1, E la + 0.1 0.9 < ||Ux|22 I 1.1.
Thus YU,V La 0. we have,
px (lv,,)))
p
[no (x) + hx(x]]
x~N(0.140)
P x~
[xxT2a x2041:1a) (x x2s+1-1d) < 0]
x TT22 Me M X1:2d
E ((.
arccos
[MMix..0 2 M x x1:2d
1
x x My M X1:2d
E
2 2
(by Lemma A.1)
π
((0,
MD x1.2d|
M / x1.2d
V2
E
IIIM x1.22 112
M X1:2d |1,
Mu x1:2d
1.1m
((0.2a)))
1
VIICMT - MM xx122|12
(1IM x1x]xx22alll2 - || x1:22 1,)2
E
1.1m
E
[](M]] - MrT. |x1:2a
1.1m
[IIMaxiaadl
N(0
Co
E
[[[ MT)xx12dll (by Lemma D.7)
1.1
N1.22~
201
||My MM /Va (by Lemma A.2)
-C IU -Vll
(20)
19

---

Published as a conference paper at ICLR 2021
It remains to lower bound the packing number. We have
M(011B C1 11-ll1//
/Vd,E)
vol(
0.1C d²
vol(B
x
dds
(21)
&
for some constant C. The proof is completed by plugging the above bound and VCdim(H) = d into Equation (2).
Lemma D.7. Suppose x, x ~ [(,, Ta), then VR, S E Raxdd we have
E [|[ - 5)x - E
|
l1yll
VISSx| + 11x 2 Co - (22)
x.y
for some constants Co independent of R, S and d.
Proof of Lemma D.7. Note that
V /|1xx112 + 11y112
V/15x112 + 11yl12
||x|| + ||Sx112
= -11/xx112 ||Sx||al
||xx| 112 |1 2 + /ISSxI + 11x112
|| 22 + ||5x|12
< |IR - 5)x(12
||xxx] 2 + 11 + vISxx| 2 + +1y112
Let F(x, d) be the edf of chi-square distribution, i.e. F(x, d) = Px | s=] Let = 3. we have F(2d, d) (20/-2)0/2 < (ze1-z)1/2, Thus Py |iv12 d/2
1, which implies for any
||x||| S 10vd.
VIncx 112 + 11x112 v |Sxx|]
E y
11y11
| 1|
+ ||5x||1
< [|(R -S)x(12
Rx 2 + ||y 12
V
_/2
1
<(1 o1) |[ 5)x(112
for some 0 < on.
Therefore, have
E (I - 5)x|21 -
V || + 11y12
VISSx + 1
x.y
2 E [I(R - S)x(2 1l ||I||| < 10va]
V [1112x| 2 + +1y11 VIISx| + 1
[ [ovo]
E
x
2a
E
[1(22 5)x(12 2 1
| s lbvor
20

---

Published as a conference paper at ICLR 2021
20102 B [|[(RR 5)x(12),
for some constant 02 > 0. Here use the other side of the tail bound of cdf of chi-square, i.e. for 2 > 1, 1-1-- - F(zd, d) < (ze" =2y/2 < (ze" (ze!=a)1/2.
D.6 PROOFS OF THEOREM 5.4
2 + (tr[M))²
Lemma D.8. Let M E Rdxd, we have
E x0,1(0,1)
[(xT Mx) =
M+M 2
Proof of Lemma D.8.
E
[xx T |x)²
(0,1))
E (0,(0
y
2
(MG + Myi M3)
E
[n-]
+
+
M3
E
[204]
(1-N10.1)
(0,1
Σ(MB) + My + MaMM)) +3 Σ M3
*
M + M
+ (tr[M]])
Theorem 5.4 (Single distribution, multiple functions, ly regression). There is problem with single input distribution, p {Px} H = {N(0,, la)} o {Ei= a,x? a, E R}. such that for any orthogonal equivariant algorithms and æ 0, (A,, d(d+3) (1 E) while there's
2-layer ConvNet architecture, such that > (ERMcNN, P,E) S d for any >> 0.
Proof Theorem 5.4. Lower bound: Similar to the proof of Theorem 5.3, suffices to for any algorithm A. A. (A, Ho (d))))) > A(d+3)) (1-s)-1, Note that HoO = [Ei Buya, Big E R} is the set of all quadratic functions. For convenience denote (x)) x Mx, VM E Rdxd Now we claim quadratic functions such that any learning algorithm A taking at most samples must loss if the ground truth quadratic function is sampled from i..d. gaussian. Morcover, the loss is at most d(d+3) for the trivial algorithm always predicting 0. In other words, if the expected sed
2
suffer d(d+ 1)
relative error
must have the expected sample complexity (A,,, n. That d(d43) E)
A -A,,A,
(1). Upper bound for E [s]]. By Lemma D.8,
M + M
+ (1r[M]33 = d+++ d(d - 1)
d(d + d(d+3) 2
E
E
E (
(0. xx (x= Mx
2
(2). Lower bound for expected loss.
The infimum of the test loss over all possible algorithms A is
inf (=) [(x.x))
[er(A((X), (1)
21

---

Published as a conference paper at ICLR 2021
=inf A (o,(00,
E
E (x.N)))xxhxx
E Pxoha
([
-y)
=inf
E
E
E
(M))) -
M=N(0.11a))
LximPx
LX
E
[tead (xx {xi, xxx,M
Var
Xx M~N(0,,12))
E Xx M~N(0,,,a)
(er(ee (xi)
where the inequality is achieved when [A( yo (x()) IE [hm (x)
{x,, W.
Thus suffices to lower bound VarM [has (x)
{h (x,) 1/ for fixed {x, ) and For conve- nience we define S {AA Rddd A A be the linear space of all d x d symmetric matrices, where the inner product (A, B) := tr BJ and II, Rddd + gddd as the projection operator for the orthogonal complement of the n-dimensional space spanned by x,x; in St. By definition, can expand
xx
axxix + +xx(xx))
Thus even conditioned on {xi, 11
and x,
hx(()) tr(xxx]] Σ xx,t(xx M] + tr tx[,,, M..])
still follows a gaussian distribution, (O,,, [xx T) }(²))
Note we can always find symmetric matrices E, with || E 1 and tr(E.T Eş] = such that
Th (A) E F A), where the rank of TT, is at least d(d+1) 2
n. Thus we have
IT, (xx |112
E
E
Estr E xx
17
k
|| E xx -112²]
E [xx T E, x (byLemma D.8)
|E5l1 2 k
d(d 1)
2
Thus the infimum of the expected test loss is
inf
E
A (0,
22

---

Published as a conference paper at ICLR 2021
E Px (0.To)
Var (Mxr(()) I (har M
E [ })1[]]
xx (=
d(d + 1)
n2
Upper bound: We use the same CNN construction as in the proof of Theorem 5.3, i.e., the function
class is FONN = {Ei "E==a,wf=? bla, w1, b RR {Ei= az²7 + bla,, E R } Thus given + samples, w.p. 1, (x7. .2..... z². 1) will be linear independent, which means ERMcNN could recover the ground truth and thus have loss.
D.7 PROOF OF THEOREM 5.5
Theorem 5.5. Let t; e; + e;+1 and 8; - e; e,+2" and P be the uniform distribution on {(s;, 1)1a= -1)] which is the classification problem for local textures in a 1-dimensional image with d pixels. Then for any permutation equivariant algorithm A, M(A, 1 })) >
(A, P, 4) 2 TO. Meanwhile, <<(ERMeNN. P,O, 6) S logg 3 + 2, where ERMoNN stands for ERMcNN for function class of 2-layer ConvNets.
Proof Theorem 5.5. Lower Bound: We further define permutation 9: 9x(x) (C++1 c,42) (ci+1 C:42)x for i E [d]. Clearly, gi(tt) = S; (s;) = t, For i. E {1,2..... d). we define d(i,g) min - j) mod d, (j i) mod d}. It can be verified that if d(i.j) 3, then
(((s)) Sj, (t,) = tg. For x = S, or t; x = or tj. we define d(x,x')= = d(i,j).
Given X Yu. we define B = xd(x,
3, Vk: E [n]] and we have P [B]
Px [d(x, x+) 2 3, vk [n]] 2 d- 2/b Therefore, we have errp errp(A(X.... (A(X,,
yn)) P (x) # I [A(X.: F B]P
x.9.A
X.y.AA
2.
P
#y yylB B]
2 A
P (((s.)).(ss)) * 11 B]
IP A
# |
A
(3.2) 1
P
* B
+
P ..d
(x)
vt,( + 11 B]
4 1.A
P [A(x.. #1 B A.A
P A
[A(X.. vn) # -1 B
d Thus for any permutation equivariant algorithm A (A, (P): 2) T0
Upper Bound: Take CNN as defined in Section 3.1 with d' = d 1, = 2, Rdd -+ R.
d (x) = E/ x. we have FONN = sign a1 1 (Wir, + 122;-1)² + -bla1, w1, w2 E R }
Note that vh E FONN. V1 <is d, h(ss) = a₁ (2w) +2w3) +b, +b, h(t,) = a1 (wf
+ + (w1 +w2) ) +b.
thus the probability of ERM Fow not achieving 0 error is at most the probability that all data in the training dataset are t, or s; (note the training error of ERM is 0)
P [x E (s Wi [m]]
[M] +P [x, E (1,1s Vi E [m]] = 2 x 2 = 22 -+1
For vector E Rd define x; [( 1) mod d+
23

---

Published as a conference paper at ICLR 2021
Convergence guarantee for Gradient Descent: We initialize all the parameters by iid. standard gaussian and train the second layer by gradient descent only, i.c. set the LR of W1, W2 as O. (Note training the second layer only is still permutation-cquivaniiii algorithm for FC nets, thus it's valid separation.)
For any convex non-increasing surrogate loss of 0-1 loss satisfying ((0) 2 1, limmim ((x) 0 e.g. logistic loss, we define the loss the weight W as
((W)= Σ [[FoNN (WF (x:)u))
==1
-Ns 1 (ar (2wî 2w02) + b) N, x xx (wf + w (wi + w2) b).
Note W1 W2 7 O with probability 1, which means the data are separable even with fixed first layer, i.e. infa,. b L(W) 0. Further note L(W) is convex in a1 and b. which implies with sufficiently small step size, GD converges to loss solution. By the definition of surrogate loss, L (W) < 1 implies for X;, (x.y)) and thus the training error is O.
24


Reviews:
[{"review_id": "uFCqE-aXBOy", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies simple distributional settings in which convolutional neural networks give a provable sample complexity advantage over fully connected networks. This perspective is a valuable complement to prior work in statistical learning theory that often focuses on distribution-free results, which make it harder to study interactions between the training distribution and learning algorithm.\n\nOverall I find this research direction very interesting and the paper is a good contribution. My two main concerns are the following:\n\n- It is unclear how the proposed theory relates to real data distributions. Concretely:\n  * The authors conduct two experiments, one of them with real examples (CIFAR-10 images) and synthetic labels (Figure 1). Did the authors explore a range of architectures and optimization hyperparameters for the fully-connected networks in Figure 1? Performance of neural networks can vary a lot under hyperparameter changes, so the separation would be more convincing if the authors performed a search through a space of hyperparameters.\n  * In addition, it would be interesting if the authors related their theory to properties of real datasets (without synthetic labels).\n  * The theoretical results (upper bounds) study the case where only the last layer of a neural network is trained. Is this also the case in Figure 1?\n\n- The presentation of the theoretical results could be improved. Concretely:\n  * The first eight pages contain about one page of definitions. While it is certainly important to be technically precise, some of the definitions could be moved to the appendix so that there is more space for conveying the core ideas in the main text (e.g., the next point).\n  * The upper bounds for gradient descent on CNNs are for the convex case where only the second layer is trained. It would be good to state this in the main text so that the reader understands the flavor of the results more easily.\n  * Some parts of the proofs in the appendix are only sketched or omitted, e.g., Lemma C.4 or the convergence guarantee for gradient descent in Theorem 4.1\n\n\nGiven these limitations, I am currently hesitant about accepting the paper even though I find the overall research questions very interesting. Addressing the points above could substantially improve the paper.\n\n\nAdditional comments:\n\n- Page 21: the step from the second to last line to the last line is unclear to me. We have conditioned on the event B, which presumably means d(x, x_i) >= 3  (the event B is not clearly defined?). Hence we should have tau_i(s_i) = s_i, but the last line replaces tau_i(s_i) with t_i?\n\n- Definition 3.3 contains \"n \\in ?\" - what does this symbol stand for?\n\n- Page 5: typo \"bewteen\"\n\n- Theorem 4.2: typo \"samples from a fixed ,\"\n\n- The appendix contains many proofs without restating the theorems from the main text, which makes it hard to read the paper thoroughly. The thm-restate package is helpful for this, see https://tex.stackexchange.com/questions/51286/recalling-a-theorem\n\n--------------------------------------------------------------------------------------------\n\nThank you for addressing my comments, I have updated my score accordingly.", "extra_scores": {}, "extra_text": {}}, {"review_id": "s0DleVmXn16", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proves that, for the learning problem where the input distribution is standard Gaussian, and the ground-truth label is given by the difference between the sum of squares of the first half coordinates and second half coordinates, any orthogonal-equivariant algorithm (e.g., a fully-connected network with SGD) needs \\Omega(d^2) samples to achieve a constant test error with a constant probability, while there exists a ConvNet which only needs O(1) samples. Similar results on l_2 regression and adaptive training algorithms are also given. \n\nI think this paper attacks the important problem of sample efficiency of ConvNets. The notion of equivariance between algorithms, including orthogonal and permutation equivariance, is clean and inspiring: it can help us understand and improve various algorithms and architectures, and may also be extended to other settings. Various proof ideas are also interesting, such as Theorem 5.1, the use of Benedek-Itai's lower bound, etc. The writing is clean in my opinion. \n\nHere is one question that is interesting to me: Suppose we insert a Gaussian-initialized fully-connected layer before a ConvNet, i.e., let the fully-connected layer be the first layer, followed by the original ConvNet. Now I think SGD on this new architecture becomes orthogonal equivariant, even if we don't train the first fully-connected layer. Does generalization deteriorate in this setting?\n\nOn the weakness of the paper, here are my thoughts:\n1. For the proofs to work, it seems that the feature distribution needs to be rotational invariant. Can we relax this condition? On the other hand, it is mentioned that the target function is still easier for ConvNets to learn on CIFAR inputs, which partly answers this question.\n2. The ConvNet used to learn the target function (given on page 15) is special: it is a nearly-minimal function class that can represent the target function. What if we use ReLU activation, max-pooling, etc.?\n\nHere are some minor comments:\n1. In the last inequality of Definition 3.3, the middle N^* should be N.\n2. In the definition of ConvNets, the subscript d'(r-1)+1:d'r should be d'(i-1)+1:d'i.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YW-4Dp1f2E1", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies an interesting theoretical question: are there any natural tasks that provably separate fc-nets from convnets. The main contribution of this paper is an Omega(d^2) vs O(1) separation. \n\nTo prove the hardness result, the authors use (and generalize) the notion of orthogonal-equivariance introduced by Ng (2004). The current submission improves the hardness results of Ng (2004) in the following aspects:\n\n1. Ng (2004) proved an Omega(d) vs O(1) separation, while this paper provides an Omega(d^2) vs O(1) separation. This is interesting not only from a theoretical perspective, but could also be relevant to practice. In practice, the dimensionality d is always moderately large. Moreover, the labeling function employed in the hard case is natural and could indeed capture practical scenarios. \n2. The hardness result by Ng (2004) does not use a fixed hard distribution, while this paper shows that there exists a universal (and in fact, natural and simple) hard distribution that is hard for any orthogonal-equivariant algorithm. Personally I find such an improvement important: in order to demonstrate the intrinsic superiority of convnets over fc-nets, it is crucial to obtain distributions that are hard for all training algorithms. \n3. The authors generalize the notion of orthogonal-equivariance and propose permutation-invariance, which allows them to prove hardness results for a wider class of algorithms. In particular, separation between fc-nets and convnets trained by Adam, which is a corollary of the hardness result in this paper, is not implied by previous results. Generalizing hardness results to a larger class of algorithms is definitely interesting for a broad class of audience in the deep learning community. \n\nThe lower bound is proved by using Benedek-Itai’s approach and carefully bounding certain covering numbers. \n\nOverall, this paper presents a set of interesting results which rigorously explain why covnets could be more sample-efficient than fc-nets. This paper is generally well-written and provides lots of intuition on why the hardness results hold. On the other hand, there are a few typos that need to be fixed (see below). Given the great importance of the topic and results in this paper, I would recommend acceptance. \n\n\nMinor Comments:\n\nFor random variable X and Y => random variables\n\nfor function class F,G => function classes. also missing space before G\n\nsemi-definite positive matrix => positive semi-definite matrix\n\nConvNets(CNN): missing space\n\n( which may depend on S) : extra space\n\nmodels below , FC-NN: extra space\n\nBut as noted in the introduction: remove but\n\nnamely, the standard Gaussian, => the standard Gaussian distribution", "extra_scores": {}, "extra_text": {}}, {"review_id": "8pUheFzp8Q", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents an interesting analysis of MLP and convnets, where they show a gap between the number of required training examples to generalize well. They show that due to orthogonality invariance in MLP training, then more examples are required compare to convnet, where one example is needed. This approach, which relies on an older result, provides an intuition as to the success of resnet.\n\nWhile the work is interesting I have one main concern:\nIs the distribution analyzed related to real problems? I think making such a relationship is important as at the moment I don't see any connection between the models analyzed and the structure of real data. \nThe reason this question is important is that in a similar way to the analysis performed, one may find a data distribution that cannot be learned with convnet but can be applied with MLP. Then convnet will get very bad error, while MLP will be able to generalize. So, it is important to explain why the distribution used in the analysis is related to realistic data. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyzes the sample complexity of convolutional architectures, proving a gap between it and that of fully connected (fc) networks. The approach builds on certain invariances of fc nets. The reviewers appreciated the technical content and its contribution to understanding the relative advantages of different architecture, as well as the role of invariance. 
Decision: Accept (Oral)