Year: 2019

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.

heading: 1 INTRODUCTION AND MOTIVATION
text: It is well known (e.g. Livni et al. (2014)) that while deep neural-networks can express any function that can be run efficiently on a computer, in the general case, training them is computationally hard. Despite this theoretic pessimism, in practice, deep neural networks are successfully trained on real world datasets. Bridging this theoretical-practical gap seems to be the holy grail of theoretical 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 a property.
To motivate this, we first recall the k-parity problem: the input is n bits, there is a subset of k relevant bits (which are unknown to the learner), and the output should be 1 if the number of 1’s among the relevant bits is even and −1 otherwise. It is well known (e.g. Shalev-Shwartz et al. (2017)) that the parity problem can be expressed by a fully connected two layer network or by depth log(n) locally connected 1 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 is 12 ); 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 1, adding a slight bias to the probability of each bit dramatically affects the behavior of the network: while on the uniform distribution the training process completely fails, in the biased case it converges to a perfect solution.
This simple experiment shows that a small change in the underlying distribution can cause a dramatic change in the trainability of neural-networks. A key property that differentiates the uniform from the biased distribution is 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 a non-negligible 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 a promising property which separates easy and hard distributions.
In this paper, we analyze the problem of learning tree-structured Boolean circuits with neuralnetworks. The key property that we assume is having sufficient correlation between every gate in the circuit and the label. We show that a variant of gradient-descent can efficiently learn such
1i.e. every two adjacent neurons are only connected to one neuron in the upper layer.
circuits for some families of distributions, where at the same time, without correlation, gradientdescent 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, gradientdescent learns the (log n)-parity problem (parity on log n 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 of 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: we train a network with two hidden-layers on a single random patch from images in the ImageNet dataset. We observe that even on a complex task such as ImageNet, a network that gets only a 3×3 patch as 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 a local correlation property: even a few “bits” of the input already have some non-negligible information on the target label.

heading: 2 RELATED WORK
text: 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 neural-networks. Other works give different guarantees on various learning algorithms for neuralnetworks. In this section, we cover the main works that are relevant to our paper.
Failures of gradient-based algorithms. Various works have shown different examples demonstrating failures of gradient-based algorithm. The work of Shamir (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-descent fails to learn parities and linear-periodic functions under the uniform distribution. In Das et al. (2019), a hardness result for learning random deep networks is shown. Other similar failure cases are also covered in Abbe & Sandon (2018); Malach & Shalev-Shwartz (2019). While the details of these works differ, they all share the same key principal - if there is no local correlation, gradient-descent 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, a large number of papers have provided positive results on learning neural-networks with gradient-descent. Generally speaking, most of these works show that over-parametrized neural-networks, deep or 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 a wide enough neural-network. The work of Brutzkus et al. (2017) shows that SGD learns a neural-network with good generalization, when the target function is linear. A growing number of works show that for a specific kernel induced
by the network activation, called the Neural Tangent Kernel (NTK), gradient-descent learns overparametrized 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 et al. (2018a;b); Oymak & Soltanolkotabi (2019); Arora et al. (2019); Du et al. (2018); Ma et al. (2019); Lee et al. (2019)). While these results show that learning neural-networks with gradientdescent is not hopeless, they are in some sense disappointing — in practice, neural-networks achieve performance that are far better than SVM, a fact 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 a 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 gradientdescent — 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 a 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 & ShalevShwartz, 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 quasipolynomial time. Another work by Kalai (2018) 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 a 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, as 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 are not aware of any work studying a problem similar to ours.

heading: 3 PROBLEM SETTING
text: We consider the problem of learning binary classification functions over the Boolean cube. So, let X = {±1}n be the instance space and Y = {±1} be the label set. Throughout the paper, we assume the target function is given by a 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 a circuit C to be a directed graph with n input nodes and a single output node, where each inner node has exactly two incoming edges, and is labeled by some arbitrary Boolean function f : {±1}2 → {±1}, which we call a gate 2. For each node v in C we denote by γ(v) ∈ { f : {±1}2 → {±1} } its gate. We recursively define hv,C : {±1}n → {±1} to be:
hv,C(x) = γ(v) (hu1,C(x), hu2,C(x))
where u1, u2 are the two nodes with outcoming edges to v. Finally, define hC = ho,C , where o is the output node.
We study the problem of learning the target function hC , 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 x1, . . . xn. 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 k bits of the input (the function calculated by f(x) = ∏ i∈I xi for some set of indexes I). We note that the total number of functions calculated by such tree grows like 6n, as shown in Farhoodi et al. (2019). 2Note that in the literature on Boolean circuits it is often assumed that the gates are limited to being AND/OR and NOT. We allow the gates to take any Boolean function, which makes this model somewhat stronger.
We introduce a few notations that are used in the sequel. Fix some tree structured binary circuit C. This circuit has d levels, and we denote vi,j the j-th node in the i-th level of the tree, and denote γi,j = γ(vi,j). Fix some i ∈ [d], let ni := 2i, and denote by Γi : {±1}ni → {±1}ni/2 the function calculated by the i-th level of the circuit:
Γi(x) = ( γi−1,1(x1, x2), . . . , γi−1,ni/2(xni−1, xni) ) For i < i′, we denote: Γi...i′ := Γi ◦ · · · ◦ Γi′ . So, the full circuit is given by hC(x) = Γ1...d(x). 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 neural-gate: a one hidden-layer ReLU network, with a hard-tanh3 activation on its output. Formally, let σ be the ReLU activation, and let φ be the hard-tanh activation, so:
σ(x) = max(x, 0), φ(x) =  −1 x ≤ −1 x x ∈ (−1, 1) 1 x ≥ 1
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 gw,v : R2 → R such that:
gw,v(x) = φ( k∑ l=1 viσ(〈wl,x〉))
Notice that a neural-gate gw,v 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 d blocks, each block has neural-gates with the same structure and connectivity as the Boolean circuit. A block BW (i),V (i) : R2 i → R2i−1 , is defined by:
BW (i),V (i)(x) = [gw(i,1),v(i,1)(x1, x2), gw(i,2),v(i,2)(x3, x4), . . . , gw(i,2i−1),v(i,2i−1)(x2i−1, x2i)]
We consider the process of training neural-networks of the form NW,V = BW (1),V (1) ◦ · · · ◦ BW (d),V (d) . Notice that indeed, a network NW,V can implement any tree-structured Boolean circuit of depth d. In practice, neural-networks are trained with gradient-based optimization algorithm, in an 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 popular, it has been recently shown to achieve performance that are comparable to end-to-end training, scaling up to the ImageNet dataset (Belilovsky et al., 2018).
Denote by P the average-pooling operator, defined by P (x1, . . . , xn) = 1n ∑n i=1 xi. Denote the hinge-loss by `(ŷ, y) = max(1 − yŷ, 0) and denote the loss on the distribution by LD(f) = E(x,y)∼D [`(f(x), y)]. For a sample S ⊆ X × Y , denote the loss on the sample by LS(f) = 1 |S| ∑
(x,y)∈S `(f(x), y). The layerwise gradient-descent algorithm for learning deep networks is described in algorithm 1.
For simplicity, we assume that the second layer of every neural-gate is fixed, such that v ∈ {±1}. Notice that this does not limit the expressive power of the network. Algorithm 1 iteratively optimizes the output of the network’s layers, starting from the bottom-most layer. For each layer, the average-pooling operator is applied to reduce the output of the layer to a single bit, and this output is optimized with respect to the target label. Note that in fact, we can equivalently optimize each neural-gate separately and achieve the same algorithm. However, we present a layerwise training process to conform with algorithms used in practice.
3We chose to use the hard-tanh activation over the more popular tanh activation since it simplifies our theoretical analysis. However, we believe the same results can be given for the tanh activation.
Algorithm 1 Layerwise Gradient-Descent input:
Sample S ⊆ X × Y , number of iterations T ∈ N, learning rate η ∈ R. Let Nd ← id for i = d . . . 1 do
Initialize W (i)0 ,V (i)
0 . for t = 1 . . . T do
Update W (i)t ←W (i) t−1 − η ∂∂W (i)t−1 LS(P (BW (i)t−1,V (i) 0 ◦ Ni))
end for Update Ni−1 ← BW (i)T ,V (i)0 ◦ Ni
end for Return N0

heading: 4 MAIN RESULTS
text: Our main result shows that algorithm 1 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 ×Y . For some function f : X → X ′, we denote by f(D) the distribution of (f(x), y) where (x, y) ∼ D. Let D(i) be the distribution Γ(i+1)...d(D). Denote by ci,j the correlation between the output of the j-th gate in the i-th layer and the label, so: ci,j := ED(i) [xjy].
Define the influence of the j-th gate in the i-th layer with respect to the uniform distribution (U ) by: Ii,j := Px∼U [Γi−1(x) 6= Γi−1(x⊕ ej)] := Px∼U [Γi−1(x) 6= Γi−1(x1, . . . ,−xj , . . . , xn)]
Now, we introduce the main assumption on the distribution D. We assume the following: Assumption 1. (local correlation) There exists some ∆ ∈ (0, 1) such that for every layer i ∈ [d] and for every gate j ∈ [2i] with Ii,j 6= 0, the value of ci,j satisfies |ci,j | > |ED [y]|+ ∆.
Another technical assumption we need to make is the following: Assumption 2. (label bias) There exists some β ∈ (0, 1) such that |ED [y]| > β.
Before we present the main results, we wish to discuss the distributional assumptions given above. Assumption 1 is the key assumption required for the algorithm to succeed in learning the target function. 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 it only for influencing gates. While this is a strong assumption, in section 5 we discuss examples of distributions where this assumption typically holds. Furthermore, the experiment described in section 1 hints that this assumption may hold for natural data. Assumption 2 is a 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 6= j′, the variables xj and xj′ are independent, for (x, y) ∼ D. A simple argument shows that any product distribution D that satisfies assumptions 1, satisfies the following properties: Property 1. There exists some ∆ ∈ (0, 1) such that for every layer i ∈ [d] and for every gate j ∈ [2i], the output of the j-th gate in the i-th layer satisfies one of the following:
• The value of the gate j is independent of the label y, and its influence is zero: Ii,j = 0.
• The value of ci,j satisfies |ci,j | > |ED [y]|+ ∆. Property 2. For every layer i ∈ [d], and for every gate j ∈ [2i−1], the value of (x2j−1, x2j) (i.e, the input to the j-th gate of layer i− 1) is independent of the label y given the output of the j-th gate: P(x,y)∼D(i) [(x2j−1, x2j) = p, y = y′|γi−1,j(x2j−1, x2j)] = P(x,y)∼D(i) [(x2j−1, x2j) = p|γi−1,j(x2j−1, x2j)] · P(x,y)∼D(i) [y = y′|γi−1,j(x2j−1, x2j)]
Property 1 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 6= j′ we have that xj and xj′ are independent, for (x, y) ∼ D). Then D satisfies property 2.
Notice that properties 1, 2 may hold for distributions that are not product distribution (as we show in the next section). Specifically, property 2 is a 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 1 and 2, instead of assuming that D is a product distribution satisfying assumption 1. So, given a distribution satisfying properties 1, 2 and assumption 2, we show that algorithm 1 achieves an arbitrarily good approximation with high probability, with sample complexity and run-time quasipolynomial in the dimension n: Theorem 1. Let D be a distribution satisfying properties 1, 2 and assumption 2. Assume that for every i we initialize W (i)0 such that ∥∥∥W (i)0 ∥∥∥ max ≤ 1 4 √ 2k . Fix some , δ > 0 and assume that k ≥ log−1( 43 ) log( 2nd δ ), and that η ≤ 1 16k . Assume we sample S ∼ D, with |S| > 128 2 min{∆,2β}2n 11+4 logn−2 log min{∆,2β} log( 8ndδ ). Then, with probability at least 1− δ, when running algorithm 1 on the sample S, the algorithm returns the a function such that:
E(x,y)∼D [N0(x) 6= hC(x)] ≤
when running T > 3 √
2 ηmin{∆,2β} n 6.5+2 logn−log min{∆,2β} steps for each layer.
The above shows a learnability result in the standard PAC setting (given our distributional assumptions), 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 hC 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 ∈ (0, 1) such that for every layer i ∈ [d], for every gate j ∈ [2i−1] and for every p ∈ {±1}2 such that P(x,y)∼D(i) [(x2j−1, x2j) = p] 6= 0, it holds that: P(x,y)∼D(i) [(x2j−1, x2j) = p] ≥ .
In section 5 we discuss distributions that satisfies assumption 3. Given all the above assumptions, we get the following: Theorem 2. Let D be a distribution satisfying properties 1, 2 and assumptions 2, 3. Assume that for every i we initialize W (i)0 such that ∥∥∥W (i)0 ∥∥∥ max ≤ 1 4 √ 2k . Fix some δ > 0 and assume that k ≥ log−1( 43 ) log( 2nd δ ), and that η ≤ 1 16k . Assume we sample S ∼ D, with |S| > 128 2 min{∆,2β}2 log( 8nd δ ). Then, with probability at least 1 − δ, when running algorithm 1 on the sample S, the algorithm returns a function such that N0(x) = hC(x) for all x ∈ X , when running T > 3 √ 2n
ηmin{∆,2β} steps for each layer.
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, j)-th 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, 1), (1,−1)} get the value 1, and the pattern (−1,−1) gets the value −1. Fix some pattern p ∈ {±1}2, and assume that the output of the (i, j)-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 the gate. In the case where the output of the gate on p is −1, the output of the neural-gate is drawn 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-gate 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 no correlation, the above argument fails immediately. Since the label is slightly biased, when there is no correlation the output of the neural-gate 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
the target function (i.e. Ii,j = 0), then this clearly doesn’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 on all its input patterns. Hence, the algorithm will fail to learn the target function. This shows that assumption 1 is in fact critical for the success of the algorithm.

heading: 5 DISTRIBUTIONS
text: In the previous section we showed that algorithm 1 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 a parity function on log n bits of the input, when the underlying distribution is a product distribution. The problem of learning parities was studied extensively in the literature of machine learning theory (Feldman et al., 2006; 2009; Blum et al., 2003; ShalevShwartz et al., 2017; Brutzkus et al., 2019), and serves as a good case-study for the above results. In the (log n)-parity problem, we show that in fact most product distributions satisfy assumptions 1-3, hence our results apply to most product distributions. Next, we study distributions given by a generative model. We show that for every circuit with gates AND/OR and NOT, there exists a distribution that satisfies the above assumptions, so algorithm 1 can learn any such circuit exactly.

heading: 5.1 PRODUCT DISTRIBUTIONS
text: We observe the k-Parity problem, where the target function is f(x) = ∏ j∈I xj some subset I ⊆ [n] of size |I| = k. A simple construction shows that f can be implemented by a tree structured circuit as defined previously. We define the gates of the first layer by:
γd−1,j(z1, z2) =  z1z2 x2j−1, x2j ∈ I z1 x2j−1 ∈ I, x2j /∈ I z2 x2j ∈ I, x2j−1 /∈ I 1 o.w
And for all other layers i < d− 1, we define: γi,j(z1, z1) = z1z2. Then we get the following: Lemma 2. Let C be a Boolean circuit as defined above. Then: hC(x) = ∏ j∈I xj = f(x).
Now, let DX be some product distribution over X , and denote pj := PDX [xj = 1]. Let D be the distribution of (x, f(x)) where x ∼ DX . Then for the circuit defined above we get the following result: Lemma 3. Fix some ξ ∈ (0, 14 ). For every product distributionD with pj ∈ (ξ, 1 2−ξ)∪( 1 2 +ξ, 1−ξ) for every j, it holds that if Ii,j 6= 0 then |ci,j | − |E [y]| ≥ ξk and P(z,y)∼Γ(i+1)...d(D) [zj = 1] ∈ (ξ, 1− ξ).
The above lemma shows that every product distribution that is far enough from the uniform distribution, or from a constant distribution, satisfies assumptions 1 and 2 with β,∆ = (2ξ)k. 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 3 is satisfied with = ξ2. This gives us the following result: Corollary 1. Let D be a product distribution with pj ∈ (ξ, 12 − ξ) ∪ ( 1 2 + ξ, 1 − ξ) for every j, with the target function being the (log n)-Parity (i.e., k = log n). Then, when running algorithm 1 as described in Theorem 2, with probability 1− δ the algorithm returns the true target function hC , with run-time and sample complexity polynomial in n.

heading: 5.2 GENERATIVE MODELS
text: Next, we move beyond product distributions, and observe families of distributions given by a generative model. We limit ourselves to circuits where each gate is chosen from the set {∧,∨,¬∧,¬∨}. For every such circuit, we define a generative distribution as follows: we start by sampling a label
for the example, from a slightly imbalanced distribution (to satisfy assumption 2). Then iteratively, 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 1 and the topmost gate is OR, we sample a pattern uniformly from {(1, 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, we 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 Γ ∈ {∧,∨,¬∧,¬∨}, we denote the following sets of patterns: SΓ = {v ∈ {±1}2 : Γ(v1, v2) = 1}, ScΓ = {±1}2 \ SΓ We recursively define D(0), . . . ,D(d), where D(i) is a distribution over {±1}2i × {±1}:
• D(0) is a distribution supported on {(1, 1), (−1,−1)} such that PD(0) [(1, 1)] = 12 + ξ and PD(0) [(−1,−1)] = 12 − ξ, for some 0 < ξ < 1 12 ( 2 3 )d . • To sample (x, y) ∼ D(i), first sample (z, y) ∼ D(i−1). Then, for all j ∈ [2i−1], if zj = 1 sample x′j ∼ Uni(Sγi,j ), and if zj = −1 sample x′j ∼ Uni(Scγi,j ). Set x = [x′1, . . . ,x ′ 2i−1 ] ∈ {±1} 2i , and return (x, y).
Then we have the following results: Lemma 4. For every i ∈ [d] and every j ∈ [2i], denote ci,j = E(x,y)∼D(i) [xjy]. Then we have:
|ci,j | − |E [y]| > 1
3
( 2
3
)d = 1
3 nlog(2/3)
We also need the following simple observation: Lemma 5. For every i ∈ [d] we have Γi(D(i)) = D(i−1).
By definition, we have E [y] = 2ξ, so D(d) satisfies assumption 2 with β = ξ. Notice that from Lemma 4, the distribution D(d) satisfies property 1 with ∆ = 13n
log(2/3) (note that since we restrict the gates to AND/OR/NOT, all gates have influence). By its construction, the distribution also satisfies property 2, and it satisfies assumption 3 with = ( 1 4 )d = 1n2 . Therefore, we can apply Theorem 2 on the distribution D(d), and get that algorithm 1 learns the circuit C exactly in polynomial time. This leads to the following nice corollary: Corollary 2. With the assumptions and notations of Theorem 2, for every circuit C with gates in {∧,∨,¬∧,¬∨}, there exists a distribution D such that when running algorithm 1 on a sample from D, the algorithm returns hC 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 a distribution that is concentrated on a single positive example, and approximating the target function on such distribution is achieved by a classifier that always returns a positive prediction. However, showing that there exists a distribution on which algorithm 1 exactly recovers the circuit, is certainly non-trivial.

heading: 6 DISCUSSION
text: In this paper we suggested the property of local corrleation as a possible candidate for differentiating 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-descent to learn 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 an extremely interesting open problem. Needless to say, finding other properties of natural distribution that determine whether gradient-based algorithms succeed or fail is another promising research direction.

heading: A EXPERIMENTS
text: Figure 2 details the results of the ImageNet experiment discussed in the introduction.

heading: B PROOFS OF SECTION 4
text: We assume w.l.o.g that for every i, j such that Ii,j = 0, the (i, j) gate is constant γi,j ≡ sign(ED [y]). Since the output of this gate has no influence on the output y, we can choose it freely without changing the target function. To prove Theorem 1 and Theorem 2, we observe the behavior of the algorithm on the i-th layer. Let ψ : {±1}ni → {±1}ni be some mapping such that ψ(x) = (ξ1 ·x1, . . . , ξni ·xni) for ξ1, . . . , ξni ∈ {±1}. We also define ϕi : {±1}ni/2 → {±1}ni/2 such that:
ϕi(z) = (ν1z1, . . . , νni/2zni/2) where νj := {
sign(ci−1,j) ci−1,j 6= 0 1 Ii−1,j = 0
Fix some ′ > 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, j) gate that appear with probability at most ′. Denote the following set of triplets:
P̃ ′ := { (i, j,p) : P(x,y)∼D(i) [(x2j−1, x2j) = p] < ′ }
Denote the following set of “bad” examples: X̃ ′ := { x ∈ X : ∃(i, j,p) ∈ P̃ ′ s.t. (z2j−1, z2j) = p for z = Γ(i+1)...d(x) } We have the following important result, which we prove in the sequel:
Lemma 6. Fix > 0 and let ′ ≤ such that P(x,y)∼D [ x ∈ X̃ ′ ] <
8 √ 2ni min{∆, 2β}. Assume we initialize w(0)l such that ∥∥∥w(0)l ∥∥∥ ≤ 14k . Fix δ > 0. Assume we sample S ∼ D, with |S| >
128 2 min{∆,2β}2 log( 8ni δ ). Assume that k ≥ log −1( 43 ) log( 8ni δ ), and that η ≤ ni 16k . Let Ψ : X → [−1, 1]ni/2 such that for every x /∈ X̃ ′ we have Ψ(x) = ψ ◦ Γ(i+1)...d(x) for some ψ as defined above. Assume we perform the following updates:
W (i) t ←W (i) t−1 − η
∂
∂W (i) t−1
LS(P (BW (i)t−1,V (i) 0 ))
Then with probability at least 1−δ, for t > 3ni√ 2η min{∆,2β} we have: BW (i)t ,V (i)0 (x) = ϕi◦Γi◦ψ(x) for every x /∈ X̃ .
Given these results, we can prove the main theorems:
Proof. of Theorem 1 and Theorem 2. Fix δ′ = δd . Let 0 ≥ · · · ≥ d > 0 such that for every i ∈ [d] we have: P(x,y)∼D [ x ∈ X̃ i ] < i−1 min{∆,2β} 8 √ 2ni (we will note the exact value of i later). We show that for every i ∈ [d], w.p at least 1 − (d − i + 1)δ′, after the i-th step of the algorithm we have Ni−1(x) = ϕi ◦ Γi...d(x) for every x /∈ X̃ i−1 . By induction on i:
• For i = d, we get the required using Lemma 6 with ψ,Ψ = id and = d−1, ′ = d.
• Assume the above holds for i, and we show it for i − 1. By the assumption, w.p at least 1− (d− i+ 1)δ′ we have Ni−1(x) = ϕi ◦ Γi...d(x) for every x /∈ X̃ i−1 . Observe that:
∂LD
∂W (i−1) t
(P (B W
(i−1) t−1 ,V (i−1) 0
◦ Ni−1)) = ∂LNi−1(D)
∂W (i−1) t
(P (B W
(i−1) t ,V (i−1) 0
))
So using Lemma 6 with ψ = ϕi, Ψ = Ni and = i−2, ′ = i−1 we get that w.p at least 1 − δ′ we have B
W (i−1) T ,V (i−1) 0
(x) = ϕi−1 ◦ Γi−1 ◦ ϕi(x) for every x /∈ X̃ i−2 . In this
case, since ϕi ◦ ϕi = id, we get that for every x /∈ X̃ i−2 : Ni−2(x) = BW (i−1)T ,V (i−1)0 ◦ Ni−1(x) = (ϕi−1 ◦ Γi−1 ◦ ϕi) ◦ (ϕi ◦ Γi...d)(x) = ϕi−1 ◦ Γ(i−1)...d(x) and using the union bound gives the required.
Notice that ϕ1 = id: by definition of D(0) = Γ1...d(D), for (z, y) ∼ D(0) we have z = Γ1...d(x) and also y = Γ1...d(x) for (x, y) ∼ D. Therefore, we have c0,1 = E(x,y)∼D(0) [xy] = 1, and therefore ϕi(z) = sign(c0,1)z = z. Now, choosing i = 1, the above result shows that with probability at least 1 − δ, the algorithm returns N0 such that N0(x) = ϕ1 ◦ Γ1 ◦ · · · ◦ Γd(x) = hC(x) for every x /∈ X̃ 0 . To prove Theorem 2, it is enough to observe that when taking 0 = · · · = d = , assumption 3 implies that P̃ = ∅ and therefore X̃ = ∅, so the theorem follows. To prove Theorem 1, we take 0 = and inductively define i =
i−1 min{∆,2β} 32 √ 2n2 . Notice that ∣∣∣P̃ i∣∣∣ ≤ ∑i∈[d] ni2 ∣∣{±1}2∣∣ = 4 ∑logn i=0 2 i−1 = 4n. So, using the union bound we get:
P(x,y)∼D [ x ∈ X̃ i ] = P(x,y)∼D [ ∪(i,j,p)∈P̃ iΓ(i+1)...d(x)(2j−1,2j) = p ] ≤
∑ (i,j,p)∈P̃ i P(x,y)∼D [ Γ(i+1)...d(x)(2j−1,2j) = p ] ≤
∑ (i,j,p)∈P̃ i P(x,y)∼D(i) [(x2j−1, x2j) = p] < ∣∣∣P̃ ′ ∣∣∣ · i ≤ i−1∆ 8 √ 2ni
Now, observing that d = min{∆,2β}d 25.5dn2d = n log min{∆,2β} n5.5+2 logn gives the required.
In the rest of this section we prove Lemma 6. Fix some i ∈ [d] and let j ∈ [ni/2]. With slight abuse of notation, we denote by w(t) the value of the weight w(i,j) at iteration t, and denote v := v(i,j) and gt := gw(t),v . Recall that we defined ψ(x) = (ξ1 · x1, . . . , ξni · xni) for ξ1 . . . ξni ∈ {±1}. Denote D̃(i) := ψ(D(i)) the distribution of (ψ(x), y), where (x, y) ∼ D(i). Let γ := γi−1,j , and let γ̃ such that γ̃(x1, x2) = γ(ξ2j−1 ·x1, ξ2j ·x2). For every p ∈ {±1}2, denote p̃ := (ξ2j−1p1, ξ2jp2), so we have γ(p̃) = γ̃(p). Then we have the following:
Lemma 7. Fix some p ∈ {±1}2 such that (i, j, p̃) /∈ P̃ . For every l ∈ [k] such that 〈w(t)l ,p〉 > 0 and gt(p) ∈ (−1, 1), the following holds:
−γ̃(p)vlνj〈 ∂LD̃(i)
∂w (t) l
,p〉 > √ 2
ni min{∆, 2β}
Proof. Observe the following:
∂LD̃(i) ∂w (t) l (P (BW (i),V (i))) = E(x,y)∼D̃(i) `′(P (BW (i),V (i))(x)) · ∂ ∂w (t) l 2 ni ni/2∑ j′=1 gw(i,j′),v(i,j′)(x2j′−1, x2j′)  = 2
ni E(x,y)∼D̃(i)
[ −y ∂
∂w (t) l
gt(x2j−1, x2j)
]
= 2
ni E(x,y)∼D̃(i)
[ −yvl1{gt(x2j−1, x2j) ∈ (−1, 1)} · 1{〈w(t)l , (x2j−1, x2j)〉 > 0} · (x2j−1, x2j) ]
We use the fact that `′(P (BW (i),V (i))(x)) = −y, unless P (BW (i),V (i))(x) ∈ {±1}, in which case gt(x2j−1, x2j) ∈ {±1}, so ∂
∂w (t) l gt(x2j−1, x2j) = 0. Fix some p ∈ {±1}2 such that 〈w(t)l ,p〉 > 0. Note that for every p 6= p′ ∈ {±1}2 we have either 〈p,p′〉 = 0, or p = −p′ in which case 〈w(t)l ,p′〉 < 0. Therefore, we get the following:
〈 ∂LD̃(i)
∂w (t) l
,p〉 = 2 ni
E(x,y)∼D̃(i) [ −yvl1{gt(x2j−1, x2j) ∈ (−1, 1)} · 1{〈w(t)l , (x2j−1, x2j)〉 ≥ 0} · 〈(x2j−1, x2j),p〉 ] = 2
ni E(x,y)∼D̃(i) [−yvl1{gt(x2j−1, x2j) ∈ (−1, 1)} · 1{(x2j−1, x2j) = p} ‖p‖]
Denote qp := P(x,y)∼D(i) [(x2j−1, x2j) = p|γ(x2j−1, x2j) = γ(p)]. Using property 2, we have:
P(x,y)∼D(i) [(x2j−1, x2j) = p, y = y′] = P(x,y)∼D(i) [(x2j−1, x2j) = p, y = y′, γ(x2j−1, x2j) = γ(p)] = P(x,y)∼D(i) [(x2j−1, x2j) = p, y = y′|γ(x2j−1, x2j) = γ(p)]P(x,y)∼D(i) [γ(x2j−1, x2j) = γ(p)] = qpP(x,y)∼D(i) [γ(x2j−1, x2j) = γ(p), y = y′] = qpP(z,y)∼D(i−1) [zj = γ(p), y = y′]
And therefore: E(x,y)∼D(i) [y1{(x2j−1, x2j) = p}] = ∑
y′∈{±1}
y′P(x,y)∼D(i) [(x2j−1, x2j) = p, y = y′]
= qp ∑
y′∈{±1}
y′P(z,y)∼D(i−1) [zj = γ(p), y = y′]
= qpE(z,y)∼D(i−1) [y1{zj = γ(p)}]
Assuming gt(p) ∈ (−1, 1), using the above we get:
〈 ∂LD̃(i)
∂w (t) l
,p〉 = 2 √
2vl ni E(x,y)∼D̃(i) [−y1{(x2j−1, x2j) = p}]
= 2 √
2vl ni E(x,y)∼D(i) [−y1{(ξ2j−1x2j−1, ξ2jx2j) = p}]
= −2 √
2vl ni E(x,y)∼D(i) [y1{(x2j−1, x2j) = p̃}]
= − 2 √
2vlqp̃ ni E(z,y)∼D(i−1) [y1{zj = γ̃(p)}]
Now, we have the following cases:
• If Ii−1,j = 0, then by property 1 zj and y are independent, so:
〈 ∂LD̃(i)
∂w (t) l
,p〉 = − 2 √
2vlqp̃ ni E(z,y)∼D(i−1) [y1{zj = γ̃(p)}]
= − 2 √
2vlqp̃ ni E(z,y)∼D(i−1) [y]P(z,y)∼D(i−1) [zj = γ̃(p)]
= −2 √
2vl ni E(z,y)∼D(i−1) [y]P(z,y)∼D(i−1) [(x2j−1, x2j) = p̃]
Since we assume γ̃(p) = sign(E [y]), and using the fact that (i, j, p̃) /∈ P̃ , we get that:
−γ̃(p)vlνj〈 ∂LD̃(i)
∂w (t) l
,p〉 = − sign(E [y])vl〈 ∂LD̃(i)
∂w (t) l
,p〉
= 2 √ 2
ni |E [y]|P(z,y)∼D(i−1) [(x2j−1, x2j) = p̃] >
2 √ 2
ni β
• Otherwise, observe that:
〈 ∂LD̃(i)
∂w (t) l
,p〉 = − 2 √
2vlqp̃ ni E(z,y)∼D(i−1) [y1{zj = γ̃(p)}]
= − 2 √
2vlqp̃ ni
E(z,y)∼D(i−1) [ y 1
2 (zj · γ̃(p) + 1) ] = − √
2vlqp̃ ni
( γ̃(p)ci−1,j + E(z,y)∼D(i−1) [y] )
And therefore, using property 1, since Ii−1,j 6= 0, we get:
−γ̃(p)vl sign(ci−1,j)〈 ∂LD̃(i)
∂w (t) l
,p〉 = √
2qp̃ ni (|ci−1,j |+ sign(ci−1,j)γ̃(p)E [y])
≥ √
2qp̃ ni
(|ci−1,j | − |E [y]|) > √ 2
ni ∆
where we use the fact that (i, j, p̃) /∈ P̃ .
We introduce the following notation: for a sample S ⊆ X ′ × Y , and some function f : X ′ → X ′, denote by f(S) the sample f(S) := {(f(x), y)}(x,y)∈S .
Lemma 8. Fix δ > 0. Assume we sample S ∼ D, with |S| > 128 2 min{∆,2β}2 log 4 δ . Then, with probability at least 1− δ, for every p ∈ {±1}2 such that 〈w(t)l ,p〉 > 0 it holds that:∣∣∣∣∣〈∂LΨ(D)∂w(t)l ,p〉 − 〈 ∂LΨ(S) ∂w (t) l ,p〉 ∣∣∣∣∣ ≤ 2√2ni min{∆, 2β}
Proof. Fix some p ∈ {±1}2 with 〈w(t)l ,p〉 > 0. Similar to what we previously showed, we get that:
〈 ∂LΨ(S)
∂w (t) l
,p〉 = 2 ni
E(x,y)∼Ψ(S) [ −yvl1{gt(x2j−1, x2j) ∈ (−1, 1)} · 1{〈w(t)l , (x2j−1, x2j)〉 ≥ 0} · 〈(x2j−1, x2j),p〉 ] = 2
ni E(x,y)∼Ψ(S) [−yvl1{gt(x2j−1, x2j) ∈ (−1, 1)} · 1{(x2j−1, x2j) = p} ‖p‖]
= 2 √ 2
ni E(x,y)∼Ψ(S) [−yvl1{gt(x2j−1, x2j) ∈ (−1, 1)} · 1{(x2j−1, x2j) = p}]
Denote f(x, y) = −yvl1{gt(x2j−1, x2j) ∈ (−1, 1)} · 1{(x2j−1, x2j) = p}, and notice that f(x, y) ∈ [−1, 1]. Now, from Hoeffding’s inequality we get that:
PS [∣∣EΨ(S) [f(x, y)]− EΨ(D) [f(x, y)]∣∣ ≥ τ] ≤ exp(−1
2 |S|τ2 ) So, for |S| > 2τ2 log 4 δ we get that with probability at least 1−
δ 4 we have:∣∣∣∣∣〈∂LΨ(D)∂w(t)l ,p〉 − 〈 ∂LΨ(S) ∂w (t) l ,p〉 ∣∣∣∣∣ = 2 √ 2 ni ∣∣EΨ(S) [f(x, y)]− EΨ(D) [f(x, y)]∣∣ < 2√2 ni τ
Taking τ = 8 min{∆, 2β} and using the union bound over all p ∈ {±1} 2 completes the proof. Lemma 9. Fix δ > 0. Assume P(x,y)∼D [ x ∈ X̃ ′ ] <
8 √ 2ni min{∆, 2β}. Assume we sample
S ∼ D, with |S| > 128 2 min{∆,2β}2 log 4 δ . Then, with probability at least 1− δ, for every p ∈ {±1} 2 such that (i, j, p̃) /∈ P̃ ′ , and for every l ∈ [k] such that 〈w(t)l ,p〉 > 0 and gt(p) ∈ (−1, 1), the following holds:
−γ̃(p)vlνj〈 ∂LΨ(D)
∂w (t) l
,p〉 > √ 2ni min{∆, 2β}
Proof. Denote α := P(x,y)∼D [ x ∈ X̃ ′ ] , and denote B(i) := BW (i),V (i) . Then, we have the following:∥∥∥∥∥∂LD̃(i)∂w(t)l − ∂LΨ(D) ∂w (t) l ∥∥∥∥∥ = ∥∥∥∥∥E(x,y)∼D [ ∂ ∂w (t) l `(PB(i) ◦ ψ ◦ Γ(i+1)...d(x))− ∂ ∂w (t) l `(PB(i) ◦Ψ(x))
]∥∥∥∥∥ ≤ E(x,y)∼D
[∥∥∥∥∥ ∂∂w(t)l `(PB(i) ◦ ψ ◦ Γ(i+1)...d(x))− ∂ ∂w (t) l `(PB(i) ◦Ψ(x)) ∥∥∥∥∥ · 1{x ∈ X̃ ′} ]
≤ E(x,y)∼D [∥∥ψ ◦ Γ(i+1)...d(x)(2j−1,2j) −Ψ(x)(2j−1,2j)∥∥ · 1{x ∈ X̃ ′}] ≤ 2 √ 2P(x,y)∼D [ x ∈ X̃ ′ ] = 2 √ 2α
So we get, using Lemma 7 and Lemma 8, with probability at least 1− δ:
−γ̃(p)vlνj〈 ∂LΨ(S)
∂w (t) l
,p〉 = −γ̃(p)vlνj ( 〈 ∂LD̃(i)
∂w (t) l
,p〉+ 〈 ∂LΨ(S)
∂w (t) l
,p〉 − 〈 ∂LΨ(D)
∂w (t) l
,p〉+ 〈 ∂LΨ(D)
∂w (t) l
,p〉 − 〈 ∂LD̃(i)
∂w (t) l
,p〉
)
≥ −γ̃(p)vlνj〈 ∂LD̃(i)
∂w (t) l
,p〉 − ∣∣∣∣∣〈∂LΨ(S)∂w(t)l ,p〉 − 〈 ∂LΨ(D) ∂w (t) l ,p〉 ∣∣∣∣∣− ∣∣∣∣∣〈∂LΨ(D)∂w(t)l ,p〉 − 〈 ∂LD̃(i) ∂w (t) l ,p〉 ∣∣∣∣∣ > √ 2
ni min{∆, 2β} − 2 √ 2ni min{∆, 2β} − ∥∥∥∥∥∂LD̃(i)∂w(t)l − ∂LΨ(D) ∂w (t) l ∥∥∥∥∥ ‖p‖ ≥ 3
2 √ 2ni min{∆, 2β} − 4α
So for α < 8 √ 2ni min{∆, 2β} we get the required.
We want to show that if the value of gt gets “stuck”, then it recovered the value of the gate, multiplied by the correlation ci−1,j . We do this by observing the dynamics of 〈w(t)l ,p〉. In most cases, its value moves in the right direction, except for a small set that oscillates around zero. This set is the following:
At = { (l,p) : (i, j, p̃) /∈ P̃ ∧ γ̃(p)vlνj < 0 ∧ 〈w(t)l ,p〉 ≤ 4η ni ∧ ( γ̃(−p)vlνj < 0 ∨ (i, j,−p̃) ∈ P̃ )} We have the following simple observation:
Lemma 10. With the assumptions of Lemma 9, with probability at least 1− δ, for every t we have: At ⊆ At+1.
Proof. Fix some (l,p) ∈ At, and we need to show that 〈w(t+1)l ,p〉 ≤ 4η ni . If 〈w(t)l ,p〉 = 0 then4 〈w(t+1)l ,p〉 = 〈w (t) l ,p〉 ≤ 4η ni
and we are done. If 〈w(t)l ,p〉 > 0 then, since (i, j, p̃) /∈ P̃ we have from Lemma 9, w.p at least 1− δ:
−〈 ∂LΨ(S)
∂w (t) l
,p〉 < γ̃(p)vlνj √ 2ni min{∆, 2β} < 0
Where we use the fact that γ̃(p)vlνj < 0. Therefore, we get:
〈w(t+1)l ,p〉 = 〈w (t) l ,p〉 − η〈
∂LΨ(S)
∂w (t) l
,p〉 ≤ 〈w(t)l ,p〉 ≤ 4η
ni
Otherwise, we have 〈w(t)l ,p〉 < 0, so:
〈w(t+1)l ,p〉 = 〈w (t) l ,p〉 − η〈
∂LΨ(S)
∂w (t) l
,p〉 ≤ 〈w(t)l ,p〉+ 4η ni ≤ 4η ni
Now, we want to show that all 〈w(t)l ,p〉 with (l,p) /∈ At and (i, j, p̃) /∈ P̃ move in the direction of γ̃(p) · νj : Lemma 11. With the assumptions of Lemma 9, with probability at least 1 − δ, for every l,t and p ∈ {±1}2 such that 〈w(t)l ,p〉 > 0, (i, j, p̃) /∈ P̃ and (l,p) /∈ At, it holds that:(
σ(〈w(t)l ,p〉)− σ(〈w (t−1) l ,p〉) ) · γ̃(p)vlνj ≥ 0
Proof. Assume the result of Lemma 9 holds (this happens with probability at least 1−δ). We cannot have 〈w(t−1)l ,p〉 = 0, since otherwise we would have 〈w (t) l ,p〉 = 0, contradicting the assumption. If 〈w(t−1)l ,p〉 > 0, since we require 〈w (t) l ,p〉 > 0 we get that:
σ(〈w(t)l ,p〉)− σ(〈w (t−1) l ,p〉) = 〈w (t) l −w (t−1) l ,p〉 = −η〈
∂LΨ(S) ∂w (t−1) l ,p〉
and the required follows from Lemma 9. Otherwise, we have 〈w(t−1)l ,p〉 < 0. We observe the following cases:
• If γ̃(p)vlνj ≥ 0 then we are done, since:( σ(〈w(t)l ,p〉)− σ(〈w (t−1) l ,p〉) ) · γ̃(p)νj = σ(〈w(t)l ,p〉) · γ̃(p)vlνj ≥ 0
4Formally, there is no gradient, but we’ll just take the sub-gradient zero.
• Otherwise, we have γ̃(p)vlνj < 0. We also have:
〈w(t)l ,p〉 = 〈w (t−1) l ,p〉 − η〈
∂LΨ(S)
∂w (t) l
,p〉 ≤ 〈w(t−1)l ,p〉+ 4η ni ≤ 4η ni
Since we assume (l,p) /∈ At, we must have (i, j,−p̃) /∈ P̃ and γ̃(−p)vlνj ≥ 0. Therefore, from Lemma 9 we get:
〈 ∂LΨ(S)
∂w (t) l
,−p〉 < −γ̃(−p)vlνj √ 2ni min{∆, 2β}
And hence:
0 < 〈w(t)l ,p〉 = 〈w (t−1) l ,p〉+ η〈
∂LΨ(S) ∂w (t−1) l ,−p〉 ≤ −ηγ̃(−p)vlνj √ 2ni min{∆, 2β} < 0
and we reach a contradiction.
From the above, we get the following:
Corollary 3. With the assumptions of Lemma 9, with probability at least 1 − δ, for every l,t and p ∈ {±1}2 such that 〈w(t)l ,p〉 > 0, (i, j, p̃) /∈ P̃ and (l,p) /∈ At, the following holds:(
σ(〈w(t)l ,p〉)− σ(〈w (0) l ,p〉) ) · γ̃(p)vlνj ≥ 0
Proof. Notice that for every t′ ≤ t we have (l,p) /∈ At′ ⊆ At. Therefore, using the previous lemma:( σ(〈w(t)l ,p〉)− σ(〈w (0) l ,p〉) ) · γ̃(p)vlνj =
∑ 1≤t′≤t ( σ(〈w(t)l ,p〉)− σ(〈w (t′) l ,p〉) ) · γ̃(p)vlνj ≥ 0
Finally, we need to show that there are some “good” neurons, that are moving strictly away from zero:
Lemma 12. Fix δ > 0. Assume P(x,y)∼D [ x ∈ X̃ ′ ] <
8 √ 2ni min{∆, 2β}. Assume we sample
S ∼ D, with |S| > 128 2 min{∆,2β}2 log 4 δ . Assume that k ≥ log −1( 43 ) log( 4 δ ). Then with probability at least 1− 2δ, for every p ∈ {±1}2 such that (i, j, p̃) /∈ P̃ , there exists l ∈ [k] such that for every t with gt−1(p) ∈ (−1, 1), we have:
σ(〈w(t)l ,p〉) · γ̃(p)vlνj ≥ ηt √ 2ni min{∆, 2β}
Proof. Assume the result of Lemma 9 holds (happens with probability at least 1 − δ). Fix some p ∈ {±1}2 such that (i, j, p̃) /∈ P̃ . For l ∈ [k], with probability 14 we have both vl = γ̃(p)νj and 〈w(0)l ,p〉 > 0. Therefore, the probability that there exists l ∈ [k] such that the above holds is 1 − ( 34 )
k ≥ 1 − δ4 . Using the union bound, w.p at least 1 − δ, there exists such l ∈ [k] for every p ∈ {±1}2. In such case, we have 〈w(t)l ,p〉 ≥ ηt
√ 2ni min{∆, 2β}, by induction:
• For t = 0 this is true since 〈w(0)l ,p〉 > 0.
• If the above holds for t − 1, then 〈w(t−1)l ,p〉 > 0, and therefore, using vl = γ̃(p)νj and Lemma 9:
−〈 ∂LΨ(D)
∂w (t) l
,p〉 > γ̃(p)vlνj √ 2ni min{∆, 2β}
And we get:
〈w(t)l ,p〉 = 〈w (t−1) l ,p〉 − η〈
∂LΨ(D)
∂w (t) l
,p〉
> 〈w(t−1)l ,p〉+ ηγ̃(p)vlνj √ 2ni min{∆, 2β}
≥ η(t− 1) √ 2ni min{∆, 2β}+ η √ 2ni min{∆, 2β}
Using the above results, we can analyze the behavior of gt(p): Lemma 13. Assume we initialize w(0)l such that ∥∥∥w(0)l ∥∥∥ ≤ 14k . Fix δ > 0. As-
sume P(x,y)∼D [ x ∈ X̃ ′ ] <
8 √ 2ni min{∆, 2β}. Assume we sample S ∼ D, with |S| >
128 2 min{∆,2β}2 log 4 δ . Assume that k ≥ log −1( 43 ) log( 4 δ ). Then with probability at least 1 − 2δ,
for every p ∈ {±1}2 such that (i, j, p̃) /∈ P̃ , for t > 3ni√2η min{∆,2β} we have:
gt(p) = γ̃(p)νj
Proof. Using Lemma 12, w.p at least 1 − 2δ, for every such p there exists lp ∈ [k] such that for every t with gt−1(p) ∈ (−1, 1):
vlpσ(〈w (t) lp ,p〉) · γ̃(p)νj ≥ ηt √ 2ni min{∆, 2β}
Assume this holds, and fix some p ∈ {±1}2 with (i, j, p̃) /∈ P̃ . Let t, such that gt−1(p) ∈ (−1, 1). Denote the set of indexes J = {l : 〈w(t)l ,p〉 > 0}. We have the following:
gt(p) = ∑ l∈J vlσ(〈w(t)l ,p〉)
= vlpσ(〈w (t) lp ,p〉) + ∑ l∈J\{lp},(l,p)/∈At vlσ(〈w(t)l ,p〉) + ∑ l∈J\{lp},(l,p)∈At vlσ(〈w(t)l ,p〉)
From Corollary 3 we have: γ̃(p)νj · ∑
l∈J\{lp},(l,p)/∈At
vlσ(〈w(t)l ,p〉) ≥ −kσ(〈w (0) l ,p〉) ≥ −
1
4
By definition of At and by our assumption on η we have: γ̃(p)νj · ∑
l∈J\{lp},(l,p)∈At
vlσ(〈w(t)l ,p〉) ≥ −k 4η ni ≥ −1 4
Therefore, we get:
γ̃(p)νj · gt(p) ≥ ηt √ 2ni min{∆, 2β} − 1 2
This shows that for t > 3ni√ 2η min{∆,2β} we get the required.
Proof. of Lemma 6. Using the result of Lemma 13, with union bound over all choices of j ∈ [ni/2]. The required follows by the definition of γ̃(x2j−1, x2j) = γi−1,j(ξ2j−1x2j−1, ξ2jx2j), and using the definition of X̃
Proof. of Lemma 1. Fix some i ∈ [d], j ∈ [ni/2],p ∈ {±1}2, y′ ∈ {±1}, such that:
P(x,y)∼D(i) [γi−1,j(x2j−1, x2j) = γi−1,j(p)] > 0
Assume w.l.o.g. that j = 1. Denote by W the set of all possible choices for x3, . . . , xni , such that when (x1, x2) = p, the resulting label is y′. Formally:
W := {(x3, . . . , xni) : Γi...d(p1, p2, x3, . . . , xni) = y′}
Then we get:
PD(i) [(x1, x2) = p, y = y′, γi−1,j(x1, x2) = γi−1,j(p)] = PD(i) [(x1, x2) = p, (x3, . . . , xni) ∈W,γi−1,j(x1, x2) = γi−1,j(p)] = PD(i) [(x1, x2) = p, γi−1,j(x1, x2) = γi−1,j(p)] · PD(i) [(x3, . . . , xni) ∈W ] = PD(i) [(x1, x2) = p|γi−1,j(x1, x2) = γi−1,j(p)] · PD(i) [γi−1,j(x1, x2) = γi−1,j(p), (x3, . . . , xni) ∈W ] = PD(i) [(x1, x2) = p|γi−1,j(x1, x2) = γi−1,j(p)] · PD(i) [y = y′, γi−1,j(x1, x2) = γi−1,j(p)]
And dividing by PD(i) [γi−1,j(x1, x2) = γi−1,j(p)] gives the required.

heading: C PROOFS OF SECTION 5
text: Proof. of Lemma 2.
For every gate (i, j), let Ji,j be the subset of leaves in the binary tree whose root is the node (i, j). Namely, Ji,j := {(j − 1)2d−i + 1, . . . , j2d−i}. Then we show inductively that for an input x ∈ {±1}n, the (i, j) gate outputs: ∏ l∈I∩Ji,j xl:
• For i = d− 1, this is immediate from the definition of the gate γd−1,j .
• Assume the above is true for some i and we will show this for i − 1. By definition of the circuit, the output of the (i − 1, j) gate is a product of the output of its inputs from the previous layers, the gates (i, 2j − 1), (i, 2j). By the inductive assumption, we get that the output of the (i− 1, j) gate is therefore: ∏
l∈Ji,2j−1∩I
xl  ·  ∏ l∈Ji,2j∩I xl  = ∏ l∈(Ji,j2−1∪Ji,2j)∩I xl = ∏ l∈Ji−1,j xl
From the above, the output of the target circuit is ∏ l∈J0,1∩I xl = ∏ l∈I xl, as required.
Proof. of Lemma 3.
By definition we have: ci,j = E(x,y)∼D [ Γ(i+1)...d(x)jy ] = E(x,y)∼D [ Γ(i+1)...d(x)jy ] = E(x,y)∼D [ Γ(i+1)...d(x)jx1 · · ·xk ] Since we require Ii,j 6= 0, then we cannot have Γ(i+1)...d(x)j ≡ 1. So, from what we showed previously, it follows that Γ(i+1)...d(x)j = ∏ j′∈I′ xj′ for some ∅ 6= I ′ ⊆ I . Therefore, we get that:
ci,j = ED  ∏ j′∈I\I′ xj′  = ∏ j′∈I\I′ ED [xj′ ] = ∏ j′∈I\I′ (2pj′ − 1)
Furthermore, we have that:
ED [y] = ED ∏ j′∈I xj′  = ∏ j′∈I ED [xj′ ] = ∏ j′∈I (2pj′ − 1)
And using the assumption on pj we get: |ci,j | − |ED [y]| = ∏
j′∈[k]\I′ |2pj′ − 1| − ∏ j′∈[k] |2pj′ − 1|
=  ∏ j′∈[k]\I′ |2pj′ − 1| 1− ∏ j′∈I′ |2pj′ − 1|  ≥
 ∏ j′∈[k]\I′ |2pj′ − 1| (1− (1− 2ξ)|I′|) ≥ (2ξ)k−|I ′| (1− (1− 2ξ)) ≥ (2ξ)k
Now, for the second result, we have: P(z,y)∼Γi...d(D) [zj = 1] = E(x,y)∼D [ 1{Γ(i+1)...d(x)j = 1} ] = E(x,y)∼D 1 2 ( ∏ j′∈I′ xj′ + 1)
 = 1
2 ∏ j′∈I′ E(x,y)∼D [xj′ ] + 1 2
And so we get: ∣∣∣∣P(z,y)∼Γi...d(D) [zj = 1]− 12 ∣∣∣∣ = 12 ∏
j′∈I′ ∣∣E(x,y)∼D [xj′ ]∣∣ < 1
2 (1− 2ξ)|I ′| ≤ 1 2 − ξ
Proof. of Lemma 4 For every i ∈ [d] and j ∈ [2i], denote the following:
p+i,j = P(x,y)∼D(i) [xj = 1|y = 1] , p − i,j = P(x,y)∼D(i) [xj = 1|y = −1]
Denote D(i)|z the distribution D(i) conditioned on some fixed value z sampled from D(i−1). We prove by induction on i that |p+i,j − p − i,j | = ( 2 3 )i :
• For i = 0 we have p+i,j = 1 and p − i,j = 0, so the required holds.
• Assume the claim is true for i− 1, and notice that we have for every z ∈ {±1}2i−1 : P(x,y)∼D(i) [xj = 1|y = 1] = P(x,y)∼D(i)|z [ xj = 1|zdj/2e = 1 ] · P(z,y)∼D(i−1) [ zdj/2e = 1|y = 1 ] + P(x,y)∼D(i)|z [ xj = 1|zdj/2e = −1 ] · P(z,y)∼D(i−1) [ zdj/2e = −1|y = 1 ]
=  p+i−1,dj/2e + 1 3 (1− p + i−1,dj/2e) if γi−1,dj/2e = ∧ 2 3p + i−1,dj/2e if γi−1,dj/2e = ∨ 1 3p + i−1,dj/2e + (1− p + i−1,dj/2e) if γi−1,dj/2e = ¬∧
2 3 (1− p + i−1,dj/2e) if γi−1,dj/2e = ¬∨
=  2 3p + i−1,dj/2e − 1 3 if γi−1,dj/2e = ∧ 2 3p + i−1,dj/2e if γi−1,dj/2e = ∨ 1− 23p + i−1,dj/2e if γi−1,dj/2e = ¬∧
2 3 − 2 3p + i−1,dj/2e if γi−1,dj/2e = ¬∨
Similarly, we get that:
P(x,y)∼D(i) [xj = 1|y = −1] =  2 3p − i−1,dj/2e − 1 3 if γi−1,dj/2e = ∧ 2 3p − i−1,dj/2e if γi−1,dj/2e = ∨ 1− 23p − i−1,dj/2e if γi−1,dj/2e = ¬∧
2 3 − 2 3p − i−1,dj/2e if γi−1,dj/2e = ¬∨
Therefore, we get:
|p+i,j − p − i,j | =
2 3 |p+i−1,dj/2e − p − i−1,dj/2e| =
( 2
3 )i From this, we get:∣∣E(x,y)∼D(i) [xjy]∣∣ = ∣∣E(x,y)∼D(i) [(21{xj = 1} − 1)y]∣∣
= ∣∣2E(x,y)∼D(i) [1{xj = 1}y]− E [y]∣∣ = |2 (PD(i) [xj = 1, y = 1]− PD(i) [xj = 1, y = −1])− E [y]| = ∣∣2 (p+i,jP [y = 1]− p−i,jP [y = −1])− E [y]∣∣
= ∣∣∣∣2(12(p+i,j − p−i,j) + ξ(p+i,j + p−i,j) ) − E [y] ∣∣∣∣ ≥ ∣∣p+i,j − p−i,j∣∣− 2ξ ∣∣p+i,j + p−i,j∣∣− |E [y]|
≥ ∣∣p+i,j − p−i,j∣∣− 6ξ > 12
( 2
3 )d And hence: ∣∣E(x,y)∼D(i) [xjy]∣∣− ∣∣E(x,y)∼D(i) [y]∣∣ ≥ 12 ( 2 3 )d − 2ξ > 1 3 ( 2 3 )d
Proof. of Lemma 5 Fix some z′ ∈ {±1}ni/2 and y′ ∈ {±1}. Then we have:
P(x,y)∼Γi(D(i)) [(x, y) = (z ′, y′)] = P(x,y)∼D(i) [(Γi(x), y) = (z′, y′)] = P(x,y)∼D(i) [ ∀j γi−1,j(x2j−1, x2j) = z′j and y = y′ ] = P(z,y)∼D(i−1) [(z, y) = (z′, y′)]
By the definitions of D(i) and D(i−1).

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

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.