Year: 2021

Abstract:
Convolutional neural networks often dominate fully-connected counterparts in 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 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 R × {±1} on which any orthogonal-invariant algorithm (i.e. fully-connected networks trained with most gradient-based methods from gaussian initialization) requires Ω(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 to an O(1) vs Ω(d/ε) gap. The proof relies on the fact that SGD on fully-connected network is orthogonal equivariant. Similar results are achieved for `2 regression and adaptive training algorithms, e.g. Adam and AdaGrad, which are only permutation equivariant.

heading: 1 INTRODUCTION
text: 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 a better match to the underlying structure of image data, and thus are able to achieve low training loss with far fewer parameters (ii) models with fewer 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 to make it rigorous would be to show explicit learning tasks that require far more training samples on FC nets than for ConvNets. (Here “task”means, as usual in learning theory, a distribution on data points, and binary labels for them generated given using a 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 or ConvNet). How then can 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 Ω(d2) factor more training samples for FC nets than for ConvNets, where d is the data dimension. (In fact this is shown even for 1-dimensional ConvNets; the lowerbound easily extends to 2-D ConvNets.) The lower bound holds for FC nets trained with any of the popular algorithms
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, `2 regularization, and various learning rate schedules.) Our proof relies on the fact that these popular algorithms lead to an orthogonalequivariance 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 `1 regularization versus other learners. For a variety of learners (including kernels and FC nets) that paper described explicit tasks where the learner has Ω(d) higher sample complexity than logistic regression with `1 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 Ω(d2) vs O(1), and not Ω(d) vs O(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 a 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 LR schedules, `2 regularizer and momentum. Thus Ng (2004)’s 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 easy 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 is the sign of ∑d/2 i=1 x 2 i − ∑d i=d/2+1 x 2 i . Figure 1 shows that this task is 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-equivariance property holds for many types of practical training algorithms, but not all. Notable exceptions are adaptive gradient methods (e.g. Adam and AdaGrad), `1 regularizer, and initialization methods that are not spherically symmetric. To prove a lower bound against FC nets with these algorithms, we identify a property, permutationinvariance, which is satisfied by nets trained using such algorithms. We then demonstrate a single
and natural task on Rd × {±1} that resembles real-life image texture classification, on which we prove any permutation-invariant learning algorithm requires Ω(d) training examples to generalize, while Empirical Risk Minimization with O(1) examples can learn a convolutional net.
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 an 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.

heading: 2 RELATED WORKS
text: Du et al. (2018) attempted to investigate the reason why convolutional nets are more sample efficient. Specifically they prove O(1) samples suffice for learning a 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 distribution-specific 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 a single task on which they proved a sample complexity separation between learning with neural networks vs. with neural tangent kernels. Notably the lower bound is specific to neural tangent kernels (Jacot et al., 2018). Relatedly, Allen-Zhu & Li (2019) showed a sample complexity lower bound against all kernels for a family of tasks, i.e., learning k-XOR on the hypercube.

heading: 3 NOTATION AND PRELIMINARIES
text: We will use X = Rd, Y = {−1, 1} to denote the domain of the data and label and H = {h | h : X → Y} to denote the hypothesis class. Formally, given a joint distribution P , the error of a hypothesis h ∈ H is defined as errP (h) := Px,y∼P [h(x) 6= y]. If h is a random hypothesis, we define errP (h) := Px,y∼P,h [h(x) 6= y] for convenience. A class of joint distributions supported on X × Y is referred as a problem, P . We use ‖·‖2 to denote the spectrum norm and ‖·‖F to 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 O(d) and GL(d) to denote the d-dimensional orthogonal group and general linear group respectively. We use Bd 2
p to denote the unit Schatten-p norm ball in Rd×d.
We useN(µ,Σ) 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 d= 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 × Y . Given an input distribution PX and a hypothesis h, we define PX h as the joint distribution on X × Y , such that (PX h)(S) = P ({x|(x, h(x)) ∈ S}), ∀S ⊂ X × Y . In other words, to sample (X,Y ) ∼ PX 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 H = {PX h | PX ∈ PX , h ∈ H}. In this work all joint distribution P can be written as PX h for some h, i.e. PY|X is deterministic.
For set S ⊂ X and 1-1 map g : X → X , we define g(S) = {g(x)|x ∈ S}. We use ◦ to denote function composition. (f ◦ g)(x) is defined as f(g(x)), and for function classes F , G, F ◦ G = {f ◦ g | f ∈ F , g ∈ G}. For any distribution PX supported on X , we define PX ◦ g as the distribution such that (PX ◦ g)(S) = PX (g(S)). In other words, if X ∼ PX ⇐⇒ g−1(X) ∼ PX ◦ g, because
∀S ⊆ X , P X∼PX
[ g−1(X) ∈ S ] = P X∼PX [X ∈ g(S)] = [PX ◦ g](S).
Algorithm 1 Iterative algorithm A Require: Initial parameter distribution Pinit supported in W = Rm, total iterations T , training
dataset {xi, yi}ni=1, parametric modelM :W → H, iterative update rule F (W,M, {xi, yi} n i=1)
Ensure: Hypothesis h : X → Y . Sample W(0) ∼ Pinit. for t = 0 to T − 1 do W(t+1) = F (W(t),M, {xi, yi}ni=1).
return h = sign [ M[W(T )] ] .
For any joint distribution P of form P = PX h, we define P ◦ g = (PX ◦ g) (h ◦ g). In other words, (X,Y ) ∼ P ⇐⇒ (g−1(X), Y ) ∼ P ◦ g. For any distribution class P and group G acting on X , we define P ◦ G as {P ◦ g | P ∈ P, g ∈ G}. Definition 3.1. A deterministic supervised Learning Algorithm A is a mapping from a sequence of training data, {(xi, yi)}ni=1 ∈ (X × Y)n, to a hypothesis A({(xi, yi)}ni=1) ∈ H ⊆ YX . The algorithmA could also be randomized, in which case the outputA({(xi, yi)}ni=1) is a distribution on hypotheses. Two randomized algorithms A and A′ are the same if for any input, their outputs have the same distribution in function space, which is denoted by A({xi, yi}ni=1) d = A′({xi, yi}ni=1). Definition 3.2 (Equivariant Algorithms). A learning algorithm is equivariant under group GX (or GX -equivariant) if and only if for any dataset {xi, yi}ni=1 ∈ (X × Y)n and ∀g ∈ GX ,x ∈ X , A({g(xi), yi}ni=1) ◦ g = A({xi, yi} n i=1), or A({g(xi), yi} n i=1)(g(x)) = [A({xi, yi} n i=1)](x). 1 Definition 3.3 (Sample Complexity). Given a problem P and a randomized learning algorithm A, δ, ε ∈ [0, 1], we define the (ε, δ)-sample complexity, denoted N (A,P, ε, δ), as the smallest number n ∈ N such that ∀P ∈ P , w.p. 1− δ over the randomness of {xi, yi}ni=1, errP (A({xi, yi} n i=1)) ≤ ε. We also define the ε-expected sample complexity for a problem P , denoted N ∗(A,P, ε), as the smallest number n ∈ N such that ∀P ∈ P , E
(xi,yi)∼P [errP (A({xi, yi}ni=1))] ≤ ε. By definition, we
have N ∗(A,P, ε+ δ) ≤ N (A,P, ε, δ) ≤ N ∗(A,P, εδ), ∀ε, δ ∈ [0, 1].

heading: 3.1 PARAMETRIC MODELS AND ITERATIVE ALGORITHMS
text: A parametric model M : W → H is a functional mapping from weight W to a hypothesis M(·) : X → Y . Given a specific parametric modelM, 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 a function FC-NN[·] : Rd → R, where Wi ∈ Rdi−1×di , d0 = d, and dL = 1:
FC-NN[W](x) = WLσ(WL−1 · · ·σ(W2σ(W1x))). Here, σ : R→ R can be any function, and we abuse the notation such that σ is also defined for vector inputs, in the sense that [σ(x)]i = σ(xi).
ConvNets (CNN): In this paper we 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) ∈ Rk × Rr × R is a function CNN[·] : Rd → R:
CNN[W](x) = r∑ i=1 arσ([w ∗ x]d′(i−1)+1:d′i) + b,
where ∗ : Rk×Rd → Rd is the convolution operator, defined as [w∗x]i = ∑k j=1 wjx[i−j−1 mod d]+1, and σ : Rd′ → R is the composition of pooling and element-wise non-linearity.

heading: 3.2 EQUIVARIANCE AND TRAINING ALGORITHMS
text: 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, or more generally,
1For randomized algorithms, the condition becomes A({g(xi), yi}ni=1) ◦ g d = A({xi, yi}ni=1), which is
stronger than A({g(xi), yi}ni=1)(g(x)) d = [A({xi, yi}ni=1)](x), ∀x ∈ X .
the parametrized model, exhibits certain symmetry per step, i.e., property 2 in Theorem C.1, then by induction it will hold till the last iteration.
Taking linear regression as an example, let xi ∈ Rd, i ∈ [n] be the data and y ∈ Rn be the labels, the GD update for L(w) = 12 ∑n i=1(x > i w − yi)2 = 12 ∥∥X>w − y∥∥2 2
would be wt+1 = F (wt,X,y) := wt−ηX(X>wt−y). Now suppose there’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′0 = Uw0, for some orthogonal matrix U . Not surprisingly, he would get the same solution for GD, just in a different basis. Mathematically, this is because w′t = Uwt =⇒ w′t+1 = F (w ′ t, UX,y) = UF (wt,X,y) = Uwt+1. In other words, he would make the same prediction for unseen data. Thus if the initial distribution of w0 is the same under all basis (i.e., under rotations), e.g., gaussian N(0, Id), then w0 d = Uw0 =⇒ F t(w0, UX,y) = UF t(w0,X,y), for any iteration t, which means GD for linear regression is orthogonal invariant.
To show orthogonal equivariance for gradient descent on general deep FC nets, it suffices to apply the above argument on 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.

heading: 4 WARM-UP EXAMPLES AND PROOF OVERVIEW
text: 4.1 EXAMPLE 1: Ω(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 a task on Rd × {±1} which is a uniform distribution on the set {(eiy, y)|i ∈ {1, 2, . . . , d}, y = ±1}, denoted by P . Each sample from P 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 of n labeled points S := {(xi, yi)}ni=1, the algorithm is asked to make a prediction on an unseen test data x, i.e., A(S)(x). Here we are concerned with orthogonal equivariant algorithms ——the prediction of the algorithm on the test point remains the same even if we rotate every xi and the test point x by any orthogonal matrix R, i.e.,
A({(Rxi, yi)}ni=1)(Rx) d = A({(xi, yi)}ni=1)(x)
Now we show this algorithm fails to generalize on task P , if it observes only d/2 training examples. The main idea here is that, for a fixed training set S, the predictionA({(xi, yi)}ni=1)(x) is determined solely by the inner products between x and xi’s due to orthogonal equivariance, i.e., there exists a random function f (which may depend on S) such that2
A({(xi, yi)}ni=1)(x) d = f(x>x1, . . . ,x >xn)
But the input distribution for this task is supported on 1-hot vectors. Suppose n < d/2. Then at test time the probability is at least 1/2 that the new data point (x, y) ∼ P , is such that x has zero inner product with all n points seen in the training set S. This fact alone fixes the prediction of A to the value f(0, . . . , 0) whereas y is independently and randomly chosen to be ±1. We conclude that A outputs the wrong answer with probability at least 1/4.
2this can be made formal using the fact that Gram matrix determine a set of vectors up to an orthogonal transformation.
4.2 EXAMPLE 2: Ω(d2) 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 to do learning on a certain task, it is actually being forced to simultaneously learn all orthogonal transformations of this task. Intuitively, this should make the learning much more sample-hungry compared to even Simple SGD on ConvNets, which is not orthogonal equivariant. Now we sketch why the obvious way to make this intuition precise using VC dimension (Theorem B.1) does not give a proper separation between ConvNets and FC nets, as mentioned in the Introduction.
We first fix the ground truth labeling function h∗ = sign [∑d
i=1 x 2 i − ∑2d i=d+1 x 2 i ] . Algorithm
A is orthogonal equivariant (Definition 3.2) means that for any task P = PX h∗, where PX is the input distribution and h∗ is the labeling function, A must have the same performance on P and its rotated version P ◦ U = (PX ◦ U) (h∗ ◦ 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∗ ◦ O(d) := {h(x) = h∗(U(x)) | U ∈ O(d)} on all distributions. (See formal statement in Theorem 5.1) By the standard lower bounds with VC dimension (See Theorem B.1), it takes at least Ω( VCdim(H◦O(d))ε ) samples for A to guarantee 1 − ε accuracy. Thus it suffices to show the VC dimension VCdim(H ◦ O(d)) = Ω(d2), towards a Ω(d2) sample complexity lower bound. (Ng (2004) picks a linear thresholding function as h∗, and thus VCdim(h∗ ◦ O(d)) is only O(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, N (A,P, ε, δ) = Ω((d2 + ln 1δ )/ε), while there’s a 2-layer ConvNet architecture, such that N (ERMCNN,P, ε, δ) = O ( 1 ε ( log 1ε + log 1 δ )) .
As noted in the introduction, this doesn’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 A the existence of a fixed distribution PX ∈ P and some orthogonal matrix UA such that the task (PX ◦ U−1A ) h∗ is hard for it. However, this does not preclude (PX ◦U−1A ) h∗ being easy for some other algorithmA′.

heading: 4.3 PROOF OVERVIEW FOR FIXED DISTRIBUTION LOWER BOUNDS
text: 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 ◦ 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 a 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, ρ, ε) defined below (also see Equation (2)).
For function class H, we use ΠH(n) to denote the growth function of H, i.e. ΠH(n) := sup
x1,...,xn∈X |{(h(x1), h(x2), . . . , h(xn)) | h ∈ H}| . Denote the VC-Dimension ofH by VCdim(H), by Sauer-Shelah Lemma, we know ΠH(n) ≤ ( en VCdim(H) )VCdim(H) for n ≥ VCdim(H).
Let ρ be a metric on H, We define N(H, ρ, ε) as the ε-covering number of H w.r.t. ρ, and D(H, ρ, ε) as the ε-packing number of H w.r.t. ρ. For distribution PX , we use ρX (h, h′) := PX∼PX [h(X) 6= 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 (ε, δ)-learns H with n i.i.d. samples from a fixed distribution PX , it must hold for every
ΠH(n) ≥ (1− δ)D(H, ρX , 2ε) (1) Since ΠH(n) ≤ 2n, we have N (A, PX H, ε, δ) ≥ log2D(H, ρX , 2ε) + log2(1− δ), which is the original bound from Benedek & Itai (1991). Later Long (1995) improved this bound for the regime
n ≥ VCdim(H) using Sauer-Shelah lemma, i.e.,
N (A, PX , ε, δ) ≥ VCdim(H)
e ((1− δ)D(H, ρX , 2ε))
1 VCdim(H) . (2)
Intuition behind Benedek-Itai’s lower bound. We first fix the data distribution as PX . Suppose the 2ε-packing is labeled as {h1, . . . , hD(H,ρX ,2ε)} and ground truth is chosen from this 2ε-packing, (ε, δ)-learns the hypothesisH means the algorithm is able to recover the index of the ground truth w.p. 1− δ. Thus one can think this learning process as a noisy channel which delivers log2D(H, ρX , 2ε) bits of information. Since the data distribution is fixed, unlabeled data is independent of the ground truth, and the only information source is the labels. With some information-theoretic inequalities, we can show the number of labels, or samples (i.e., bits of information) N (A, PX H, ε, δ) ≥ log2D(H, ρX , 2ε)+log2(1−δ). A more closer look yields Equation (2), because when VCdim(H) < ∞, then only log2 ΠH(n) instead of n bits information can be delivered.

heading: 5 LOWER BOUNDS
text: Below we first present a reduction from a 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. IfPX is a set of data distributions that is invariant under group GX , i.e.,PX ◦GX = PX , then the following inequality holds. (Furthermore it becomes an equality when GX is a compact group.)
inf A∈AGX N ∗(A,PX H, ε) ≥ inf A∈A N ∗(A,PX (H ◦ GX ), ε) (3)
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 GX , and thus Theorem 5.1 says that GX -equivariant learning against hypothesis classH is as hard as learning against hypothesisH ◦ GX without equivariance constraint.
5.1 Ω(d2) LOWER BOUND FOR ORTHOGONAL EQUIVARIANCE WITH A FIXED DISTRIBUTION
In this subsection we show Ω(d2) vs O(1) separation on a single task in our main theorem (Theorem 5.2). With the same proof technique, we further show we can get correct dependency on ε for the lower bound, i.e., Ω(d 2
ε ), by considering a slightly larger function class, which can be learnt by ConvNets with O(d) samples. We also generalize this Ω(d2) vs O(d) separation to the case of `2 regression with a different proof technique.
Theorem 5.2. There’s a single task, PX h∗, where h∗ = sign [∑d i=1 x 2 i − ∑2d i=d+1 x 2 i ] and
PX = N(0, I2d) and a constant ε0 > 0, independent of d, such that for any orthogonal equivariant algorithm A, we have
N ∗(A, PX h∗, ε0) = Ω(d2), (4)
while there’s a 2-layer ConvNet, such that N (ERMCNN, PX h∗, ε, δ) = O ( 1 ε ( log 1ε + log 1 δ )) . 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 = N(0, I2d) is invariant under O(2d), by Theorem 5.1, it suffices to show that there’s a constant ε0 > 0 (independent of d), for any algorithm A, it takes Ω(d2) samples to learn the augmented function class h∗ ◦ O(2d) w.r.t. PX = N(0, I2d). Define hU = sign [ x>1:dU xd+1:2d ] , ∀U ∈ Rd×d, and by Lemma D.2, we haveH = {hU | U ∈ O(d)} ⊆ h∗ ◦ O(2d). Thus it suffices to a Ω(d2) sample complexity lower bound for the sub function classH, i.e.,
N ∗(A, N(0, I2d) {sign [ x>1:dU xd+1:2d ] }, ε0) = Ω(d2). (5)
By Benedek&Itai’s lower bound, (Benedek & Itai, 1991) (Equation (1)), we know N (A,P, ε0, δ) ≥ log2 ((1− δ)D(H, ρX , 2ε0)) . (6) By Lemma D.4, there’s some constant C, such that D(H, ρX , ε) ≥ (Cε ) d(d−1) 2 , ∀ε > 0.
The high-level idea for Lemma D.4 is to first show that ρX (hU , hV ) ≥ Ω( ‖U−V ‖F√
d ), and then we
show the packing number of orthogonal matrices in a small neighborhood of Id w.r.t. ‖·‖F√ d
is roughly the same as that in the tangent space of orthogonal manifold at Id, i.e., the set of skew matrices, which is of dimension d(d−1)2 and has packing number ( C ε ) d(d−1) 2 . The advantage of working in the tangent space is that we can apply the standard volume argument.
Setting δ = 12 , we have N ∗(A,P, ε0) ≥ N (A,P, 12 , 2ε0) ≥ d(d−1) 2 log2 C 4ε0 − 1 = Ω(d2).
Indeed, we can improve the above lower bound by applying Equation (2), and get
N (A,P, ε, 1 2 ) ≥ d 2 e
( 1
2
) 1 d2 ( C
ε
) 1 2− 1 2d
= Ω(d2ε− 1 2+ 1 2d ). (7)
Note that the dependency in ε in Equation (7) is ε− 1 2+ 1 2d is not optimal, as opposed to ε−1 in upper bounds and other lower bounds. A possible reason for this might be that Theorem 4.2 (Long’s improved version) is still not tight and it might require a tighter probabilistic upper bound for the growth number ΠH(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 Ω(d 2
ε ) sample complexity for all orthogonal equivariant algorithms.
However, if the hypothesis is of VC dimension O(d), using a similar idea, we can prove a Ω(d2/ε) sample complexity lower bound for equivariant algorithms, and O(d) upper bounds for ConvNets. Theorem 5.3 (Single distribution, multiple functions). There is a problem with single input distribution, P = {PX } H = {N(0, Id)} {sign [∑d i=1 αix 2 i ] | αi ∈ R}, such that for any orthogonal equivariant algorithms A and ε > 0, N ∗(A,P, ε) = Ω(d2/ε), while there’s a 2-layer ConvNets architecture, such that N (ERMCNN,P, ε, δ) = O( d log 1ε+log 1 δ ε ).
Interestingly, we can show an analog of Theorem 5.3 for `2 regression, i.e., the algorithm not only observes the signs but also the values of labels yi. Here we define the `2 loss of function h : Rd → R as `P (h) = E
(x,y)∼P
[ (h(x)− y)2 ] and the sample complexity N ∗(A,P, ε) for `2 loss similarly as
the smallest number n ∈ N such that ∀P ∈ P , E (xi,yi)∼P [`P (A({xi, yi}ni=1))] ≤ ε E (x,y)∼P
[ y2 ] . The
last term E (x,y)∼P
[ y2 ] is added for normalization to avoid the scaling issue and thus any ε > 1 could
be achieved trivially by predicting 0 for all data. Theorem 5.4 (Single distribution, multiple functions, `2 regression). There is a problem with single input distribution, P = {PX } H = {N(0, Id)} { ∑d i=1 αix 2 i | αi ∈ R} , such that for any orthogonal equivariant algorithms A and ε > 0, N ∗(A,P, ε) ≥ d(d+3)2 (1− ε)− 1, while there’s a 2-layer ConvNet architecture, such that N ∗(ERMCNN,P, ε) ≤ d for any ε > 0.
5.2 Ω(d) LOWER BOUND FOR PERMUTATION EQUIVARIANCE
In this subsection we will present Ω(d) lower bound for permutation equivariance via a different proof technique — direct coupling. The high-level idea of direct coupling is to show with constant probability over (Xn,x), we can find a g ∈ GX , such that g(Xn) = Xn, but x and g(x) has different labels, in which case no equivariant algorithm could make the correct prediction. Theorem 5.5. Let ti = ei + ei+1 and si = ei + ei+23 and P be the uniform distribution on {(si, 1)}ni=1∪{(ti,−1)}ni=1, which is the classification problem for local textures in a 1-dimensional image with d pixels. Then for any permutation equivariant algorithm A, N (A,P, 18 , 1 8 ) ≥ N ∗(A,P, 14 ) ≥ d 10 . Meanwhile, N (ERMCNN ,P, 0, δ) ≤ log2 1 δ + 2, where ERMCNN stands for ERMCNN for function class of 2-layer ConvNets. Remark 5.2. The task could be understood as detecting if there are two consecutive white pixels in the black background. For proof simplicity, we take texture of length 2 as an illustrative example. It
3For vector x ∈ Rd, we define xi = x(i−1) mod d+1.
is straightforward to extend the same proof to more sophisticated local pattern detection problem of any constant length and to 2-dimensional images.

heading: 6 CONCLUSION
text: We rigorously justify the common intuition that ConvNets can have better inductive bias than FC nets, by constructing a single natural distribution on which any FC net requires Ω(d2) 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, `1 regularization, etc. The separation becomes Ω(d) vs O(1) in this case.

heading: A SOME BASIC INEQUALITIES
text: Lemma A.1. ∀x ∈ [−1, 1], arccosx√
1− x ≥ √ 2.
Proof. Let x = cos(t), t ∈ [−π, π], we have arccos(x)√
1− x = t√ 1− cos(t) = t√ 2 sin(t/2) ≥ √ 2.
Lemma A.2. ∃C > 0, ∀d ∈ N+,M ∈ Rd×d,
C ‖M‖F / √ d ≤ E
x∼Sd−1 [‖Mx‖2] ≤ ‖M‖F /
√ d. (8)

heading: Proof of Lemma A.2.
text: Upper Bound: By Cauchy-Schwarz inequality, we have
E x∼Sd−1
[‖Mx‖2] ≤ √
E x∼Sd−1
[ ‖Mx‖22 ] = √ tr [ M E
x∼Sd−1 [xx>]M>
] = √ tr[MM>]
d = ‖M‖F√ d .
Lower Bound: Let M = UΣV > be the singular value decomposition of M , where U, V are orthogonal matrices and Σ is diagonal. Since ‖M‖F = ‖Σ‖F , and E
x∼Sd−1 [‖Mx‖2] = E x∼Sd−1 [‖Σx‖2],
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 some constant C, such that
C ‖Σ‖F = C √√√√ d∑ i=1 σ2i ≤ E x∼N(0,Id) √√√√ d∑ i=1 x2iσ 2 i = E x∼N(0,Id) [‖Mx‖]2 .
By Cauchy-Schwarz Inequality, we have E x∼N(0,Id)
[‖x‖2] ≤ √
E x∼N(0,Id)
[ ‖x‖22 ] = √ d. Therefore,
we have C ‖Σ‖F ≤ E
x∼N(0,Id) [‖Mx‖]2
= E x̂∼Sd−1 [‖M x̂‖]2 E x∼N(0,Id) [‖x‖2]
≤ E x̂∼Sd−1
[‖M x̂‖]2 √ d,
(9)
which completes the proof.
Lemma A.1. For any z > 0, we have
Pr x∼N(0,σ) (|x| ≤ z) ≤ 2√ π z σ
Proof.
Pr x∼N(0,σ) (|x| ≤ z) = ∫ z −z 1√ 2π σ exp ( − x 2 2σ2 ) dx ≤ √ 2 π z σ

heading: B UPPERAND LOWER BOUND FOR SAMPLE COMPLEXITY WITH VC DIMENSION
text: Theorem B.1. [Blumer et al. (1989)] If learning algorithm A is consistent and ranged in H, i.e. A({xi, yi}ni=1) ∈ H and A({xi, yi} n i=1)(xi) = yi, ∀i ∈ [n], then for any distribution PX and 0 < ε, δ < 1, we have
N (A, PX H, ε, δ) = O( VCdim(H) ln 1ε + ln 1 δ
ε ). (10)
Meanwhile, there’s a distribution PX supported on any subsets {x0, . . . , xd−1} which can be shattered byH, such that for any 0 < ε, δ < 1 and any algorithm A, it holds
N (A, PX H, ε, δ) = Ω( VCdim(H) + ln 1δ
ε ). (11)

heading: C EQUIVARIANCE IN ALGORITHMS
text: 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 a group acting on X = Rd, the iterative algorithmA is GX -equivariant (as defined in Algorithm 1) if the following conditions are met: (proof in appendix)
1. There’s a group GW acting on W and a group isomorphism τ : GX → GW , such that M[τ(g)(W)](g(x)) = M[W](x), ∀x ∈ X ,W ∈ W, g ∈ G. (One can think g as the rotation U applied on data x in linear regression and τ(U) as the rotation U applied on w.)
2. Update rule F is invariant under any joint group action (g, τ(g)), ∀g ∈ G. In other words, [τ(g)](F (W,M, {xi, yi}ni=1)) = F ([τ(g)](W),M, {g(xi), yi} n i=1).
3. The initialization Pinit is invariant under group GW , i.e. ∀g ∈ GW , Pinit = Pinit ◦ g−1.
Here we want to address that the three conditions in Theorem C.1 are natural and almost necessary. Condition 1 is the minimal expressiveness requirement for modelM to allow equivariance. Condition 3 is required for equivariance at initialization. Condition 2 is necessary for induction.
Proof of Theorem C.1. ∀g ∈ GX , we sample W(0) ∼ Pinit, and W̃(0) = τ(g)(W(0)). By property (3), W̃(0) d= W(0) ∼ Pinit. Let W(t+1) = F ( W(t),M, {xi, yi}ni=1 ) and W̃(t+1) =
F ( W̃(t),M, {g(xi), yi}ni=1 ) for 0 ≤ t ≤ T − 1, we can show W̃(t) = τ(g)W(t)) by induction using property (2). By definition of Algorithm 1, we have
A{xi, yi}ni=1 d =M[W(T )],
and M[W̃(T )] ◦ g d= A({g(xi), yi}ni=1) ◦ g.
By property (1), we have M[W̃(T )](g(x)) = M[τ(g)(W(T )](g(x)) = M[W(T )](x). Therefore, A({xi, yi}ni=1) d = M[W(T )] = M[W̃(T )] ◦ g d= A({g(xi), yi}ni=1) ◦ 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 W(t+1) = Ft({W(s)}ts=1,M, {xi, yi} n i=1), as long as (the distribution of) each Ft is invariant under joint transformations.
Below are two example applications of Theorem C.1. Other results in Table 1 could be achieved in the same way.
For classification tasks, optimization algorithms often work with a differentiable surrogate loss ` : R→ R instead the 0-1 loss, such that `(yh(x)) ≥ 1 [yh(x) ≤ 0], and the total loss for hypothesis h and training, L(M(W); {xi, yi}ni=1) is defined as ∑n i=1 `(yi[M(W)](xi)). It’s also denoted by L(W) when there’s no confusion. Definition C.1 (Gradient Descent for FC nets). We call Algorithm 1 Gradient Descent if M = FC-NN and F = GDL , where GDL(W) = W − η∇L(W) is called the one-step Gradient Descent update and η > 0 is the learning rate.
Algorithm 2 Gradient Descent for FC-NN (FC networks)
Require: Initial parameter distribution Pinit , total iterations T , training dataset {xi, yi}ni=1, loss function ` Ensure: Hypothesis h : X → Y . Sample W(0) ∼ Pinit. for t = 0 to T − 1 do W(t+1) = W(t) − η
n∑ i=1 ∇`(FC-NN(W(t))(xi), yi)
return h = sign [ FC-NN[W(T )] ] .
Corollary C.2. Fully-connected networks trained with (stochastic) gradient descent from i.i.d. 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 is for the first condition.
Lemma C.3. There’s a subgroup GW of O(m), and a group isomorphism τ : GX = O(d)→ GW , such that FC-NN[τ(R)(W)] ◦R = FC-NN[W], ∀W ∈ W, R ∈ GX .
Proof of Lemma C.3. By definition, FC-NN[W](x) could be written FC-NN[W2:L](σ(W1x)), which implies FC-NN[W](x) = FC-NN[W1R−1,W2:L](Rx), ∀R ∈ O(d), and thus we can pick τ(R) = O ∈ O(m), where O(W) = [W1R−1,W2:L], and GW = τ(O(d)).
A notable property of Gradient Descent is that it is invariant under orthogonal re-parametrization. Formally, given loss function L : Rm → R and parameters W ∈ Rm, an orthogonal re-parametrization of the problem is to replace (L,W ) by (L ◦O−1, OW ), where O ∈ Rm×m is an orthogonal matrix. Lemma C.4 (Gradient Descent is invariant under orthogonal re-parametization). For any L,W and orthogonal matrix O ∈ Rm×m, we have OGDL(W ) = GDL◦O−1(OW ).
Proof of Lemma C.4. By definition, it suffices to show that for each i ∈ [n], and every W and W′ = OW,
O∇W`(FC-NN(W)(xi), yi) = ∇W′`(FC-NN(O−1W′)(xi), yi),
which holds by chain rule.
For any R ∈ O(d), and set O = τ(R) by Lemma C.3, [L ◦ O−1](W) =∑n i=1 `(yiFC-NN[O −1(W)](xi)) = ∑n i=1 `(yiFC-NN[W](Rxi)). The second condition in Theorem C.1 is satisfied by plugging above equality into Lemma C.4.
The third condition is also satisfied since the initialization distribution is 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 GL(d)-equivariant, or equivariant under the group of invertible linear transformations.
Here, Netwon’s method means to use NT(W) = W − η(∇2L(W))−1∇L(W) as the update rule and we assume∇2L(W) is invertible. Proof is deferred into Appendix, .
Proof of Corollary C.5. The proof is almost the same as that of Corollary C.2, except the following modifications.
Condition 1: If we replace theO(d),O(m) by GL(d),GL(m) in the statement and proof Lemma C.3, the lemma still holds.
Condition 2:By chain rule, one can verify the update rule Newton’s method is invariant under invertible linear re-parametization, i.e. OGDL(W ) = NTL◦O−1(OW ), for all invertible matrix O.
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 to the case of momentum and Lp regularization. For momentum, we only need to ensure that the following update rule, W(t+1) = GDM(W(t),W(t−1),M, {xi, yi}ni=1) = (1 + γ)W(t) − γW(t−1) − η∇L(W(t)), also satisfies the property in Lemma C.4. For Lp regularization, because ‖W‖p is independent of {xi, yi} n i=1, we only need to ensure ‖W‖p = ‖τ(R)(W)‖p , ∀R ∈ GX , which is easy to check when GX only contains permutation or sign-flip.

heading: C.1 EXAMPLES OF EQUIVARIANCE FOR NON-ITERATIVE ALGORITHMS
text: To demonstrate the wide application of our lower bounds, we give two more examples of algorithmic equivariance where the algorithm is not iterative. The proofs are folklore. Definition C.2. Given a positive semi-definite kernel K, the Kernel Regression algorithm REGK is defined as:
REGK({xi, yi}ni=1)(x) := 1 [ K(x,XN ) ·K(XN ,XN )†y ≥ 0 ] where K(XN ,XN ) ∈ Rn×n, [K(XN ,XN )]i,j = K(xi,xj), y = [y1, y2, . . . , yN ]> and K(x,XN ) = [K(x,x1), . . . ,K(x,xN )].
Kernel Regression: If kernel K is GX -equivariant, i.e., ∀g ∈ GX ,x,y ∈ X , K(g(x), g(y)) = K(x,y), then algorithm REGK is GX -equivariant. ERM: If F = F ◦ GX , and argminh∈F ∑n i=1 1 [h(xi) 6= yi] is unique, then ERMF is GX - equivariant.

heading: D OMITTED PROOFS

heading: D.1 PROOFS OF SAMPLE COMPLEXITY REDUCTION FOR GENERAL EQUIVARIANCE
text: Given GX -equivariant algorithm A, by definition, N ∗(A,P, ε) = N ∗(A,P ◦ g−1, ε),∀g ∈ GX . Consequently, we have N ∗(A,P, ε) = N ∗(A,P ◦ GX , ε). (12) Lemma D.1. Let A be the set of all algorithms and AGX be the set of all GX -equivariant algorithms, the following inequality holds. The equality is attained when GX is a compact group.
inf A∈AGX N ∗(A,P, ε) ≥ inf A∈A N ∗(A,P ◦ GX , ε) (13)
Proof of Lemma D.1. Take infimum over AGX over the both side of Equation 12, and note that AGX ⊂ A, Inequality 13 is immediate. Suppose the group GX is compact and let µ be the Haar measure on it, i.e. ∀S ⊂ GX , g ∈ GX , µ(S) = µ(g◦S). We claim for each algorithmA, the sample complexity of the following equivariant algorithm A′ is no higher than that of A on P GX :
A′({xi, yi}ni=1) = A({g(xi), yi} n i=1) ◦ g, where g ∼ µ.
By the definition of Haar measure, A′ is GX -equivariant. Moreover, for any fixed n ≥ 0, we have inf P∈P E (xi,yi)∼P [errP (A′({xi, yi}ni=1))] = infP∈P Eg∼µ E(xi,yi)∼P◦g−1 [errP (A({xi, yi}ni=1))]
≥ inf P∈P inf g∈GX E (xi,yi)∼P◦g−1 [errP (A({xi, yi}ni=1))] = infP∈P◦GX E(xi,yi)∼P [errP (A({xi, yi}ni=1))] ,
which implies infA∈AGX N ∗(A,P, ε) ≤ infA∈AN ∗(A,P ◦ GX , ε).
Proof of Theorem 5.1. Simply note that (PX H)◦GX = ∪g∈GX (PX ◦g) (H◦g−1) = ∪g∈GXPX (H ◦ g−1) = PX (H ◦ GX ), the theorem is immediate from Lemma D.1.

heading: D.2 PROOF OF THEOREM 4.1
text: Lemma D.2. Define hU = sign [ x>1:dU xd+1:2d ] , ∀U ∈ Rd×d, we haveH = {hU | U ∈ O(d)} ⊆
sign [∑d
i=1 x 2 i − ∑2d i=d+1 x 2 i ] ◦ O(2d).
Proof. Note that
[ 0 U U> 0 ] = [ Id 0 0 U> ] · [ 0 Id Id 0 ] · [ Id 0 0 U ] ,
and
[ 0 Id Id 0 ] = [√ 2 2 Id − √ 2 2 Id√
2 2 Id
√ 2 2 Id
] · [ Id 0 0 −Id ] · [ √ 2 2 Id
√ 2 2 Id
− √ 2 2 Id √ 2 2 Id
] ,
thus for any U ∈ O(d), ∀x ∈ R2d, hU (x) = sign [ x>1:dU xd+1:2d ] = sign [ x> [ 0 U U> 0 ] x ] =sign [ gU (x) > [ Id 0 0 −Id ] gU (x) ] ∈ h∗ ◦ O(2d),
(14)
where gU (x) = [ Id 0 0 U ] · [√ 2 2 Id − √ 2 2 Id√
2 2 Id
√ 2 2 Id
] · x is an orthogonal transformation on R2d.
Lemma D.3. Define hU = sign [ x>1:dU xd+1:2d ] , ∀U ∈ Rd×d, and H = {hU | U ∈ O(d)}, we have
VCdim(H) ≥ d(d− 1) 2 .
Proof. Now we claim H shatters {ei + ed+j}1≤i<j≤d, i.e. O(d) can shatter {eie>j }1≤i<j≤d, or for any sign pattern {σij}1≤i<j≤d, there exists U ∈ O(d), such that sign [〈 U, eie > j 〉] = σij , which implies VCdim(H) ≥ d(d−1)2 .
Let so(d) = {M |M = −M>,M ∈ Rd×d}, we know
exp(u) = Id + u+ u2
2 + · · · ∈ SO(d), ∀u ∈ so(d).
Thus for any sign pattern {σij}1≤i<j≤d, let u = ∑
1≤i<j≤d σij(eie
> j − eje>i ) and λ→ 0+,
sign [〈
exp(λu), eie > j
〉] = sign [ 0 + λσij +O(λ 2) ] = sign [σij +O(λ)] = σij .
Theorem 4.1 (All distributions, single hypothesis). Let P = {all distributions} {h∗}. For any orthogonal equivariant algorithms A, N (A,P, ε, δ) = Ω((d2 + ln 1δ )/ε), while there’s a 2-layer ConvNet architecture, such that N (ERMCNN,P, ε, δ) = O ( 1 ε ( log 1ε + log 1 δ )) .
Proof of Theorem 4.1. Lower bound: Suppose d = 2d′ for some integer d′, we construct P = PX H, where PX is the set of all possible distributions on X = R3k, and H = {sign [∑d′ i=1 x 2 i − ∑2d′ i=d′+1 x 2 i ] }. By Lemma D.2, H′ = {sign [ x>1:dU xd+1:2d ] | U ∈ O(d′)} ⊆ H ◦ O(d). By Theorem 5.1, we have
inf A∈AGX N ∗(A,PX H, ε) ≥ inf A∈A N ∗(A,PX (H ◦ GX ), ε) ≥ inf A∈A N ∗(A,PX H′, ε) (15)
By the lower bound in Theorem B.1, we have infA∈AN ∗(A,PX H′, ε) ≥ VCdim(H′)+ln 1δ
ε . By
Lemma D.3 VCdim(H′) ≥ d ′(d′−1)
2 = Ω(d 2).
Upper Bound: Take CNN as defined in Section 3.1 with d = 2d′, r = 2, k = 1, σ : Rd′ → R, σ(x) = ∑d′ i=1 x 2 i (square activation + average pooling), we have
FCNN = { sign [∑2 i=1 ai ∑d′ j=1 x 2 (i−1)d′+jw 2 1 + b ] |a1, a2, w1, b ∈ R } .
Note that min h∈FCNN errP (h) = 0, ∀P ∈ P , and the VC dimension of F is 3, by Theorem B.1, we have ∀P ∈ P , w.p. 1− δ, errP (ERMFCNN({xi, yi} n i=1)) ≤ ε, if n = Ω ( 1 ε ( log 1ε + log 1 δ ) )) .
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 0. (Note training the second layer only is still a orthogonal-equivariant algorithm for FC nets, thus it’s a valid separation.)
For any convex non-increasing surrogate loss of 0-1 loss l satisfying l(0) ≥ 1, limx→∞ l(x) = 0 e.g. logistic loss, we define the loss of the weight W as (xk,i is the kth coordinate of xi)
L(W) = n∑ i=1 l(FCNN[W](xi)yi) = n∑ i=1 l  2∑ k=1 ai d′∑ j=1 x2(k−1)d′+j,iw 2 1 + b  yi  ,
which is convex in ai and b. Note w1 6= 0 with probability 1, which means the data are separable even with fixed first layer, i.e. mina,b L(W) = L(W) |a=a∗,b=0= 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) < 1 implies for xi, l(xiyi) < 1 and thus the training error is 0.

heading: D.3 PROOFS OF LEMMAS FOR THEOREM 5.2
text: Lemma D.4. Define hU = sign [ x>1:dU xd+1:2d ] , H = {hU | U ∈ O(d)}, and ρ(U, V ) := ρX (hU , hV ) = Px∼N(0,I2d) [hU (x) 6= hV (x)]. There exists a constant C, such that the packing
number D(H, ρX , ε) = D(O(d), ρ, ε) ≥ ( C ε ) d(d−1) 2 .
Proof of Lemma D.4. The key idea here is to first lower bound ρX (U, V ) by ‖U − V ‖F / √ d and apply volume argument in the tangent space of Id in O(d). We have
ρ(hU , hV ) = P x∼N(0,I2d) [hU (x) 6= hV (x)]
= P x∼N(0,I2d)
[( x>1:dU xd+1:2d ) ( x>1:dV xd+1:2d ) < 0 ]
= 1
π E
x1:d∼N(0,Id)
[ arccos ( x>1:dUV >x1:d
‖x1:d‖2
)]
≥ 1 π E x1:d∼N(0,Id)
[√ 2− 2 x>1:dUV >x1:d
‖x1:d‖2
] (by Lemma A.1)
= 1
π E
x∼Sd−1
[√ 2− 2x>UV >x ] = 1
π E
x∼Sd−1
[∥∥(U> − V >)x∥∥ F ] ≥C1 ‖U − V ‖F / √ d (by Lemma A.2)
(16)
Below we show it suffices to pack in the 0.4 `∞ neighborhood of Id. Let so(d) be the Lie algebra of SO(d), i.e., {M ∈ Rd×d | M = −M>}. We also define the matrix exponential mapping exp : Rd×d → Rd×d, where exp(A) = A+ A 2
2! + A3
3! + · · · . It holds that exp(so(d)) = SO(d) ⊆ O(d). The benefit of covering in such neighborhood is that it allows us to translate the problem into the tangent space of Id by the following lemma.
Lemma D.5 (Implication of Lemma 4 in (Szarek, 1997)). For any matrix A,B ∈ so(d), satisfying that ‖A‖∞ ≤ π 4 , ‖B‖∞ ≤ π 4 , we have
0.4 ‖A−B‖F ≤ ‖exp(A)− exp(B)‖F ≤ ‖A−B‖F . (17)
Therefore, we have
D(H, ρX , ε) ≥ D(O(d), C1 ‖·‖F / √ d, ε) ≥ D(so(d) ∩ π
4 Bd
2 ∞ , C1 ‖·‖F / √ d, 2.5ε). (18)
Note that so(d) is a d(d−1)2 -dimensional subspace of R d2 , by Inverse Santalo’s inequality (Lemma 3, (Ma & Wu, 2015)), we have
( vol(so(d) ∩Bd2∞) vol(so(d) ∩Bd22 ) ) 2 d(d−1) ≥ C2 √ dim(so(d))
E G∼N(0,Id2 )
[∥∥Πso(d)(G)∥∥∞] .
where vol(·) is the d(d−1)2 volume defined in the space of so(d) and Πso(d)(G) = G−G>
2 is the projection operator onto the subspace so(d). We further have
E G∼N(0,Id2 ) [∥∥Πso(d)(G)∥∥∞] = E G∼N(0,Id2 ) [∥∥∥∥G−G>2 ∥∥∥∥ ∞ ] ≤ E G∼N(0,Id2 ) [‖G‖∞] ≤ C3 √ d,
where the last inequality is by Theorem 4.4.5, Vershynin (2018).
Finally, we have
D(so(d) ∩ π 4 Bd 2
∞ , C1 ‖·‖F / √ d, 2.5ε)
=D(so(d) ∩Bd 2 ∞ , ‖·‖F , 10 √ dε
C1π )
≥vol(so(d) ∩B d2 ∞) vol(so(d) ∩Bd22 ) × ( C1π 10 √ dε ) d(d−1) 2
≥
C1C2π √ d(d−1) 2
10dε
 d(d−1) 2
:=
( C
ε
) d(d−1) 2
(19)

heading: D.4 PROOF OF THEOREM 5.3
text: Theorem 5.3 (Single distribution, multiple functions). There is a problem with single input distribution, P = {PX } H = {N(0, Id)} {sign [∑d i=1 αix 2 i ] | αi ∈ R}, such that for any orthogonal equivariant algorithms A and ε > 0, N ∗(A,P, ε) = Ω(d2/ε), while there’s a 2-layer ConvNets architecture, such that N (ERMCNN,P, ε, δ) = O( d log 1ε+log 1 δ ε ). Proof of Theorem 5.3. Lower bound: Note P = {N(0, Id)} H, whereH = {sign [∑d i=1 αix 2 i ] | αi ∈ R}. Since N(0, Id) is invariant under all orthogonal transformations, by Theorem 5.1, inf
equivariantA N ∗(A, N(0, Id) ◦ H, ε0) = inf A N ∗(A, N(0, Id) (H ◦ O(d)), ε0). Furthermore, it can be show that H ◦ O(d) = {sign [∑
i,j βijxixj ] | βij ∈ R}, the sign functions of all quadratics in
Rd. Thus it suffices to show learning quadratic functions on Gaussian distribution needs Ω(d2/ε) samples for any algorithm (see Lemma D.6, where we assume the dimension d can be divided by 4).
Upper bound:Take CNN as defined in Section 3.1 with d = d′, r = 1, k = 1, σ : R→ R, σ(x) = x2 (square activation + no pooling), we have FCNN = { sign [∑d i=1 aiw 2 1x 2 i + b ] |ai, w1, b ∈ R } ={
sign [∑d
i=1 aix 2 i + b ] |ai, b ∈ R } .
Note that min h∈FCNN errP (h) = 0, ∀P ∈ P , and the VC dimension of F is d+ 1, by Theorem B.1, we have ∀P ∈ P , w.p. 1− δ, errP (ERMFCNN({xi, yi} n i=1)) ≤ ε, if n = Ω ( 1 ε ( d log 1ε + log 1 δ ) )) .
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 0. (Note training the second layer only is still a orthogonal-equivariant algorithm for FC nets, thus it’s a valid separation.)
For any convex non-increasing surrogate loss of 0-1 loss l satisfying l(0) ≥ 1, limx→∞ l(x) = 0 e.g. logistic loss, we define the loss of the weight W as (xk,i is the kth coordinate of xi)
L(W) = n∑ i=1 l(FCNN[W](xi)yi) = n∑ i=1 l
( (
d∑ k=1 w21aix 2 k,i + b)yi
) ,
which is convex in ai and b. Note w1 6= 0 with probability 1, which means the data are separable even with fixed first layer, i.e. mina,b L(W) = L(W) |a=a∗,b=0= 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) < 1 implies for xi, l(xiyi) < 1 and thus the training error is 0.

heading: D.5 PROOF OF LEMMA D.6
text: Lemma D.6. For A ∈ Rd×d, we define MA ∈ R2d×2d as MA = [ A 0 0 Id ] , and hA :
R4d → {−1, 1} as hA(x) = sign [ x>1:2dMAx2d+1:4d ] . Then for H = {hA | ∀A ∈ Rd×d} ⊆
{sign [ x>Ax]|∀A ∈ R4d×4d ] }, satisfies that it holds that for any d, algorithm A and ε > 0,
N ∗(A, {N(0, I4d)} H, ε) = Ω( d2
ε ).
Proof of Lemma D.6. Below we will prove a Ω( ( 1 ε )d2 ) lower bound for packing number, i.e. D(H, ρX , 2ε0) = D(Rd×d, ρ, 2ε0), where ρ(U, V ) = ρX (hU , hV ). Then we can apply Long’s improved version Equation (2) of Benedek-Itai’s lower bound and get a Ω(d2/ε) sample complexity lower bound. The reason that we can get the correct rate of ε is that the VCdim(H) is 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 ρ(U, V ) by ‖U − V ‖F / √ d and apply volume argument. Recall for A ∈ Rd×d, we define MA ∈ R2d×2d
as MA = [ A 0 0 Id ] , and hA : R4d → {−1, 1} as hA(x) = sign [ x>1:2dMAx2d+1:4d ] . Then for H = {hA | ∀A ∈ Rd×d} . Below we will see it suffices to lower bound the packing number of a subset of Rd×d, i.e. Id + 0.1Bd 2 ∞ , where B d2
∞ is the unit spectral norm ball. Clearly ∀x, ‖x‖2 = 1,∀U ∈ Id + 0.1Bd 2 ∞ , 0.9 ≤ ‖Ux‖2 ≤ 1.1.
Thus ∀U, V ∈ Id + 0.1Bd 2
∞ we have, ρX (hU , hV ) = P
x∼N(0,I4d) [hU (x) 6= hV (x)]
= P x∼N(0,I4d)
[( x>1:2dMU x2d+1:4d ) ( x>1:2dMV x2d+1:4d ) < 0 ]
= 1
π E
x1:2d∼N(0,I2d)
[ arccos ( x>1:2dMUM
> V x1:2d∥∥M>U x1:2d∥∥2 ∥∥M>V x1:2d∥∥2
)]
≥ 1 π E x1:2d∼N(0,I2d)
[√ 2− 2
x>1:2dMUM > V x1:2d∥∥M>U x1:2d∥∥2 ∥∥M>V x1:2d∥∥2
] (by Lemma A.1)
≥ √ 2
1.1π E
x1:2d∼N(0,I2d) [√∥∥M>U x1:2d∥∥2 ∥∥M>V x1:2d∥∥2 − x>1:2dMUM>V x1:2d] = 1
1.1π E
x1:2d∼N(0,I2d) [√∥∥(M>U −M>V )x1:2d∥∥22 − (∥∥M>U x1:2d∥∥2 − ∥∥M>V x1:2d∥∥2)2] ≥ 1
1.1π ( E x1:2d∼N(0,I2d) [∥∥(M>U −M>V )x1:2d∥∥2] − E
x1:2d∼N(0,I2d) [∣∣∥∥M>U x1:2d∥∥2 − ∥∥M>V x1:2d∥∥2∣∣]) ≥ C0
1.1π E
x1:2d∼N(0,I2d) [∥∥(M>U −M>V )x1:2d∥∥2] (by Lemma D.7) ≥C1 ‖MU −MV ‖F / √ d (by Lemma A.2) =C1 ‖U − V ‖F / √ d
(20)
It remains to lower bound the packing number. We have
M(0.1Bd 2 ∞ , C1 ‖·‖F / √ d, ε)
≥vol(B d2 ∞) vol(Bd22 ) × ( 0.1C1√ dε )d2
≥ ( C
ε
)d2 ,
(21)
for some constant C. The proof is completed by plugging the above bound and VCdim(H) = d2 into Equation (2).
Lemma D.7. Suppose x,x ∼ N(0, Id), then ∀R,S ∈ Rd×d, we have
E x [‖(R− S)x‖2]− E x,y [∣∣∣∣√‖Rx‖22 + ‖y‖22 −√‖Sx‖22 + ‖y‖22∣∣∣∣] ≥ C0 Ex [‖(R− S)x‖2] , (22) for some constants C0 independent of R,S and d.
Proof of Lemma D.7. Note that∣∣∣∣√‖Rx‖22 + ‖y‖22 −√‖Sx‖22 + ‖y‖22∣∣∣∣ = |‖Rx‖2 − ‖Sx‖2|
‖Rx‖2 + ‖Sx‖2√ ‖Rx‖22 + ‖y‖ 2 2 + √ ‖Sx‖22 + ‖y‖ 2 2
≤‖(R− S)x‖2 ‖Rx‖2 + ‖Sx‖2√
‖Rx‖22 + ‖y‖ 2 2 + √ ‖Sx‖22 + ‖y‖ 2 2
Let F (x, d) be the cdf of chi-square distribution, i.e. F (x, d) = Px [ ‖x‖22 ≤ x ] . Let z = xd , we
have F (zd, d) ≤ (ze1−z)d/2 ≤ (ze1−z)1/2. Thus Py [ ‖y‖22 ≤ d/2 ] < 1, which implies for any ‖x‖2 ≤ 10 √ d,
E y
[∣∣∣∣√‖Rx‖22 + ‖y‖22 −√‖Sx‖22 + ‖y‖22∣∣∣∣]
≤‖(R− S)x‖2 E y  ‖Rx‖2 + ‖Sx‖2√ ‖Rx‖22 + ‖y‖ 2 2 + √ ‖Sx‖22 + ‖y‖ 2 2  ≤(1− α1) ‖(R− S)x‖2 ,
for some 0 < α1.
Therefore, we have
E x [‖(R− S)x‖2]− E x,y [∣∣∣∣√‖Rx‖22 + ‖y‖22 −√‖Sx‖22 + ‖y‖22∣∣∣∣] ≥E
x
[ ‖(R− S)x‖2 1 [ ‖x‖ ≤ 10 √ d ]]
− E x,y [∣∣∣∣√‖Rx‖22 + ‖y‖22 −√‖Sx‖22 + ‖y‖22∣∣∣∣1 [‖x‖2 ≤ 10√d]] ≥α1 E
x
[ ‖(R− S)x‖2 1 [ ‖x‖2 ≤ 10 √ d ]]
≥α1α2 E x [‖(R− S)x‖2] ,
for some constant α2 > 0. Here we use the other side of the tail bound of cdf of chi-square, i.e. for z > 1, 1− F (zd, d) < (ze1−z)d/2 < (ze1−z)1/2.

heading: D.6 PROOFS OF THEOREM 5.4
text: Lemma D.8. Let M ∈ Rd×d, we have E x∼N(0,Id)
[ (x>Mx)2 ] = ∥∥∥M+M>2 ∥∥∥2
F + (tr[M ])2.

heading: Proof of Lemma D.8.
text: E x∼N(0,Id)
[ (x>Mx)2 ] = E
x∼N(0,Id)  ∑ i,j,i′j′ xixjxi′xj′MijMi′j′  = ∑ i6=j (M2ij +MijMji +MiiMjj) ( E x∼N(0,1) [ x2 ])2 + ∑ i M2ii E x∼N(0,1) [ x4 ]
= ∑ i6=j (M2ij +MijMji +MiiMjj) + 3 ∑ i M2ii
= ∥∥∥∥M +M>2 ∥∥∥∥2 F + (tr[M ])2
Theorem 5.4 (Single distribution, multiple functions, `2 regression). There is a problem with single input distribution, P = {PX } H = {N(0, Id)} { ∑d i=1 αix 2 i | αi ∈ R} , such that for any orthogonal equivariant algorithms A and ε > 0, N ∗(A,P, ε) ≥ d(d+3)2 (1− ε)− 1, while there’s a 2-layer ConvNet architecture, such that N ∗(ERMCNN,P, ε) ≤ d for any ε > 0.
Proof of Theorem 5.4. Lower bound: Similar to the proof of Theorem 5.3, it suffices to for any algorithmA,N ∗(A,H◦O(d), ε) ≥ d(d+3)2 (1−ε)−1. Note thatH◦O(d) = { ∑ i,j βijxixj | βij ∈ R} is the set of all quadratic functions. For convenience we denote hM (x) = x>Mx, ∀M ∈ Rd×d. Now we claim quadratic functions such that any learning algorithm A taking at most n samples must suffer d(d+1)2 −n loss if the ground truth quadratic function is sampled from i.i.d. gaussian. Moreover, the loss is at most d(d+3)2 for the trivial algorithm always predicting 0. In other words, if the expected relative error ε ≤ d(d+1) 2 −n d(d+3)
2
, we must have the expected sample complexity N ∗(A,P, ε) ≥ n. That
is N ∗(A,P, ε) ≥ d(d+3)2 (1− ε)− 1. (1). Upper bound for E [ y2 ] . By Lemma D.8,
E M∼N(0,Id2 ) E x∼PX ,y=x>Mx
[ y2 ]
= E M∼N(0,Id2 ) [∥∥∥∥M +M>2 ∥∥∥∥2 F + (tr[M ])2 ] = d+d+ d(d− 1) 2 = d(d+ 3) 2 .
(2). Lower bound for expected loss.
The infimum of the test loss over all possible algorithms A is
inf A E M∼N(0,Id2 )
[ E
(xi,yi)∼PX hM [`P (A({xi, yi}ni=1))]
]
= inf A E M∼N(0,Id2 )
[ E
(xi,yi)∼PX hM
[ E
x,y∼PX◦hM
[ ([A({xi, yi}ni=1)](x)− y)
2 ]]]
= inf A E M∼N(0,Id2 )
[ E
xi∼PX
[ E
x∼PX
[ ([A({xi, hM (xi)}ni=1)](x)− hM (x))2 ]]] ≥ E
xi,x∼PX M∼N(0,Id2 )
[ Var
x,xi,M [hM (x) | {xi, hM (xi)}ni=1,x]
]
= E xi,x∼PX
M∼N(0,Id2 )
[ Var M [hM (x) | {hM (xi)}ni=1] ] ,
where the inequality is achieved when [A({xi, yi}ni=1)](x) = E M [hM (x) | {xi, yi}ni=1].
Thus it suffices to lower bound VarM [hM (x) | {hM (xi)}ni=1], for fixed {xi}ni=1 and x. For convenience we define Sd = {A ∈ Rd×d | A = A>} be the linear space of all d× d symmetric matrices, where the inner product 〈A,B〉 := tr[A>B] and Πn : Rd×d → Rd×d as the projection operator for the orthogonal complement of the n-dimensional space spanned by xix>i in Sd. By definition, we can expand
xx> = n∑ i=1 αixix > i + Πn(xx >).
Thus even conditioned on {xi, yi}ni=1 and x,
hM (x) = tr[xx >] = n∑ i=1 αitr[xix > i M ] + tr[Πn(xx >)M ],
still follows a gaussian distribution, N(0, ∥∥Πn(xx>)∥∥2F ).
Note we can always find symmetric matrices Ei with ‖Ei‖F = 1 and tr[E>i Ej ] = 0 such that Πn(A) = ∑k i=1Eitr[E > i A], where the rank of Πn, is at least d(d+1) 2 − n. Thus we have
E x [∥∥Πn(xx>)∥∥2F ] =E
x ∥∥∥∥∥ k∑ i=1 Eitr[E > i xx >] ∥∥∥∥∥ 2
F  =
k∑ i=1 E x [∥∥Eitr[E>i xx>]∥∥2F ] =
k∑ i=1 E x [ (x>E>i x) 2 ] (byLemma D.8)
≥ k∑ i=1 ‖Ei‖F2 ≥ k
≥d(d+ 1) 2 − n
Thus the infimum of the expected test loss is
inf A E M∼N(0,Id2 )
[ E
(xi,yi)∼PX hM [`P (A({xi, yi}ni=1))]
]
≥ E xi,x∼PX
M∼N(0,Id2 )
[ Var M [hM (x) | {hM (xi)}ni=1] ] .
= E xi∼PX
M∼N(0,Id2 )
[ E x [∥∥Πn(xx>)∥∥2F ]] . ≥d(d+ 1)
2 − n.
Upper bound: We use the same CNN construction as in the proof of Theorem 5.3, i.e., the function class is FCNN = {∑d i=1 aiw 2 1x 2 i + b|ai, w1, b ∈ R } = {∑d i=1 aix 2 i + b|ai, b ∈ R } . Thus given
d+ 1 samples, w.p. 1, (x21, x 2 2, . . . , x 2 d, 1) will be linear independent, which means ERMCNN could recover the ground truth and thus have 0 loss.

heading: D.7 PROOF OF THEOREM 5.5
text: Theorem 5.5. Let ti = ei + ei+1 and si = ei + ei+24 and P be the uniform distribution on {(si, 1)}ni=1∪{(ti,−1)}ni=1, which is the classification problem for local textures in a 1-dimensional image with d pixels. Then for any permutation equivariant algorithm A, N (A,P, 18 , 1 8 ) ≥ N ∗(A,P, 14 ) ≥ d 10 . Meanwhile, N (ERMCNN ,P, 0, δ) ≤ log2 1 δ + 2, where ERMCNN stands for ERMCNN for function class of 2-layer ConvNets.
Proof of Theorem 5.5. Lower Bound: We further define permutation gi as gi(x) = x − (ei+1 − ei+2)
>(ei+1 − ei+2)x for i ∈ [d]. Clearly, gi(ti) = si, gi(si) = ti. For i, j ∈ {1, 2, . . . , d}, we define d(i, j) = min{(i − j) mod d, (j − i) mod d}. It can be verified that if d(i, j) ≥ 3, then gi(sj) = sj , gi(tj) = tj . For x = si or ti, x′ = sj or tj , we define d(x,x′) = d(i, j).
Given Xn,yn, we define B := {d(x,xk) ≥ 3, ∀k ∈ [n]} and we have P [B] = Px [d(x,xk) ≥ 3, ∀k ∈ [n]] ≥ d− d10∗5 d = 1 2 . Therefore, we have
errP (A(Xn,yn)) = P x,y,A [A(Xn,yn)(x) 6= y] ≥ P x,y,A [A(Xn,yn)(x) 6= y | B]P [B]
≥ 1 2 P x,y,A [A(Xn,yn)(x) 6= y | B]
= 1
4 P i,A
[A(Xn,yn)(si) 6= 1 | B] + 1
4 P i,A [A(Xn,yn)(ti) 6= −1 | B]
(3.2) =
1 4 P i,A [A(gi(Xn),yn)(gi(si)) 6= 1 | B] + 1 4 P i,A [A(Xn,yn)(ti) 6= −1 | B]
= 1
4 P i,A
[A(Xn,yn)(ti) 6= 1 | B] + 1
4 P i,A
[A(Xn,yn)(ti) 6= −1 | B] = 1
4 .
Thus for any permutation equivariant algorithm A, N ∗(A, {P}, 14 ) ≥ d 10 .
Upper Bound: Take CNN as defined in Section 3.1 with d′ = d, r = 1, k = 2, σ : Rd → R, σ(x) = ∑d i=1 x 2 i , we have FCNN = { sign [ a1 ∑d i=1(w1xi + w2xi−1) 2 + b|a1, w1, w2, b ∈ R ]} .
Note that ∀h ∈ FCNN, ∀1 ≤ i ≤ d, h(si) = a1(2w21+2w22)+b, h(ti) = a1(w21+w22+(w1+w2)2)+b, thus the probability of ERMFCNN not achieving 0 error is at most the probability that all data in the training dataset are ti or si: (note the training error of ERMFCNN is 0)
P [ xi ∈ {sj}dj=1,∀i ∈ [n] ] +P [ xi ∈ {tj}dj=1,∀i ∈ [n] ] = 2−n × 2 = 2−n+1.
4For vector x ∈ Rd, we define xi = x(i−1) mod d+1.
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, w2 as 0. (Note training the second layer only is still a permutation-equivariant algorithm for FC nets, thus it’s a valid separation.)
For any convex non-increasing surrogate loss of 0-1 loss l satisfying l(0) ≥ 1, limx→∞ l(x) = 0 e.g. logistic loss, we define the loss of the weight W as
L(W) = n∑ i=1 l(FCNN[W](xi)yi)
=NS × l ( a1(2w 2 1 + 2w 2 2) + b ) +Nt × l ( −a1(w21 + w22 + (w1 + w2)2) + b ) .
Note w1w2 6= 0 with probability 1, which means the data are separable even with fixed first layer, i.e. infa1,b L(W) = 0. Further note L(W) is convex in a1 and b, which implies with sufficiently small step size, GD converges to 0 loss solution. By the definition of surrogate loss, L(W) < 1 implies for xi, l(xiyi) < 1 and thus the training error is 0.

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