Learning Boolean Circuits with Neural Networks
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.
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.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
Learning Boolean Circuits with Neural Networks
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.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



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