Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Thank the authors for their rebuttal. It resolves all my previous concerns.
##############################

This 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.

Strengths,
1, 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.
2, 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.

Weakness,
1, 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|.
2, It is not clear to me why the the "label bias" is important for learning a boolean circuit. Could the authors clarify to me ? 
3, It is also helpful to empirically compare the cases when there are local correlations and there aren't. 
4, 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.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 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. 

Due 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. 

Overall, I believe this is a fine theoretical foundation paper that should attract the attention of the researchers in deep learning community.
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: 
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.

review_title: Official Blind Review #2

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