Computational Separation Between Convolutional and Fully-Connected Networks
Authors: eran malach
Shai Shalev-Shwartz
Venue: ICLR 2021 Poster (2021)
Keywords: Neural Networks
Deep Learning
Convolutional Networks
Fully-Connected Networks
Gradient Descent

Abstract: Convolutional neural networks (CNN) exhibit unmatched performance in a multitude of computer vision tasks. However, the advantage of using convolutional networks over fully-connected networks is not understood from a theoretical perspective. In this work, we show how convolutional networks can leverage locality in the data, and thus achieve a computational advantage over fully-connected networks. Specifically, we show a class of problems that can be efficiently solved using convolutional networks trained with gradient-descent, but at the same time is hard to learn using a polynomial-size fully-connected network.

Published as a conference paper at ICLR 2021
COMPUTATIONAL S BETWEEN CONVOLU- TIONAL AND FULLY-CONNECTED NETWORKS
Eran Malach
Shai Shalev-Shwariz
School Computer Science
School of Computer Science
Hebrew University
Hebrew University
Jerusalem, Israel
Jerusalem, Israel
eran, www.allllllee mhllach@mail. hwji.ui.... wuji.ac.
wwt.@sssshui.cc... shais0cs www.huiiii...
ABSTRACT
Convolutional neural networks (CNN) exhibit unmatched performance in mul- titude of computer vision tasks. However, the advantage of using convolutional networks fully-connected networks is not understood from theoretical per- spective. this work, we show how convolutional networks can leverage locality in the data, and thus achieve computational advantage fully-connected net- works. Specifically, we show a class of problems that can be efficiently solved using convolutional networks trained with gradient-descent, but the same time is hard to learn using polynomial-Se fully-connected network.
INTRODUCTION
Convolutional neural networks (LeCun al., 1998; Krizhevsky et al., 2012) achieve state-of-the-an performance every possible task in computer vision. However, while the empirical success of convolutional networks indisputable, the advantage of using them is not well understood from theoretical perspective. Specifically, consider the following fundamental question:
Why do convolutional networks (CNNs) perform better than fully-connected networks (FCNs)?
Clearly, when considering expressive power, FCNs have big advantage. Since convolution is linear operation, any CNN can be expressed using FCN, whereas FCNs can express strictly larger family of functions. So, any advantage of CNNs due to expressivity can be leveraged by FCNs as well. Therefore, expressive power does not explain the superiority of CNNs over FCNs.
There are several possible explanations to the superiority of CNNs over FCNs: parameter ef- ficiency (and hence lower sample complexity), weight sharing, and locality prior. The main sult of this paper is arguing that locality is key factor by proving computational separa- tion between CNNs and FCNs based on local- ity. But, before that, let's discuss the other pos- sible explanations.
90
CNN-2
test accuracy
80
CNN-4
CNN-6
FCN-2
FCN-6
FCN-4
First, we observe that CNNs seem be much more efficient in utilizing their parameters. A FCN needs to use a greater number parame- ters compared to an equivalent CNN: each neu- ron a CNN is limited to a small receptive field, and moreover, many of the parameters of the CNN are shared. From classical results in learning theory, using large number of param- eters may result in inferior generalization. So, can the advantage of CNNs explained simply by counting parameters?
60
0.5
1
1.5
# params
-107
Figure I: Comparison between CNN and FCN of various depths (2/4/6) and widths, trained for 125 epochs with RMSprop optimizer.

---

Published as a conference paper at ICLR 2021
To answer this question, we observe the performance of CNN and FCN based architecture of various widths and depths trained on the CIFAR-10 dataset. For each architecture, we observe the final test accuracy versus the number of trainable parameters. The results are shown in Figure 1. As can be seen, CNNs have a clear advantage over FCNs, regardless of the numher of parameters used. As is often observed, a large number of parameters does not hurt the performance of neural networks, and so parameter efficiency cannot explain the advantage of CNNs. This is in line with various theoretical works on optimization of neural networks, which show that over-parameterization is beneficial for convergence of gradient-descent (e.g., Du et al. (2018); Soltanolkotabi et al. (2018); Li & Liang (2018)).
The superiority of CNNs can be also attributed to the extensive weight sharing between the different convolutional filters. Indeed, it has been previously shown that weight sharing important for the optimization of neural networks (Shalev-Shward et al., 2017b). Moreover, the translation-invarian nature of CNNs, which relies on weight sharing, is often observed to be beneficial in various signal processing tasks (Kauderer- Abrams, 2017; Kayhan & Gemert, 2020). So, how much does the weight sharing contribute to the superiority of CNNs over FCNs?
To understand the effect of weight sharing on the behavior of CNNs, it is useful to study locally- connected network (LCN) architectures, which are similar to CNNs, but have no weight sharing between the kernels of the network. While CNNs are far more popular in practice (also due to the fact that they are much more efficient in terms of model size), LCNS have also been used in different contexts (e.g., Bruna et al. (2013); Chen et al. (2015); Liu et al. (2020)). It has been recently observed that in some cases, the performance of LCNs is on par with CNNs (Neyshabur, 2020), So, even if weight sharing explains some of the advantage of CNNs, it clearly doesn't tell the whole story.
Finally, a key property of CNN architectures is their strong utilization of locality in the data. Each neuron CNN is limited to a local receptive field of the input, hence encoding a strong locality bias. In this work we demonstrate how CNNs can leverage the local structure of the input, giving them a clear advantage in terms of computational complexity. Our results hint that locality is the principal property that explains the advantage of using CNNs.
Our main result a computational separation result between CNNs and FCNs. To show this result, we introduce family of functions that have very strong local structure, which we call k-patterns. A k-pattern is a function that is determined by k consecutive bits of the input. We show that for inputs of n bits, when the target function is a (log ni)-paterm, training CNN of polynomial size with gradient- descent achieves small error in polynomial time. However, gradient-descen will fail to learn (log n) -patterss, when training FCN of polynomial-size.
1.1 RELATED WORK
has been empirically observed that CNN architectures perform much better than FCNs on com- puter vision tasks, such digit recognition and image classification (e.g.. Urban et al. (2017); Driss et al. (2017)). While some works have applied various techniques to improve the performance of FCNs (Lin et al. (2015); Fernando al. (2016); Neyshabur (2020)), there is still a gap between performance of CNNs and FCNs, where the former give very good performance "out-of-the-box" The focus of this work is to understand, from a theoretical perspective, why CNNs give superior performance when trained on input with strong local structure.
Various theoretical works show the advantage of architectures that leverage local and hierarchical structure. The work of Poggio et al. (2015) shows the advantage of using deep hierarchical models over wide and shallow functions. These results are extended in Poggio al. (2017), showing an exponential gap between deep and shallow networks, when approximating locally compositional functions. The works of Mossel (2016); Malach & Shalev-Shwartz (2018) study learnability of deep hierarchical models. The work of Cohen et al. (2017) analyzes the expressive efficiency of convolutional networks via hicrarchical tensor decomposition. While all these works show that indeed CNNs powerful due their hierarchical nature and the efficiency of utilizing local structure, they do not explain why these models are superior to fully-connected models.
There are few works that provide theoretical analysis of CNN optimization. The works of Brutzkus & Globerson (2017); Du et al. (2018) show that gradient-descent can learn a shallow CNN with single filter, under various distributional assumptions. The work of Zhang et al. (2017)
2

---

Published as a conference paper at ICLR 2021
+1
Figure 2: Example of k-pattern with &
shows learnability of convex relaxation of convolutional networks. While these works focus computational properties of learning CNNs, as we do in this work, they do not compare CNNs to FCNs, but focus only the behavior of CNNs. The works of Cohen & Shashua (2016); Novak et al. (2018) study the implicit bias of simplified CNN models. However, these result are focused on generalization properties of CNNs, and not on computational efficiency of the optimization.
2 DEFINITIONS AND NOTATIONS
Let X' [+1] jRs be our instance space, and let y= = [+1} be the label space. Throughout the paper, we focus on learning binary classification problem using the hinge-loss: Elý: y) max {1 -y. 0). Given some distribution D over X, some target function f X + y and some hypothesis h X
V. we define the loss with respect to f on the distribution by:
(h) = TE x~D
[((h(x),
The goal of supervised learning algorithm is, given access examples sampled from D and labeled by S. to find a hypothesis that minimizes (h)).. We focus on the gradient-descent (GD) algorithm: given some parametric hypothesis class H. = {hw w E RR), gradient-descent starts with some (randomly initialized) hypothesis ()) and, for some learning rate >> O, updates:
w (1 = (1-1) 1/ w,
We compare the behavior of gradient-descent, when learning two possible neural network architec- tures: convolutional network (CNN) and fully-connected network (FCN).
Definition 1. A convolutional network W. b is defined follows:
(x.
( oo OWW -b))
for activation function a, with kernel W E Baxk bias b E R2 and readout layer u(!), ,..., u(() RRY. Note that this is a standard depth-2 CNN with kernel k. stride I and q filters.
Definition 2. A fully-connected network ha,w. is defined as follows:
Nu,w Σ uio ((w!),,)) + bz)
for activation function a, first layer w()) w( R", bias b IR9 and second layer R9.
We demonstrate the advantage of CNNs FCNs by observing problem that be learned using CNNs, but is hard to learn using FCNs. We call this problem the k-pattern problem:
Definition 3. A function f X + y is a k-pattern, for some {+1] - y and index j":
f(x)
Namely, a k-pattern is function that depends only on small pattern of consecutive bits of the input. The l-pattern problem the problem of learning k-patterns: for some k-pattern f and some distribution D over X. given access to D labeled by find hypothesis h with L (h) We note that a similar problem has been studied in Golovnev et al. (2017), providing results on PAC learnaillity of related target class.

---

Published as a conference paper at ICLR 2021
3 CNNS EFFICIENTLY LEARN (log PATTATERSS
The main result in this section shows that gradient-descent can learn k-patterns when training con- volutional networks for poly(2", n) iterations, and when the network has poly n) neurons:
Theorem 4, Assume we uniformly initialize W()) ~ [=1/k]xx b, = 1/k kk 1 and (0:3) = 0 for every j. Assume the activation satisfies |o|
c. c.loo1 I L. for some constant Fix some > 0, some k-paltern I and some distribution 'D over X. Then, if > 2*+3 log(2*/8) with probability at least 5 over the initialization, when training convolational network Wi, using gradient yn /PT
descent with 17
we have:
22
k(2*k)² Vqn
c2 /q
Σ (hoo(
T
Before we prove the theorem, observe that the above immediately implies that when k = O(log n),, gradient-descent can efficiently learn to solve the k-pattern problem, when training a CNN:
Corollary 5. Let k Ologgn), Then, running GD for T = O(E O0e2((22 logn) iterations, using a sample S ~ 'D of size O(E "nkq log(nkq/6)), learns the k-pptternn problem up to accuracy w.p. 2 1 8.
CNN with q O( n log" n) neurons
Proof. Sample S ~ DD and let D be the uniform distribution over S. Then, from Theorem and the
choice of q and T there exists [I'] with y (hato, ,wt,,,) S e/2, i.e. GD finds a hypothesis with
train loss at most e/2. Now, using the fact the VC dimension of depth-2 ReLU networks with W weights is O(W log W' (see Bartlett et al. (2019)), we can bound the generalization gap by c/2. O
To prove Theorem 4, we show that, for large enough CNN, the k-pattern problem becomes linearly separable, after applying the first layer of the randomly initialized CNN:
Lemma 6. Assume we uniformly initialize W {#1/k]]xx and b, = 11/k-1 Fix some O. Then if > 2*+3 log(2* (og(2//)) /8), w.p. 2 1
8 over the choice of W, for every k-pattern J there exist
Ww.,W.6 (1) u (n-k) E R9 with || | 2 and || for j + j", s.t. W.b = fxx).
/4
Proof. Fix some E [+1]*, then for every w(O ~ /+1/k] we have: IP [sign(w (w( = 2] 2 Denote by Ja [g] the subset of indexes satisfying sign w(()) z, for every Jz. and note that Ew |Jal = g2-x k_ From Chernoff bound:
[1 S x2 92 92 /8
82
by choosing > 2*+ log(2*/15 /8). So, using the union bound, w.p. at least 1-6, for every {=1}* we have |/2] 2 - By the choice of 6, we have o ((w((1), z)) b.) ( w()) z).
k-1
Now, fix some k-pattern f, where f(x) = s(x,'....)) + +6-1). For every i E Ja we choose u, -(0) &
[J.] g(z) and uz() = 0 for every j # jr Therefore, we get:
(Wxx +. -)) Σ u,
4:00 (000((()) ((w(), (x)."),xx....+ + bi)
* KE
Σ
= _(05)...-4--1)) s(x)
zE(+1J+
Note that by definition of u (1") we have |
Eme( Eie,, 42 1T.TT < 4 (2*k)²
Comment 7. Admittedly, the initialization assumed above is non-standard, but is favorable for the analysis. similar result can be shown for more natural initialization (c.g., normal distribution), using known results from random features analysis (for example, Bresler & Nagaraj (2020)).
4

---

Published as a conference paper at ICLR 2021
From Lemma 6 and known results on learning linear classifiers with gradient-deseent, solving the k-pattern problem can be achieved by optimizing the second layer of a randomly initialized CNN. However, since in gradient-descent fined analysis to show that full gradient-descent learns to solve the problem. We follow the scheme introduced in Daniely (2017), adapting it our setting.
optimize both layers of the network, we need more
We start by showing that the first layer of the network does not deviate from the initialization during the training:
Lemma 8. We have ||u || S nT for all j [n 10--), k), and [ w - Ty
We can now bound the difference in the loss when the weights of the first layer change during the training process:
Lemma 9, For every u² we have:
P
Whr, - Ly, woo,)))))) s 2 nk
u (
j=1
The proofs of Lemma 8 and Lemma are shown in the appendix.
Finally, we use the following result on the convergence online gradient-descent to show that gradient-descent converges good solution. The proof of the Theorem is given in Shalev-Shwartz et al. (2011), with an adaptation to similar setting in Daniely & Malach (2020).
Theorem 10. (Online Gradient Descent) Fix some n, and let fi...., fo some sequence of convex functions. Fix some 0,, and update 8.41 = 0g v)Vf((()). Then for every l the following holds:
T
T
1 T f(().) S T E f(()++ + 2nT 110-12 + 10:11 Σ
IV
+ "
Σ t=1
Proof of Theorem 4. From Lemma 6, with probability at least 1 8 over the initialization, there exist u (1) ...., u (k= E Ie with [|u](]] || s 26 and ||u~00|| 0 for > 1 such that ha wii,, 6 (x) = f(x), and so (huhh,,woo 0. Using Theorem 10, since y w.)) is convex with respect to we have:
Σ
T
T
n-
T
a
( Lg.0(Mu..wo,.p 6) +
u (i)
+ +1
Σ
L LID (I
T
2nT
Ou
t=1
1=1
t=1
(ha wro, k)
$
T
Σ
o² pmq = (*)
t=1
Using Lemma 9 we have:
T s Σ (ha w(o) + on 2T
T
2(2
u [0)
+
+ cnnn
1=1
2(2*k)²
< 2e
Empq
qnp
Now, choosing 1
f VqT
get the required.
3.1 ANALYSIS OF LOCALLY-CONNERS
NETWORKS
The above result shows that polynomial-sizz CNNs can learn (log patterns in polynomial time. As discussed in the introduction, the success of CNNs can be attributed either the weight sharing
5

---

Published as a conference paper at ICLR 2021
or the locality-biat of the architecture. While weight sharing may contribute to the success of CNNs in some cases, we note that it gives no benefit when learning k-patterns. Indeed, we can show a similar positive result for locally-connected networks (LCN), which have no weight sharing.
Observe the following definition a LCN with one hiyde:-layer:
Definition 11. locally-connected network w.,w is defined as follows:
nー
hu, W. (.)b())= Σ ( o - + +b(1)
for some activation function funcciooo o, with W()), ...., W(9) Ro bias (( ..... b( RR9 and readout layer u(1), u!!)....,, u (()) IR..
Note that the only difference from Definition is the fact that the weights of the first layer are not shared. It is easy to verify that Theorem can be modified in order to show similar positive result for LCN architectures. Specifically, we note that in Lemma 6, which is the core of the Theorem, we do not use the fact that the weights in the first layer are shared. So, LCNs "as good as" CNNs for solving the k-pattern problem. This of course does not resolve the question of comparing between LCN and CNN architectures, which we leave for future work.
4 LEARNING (log n) PAATTERNS WITH FCN
In the previous section we showed that patterns of size log n are efficiently learnable, when using CNNs trained with gradient-descent, In this section show that, in contrast, gradient-descent fails to learn (log n1 -patterss using fully-connected networks, unless the size of the network is super- polynomial (namely, unless the network is of size n[ For this, we will show an instance of the k-pattern problem that is hard for fully connected networks.
We take 'D to be the uniform distribution over X, and let f(x) = Iiir Ti. where T is some set of consecutive bits. Specifically, we take I = f1.....At, k), although the same proof holds for any choice of I. In this case, show that the initial gradient of the network is very small, when fully- network is initialized from a permutation invariant distribution.
Theorem 12. Assume ol I c, S 1. Let W be some permutation invariant distribution over R", and assume we initialize w w(1) W and initialize u such that |ug S 1 and for all x we have ha, (x) 1]. Then, the following holds:
E Ew-w 1i L, (1bu,,,, b))l S.n qn min { ((=1))² (E=))
. Ew-w la L... (h,, w. 112 (8)
From the above result, if 2(logn) n) then the average norm of initial gradient is qn qn -20lo n). Therefore, unless 9 n ([ogg)))) we get that with overwhelming probability over the randomness of the initialization, the gradient extremely small. In fact, if we run GD on a finite-precision machine, the true population gradient is effectively zero. A formal argument relating such bound on the gradient norm the failure of gradient-based algorithms has been shown in various previous works (e.g. Shamir (2018); Abbe & Sandon (2018); Malach & Shalev-Shwartz (2020)).
The key for proving Theorem 12 is the following observation: since the first layer of the FCN is initialized from symmetric distribution, we observe that if learning some function that relies on bits of the input hard, then learning any function that relies on l bits is hard. Using Fourier analysis (e.g., Blum et al. (1994); Kearns (1998); Shalev-Shwartz et al. (2017a)), we can show that learning k-parities (functions of the form x + [Ierrz;) using gradient-descent is hard. Since an arbitrary k-parity is hard, then any k-parity, and specifically parity of & consecutive bits, is also hard. That is, since the first layer is initialized symmetrically, training a FCN on the original input is equivalent to training FCN on an input where all the input bits are randomly permuted. So, for FCN, learning a function that depends on consecutive bits is just as hard as learning a function that depends arbitrary bits (a task that is known to be hard).

---

Published as a conference paper at ICLR 2021
Proof of Theorem 12. Denote X2 Ikkr T4, so f(x) Xa with I (l....,k) k}. We begin by
calculating the gradient w.r.p to w (0)
2 Ow
(hu [(x)) - - Lounoo ((w(T), bi) xx(x)]
L (.D.
E D
Fix some permutation π in] + [n]. For some vector x (Ix()) for some subset 1 S [ni] we denote (() = Ujer(m(i)}. Notice that we have for all x, R": xx(x(x)) Xa(f) and (π(x), z) (x, π (2)). Denote ((in,,,b)(x))
R we denote x(x)
+ b,). Denote (D) the distribution of π (x) where ~ D. Notice that since D is the uniform distribution, we have (DD D. From all the above, for every permutation with x(j) = we have:
E (LT(((((())
[anuzad ((w(0),)) + xx(]
I Xxxin, DM.... E xnD
awg
[iyidd (( (000,=-((x) + bi) xr(x)
E x~<(D)
22u10' ((z(w((0),x)) + b.) xx(x))
Lx 2 ( (bu,,,.))
xnD
Ow!
Fix some I C [n] with | = k and [n]. Now, let Sj be of permutations satisfying:
1. For all Tı, E Sj with कi # T2 we have (I) + T2()..
2. For all E S we have r(i)= = =j.
Note that if j I then the maximal size of such Sj is ("=²), and if j I then the maximal size (x=1)- Denote (x( = xyu,o((((()) x) b,). We denote the inner-product (1))) =
ExND (xx) and the induced norm || (wb, ///,))) v) Since (xr) is orthonormal basis w.r.p. to (D)) from Parseval's equality we have:
i (w Ix (TT.
Σ TES,
Σ xSS
Xxxus ((hu...))
aw
(3)
Σ
(g. Xx()))
Σ
(gg, (r):21100 = -11g,1? s
RES
rC
So, from the above we get that, taking Sj of maximal size:
((T. < ", < min (" iw
12
E
Lx
S
k -
Now, for some permutation invariant distribution of weights W have:
a wwW. Ow
Lx D.x...w.......)
LE
E
Lx D (..
s S|S
wwwWW
Ow,
Summing over all neurons we get:
{
1
E w-W
ae Lx D (fh
S qn min
mon-min
We similar argument to bound the gradient of We leave the details the appendix. n

---

Published as a conference paper at ICLR 2021
n=5
n=13
n=19
0.8
0.8
0.8
accuracy
0.7
0.7
0.7
0.6
CNN
0.6
0.6
LCN
0.5
0.5
0.5
0
10
20
30
10
20
30
10
20
30
epoch
epoch
epoch
19467
633/063540966
Figure 3: Top: Performance of different architectures on size-n MNIST sequences. where the label determined by the parity of the central digits. Bottom: MNIST sequences of varying length.
NEURAL ARCHITECTURE SEARCH
So far, we showed that while the (log n)-pattern problem be solved efficiently using a CNN, this problem is hard for a FCN to solve. Since the CNN architecture is designed for processing consccutive patterns of the inputs, it can easily find the pattern that determines the label. The FCN, however, disregards the order of the input bits, and so it cannot enjoy from the fact that the bits which determine the label are consecutive. In other words, the FCN architecture needs to learn the order of the bits, while the CNN already encodes this order in the architecture.
So, FCN fails recover the k-pattern since it does not assume anything about the order of the input bits. But, is it be possible to recover the order of the bits prior to training the network? Can we apply some algorithm that searches for an optimal architecture to solve the k-pattern problem? Such motivation stands behind the thriving research field of Neural Architecture Search algorithms (see Elsken et al. (2018) for a survey).
Unfortunately, we claim that if the order of the bits is not known to the learner, architecture search algorithum can help in solving the k-pattern problem. To see this, it is enough to observe that when the order of the bits is unknown, the k-pattern problem is equivalent to the k-Junta problem: learning a function that depends on an arbitrary (not necessarily consecutive) set of &o bits from the input. Learning k-Juntas is a well-studied problem in the literature of learning theory (e.g., Mossel et al. (2003)). The best algorithm for solving the (Jogn)-Junta problem runs in time (logg)) and no poly-time algorithm is known for solving this problem. Moreover, if we consider statistical-query algorithms (a wide family of algorithms, that only have access to estimations of query function the distribution, e.g. Blum et al. (2003)), then existing lower bounds show that the (log n) -Junta problem cannot be solved in polynomial time (Blum al., 1994).
EXPERIMENTS
In the previous sections we showed a simplistic learning problem that can be solved using CNNs and LCNs, but hard to solve using FCNs. In this problem, the label is determined by a few consecutive bits of the input. In this section show some experiments that validate our theoretical results. In these experiments, the input to the network is a sequence of n MNIST digits, where each digit is scaled and cropped CNN and LCN. The CNN and LCN architectures have kernels of size 24 x 24, so that 3 MNIST digits fit in a single kernel. In all the architectures we use single hidden-layer with 1024 neurons, and ReLU activation. The networks are trained with AdaDelta optimizer for 30 epochs! !
size of 24 8. We then train three different network architectures: FCN.
In each epoch we randomly shuffle the sequence of the digits.
8

---

Published as a conference paper at ICLR 2021
n=5
n=19
0.7
0.7
accuracy
accuracy
0.6
0.6
0.5
0.5
10
20
30
0
10
20
30
epoch
epoch
Figure 4: n-sequence MNIST with non-consecutive parity.
In the first experiment, the label of the example is set to be the parity of the sum of the 3 consecutive digits located in the middle of the sequence. So, as our theoretical analysis, the label is determined by small area of consecutive bits of the input. Figure 3 shows the results of this experiment. As can be clearly seen, the CNN and LCN architectures achieve good performance regardless of the choice of where the performance of the FCN architectures critically degrades for larger achieving only chance-level performance when n = 19. We also observe that LCN has clear advantage over CNN in this task. As noted, our primary focus is demonstrating the superiority of locality- -based architectures, such as CNN and LCN, and we leave the comparison between the two to future work.
Our second experiment is very similar to the first, but instead of taking the label be the parity of 3 consecutive digits, we calculate the label based on digits that are far apart. Namely, we take the parity of the first, middle and last digits of the sequence. The results of this experiment are shown in Figure 4. As can be seen, for small n, FCN performs much better than CNN and LCN, This demonstrates that when we break the local structure, the advantage of CNN and LCN disappears, and using FCN becomes better choice. However, for large all architectures perform poorly.
This research is supported by the European Research Council (TheoryDL project). We thank Tomaso Poggio for raising the main question tackled in this paper and for valu- able discussion and comments
Acknowledgements:

---

Published as a conference paper at ICLR 2021
REFERENCES
Emmanuel Abbe and Colin Sandon. Provable limitations of deep learning. arXiv preprint 1.X.:1881..0666,, 2018.
Peter L Bartleut Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension J. Mach. Learn. Res., 20:
and pseudodimension bounds for piecewise linear neural networks. 63-1,2019.
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Pro- ceedings of the twenty-sixts annual ACM symposium on Theory of computing, pp. 253-262, 1994.
Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-51) 519, 2003.
Guy Bresler and Dheeraj Nagaraj. A corrective view of neural networks: Representation, memo- rization and learning. arXiv preprint arXiv:2002.00274 2020.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 2013.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. arXiv preprint 1eXivv1702.079000 2017.
Yu-hsin Chen, Ignacio Lopez-Moreno, Tara N Sainath, Mirkó Visontai, Raziel Alvarez, and Carolina Parada. Locally-conneco and convolutional neural networks for small footprint speaker recog- nition. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
Nadav Cohen and Amnon Shashua. Inductive bias of deep convolutional networks through pooling geometry. arXiv preprint arXiv: meee:6005664440 2016
Nadav Cohen, Or Sharir, Yoav Levine, Ronen Tamari, David Yakira, and Amnon Shashua. Analysis and design of convolutional networks via hierarchical tensor decompositions. arXiv preprint arXiv: 1705.02700223000 2017.
Amit Daniely. Sgd learns the conjugate kernel class of the network. In Advances in Neural Infor- mation Processing Systems, pp. 2422-2430, 2017.
Amit Daniely and Eran Malach. Learning parities with neural networks. arXiv preprint arXiv:2002.074000 2020.
Ben Driss, Mahmoud Soua, Rostom Kachouri, and Mohamed Akil. A comparison study between mlp and convolutional neural network models for character recognition. In Real-Time Image and Video Processing 2017, volume 10223, pp. 1022306. International Society for Optics and Photonics, 2017.
Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer enn: Don't be afraid of spurious local minima. International Conference on Machine Learming. pp. 1339-1344 2018
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey, arXiv preprint /00..0/80000037777 2018.
Chrisantha Fernando, Dylan Banarse, Malcolm Reynolds, Frederic Besse, David Pfau, Max Jader- berg, Mare Lanctot, and Daan Wierstra. Convolution by evolution: Differentiable pattern produc- ing networks. In Proceedings of the Genetic and Evolutionary Computation Conference 2016,
pp. 109-116, 2016.
Alexander Golovnev, Mika Göös, Daniel Reichman, and Igor Shinkar. String matching: Communi- cation, circuits, and learning. arXiv preprint arXiv: 2017.
Eric Kauderer-Abrams, Quantifying monsslatio-invarianne in convolutional neural networks. arXiv preprint 1001.0800..044 2017.
10

---

Published as a conference paper at ICLR 2021
Osman Semih Kayhan and Jan van Gemert. On translation invariance in cnns: Convolutional layers can exploit absolute spatial location. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14274-14285, 2020.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6))983-1066, 1998.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-bail based learning applied to document recognition. Proceedings of the IEEE,
1998.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 81577 8166, 2018
Zhouhan Lin, Roland Memisevic, and Kishore Konda. How far can go without convolution: Improving fully-connected networks. arXiv preprint arXiv:1511.02555 2015.
Wen Liu, Hong Chen, Zhongliang Deng, Xinyu Zheng, Xiao Fu, and Qianqian Cheng. Lc-dnn: Local connection based deep neural network for indoor localization with esi. IEEE Access, 8: 108720-108730, 2020.
Eran Malach and Shai Shalev-Shwartz. A provably correct algorithm for deep learning that actually works. arXiv preprint arXiv: 1800::90330000 2018.
Eran Malach and Shai Shalev-Shwartz. When hardness of approximation meets hardness of learning. arXiv preprint arXiv:2008. 2008000008,08099 2020.
Elchanan Mossel.
Deep learning and hierarchal generative models.
arXiv preprint
161.001612.09057 2016.
Elchanan Mossel, Ryan O'Donnell, and Rocco P Servedio. Learning juntas. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 206-212, 2003.
Behnam Neyshabur. Towards learning convolutions from scratch. arXiv preprint arXiv:2007.1366: 2020.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. arXiv preprint arXiv:1810.05144 2018
Tomaso Poggio, Fabio Anselmi, and Lorenzo Rosasco. I-theory on depth vs width: hierarchical function composition. Technical report, Center for Brains, Minds and Machines (CBMM), 2015.
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-bur shallow-networks avoid the curse of dimensionality: a review. Inter- national Journal of Automation and Computing, 14(5):503-511 2017.
Shai Shalev-Shwartz. Ohad Shamir, and Shaked Shammah. Failures of gradient- -ased deep learning- arXiv preprint arXiv: arXiv: 1703.07900 2017a
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Weight sharing is crucial to succesful optimization. arXiv preprint 300tv::77060068777 2017b.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and trends in Machine Learning, 4(2):107-194, 20
Ohad Shamir. Distribution-specific hardness learning neural networks. The Journal of Machine Learning Research, 2018. 2018.
11

---

Published as a conference paper at ICLR 2021
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-7669 2018.
Gregor Urban, Krzysztof Geras, Samira Ebrahimi Kahou, Ozlem Aslan, Shengjie Wang, Rich Caruana, Abdelrahman Mohamed, Matthai Philipose, and Matt Richardson. Do deep convolu- tional nets really need be deep and convolutional? International Conference on Learning Representations, 2017.
Yuchen Zhang, Percy Liang, and Martin J Wainwright. Convexified convolutional neural networks. In International Conference on Machine Learning, pp. 4044-4053, PMLR, 2017.
12


Reviews:
[{"review_id": "pgX18LkPGD", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 establishes a separation result between a convolutional network (CNN) and the fully connected network (FC).\nSpecifically, the authors show that a polynomial-size of CNN trained by gradient descent with a polynomial number of iterations can learn functions that depend only on a small pattern of $k$-consecutive bits of the input,\nwhere $k = O(\\log n)$ and $n$ is the input dimension. On the other hand, they show that for FC, gradient descent fails to learn a $k=O(\\log n)$-parity function unless the network size is $\\Omega( n^{\\log n})$. Hence, the separation result in the computational aspect is proven. An experiment is conducted to support the theoretical results.\n\n\nI believe this paper makes a significant contribution. The writing is good and the proof is short and concise. The authors first discuss other possible explanations for the observation that CNN performs better than FC in practice and argue that parameter efficiency and weight sharing might not be the main reason for the superiority of CNN. Then, in the rest of the paper, the authors show that the key is that CNN is able to exploit the locality in the data.\n\n\nQ: It appears that in the analysis of the positive result regarding CNN, the training is in the neural tangent kernel regime, as you have to bound the deviation from the initial point and that you show a randomly initialized CNN already works well for the $k$-pattern problem. Does it suggest that the kernel method can learn the $k$-parity function? What is the catch here? I saw the sparsity here but I am hoping the authors can explain the intuition behind their results more.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "S6LaXnha1rN", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "It is well-known that neural networks (NN) perform very well in various areas and in particular if one looks at computer vision convolutional neural networks perform very well. Although convolutional neural networks (CNN) are limited in their architecture (since they only allow nearest-neighbour connections) compared to fully-connected NNs (FCNN), their superiority in performance is unclear. In this paper they answer the following fundamental question: can one formally show that CNNs are better than FCNNs for a specific learning task? In this direction they answer in the affirmative.  In particular, more than just giving an example, they show that an interesting property called locality, instead of other parameters like parameter and efficiency weight sharing is the reason for its superior performance. \n\nIn order to exhibit their separation, they consider the class which they denote k-patterns which is is simply a k-junta, i.e., f is a function on n-bits but when defining f it only depends on an arbitrary function of the k out of the n inputs bits, which are fixed when defining f, but unknown to a learner. In this paper, the authors consider such k-patterns which are very local simply by definition and show that for these class of functions, training a CNN with  gradient descent can learn these functions in polynomial time (for k = O(log n)) however gradient descent fails to learn these functions when training a FCNN. The proof of the lower bound for FCNN uses the well-known statistical query framework which shows that using gradient descent to learn k-parities requires time n^k (and in their application n^ log n). In order to prove the upper bound for CNN, they combine various techniques that were introduced in many recent works (in a non-trivial way).\n\nOverall, I think this paper resolves an important and interesting question. Given that most of machine learning is well understood in the non-rigorous setting, giving a rigorous separation between CNN and FCNN is an important problem and they have resolved it. If I had to be nit-picky, I would say the concept class they give this separation for is well-suited for their separation and doesn't really say much more than that, but I think it's already interesting that one can show such a separation theoretically.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QPzAgFN8FMy", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 tries to provide an explanation for the performance advantage of CNNs over FCNs  by trying to identify labelling functions where the performance gap between the two for supervised learning can be proven rigorously. The identify an interesting class of such labelling functions : the pseudo-Boolean functions called the k-pattern functions and they are able to show that depth 2 CNNs can easily learn this class.  I am personally very excited by Theorem 4. I think this is a very cool observation and this could lead to a lot of future work.  But unfortunately this is where the concrete part of the argument in this paper stops. \n\nI dont see why the argument in Section 4 is enough to prove that this k-pattern is hard to learn for FCNs. To the best of my understanding Section 4 is not an impossibility result or a lowerbound to learning but is only making a plausibility argument towards such. I think Theorem 12 is essentially motivating the conjecture that if the expected gradient at initialization can be arbitrarily small then maybe GD will find it hard to learn. But this conjecture is not getting proven here.  \n\nI think this point needs to be made clear and we need something stronger to be said about this for Section 4 to qualify as a serious piece of argument. Currently I can think of \"counter examples\" which I would like the authors to address :  Consider the ODE : dx/dt = (2/t^3)*e^{-1/t^2} with the initial condition x(0) = 0. As you can convince yourself dx/dt at t=0 = 0 So this gradient flow starts with exactly 0 velocity/gradient but this ODE does integrate to x(t) = e^{-1/t^2} which is an increasing function of time and it gets further far away from the origin as time passes.  \n\nSo if this phenomenon can happen with ODEs why cant this happen with GDs - or even SGDs where the gradient oracle is say initially sending noisy estimates of this dx/dt above and one is initializing at the origin. There noise should maybe only help rather than hurt. So given this I am not convinced that having the expected gradient at initialization being low is a barrier to GD's or SGD's movement.  I would like to know if there is a reason why my intuition based on this example could be wrong! \n\nAlso the notation \"x_{j,..j+k}\" seems to suggest that this vector comprises of the entries of the vector of x at coordinates j,j+1,..,j+k. So this is a \"k+1\" dimensional vector.  Then shouldn't W be a q x (k+1) dimensional vector and similar adjustments be made everywhere else? \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5lOSoGfIH8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Summary:\n\nThe paper studies the problem of computational separation between two-layer convolutional neural network (CNN) and fully-connected neural network (FCN). It shows that there is a class of function, which is defined in the paper as k-pattern, such that CNN could learn this class within polynomial time with polynomial number of neurons while FCN needs exponential number of neurons to avoid getting stuck at initialization.\n\nPros:\n- The problem about the separation between neural network architectures, such as CNN and FCN in this paper, is an interesting and important topic. This paper gives evidences that CNN is preferred when input data has local structure.\n- The result theoretically justifies the intuition that CNN could utilize locality of data.\n- Experiments are also provided to support the results.\n- The paper overall is well motivated and easy to follow. \n\n\nCons/Questions: I think overall this paper is good, below are some of my minor concerns/questions. \n- The current convergence proof relies on the online optimization technique, which could show the average loss across all iteration is small. I admit that the setting is different from NTK analysis. However, given that current proof also relies on the fact that the first layer does not move to much from initialization, which is quite similar with the idea of NTK analysis, I was wondering if some techniques in NTK analysis could be applied to show the convergence of last iteration. \n- As mentioned in the paper, the analysis for CNN uses a non-standard initialization.\n- The result for FCN shows that the gradient at initialization is small in expectation. I was wondering if a high probability result could also hold. Also, to show gradient descent will get stuck at initialization, seems author(s) implicitly assume that step size is upper bounded. Otherwise, one can take large enough step size to escape the initialization. It would be better to explicitly mention this.\n\n\nMinor:\n- Notations for u at time T seems to be inconsistent. In Theorem 4, it is u^{(0,j)}, while in Lemma 8 it becomes u^{(j,T)}.\n- Proof. of Theorem x. -> Proof of Theorem x.\n\nAfter authors' response:\nThanks for the response! I will keep my score.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims at answering an interesting question that puzzles the whole community of deep learning: why CNNs perform better than FCNs? The authors show that CNNs can solve the k-pattern problem much more efficiently than FCNs, which partially contributes to the answer of the question.

Pros:
1. Studies an interesting question on DNNs.
2. Constructs a specific problem, the k-pattern problem, so that CNNs can solve much more efficiently than FCNs.

Cons:
1. The analysis is only a very limited answer to the question. It only shows that CNNs are more efficient than FCNs on a very specific problem, which is of little interest to the community. On the one hand, people want to see the advantage of CNNs on more common problems, perhaps the image recognition problem (The AC understands that analyzing this problem is nearly impossible. It is just for hinting the choice of problems to analyze)? On the other hand, maybe others can find another specific problem that FCNs can solve much more efficiently than CNNs. If so, the value of this paper will be totally gone. The authors did not exclude such a possibility (Nonetheless, it is still a computational "separation" between CNNs and FCNs :)).
2. Reviewer #4 pointed out an issue in the proof. The response from the authors, though looked promising, did not fully convince the reviewer (in the confidential comment). Reviewer #3 also raised a question on the bounded stepsize. The authors should address both issues.

Overall, since the problem studied is of great interest to the community and the analysis is mostly sound, the AC recommended acceptance.
Decision: Accept (Poster)