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.
Summary: 
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. 
Overall:
Weak reject. My main concerns are as follows.
First, 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.
Second, 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.
However, 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.
Clarity: 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).
Significance: I do not think the results are particularly significant.
Detailed comments:
Section 1.
- 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).
- 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).
- 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. 
- 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.
Section 2.
- This is a well-written section that does a good job of situating this work.
Section 3.
- 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?
- 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).
- 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.
- How are v and w initialized?
Section 4.
- 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?
- Assumption 2 is at odds with the fact that datasets are typically designed to be as balanced as possible. Can you reconcile these?
Appendix.
- It would be nice if this read as well as the main paper.