Learning Boolean Circuits with Neural Networks
Authors: Eran Malach
Shai Shalev-Shwartz
Venue:  (2020)
Keywords: neural-networks
deep learning theory

Abstract: Training neural-networks is computationally hard. However, in practice they are trained efficiently using gradient-based algorithms, achieving remarkable performance on natural data. To bridge this gap, we observe the property of local correlation: correlation between small patterns of the input and the target label. We focus on learning deep neural-networks with a variant of gradient-descent, when the target function is a tree-structured Boolean circuit. We show that in this case, the existence of correlation between the gates of the circuit and the target label determines whether the optimization succeeds or fails. Using this result, we show that neural-networks can learn the (log n)-parity problem for most product distributions. These results hint that local correlation may play an important role in differentiating between distributions that are hard or easy to learn.

Under review as a conference paper at ICLR 2020
LEARNING BOOLEAN CIRCUITS WITH NEURAL NET- WORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Training neural-networks is computationally hard. However, in practice they are trained efficiently using gradient-based algorithms, achieving remarkable perfor- mance on natural data. To bridge this gap, we observe the property of local cor- relation: correlation between small patterns of the input and the target label. We focus on learning deep neural-networks with a variant of gradient-descent, when the target function is a tree- serusttuutured Boolean circuit. We show that in this case, the existence of correlation between the gates of the circuit and the target label determines whether the optimization succeeds or fails. Using this result, we show that neural-networks can learn the (log n)) -pa-iitity problem for most product distri- butions. These results hint that local correlation may play an important role in differentiating between distributions that are hard or casy to learn.
INTRODUCTION AND MOTIVATION
is well known (c.g. Livni et al. (0144) that while deep neural-networks can express any function that can be efficiently hard. Despite this theoretic pessimism, in practice, deep neural networks are successfully trained on real world datasets. Bridging this eecoretical-practiin machine learning nowadays. Maybe the most natural direction to bridge this gap is to find a property of data distributions that determines whether training is computationally easy or hard. The goal of this paper is to propose such property.
computer, in the general case, training them is computationally
gap seems to be the holy grail of theoretical
To motivate this, we first recall the k- k-parity problem: the input is n bits. there is subset of relevant bits (which are unknown to the learner), and the output should be 1 if the number of I's among the relevant bits is even and 11 otherwise. parity problem can be expressed by a fully connected two layer network or by depth log (2) locally connected] [ network. We observe the behavior of a one hidden-layer neural network trained on the k-parity problem, in two different instances: first, when the underlying distribution is the uniform distribution (i.e. the probability to see every bit { and second, when the underlying distribution is a slightly biased product distribution (the probability for every bit to be 1 is 0.6). As can be clearly seen in figure [ adding a slight bias to the probability of each bit dramatically affects the behavior of the network: while the uniform distribution the training process completely fails, in the biased case it converges to a perfect solution.
well known (e.g. (Shalev-Shwand SSwartz et al. (201) 7b) that the
This simple experiment shows that small change in the underlying distribution cause dramatic change in the trainability of neural-networks. A key property that differentiates the uniform from the biased distribution the correlation between input bits and the target label. While in the uniform distribution, the correlation between each bit and the label is zero, in the biased case every bit of the k bits in the parity has non- neglliiiee correlation to the label (we show this formally in section 5 So, local correlations between bits of the input and the target label seems to be promising property which separates easy and hard distributions.
In this paper. we analyze the problem of learning tree-structured Boolean circuits with neural- networks. The key property that we assume is having sufficient correlation between every gate in the circuit and the label. We show that variant of gradient-descent can efficiently learn such
i.c. every adjacent neurons are only connected one neuron in the upper layer.

---

Under review as a conference paper at ICLR 2020
biased uniform
0.9
accuracy
0.8
0.7
0.6
0.5
0
0.5 iteration
-10
Figure 1: Trainig ReLU networks with one hidden-layer of size 128 with Adam optimizer, on both instances the k-Parriy problem n 128). The figure shows the accuracy on set.
circuits for some families of distributions, where at the same time, without correlation, gradient- descent is likely to fail. More concretely, we discuss specific target functions and distributions that satisfy the local correlation requirement. We show that for most product distributions, gradient- descent learns the (log n -)-pait problem (parity on log bits of an input with dimension n)), We further show that for every circuit with AND/OR/NOT gates, there exists a generative distribution, such that gradient-descent recovers the Boolean circuit exactly.
Admittedly, as the primary focus this paper is on theoretical analysis, the distributions we study are synthetic in nature. However, to explain the empirical success of neural-networks, we need to verify whether the local correlation property holds for natural datasets as well. To confirm this, we perform the following simple experiment: random patch from images in the ImageNet dataset. We observe that even on a complex task such as ImageNet, network that gets only a 3 patch an input, achieves 2.6% top-5 accuracy much better than a random guess (0.5% top-5 accuracy). The full results of the experiment are detailed in the appendix. This experiment highlights that, to some extent, natural datasets display local correlation property: even few "bits" of the input already have some non-negligible information on the target label.
train network with two hidden-layers
single
RELATED WORK
In recent years, the success of neural-networks has inspired an ongoing theoretical research, trying to explain empirical observations about their behavior. Some theoretical works show failure cases of netral-setworks. Other works give different guarantees on various learning algorithms for neural- paper.
networks. In this section, cover the main works that relevant
Failures of gradient-based algorithms. Various works have shown different examples demonstrat- ing failures of gradient-based algorithm. The work of SSamii (2018) shows failures of gradient descent, both in learning natural target functions and in learning natural distributions. The work of Shalev-Shwartz et al. (2017) shows that gradient-descenl fails learn parities and linear-periodic functions under the uniform distribution. In Das et al. (219)) a hardness result for learning random deep networks shown. Other similar failure cases also covered in Abbe & Sandon (2018); Malach & Shalev-Shwarde
(2019). While the details of these works differ, they all share the same key principal if there no local correlation, dradient fails. Our work complements these results, showing that in some cases, when there are local correlations to the target, gradient-descent succeeds to learn the target function.
Learning neural-networks with gradient-descent. Recently, large number of papers have pro- vided positive results on learning neural-networks with gradient-descent. Generally speaking, most of these works show that over-parametrized neural-networks, deep shallow, achieve performance that is competitive with kernel-SVM. Daniely (2017) shows that SGD learns the conjugate kernel associated with the architecture of the network, for wide enough neural-network. The work of Brutzkus et al. (2017) shows that SGD learns neural- network with good generalization, when the target function linear. A growing number of works show that for specific kemnll induced
2

---

Under review as a conference paper at ICLR 2020
by the network activation, called the Neural Tangent Kernel (NTK), gradient-descent learns over- parametrized networks, for target functions with small norm in the reproducing kernel Hilbert space (see the works of Jacot et al. (2018); Xie et al. (2016); Oymak & Soltanolkotabi (2018) Allen-Zhu
jet al. (2019)
8018a b); Oymak & Soltanolkotabi (2019h; Arora et al. (2019): Du et al. (2018); Ma et al.
Lee et al. (2019)) While these results show that learning neural-networks with gradient-
descent is not hopeless, they are in some sense disappointing - in practice, neural-networks achieve performance that are far better than SVM, a fatt that is not explained by these works. A few results do discuss success cases of gradient-descent that go beyond the kernel-based analysis (Brutzkus & Globerson 2017 2019 Allen Zhu & Li| 2019 Yehudai & Shamir 2019). However, these works still focus on very simple cases, such as learning single neuron, or learning shallow neural-networks in restricted settings. In this work we deal with learning deep networks, going beyond the common
reduction to linear classes of functions.
Layerwise optimization algorithms. In this paper, we analyze the behavior of layerwise gradient- descent- - optimizing one layer at a time, instead of the common practice to optimize the full network end-to-end. We do so since such algorithm greatly simplifies our theoretical analysis. While layerwise training is not common practice, recent works (Belilovsky et al., 2018 2019) have shown that such algorithms achieve performance that are competitive with the standard end-to-end approach, scaling up to the ImageNet dataset. We note that other theoretical works have studied iterative algorithms that learn neural-networks layer-by-layer (Arora et al.) [2014] Malach & Shalev- Shwartz 2018). However, our work focuses specifically on layerwise gradient-descent, considering the problem of learning Boolean circuits.
Learning Boolean Circuits. The problem of learning Boolean circuits has been studied in the classical literature of theoretical machine learning. The work of Kearns et al. (1987) gives various positive and negative results on the learnability of Boolean Formulas, including Boolean circuits. The work of Linial et al. (1989) introduces an algorithm that learns a constant-depth circuit in quasi- polynomial time. Another work by Kalai (018) discusses various properties of learning Boolean formulas and Boolean circuits. Our work differs from the above in various aspects. Our main focus is learning deep neural- networks with gradient descent, where the target function is implemented by Boolean circuit, and we do not aim to study the learnability of Boolean circuits in general. Furthermore, we consider Boolean circuits where a gate can take any Boolean functions, and not only AND/OR/NOT, is often considered in the literature of Boolean circuits. On the other hand, we restrict ourselves to the problem of learning circuits with a fixed structure of full binary trees. We not aware of any work studying problem similar ours.
PROBLEM SETTING
We consider the problem of learning binary classification functions over the Boolean cube. So, let X' = [=1]" be the instance space and ) = {=1} be the label set. Throughout the paper, we assume the target function is given by Boolean circuit. In general, such assumption effectively does not limit the set of target functions, as any computable function can be implemented by a Boolean circuit. We define circuit C to be directed graph with input nodes and single output node, where each inner node has exactly two incoming edges, and is labeled by some arbitrary Boolean function f {=1]² + [=1], which we call gate For each node in C we denote by (u)) E ( (+1)²- + [+1}} its gate. We recursively define hw.c : (+1]) {+1 to be:
h=,c(x) (v) (Au,, c(:), c()))
where u1, u2 are the two nodes with outcoming edges to v. Finally, define he ho where is the output node.
We study the problem of learning the target function he, when C is a full binary tree, and n 2d where d is the depth of the tree. The leaves of the tree are the input bits, ordered by Tı.... In- Admittedly, such assumption greatly limits the set of target functions, but still gives a rather rich family of functions. For example, such circuit can calculate the parity function on any & bits of the input (the function calculated by f() = ll 24 for some set of indexes T). We note that the total number of functions calculated by such tree grows like 6", as shown in Farhoodi et al. 2019).
2 Note that in the literature on Boolean circuits it is often assumed that the gates are limited to heing AND/OR and NOT. We allow the gates to take any Boolean function, which makes this model somewhat stronger.
3

---

Under review as a conference paper at ICLR 2020
We introduce few notations that used in the sequel. Fix some tree structured binary circuit C. This circuit has levels, and we denote Vi, the j-th node in the i-th level of the tree, and denote Vi. (Vs,)). Fix some E [d], let n, := 2', and denote by r {+1) + {=1]n// the function calculated by the i-th level of the circuit:
[x( (7--1, (21, 22). 1 (In:))
For i < i', we denote: Te... := :; o ...o Fp. So, the full circuit is given by hc(x) I (.)..(
As noted, our goal is to learn Boolean circuits with neural-networks. To do so, we use a network architecture that aims to imitate the Boolean circuits described above. We replace each Boolean gate with a seural-gates a one hidden-layer ReLU network, with a hard-tanlf activation on its output. Formally, let be the ReLU activation, and let ø be the hard-tanh activation, So:
x x 5 -1
a (x) max (1, 0), ((x)
x
IE (-1,1)
x21
Define a neural-gate to be a neural-network with one hidden layer, input dimension 2, with ReLU activation for the hidden-layer and hard-tanh for the output node. Namely, denote Jw.v RR2 R such that:
gw (x) = Φi Poo((wr x)))
Notice that a neural-gate Iw,s of width 4 or more can implement any Boolean gate. That is, we can replace any Boolean gate with a neural-gate, and maintain the same expressive power. To implement the full Boolean circuit defined above, we construct a deep network of depth d (the depth of the Boolean circuit), with the same structure as the Boolean circuit. We define blocks, each block has neural-gates with the same structure and connectivity as the Boolean circuit. A block Bw v IR2 R defined by:
Bw yoo (x) ( (6.a) (11, x22,, (wi (Iz,, za).... ".a 1 101,2)
(Z22-1,
We consider the process of training Bwite, v(d). Notice that indeed, network Nw.v implement any tree-structured Boolean cir- cuit of depth d. In practice, neural-networks are trained with gradient-based optimization algorithm, in end-to-end fashion. That is, the weights of all the layers are optimized together, with gradient updates on a given sample. To simplify the analysis, we instead consider a layerwise optimization algorithm, that performs gradient updates layer-by-layer. While this approach is much less popu- lar, it has been recently shown to achieve performance that are comparable to end-to-end training, scaling up the ImageNet dataset (Belilovsky al. 2018).
of the form Nw. = Bw vv v o
Denote by P the average-pooling operator, defined by P(E = E Iy. Denote the hinge-loss by E(g. y) max(1 yÿ. 0) and denote the loss on the distribution by LD(f) B(a.))~D [(( v)]. For a sample S S X' x V, denote the loss on the sample by Ls(f) =
E Ee {(((x).)) (.).))) y). The layerwise gradient-descent algorithm for learning deep networks is described in algorithm
For simplicity, we assume that the second layer of every neural-gate is fixed, such that v E {+1]. Notice that this does not limit the expressive power of the network. Algorithm | iteratively opti- mizes the output of the network's 's layers, starting from the bottom-most layer. For each layer, the wverage-pooling operator is applied is optimized with respect to the target label. Note that in fact, we can equivalently optimize each neural-gat gate separately and achieve the same algorithm. However, we present layerwise training process to conform with algorithms used in practice.
reduce the output of the layer to a single bit, and this output
We chose to use the hard-tanh activation over the more popular tanh activation since it simplifies theoretical analysis. However, we believe the same results be given for the tanh activation.
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Layerwise Gradient-Descen
input:
Sample C X' V/ number of iterations E N, learning rate 1) E IR.
Na id
for d... de
Initialize W (8)
for 1...7 do
Update w
W - 2o
Ls( (P(B with v/ Ng))
v
end for Update No-1 B Who, vo o.
end for Return No
MAIN RESULTS
Our main result shows that algorithm can learn a function implemented by the circuit C, when running on "nice" distributions, with the local correlation property. We start by describing the distributional assumptions needed for our main results. Let D be some distribution over X' x V. For some function f X + X', we denote by S(D) the distribution of (f(z), y) where (I, D. Let D(0 be the distribution I ((i+1)... Denote by c.j the correlation between the output of the j-th gate in the i-th layer and the label, so: C. == Epo [zzz]]
Define the influence of the j-th gate in the i-th layer with respect the uniform distribution (U) by:
Iıjj := Pa-U (x)) A i @ e;)] PP-- [ (2) + ri- (Z (Zi,.... ........ -....... In)] Now, we introduce the main assumption on the distribution D. We assume the following: Assumption 1. (local correlation) There exists some A (0, 1) such that for every layer i [d] and for every gate E [2'] with Iz, + O, the value of Ci.j satisfies |ci,l > [R [v]l A.
Another technical assumption we need to make is the following:
Assumption 2. (label bias) There exists some 3 E (0, 1) such that ED [vl
B.
Before we present the main results, we wish to discuss the distributional assumptions given above. Assumption i is the key assumption required for the algorithm to succeed in learning the target func- tion. Essentially, this assumption requires that the output of every gate in the circuit will "explain" the label slightly better then simply observing the bias between positive and negative examples. Clearly, gates that have no influence on the target function never satisfy this property, so we require only for influencing gates. While this is strong assumption, in section we discuss examples of distributions where this assumption typically holds. Furthermore, the experiment described in section hints that this assumption may hold for natural data. Assumption 2 is simple technical assumption, that requires that the distribution of positive and negative examples is slightly biased. In a sense, we expect that "most" distributions would not be exactly balanced, so this assumption is easy to satisfy.
Now, consider the case where D (limited to X) is a product distribution: for every * J', the variables zj and zy' independent, for (x. ~ D. A simple argument shows that any product distribution D that satisfies assumptions] [ satisfies the following properties:
Property 1. There exists some A E (0, 1) such that for every layer [d] and for every gate j E [2'), the output of the j-th gate in the i-th layer satisfies one of the following:
The value of the gate is independent of the label y, and its influence is zero: Iijj 0.
The value of Gig satisfies |ca,1 > EE [w] +
Property 2. For every layer i E [d], and for every gate j E [22-1), the value of (x25-1 1,, 125)) (i.e, the input to the j-th gate of layer 1) independent of the label y given the output of the j-th gate:
P ((.)))Dio [112] x22)) P. y = s (12)
P (())))D( [ 1, Ø22) 1 {2 P ((m.))DD [y = 1/11-15 125)
5

---

Under review as a conference paper at ICLR 2020
Property is immediate from assumption 1 The following lemma shows that property 2 is satisfied as well for any product distribution:
Lemma 1. Assume D (restricted to X) ) is a product distribution (i.e., for every + j' we have that I and y are independent, for (z. y) ~ DD. Then 'D satisfies property 2
Notice that properties 1 may hold for distributions that are not product distribution (as we show in the next section). Specifically, property 2 is very common assumption in the field of Graphical Models (see Koller & Friedman (2009)) For our results to hold in a more general setting, we use properties I and instead of assuming that D is product distribution satisfying assumption T So, given a distribution satisfying properties 2 and assumption 2 we show that algorithm achieves an arbitrarily good approximation with high probability, with sample complexity and run-time quasi- polynomial in the dimension n::
Theorem Let DD be a distribution satisfying properties 4 and assumption for every i initialize ( such that (
Assume that
S
4v2k" Fix some c, 0 and
max
sume that k 2 log ((4) 1og( (2nd), and that "j I
Assume we sample S ~ D, with
16k
|S] min A. 2,2 11+44 log -2 2ng min( (A,2A) log( Snd 8
128
Then, with probability at least 1 - 5, when
running algorithm 7 on the sample S. the algorithm returns the function such that:
E ( (No(z) + hc(()) S
when running T
3 min min:Ann...... 20JE
0.5+ log min min (A,2H) steps for each layer.
The above shows a learnability result in the standard PAC setting (given our distributional assump- tions), where we only guarantee approximation of the target function under the given distribution. In fact, we can get a stronger result, and show that the algorithm learns the function le exactly, with run-time and sample complexity polynomial in n. To get this result, we need to require that there is no feasible pattern (pair of bits) in the Boolean circuit that is extremely rare:
Assumption 3. There exists some c E (0, such that for every layer i E [d]. for every gate j [2'-|] and for every p {=1}² such that ((a.))/D ((22)-1.22)) pl 0, it holds that: P (m..))DD [, = p 2
In section 5 we discuss distributions that satisfies assumption 3 we get the following:
Given all the above assumptions,
Theorem 2. Let D be a distribution satisfying properties
7
2 and assumptions
Assume 4v2k" Fix some >>> 0 and as-
that for every i we initialize w( such that W(
max
sume that ho 2 log (())
Assume we sample S DD with mint 2,377 log( (Sgd) ). Then, with probability at least 1 - 8, when running algorithm
log( log( 2gd), and that n S Isk
|S| >
128
on the sample S, the algorithm returns function such that No(x)) = hc( for all x E EX, when steps for each layer.
3v2n running T (mn].
We give the full proof of the theorems in the appendix, and give a sketch of the argument here. Observe that the input to the (i, neural-gate is a pattern of two bits. The target gate (the (i,j)-th gate in the circuit C)) identifies each of the four possible patterns with a single output bit. For example, if the gate is OR, then the patterns {(1, 1), (-,, (1, get the value 1, and the pattern (-1,-1) gets the value 1.. Fix some pattern E [=1}², and assume that the output of the (i. -)th gate on the pattern p is 1. Since we assume the output of the gate is correlated with the label, the loss function draws the output of the neural-gate on the pattern p toward the correlation of drawn
the gate. In the case where the output of the gate on p is 11, the output of the neural-gan to the opposite sign of the correlation. All in all, the optimization separates the patterns that evaluate to 1 from the patterns that evaluate to 1. In other words, the neural- -atee learns to implement the target gate. This way, we can show that the optimization process makes the network recover all the influencing gates, so that at the end of the optimization the network implements the circuit.
Observe that when there is correlation, the above argument fails immediately. Since the label is slightly biased, when there is no correlation the output of the neural-gane is drawn towards the bias of the label for all the input patterns, regardless of the value of the gate, If the gate is not influencing
6

---

Under review as a conference paper at ICLR 2020
the target function (i.e. I 0), then this clearly doesn't 't effect the overall behavior. However, if there exists some influencing gate with no correlation to the label, then the output of the neural-gate will be constant all its input patterns. Hence, the algorithm will fail to learn the target function. This shows that assumption is fact critical for the success of the algorithm.
5 DISTRIBUTIONS
In the previous section we showed that algorithm | can learn tree-structured Boolean circuits in polynomial run-time and sample complexity. These results require some non-trivial distributional assumptions. In this section we study specific families of distributions, and show that they satisfy the above assumptions.
First, we study the problem of learning parity function on log bits of the input, when the under- lying distribution a product distribution. The problem of learning parities studied extensively in the literature of machine learning theory (Feldman et al., 2006 2009 Blum et al. 2003] [Shale-] Shwartz et al., 2017 Brutzkus et al. 2019), and serves as good case-study for the above results. In the (log r p-arity problem, we show that in fact most product distributions satisfy assumptions 3 hence our results apply most product distributions. Next, we study distributions given by generative model. We show that for every circuit with gates AND/OR and NOT, there exists distribution that satisfies the above assumptions, so algorithm [ can learn any such circuit exactly.
5.1 PRODUCT DISTRIBUTIONS
We observe the k-Parity problem, where the target function is f(x) il r Ty some subset I [n]] of size [|| k. simple construction shows that f can be implemented by tree structured circuit as defined previously. We define the gates of the first layer by:
21
22j 1, U2j E I
21
T2
1 22 $
Rd (211
=
22
T2j
I, 12 1 $
0.W
And for all other layers i < d d- 1, we define: ( 21) 21 Then we get the following:
Lemma 2. Let C' be a Boolean circuit as defined above. Then: ho(x)) = Ilser 2j = f(x).
Now, let Dx be some product distribution over X, and denote pj := PDx [az = 1]. Let 'D be the distribution (æ, f(x)) where x ~ Dx. Then for the circuit defined above we get the following result:
Lemma 3. Fix some & E (0, 1). For every product distribution D with p5 E (E, -
for every j. it holds that if In.j # 0 then le.gl (-).
E [v]] 2 &h and F(z.)) (..) [ E
The above lemma shows that every product distribution that is far enough from the uniform distri-
bution, from constant distribution, satisfies assumptions [ and 2 with B, A (2E)* Using the fact that at each layer, the output of each gate is an independent random variable (since the input distribution is a product distribution), we get that assumption is satisfied with e = -a This gives us the following result:
Corollary 1. Let D be product distribution with p; E (5, -) U) E. E) for every j.
with the target function being the (log ParPit (i.e., k = logn). Then, when running algorithm ! as described in Theorem 2 with probability 1 1- the algorithm returns the true target function he, with run-time and sample complexity polynomial n.
5.2 GENERATIVE MODELS
Next, move beyond product distributions, and observe families of distributions given by gener- ative model. We limit ourselves to circuits where each gate is chosen from the set (A, V, -A, -A,-V), For every such circuit, define generative distribution follows: start by sampling label

---

Then iteratively, Under review as a conference paper at ICLR 2020
for the example, from slightly imbalanced distribution (to satisfy assumption 2)
for every gate, we sample uniformly at random a pattern from all the pattern that give the correct output. For example, if the label is and the topmost gate is OR, we sample a pattern uniformly from {11, 1), (1, 1), (-1, 1)). The sampled pattern determines what should be the output of the second topmost layer. For every gate in this layer, sample again a pattern that will result in the correct output. We continue in this fashion until reaching the bottom-most layer, which defines the observed example.
Formally, for a given gate I' E {A, VA -V,, we denote the following sets of patterns:
=p = fu E (+1}² T(01, 02) 1), SF {=1}² Sr
We recursively define D("), ,..., D(d), where D(() is a distribution over {=1]²* x {=1}:
D( is distribution supported on {(1, 1), (-1,,-1)))1)) such that Por [11, 1)] 1/2 + g and
P pio) [[-1, -1)] 1/2 - &. for some 0 < < 12 (3)
To sample (xx D(i), first sample (z, v) D(i-1), Then, for all j 12 if
23 = 1 sample 2jj ~ Uni(S,,,)) and if 2j = -1 sample z'j ~ Uni(S ). Set x
[21,-... 2g. E {=]]², and return (æ,
Then we have the following results: Lemma 4. For every E [d] and every j E [2"). denote c.j (m.)))D [z,z). Then we have:
|c,a E [vl
1 2
1
n2 (2g(3/3)
3
3
3
We also need the following simple observation:
Lemma 5. For every E [d] we have (((()))== = D(G-1)
By definition, we have [y] 26. so D(d) satisfies assumption 2 with = &. Notice that from Lemma 4 the distribution Did) satisfies property I with A f (2g(3)) (note that since we re- strict the gates to AND/OR/NOT, all gates have influence). By its construction, the distribution also satisfies property 2 and satisfies assumption 3 with (1)² = n Therefore, we can apply The- orem 2 on the distribution D(4), and get that algorithm learns the circuit C exactly in polynomial time. This leads to the following nice corollary:
Corollary 2. With the assumptions and notations of Theorem for every circuit C with gates in {A, V, -n,-V,, there exists distribution D such that when running algorithm 7 on sample from D, the algorithm returns he with probability 1 in polynomial run-time and sample complexity.
Note that the fact that for every circuit there exists a distribution that can be learned in the PAC setting is trivial: simply take distribution that is concentrated on single positive example, and approximating the target function on such distribution is achieved by classifier that always returns a positive prediction. However, showing that there exists distribution on which algorithm exactly recovers the circuit, is certainly non-trivial.
6 DISCUSSION
In this paper we suggested the property of local corrleation as a possible candidate for differenti- ating between hard and easy distributions. We showed that on the task of learning tree-structured Boolean circuits, the existence of local correlations between the gates and the target label allows layerwise gradient-deseent to Iearn the target circuit. Furthermore, we showed specific tasks and distributions which satisfy the local correlation property. These results raise a few open questions, which we leave for future work. The most immediate research problem is showing similar results for more general structures of Boolean circuit, and on a wider range of distributions (beyond product distributions or generative models). More generally, we suggest that the local correlation property may be important in a broader context, beyond Boolean circuits. For example, examining whether an equivalent property exists when the target function is a convolutional network is extremely inter- esting open problem. Needless to say, finding other properties of natural distribution that determine whether gradient-basee based algorithms succeed or fail is another promising research direction.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Emmanuel Abbe and Colin Sandon. Provable limitations of deep learning. arXiv:1812.063399 2018.
arXiv preprint
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint arXiv:1905.103:3 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter ized neural networks, going beyond two layers. arXiv preprint arXiv:1811.049/ 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. arXiv preprint 1rXiv:1811.03962 2018b.
Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma. Provable bounds for learning some deep representations. In International Conference on Machine Learning, pp. 584-592, 2014.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584, 2019.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. arXiv preprint /8/2 2018.
Eugene Belilovsky, Michael Fickenberg, and Edouard Oyallon. Decoupled greedy learning of cnns. arXiv preprint arXiv: 1911190011144. 2019.
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-57) 2003.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian Hhaaning-Volume Volume 70, pp-
inputs. In Proceedings of the 34th International Conference on Machine Learning- 605-614. JMLR. org, 2017.
Alon Brutzkus and Amir Globerson. Why larger models generalize better? a theoretical per- spective via the xor problem. In International Conference on Machine Learning, pp. 822-830, 2019.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. arXiv preprint arXiv:1710.10174, 2017.
Alon Brutzkus, Amit Daniely, and Eran Malach. Id3 learns juntas for smoothed product distribu- tions. arXiv preprint 190.::99060086... 2019.
Amit Daniely. Sgd learns the conjugate kernel class of the network. In Advances in Neural Infor- mation Processing Systems, pp. 2422-242244222 -2430, 2017.
Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, and Rina Panigrahy, On the learnability of deep random networks. arXiv preprint xrXiv:190400366. 2019.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018.
Roozbeh Farhoodi, Khashayar Filom, Ilenna Simone Jones, and Konrad Paul Kording, On functions computed on trees. arXiv preprint arXiv: 02309, 2019.
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. New results for learning noisy parities and halfspaces. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) pp. 563-574. IEEE, 2006.
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM Journal on Computing, 39(2):606 645, 2009.

---

Under review as a conference paper at ICLR 2020
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Gil Kalai. Boolean functions: Influence, threshold and noise. In European Congress of Mathematics, pp. 85-110, 2018.
Michael Kearns, Ming Li, Leonard Pitt, and Leslie Valiant. On the learnability of boolean formulae. In Anmual ACM Symposium on Theory of Computing: Proceedings of the nineteenth annual ACM conference on Theory of computing, volume 1987, pp. 285-295, Citeseer, 1987.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein and Jef- frey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. arXiv preprint 1mXiv:1902.06720 2019.
Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. In 30th Annual Symposium on Foundations of Computer Science, pp. 574-579. IEFE, 1989.
Roi Livni, Shai Shalev- Shwarr-S and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in neural information processing systems, pp. 855-863, 2014.
Chao Ma, Lei Wu, et al. A comparative analysis of the optimization and generalization property of two-layer neural network and random feature models under gradient descent dynamics. arXiv preprint arXiv: 04326, 2019.
Eran Malach and Shai Shalev-Shwartz. A provably correct algorithm for deep learning that actually works. arXiv preprint arXiv: 2018.
Eran Malach and Shai Shalev-Shwartz. Is deeper better only when shallow is good? arXiv preprint TrXiv:/903.03480 2019.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? arXiv preprint arXhv:1812.10004 2018.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparaneetrrizatio:: global con- vergence guarantees for training shallow neural networks. arXiv: 1902,0400 04674 [cs, math, stat], February 2019. http::tt//aaatt http://aaaaa...cg//////0000000
arXiv: 1902.04674.
Shai Shwarz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In Proceedings of the 34th International Conference on Machine Learning- Learning-Volume Volume 70, pp. 3067-
3075. JMLR. org, 2017.
Ohad Shamir. Distribution-spedee hardness of learning neural networks. The Journal of Machine Learning Research, 19(1): 1011115-1100 1163, 2018.
Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. arXiv preprint 161 1ot.::11....311.111111111 2016.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint 19Xiv: 2019.
10

---

Under review as a conference paper at ICLR 2020
A
EXPERIMENTS
Figure details the results the ImageNet experiment discussed the introduction.
Top-5 (random)
Top-5 (single-patch)
accou accuracy (%
Top-1 (random)
Top-1 (single-patch)
3
7
patch size (px)
Training ReLU neural network, with two hidden-layers of size 512, on a single patch of size ie x & from the ImageNet data. The patch is randomly chosen from inside the image. We train the networks with Adam, with batch size of 50, for 10k iterations.
Figure 2:
B PROOFS OF SECTION
We assume w.l.o.g that for every i.ý such that Zz = O, the (i,j) gate is constant Yi = sign(EE [v]). Since the output of this gate has influence the output y, freely without changing the target function. To prove Theorem [ and Theorem
choose
[ we observe the behavior of the algorithm on the i-th layer. Let v {=1]m {=1}" "h be some mapping such that (<x) (&1 21,... En, -nn)) for fI....: {+1). We also define pi {=1)m//2 + tt1/ such that:
pz(2)
where My = sign((--1))
C-1, #0
Fix some e'> 0. We need to handle "bad" examples examples that "rare" patches appear in them. For every (i.j) gate, we observe all the input patterns p to the (i, gate that appear with probability at most e'. Denote the following set of triplets:
P.r {i.,.p) P(ma))DO) (122-11. = pp < <e}
Denote the following set of "bad" examples:
:- x 3(I.j.)) E P. s.t. (225-1, 225) = for x [((++))...())
We have the following important result, which we prove in the sequel:
Lemma 6. Fix > and let I e such that P (( x X < 8v2n, min (A, 233. Assume
we initialize w (0) such that |Lm0 S TI- Fix > O. Assume we sample S ~ D, with |S| >
128 log( 8q:). Assume that k. 2 log (g)) log( 88z),, and that S I6k Let v X
-1,1]a//2 such that for every X we have (xx) v ((+)))...(xx) for some ub defined
above. Assume we perform the following updates:
w (6) + (
(PBB ( (.
Ow
Then with probability at least for for every & X.
3n.
we huve: w yio (2(2)) (
/2 min (A229)

---

Under review as a conference paper at ICLR 2020
Given these results, can prove the main theorems:
Proof. of Theorem and Theorem 2 Fix d' = a- Let 6D 2 ... 2 ca > such that for every E [d]
we have: (())))) @ E Le,
< fi-1 min A A.23 (we will note the exact value of e; later), We show 8v2n,
that for every i E [d], w.p at least 1 - (d - i + 1)8', after the i-th step of the algorithm we have
N (z) = yp o ot (x) for every x & X By induction i:
For i d, we get the required using Lemma with e', v/ id and e Ed-1. Ed-
Assume the above holds for and we show for i i 1. By the assumption, w.p at least 1- (d i- 1)8' we have 1zx = 4i o (o....((x)) for every a & Ne. Observe that:
aw () (P(B w vo 1) o NN- @LN(-1(D)
ÖLD
aw(i-1) (i "w""",,""" v...-)))))
So using Lemma 6 with di Pi, v Ni and e 6j-2, = Ei-1 we get that w.p at least
1- 8' we have B B 1) v. (xx) 9i-1 o -i- pp(a)) for every x & Xe-22 In this case, since si o pi = id, we get that for every æ & Ne,
N1-2(x)= = ( yo " (x)
= (Pi-1 i pi)) (4ps o T (zr) = Pi-1 oo ((
and using the union bound gives the required.
Notice that (01 = id: by definition of D = I for (z. v) ~ D(0) we have 2 = (I..((a)) and also y = (<) for (z, y) D. Therefore, we have Co,1 = (zzg) [xy] = 1. and there- fore (2) = sign(Co.1) = Now, choosing i 1, the above result shows that with probability least 1 1- 6, the algorithm returns No such that Noxx) = 11 o oli o.... .la(() = hc( for every X
To prove Theorem implies that P. and therefore X. = 0, so the theorem follows. To prove Theorem | we
enough to observe that when taking 6o = 6d = 6, assumption
take co = c and inductively define 6; f A.2() Notice that |Pe, S E Ejetar 2 [{=1}
32v/n²
log 2 = 4n. So, using the union bound we get: ==
P PIaWy~D (o E Ke.]
P(aw)>> MUSIEER I ((+))).(())(2) P
Σ
P P(any>D
p]
(L..p)eP.,
Σ
P P(an))DD (x = =pl P E; S
4--1
8/2n,
(I..P))P.
Now, observing that <
min A.203%
fl (2, no.042logn
gives the required.
28 24g
In the rest of this section we prove Lemma 6 Fix some i E [d] and let j E [n./2]. With slight abuse of notation, we denote by (t) the value of the weight (i.) at iteration t, and denote v := (..) and gr : (w Recall that we defined (xxx)
(&1 21,..., 2nn)) for & e.... En, E {+1). Denote D = ()(())) the distribution of (1/(z)) y). where (æt ~ D(i) Lety := %- and let
y such that ((1,, .22 = 7(22)-1 -1, Eas x2). For every E {+1}? denote P == (E2j-1P1, E25P2),
so we have (p) (p). Then have the following:
Lemma 7. Fix some p E {+1}2 such that (i.j.)) p) & P.. For every I E [k] such that (wo²), .p) > and (x( E (-1, 1), the following holds:
a D0
22c
-5(p)ens dw
p)
min A 23}
n;
12

---

Under review as a conference paper at ICLR 2020
Proof. Observe the following:
po (t)
Φ 2 ni/2
(P(Bwro,,to))
(m
l' (eeBiiis.roeee
Σ
( (1, 222))
owl (t) ni j'ml
2
E (a.)))
y
dw (c) St (122)-1
11;
-111(9(((2--11222) E (-1,1)) 1((0))) (12)-11 > 03 (12)-1,
T4 (a.y))D(1))
We use the fact that (P v (2=) y, unless P(Bwa, ((B E {+1), in which case
Io (2))) E { so awl (22) = O. Fix some p E {+1}² such that (w)) .p) > 0.
Note that for every p * p' {=1} we have either (p.p') or p -p' in which case (wo) .P") < 0. Therefore, we get the following:
TL. Ow! (t) P)
2 E (a.))) n4
(0 (-1,1)) 1((w)) (8) ((2))1:22))) 0} ((12)-1, p))
E
(mn))Din 1- (-001 E (-1, (( = p) |pl|]
74
Denote 9p == P (m..))>D()) [[22]-1, p p17(22)-1,225) -(p)]. Using property 2 we have:
((.y)DD [[x2]- x2j) = p.y = :/]
= -Paay)DD [ (2j) = p.y = 1/ (x22--1, = 7P)]
((a [xz))-1, )2,) = p. = 1/ (122//111 [p]] IP (m.))) h(#2)-1,22)) = 7p)
apll (a.))D(()) (1 7(p) y = v'l
4pp (x.)) 1) [2j (P).y v'l
And therefore:
E (x.))~D() ( pp}
Σ
y'P (ew)DD (22))11 = p. y']
v'El11)
4p
Σ
xp)) = s'1
( 1) [yl (p)H
Assuming (x( E (-1,1), 1), using the above we get:
20
p)
n b
EE
( pHl
Owly (1)
2 20 20
E
(aa))D ( = p]]
n4
2/201
E
[y| ( 12y) = pH
2//21 qp
(Z.W)~D | = 7p))
n
Now, we have the following cases:
13

---

Under review as a conference paper at ICLR 2020
If If-1. 0. then by property
2j and y independent,
Dop Ow!
2v 2014p
p)
E
(z.)) [z] 7(p)]]
n4
2v 22
((..))) [v] P ((..))D(-)) [zj = 7()]
E 20y
(x.))
[y] (z,))~D(-1) ((22)-1, = pl
n;
Since we assume 7(p) = sign(E [w]), and using the fact that (i,j.p) & Pe, we get that:
ÖL
aL
dmr (2) p) sign(EE (y))
Sur (2) p)
2v2
2v2 T4;
EE [B]
IP (2.))~D(-1) ([2]) = []]
Be
Otherwise, observe that:
2 201
p)
=
(2.))
[z] = 7()))
iw
2v 22197 E
1
y 55(25 7(p) 1)
(=()))((--1)
Thi
/20iqe
(5(p) + B(E,))DD-))) (y])
14.
And therefore, using property I since I;-1,5 # 0, we get:
V2gp
u sign(c-1s){
p)
(1oz-1.j + sign sign((i-1.)7((p)B by)
ow (1)
v 22 (l0z -
V2e ^
[v]])
n;
nle
where the fact that (i.j.D $ P..
We introduce the following notation: for a sample S C 2" x V, and some function f X" -> X", denote by f(S) the sample f(S) == ((((x), v))
Lemma 8. Fix Assume we sample S D. with |S| (A233) log 3. Then, with
128
probability at least for every {+132 such that (w)) (1) p)) 0 it holds that:
[Tw((s)
< e min A 233
p))
dwl() (t) .p)
Ow!
2/2n
14

---

Under review as a conference paper at ICLR 2020
Proof.
Fix some p {=1]² with (w/ .p)
Similar to what previously showed, get
that:
(L
p))
2
E B(a.)))((s))
( -y0:1(00(00) E (-1,1)) 1((1))) (#25-1, 2 0} (2)))
Owl)
2
E ((..)~~
( 1( p) |p]l]
71
2v2
E (m)))~((s)
1g E (-1, 1)} (((22)-1, = p)
n,
Denote f(x, v) = - you (12) E (-1 1,
p), and notice that
v( E [1, Now, from Hoeffding's inequality we get that:
1 - 15/
Pss [ss))) (f, v)1 - (D) (a vill 2 -] S exp
So. for |S| >
2
log 4 z we get that with probability at least 1 we have:
7
@ ( p)
2v2 n, Bv(s) [f v)] Bo(D) [f v)] 2v2
p)
Ow
Ow (t)
ng
Taking min { A, 2 and using the union bound over all p E {=1}² completes the proof.
Lemma 9. Fix > 0. Assume P(m.a)) [ Ee
8v2n. min min Assume we sample
log ..4 Then, with probubility at least - 6, for every p E {+1}² such that (i.j.p) o Pee, and for every I E [k] such that (w)" p) > and ge(p) 1), the following holds:
S~D, with |S| > 2² 128
(L) p) ow
-5p)ure
min A 28}
V2n,
Proof. Denote P(a.))D E J and denote B(i) Bw Then, we have the
following:
@L
QLv(D)
a v(x))
( ((PB))
(P
Ow!l" ()) Ow
dw
Ow
B(a
(PBO)
op ((()))))).a)()))
d (PB o v()))
1 x [x
Dwo (3)
dw
I B(a.D)DD
||
(z)
(()) 1 f xx
< 2/21 (a.))D
x &
2/22x
So get, using Lemma and Lemma with probability least 1 5:
(Lv(s)
OL Iw
(Lv(s)
OL
(L
Ow (t) .p) - aL
-ū(p)vis
p) -
.p) +
.p)
p) +
p)
Ow
Ow
ow
Ow
TT. Ow
aLo(s)
aLv(D)
ALv(D)
aTupes
2 (p))
.P)
p))
.p)
.p)
.))
dw
Ow (1)
Ow
Ow
/2c
OL
OLv(D)
min 2,3)
min ( 23}
|pll|
2/2n;
Ow
(2)
Ow
3e
min A, 233 4a
2V2n;
So for < 3/2n. A, 2,3} we get the required.
15

---

Under review as a conference paper at ICLR 2020
We want show that if the value of Sr gets "stuck", then it recovered the value of the gate, multiplied by the correlation G--1,-- We do this by observing the dynamics of (umf" .p). In most cases, its value moves in the right direction, except for small set that oscillates around zero. This set is the following:
A --<(DD) (L...P) PeA(()u < (w) P) S 4n ^ ( < <OV (1., (0.
We have the following simple observation:
Lemma 10. With the assumptions of Lemma A, S A4+1-
with probability at least 1 for every we have:
Proof. Fix some (l,p) E Ar, and we need to show that (urf
(2+1) (uv(++1) .P) S n,
(9) .p) - ther (wo)
(w) (f+1) P) (w)) .p) I 4y and we are done. (wo p) > then, since (t, P) $ P. we have
from Lemma 9 w.p at least 6:
(L iw) (t)
p) < (p))mu min A 23} < 0
22n
Where we the fact that {p))uvy 0. Therefore, we get:
(ww) 11-1) .p) = (ww .)) 1n( (lp(())
.p) S (10) (1) .p) S 4n
ow
Otherwise, we have (w,
(1) .p) < 0,
(10) (1+1) .p) = (ww n7
(1+1)
0L ow
p) S (10/)) ,p) + 4nj
4n
<
n
Now, we want to show that all (mo) (9) p) with (1,p) & A, and (i,j.P) $ P. move in the direction of 7(p) My:
Lemma 11. With the assumptions of Lemma with probability least 1 8, for every l,t and
p f+ such that (w(") ,p) > 0, (1. p) $ P. and (1,p) & A, it holds that:
(o((w)) (1) p))
a(w) (t-1) pi)) FD))vr 20
Proof. Assume the result of Lemma Phannaagholl holds (this happens with probability least 5). We cannot have (w)) (t-1) p) O, since otherwise we would have (w) .)) = O, contradicting the assumption.
(w) (1-1)
p)) O, since we require (wn (t) .p) > we get that:
o (ww (t) .p) - ((ww)( .p)) (ww) w (f-1) .p) = -11( [L
Ow (t-1) p)
and the required follows from Lemma following cases:
Otherwise, we have (wo(t-1), .). .p) < 0. We observe the
If (p))uz 2 0 then we are done, since:
(o((wu)) p)) a((nn' p))) = = p)) 7())m1 20
Foormalyy there is gradient, but we'll just take the auh-gradient zero.
16

---

Under review as a conference paper at ICLR 2020
Otherwise, we have 7(p)urz < 0. We also have:
(w)) 1 .p) (w! p) 7
QLv(s)
Ow (6) p)) S (w) (w .p)
4n 4n n;
-
n
Since we assume (L. p) & Ar. we must have (1.j. p) $ Pe and 7( P) Dlu 2 0. There- fore, from Lemma we get:
(L iw
p) < -5((-)) E min 23}
/2n
And hence:
< (w)) p) = (wm) (1-1) p) + n (Lv(S)
-p) S 1p((-p)ery min 2.3 < /2n;
Owl )rn((-1)"
and we reach contradiction.
From the above, we get the following:
Corollary 3. With the assumptions of Lemma with probability at least for every 1, and
p E {#1]² such that (w)(), .p) > O, (i,j.p) $ Pe and (1,p) & Av, the following holds:
(o((1))) (0) .p)) o ((w) (0) pi)) Kpp)wuy 2 0
Notice that for every l' < l we have (l,p) & Av S A.. Therefore, using the previous lemma:
Proof.
(o((w(() .p) a((w) (0) pi)) 7pp)mu
E (o((w))) .p)) ol(wi (6) .p)ppp)p)))))))))))) F(p)um) 2 0 ISPSt
Finally, we need to show that there are some "good" neurons, that are moving strictly away from zero:
Lemma 12. Fix 8 > 0. Assume P( x E Xee < 8v2n, min A, 25}. Assume we sample
S S~ D, with [S|
2 28 log 1. Assume that k log (1) log()) (). Then with probability
128
at least 25, for every p E [+1]2 such that (i,j.P) & Pe. there exists E [k] such that for every
t with (p) E (-1,1), we have:
a(ww)) ((w,)pp)) ,p) Kp))mr 2 nt min A 2,33
V2n,
Proof. Assume the result of Lemma 9 holds (happens with probability at least - 5). Fix some p E {=1]² such that (i,j.p) & P.. For [k], with probability we have both 1 (p)
and (w) (0) p) > 0. Therefore, the probability that there exists 1 [A]] such that the above holds is
1 3 2 1 - 4. Using the union bound, w.p at least 8, there exists such / E [k] for every
p 2 In such case, we have (w) pp) nt Ven. min 233, by induction:
For this true since (w) (0) p) > O.
If the above holds for 1, then (w0(--1) (1 .p) > 0, and therefore, using i = =ūp)v, and Lemma 9
17

---

Under review as a conference paper at ICLR 2020
(LV(D) Owl
pP) > {(p)urv; minf A, 28}
V2n,
And we get:
(w) p) (w(( .p) 1n( (Lv(D)
Ow (t) p))
(w((-1)), .p) + (p /2n:
[4i 233
2 n)(t 1) c min A, 23) +
min (A, 23}
V2n
v 22m
Using the above results, we can analyze the behavior of (:)::
Lemma 13. Assume
we initialize wi such that [
(0)
S
Fix
0. As-
4k"
sume P(a,))~ x E &e <<ven, min A, 2 av2n,
Assume we sample S
D, with |S|
>
23337 log J. Assume that k 2 log ((g(())))) Then with probability least 1 26,
128
for every p P {+1] such that (i, p) Pe. fort >
3m,
we have:
Vege min/
(p) =
Proof. Using Lemma every t with (p) 1,1):
w.p at least 26, for every such p there exists lp E [k] such that for
"r, ((w) 10 p)) 7(p)p; 2 nll V2n;
min 23}
Assume this holds, and fix some E {+1]2 with (1.j.) E P.. Let I, such that 9t-1 E (-1, Denote the set of indexes J = (w))
(t) .p) 0}. We have the following:
(c(p) Σ una(( (t) .p))
1 o (w p)) +
E vo((w(()p)) p)) +
Σ
nio((u{)) p))
From Corollary 3 we have:
7P)),
Σ
(oww .p)) 2 kow(1) (0) .p)) 2
By definition of A₁ and by our assumption on 17 we have:
7())2)-
Σ
vro((1) (0) .p)) (p)
2 -k 41
>
n4
Therefore, we get:
1
7()); ge(p) 1n 22n min A, 2,3)
2
This shows that for
22ee A,28) we get the required.
Proof. 6 Using the result of Lemma 13 with union bound over all choices of [n./2]. The required follows by the definition of ( x23) the definition of X.
Ni (1-15((2--00 101-1122---1 {2522)), and using
18

---

Under review as a conference paper at ICLR 2020
Proof. of Lemma 1 Fix some i [d].j [n4/2]. p E {=1}², y {=1), such that:
P ((ay))D( (1=j)
Assume w.l.o.g. that j Denote W the set of all possible choices for F3. .3..... En. such that when (2) = p. the resulting label y' Formally:
W = {133,..... In,)
Pi... (P,,1,, P2, 23,,,,..... = 1/}
Then we get:
DD) [(11, 12) p.y = 3/, / (=1,)(11 = x-1,
Pai (2) - p. (T3 Fn. E W, 1 (21, 1-11 (D)
PDD [2) = ( = N-1.)
PDD [e33.... In,) E W]
PDU [(11,2)) 22) ( (p)1) PDO (--1, x22) 1- (p), (I3. W]
PDi x2) (p -x-1)( DD [y v/ 78- 7- 18 70 1,5 (p))
And dividing by DI (111)(21, = 7--1 (p)) gives the required.
C PROOFS SECTION 5
Proof. of Lemma 2
For every gate (i,j), let Jı, be the subset of leaves in the binary tree whose root is the node (i,j). Namely, Ja.j == {(j - 1)2d-i + +,,..,,, Then we show inductively that for an input x E {+1}", the (i, gate outputs: Ilterns., 24:
For i = d 1, this is immediate from the definition of the gate 7d-1,j- 1,j
Assume the above is true for some and will show this for By definition of the circuit, the output of the (i 1,j) gate is product of the output of its inputs from the previous layers, the gates (i, 2ÿ 1), (i, 2j). By the inductive assumption, get that the output of the (i 1, gate is therefore:
II
II
zi
I
IEJ+.a 1n7
IEJi,a3N
LEJ; 1.5
From the above, the output of the target circuit is Ile 31 nler 21, required.
Proof. of Lemma 3
By definition we have:
C.j = (m (Ti+
= (a (())) = (( [ (()))))..))))))) ... 2s
Since require I # 0, then cannot have I ((411)...d ( So, from what showed previously, it follows that I ((44))...a))) Iy Fz for some @ I' I. Therefore, get that:
G. = ED
II
II JERV
En
II (2pr 1)
j'El'r
JEENP
Furthermore, we have that:
Ep [v] = Ep
II
ZT''
Ep [xy]
II JeEl
(2py 1)
jeel
jer
19

---

Under review as a conference paper at ICLR 2020
And using the assumption Pj get:
D
[ull
II S'EMNN
12p
II
12py 1
5'E(M]
[2.
1
1
II
12p 11
PERR
J'EI'
(1-(1-29))
12p 11
SER
(25)*~11 1 (1 (1 - 2()) 2 (2E)*
Now, for the second result, we have:
((x.)))P.... a(D) [zj = 1] E(
[(T (1+1)... 1}}
1
2 Izz + +1)
J'Er
II
(a
[zy] +
1
2
j'El'
And so get:
P (..)))....((D)) = =1]
II j'EI'
E B [xp]]]
2
< (1 28)
|l
-
2
Proof. of Lemma 4 For every E [d] and j E [2'], denote the following:
P IP (a.g) [zr 1ly 1), Pi,j P (aay))Din [xy = 1 -1]
Denote D( l the distribution (() conditioned on some fixed value z sampled from D(i-1), We
prove by induction on i that P.,, pr.j (2))
For i we have Pi,j and P..j 0, so the required holds.
Assume the claim is true for 1, and notice that we have for every 2 E {=1]]²-
IP (aa,)))DDo [Ir 1 TP (
[rg
1|2///2] 1] PP (=.0))D(i-n)
[2[5/2] 1ly 1
(.))))(()))
[x. = 1|2 -1] -P ((.N))D(
[ = = =
P.- P/-1,33/1
+ {1 p.-1.15/27)
if X--11//2] = A
2 3P1-1.11/2
i. 7 1/f/// = V
1P.
+ (1 p1-1.13/2))
i 7-111//2] -^
[(1 - -
if x-1.15/21 = -V
2 1p
if % 1.1// = ^
11-1.1/21 = V
1- 3P.1111/11
if %1-11///1 = =
2
if 76-1.19/21 = -V
3
20

---

Under review as a conference paper at ICLR 2020
Similarly, get that:
3P 1//2//1
if 1;-1,13/21 if 1/-1.11/21 V
3 3P1-1.10/21
P (a.y))D(o [z, 1ly -1]
- P111111//11
if 7/-1,13//21 =>
$P1-1.13/21
if 7/-1.11/21 -V
Therefore, we get:
2 1 Pigl
2
P. P/-1.13/21 -P-1.15/221
3
From this, we get:
((, [z
[(o.) (21 = 1} 1ull
() [1(2; 1}y] E [v]]
12 (TP Dio [rg =, 1] - -Paca [z) 1, y -1]) E [v]
22 (PTy.P 1P ly 1] Pī, d by ---1 1]) E [v]
( (ptts -PT,) + E(P + PT.))
E [y
2 | Pi.j
- 2 pt. + Po.j
E [v]
2
2 | Pa.
- 6E >
2 3
And hence:
1 //2" d
1
2 d
E ( [z,u]]
[+|
2
2
2
3
3
Proof. of Lemma 5 Fix some z' E n2 and s/ {+1). Then we have:
P ((.)))T,((()) [(.,v) = (=', P ((1)) [(T(()), (x)) v) (z',
((. [Vj
2/J and y y']
((E [(z,)) = (z',8')l
By the definitions of DD and ())
21


Reviews:
[{"review_id": "rJlPEXk3Yr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "Thank the authors for their rebuttal. It resolves all my previous concerns.\n##############################\n\nThis paper proposes to use neural networks for learning binary tree structured boolean circuits. For the boolean circuits problem, the authors notice two importance factors influencing why the target circuit is easy to learn or not. The two factors include \"local correlation\" and \"label bias\". On the one hand, \"local correlation\" requires every influential node in the circuit have strong correlations with the target label, which makes the network trainable to exploit this correlation for minimizing losses. On the other hand,  \"label bias\" requires that there are not the same amount of positive and negative examples. The paper proves that the proposed algorithm can faithfully learn the target circuit  and presents multiple examples for the scenario of learning binary tree structured boolean circuits.\n\nStrengths,\n1, This paper points out the two key factors \"local correlation\" and \"label bias\" for the learnability of a boolean circuit. Empirically in Figure1, they also validates the finding by demonstrating problems with balanced labels are more difficult to train.\n2, The paper puts their theoretical findings to the setup of k-parity problem, proving that their proposed algorithm can faithfully tackle the k-parity problem.\n\nWeakness,\n1, The main theorem proves that the target networks can be approximated using O(n^logn) examples. However, it it apparent that binary tree boolean circuits cannot represent all 2^n n-ary boolean functions. Actually, I GUESS all functions a binary tree can represent MIGHT also be in the scale of O(n^logn). Then the result is not surprising, as the training set probably covers all training examples. I think it is necessary that the authors give some estimates on the total number of representable functions and compare it with their |S|.\n2, It is not clear to me why the the \"label bias\" is important for learning a boolean circuit. Could the authors clarify to me ? \n3, It is also helpful to empirically compare the cases when there are local correlations and there aren't. \n4, Sec 5.1 shows that the proposed algorithm can solve the k-parity problem, however they assumed that all parity nodes locates together. In practice, these parity nodes might scatter everywhere, which could incur big problems for a binary-tree  to approximate.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SyeYAMQIKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "\nSummary: \nThe paper proposes a layer-wise method for training the weights of a binary-tree-structured neural network such that it correctly reproduces certain classes of Boolean functions defined by binary-tree-structured Boolean circuits. Specifically, this paper shows analytically that if a circuit satisfies a property termed “local correlation” where there is sufficient correlation between every gate in the circuit and the true output label of the circuit, then this circuit can be learned by a neural network with the same structure as the circuit by training it one layer at a time from the input to the output. The paper motivates this by showing empirically that the k-parity problem with some bias to the labels can be learned by a neural network, but that this does not work when there is no bias in the labels, implying that this bias is necessary for successful learning. The paper shows formally that instances of the k-parity problem satisfy the local correlation assumption and can thus be learned, and also shows that there exists at least one distribution given by a simple generative model that satisfies this assumption and is thus also learnable in this manner. \n\nOverall:\nWeak reject. My main concerns are as follows.\n\nFirst, if you define a circuit such that each gate’s output is correlated with the actual label, and then simply copy that structure and learn each gating function independently to predict the value that it is correlated with, then it seems likely that each additional gate should improve the representation. And because the network mimics exactly the circuit structure, the capacity of the network will not be a problem either. Thus, while it’s not trivial to say that the function can be recovered exactly, it is not exactly surprising either, and I don’t see what this offers in terms of novel intuition.\n\nSecond, the definitions and assumptions are not very reflective of what is actually done in deep learning, and I do not see a clear connection that would make this result useful in the field. It doesn’t connect well enough to actual datasets, problems, models, or learning algorithms that are used, so I do not see what insights can be taken from it.\n\nHowever, I do not have a problem with the quality of the paper, and think it would find a more appropriate audience at a different venue.\n\nClarity: The paper is quite well written and intelligible, although the notation is fairly dense and not always intuitive (e.g., numbering layers of the network from output to input).\nSignificance: I do not think the results are particularly significant.\n\nDetailed comments:\nSection 1.\n- The claims made in this section come off overly strong for the remainder of the paper. For example, training a deep neural network is not necessarily computationally hard because training is almost always taken to mean using SGD to locally minimize some loss function, and not taken to mean global optimization. This should be made more clear. Further, in my opinion, the “holy grail” of theoretical deep learning right now is the work on understanding why these networks generalize, not on global optimization or exact function learning (although there is some overlap between these two goals).\n- Can you better explain why correlation between the input bits and the label being necessary is not obviously necessary for all standard correlation-based learning methods? I agree that it would be nice if our methods were not so limited but this seems to simply reiterate the fact that they are. (e.g., I would not expect a deep network to learn on ImageNet if there was no correlation between some pixels and the output).\n- The ImageNet example is not particularly clear. First, the appendix implies you are taking center crops from each image, not random crops as stated in the intro. Second, I assume that you take a center crop per image, but the text is written to sound like only a single crop for all of ImageNet is used, which doesn’t make sense. \n- I do not think that the ImageNet experiment implies that local correlation exists in ImageNet any more than is already well known. It simply shows that an even smaller center crop from ImageNet images is still mildly predictive of the output classes; however, since ImageNet images are generally object-centered already, this is not particularly surprising.\n\nSection 2.\n- This is a well-written section that does a good job of situating this work.\n\nSection 3.\n- The assumption that the circuit must be a binary tree is quite restrictive and excludes pretty much all common deep learning architectures. Could this be relaxed empirically, even if not analytically?\n- In neural networks, it is common to define layer 1 as the input and layer d as the output, and it wasn’t immediately clear from the notation here that the opposite was being done here. Please make this more clear early on (or flip the ordering).\n- In the neural-gate definition, should v_i be v_l? Otherwise what is i indexing? Further, since v is not actually learned later, can it just be removed? This would simplify the notation somewhat.\n- How are v and w initialized?\n\nSection 4.\n- While it is strong to assume that every gate’s output should correlate with the label, it’s natural to think that many of each layer’s output in an actual neural network will correlate with the output, since earlier layers can be thought of as an input corresponding to a transformed representation of the actual input. This is also implied by the Belilovsky et al. layer-wise training work. Making these points more clearly and providing some empirical evidence could strengthen this paper’s claims. Perhaps measure the correlation between outputs in different layers and the labels?\n- Assumption 2 is at odds with the fact that datasets are typically designed to be as balanced as possible. Can you reconcile these?\n\nAppendix.\n- It would be nice if this read as well as the main paper.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1g4Qu4ctB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 aims to study the correlation between the neural network's input and output by abstracting the network as a binary tree Boolean circuit problem. The paper is well-written, motivations are clearly presented, and literature reviews are well placed. The contributions are mainly theoretical, and the experimental plots are simply used for concept illustrations, therefore the correctness of the theoretical analysis has no empirical evaluations. \n\nDue to the rareness of the study regarding deep learning theory, this manuscript makes one step further towards understanding the training hardness on a few certain types of neural networks with different underlying distributions. Multiple strong assumptions have made to favor the analysis, however, due to the lack of expertise, I can understand parts of the intuitions behinds them. To mimic the Boolean circuits network, the authors have focused the analysis on a layerwise gradient-based training, which might be a potential drawback because modern deep models are much more complex (e.g., the Residual network architecture shares connections between layers) and this over-simplified analysis may be too restricted. My understanding is that this paper could become a very solid work if a few rules of thumb or intuitions can be proposed to guide finding the correlation property in realistic neural network architectures such that we can verify these proposed theories with some experiments. \n\nOverall, I believe this is a fine theoretical foundation paper that should attract the attention of the researchers in deep learning community.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper puts forward a theoretical investigation of the learnability of                                                          
tree-structured Boolean circuits with neural networks.                                                                             
The authors identify *local correlations*, ie correlation of each internal                                                         
target circuit gate with the target output, as critical property for                                                               
characterizing learnability by layerwise training.                                                                                 
                                                                                                                                   
The reviewers agree that the paper is well written and content to be correct                                                       
(to the best of their knowledge).                                                                                                  
However, they have reservations about the strength of the assumptions about the                                                    
target functions as well as the layerwise training procedure.                                                                      
                                                                                                                                   
I think this paper is slightly below acceptance threshold for ICLR, which is a quite                                               
applied conference.                                                                                                                
The assumptions are quite strong, ie local correlations and the topology of the                                                    
circuit to be known as well as layerwise training, and possibly too far removed                                                    
from current deep learning practice.
Decision: Reject