On Learning Read-once DNFs With Neural Networks
Authors: Ido Bronstein
Alon Brutzkus
Amir Globerson
Venue:  (2021)
Keywords: neural network
DNF
read-once
inductive bias
reconstruction
alignment

Abstract: Learning functions over Boolean variables is a fundamental problem in machine learning. But not much is known about learning such functions by neural networks. Because learning these functions in the distribution free setting is NP-Hard, they are unlikely to be efficiently learnable by networks in this case. However, assuming the inputs are sampled from the uniform distribution, an important subset of functions that are known to be efficiently learnable is read-once DNFs. Here we focus on this setting where the functions are learned by a convex neural network and gradient descent. 
We first observe empirically that the learned neurons are aligned with the terms of the DNF, despite the fact that there are many zero-error networks that do not have this property. Thus, the learning process has a clear inductive bias towards such logical formulas. To gain a better theoretical understanding of this phenomenon we focus on minimizing the population risk. We show that this risk can be minimized by multiple networks: from ones that memorize data to ones that compactly represent the DNF. We then set out to understand why gradient descent ``"chooses" the compact representation. 
We use a computer assisted proof to prove the inductive bias for relatively small DNFs, and use it to design a process for reconstructing the DNF from the learned network. We then continue to provide theoretical insights on the learning process and the loss surface to better understand the resulting inductive bias. For example, we show that the neurons in solutions with minimum $l_2$-norm of the weights are also aligned with the terms of the DNF. Finally, we empirically show that our results are validated in the empirical case for high dimensional DNFs, more general network architectures and tabular datasets.

Under review as a conference paper at ICLR 2021
ON LEARNING READ-ONCE DNFs WITH NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Learning functions over Boolean variables is a fundamental problem in machine learning. But not much is known about learning such functions using neural net- works. Because learning these functions in the distribution free setting is NP- Hard, they are unlikely to be efficiently learnable by networks this case. How- ever, assuming the inputs are sampled from the uniform distribution, an important subset of functions that are known to be efficiently learnable is read-once DNFs, Here we focus this setting where the functions are learned by convex neural network and gradient descent. We first observe empirically that the learned neu- rons aligned with the terms of the DNF, despite the fact that there many zero-error networks that do not have this property. Thus, the learning process has a clear inductive bias towards such logical formulas. To gain better theoretical derstanding of this phenomenon we focus minimizing the population risk. We show that this risk can be minimized by multiple networks: from ones that memo- rize data to ones that compactly represent the DNE. We then set out to understand why gradient descent "chooses" the compact representation. We use a computer assisted proof to prove the inductive bias for relatively small DNFs, and use it to design a process for reconstructing the DNF from the learned network. We pro- ceed to provide theoretical insights the learning process and the optimization to better understand the resulting inductive bias. For example, we show that the network that minimizes the l2 norm of the weights subject to margin constraints is also aligned with the DNF terms. Finally, we empirically show that our results are validated in the empirical case for high dimensional DNFs, more general network architectures and tabular datasets.
INTRODUCTION
The training objective of overparameterized neural networks is non-convex and contains multi- ple global minima with different generalization properties. Therefore, just minimizing the train- ing objective does not guarantee good generalization performance. Nonetheless, neural networks trained in practice with gradient-based methods show good test performance across numerous tasks (Krizhessky et al. 2012] Silver et al.) 2016). suggesting an inductive bias towards desirable solu- tions. Understanding this inductive bias and how depends on the algorithm, architecture and data is one of the major open problems in machine learning (Zhang et al. 2017 Neyshabur et al. 2018).
In recent years, there have been major efforts tackle this challenge. One line of works considers the Neural Tangent Kernel (NTK) approximation of neural networks which reduces to convex optimization problem (Jacot et al. 2018). However, it has been shown that the NTK approximation is limited and does not accurately model neural networks as they are used in practice (Yehudai & Shamir 2019, Daniely & Malach 2020). Other works tackle the non-convexity directly for specific cases. However, current results are either for very simplified settings (c.g., diagonal linear networks Woodworth et al. 2019) or for specific cases such as regression with 2-layer models and Gaussian distributions (Li et al. 2020). for impractical settings with infinitely wide two-layer networks CCiiat & Bach 2020). Presumably, the reason for this relatively limited progress is the lack of general mathematical tools to analyze the non-convexity directly, except for a few simplified cases.
One approach to make progress on this front is to use empirical tools in addition to theory, when the theoretical analysis is not tractable. In this work, use this approach and study the inductive bias

---

Under review as a conference paper at ICLR 2021
150
10
150
150
0.020
130
0.5
0.8
130-
0.015
110
110
0.6
90
0.0 90
90
70
70
6.2
0.005
-1.0
0.000
(a)
(b)
Figure I: Examples of global minima for learning the read-once DNF: (3) A 23) v (I4 A 25 A
T6) (2y A zg Agg) with convex network. (a) Global minimum that memorizes the training points.
(b) Global minimum that recovers the DNF. (c) Global minimum that GD converges to.
in challenging and novel setting which is not addressed in previous theoretical works. Concretely, we consider learning read-once DNFs under the uniform distribution with one-hidden layer, non- homogeneous convex network with ReI.U activations and gradient descent (GD)
In computational learning theory, the problem of learning DNFs has long history. Learning DNFs is hard (Pitt & Valiant 1988) and the best known algorithms for learning DNFs under the uni- time (Verbeurgt 1990). On the other hand, for learning
form distribution run in quasi-polynome read-once DNFs under the uniform distribution there exist efficient learning algorithms (Mansour Schain 2001 Therefore, it interesting to understand whether neural networks can learn read- once DNFs under the uniform distribution and this motivates the study of the inductive bias in this case.
To better understand the inductive bias, we focus the population setting. We show that even in this setting, where the training set consists of all possible binary vectors, there exist global minima of the training objective with significantly different properties. For example, global minimum which memorizes the training points in its neurons, and another minimum whose neurons align exactly with the terms of the DNE, which call DNF-recovery solution. Figure Th-b shows an example of these global minima. Therefore, the key question is what is the inductive bias of GD this case. Namely, to which global minimum does converge?
To address this question, we provide a computer-assisted proof for the convergence of GD in low dimensional DNFs. We circumvent the difficulty of floating point errors in the computer-assisted proof by utilizing unique feature of our setting that allows to perform calculations in integers. We prove that under a symmetric initialization, the global minimum that GD converges to is similar to DNF-recovery solution. Figure Tc shows example of the global minimum GD converges to, which indeed looks similar to the reCovryy solution Figure Tbb We prove, using the computer assisted proof, that after simple procedure of pruning and rounding of the weights, can obtain the exact DNF-recovery solution from the model that GD converges to. Consequently, the terms of the DNF can be reconstructed from the network weights.
We provide additional theoretical results for the population setting. We show that for a symmetric initialization, gradient descent has the following unique stability property: if at some iteration neuron is aligned with a term a DNF, it will continue to be aligned with the term for all subsequent iterations. This gives further evidence that GD is biased towards neurons that are aligned with terms. We also study minimum 12 norm solutions of our problem, inspired by recent works that show connections between norm minimization and GD for homogeneous models (Lu Li, 2020 Chizat & Bach 2020). We prove that the l2 minimum norm solutions are all DeC-rrcy solutions.
We corroborate our findings with empirical results which show that our conclusions hold more broadly. Specifically, we perform experiments on DNFs of higher dimension, standard one- one-hiddes hidden layer neural networks and Gaussian initialization. Taken together, our results demonstrate that gradi-
I Non- homogeneity here is a result of bias in the second layer.
In read-once DNF each literal appears once. See Section for formal definition.
2

---

Under review as a conference paper at ICLR 2021
ent descent can recover simple descriptions of Boolean functions from data, fact that has important implications on the question of interpretability.
RELATED WORK
Recently, several works studied the inductive bias of two-layer homogeneous networks and show
connections between gradient methods and margin maximization (Chizat & Bach 2020 Lyu & Lij 2020 Ji & Telgarsky 2020). Preliminary results for non-homogeneous networks were provided in Nacson et al. 2019). We note that these results do not provide convergence guarantees and hold under assumptions on the dynamics of gradient methods (c.g., that they reach certain loss value). Other works study fully connected neural networks under certain assumptions on the data such as linearly separable data (Brutzkus et al., (018)) or Gaussian data (Safran & Shamir (2088), |Malcch & Shalev-Shwartz (2019) show that certain structured Boolean circuits can be learned with network architecture that is specialized for their data structure. Fully connected networks were also analyzed
via the NTK approximation (Du et al. 2019
2018 Arora al.
2019
Fiat et al. 2019).
Another line of works (Saad & Solla 1996; Goldt ct al. 2019; Tian 2019) studies neural networks in teachttteacchr setting and shows "specialization" phenomenon, where subset of student neurons aligns with teacher neurons. The main difference from our setting is that we consider classification binary data, and they consider regression tasks non-discrete data (e.g., Gaussian). Furthermore, we perform exact DNF recovery which is unique in our classification setting.
Bengio et al. 2006); Bach (017) study convex networks with infinitely many hidden units and devise convex relaxation algorithms. In this work, we consider convex networks with finitely many hidden neurons and study gradient descent non-convex objective.
Rudin 2019) argues that methods for explaining large neural networks should be avoided because networks are too complex for humans to understand. However, we show, albeit in a restricted setting, that learned networks can be rather simple, and are easily mapped to the underlying DNF.
3 PROBLEM FORMULATION
DNFs and Read-Once DNFs: In what follows, we use [n] to denote the set (1,2...., n). and let
X = [+1}² and y = [+ DNFs (e.g., see O'Donnel,, 2014) are usually defined on inputs with entries in {0,1) to output in 1). In this work, we consider DNFs on inputs with entries in {+1} and output in {+1]. Therefore, we will use the following notation for DNFs. Let ti .... Ex E
(0, 1) We refer each t as term and define its set of active indices by A., (j e [ 1), where th is the jth entry of t We define DNF f" X y with K terms ti,..., tx follows:
f((x) 1 in [K] s.t. t = [An) and otherwise f (x) -1. Notice that f is monotone.
We refer to t; as term n of f and we say that a sample x e X satisfies the term t if x t; = |A,l- We refer A,, the size of the term t.- To compare our notation with the standard one, for example, the DNF (x) AI2) ) v (Iz A X4) with 4 inputs has terms ti = 11,100000 and E = (0.0, 1, We will use the standard notation when convenient, e.g., as in Figure In this work we will focus on read-once DNFs where for all i j [K], A; n Aj
Learning Setup: Let D be a the uniform distribution over X' and I be monotone read-once DNF... We consider learning fr given a training set S c X' x V, where for each (2,y) E S, æ sampled IID from D and y (x) Denote S., = (z (xx y) S) and the positive samples by S, {x (æ,1). SS.
Neural Architecture: We consider convex one-hidden layer neural network (NN) with r hidden units and parameters (W, b) R'D, Rr which is defined by:
N(:; W, b) Σ oww, . x + b:)
se[rl
IIn the case of the uniform distribution, we can assume monotone DNFs WLOG, This follows since for the uniform distribution (that has III Bernoulli entries), by symmetry, any negated literal can he replaced with the original literal (without negation) and all results still hold.
3

---

Under review as a conference paper at ICLR 2021
where (xx) max(0.2) is the ReLU function, w; is the hthh row of W and b, is the 7th entry of b. Note that the network is not homogeneous and therefore recent results on homogeneous networks do not apply (see Section The network is convex because it is sum of convex ReLU functions.
Training Loss:
To learn f" we aim to minimize the following hinge loss:
1
L(W. b)
Σ
max (0000001111..000 yN; (.:):
(2.
We note that the above loss function is generally non-convex (even though the network N con- vex). For optimization we use Gradient Descent (GD) with fixed learning rate 1). We denote the initialization of GD by (W("), b(0)) and the weights at iteration by (W('),b b(+)). ). If the iteration index is clear from context we omit it and use (W, b). See Section A for the gradient update.
In this work we will mainly focus on the population case. This corresponds optimizing the loss in Eq. (2) with g x Many works have studied it as proxy to understand the performance in the empirical case (e.g.. Brutzkus Globerson, 2017: Daniely & Malach 2020).
Remark 3.1. The convex network considered here a good test-bed for understanding the inductive bias of learning read-once DNFs with me-hidden layer NNs because: (1) It has the same expressive power as standard NNs for implementing Boolean functions (Section 4 (2) It outperforms standard
NNs on learning read-once DNFs in our setting (Section g (3) Its analysis can be used to better
understand the inductive bias of standard NNs (Section)
EXPRESSIVE POWER
In this section we show that the network in Eq. ① has the expressive power to implement any Boolean function over X. Therefore, in terms of expressive power, the network is suitable for learning Boolean functions and has the same expressive power for implementing Boolean functions as standard one- miedenn layer NN.
Theorem 4.1. Let f: X + y. Then, there exists (W, b) and network N in Eq. 7 with r s 2
neurons such that for all x X, sign (N(x;; W, b)) = sign Σ alw, + b.) - = (2)) [e[r]
Proof. Let B., far X [(x) = =1 and denote B, , ..., B. 1.)) Define |B,|| and for each e [r] define w; x; and b; -D + Then Va, IB, holds that a aww; 2; + b:) and Væ: æ;
holds that o ow. x + 6;) = 0. Therefore Vx e B. we have N(x; W.b) = and for x é B, it holds
that Na; W, b) = 11 from which the claim follows.
MULTIPLE GLOBAL MINIMA IN THE POPULATION SETTING
Assume that S. = X. Then any global minimum of the loss in Eq. implements the ground-truth function f². However, as we will show next, there are global minima that implement f with dras- tically different properties. Understanding which global minimum GD converges is important, because the population case is an approximation of the empirical case with sufficiently many train- ing points. Thus a good understanding of the population case can have direct implications on our understanding of the empirical setting. Indeed, we show in Section g that using our understanding of the population case leads to a procedure that accurately reconstructs the ground-truth DNF from network trained on practical-size training sets.
One network that globally minimizes the loss is the one whose neurons simply "memorize" all positive points, as the following Proposition states (proof follows from Theorem 4.1b
Proposition 5.1. Assume S,, = X. Consider (W. b) with r |Sp s.l. for any x Sp there exists i e [r] where un x and by = - D + Then (W, b) is global minimum of the loss in Eq. P
"This follows since for the uniform distribution we have En-D. fa--D.g/**C (=)(() [max([0 yN W. W.b) b]] Σ max 1 (=: W.b).
[
asX (x))
4

---

Under review as a conference paper at ICLR 2021
We call the above minimum the memorizing solution. Intuitively, converging to this solution in the population case is undesirable, since this may imply memorization in the empirical setting, which can lead to wrong predictions unobserved samples.
Next, we show a different global minimum which recovers the DNF formula explicitly in its neurons. We first need the following definitions.
[r] is covering neuron with respect DNF f*, if there exists M[K [K] and X > 0 such that w; = >2tt,- We refer to X as the covering coefficient of neuron i. We also refer to this neuron covering the term
Definition 5.1. A neuron
n e
Definition 5.2. W covers f", Vn [K] there exists i E [r] such that neuron i covers term
We can now define DNF-recovery solution: Definition 5.3. W is DNF-recovery solution if it covers f and for neurons e [r] that are not covering, it holds that w;
For convenience, we will group all neurons that cover a specific term: Definition 5.4. Assume that W covers the DNF f*. For each [K], we define the set Cn to be the sel of all i & [r] such that neuron i covers term nt.
Next, we show that any DNF-recove
solution is a global minimum under certain conditions.
Proposition 5.2. Assume that Sn X and W a DNF-recovery solution. Then (W, b) is global minimum of the loss in Eq. (2) if the following holds. (1) For every covering neuron with covering coefficient XS and which covers the term n, it holds that b, = )₂ -|t (1t,,)))) (2) For a neuron i that is not covering, b, 0. (3) For all [K]. Eisc, X 2 1.
We note that the third condition ensures that for all a Sp it holds that (Cc: W b) 2 1. We need this condition ensure global optimality. The proof provided in Section [ Intuitively, converging to this global minimum is desirable, because it learns good representations of the data: the terms of the ground-truth read-once DNF f". Thus, given this global minimum, the read-once DNF can be easily reconstructed from the network weights, which can be useful for interpretability. Intuitively, since DNF- DeF-recovery solution is equivalent to a network with a small number of neurons, converging to in the population case may suggest good sample complexity in the empirical case. Indeed, we show empirically in Section that the convex network has good sample complexity for learning read-once DNFs in our setting. The remaining question is which global minimum GD converges
CONVERGENCE ANALYSIS WITH A COMPUTER ASSISTED PROOF
In this section we characterize the global minimum that GD converges to in the population setting. Answering this question via theoretical analysis is extremely challenging due to the non-convexity and complex dynamics of GD. Therefore, to tackle this problem, we opt for a computer assisted proof. Using computer assisted proof show that for low dimensional DNFs, GD converges to solution which is similar to the DNF-recovery solution in the following sense: after a simple pruning and reconstruction procedure, the DNF-recovery solution can be obtained from the global minimum of GD (see Theorem 1. We use unique property of our setting (see Lemma 6. that allows us
perform calculations integers and avoid floating point errors. In Section 7 we provide further theoretical results on the dynamics of GD that corroborate our findings.
6.1 SETUP
We next provide details on the setup of the computer assisted proof. See Section | for more details.
Network and Algorithm: We consider the network in Eq. (1 with 2n and GD with initializa-
tion (0) corresponding to all possible vectors in {=c)" and ((0)) = o We execute the proof for
D < 15. We use small values of converge to global minima that similar to Figure Ic For
'We chose single symmetric initialization of all binary vectors with entries in {=c} to serve as a repre- sentative of initializations used in practice. Indeed, we show in Section X that the conclusions of Theorem 6.1 empirically hold for Gaussian initializations.
5

---

Under review as a conference paper at ICLR 2021
large initializations, GD has different inductive bias (see Section Details on values of and learning rate are provided in Section !
DNFs; We define a balanced DNF to be read-once DNF such that for all i j {[K], [A.] |Ayl- For the proof, we consider all balanced read-once DNFs f with input dimension s D S 12 where each term is of size at least two [ We denote the latter set of DNFs by F.
Pruning and Reconstruction: Figure Ic shows an example of the global minimum that GD con- verges to. Most of the neurons cover term, but not all. Except for the non-covering neurons, the global minimum looks very similar to a DNF-recovery solution. Based on this observation, we will devise a pruning and rounding procedure that when applied to the global minimum of GD, will provably return a DNF-recovery solution for the cases we consider in the computer assisted proof. Section& shows that this procedure also works empirically for various other settings. Next we define the pruning procedure we will use.
Definition 6.1. For 0 & 2 S and a network N with parameters (W,b) b), define Q+(W) = [r] [[w -0 > MMa (W)) where (W) max[]]w;
ad[r]
The pruning procedure removes all neurons that have Lo0 norm which is less than >Ma (W). Next we define the reconstruction procedure.
Definition 6.2. For S 3 1, 3-reconstruution of weight matrix W is (W) E (0. 13 such that for all e [r] and j [D], (W)) = wij > l|l. or (W)s = 0 otherwise.
Figure 2 shows example of the pruning and reconstruction procedures. We use the values of 0.4 S 3 S 0.9 and 0.4 $ y S 0.9 in our proof. Further details are given in Section !
6.2 MAIN RESULT
We can now state our main result, which states that for the set of DNFs F it holds that GD in the setup of Section 6. followed by rounding will converge to a DNF-recovery solution. See Figure 2 for an example of this result.
Theorem 6.1. For all f* e E, parameters n, n, n. as described in Section ! and S. = X, GD converges to a global minimum (W, b) such that Rg (W)) is DNF-recovery solution.
We next provide a sketch of the proof. The main challenge is of course simulating the GD updates, while avoiding floating point errors. We use a key observation that in our setting, we can perform equivalent calculations of the dynamics in integers. This follows since in our binary input setting, the network dynamics can be calculated with rational numbers. Then, by scaling several parameters, we can perform equivalent calculations in integers. The scaling procedure is defined below.
Definition 6.3. Given a > O, weight (") and learning rate т,, the a-GD algorithm is defined as follows. Initialize U(t) (0), (0) 0. Then run GD with constant learning rale Tka na with Σ m0 a (x; where N (a; = Σ o(u; (uux. x c;) a. se[r]
loss CU,
(x
Since the inputs are integers, by taking the learning rate and e to be rational numbers and a to be a sufficiently large integer, o-GD can perform all calculations in integers. Next, show that a-GD performs the same calculations as GD up to a scaling factor. Therefore, we can run a-GD to simulate GD without floating point errors.
Lemma 6.1. Assume we run GD with initialization (W()), ((0) where ())) = 0 and constant 22) and assume we a-GD with paramaters ( and
learning rate тj to optimize the loss in Eq. learning rate r7. Then it holds that a W = Dt. ab' = cd' and aL W b') = (U',
We prove this lemma by induction on t (see Section E). For the computer assisted proof, we run a-GD for each f F and data S. X labeled by f*, with suitable a, rational and 1) such that all calculations are performed in integers. We note that the pruning and reconstruction procedures can be performed with integers as well. Further details are given in Section [
'We focus on balanced DNFs because while the symmetric initialization (0) described above a good test-bed for understanding the inductive bias for balanced DNFs, it is not so for unbalanced DNFs. Indeed, we observe empirically that GD converges in some instances to spurious local minima in this case. However, we will empirically show in Section B that this is not the case for Gaussian initialization and that for this initialization can successfully reconstruct DNFs using the method described in this section.

---

Under review as a conference paper at ICLR 2021
290
290
460
250
250
360
310
170
170
260
210
90
90
110
50
50
60
10
Figure 2: Illustration of pruning and reconstruction for the read-once DNF: (x1 A Az3 (I Is A Is) V (x7 A 2g A Lg). (a) The global minimum that GD converges to. (b) Global minimum
after pruning (Definition 6.1 (c) Global minimum after pruning followed by 8-reconstruction (Definition 6.2
7 THEORETICAL INSIGHTS
In this section we give two theoretical results shedding further light on the inductive bias of GD. Preservation of Term Alignment: Assume the symmetrie initialization in the computer assisted proof. the next theorem we show that if at some iteration 7 of GD, all weight entries a term are equal, then this will continue to hold for all t T. This provides further evidence that GD is biased towards term alignment.
Theorem 7.1. Assume GD is initialized with (W b0) as described in Section and S X.
(T) Then Assume that there exists T 2 0, i é [r] and E [K] such that for all j1. d2 Ann w ijs ij2 (t)
for all I T, j1. E Anp it holds that Wijh Wija"
The proof idea is to exploit the symmetry of the initialization and population setting to show that the GD update constrained to preserve term alignment. The proof is given in Section
Norm Minimization implies DNF-Recovery: Recent works have highlighted interesting connec- tions between gradient methods and norm minimization (Lyu Li, 2020) Nacson al.) (019). The optimization problem is to minimize the norm of the model weights subject to the constraint (x: W, b) for (z the training data. In Lyu Li (2020) it was shown that under some conditions GD will converge to KKT point of this problem. We next show surprising result in our context: the global optimum of this min-norm problem is a DNF-recovery solution. This means that if GD converges to the optimal KKT point, it will find DNF-recovery solution.
Theorem 7.2. Consider the marginn-axxmiiztiin optimization problem:
min
Σietr (w,, by)
(3)
s.f. yN (x: W. b) 21, e
Then, for any solution (W* b') ) of Eq. W is a DNF-recovery solution.
The proof is technical and given in Section The key idea is to show an upper bound on the bias of any global minimum and that the bound is tight for a minimum la norm solution. Then, using this fact together with the optimality of (W*, .b") the theorem can be proved.
EMPIRICAL RESULTS
In this section we perform numerous experiments that support our analysis and show that our con- clusions hold in different settings. For each experiment we show sample of the empirical results due to space constraints. Further details and results are provided in the supplementary.
Comparing Convex and Standard Networks: Our analysis focused on convex network. Here compare it to standard 2-layer network with trainable output layer. Figure 3a reports results,
For the hinge loss, we do not expect GD to converge exactly to the min norm solution. Indeed, Figure 2a from the computer assisted proof shows that GD converges solution which is DNF recovery solution.

---

Under review as a conference paper at ICLR 2021
100
650
050
Success Rate
0.75
550
550
Accuracy
0.50
430
0.03
430
0.05
96
Convex
Standard
0.25
Conves
250
330
0:01
250
230
-0.5
94
0.00
Standard
150
130
2500 5000 7500
Size
2500
Train Set
5000
7500
10.03
25
-0 -010
(a)
(b)
(c)
(d)
Figure 3: Experiments for learning read-once DNFs. (a) Test performance of convex and standard two-layer networks for D = 9. (b) Reconstruction success rate for convex and standard two-layer networks, for D 27. (c) Model learned by a convex network for DNF with D = 100 and small
initialization (d) Same setting (c) with large initialization.
showing that the convex network outperforms the standard one for DNF with D = 9. This shows that the convex network is a good model for studying inductive bias in our setting.
Reconstruction of DNF' in Other Settings: Theorem 6. holds under the assumption of low di- mensional DNFs, a convex network, population case, symmetric initialization and balanced DNFs. Here show that the reconstruction procedure in the theorem can be applied in broader settings. Specifically, we consider a setting with Gaussian initialization, finite data and unbalanced high di- mensional DNFs for D 27. Figure 3b shows the reconstruction success rate for both networks. For each training set size, the recovery is performed for different initializations and training sets. Note that for standard NNs we slightly modified the recovery procedure to accommodate for these networks. In both cases, we see that for at least a moderate training set size, the recovery procedure has high success rate (recall this is for perfect recovery). We note that for D > the recovery for standard neural networks did not work well. However, for the convex network even for D 100, the reconstruction worked well (see Section HD. Figure 3c shows an example of global minimum of GD for D = 100, where the DNF recovery was successful.
Large Initialization: Our results in Section o a small initialization scale. However, several works have shown that the scale of the initialization has significant effect on the inductive bias (Woodworth et al. 22119; Chizat et al.) 2019). What is the inductive bias in the case of large initial- ization our setting? Figure 3d shows the neurons of the global minimum that GD converges to for large initialization and the setting of Figure Sc. We see that neurons are not aligned with terms and have very different inductive bias. Indeed, this model also overfits with 67% test accuracy, compared to 100% test accuracy for the small-scale initialization model in Figure 3c
The fact that SGD recovers simple Boolean formulas is very attractive in the context of interpretability. We showed that we can reconstruct DNFs under certain idcalized assumptions (e.g., uniform distribution, read-once). However, our reconstruction method might produce meaningless reconstructions on datasets which are not uniform nor labeled with a read-once DNF. We tested our reconstruction method on three tabular UCI datasets kr-vs-kp, dia- betes and Splice (Dua & Graff 2017). Learning with our convex network resulted in test accuracies of 93%, 96% and 96% on these datasets, respectively. Our reconstruction method obtained a small DNF (3 terms of size less than 3) on kr-vs-kp with test accuracy 83%. For diabetes, the reconstruc- tion method returned a large DNF (more than 10 terms) with test accuracy 93%. On Splice we got 2-term DNF of sizes 2 and 3 with 95% test accuracy. The latter is very compact DNF with very small loss in accuracy, illustrating the potential of recovery on interpretability.
Experiments Tabular Datasets:
9 CONCLUSIONS
Understanding the inductive bias of neural networks for learning DNF' is an important challenge. In this work we mainly focused on learning read-once DNFs under the uniform distribution with convex network. We provided theoretical results, computer assisted proofs and experiments, all of which suggest that GD is biased towards unique global minima that recover the terms of the DNF. Using our analysis we derived a DNF reconstruction method and showed that it works in broader settings that include standard two-layer networks and tabular datasets.
8

---

Under review as a conference paper at ICLR 2021
Our work opens up many interesting directions for future work. For example, it would be interesting to understand if DNF recovery is possible for other distributions and DNFs that are not read-once. Another interesting direction is to understand the sample complexity of neural networks for learning DNFs and how relates to DNF-recovery. Finally, will be interesting to understand how learning dynamics in neural nets related to other algorithms for learning DNFs.
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang- Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332, 2019.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):62--611, 2017.
Yoshua Bengio, Nicolas L Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. In Advances in neural information processing systems, pp. 123-130, 2006.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International Conference on Machine Learning, pp. 605-614, 2017.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. International Con- ference on Learning Representations, 2018.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.04486 2020.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances in Neural Information Processing Systems, pp. 2933-2943, 2019.
Amit Daniely and Eran Malach. Learning parities with neural networks. arXiv preprint arXiv:2002.00 074000 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp- 1675- 1685, 2019.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. International Conference Learning Representations, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://aaa/t ics uci edu/ml
Jonathan Fiat, Eran Malach, and Shai Shalev-Shwartz. Decoupling gating from linearity. arXiv preprint arXiv:1906.05030 2019.
Sebastian Goldt, Madhu Advani, Andrew Saxe, Florent Krzakala, and Lenka Zdeborová. Dy- namics of stochastic gradient descent for two-layer neural networks in the seccher-ttudnt setup. In Advances in Neural Information Processing Systems, pp. 6981-6991, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- cralization in neural networks. In Advances in neural information processing systems, pp. 8571- 8580, 2018
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning, 2020.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yuanzhi Li, Tengyu Ma. and Hongyang R Zhang. Learning over parammerrid two-layer neural networks beyond ntk. In Conference on Learning Theory, pp. 2613-2682, 2020.

---

Under review as a conference paper at ICLR 2021
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. ICLR, 2020.
Eran Malach and Shai Shalev-Shwartz. Learning boolean circuits with neural networks. arXiv preprint arXiv:I910.111 1992,, 2019.
Yishay Mansour and Mariono Schain. Learning with maximum-entropy distributions. In Machine Learning. pp. 123-145, 2001.
Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro. and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and oon-homogencous deep models. In International Conference Machine Learning, pp. 4683-469999 2019.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. To- wards understanding the role of parpeearaetiinnionnn in generalization of neural networks. arXiv preprint 1rXiv 2018
Ryan D'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014.
Leonard Pitt and Leslie G Valiant. Computational limitations on learning from examples. Journal of the ACM (JACM), 35(4):965-98) 1988.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019.
David Saad and Sara A Solla. Dynamics of on-line gradient descent learning for multilayer neural networks. In Advances neural information processing systems, pp. 302-308, 1996.
Itay Safran and Ohad Shamir. Spurious local minima are common two-layer relu neural networks. In International Conference on Machine Learning, pp. 4433 4441. PMLR, 2018.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
Yuandong Tian. Student specialization in deep relu networks with finite width and input dimension. arXiv, pp. arXiv-1909, 2019.
Karsten Verbeurgt. Learning dnf under the uniform distribution in quasi-polynomial time. In Pro- ceedings of the third annual workshop on Computational learning theory, pp. 314-326, 1990.
Blake Woodworth, Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. arXiv preprint arXiv: 1906.058777 2019.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. In Advances in Neural Information Processing Systems, pp.
2019,
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017.
10

---

Under review as a conference paper at ICLR 2021
A GRADIENT UPDATE
The following definition will be used in order to simplify the gradient updates of GD:
Definition A.1. Given (W(t), )) for each neuron e [r] define:
G (1) ((x, y)
yN W (())()) 0
w (t)
b/ 0)
The set ( consists of all samples that included in the gradient update for neuron i time t. Using this definition, the update rule of GD for neuron i at time is given by:
(1) w w (1-1)
7
Σ
yæ
(( = (1-1)
Σ
y
(5)
(2.8)EC((-1)
(2.))EC(--))
B PROOF OF PROPOSITION 5.2
To prove the result we show necessary properties of global minima when S = X' that will also be useful in the proof of Theorem 7.2 The proof of Proposition 5.2 follows directly from Lemma B.2 below.
B. A SIMPLE PROPERTY OF GLOBAL MINIMA
Recall the definition S, {ae (ar, 1) SS. We also define S, = {a> (1) E S). We first need the following definitions.
Definition B.1. We say that (W, b) satisfies the MIN, property if vo Sp there exists I [r] such by 2 2.
that Σ
iel
Definition B.2. We say that (W,b) satisfies the MIN_ property if a Sn,. Vie [r] w. x b, s O.
The following property of global minimum follows directly by the definition of the network in Eq. ① and the loss function Eq. (2) The proof given Section
Lemma B.1. Assume that S X. Then (W, b) is global minimum of Eq. 2 if and only if (W, satisfies MIN. and MIN..
We note that one direct consequence of Lemma B. is that if a negative S, is activated by neuron i [r]] i.e., w. x + b, then (x. y) G. We will use this fact later sections.
B.2 THE BLAS THRESHOLD
In this section we show that when S. = X, the bias of any neuron in global minimum is upper bounded by a certain value which we call the bias threshold. This upper bound will be useful the proof of Theorem 7.2
Definition B.3. For each term n e [K] of f and é [r] define Vn (w:) max/min(uus 0}.
jehn
Definition B.4. The bias threshold for weight is BT(w) =||ww||: + Σ Vn(w).
ne[
Lemma B.2. Assume that S = X. If (W.b) satisfies that Vie e [r] (T,w., and satisfies the MIN_ property. Then it is a global minimum of the loss in Eq. (2
The proof given in Section D The idea to find for each [r] negative point é; such that
-. BT(w;) and that for any other negative point 24 2; 2; From this, we show that the MIN_ property satisfied if and only if vi [r], b, (T::). Then, using Lemma B. complete the proof.
C PROOF OF LEMMA B.I
Proof. If ( (W, b) is a global minimum, then for all (x, y) S, (x; W. b) 2 1. Therefore,
y Σ ow,, b.) 2 2. Thus, there exists I [r] such that Σ w. x b 2 2. If y -1, s[[]]
de

---

Under review as a conference paper at ICLR 2021
then Σ o(w; x b,) 0 and therefore for all ie [r]], w, b, s 0. The other direction follows se[r]
similarly.
D PROOF OF LEMMA B.2
Definition D.I. We define the set of indices which are not active in any term as the noisy indices and denote them by Ax+1 [D]] Une[K] Ann
The lemma follows directly from Lemma B.I the following lemma.
Lemma D.1. Given a neuron (w, there is negative sample a: & for which w a + > 0 and only b (T(
Proof. Given neuron (w, b), we define the minimum index of a term n é [K] as Jn arg migg (ws) }.
jehn
Consider sample è e Sr where for each j [D]:
sign(wy) wy) En [K] V (ww > 0 A j= otherwise
(6)
(w,)
For a term n [K]. if Vn (w) > then J. -sign(w. = 11, otherwise Vn (w) = and there exists j E A. such that W 0, i.e.. æj sign( (w,) = 1. In any case, ty Aln). Therefore, the label of this sample is negative and denote it by ÿ 11
Now, we have the following:
Wi w. += Σ D
Wg.
Σ
Σ jehnn
Wy
nef K+1]
Σ
Wj sign(w;) ws, sign(ws.)
ne[K] and Va (w (()n
Σ
Σ wy wyy sign(w;)
E JEAK:I
+
ne[K] and V., (w)=0 jehn
Σ
Σ
|uy1 1oyl-lur 11wsaa +
Σ
Σ
lw0il + Σ |w
ne[K] K] and Vu
jea, (n
ne [e[ and (n
jeAln
jehx-i
Σ
Σ
|wyl -2V
Σ
Σ |uys ~Vv(2w
+ Σ lwyl
nel []] and V. (u(w)>
JeAn
ne[K] and Va (w))= jeATn
jahxo1
= Σ Σ
|wy| - vV))w))
+ Σ
|wyl= Σ
1wyl-2 -2 Σ Va(w)
[][ jedl
jedxe
sc[D]
ne[k]
= ||oo||1 -2 Σ Va(w)= = = BT(w)
ne[K]
For the first direction, if BT(w) then w b= BT > 0, as desired.
In the second direction, assume that there is negative sample Sn such that w x + bb>bb 0. We will show that æ w s & w. Every term n E [K] satisties:
Vje An IyWj s /uyl sign(w;)w; = k,
(8)
If (w)) 0, then the index J, also satisfies Eq. ( by the definition of a. Otherwise V,, V.(w) > 0 and we know that there exists jr An such that Fyrr -1 (otherwise the sample's label is not negative), and W.,, wy > O. If Jn, j', then rywy = Wy- Otherwise, the following holds:
Dy F.J. W.J, -0 + Ws,, < 0 < wy w.. &y + $ W... W.J.J.
12

---

Under review as a conference paper at ICLR 2021
Note that every every index in Ak+1 satisfies Eq. conclude that:
8 as well. Therefore, a S Φ w. We can
0 <
+ bs s w + -B=
(10)
which implies that b (T) desired.
E PROOF OF LEMMA 6.
Proof. We wish to prove that the a-GD optimization procedure is equivalent to the original GD, up to scaling. We begin with some definitions.
Definition E.1. Given (U(1), ()),,,, for a neuron i [r] is defined:
H ((x,)) e $ y.a ()))) >0 x >0}
(11)
The update rule of a-GD for (U(t), c(t)) can be simplified as follows:
(1) u u (1-1) ( [ a[=t] aw
(1) (t-1)
Σ
(12)
(a.g)Ek
(æ.y)
We prove the claim by induction on t. For t = 0 by the definition of the initialization we have:
( [0] ab)
(13)
The network satisfies:
Na (0)
Σ
ou, (0)
x (0)) a Σ
(aw (0)
xc[r]
ie[r]
Σ oo (w (0)
x +++
Σ
(w
(0)
x (60)))
(14)
xrrl
[E[r]
ax: (0)
(0) (()))(
and we can conclude that:
1
(U
(0) = Σ
max a yN; (0))
S (æ.y)e8
1
Σ
max
W (0))
(15)
g
(n.y)e
Σ E
m, (0)) (0))
a (W (0) (()))
For the induction step, we assume correctness the claim for /- 1, and prove for t. First, we can
see that by the induction assumption for & S2 and i e [r] we have that u; (t-1). x + ci (t-1) > if and
only if (t-1), x (((-1) > 0. addition, we have that a - yNo (x;; ((-11) c((-1)) 0 and only -1yN((x; (t-1)) b (((-)))) > 0.
By Definition A.l and Definition E.1 and the induction hypothesis, for every i [r] it holds that
G ((-11) H Then, by the induction hypothesis, the following holds:
u
(t)
u
(f-1)
om
Σ
yo aw (t-1)
[77
Σ yo aw! (1)
(16)
(2.))
(2.))=((t-))
c (1-1)
Σ
ab
(1-1)
an Σ
y yb (1)
(a.8)eB(te (-1)
(xt))
as required for the first condition.
To prove that N.(x: U(1) .)))) aN W b()) and aL(W', = (U (U*,c.).. we can repeat the process of Eq. (14) and Eq. (15) with iteration / instead of 0.
13

---

Under review as a conference paper at ICLR 2021
F PROOFS OF THEOREM 7.1
PRESERVATION OF TERM ALIGNMENT)
We use Definition D.1 where K+ [D]] [K] An. We first prove a symmetry lemma in Section F.1 and then prove the theorem in Section F2
F.1 SYMMETRY LEMMA
Definition F.1. We define a reordering of A1..... K+ as the set R = ( TK+I), where each my is a permutation of elements in A, for all 1 sis K +
Definition F.2. Given a reordering R, we define for every sample (x.,y) e a pair (x" .y²) such that:
Vn [K+1] Vj Ann x *x,1]= Z3
(17)
and 1 = y.
Since the label of sample is invariant to reordering, it holds that (x* ,y c..
Lemma F.I. Given (W(O), b))), reordering R. and step 1.2 O, every a E Sy satisfies:
(x; w(),, (1), (())= N (<=; w((), (())
(18)
Proof. Given (W("), ((0) and a reordering R. we define the function P: [r] [r] as follows:
P(h)) i2 Vn [K+1] 1] Vj e A. ( w 1g
(0) and (0) 1/2
(19)
i
By our assumption on the initialization, for every i [r] there exists a unique i2 e [r] such that P(i.) = i2. Therefore, P is well defined inverse function.
We will prove the following claim by induction on 1.2 0:
(1) 1. [rl (Yn [K 1] Vj An w w (t) (()) and (b =b b(()))
2. Vx N(x; ((), b(0)= N(=;; ((1,bb0
For = O, the first property is correct by the definition of P. By our initialization assumption, every ee [r] satisfies w! w
pp(()
(0) xx and ((0)) =b(() =.. Then the second property be proven
P(t)
by:
N(x: (0) (0) (0)) Σ aw ie[r]
( x (0)
) -1 Σ oo P(t) x T + +6)))) ) -1 1NN:N(<; (0)) b (0)
ie[r]
(20)
Assuming the correctness of the claim for t 1, we prove the claim for t. According to Eq. proving the first property, it is enough to show for every i [r] that the following holds:
5 for
Vn [K + 1] Vje e An
(1-1) W
y
=
w
(t-1) P(()
1/
S
(w.y)ec((
(1-
(a.
(t-1)
mnDi
b (11-1) +
7
Σ
y/
1 ((--1)
P())
11
Σ
y
(21)
(m.))e
(1-1)
(a.y)EG(t1)
PCO
By the induction assumption, that every x S2 satisfies:
w is
(1-1) (1-1)
w
P())
and b/())
((-1))
Therefore, we can see
wi
(f-1),
x 6 (1-1)
= Σ
wij Ij +b, 6(th (t-1) Σ Σ (t-1)
(1-1)
wi x. + ((((-1) (t-1)
(22)
]c[D]
nc[K+1]
Σ
Σ
w (t-1)
(1-1)
Σ
w (t-1)
P(1)) + (1-1)
P())
P())
[c[D]
w P(i)
(t-1)
x. +
b1())
14

---

Under review as a conference paper at ICLR 2021
Recall, = y", then by the induction assumption and Definition A.1 the following holds:
Gi (1-1) =1 yN(;; W((-)) w((-1),,((-1) >
wi (t-1)
by
(t-1), 0
(23)
= 1 Nx=" W((-), (o((-)))(((()))) 0 w p()) x + bp()) > 0 = x²
(t-1)
@GP())
Therefore,
Σ ye
Σ ya and
Σ
Σ
y
(24)
(x.g))
(x)1))
(a. P()
We conclude that Eq. 21) is correct, and as a result the first claim in our proof by induction is (1) correct. Therefore, every pair xx S satisfies w (t) a "P(() x", by the first claim and =
Definition F.2 Similarly, it holds that 6. Dp()) Therefore:
(w; (0 )()) Σ [w ( Σ ve[r]
a( (t)
P()) x x=+b/// +b)( - 11==11="; w(() ()))
scrr
(25)
which completes the proof.
F.2 PROOF OF THEOREM
We will prove the claim by induction on t. For f = T the claim is correct by the claim's assumption. Assuming the correctness of the claim for will prove it for t. By Eq. (5)
w
w
(t-1)
Σ
ya
(26)
S
(oo.))e (1-1),
Given j1,32 An, by the induction assumption w
(t-1)
if1
w 6/2
Then, w in
w0(0) if and only
Σ
yo
Σ
ye
(27)
(a.
(m.
j2
We define the following ordering R:
1. vn' e [[K 1](n Vje A., Tee [i]=j
2. Vje A., (2) mn[s]= jj and T [ni = [n[i =
In other words, is the permutation that switches f1 and j2. Since w (t-1) (((1-) we can de- termine that x wi x.. Recall that N (111) ()()) N(x w(1), ((0) by Lemma
F1 Thus, (x.y) (((--) (a".y") e (G(-1) by Definition A.1 Then, using the fact that
(z,,)) E 0 (1-1) yon I F yz conclude that:
Σ y
Σ
y
(N.N))
as required.
G PROOF OF THEOREM 7.2 (MINIMUM 12-NORM IS DNF-RECOVERY SOLUTION)
We set out to characterize the structure of the min- norm solution. In the proof we use Definition D.I [D]] Un][K] A., Following the notation from Definition B. say that solution
where A AK+1
15

---

Under review as a conference paper at ICLR 2021
(W,b) ,) satisfies the MIN, property for positive point Sp if there exists I s [r] such that Σ w, 2 + b, 2 2. We define to the set global minima of the loss in Eq. (). We first prove iel
several lemmas.
G.1 AUXILIARY LEMMAS
Definition G.1. For a term E [K], we define the special sample (n) Sg this term as:
Vj é An oj and jj [D]]An 2) (n) =
(28)
We denote the set of all the special samples by O = far p 3n [K] = a1
Lemma G.1. Given (W, (Wb), assume the following conditions are satisfied:
1. Vi [r], Vj e [D]
Wij 2 O.
2. Every æ e O satisfies the MIN, property.
Then (W, b) satisfies the MIN property for positive samples.
Proof. Let Sy. Then En E [K] such that j An Bj According the second assumption, SIg [r] such that Σ w; (())
For every e [r] the following holds:
w; x
Σ
WifJy
Σ
wij
Σ je[D](An
WyWij
(29)
cc[D]
JEh,
From the first condition of the claim we can deduce that
Σ
Wiy
Σ
IyWiy 2 Σ
Wiy
Σ
Wij Σ
wijzs (n)
w. (())
(30)
Jeng
Di
jehn
Sc[D]
Then:
Eo(w; - x b:) 2 Σ
oww; (n) b;) 2 2
(31)
del
sel
and (W, b) satisfies the MIN, property for required.
The following definition will be very useful in our analysis.
Definition G.2. Given min-norm solution (W* ,b"), then say that the solution (W. b) is
i-modified solution if the following holds:
Vi' [r]]]] wy w. and by by.
(32)
Thus, given a min-norm solution, to define an i-modified solution, we only need to define the neuron (w;,d,) b.).
Lemma G.2. Given
then every i [r] satisfies:
1. b = BT.w;).
2. Vj 6 [D] wi 2 O.
3. 3n [K] such that Vj An wi 2 0 and Vjj [D]]An, Wij = 0.
Proof. Given (W*, b*) and i [r]. we will prove the propertics one by one.
Property 1 Assume by contradiction that b7 * BT(w)). By Lemma B.2 b, has to be smaller
than BT(w)), because otherwise (W*, b²) is not a global minimum of the loss in Eq. 2 Now
consider the i-modified solution, (W, 6). which is defined by:
w w b. BT(w)
(33)
16

---

Under review as a conference paper at ICLR 2021
By the assumption 8, > bg Then, every Sn satisfies the following:
x : + by x. W. b;
(34)
Because (W*, b*) satisfies the MIN, property, then (W, 6) satisfies it as well. Recall that (W*, b*) also satisfies the MIN_ property, thus from Definition G.2 every E S, satisfies:
Vi'e [r]Mi) 0> x w + by x wp by
(35)
In addition, from Lemma D.1 we know that 0 wi; b,. Therefore, (W, b) satisfies the MIN_ property. By Lemma B.1
(W. b) W. From Definition B.4 the bias threshold is negative, then bū < b, s 0 |b,] 16:1. We know that w, = w the (1 6,)112 < [1(w] 6ū )ll which in contradiction to the optimality of (W*,b*).
Property Assume by contradiction that 3j' [D] such that wiy < 0. Consider the following i-modified solution (W, b):
ýj E [DM'')) Wij =wij A wiy =0 BT(x))
(36)
We want show that:
Σ V. (w))= [
Σ Vi((i)) mc[R]
(37)
If 3n' [K] such that j' e Ang, then it follows that (ww Vn (20;) = 0 and Eq. (37 is satisfied.
Otherwise, j' Ax+I, by Definition D.I, the indices of Ax+1 don't affect the value of the sums in
Eq. (37). Therefore, this equation is satisfied in this case as well.
We know that bū =B)(w;) from the first property, thus every æ S3 satisfies the following:
a W by = Σ
2,wig + +T(ww,)
(38)
Σ
zywly wy - 1ugyl
lugg+ + Σ 2Vx(w, (w))
j<DD]G>>>
ne[K]
We can see that w. - lutyl s 0 for every zy. Then,
Σ mywly + xy - |u5rl - Σ luiyl Σ 2Vn(w,) ne[k]
je(D]N6)
s Σ 2,wiy E W Σ (ww)
(39)
*(D])(
jC(D)(())
ne[k]
Σ 2yūij - -1 + Σ 2V, (w.) je[D]
x w BT((;;) x. uù; +
mc[R]
Using the fact that x w by S x 10 b, with the fact that (W*,b) satisfies the MIN, property, we can conclude that (W, b) satisfies this property too.
According to the "Property 1" above and Definition G.2 we have:
vi'e [r]][t] (T(w)) BT (T;ww by. by
(40)
In addition, we know that 6, BT ( by Eq. (36..
According to Lemma D.I the solution satisfies
the MIN_ property and from Lemma B.1 W b) TU
From Eq. 36), we know that |w |0are + || || > || Combining this with Eq. (7) we can conclude that [BT(w;)) ) > |BT
|b [6]] Therefore, b1( < I|( [[w= b )
2 in
contradiction the optimality of (W*,
Property 3- Assume by contradiction that there exists i [r] such that: 3n,, n2 [K 1] such that 3j An, wij > and 3j Anz wiz 0
(41)
Without loss of generality we assume:
Wij 2 Σ Wii Σ jeAn
(42)
jehnng
17

---

Under review as a conference paper at ICLR 2021
Let's look on the following i-modified (W,b) which is defined by:
Vje E Ann V8zz 0 and Vj [D]]Ann wiy = Wiy and b, (T((;;)
(43)
First, we will show that b, 2 big If n2 # K ++1, from Definition and the assumption that Amnzl > 1, the following holds:
6. = BT((;)) = (
Σ johng
|wyl - 2V (w,,) = b; +
Σ
|uiy]
2V (wx) 2 bj
(44)
jaAnng
Otherwise n2 K and from Definition the following holds:
b, BT( (T
+
Σ
|wazg = bi+ +
Σ
|wnyl
2
(45)
jehnz
jehnng
In both cases b, 2 by as required.
Given 7 [K]. we know that (W*, ,b") IU and thus it satisfies the MIN, property for x()), Then, 37 [r] such that:
Ew w x + 2 2
(46)
Pel
We will show that (W, b) satisfies this property for 7i as well. If n2 n2, due the first properly of this lemma and the fact that b, 2 bj the following holds:
w x (1)
E
(
Σ jeAnz
w + bi
E
wiy (3)
+
Σ
(0)
+ b.
sq[D]
=00, or (T)
by
(47)
Then we can conclude that (W, b) satisfies the MIN, MIN,property for x (8) from the following inequal- ities:
Σ Eo x + by 2 Σ w x by. 2
(48)
Pel
wel
Otherwise, πi = n2. By the fact that by = BT(w()) s O, the first property of this lemma and Eq. 42 the following holds:
w b+
Σ
w
Σ
b < Σ wiz- Σ
wi
Σ
why- Σ
wij 0 (49)
jEhun
je[D][An2
jehnz
jehn,
jehnz
jehns
Therefore, using Definition G.2 (W, b) satisfies the following:
Σ pell(()
iy x by
Σ wi x 63 2 Ewi PEl(
w x + by 22
(50)
Pet
We can conclude that (W, b) satisfies the MIN, property for x (%) Combining this with the first
property we can see that (W, b) meets the condition of Lemma G.1 and then it satisfies the MIN, property for all positive samples.
According to the first property and Definition G.2
Vi's [r]][t] (w))) BT(w;) bb by
(51)
In addition, we know that 0, BT (h: by Eq. 43). According to Lemma D.1 the solution satisfies the MIN. property and from Lemma B.1 (W. b) e U.
As we saw 0 2 by > b. + |6,| |b and Vj Ang w 2 = wis then [1(ww, 6 113 |[(,,, 8 in contradiction to the optimality of (W*.b")
We next prove the following covering lemma. Lemma G.3. Given (W*, b²), every i [r] covers some term [K] or w. =
18

---

Under review as a conference paper at ICLR 2021
Proof. Given [r], if w, 0 the claim is true. Otherwise, by the third property of Lemma 3n [r] such that:
G.2
Vj An wij 0 and Vj [D] wij =0
(52)
We will prove the claim for by assuming by contradiction that:
J2 An such that wij, Wija
(53)
Without loss of generality, we assume wig, why and wig, min(w]] Define the following i-modified solution (W.b):
jehn
Vj An thny why and j [D) Wiz why and b BT(w)) Note that Vi (ww (zū)) Wija.
(54)
Given æ Sp, we know that (W*, b") satisfies the MIN, property for æ. Then, 3/ S [r] such that:
Σ w + by 2
(55)
If t, 11,,, due to the third property of Lemma G.2 the following holds:
w. x + bi
Σ
wij
+ BT(w())=
Σ
w
Σ
2V (v=,() = 200
(56)
jeAn
jeAn
jeAp
Σ w Σ
wij
2w
Σ
Wi
|| (v;))())) w. +b
jeAn
jeh.
jeAn
Then conclude that (W,b) b) satisfies this property for from the following:
Ewy x by Σ
x 2
(57)
Fel
Pel
Otherwise, t, ||ll and by Definition B.4
w x + b = Σ wij + (T:BT(() w S
(58)
jehn
Therefore, using Definition G.2 we have that (W. b) satisfies:
Σ
w. x by
Σ w x 67 2 Σ
x + b, 2
(59)
Pel
We can conclude that (W, b) satisfies the MIN property for According to the first property of Lemma G.2 and Definition G.2
Vi's E [r]] (T()))) = BT (w))) by = by
(60)
In addition, we know that 0, = BT (w;;) (i; by Eq. 544. According to Lemma D.1 the solution satisfies the MIN_. property and from Lemma B. (W
b) E U
Finally, we can see that, || || || implies that [B:(w;)) (BT and Vj e [D]w 2 wiy- Thus, have [|w 6ū )l > |I( (wx;. B.)1B.. This is contradiction to the optimality of (W*, bb),, as desired.
We can define X, Vn (ww)) and we know that the neuron i satisfies:
Vj e An w/y = X; and Vj e [D]] w/y 0
(61)
Therefore, w. Axtt, and we can say that the neuron covers the term n.
19

---

Under review as a conference paper at ICLR 2021
100
100
Accuracy (%%
Accuracy (%)
Accuracy (%)
95
98
95
Convex
96
Convex
Convex
90
Standard
Standard
90
Standard
94
250
500
2500 5000 7500
2000
4000
Train Set Size
Train Set Size
Train Set Size
(a)
(b)
Figure 4: Test accuracy for the convex and standard networks. (a) D = 10 and the target DNF has terms of size: (2,3.3) (b) D 27 and the target DNF has 3 terms of size 3, 2 terms of size and one term of size 6. (c) D = 35 and the target DNF has terms of size 2, 4 terms of size 4 and 2 terms of size 2.
G.2 FINISHING THE PROOF OF THEBRRM
Proof. We know from Lemma G.3 that each neuron covers some term. We denote the term that is covered by neuron as n2. Given [K]. we assume by contradiction that it covered, namely Vi [r] n, n. Consider the special positive sample x(") for which it holds that:
Vi [r] x (*) w = (,) tú, =->ullt <0
(62)
By the first property of Lemma G.3 Vi [r], by BT(w;)) s Therefore, [r] (*) O in contradiction to the fact that (W*, b²)) e T
(a) unn +b;
By Definition 5.2 W covers the DNF f". Together with Lemma G.3 this implies that W is DNF-recovery solution.
H EXPERIMENT DETAILS AND ADDITIONAL RESULTS
we use a small Gaussian initialization ( (O0, 10 and ((() = [0] The learning rate for GD is 17= 10-2, and the number of hidden units 700. We create the train set by sampling uniformly from [=1]P. The test set size 10*, sampled uniformly from [=
In the experiments for Figure 3a and Figure 3b
In the experiments of Figure Sa for every train set size we run the experiment five times and report average accuracy. If GD converges local minimum during learning we re-initialize and re-train. Therefore, all our results are taken when the train error is zero.
For the tabular datasets, we consider the three UCI datasets: kr-vs-kp. Splice, and diabetes. For all these, we convert the input into binary by changing categorical variables to one-hot. We also consider binary classification so in kr-vs-kp the class 'won' is positive considered and 'notwon' is negative, in Splice the classes 'El' and 'IE' are considered positive and 'N' negative, and diabetes is binary by design. We train on 90% the data and test on 10%.
H.1 ADDITIONAL EXPERIMENTS
Here we report additional experiments on various D values and DNFs. Figure 4 reports results on test accuracy for convex and standard networks, for D 10, 27, 35. We note that for D 40 values the standard network converges very slowly and often does not converge to zero error, and thus we do not include comparisons in these cases.
Figure reports results on DNF recovery accuracy for D = 10, 30, 100. For 2 30, the standard network typically fails to recover the DNF.
Figure 6 shows learning with small and large initial scale for an unbalanced DNE, To create the figures of the global minima, use hierarchical clustering to cluster the neurons.
20

---

Under review as a conference paper at ICLR 2021
1.0
Success Rate
Success Rate
Success Rate
0.5
50
0.0
100
200
2500 5000 7500
2500 5000 7500
Train Set Size
Train Set Size
Train Set Size
(a)
(b)
(c)
Figure 5: Reconstruction success rate for the convex and standard networks. (a) D = 10 and the target DNF has terms size: (2,3,3) (b) D=30 and the target DNF has 5 terms of size Standard network fails to reconstruct (success rate below 5%). (c) D = 100 and the target DNF has 15 terms of size 5. Standard network fails reconstruct (successs rate below 5%).
650
0.030
650
0.20
0.15
450
450
0.10
0.015
0.05
250
0.010
250
0.00
150
0.005
50
50
0.000
-0.0
5
10
15 20
25
10
15
20
(a)
(b)
Figure 6: Model learned by a convex network for DNF with = for different initailization scales. The ground-trtuh DNF has 3 terms of size 3. terms of size 2 and one term of size 1. (a) Small initialization Can be seen to lead to good recovery. (b) Large initialization Does not lead to good recovery.
I DETAILS FOR COMPUTER ASSISTED PROOF
The set FF for which we proved the result consists of all balanced DNFs with input dimension 4 < D S 15 with terms of sizes at least two, including ones where variables are not part of any term (c.g., when D = 6, we consider also the DNF: (z) A 22) v (Iz A x4)).
We consider the following parameter ranges in the proof: 7 (0.4,0.5,0.9) and 3 (0.4,0,5000 For 4 < D < 12 used n 10-5 and 100 2 - 3- 40-6 1.-1100--1000 10-5 10-660-66601 10066-10777110--.11 7--0- 10-5). For 13 & D & 15 we used v 10 and 2- 10 to avoid long run time
Given D, n. c and target function f" we use lemma a-GD learn f". This allows us to perform the simulation in integers without floating point inaccuracies. According to lemma 6.1 this is equivalent 2 -00 such
to learning with standard GD in term of convergence and recovery. We choose that the initialization integer and by Eq. (5) the update step in integer steps. We use int64 to avoid integer overflow problem.
The procedure begins by initializing W [=<x]] and [0]P. Then we apply Eq. 5 using
matrix multiplication in tensorflow GPU, until achieve loss. After the network converges to a global minimum, we execute y-pruning. To keep the simulation in integers we use the following trick. Instead of calculating if ||w;]loo is larger than 3M (W), we calculate 10 || and 10- y Ma (W), because 10y an integer. Finally, we apply 3-reconstruction to the pruned network to get the reconstructed network, using the same trick to do the simulation in integers.
In the case of = 13 and the target DNF (ar Arr Wat.Xa/aaee.EEaaaa//aaaaaaaaaaaa used 17 10 for reducing the run time even more.
21

---

Under review as a conference paper at ICLR 2021
For validating if our reconstructed network is equivalent to f", go over all the terms of f* and check that there a neuron that is equal to it. In addition, we go over all the neurons and check that they have corresponding term.
22


Reviews:
[{"review_id": "WA0ds_3555F", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nLearning 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. \n\n\nPros:\n1. Provides understanding of the inductive bias of convex neural networks using gradient descent\n2. Computer assisted proof and experiments are used to complement theoretical results\n3. Clearly and concisely written paper, a significant amount of supplementary material to  make a more detailed treatment available for those interested\n\nCons:\n1. Results cover read-once DNFs which is very restricted class of DNFs, which might limit the impact of the results\n2. Without access to code, it's impossible to assess the correctness and quality of the computer assisted proof\n\n\nQuestions:\n\nIt's quite unclear what is happening in Figure 2, could you add some more explanations?\n\nWill the code related to computer assisted proof and the other experiments be made publicly available?\n\nMinor comments: \n\nRemark 3.1: \"Boolean\" not \"boolean\"\n\nThere 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.\n\nKKT in page 7 not defined ", "extra_scores": {}, "extra_text": {}}, {"review_id": "J6GrpfDLUCz", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nFirst 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). \n\nNext, 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.)\n\nFinally, 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.\n\nVitaly Feldman. Learning DNF expressions from Fourier spectrum. In Proc. Conf. Learn. Theory (COLT), pages 17.1–17.19, 2012.\n\nThomas Hancock and Yishay Mansour. Learning monotone k-µ DNF formulas on\nproduct distributions. In Proceedings of the 4th Annual Conference on Computational\nLearning Theory (COLT), pages 179–193, 1991.\n\nYishay Mansour and Mariano Schain, Learning with Maximum-Entropy Distributions. Machine\nLearning, 45(2):123-145, 2001.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7NrvDFCVqZq", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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. \n\nI don’t think the “computer-aided proof” is really a proof. So, I am afraid that it should not be stated as a theorem. \n\nAs a summary, I feel that the technical results are still preliminary and not mature enough to be published.  \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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