Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper considers learning Boolean functions represented by read-once DNFs by using neural networks. The neural network architecture consists of a hidden layer with 2^D components, which is rich enough to express any Boolean functions. Given a whole 2^D instances of some read-once DNF, the authors showed that (1) weights corresponds to the true DNF is the global minimum of the loss minimization problem with the network, (2) they empirically observe that gradient descent with a rounding heuristics finds the true DNF expression, and(3) the solution of a 2-norm minimization recovers the true DNF.

The assumption that the whole set of instances of the true read-once DNF is given is too strong. It would be much nicer, given a partial set of instances S \subset X, one can learn a consistent DNF by using neural networks. Then, previous PAC learning results of read-once DNFs could be applied to obtain sample complexity results. 

I don’t think the “computer-aided proof” is really a proof. So, I am afraid that it should not be stated as a theorem. 

As a summary, I feel that the technical results are still preliminary and not mature enough to be published.  

review_title: The idea is interesting, but the results are preliminary.

final_score: rating: 7: Good paper, accept
review_content: In this paper the aim in to understand the inductive bias of neural networks learning DNFs. The focus is in convex neural networks and gradient descent. It is shown that under a symmetric initialization, the global minimum that gradient descent converges to is similar to a DNF-recovery solution. Further, experimental evaluation demonstrates that gradient descent can recover read-once DNFs from data. 

Learning functions over Boolean variables is a fundamental problem and there have been an increasing interest towards using neural networks for this task. This paper sheds light to this task in a very specific case. I am not an expert on the area of the paper, and hence cannot fully assess the novelty and impact of the work. However, I found the development in the paper concise and enough details are provided for even a non-expert to follow the presentation. The restriction to read-once DNFs seems rather severe. However, I found the analysis of the inductive bias of gradient decent towards logical formulas interesting. 


Pros:
1. Provides understanding of the inductive bias of convex neural networks using gradient descent
2. Computer assisted proof and experiments are used to complement theoretical results
3. Clearly and concisely written paper, a significant amount of supplementary material to  make a more detailed treatment available for those interested

Cons:
1. Results cover read-once DNFs which is very restricted class of DNFs, which might limit the impact of the results
2. Without access to code, it's impossible to assess the correctness and quality of the computer assisted proof


Questions:

It's quite unclear what is happening in Figure 2, could you add some more explanations?

Will the code related to computer assisted proof and the other experiments be made publicly available?

Minor comments: 

Remark 3.1: "Boolean" not "boolean"

There are couple of references "We use a unique property of our setting that allows us to perform calculations in integers and avoid floating point errors." (intro, start of Sec. 6) where it is unclear what this property is. This is finally explained before Def. 6.3. It could be better to explain this in short in the earlier mentions, because in their current format they do not really help the reader, but rather make them wonder what is this property.

KKT in page 7 not defined 
review_title: Learning read-once DFNs using a convex neural network and gradient descent

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper investigates the problem of learning monotone read-once DNF formulas using convex neural networks. Specifically, the authors explore the distribution-specific PAC setting, where training samples are drawn independently according to the uniform distributions and are labeled according to a target monotone read-once DNF. The main contribution of this study is essentially empirical: convex neural nets, trained with GD for minimizing the cumulative hinge loss, converge to global minima for which neural units coincide with the monomials of the target DNF. This remarkable stability is corroborated by theoretical insights about global minima.

First of all, the formal setting should be clarified: according to the specifications given in Section 3, this study focuses on “monotone” read-once DNF formula for which all literals are positive. I don’t think that this restriction has a major impact on the result since read-once DNFs are unate (i.e. we can rename negative literals in order to obtain a monotone variant). 

Next, the learnability result about read-once DNF formula should be clarified. In the introduction, it is indicated that this concept class is efficiently PAC learnable under the uniform distribution, by quoting Fiat & Pechyony (2004). Well, this is not exactly true: Fiat & Pechyony (2004) used a result obtained by Mansour & Schain (2001), in which it was shown that read-once DNF formulas are properly and efficiently PAC learnable under any maximum entropy distribution. But in F&P (2004), it was not explicitly demonstrated that “any” read-once DNF formula is properly and efficiently PAC learnable under the uniform distribution. So, for the sake of completeness, it would be legitimate to provide such a result (in the Appendix, for example.)

Finally, and most importantly, I am not entirely convinced by the impact of this study. On the one hand, as indicated above, the authors empirically demonstrate that convex neural nets are able to learn monotone read-once DNF concepts by converging to global minima that capture the target concept. This is indeed interesting in practice, but there is no formal proof that convex neural nets are able to learn “any” monotone read-once DNF in polynomial time with polynomial sample complexity. On the other hand, it is already known that monotone read-once DNF functions are “improperly” but efficiently PAC learnable under the uniform distribution (Hancock & Mansour, 1991). In fact, Hancock and Mansour have shown that monotone read-k DNF functions are efficiently PAC learnable under product distributions. Actually, many subclasses of DNF are known to be efficiently learnable under product distributions, using spectral approaches (see e.g. Feldman, 2012). So, in light of such strong results, it seems that the contribution of the present paper is slightly behind.

Vitaly Feldman. Learning DNF expressions from Fourier spectrum. In Proc. Conf. Learn. Theory (COLT), pages 17.1–17.19, 2012.

Thomas Hancock and Yishay Mansour. Learning monotone k-µ DNF formulas on
product distributions. In Proceedings of the 4th Annual Conference on Computational
Learning Theory (COLT), pages 179–193, 1991.

Yishay Mansour and Mariano Schain, Learning with Maximum-Entropy Distributions. Machine
Learning, 45(2):123-145, 2001.

review_title: Review: On Learning Read-once DNFs With Neural Networks

Meta-review: This paper studies how two-layer neural networks can learn DNFs. The paper provides some theoretical analysis together with empirical evidence.

The direction of analyzing how neural networks learn certain concept classes is definitely extremely important, and the authors do make some progress towards this direction. However, there are some major concerns about the paper:

 In the main result, the authors seem to only able to prove that the learning process converges with exponentially many neurons (exponential in the input dimension, see 6.1 setup). With this many neurons, it is unclear whether the result is directly covered by existing works such as:



(a). "Learning and generalization in overparameterized neural networks, going beyond two layers".
(b). "Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks" 

These two works provide efficient optimization and generalization bounds w.r.t the complexity of the function. However, these works are still in the NTK regime. It would be nice if the authors can distinguish the current technique from NTKs by providing some theoretical guarantee that their main result is indeed more efficient than kernels (as they argue in the intro), the author can refer to:



(a) "What can ResNet efficiently learn, going beyond kernels" .
 (b) "When Do Neural Networks Outperform Kernel Methods?"


With the current form of the draft, it is unclear how the result is better than existing approaches. The authors should address that in the next version of the paper. 

Missing reference of NTKs:
"A convergence theory for deep learning via over-parameterization"



Decision: Reject