Title: COMPLEXITY OF TRAINING RELU NEURAL NETWORK

Abstract: In this paper, we explore some basic questions on the complexity of training Neural networks with ReLU activation function. We show that it is NP-hard to train a two-hidden layer feedforward ReLU neural network. If dimension d of the data is fixed then we show that there exists a polynomial time algorithm for the same training problem. We also show that if sufficient over-parameterization is provided in the first hidden layer of ReLU neural network then there is a polynomial time algorithm which finds weights such that output of the over-parameterized ReLU neural network matches with the output of the given data.

1. INTRODUCTION:

Deep neural networks (DNNs) are functions computed on a graph parameterized by its edge weights. More formally, the graph corresponding to a DNN is defined by input and output dimensions w 0 , w k+1 ∈ Z + , number of hidden layers k ∈ Z + , and by specifying a sequence of k natural numbers w 1 , w 2 , . . . , w k representing the number of nodes in each of the hidden k-layers. The function computed on the DNN graphs is:

f := a K+1 • τ • a K • • • • • a 2 • τ • a 1 ,

where • is function composition, τ is a nonlinear function (applied componentwise) called as the activation function, and a i : R wi-1 → R wi are affine functions.

Given input and corresponding output data, the problem of training a DNN can be thought of as determining edge weights of directed layered graph for which output of the neural network matches the output data as closely as possible. Formally, given a set of input and output data {(x i , y i )} N i=1 where (x i , y i ) ∈ R w0 × R w k+1 , and a loss function l : R w k+1 × R w k+1 → R + (for example, l can be a norm) the task is to determine the weights that define the affine function a i 's such that

N i=1 l(f (x i ), y i ) (1)

is minimized.

Some commonly studied activation functions are: threshold function, sigmoid function and ReLU function. ReLU is one of the important activation functions used widely in applications and literature. However, the problem of complexity of training multi-layer fully-connected ReLU neural network remained open. This is where we add our contributions. Before formally stating the results, we take a look at current state-of-the-art in the literature.

Complexity of training DNNs with threshold activation function:

The threshold (sign) function is given by sgn(x) := 1 if x > 0 -1 if x < 0 .

Neural network with threshold activation function is also called as binary neural network in modern machine learning literature. It was shown by Blum et al. Blum & Rivest (1988) that problem of training a simple two layer neural network with two nodes in the first layer and one node in the second layer while using threshold activation function at all the nodes is NP-complete. The problem turns out to be equivalent to separation by two hyperplanes which was shown to be NP-complete by Megiddo (1988) . There are other hardness results such as crypto hardness for intersection of k-hyperplanes which apply to binary neural networks Shalev-Shwartz & Ben-David (2014) ; Klivans & Sherstov (2009) . In Shalev-Shwartz & Ben-David (2014) it is shown that even the problem of training a binary neural network with 3 or more nodes in first hidden layer and 1 node in second hidden layer is NP-hard.

DNNs with rectified linear unit (ReLU) activation function Theoretical worst case results presented above, along with limited empirical successes lead to DNN's going out of favor by late 1990s. However, in recent time, DNNs became popular again by advent of first-order gradient based heuristics for training. This success started with the work of Hinton et al. (2006) which gave empirical evidence that if DNNs are initialized properly then we can find good solutions in reasonable runtime. This work was soon followed by series of early successes of deep learning in natural language processing Collobert & Weston (2008) , speech recognition Mohamed et al. (2012) and visual object classification Krizhevsky et al. (2012) . It was empirically shown by Zhang et al. (2016) that a sufficiently over-parameterized neural network can be trained to global optimality.

These gradient-based heuristics are not useful for binary neural networks as there is no gradient information. Even networks with sigmoid activation function fell out of favor because gradient information is not valuable when input values are large. The popular neural network architecture uses ReLU activations on which gradient based heuristics are useful. Fomally, the ReLU function is given by: [x] + := max(x, 0).

Related literature As discussed before, most hardness results so far are for binary neural networks Blum & Rivest (1988) ; Klivans & Sherstov (2009) ; Shalev-Shwartz & Ben-David (2014) . There are also limited results for ReLU that we discuss next: Recently, Livni et al. (2014) examined ReLU activations from the point of view that, a shifted ReLU subtracted from another ReLU yields an approximation to threshold function, so such a class of ReLU network should be as hard as binary neural network. Similar results are shown by DasGupta et al. (1994) . In both these papers, in order to model "a shifted ReLU subtracted from another ReLU", the Neural network studied is not a fully connected network. More specifically, in the underlying graph of such a neural network, each node in the second hidden layer is connected to exactly one distinct node in the first hidden layer, weight of the connecting edge is set to -1 with the addition of some positive bias term. Figure 1 shows the difference between ReLU network studied by Livni et al. (2014) ; DasGupta et al. (1994) and fully connected ReLU network. Clearly, the architecture described in Livni et al. (2014); DasGupta et al. (1994) artificially restrict the form of the affine functions in order to prove NP-hardness. In particular, it requires connecting hidden layer matrix to be a square diagonal matrix. Due to this restriction, it was unclear whether allowing full matrix to be non-zero would make problem easy (more parameters hence higher power to neural network function) or hard (more parameters so more things to decide). there exists a class of special functions generated by single hidden layer neural network for which learning will require exponential number of queries (i.e. sample gradient evaluations) for data coming from product measure of real valued log-concave distribution. These are interesting studies in their own right and generally consider hardness with respect to the algorithms that use stochastic gradient queries to the population objective functions. In comparison, we consider the framework of NP-hardness which takes into account complete class of polynomial time algorithms, generally assumes that data is given and looks at corresponding empirical objective.

Recently, Arora et al. (2016) showed that a single hidden layer ReLU network can be trained in polynomial time when dimension of input, w 0 , is constant.

Based on the above discussion, we see that the complexity status of training the multi-layer fullyconnected ReLU neural network remains open. Given the importance of the ReLU NN, this is an important question. In this paper, we take the first steps in resolving this question.

Main Contributions:

• NP-hardness: We show that the training problem for a simple two hidden layer fully connected NN which has two nodes in the first layer, one node in the second layer and ReLU activation function at all nodes is NP-hard. Underlying graph of this network is exactly the same as that in Blum et al. Blum & Rivest (1988) ReLU activation function can be solved in polynomial-time. The first case is when the dimension of the input is fixed. The second case is when we have a network where the number of nodes in the first layer is equal to the number of input data points (highly overparameterized neural network). This second result leads to interesting open questions that we discuss later.

2. NOTATION AND DEFINITIONS:

We use the following standard set notation [n] := {1, . . . , n}. The letter d generally denotes the dimension of input data, the output data is 1 dimensional and N denotes the number of data-points.

The main training problem of interest for the paper corresponds to a neural network with 3 nodes. The underlying graph is a layered directed graph with two layers. The first layer contains two nodes and the second layer contains one node. The network is fully connected feedforward network. One can write the function corresponding to this neural network as follows:

EQUATION

where a i : R d → R for i ∈ {1, 2} are real valued affine functions, and w 0 , w 1 , w 2 ∈ R. The output , so without loss of generality we will assume w 1 , w 2 ∈ {-1, 1}.

We will refer to (k, j)-ReLU NN as generalization of (2, 1)-ReLU NN where there are k ReLU nodes in first layer and j ReLU nodes in second layer. Moreover, output of (k, j)-ReLU NN lies in R j . If there is only one node in the second layer, we will often drop the 1 and refer it as a 2-ReLU NN or k-ReLU NN depending on whether there are 2 or k nodes in the first layer. Definition 2.1 (Decision-version of training problem) Given a set of training data (x i , y i ) ∈ R d × {1, 0} for i ∈ S, does there exist edge weights so that the resulting function F satisfies

F (x i ) = y i for i ∈ S.

The decision version of the training problem in Definition 2.1 is asking if it is possible to find edge weights to obtain zero loss function value in the expression (1), assuming l is a norm i.e. l(a, b) = 0 iff a = b.

3. MAIN RESULTS:

Theorem 3.1 It is NP-hard to solve the training problem for 2-ReLU NN.

The proof of Theorem 3.1 is obtained by reducing the 2-Affine Separability Problem to the training problem of 2-ReLU NN. Details of this reduction and the proof is presented in Section 4. Corollary of Theorem above is as follows: Corollary 3.2 Training problem of (2,j)-ReLU NN is NP hard, for all j ≥ 1. Megiddo (1988) shows that the separability with fixed number of hyperplanes (generalization of 2-affine separability problem) can be solved in polynomial-time in fixed dimension. Therefore 2affine separability problem can be solved in polynomial time given dimension is constant. Based on the reduction used to prove Theorem 3.1 , a natural question to ask is "Can one solve the training problem of 2-ReLU NN problem in polynomial time under the same assumption?". We answer this question in the affirmative. Theorem 3.3 Under the assumption that dimension of input, d, is a constant, there exist a poly(N) solution to the training problem of 2-ReLU neural network, where N is number of data-points.

A proof of this Theorem is presented in Appendix A.6. This theorem suggests that hardness of learning is due to high dimension and as long as d is small, we can find reasonably good algorithms (for practical purposes) for large values of N .

We also study this problem under over-parameterization. Structural understanding of 2-ReLU NN yields an easy algorithm to solve training problem for N-ReLU neural network over N data points. Theorem 3.4 Given data, {x i , y i } i∈[N ] , then the training problem for N -ReLU NN has a poly(N,d) randomized algorithm, where N is the number of data-points and d is the dimension of input.

A proof of this Theorem is presented in Appendix A.7.

4. TRAINING 2-RELU NN IS NP-HARD:

In this section we give details about the NP-hardness reduction for the training problem of 2-ReLU NN. We begin with the formal definition of 2-Affine Separability Problem. Definition 4.1 (2-Affine Separability Problem) Given a set of points {x i } i∈[N ] ∈ R d and a partition of [N ] into two sets: S 1 , S 0 , (i.e. S 1 ∩ S 0 = ∅, S 1 ∪ S 0 = [N ]) decide whether there exist two hyperplanes

H 1 = {x : α T 1 x + β 1 = 0} and H 2 = {x : α T 2 x + β 2 = 0}(α 1 , α 2 ∈ R d , β 1 , β 2 ∈ R)

that separate the set of points in the following fashion: i For each point

x i such that i ∈ S 1 , both α T 1 x i + β 1 > 0 and α T 2 x i + β 2 > 0.

ii For each point x i such that i ∈ S 0 , either α T

1 x i + β 1 < 0 or α T 2 x i + β 2 < 0.

The problem 2-affine separability is NP-complete Megiddo (1988) . Note the difference between conditions i and ii above. First one is an "AND" statement and second is an "OR" statement. Geometrically, solving 2-affine separability problem means that finding two affine hyperplanes {α 1 , β 1 } and {α 2 , β 2 } such that all points in set S 1 lie in one quadrant formed by two hyperplanes and all points in set S 0 lie outside that quadrant. Due to this geometric intuition, the problem is called separation by 2-hyperplanes or 2-affine separability. We will construct a polynomial reduction from this NP-complete problem to training 2-ReLU NN, which will prove that training 2-ReLU NN is NP-hard.

Remark [Variants of 2-affine separability]: Note here that some sources also define 2-affine separability problem with minor difference. In particular, the change is that strict inequalities, '>', in Definition 4.1.i are diluted to inequalities, '≥'. In fact, these two problems are equivalent in the sense that there is solution for the first problem if and only if there is a solution for the second problem. Solution for the first problem implies solution for the second problem trivially. Suppose there is a solution for the second problem, that implies there exist {α 1 , β 1 } and {α 2 , β 2 } such that for all i ∈ S 0 we have either α T

1 x i + β 1 < 0 or α T 2 x i + β 2 < 0. This implies := min i∈S0 max{-α 1 x i -β 1 , -α 2 x i -β 2 } > 0. So if we shift both

planes by 1 2 i.e. β i ← β i + 1 2 then this is a solution to the first problem.

Assumption: 0 ∈ S 1 (Here 0 ∈ R d is a vector of zeros.) Suppose we are given a generic instance of 2-affine separability problem with data-points

{x i } i∈[N ] from R d and partition S 1 /S 0 of set [N ]

.

Since the answer of 2-affine separability instance is invariant under coordinate translation, we shift the origin to any x i for i ∈ S 1 , and therefore assume that the origin belongs to S 1 henceforth.

4.1. REDUCTION:

Now we create a particular instance for 2-ReLU NN problem from general instance of 2-affine separability. We add two new dimensions to each data-point x i . We also create a label, y i , for each data-point. Moreover, we add a constant number of extra points to the training problem. Exact details are as follows:

Consider training set {(x i , 0, 0),

y i } i∈[N ] where y i = 1 if i ∈ S 1 0 if i ∈ S 0 .

Add additional 12 data points to the above training set as follows: {p 1 ≡ {(0, 1, 1), 1}, p 2 ≡ {(0, 2, 1), 1}, p 3 ≡ {(0, 1, 2), 1}, p 4 ≡ {(0, 2, 2), 1}, p 5 ≡ {(0, 1, -1), 0}, p 6 ≡ {(0, 2, -1), 0}, p 7 ≡ {(0, 3, -1), 0}, p 8 ≡ {(0, -1, 1), 0}, p 9 ≡ {(0, -1, 2), 0}, p 10 ≡ {(0, -1, 3), 0}, p 11 ≡ {(0, -1, 0), 0}, p 12 ≡ {(0, 0, -1), 0}}.

Lets call the set of additional data points with label 1 as T 1 and additional data points with label 0 as T 0 . These additional data points (we refer to these points as the "gadget points") are of fixed size. Figure 3 shows the gadget points. Note that origin is added to the gadget because there exists i ∈ S 1 such that x i = 0. Hence training set has the data-point {(0, 0, 0), 1}.

Lets call the training problem of fitting 2-ReLU NN to this data as (P):

. Now what remains is to show that general instance of 2-affine separability has a solution if and only if constructed instance of 2-ReLU NN has a solution. We will first show the forward direction of reduction. This is also the easier direction.

Lemma 4.1 If 2-affine separability problem has a solution then problem (P) has a solution.

The proof of Lemma 4.1 can be found in appendix section A.1.

To prove reverse direction we need to show that if a set of weights solve the training problem (P) then we can generate a solution to the 2-affine separation problem. To understand the approach we take to prove this direction, we introduce the notion of "hard-sorting". Hard-sorting is formally defined below, and its significance is stated in Lemma 4.4.

Definition 4.2 (Hard-sorting) We say that a set of points {π i } i∈S , partitioned into two sets Π 1 , Π 2 can be hard-sorted with respect to Π 1 if there exist two affine transformations l 1 , l 2 and scalars w 1 , w 2 , c such that either one of the following two conditions are satisfied:

1. w 1 l 1 (π) + + w 2 l 2 (π) + = c for all π ∈ Π 1 > c for all π ∈ Π 2 2. w 1 l 1 (π) + + w 2 l 2 (π) + = c for all π ∈ Π 1 < c for all π ∈ Π 2

Being able to hard-sort implies that after passing data through two nodes of the first hidden layer, the scalar input to the second hidden layer node must have a separation of the data-points in Π 1 and the data-points in Π 2 , moreover, scalar input for all data points in Π 1 must be a constant.

Remark 4.2 Hard-sorting property is invariant under sign change of both w 1 , w 2 .

Remark 4.3 Let Π 1 ⊂ Π 1 and Π 2 ⊂ Π 2 . Then hard-sorting of Π 1 ∪ Π 2 with respect to Π 1 ⇒ hard-sorting of Π 1 ∪ Π 2 with respect to Π 1 .

It is not difficult to see that hard-sorting implies (P) has a solution. We show that hard-sorting is also required for solving training problem. This is formally stated in lemma below. The proof of Lemma 4.4 can be found in appendix section A.2 . Figure 4 below explains geometric interpretation of Lemma 4.4

(a) Input is hard-sorted. This can give a perfect fit.

(b) Since there are two red points so input is not hard-sorted. This cannot give a perfect fit.

(c) Since blue points lies on different side of red points so input is not hard-sorted. This cannot give a perfect fit. In the rest of the proof we will argue that the only way to solve the training problem for 2-ReLU NN (P) or equivalently hard-sort data-points is to find two affine function a 1 , a 2 such that i) a 1 (x) ≤ 0 and a 2 (x) ≤ 0 for all x ∈ S 1 ∪ T 1 and ii) a 1 (x) > 0 or a 2 (x) > 0 for all x ∈ S 0 ∪ T 0 . If such a solution exists then there exists a solution to 2-affine separability problem after dropping coefficients of last two dimensions of affine functions -a 1 and -a 2 .

We will first show that we can hard-sort the gadget points only under the properties of a 1 and a 2 mentioned above. This implies that a solution to (P) which hard-sorts all points (including the gadget points) must have same properties of a 1 and a 2 . This follows from counter-positive to Remark 4.3 i.e. if subset of data-points can not be hard-sorted then all data-points can not be hard-sorted. So henceforth, we will focus on the gadget data-points (or the last two dimensions of the data).

4.1.1. GADGET POINTS AND HARD-SORTING:

For lemma provided below, we assume a 1 , a 2 : R 2 → R are affine functions and 0 ∈ R 2 . They can be thought of as projection of original a i : R d+2 → R and 0 ∈ R d+2 to last two dimension which are relevant for gadget data points added according to set T 1 ∪ T 0 . Lemma 4.5 Suppose affine functions a 1 , a 2 : R 2 → R satisfy hard-sorting of the data-points T 1 ∪ T 0 ∪ {0} with respect to T 1 ∪ {0} then all points x ∈ T 1 must satisfy a 1 (x) ≤ 0 and a 2 (x) ≤ 0 with at least one inequality being a strict inequality.

First observe that if a 1 and a 2 satisfy hard-sorting, then neither of them can be a constant function. This is trivially true if both of them are constant. If one of them is constant then data needs to be linearly separable which is not the case for gadget data-points T 1 ∪ T 0 ∪ {0}. So we will assume that both of them are affine functions with non-zero normal vector. Now, the proof of Lemma 4.5 is divided into the following sequence of propositions: Proposition 4.6 Suppose there exists affine functions a 1 , a 2 : R 2 → R, such that a 1 (x) = 0 and a 2 (x) = 0 are parallel lines. Moreover, assume that magnitude of the normal to these lines is equal i.e. ∇a 1 = ∇a 2 = 0. Then such a 1 , a 2 can not satisfy hard-sorting of data points T 1 ∪T 0 ∪{0} with respect to T 1 ∪ {0} Remark 4.7 A key corollary of Proposition 4.6 is that if a 1 , a 2 satisfy hard-sorting of gadget data points T 1 ∪ T 0 ∪ {0} with respect to T 1 ∪ {0} then set L := {x|w 1 a 1 (x) + w 2 a 2 (x) = c} is a line for all c ∈ R. Henceforth, in the proofs of subsequent propositions, we will refer L as w 1 a 1 + w 2 a 2 = c hiding the input variable, x, for ease of notation.

Proposition 4.8 Suppose there exists affine functions a 1 , a 2 : R 2 → R, such that a 1 (x) ≥ 0 and a 2 (x) ≥ 0 for any 3 points, x ∈ T 1 , then such functions can not satisfy hard-sorting of T 1 ∪ T 0 ∪ {0} with respect to T 1 ∪ {0}.

Proposition 4.9 Suppose there exists affine functions a 1 , a 2 : R 2 → R, such that a 1 (x) ≥ 0 and a 2 (x) ≥ 0 for exactly 2 points, x ∈ T 1 , then such functions can not satisfy hard-sorting of T 1 ∪ T 0 ∪ {0} with respect to T 1 ∪ {0}. Proposition 4.10 Suppose there exists affine functions a 1 , a 2 : R 2 → R, such that a 1 (x) ≥ 0 and a 2 (x) ≥ 0 for exactly 1 point, x ∈ T 1 , then such functions can not satisfy hard-sorting of T 1 ∪ T 0 ∪ {0} with respect to T 1 ∪ {0}.

From Propositions 4.8 , 4.9 and 4.10 , we conclude that no point x ∈ T 1 can be on non-negative side of both affine functions when those affine functions are required to satisfy hard-sorting for the gadget points. Now we will show that any single point x ∈ T 1 can not be on the positive side of even one of the affine functions. Proposition 4.11 Suppose there exists affine functions a 1 , a 2 : R 2 → R, such that a 1 (x) > 0 or a 2 (x) > 0 for any x ∈ T 1 , the such functions can not satisfy hard-sorting of T 1 ∪ T 0 with respect to T 1

Note that Propositions 4.8 , 4.9 , 4.10 and 4.11 imply that given affine functions a 1 , a 2 hard-sorting T 1 ∪ T 0 ∪ {0} with respect to T 1 ∪ {0}, all points x ∈ T 1 must satisfy a 1 (x) ≤ 0 and a 2 (x) ≤ 0 with at least one of them being strict inequality. It is clear that each x ∈ T 1 must satisfy inequalities a 1 (x) ≤ 0, a 2 (x) ≤ 0. At least one of these inequalities has to be strictly negative otherwise we have a contradiction to Proposition 4.10.This proves Lemma 4.5.

Now we show one more simple lemma which is critical in proving the final result. Lemma 4.12 Affine functions a 1 , a 2 and weights w 1 , w 2 satisfy hard-sorting of T 1 ∪ T 0 ∪ {0} with respect to T 1 ∪ {0} then parity of weights must be same i.e. w 1 = w 2 = 1 or w 1 = w 2 = -1.

In the next section, we show that this result on gadget data-points gives us solution to the original 2-affine separability problem.

4.1.2. FROM GADGET DATA TO COMPLETE DATA:

Note that if there is a solution to problem (P), say a 1 , a 2 ∈ R d+2 and w 1 , w 2 , w 0 , θ ∈ R, then by Lemma 4.5 , Lemma 4.12 and counterpositive of Remark 4.3 we have 1. Parity of w 1 , w 2 is same.

2. w 1 a 1 (x) + + w 2 a 2 (x) + = 0 for all x ∈ S 1 ∪ T 1 due to requirement of hard-sorting.

Since parity of w 1 , w 2 is same so 2 above is satisfied if a 1 (x) ≤ 0 and a 2 (x) ≤ 0 for all x ∈ S 1 ∪T 1 . Moreover, we require a 1 (x) > 0 or a 2 (x) > 0 for all x ∈ S 0 ∪ T 0 because otherwise we will violate hard-sorting. Now as discussed earlier, -a 1 , -a 2 after ignoring coefficients of last two dimensions will yield solution to 2-affine separability problem. So we have the following lemma. Lemma 4.13 If there is a solution to the problem (P), then there is a solution to corresponding 2-Affine separability problem. Theorem 4.14 Training problem for 2-ReLU NN is NP-hard.

Proof. Using Lemma 4.1 and Lemma 4.13, we conclude the proof.

Immediate corollary of Theorem 4.14 is as follows: Corollary 4.15 Training problem of (2,j)-ReLU NN is NP hard.

5. DISCUSSION:

We showed that the problem of training 2-ReLU NN is NP-hard. Given the importance of ReLU activation function in neural networks, in our opinion, this result resolves a significant gap in understanding complexity class of the problem at hand. On the other hand, we show that the problem of training N -ReLU NN is in P. So a natural research direction is to understand the complexity status when input layer has more than 2 nodes and strictly less than N nodes. A particularly interesting question in that direction is to generalize the gadget we used for 2-ReLU NN to the case of k-ReLU NN.

A PROOFS OF AUXILIARY RESULTS:

In this appendix, we provide proof of all auxiliary results.

A.1 PROOF OF LEMMA 4.1 Suppose (α 1 , β 1 ) and (α 2 , β 2 ) are solution satisfying condition for 2-affine separability. Note that there is a data-point 0 ∈ S 1 so we obtain β 1 , β 2 > 0. Without loss of generality we can assume β 1 = β 2 = 0.5. This is due to the fact that scaling the original solution by any positive scalar yields a valid solution. Define := min

i∈S0 -α T 1 x i -β 1 + + -α T 2 x i -β 2 + .

Note that since we have a valid solution to 2-affine separability, we must have > 0 because sum of two non-negative quantities where at least one is positive must be positive. Define η := min{ 1 2 , 1 4 }. By definition η > 0 and hence η -1 is defined. Now 2-ReLU neural network function can be written as follows:

f (x, y, z) = 1 η --α T 1 x -β 1 -y + --α T 2 x -β 2 -z + + η + .

We claim that 2-ReLU NN with weights assigned as above solves the training problem (P).

1. For x ∈ S 1 , we have

f (x, 0, 0) = 1 η --α T 1 x -β 1 + --α T 2 x -β 2 + + η + = 1 η [0 + 0 + η] = 1.

2. For x ∈ S 0 , we have

f (x, 0, 0) = 1 η --α T 1 x -β 1 + --α T 2 x -β 2 + + η + . Now note that -α T 1 x -β 1 + + -α T 2 x -β 2 + ≥ , ∀ x ∈ S 0 .

So inner term of above expression is less than or equal to -+ η. Since η ≤ 1 2 , the inner term is negative. Hence for all x ∈ S 0 , f (x, 0, 0) = 0. 3. For x = (0, l, m) ∈ T 1 , we have

f (0, l, m) = 1 η --β 1 -l + --β 2 -m + + η + .

Note that since β 1 = β 2 = 1/2 and l, m ∈ {1, 2} so the two ReLU terms inside are both zero for all x ∈ T 1 . Hence f (x) = 1. 4. For x = (0, l, m) ∈ T 0 , we have

f (0, l, m) = 1 η --β 1 -l + --β 2 -m + + η + .

Note that since β 1 = β 2 = 1/2 and either l or m equals -1, we obtain that either one of the ReLU terms equals 1/2. So inner term is less than or equal to -1/2 + η, but η ≤ 1/4 therefore f (x) = 0 for all x ∈ T 0 .

This proves existence of weights solving the training problem (P).

A.2 PROOF OF LEMMA 4.4

Suppose points are hard-sorted as required by lemma with condition 1 of hard sorting. Then define

:= min x∈S0∪S0 w 1 l 1 (x) + + w 2 l 2 (x) + -c. By definition > 0.

Then it is easy to check that neural network f (x) = 2 -w 1 l 1 (x) + -w 2 l 2 (x) + +c+ /2 + solves training problem. Similar arguments hold when points can be hard-sorted with condition 2 of hard-sorting. Now we assume that points can not be hard-sorted and conclude that there does not exist weight assignment solving training problem of 2-ReLU NN. Since the points cannot be hard-sorted so there does not exist any l 1 , l 2 , w 1 , w 2 , c satisfying either condition 1 or condition 2. This implies for all possible weights we either have a) w 1 l 1 (x) + + w 2 l 2 (x) + is not constant for all x ∈ S 1 ∪ S 1 or b) If w 1 l 1 (x) + + w 2 l 2 (x) + = c for all x ∈ S 1 ∪ S 1 and some constant c, then same expression evaluated on x ∈ S 0 ∪ S 0 is not strictly on same side of c.

If we choose l 1 , l 2 , w 1 , w 2 , c such that a) happens, then such weights will not solve training problem as their output of 2-ReLU NN for points p ∈ S 1 ∪ S 1 will be at least two distinct numbers which is an undesirable outcome. Specifically, we want θ w 0 + w 1 l 1 (x) + + w 2 l 2 (x) + + to evaluate to 1 for all x ∈ S 1 ∪ S 1 so we must have θ > 0 and w 0 + w 1 l 1 (x) + + w 2 l 2 (x) + take a constant positive value for all x ∈ S 1 ∪ S 1 . Hence w 1 l 1 (x) + + w 2 l 2 (x) + must be a constant for all x ∈ S 1 ∪ S 1 . This requirement is violated in case a).

If we choose l 1 , l 2 , w 1 , w 2 , c such that b) happens, then we can set w 0 , θ such that F (x) = θ w 1 l 1 (x) + +w 2 l 2 (x) + +w 0 + , w 0 +c > 0 and θ = 1 w0+c . Since not all x ∈ S 0 ∪S 0 are strictly on one side, we conclude there exist x ∈ S 0 ∪ S 0 such that w 1 l 1 (x ) + + w 2 l 2 (x ) + = c ≥ c hence F (x ) := θ w 1 l 1 (x ) + + w 2 l 2 (x ) + + w 0 + ≥ 1 which is an undesirable outcome for a point with label 0. Since all choices of l 1 , l 2 , w 1 , w 2 , c satisfy either a) or b) so we conclude that there does not exist weights solving training problem of 2-ReLU NN.

A.3 PROOF OF PROPOSITION 4.6:

We assume that magnitude of the normal to these lines is equal i.e. ∇a 1 = ∇a 2 = 0. Note that we have two possible situations here: a 1 , a 2 satisfy 1)a 1 (x) + a 2 (x) = c, ∀ x ∈ R when normals point in opposite directions and 2) a 1 (x) -a 2 (x) = c, ∀x ∈ R when normals point in same direction. (Here c ∈ R is a constant). We will consider both these cases separately and show that expression w 1 a 1 + + w 2 a 2 + can not hard-sort as required irrespective of the parity of weights w 1 , w 2 . Due to Remark 4.2, we just need to check for case {w 1 , w 2 } = {1, 1} and {w 1 , w 2 } = {1, -1}. More specifically, {w 1 , w 2 } = {-1, -1} yields a hard-sorting solution iff there exists a hard-sorting solution for {w 1 , w 2 } = {1, 1}. Equivalent argument can be made about the case {w 1 , w 2 } = {-1, 1} and {w 1 , w 2 } = {1, -1} Case 1: Normals point in opposite direction. Let a 1 + a 2 = c. Suppose c ≥ 0. Then it can be verified that

a 1 + (x) + a 2 + (x) =    c if c ≥ a 1 (x) ≥ 0 a 1 (x) if a 1 (x) ≥ c c -a 1 (x) if a 1 (x) ≤ 0.

By hard-sorting requirement, we need all five points in T 1 ∪ {0} should be in set {x : a 1 (x) ∈ [0, c]} and all points in T 0 should not be in this set. Now observe that if c = 0, then the set {x : a 1 (x) = 0} is one dimensional, and therefore can not contain all the points of T 1 ∪ {0}. Hence we must have c > 0. It can be seen that this is impossible to achieve by two parallel lines a 1 = 0 and a 1 = c for the given set up of data points T 0 ∪ T 1 ∪ {0}. Similarly when c < 0, then it can be verified that

a 1 + (x) + a 2 + (x) =    0 if c ≤ a 1 (x) ≤ 0 a 1 (x) if a 1 (x) ≥ 0 c -a 1 (x) if a 1 (x) ≤ c

Again, for hard-sorting, as in the previous case, we need all five points in T 1 ∪ {0} should be in set {x : a 1 (x) ∈ [c, 0]} and all points in T 0 should not be in this set which can not be achieved. Now consider case where parity of w i 's is different. When c ≥ 0, it can be verified that

a 1 + (x) -a 2 + (x) =    a 1 (x) -c if a 1 (x) ≤ 0 2a 1 (x) -c if 0 ≤ a 1 (x) ≤ c a 1 (x) if a 1 (x) ≥ c

It is clear that all five points in T 1 ∪ 0 can not be on line a 1 (x) = δ for any constant δ. So this type of function can not hard-sort given points.

Under review as a conference paper at ICLR 2019 When c < 0. Then it can be verified that

a 1 + (x) -a 2 + (x) =    a 1 (x) if a 1 (x) ≥ 0 0 if 0 ≥ a 1 (x) ≥ c a 1 (x) -c if a 1 (x) ≤ c

For hard-sorting with this type of function, we again need all points in T 1 ∪ {0} to be in set {x : a 1 (x) ∈ [c, 0]} while all remaining points to be outside this set which is not possible to be achieved by any affine function a 1 . Case 2: a 1 -a 2 = c. Suppose c ≥ 0. Then it can be verified that

a 1 + (x) -a 2 + (x) =    a 1 (x) if c ≥ a 1 (x) ≥ 0 c if a 1 (x) ≥ c 0 if a 1 (x) ≤ 0 If c = 0 then a 1 + (x) -a 2 + (x) = 0 for all x ∈ R 2 .

So this can not hard-sort data. Hence for hard-sorting we definitely need c > 0. Moreover, we need either 1) T 1 ∪ {0} ⊂ {x : a 1 (x) ≤ 0} and T 0 ⊂ {x : a 1 (x) > 0} or 2) T 1 ∪ {0} ⊂ {x : a 1 (x) ≥ c} and T 0 ⊂ {x : a 1 (x) < c}. So essentially the points in T 1 ∪ T 0 ∪ {0} must be separable by a line. This is not possible. Note that when c < 0, one can write a 2 -a 1 = -c and write similar functional form for a 2 +a 1 + . Now consider case when parity of weights w i 's is same. Again suppose c ≥ 0. Then one can verify that

a 1 + (x) + a 2 + (x) =    0 if a 1 (x) ≤ 0 a 1 (x) if c ≥ a 1 (x) ≥ 0 2a 1 (x) -c if a 1 (x) ≥ c

Clearly, for hard-sorting we need strict separation by the line a 1 (x) = 0 which is not possible. When c < 0 then we can write a 2 -a 1 = -c and we will need strict separation at line a 2 (x) = 0 which is again not possible. Since in both cases, none of the parity combinations were able to achieve hard-sorting T 1 ∪ T 0 ∪ {0} w.r.t. T 1 ∪ {0}, so we conclude the proof.

A.3.1 PROOF OF PROPOSITION 4.6:

Note that we have two possible situations here: a 1 , a 2 satisfy 1)a 1 (x) + a 2 (x) = c, ∀ x ∈ R when normals point in opposite directions and 2) a 1 (x) -a 2 (x) = c, ∀x ∈ R when normals point in same direction. (Here c ∈ R is a constant). We will consider both these cases separately and show that expression w 1 a 1 + + w 2 a 2 + can not hard-sort as required irrespective of the parity of weights w 1 , w 2 . Due to Remark 4.2, we just need to check for case {w 1 , w 2 } = {1, 1} and {w 1 , w 2 } = {1, -1}. More specifically, {w 1 , w 2 } = {-1, -1} yields a hard-sorting solution iff there exists a hard-sorting solution for {w 1 , w 2 } = {1, 1}. Equivalent argument can be made about the case {w 1 , w 2 } = {-1, 1} and {w 1 , w 2 } = {1, -1} Case 1: Normals point in opposite direction. Let a 1 + a 2 = c. Suppose c ≥ 0. Then it can be verified that

a 1 + (x) + a 2 + (x) =    c if c ≥ a 1 (x) ≥ 0 a 1 (x) if a 1 (x) ≥ c c -a 1 (x) if a 1 (x) ≤ 0.

By hard-sorting requirement, we need all five points in S 1 ∪{0} should be in set {x : a 1 (x) ∈ [0, c]} and all points in S 0 should not be in this set. Now observe that if c = 0, then the set {x : a 1 (x) = 0} is one dimensional, and therefore can not contain all the points of S 1 ∪ {0}. Hence we must have c > 0. It can be seen that this is impossible to achieve by two parallel lines a 1 = 0 and a 1 = c for the given set up of data points S 0 ∪ S 1 ∪ {0}. Similarly when c < 0, then it can be verified that

a 1 + (x) + a 2 + (x) =    0 if c ≤ a 1 (x) ≤ 0 a 1 (x) if a 1 (x) ≥ 0 c -a 1 (x) if a 1 (x) ≤ c

Again, for hard-sorting, as in the previous case, we need all five points in S 1 ∪ {0} should be in set {x : a 1 (x) ∈ [c, 0]} and all points in S 0 should not be in this set which can not be achieved. Now consider case where parity of w i 's is different. When c ≥ 0, it can be verified that

a 1 + (x) -a 2 + (x) =    a 1 (x) -c if a 1 (x) ≤ 0 2a 1 (x) -c if 0 ≤ a 1 (x) ≤ c a 1 (x) if a 1 (x) ≥ c

It is clear that all five points in S 1 ∪ 0 can not be on line a 1 (x) = δ for any constant δ. So this type of function can not hard-sort given points. When c < 0. Then it can be verified that

a 1 + (x) -a 2 + (x) =    a 1 (x) if a 1 (x) ≥ 0 0 if 0 ≥ a 1 (x) ≥ c a 1 (x) -c if a 1 (x) ≤ c

For hard-sorting with this type of function, we again need all points in S 1 ∪ {0} to be in set {x : a 1 (x) ∈ [c, 0]} while all remaining points to be outside this set which is not possible to be achieved by any affine function a 1 . Case 2: a 1 -a 2 = c. Suppose c ≥ 0. Then it can be verified that

a 1 + (x) -a 2 + (x) =    a 1 (x) if c ≥ a 1 (x) ≥ 0 c if a 1 (x) ≥ c 0 if a 1 (x) ≤ 0 If c = 0 then a 1 + (x) -a 2 + (x) = 0 for all x ∈ R 2 .

So this can not hard-sort data. Hence for hard-sorting we definitely need c > 0. Moreover, we need either 1) S 1 ∪ {0} ⊂ {x : a 1 (x) ≤ 0} and S 0 ⊂ {x : a 1 (x) > 0} or 2) S 1 ∪ {0} ⊂ {x : a 1 (x) ≥ c} and S 0 ⊂ {x : a 1 (x) < c}. So essentially the points in S 1 ∪ S 0 ∪ {0} must be separable by a line. This is not possible. Note that when c < 0, one can write a 2 -a 1 = -c and write similar functional form for a 2 +a 1 + . Now consider case when parity of weights w i 's is same. Again suppose c ≥ 0. Then one can verify that

a 1 + (x) + a 2 + (x) =    0 if a 1 (x) ≤ 0 a 1 (x) if c ≥ a 1 (x) ≥ 0 2a 1 (x) -c if a 1 (x) ≥ c

Clearly, for hard-sorting we need strict separation by the line a 1 (x) = 0 which is not possible. When c < 0 then we can write a 2 -a 1 = -c and we will need strict separation at line a 2 (x) = 0 which is again not possible. Since in both cases, none of the parity combinations were able to achieve hard-sorting S 1 ∪ S 0 ∪ {0} w.r.t. S 1 ∪ {0}, so we conclude the proof.

A.3.2 PROOF OF PROPOSITION 4.8:

From Proposition 4.6 we obtain that w 1 a 1 + w 2 a 2 = c is a line irrespective of parity of w 1 , w 2 and any value of c. Define set S + := {x : a 1 (x) ≥ 0 and a 2 (x) ≥ 0}. Then {x ∈ S + : w 1 a 1 + + w 2 a 1 + (x) = c} is a one dimensional set. Now any 3 points in S 1 which are given to be in S + can not be on a single line (because they are not collinear). So we get that any 3 points in S 1 can not be in S + while condition for hard-sorting holds.

A.3.3 PROOF OF PROPOSITION 4.9 By Proposition 4.6, we know that w 1 a 1 + w 2 a 2 = c is a line irrespective of parity of weights w 1 , w 2 and value of constant c. Case 1: Parity of w 1 , w 2 is same. Suppose exactly p 3 , p 4 are two points in S 1 which satisfy required conditions. Suppose

a 1 + (x) + a 2 + (x) = c for all x ∈ S 1 . Then a 1 (p i ) + a 2 (p i ) = c, i = 3, 4. Note that c ≥ 0 and 0 ≤ a 1 (p i ) ≤ c, i = 3, 4.

We first claim that c > 0. Assume by contradiction, c = 0. In this case a 1 (p 3 ) = a 1 (p 4 ) = a 2 (p 3 ) = a 2 (p 4 ) = 0. Since p 3 , p 4 are distinct points, this implies that {x : a 1 (x) = 0} and {x : a 2 (x) = 0} are the same line and this line passes through points p 3 and p 4 . Since p 9 is in affine hull of p 3 and p 4 , we therefore have that a 1 (p 9 ) = a 2 (p 9 ) = 0. This clearly violates condition of hard-sorting. Thus c > 0. The observation that c > 0 together with Proposition 4.8 gives us that p 1 , p 2 must be separated from p 3 , p 4 by exactly one of the lines a 1 = 0 and a 2 = 0. (At least one line because of Proposition 4.8 i.e. we can not allow p 1 to be in S + := {x : a 1 (x) ≥ 0 and a 2 (x) ≥ 0} along with p 3 , p 4 . At most one line because of observation c > 0, so a 1 + (p 1 ) + a 2 + (p 1 ) must equals c which is strictly positive quantity. Similar arguments can be made for p 2 ). In essence, we get exactly two sub-cases:

1. Line a 1 (x) = 0 separates only p 1 and a 2 (x) = 0 separates only p 2 . Equivalently, a 1 (p 1 ) < 0 and a 2 (p 2 ) < 0.

Since a 1 (p 1 ) < 0 ≤ a 1 (p 3 ) so we conclude a 1 (p 2 ) < a 1 (p 4 ). But as noted before, we have a

1 (p 4 ) ≤ c which implies a 1 (p 2 ) < c. So a 1 + (p 2 ) + a 2 + (p 2 ) = a 1 (p 2 ) < c, contradiction to condition of hard-sorting.

2. a 1 = 0 separates both p 1 , p 2 and a 2 = 0 separates none of p 1 , p 2 . Equivalently, a 1 (p 1 ) < 0, a 1 (p 2 ) < 0.

a 1 + (p i ) + a 2 + (p i ) = a 2 (p i ), i = 1, 2. So a 2 (p i ) = c, i = 1, 2.

Hence a 2 is constant for all points on line passing through p 1 , p 2 . Hence a 2 (p 3 ) = a 2 (p 4 ). Hence a 1 (p 3 ) = a 1 (p 4 ). Again, since p 3 and p 4 are distinct points and p 9 is on the affine hull of p 3 and p 4 , this implies that a 1 (p 3 ) = a 1 (p 9 ) and a 2 (p 3 ) = a 2 (p 9 ), and hence p 3 , p 4 and p 9 will have the same output, a contradiction to condition of hard-sorting.

Similar arguments can be made about pairs {p 1 , p 2 }, {p 1 , p 3 } and {p 2 , p 4 }. Suppose p 2 , p 3 ∈ S + . Then {x : a 1 (x) + a 2 (x) = c} line passes through p 2 , p 3 . Note that this line strictly separates p 1 , p 4 . So we may assume a 1 (p 4 ) + a 2 (p 4 ) > c. Also by Proposition 4.8, p 4 must be separated from p 2 , p 3 by at least one of the lines a 1 = 0, a 2 = 0. So we may assume a 1 (p 4 ) < 0 ⇒ a 2 (p 4 ) > c ⇒ a 1 + (p 4 ) + a 2 + (p 4 ) > c. Contradiction to condition of hardsorting. Similar argument can be made about pair {p 1 , p 4 }. Case 2 Parity of w 1 , w 2 is different. Suppose a 1 + -a 2 + = c. Suppose c > 0. (We will argue c = 0 separately. Arguments for c < 0 will go through in similar fashion by interchanging a 1 , a 2 and replacing c by -c). Suppose p 3 , p 4 ∈ S + := {x : a 1 (x) ≥ 0, a 2 (x) ≥ 0}. It is clear that for hard-sorting a 1 (x) ≥ c > 0, ∀ x ∈ {p 1 , p 2 }. So by Proposition 4.8, we must have a 2 (x) < 0, ∀ x ∈ {p 1 , p 2 }. This implies a 1 (x) = c line passes through p 1 , p 2 . So a 1 (p 3 ) = a 1 (p 4 ) ⇒ a 2 (p 3 ) = a 2 (p 4 ). So lines a 1 = 0, a 2 = 0 are parallel to line passing through p 3 , p 4 . Hence a 1 + (p 9 ) -a 2 + (p 9 ) = c, a contradiction to condition of hard-sorting. Suppose c = 0. Then a 1 (x)-a 2 (x) = 0 line passes through p 3 , p 4 . Consider q, point of intersection of lines a 1 = 0, a 2 = 0 (These lines can't be parallel. Otherwise line a 1 -a 2 = 0 will be parallel to line a 1 = 0 and a 2 = 0. We know that a 1 -a 2 = 0 passes through p 3 , p 4 . So a 1 = 0 and a 2 = 0 will be parallel to line passing through p 3 , p 4 . This implies p 9 will have same output as p 3 , p 4 . This is contradiction to condition of hard-sorting. So a unique point, q, exists). Point q trivially lies on line a 1 -a 2 = 0 or equivalently on the line passing through p 3 , p 4 . We claim that p 9 / ∈ S + . Assume by contradiction that p 9 ∈ S + . We know that a 1 -a 2 passes through p 3 , p 4 and p 9 is in affine combination of p 3 , p 4 so a 1 (p 9 ) -a 2 (p 9 ) = 0. This implies a 1 + (p 9 )a 1 + (p 9 ) = 0, a contradiction to condition of hard-sorting. So p 9 must not be in S + . Since p 3 , p 4 ∈ S + and p 9 / ∈ S + so we obtain that q must lie on line segment p 9 p 3 . Hence lines a 1 = 0, a 2 = 0 must separate p 3 , p 9 . So a 1 (p 9 ) ≤ 0, a 2 (p 9 ) ≤ 0 ⇒ a 1 + (p 9 ) -a 2 + (p 9 ) = 0. Since c = 0, this is contradiction to condition of hard-sorting. Similar arguments can be made about pairs {p 1 , p 2 }, {p 1 , p 3 } and {p 2 , p 4 }. Suppose p 2 , p 3 ∈ S + . Then by Proposition 4.8, either a 1 (p 1 ) < 0 or a 2 (p 1 ) < 0. Without loss of generality, we may assume a 1 (p 1 ) < 0. Since a 1 (p 3 ) ≥ 0 we get a

1 (p 3 ) > a 1 (p 1 ) ⇒ a 1 (p 4 ) > a 1 (p 2 ) ≥ 0. Since a 1 (p 4 ) > 0, by Proposition 4.8, we conclude a 2 (p 4 ) < 0 ≤ a 2 (p 3 ) ⇒ a 2 (p 1 ) > a 2 (p 2 ) ≥ 0. Now a 1 + (p 1 ) -a 2 + (p 1 ) = -a 2 (p 1 ) < 0 and a 1 + (p 4 ) -a 2 + (p 4 ) = a 1 (p 4 ) > 0.

So we get a contradiction. Similar argument can be made about pair {p 1 , p 4 }.

A.3.4 PROOF OF PROPOSITION 4.10 By Proposition 4.6, we know that w 1 a 1 + w 2 a 2 = c is a line irrespective of parity of weights w 1 , w 2 and value of constant c. Case 1: Parity of w 1 , w 2 is same. Suppose a 1 + (x) + a 2 + (x) = c for all points x ∈ S 1 ∪ {0}. We assume c > 0. (We will argue about c = 0 separately). Suppose p 1 ∈ S + := {x : a 1 (x) ≥ 0, a 2 (x) ≥ 0}. Then by Propositions 4.8, 4.9, we conclude that all points in x ∈ S 1 \ {p 1 } must satisfy exactly one of the following inequalities: a 1 (x) ≥ 0, a 2 (x) ≥ 0. (At most one inequality because of Propositions 4.8, 4.8 i.e. we can not allow p i , i = 2, 3, 4 to be in S + := {x : a 1 (x) ≥ 0 and a 2 (x) ≥ 0} along with p 1 . At least one inequality because of observation c > 0, so a 1 + (p 1 ) + a 2 + (p 1 ) must equals c which is strictly positive quantity.) Hence there are two distinct cases to consider:

1. Any two of S 1 \ {p 1 } satisfy a 1 (x) ≥ 0, a 2 (x) < 0. Remaining one satisfy a 1 (x) < 0, a 2 (x) ≥ 0. So a 2 (x) ≥ 0 is satisfied by only two points in S 1 one of which is p 1 . By arrangement of points in set S 1 it is clear that either 1)

a 2 (p i ) ≥ 0, i = 1, 2 ⇒ a 1 (p i ) ≥ 0, i = 1, 3, 4 or 2) a 2 (p i ) ≥ 0, i = 1, 3 ⇒ a 1 (p 1 ) ≥ 0, i = 1, 2, 4.

These two are rotationally equivalent cases so we will only prove for case 1). Case 2) will have similar proof. For hard-sorting, a 1 + (p 3 ) + a 2 + (p 3 ) = a 1 + (p 4 ) + a 2 + (p 4 ). Since a 2 (p i ) < 0, i = 3, 4 so we get a 1 (p 3 ) = a 1 (p 4 ). This implies a 1 (p 1 ) = a 1 (p 2 ). Contradiction to assumptions of case 1. 2. All points in S 1 \ {p 1 } satisfy a 1 (x) ≥ 0, a 2 (x) < 0. Then for satisfying conditions of hard-sorting, we must have a 1 + (p i ) + a 2 + (p i ) = a 1 (p i ) = c, i = 2, 3, 4. Clearly p 2 , p 3 , p 4 are not collinear so this is impossible.

Similar arguments can be made about p 2 , p 3 , p 4 when c > 0. Suppose c = 0 and p 1 ∈ S + . Then line a 1 = 0, a 2 = 0 passes through p 1 . Moreover a 1 + (p i ) + a 2 + (p i ) = 0, i = 2, 3, 4 implies a 1 (p i ) ≤ 0, a 2 (p i ) ≤ 0, i = 2, 3, 4. Now note that p 4 can not lie on the line {x : a 1 (x) = 0} because otherwise {x : a 1 (x) = 0} will be line passing through p 1 , p 4 hence strictly separate p 2 , p 3 . So either one of p 2 , p 3 will satisfy a 1 (x) > 0 which is contradiction to the fact that a 1 + (x) + a 2 + (x) = 0 for all x ∈ {p 2 , p 3 }. Similarly p 4 can not lie on {x : a 2 (x) = 0}. Hence a 1 (p 4 ) < 0, a 2 (p 4 ) < 0 and a 1 (p 1 ) = 0, a 2 (p 1 ) = 0. Since 0, p 1 , p 4 are collinear, we get that a 1 (0) > 0, a 2 (0) > 0. But then a 1 + + a 2 + (0) > 0. This contradicts condition of hard-sorting. Suppose p 2 ∈ S + . Then line a 1 = 0, a 2 = 0 passes through p 2 . Moreover a 1 + + a 2 + (p i ) = 0, i = 1, 3, 4 implies a 1 (p 1 ) ≤ 0, a 2 (p 1 ) ≤ 0. So by colinearity of p 2 , p 1 , p 8 we conclude that a 1 (p 8 ) ≤ 0, a 2 (p 8 ) ≤ 0. Then a 1 + (p 8 ) + a 2 + (p 8 ) = 0 which is contradiction to condition fo hard-sorting. For p 3 or p 4 while c = 0: arguments similar to that of p 2 can be made.

Case 2: Parity of w 1 , w 2 is different. Suppose p 1 ∈ S + and a 1 + (x) -a 2 + (x) = c for all x ∈ S 1 ∪ {0}. Assume c > 0. Proof for c < 0 will follow from this case with a 1 , a 2 exchanged and c replaced with -c. (We will argue for c = 0 separately). Since c > 0, we conclude a 1 (p i ) ≥ c > 0, i = 2, 3, 4. By statement of Proposition it implies a 2 (p i ) < 0, i = 2, 3, 4. Then a 1 + (p i ) + a 2 + (p i ) = a 1 (p i ), i = 2, 3, 4. Since p 2 , p 3 , p 4 are not collinear points, so we get contradiction to condition of hard-sorting. Similar arguments will work for p 2 , p 3 , p 4 . Suppose c = 0 and p 1 ∈ S + . If a 1 (p 2 ) > 0 then a 2 (p 2 ) > 0 but only p 1 ∈ S + so a 1 (p 2 ) ≤ 0, a 2 (p 2 ) ≤ 0. Similarly a 1 (p i ) ≤ 0, a 2 (p i ) ≤ 0, i = 3, 4. By Proposition 4.9, we have that either a 1 (p 4 ) < 0 or a 2 (p 4 ) < 0. Without loss of generality, we assume a 1 (p 4 ) < 0. Since p 4 , p 1 , 0 are collinear so a 1 (0) > 0. Since c = 0 and a 1 + (0) -a 2 + (0) = c so we conclude that a 2 (0) > 0.

So a 1 -a 2 = 0 line passes through 0, p 1 . Note that by collinearity of p 3 , p 1 , p 5 and a i (p 3 ) ≤ 0, a i (p 1 ) = 0 for i = 1, 2 we obtain a 1 (p 5 ) ≥ 0, a 2 (p 5 ) ≥ 0. Similarly by collinearity of p 2 , p 1 , p 8 , we obtain a 1 (p 8 ) ≥ 0, a 2 (p 8 ) ≥ 0. So 0, p 1 , p 5 , p 8 ∈ S + . Moreover a i + (x) = a i (x), ∀ x ∈ S + . So we get a 1 + (x) -a 2 + (x) = a 1 (x) -a 2 (x) for all x ∈ {0, p 1 , p 5 , p 8 }. Since a 1 -a 2 = 0 lines passes through 0, p 1 , it separates p 5 , p 8 . So we get contradiction. Suppose p 2 ∈ S + and c = 0. So we have a 1 (p 1 ) ≤ 0, a 2 (p 1 ) ≤ 0. By collinearity of p 2 , p 1 , p 8 we get a 1 (p 8 ) ≤ 0, a 2 (p 8 ) ≤ 0 ⇒ a 1 + -a 2 + (p 8 ) = 0 which is a contradiction to assumption of hard-sorting. Similar arguments can be made about p 3 , p 4 .

A.3.5 PROOF OF PROPOSITION 4.11

Case 1: Parity of w 1 , w 2 is same. Suppose p 1 ∈ S + := {x : a 1 (x) > 0}. Let T + := {x : a 2 (x) > 0}. Then by Propositions 4.8, 4.9, 4.10, we have a 2 (p 1 ) < 0. So a 1 + (p 1 ) + a 2 + (p 1 ) = c > 0. For hard-sorting, each x ∈ S 1 must be on strictly on positive side of exactly one of the lines. So we conclude that S + , T + is a partition of S 1 . Note that if there are any three points in set S 1 ∩ S + then a 1 (x) will have at least two distinct values for points in set S 1 ∩ S + because of non-collinearity. For points x ∈ S + ∩ S 1 , we have a 1 + (x) + a 2 + (x) = a 1 (x). So we have contradiction to condition of hard-sorting. Similarly there can not be any three points in T + ∩ S 1 . So both S + , T + must contain exactly two points from S 1 . Clearly {p 2 , p 3 } or {p 1 , p 4 } can not be in S + or T + . So the partition has to be either 1) {p 1 , p 2 }, {p 3 , p 4 } or 2) {p 1 , p 3 }, {p 2 , p 4 }. If 1) then lines a 1 = 0, a 2 = 0 are parallel to line passing through p 1 , p 2 . So a 1 + + a 2 + (p i ) will be same for i = 1, 2, 8 which is a contradiction to condition of hard-sorting. Similar contradiction can be found in case of 2). Case 2: Parity of w 1 , w 2 is different. If a 1 (p 1 ) > 0 then a 2 (p 1 ) < 0 (By Propositions 4.8, 4.9, 4.10). Then a 1 + (x) -a 2 + (x) = a 1 (p 1 ) for all x ∈ S 1 . This implies a 1 (x) > 0 for all x ∈ S 1 ⇒ a 2 (x) < 0 for all x ∈ S 1 . Then a 1 + (x) -a 2 + (x) = a 1 (x) for all x ∈ S 1 . But then a 1 (x) can not be a constant number for x ∈ S 1 which yields a contradiction.

A.4 PROOF OF LEMMA 4.12 Lemma 4.5 yields that any hard-sorting a 1 , a 2 must satisfy a 1 (x) ≤ 0, a 2 (x) ≤ 0 for all x ∈ T 1 ∪ {0}. Suppose parity of w 1 , w 2 is different. Since a 1 and a 2 satisfy hard-sorting of gadget so we have a 1 (x) + -a 2 (x) + = c, ∀ x ∈ T 1 . Due to Lemma 4.5, c = 0. Then to fulfill hard-sorting condition, we need a 1 (x) + -a 2 (x) + > 0∀ x ∈ T 0 . (Case for " a 1 (x) + -a 2 (x) + < 0" will have same proof with all a 1 exachanged by a 2 in next 3 lines.) This implies a 1 (x) > 0 for all x ∈ T 0 . In particular, we note that a 1 (p 7 ) > 0, a 1 (p 10 ) > 0. Moreover, a 1 (p 1 ) ≤ 0 as p 1 ∈ T 1 . But p 7 , p 1 , p 10 are collinear points so p 1 is not separable from p 7 , p 10 by an affine function. So we get a contradiction to the assumption that parity of weights w 1 , w 2 is different.

A.5 PROOF OF COROLLARY 4.15:

The reduction is similar except the labels need to be changed from R to R j . Simply add j -1 zeros to original output labels. Now output of j -1 nodes is 0 for all data-points so these are redundnant. In particular, for k ∈ [j], every k-th node in the second layer is connected to 2 nodes in the first layer by distict edges whose weights are parameterized by w k,1 , w k,2 and bias weight w k,0 . We can set w k,1 = w k,2 = -1 and w k,0 = 0 for all k ∈ [j] \ {1}. This yields the output 0 at all nodes k ∈ [j] \ {1}, irrespective of the affine functions a 1 , a 2 in the first layer. Now, first node satisfied to global optimality will yield solution a 1 , a 2 , w 1,1 , w 1,2 , w 1,0 . By the reduction, we know that -a 1 , -a 2 after ignoring last two co-ordinates yield solution to 2-affine separability problem.

A.6 PROOF OF THEOREM 3.3

We will use result by Edelsbrunner et al. (1986) . This work shows that given a set of points {x i } i∈N in R d we can enumerate all possible partition created by linear separators in O(N d ) time.

Suppose we partition:

[N ] into Q 1 /Q 1 and Q 2 /Q 2 such that a 1 (x) = 0 separates Q 1 /Q 1 and a 2 (x) = 0 separates Q 2 /Q 2 . We define T 1 = Q 1 ∩ Q 2 , T 2 = Q 1 ∩ Q 2 , T 3 = Q 1 ∩ Q 2 and T 4 = Q 1 ∩ Q 2 . Let z = (a 1 , a 2 , w 1 , w 2 , w 0 , θ).

Then objective function can be written as

f (z) = i∈T1 θ w 0 + w 1 a 1 (x i ) + w 2 a 2 (x i ) + -y i 2 + i∈T2 θ w 0 + w 2 a 2 (x i ) + -y i 2 + i∈T3 θ w 0 + w 1 a 1 (x i ) + -y i 2 + i∈T4 θ w 0 + -y i 2

Now we can partition T 1 , T 2 , T 3 into T 1i , T 2i , T 3i where i = 1, 2 respectively. For T j1 , ReLU terms in the objective, f , are constrained to be non-negative and for T j2 , ReLU terms are constrained to be non-positive, j = 1, 2, 3. Observe that it suffices to check for θ, w 1 , w 2 = ±1. We will divide the optimization problem in two cases w 0 ≥ 0 and w 0 ≤ 0. In both cases, we will solve for convex program for all possible cases of θ, w 1 , w 2 ∈ {-1, 1}. So there are totally eight cases for each case of w 0 . Since convex program is efficiently solvable so we get the global optimality of the training problem for 2-ReLU NN.

To claim global optimality, we need to enumerate all possible Q 1 /Q 1 and Q 2 /Q 2 which take O(N d ) time each. Also total number of possible partitions is O(N d ). So total O(N 2d ) time to enumerate all possible combinations of Q 1 , Q 2 . For each enumerated combination, Q 1 , Q 2 , we again need to enumerate all possible partitions of T i which are T i1 /T i2 , i = 1, 2, 3. Using the same result Edelsbrunner et al. (1986) , we know that this can be done in O(|T i | d ) = O(N d ) time again. We have to consider all possible combinations of partitions of T i , hence we need O(N 3d ) time to enumerate all possible combinations. Since we need to solve O(N 3d ) convex programs for each choice of Q 1 , Q 2 therefore we need to solve O(N 5d ) convex programs. Each program can be solved in poly(N,d) time. Therefore overall this is poly(N) algorithm for a fixed d. Now we give detail of convex program. Fix θ, w 1 , w 2 for some value in {-1, 1}. Then objective can be written as

f (z) = i∈T11 θ(w 0 + w 1 a 1 (x i ) + w 2 a 2 (x i )) -y i 2 + i∈T21 θ(w 0 + w 2 a 2 (x i )) -y i 2 + i∈T31 θ(w 0 + w 1 a 1 (x i )) -y i 2 + i∈T4 θ w 0 + -y i 2 + i∈T12∪T22∪T32 (0 -y i ) 2 subject to constraints a 1 (x i ) ≥ 0, i ∈ Q 1 a 1 (x i ) ≤ 0, i ∈ Q 1 a 2 (x i ) ≥ 0, i ∈ Q 2 a 2 (x i ) ≤ 0, i ∈ Q 2 w 0 + w 1 a ( x i ) + w 2 a 2 (x i ) ≥ 0, i ∈ T 11

w 0 + w 1 a ( x i ) + w 2 a 2 (x i ) ≤ 0, i ∈ T 12 w 0 + w 2 a 2 (x i ) ≥ 0, i ∈ T 21 w 0 + w 2 a 2 (x i ) ≤ 0, i ∈ T 22 w 0 + w 1 a 1 (x i ) ≥ 0, i ∈ T 31 w 0 + w 1 a 1 (x i ) ≤ 0, i ∈ T 32

We claim that in the algorithm presented above, for every iteration i, we compute new function a j in such a way that a j + (x k ) = 0 for all k less than current iteration, say i. We also have that a j + (x i ) is set in so that newly updated f satisfies f (x i ) = 1 if y i = 1 < 1 otherwise . Finally, newly computed g is an affine function with normal vector which is 1)in direction of -v if y i = 0 and 2) in direction v or 0 when y i = 1. We will prove these facts by induction on i. We will call newly computed g in each case as g new to distinguish between old and new function, g. Similarly after addition of a new node, the updated f will called as f new . This is clearly true for i = 1 i.e. a 1 (x) and corresponding g(x) defined in Initialization step satisfy all the conditions defined in inductive hypothesis. Suppose this is true for some i and we need to show this for i + 1.

Case 1 and 3 are trivially true.

For case 2, we know that f (x k ) = 1 for k ≤ i and y i = 1 < 1 for k ≤ i and y i = 0 . So a j (x) = f (x) -1 ≤ 0 for all x ∈ {x 1 , . . . , x i } as required. Moreover g(x i+1 ) > 1 because v T x i > v T x i-1 and g(x i ) > g(x i-1 ) then, g must have normal in +v direction. Therefore, we obtain g(x i+1 ) > g(x i ) = 1 because v T x i+1 > v T x i . Hence we conclude that newly added function, a j (x) satisfied a j (x i+1 ) > 0 so f new (x k ) = f (x) + w j a j + = 1 for k = i + 1 f (x k ) for k ≤ i . Finally at x i+1 we have g new (x) = f (x) + w j a j (x) = 1 so the normal is 0. This is valid since y i+1 = 1. This proves induction for case 2.

For case 4, since y i = 0 so g must be an affine function in -v direction at x i . Since v T x i+1 > v T x i so we obtain g(x i+1 ) < g(x i ) < 1. So 1-g(x i+1 ) zi+1-zi is a positive scalar. Moreover, we have v T x k ≤ z i for all k ≤ i. So a j + (x k ) = 0 for all k ≤ i. Also a j (x i+1 ) = 1 -g(x i+1 ) > 0 therefore f new (x i+1 ) = f (x i+1 ) + a j + (x i+1 ) = g(x i+1 ) + a j + (x i+1 ) = 1. Finally, at x i+1 we have that normal vector of g new must be either in direction ±v or 0 because normal of a j is in direction +v and g has normal either in direction ±v or is 0. Since g(x i ) = f (x i ) = f new (x i ) < f new (x i+1 ) = g new (x i+1 ) therefore we conclude that normal must be in the direction +v. This is valid since y i+1 = 1. This proves induction for case 4. For case 5, since a j (x) = g(x) -1 + v T x -z i , we can see that a j (x k ) ≤ 0 for k ≤ i because v T x k ≤ z i and f (x k ) ≤ 1. So we immediately get f new (x k ) = f (x k ) for all k ≤ i. Since y i = 1 so g(x) has normal either in direction +v or 0. In both cases, g(x i+1 ) ≥ 1. So we get that a j (x i+1 ) ≥ 0. Hence g new (x i+1 ) = g(x i+1 ) + w j a j (x i+1 ) = 1 + z i -z i+1 < 1. Finally, at x i+1 we have that normal vector of g new must be either in direction ±v or 0 because of the form of a j and inductive hypothesis on f . Since g new (x i ) = 1 > g new (x i+1 ) so normal must be in -v direction which is valid since y i+1 = 0. This proves induction for case 5. Since induction holds for all i so f (x) = j∈J w j a j + (x) satisfies f (

x k ) = 1 if y k = 1 < 1 if y k = 0 .

Moreover, in every iteration we add at most 1 node and there are total N -1 iterations. So we can have at most N nodes. (1 node is created in initialization step). Hence we conclude the proof. Note that since g, a j are affine functions so there addition reduces to addition of vectors which can be done efficiently.

:



Figures and Tables:

(a) ReLU network studied in Livni et al. (2014); Das-Gupta et al. (1994) (b) Fully connected ReLU

Figure 1: Difference between ReLU model studied in Livni et al. (2014); DasGupta et al. (1994) and typical fully connected counterpart

Figure 2: (2,1)-ReLU Neural Network. Also called 2-ReLU NN after dropping '1'. Here ReLU function is presented in each node to specify the type of activation function at the output of each node.of the two affine maps a 1 , a 2 are the inputs to the two ReLU nodes in first hidden layer of network. The weights {w 0 , w 1 , w 2 } denote affine map for ReLU node in second layer. The coefficient θ ∈ R is the linear map of the output layer. Henceforth, we refer to the network defined in (2) as (2,1)-ReLU Neural Network(NN). As its name suggests, it has 2 ReLU nodes in first layer and 1 ReLU

Figure 3: Gadget: Blue points represent set T 1 and red points represent set T 0

The 2-ReLU NN training problem (P) has a solution if and only if data-points S 1 ∪ T 1 ∪ S 0 ∪ T 0 are hard-sorted with respect to S 1 ∪ T 1

Figure 4: X-axis in figures above is output of the first layer of 2-ReLU NN i.e. w 1 l 1 (π) + + w 2 l 2 (π) + . Y-axis is the output of second hidden layer node. Since output of first hidden layer goes to input of second hidden layer, we are essentially trying to fit ReLU node of second hidden layer. In particular, red and blue dots represent output of first hidden layer on data points with label 1 and 0 respectively. In fig (a) we see that hard-sorted input can be classified as 0/1 by a ReLU function. In fig (b) and (c) we see that input which is not hard-sorted can not be classified exactly as 0/1 by a ReLU function.

Peer review (iclr2019):
 This paper claims results showing ReLU networks (or a particular architecture for that) are NP-hard to learn. The authors claim that results that essentially show this (such as those by Livni et al.) are unsatisfactory as they only show this for ReLU networks that are fully connected. However, the authors fail to criticize their own paper for only showing this result for a network with 3 gates. For the same reason that the Livni et al. results don*t imply anything for fully connected networks, these results don*t imply anything for larger networks. Conceivably certain gadgets could be created to ensure that the larger networks are essentially forced to ignore the rest of the gates. This line of research isn*t terribly interesting and furthermore the paper is not particularly well written. For learning ReLUs, it is already known (assuming conjectures based on hardness of improper PAC learning) that functions that can be represented as a single hidden layer ReLU network cannot be learned even using a much larger network in polynomial time (see for instance the Livni et al. paper, etc.). Proving NP-hardness results for proper isn*t as useful as they usually are very restricted in terms of architectures the learning algorithm is allowed to use. However, if they do want to show such results, I think the NP-hardness of learning 2-term DNF formulas will be a much easier starting point. Also, I think there is a flaw in the proof of Lemma 4.1. The function f *cannot* be represented by the networks the authors claim to use. In particular the 1/.eta outside the max(0, x) term is not acceptable.