Year: 2018

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.

heading: 1 INTRODUCTION
text: 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 w0, wk+1 ∈ Z+, number of hidden layers k ∈ Z+, and by specifying a sequence of k natural numbers w1, w2, . . . , wk representing the number of nodes in each of the hidden k-layers. The function computed on the DNN graphs is:
f := aK+1 ◦ τ ◦ aK ◦ · · · ◦ a2 ◦ τ ◦ a1,
where ◦ is function composition, τ is a nonlinear function (applied componentwise) called as the activation function, and ai : Rwi−1 → Rwi 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 {(xi, yi)}Ni=1 where (xi, yi) ∈ Rw0 × Rwk+1 , and a loss function l : Rwk+1 × Rwk+1 → R+ (for example, l can be a norm) the task is to determine the weights that define the affine function ai’s such that
N∑ i=1 l(f(xi), yi) (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).
Another interesting line of research in understanding the hardness of training ReLU neural networks assumes that data is coming from some distribution. More recent work in this direction include Shamir (2016) which shows a smooth family of functions for which gradient of squared error function is not informative while training neural network over Gaussian input distribution. Song et al. (2017) consider Statistical Query (SQ) framework (which contains SGD algorithms) and show that
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, w0, 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.

heading: Main Contributions
text: • 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) but all activation functions are ReLU instead of threshold function. Techniques used in the proof are different from earlier work in literature because there is no combinatorial interpretation to ReLU as opposed to threshold function.
• Polynomial-time solvable cases: We present two cases where the training problem with 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.

heading: 2 NOTATION AND DEFINITIONS
text: 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:
F (x) = θ [ w0 + w1 [ a1(x) ] + + w2 [ a2(x) ] + ] + , (2)
where ai : Rd → R for i ∈ {1, 2} are real valued affine functions, and w0, w1, w2 ∈ R. The output
of the two affine maps a1, a2 are the inputs to the two ReLU nodes in first hidden layer of network. The weights {w0, w1, w2} 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
node in second layer. Figure 2 shows (2, 1)-ReLU NN. Note that w[ax+ b]+ ≡ sgn(w)[|w|(ax+ b)]+ = sgn(w)[ãx+ b̃], so without loss of generality we will assume w1, w2 ∈ {−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 Rj . 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 (xi, yi) ∈ Rd × {1, 0} for i ∈ S, does there exist edge weights so that the resulting function F satisfies F (xi) = yi 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.

heading: 3 MAIN RESULTS
text: 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 2- affine 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, {xi, yi}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.

heading: 4 TRAINING 2-RELU NN IS NP-HARD
text: 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 {xi}i∈[N ] ∈ Rd and a partition of [N ] into two sets: S1, S0, (i.e. S1 ∩ S0 = ∅, S1 ∪ S0 = [N ]) decide whether there exist two hyperplanes H1 = {x : αT1 x+ β1 = 0} and H2 = {x : αT2 x+ β2 = 0}(α1, α2 ∈ Rd, β1, β2 ∈ R) that separate the set of points in the following fashion:
i For each point xi such that i ∈ S1, both αT1 xi + β1 > 0 and αT2 xi + β2 > 0.
ii For each point xi such that i ∈ S0, either αT1 xi + β1 < 0 or αT2 xi + β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 S1 lie in one quadrant formed by two hyperplanes and all points in set S0 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 ∈ S0 we have either αT1 xi + β1 < 0 or αT2 x
i + β2 < 0. This implies := min i∈S0 max{−α1xi − β1,−α2xi − β2} > 0. So if we shift both
planes by 12 i.e. βi ← βi + 1 2 then this is a solution to the first problem.
Assumption: 0 ∈ S1 (Here 0 ∈ Rd is a vector of zeros.) Suppose we are given a generic instance of 2-affine separability problem with data-points {xi}i∈[N ] from Rd and partition S1/S0 of set [N ]. Since the answer of 2-affine separability instance is invariant under coordinate translation, we shift the origin to any xi for i ∈ S1, and therefore assume that the origin belongs to S1 henceforth.

heading: 4.1 REDUCTION
text: 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 xi. We also create a label, yi, 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 {(xi, 0, 0), yi}i∈[N ] where yi = {
1 if i ∈ S1 0 if i ∈ S0 .
Add additional 12 data points to the above training set as follows: {p1 ≡ {(0, 1, 1), 1}, p2 ≡ {(0, 2, 1), 1}, p3 ≡ {(0, 1, 2), 1}, p4 ≡ {(0, 2, 2), 1}, p5 ≡ {(0, 1,−1), 0}, p6 ≡ {(0, 2,−1), 0}, p7 ≡ {(0, 3,−1), 0}, p8 ≡ {(0,−1, 1), 0}, p9 ≡ {(0,−1, 2), 0}, p10 ≡ {(0,−1, 3), 0}, p11 ≡ {(0,−1, 0), 0}, p12 ≡ {(0, 0,−1), 0}}. Lets call the set of additional data points with label 1 as T1 and additional data points with label 0 as T0. These additional data points (we refer to these points as the “gadget points”) are of fixed size.
So this is a polynomial time reduction.
Figure 3 shows the gadget points. Note that origin is added to the gadget because there exists i ∈ S1 such that xi = 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 l1, l2 and scalars w1, w2, c such that either one of the following two conditions are satisfied:
1. w1 [ l1(π) ] + + w2 [ l2(π) ] + { = c for all π ∈ Π1 > c for all π ∈ Π2
2. w1 [ l1(π) ] + + w2 [ l2(π) ] + { = 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 w1, w2.
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.
Lemma 4.4 The 2-ReLU NN training problem (P) has a solution if and only if data-points S1 ∪ T1 ∪ S0 ∪ T0 are hard-sorted with respect to S1 ∪ T1
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.
Figure 4: X-axis in figures above is output of the first layer of 2-ReLU NN i.e. w1 [ l1(π) ] + +
w2
[
l2(π)
]
+
. 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.
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 a1, a2 such that i) a1(x) ≤ 0 and a2(x) ≤ 0 for all x ∈ S1 ∪ T1 and ii) a1(x) > 0 or a2(x) > 0 for all x ∈ S0 ∪ T0. 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 −a1 and −a2. We will first show that we can hard-sort the gadget points only under the properties of a1 and a2 mentioned above. This implies that a solution to (P) which hard-sorts all points (including the gadget points) must have same properties of a1 and a2. 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).

heading: 4.1.1 GADGET POINTS AND HARD-SORTING
text: For lemma provided below, we assume a1, a2 : R2 → R are affine functions and 0 ∈ R2. They can be thought of as projection of original ai : Rd+2 → R and 0 ∈ Rd+2 to last two dimension which are relevant for gadget data points added according to set T1 ∪ T0. Lemma 4.5 Suppose affine functions a1, a2 : R2 → R satisfy hard-sorting of the data-points T1 ∪ T0 ∪{0} with respect to T1 ∪{0} then all points x ∈ T1 must satisfy a1(x) ≤ 0 and a2(x) ≤ 0 with at least one inequality being a strict inequality.
First observe that if a1 and a2 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 T1 ∪ T0 ∪ {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 a1, a2 : R2 → R, such that a1(x) = 0 and a2(x) = 0 are parallel lines. Moreover, assume that magnitude of the normal to these lines is equal i.e. ‖∇a1‖ = ‖∇a2‖ 6= 0. Then such a1, a2 can not satisfy hard-sorting of data points T1∪T0∪{0} with respect to T1 ∪ {0} Remark 4.7 A key corollary of Proposition 4.6 is that if a1, a2 satisfy hard-sorting of gadget data points T1∪T0∪{0} with respect to T1∪{0} then set L := {x|w1a1(x)+w2a2(x) = c} is a line for all c ∈ R. Henceforth, in the proofs of subsequent propositions, we will refer L as w1a1 +w2a2 = c hiding the input variable, x, for ease of notation.
Proposition 4.8 Suppose there exists affine functions a1, a2 : R2 → R, such that a1(x) ≥ 0 and a2(x) ≥ 0 for any 3 points, x ∈ T1, then such functions can not satisfy hard-sorting of T1∪T0∪{0} with respect to T1 ∪ {0}.
Proposition 4.9 Suppose there exists affine functions a1, a2 : R2 → R, such that a1(x) ≥ 0 and a2(x) ≥ 0 for exactly 2 points, x ∈ T1, then such functions can not satisfy hard-sorting of T1∪T0∪ {0} with respect to T1 ∪ {0}. Proposition 4.10 Suppose there exists affine functions a1, a2 : R2 → R, such that a1(x) ≥ 0 and a2(x) ≥ 0 for exactly 1 point, x ∈ T1, then such functions can not satisfy hard-sorting of T1 ∪ T0 ∪ {0} with respect to T1 ∪ {0}.
From Propositions 4.8 , 4.9 and 4.10 , we conclude that no point x ∈ T1 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 ∈ T1 can not be on the positive side of even one of the affine functions. Proposition 4.11 Suppose there exists affine functions a1, a2 : R2 → R, such that a1(x) > 0 or a2(x) > 0 for any x ∈ T1, the such functions can not satisfy hard-sorting of T1 ∪ T0 with respect to T1
Note that Propositions 4.8 , 4.9 , 4.10 and 4.11 imply that given affine functions a1, a2 hard-sorting T1 ∪ T0 ∪ {0} with respect to T1 ∪ {0}, all points x ∈ T1 must satisfy a1(x) ≤ 0 and a2(x) ≤ 0 with at least one of them being strict inequality. It is clear that each x ∈ T1 must satisfy inequalities a1(x) ≤ 0, a2(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 a1, a2 and weights w1, w2 satisfy hard-sorting of T1 ∪ T0 ∪ {0} with respect to T1 ∪ {0} then parity of weights must be same i.e. w1 = w2 = 1 or w1 = w2 = −1.
In the next section, we show that this result on gadget data-points gives us solution to the original 2-affine separability problem.

heading: 4.1.2 FROM GADGET DATA TO COMPLETE DATA
text: Note that if there is a solution to problem (P), say a1, a2 ∈ Rd+2 and w1, w2, w0, θ ∈ R, then by Lemma 4.5 , Lemma 4.12 and counterpositive of Remark 4.3 we have
1. Parity of w1, w2 is same. 2. w1 [ a1(x) ] + + w2 [ a2(x) ] + = 0 for all x ∈ S1 ∪ T1 due to requirement of hard-sorting.
Since parity ofw1, w2 is same so 2 above is satisfied if a1(x) ≤ 0 and a2(x) ≤ 0 for all x ∈ S1∪T1. Moreover, we require a1(x) > 0 or a2(x) > 0 for all x ∈ S0∪T0 because otherwise we will violate hard-sorting. Now as discussed earlier, −a1,−a2 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.

heading: 5 DISCUSSION
text: 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.

heading: A PROOFS OF AUXILIARY RESULTS
text: In this appendix, we provide proof of all auxiliary results.

heading: A.1 PROOF OF LEMMA 4.1
text: Suppose (α1, β1) and (α2, β2) are solution satisfying condition for 2-affine separability. Note that there is a data-point 0 ∈ S1 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
{[ − αT1 xi − β1 ] + + [ − αT2 xi − β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{ 12 , 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
η
[ − [ − αT1 x− β1 − y ] + − [ − αT2 x− β2 − z ] + + η ] + .
We claim that 2-ReLU NN with weights assigned as above solves the training problem (P).
1. For x ∈ S1, we have
f(x, 0, 0) = 1
η
[ − [ − αT1 x− β1 ] + − [ − αT2 x− β2 ] + + η ] + = 1
η [0 + 0 + η] = 1.
2. For x ∈ S0, we have
f(x, 0, 0) = 1
η
[ − [ − αT1 x− β1 ] + − [ − αT2 x− β2 ] + + η ] + .
Now note that [ − αT1 x− β1 ] + + [ − αT2 x− β2 ] + ≥ ,∀ x ∈ S0. So inner term of above expression is less than or equal to − + η. Since η ≤ 12 , the inner term is negative. Hence for all x ∈ S0, f(x, 0, 0) = 0.
3. For x = (0, l,m) ∈ T1, 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 ∈ T1. Hence f(x) = 1.
4. For x = (0, l,m) ∈ T0, 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 ∈ T0.
This proves existence of weights solving the training problem (P).

heading: A.2 PROOF OF LEMMA 4.4
text: Suppose points are hard-sorted as required by lemma with condition 1 of hard sorting. Then define := min x∈S0∪S0 w1 [ l1(x) ] + + w2 [ l2(x) ] + − c. By definition > 0. Then it is easy to check that
neural network f(x) = 2 [ −w1 [ l1(x) ] + −w2 [ l2(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 l1, l2, w1, w2, c satisfying either condition 1 or condition 2. This implies for all possible weights we either have
a) w1 [ l1(x) ] + + w2 [ l2(x) ] +
is not constant for all x ∈ S1 ∪ S1 or b) If w1 [ l1(x) ] + +w2 [ l2(x) ] +
= c for all x ∈ S1 ∪ S1 and some constant c, then same expression evaluated on x ∈ S0 ∪ S0 is not strictly on same side of c. If we choose l1, l2, w1, w2, c such that a) happens, then such weights will not solve training problem as their output of 2-ReLU NN for points p ∈ S1 ∪ S1 will be at least two distinct numbers which is an undesirable outcome. Specifically, we want θ [ w0 + w1 [ l1(x) ] + + w2 [ l2(x) ] + ] +
to evaluate to 1 for all x ∈ S1 ∪ S1 so we must have θ > 0 and w0 + w1 [ l1(x) ] + + w2 [ l2(x) ] +
take a constant positive value for all x ∈ S1 ∪ S1. Hence w1 [ l1(x) ] + + w2 [ l2(x) ] +
must be a constant for all x ∈ S1 ∪ S1. This requirement is violated in case a). If we choose l1, l2, w1, w2, c such that b) happens, then we can set w0, θ such that F (x) = θ [ w1 [ l1(x) ] + +w2 [ l2(x) ] + +w0 ] +
,w0+c > 0 and θ = 1w0+c . Since not all x ∈ S0∪S0 are strictly on one side, we conclude there exist x′ ∈ S0 ∪ S0 such that w1 [ l1(x ′) ] + + w2 [ l2(x ′) ] +
= c′ ≥ c hence F (x′) := θ [ w1 [ l1(x ′) ] + + w2 [ l2(x ′) ] + + w0 ] + ≥ 1 which is an undesirable outcome for a point with label 0. Since all choices of l1, l2, w1, w2, c satisfy either a) or b) so we conclude that there does not exist weights solving training problem of 2-ReLU NN.

heading: A.3 PROOF OF PROPOSITION 4.6
text: We assume that magnitude of the normal to these lines is equal i.e. ‖∇a1‖ = ‖∇a2‖ 6= 0. Note that we have two possible situations here: a1, a2 satisfy 1)a1(x) + a2(x) = c,∀ x ∈ R when normals point in opposite directions and 2) a1(x) − a2(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 w1 [ a1 ] + + w2 [ a2 ] +
can not hard-sort as required irrespective of the parity of weights w1, w2. Due to Remark 4.2, we just need to check for case {w1, w2} = {1, 1} and {w1, w2} = {1,−1}. More specifically, {w1, w2} = {−1,−1} yields a hard-sorting solution iff there exists a hard-sorting solution for {w1, w2} = {1, 1}. Equivalent argument can be made about the case {w1, w2} = {−1, 1} and {w1, w2} = {1,−1} Case 1: Normals point in opposite direction. Let a1 + a2 = c. Suppose c ≥ 0. Then it can be verified that
[ a1 ] + (x) + [ a2 ] + (x) =  c if c ≥ a1(x) ≥ 0 a1(x) if a1(x) ≥ c c− a1(x) if a1(x) ≤ 0.
By hard-sorting requirement, we need all five points in T1∪{0} should be in set {x : a1(x) ∈ [0, c]} and all points in T0 should not be in this set. Now observe that if c = 0, then the set {x : a1(x) = 0} is one dimensional, and therefore can not contain all the points of T1 ∪ {0}. Hence we must have c > 0. It can be seen that this is impossible to achieve by two parallel lines a1 = 0 and a1 = c for the given set up of data points T0 ∪ T1 ∪ {0}. Similarly when c < 0, then it can be verified that
[ a1 ] + (x) + [ a2 ] + (x) =  0 if c ≤ a1(x) ≤ 0 a1(x) if a1(x) ≥ 0 c− a1(x) if a1(x) ≤ c
Again, for hard-sorting, as in the previous case, we need all five points in T1 ∪ {0} should be in set {x : a1(x) ∈ [c, 0]} and all points in T0 should not be in this set which can not be achieved. Now consider case where parity of wi’s is different. When c ≥ 0, it can be verified that
[ a1 ] + (x)− [ a2 ] + (x) =  a1(x)− c if a1(x) ≤ 0 2a1(x)− c if 0 ≤ a1(x) ≤ c a1(x) if a1(x) ≥ c
It is clear that all five points in T1 ∪ 0 can not be on line a1(x) = δ for any constant δ. So this type of function can not hard-sort given points.
When c < 0. Then it can be verified that
[ a1 ] + (x)− [ a2 ] + (x) =  a1(x) if a1(x) ≥ 0 0 if 0 ≥ a1(x) ≥ c a1(x)− c if a1(x) ≤ c
For hard-sorting with this type of function, we again need all points in T1 ∪ {0} to be in set {x : a1(x) ∈ [c, 0]} while all remaining points to be outside this set which is not possible to be achieved by any affine function a1. Case 2: a1 − a2 = c. Suppose c ≥ 0. Then it can be verified that
[ a1 ] + (x)− [ a2 ] + (x) =  a1(x) if c ≥ a1(x) ≥ 0 c if a1(x) ≥ c 0 if a1(x) ≤ 0
If c = 0 then [ a1 ] + (x) − [ a2 ] +
(x) = 0 for all x ∈ R2. So this can not hard-sort data. Hence for hard-sorting we definitely need c > 0. Moreover, we need either 1) T1 ∪ {0} ⊂ {x : a1(x) ≤ 0} and T0 ⊂ {x : a1(x) > 0} or 2) T1 ∪ {0} ⊂ {x : a1(x) ≥ c} and T0 ⊂ {x : a1(x) < c}. So essentially the points in T1 ∪ T0 ∪ {0} must be separable by a line. This is not possible. Note that when c < 0, one can write a2 − a1 = −c and write similar functional form for [ a2 ] + −[
a1 ] +
. Now consider case when parity of weights wi’s is same. Again suppose c ≥ 0. Then one can verify that [
a1 ] + (x) + [ a2 ] + (x) =  0 if a1(x) ≤ 0 a1(x) if c ≥ a1(x) ≥ 0 2a1(x)− c if a1(x) ≥ c
Clearly, for hard-sorting we need strict separation by the line a1(x) = 0 which is not possible. When c < 0 then we can write a2 − a1 = −c and we will need strict separation at line a2(x) = 0 which is again not possible. Since in both cases, none of the parity combinations were able to achieve hard-sorting T1∪T0∪{0} w.r.t. T1 ∪ {0}, so we conclude the proof.

heading: A.3.1 PROOF OF PROPOSITION 4.6
text: Note that we have two possible situations here: a1, a2 satisfy 1)a1(x) + a2(x) = c,∀ x ∈ R when normals point in opposite directions and 2) a1(x) − a2(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 w1 [ a1 ] + + w2 [ a2 ] +
can not hard-sort as required irrespective of the parity of weights w1, w2. Due to Remark 4.2, we just need to check for case {w1, w2} = {1, 1} and {w1, w2} = {1,−1}. More specifically, {w1, w2} = {−1,−1} yields a hard-sorting solution iff there exists a hard-sorting solution for {w1, w2} = {1, 1}. Equivalent argument can be made about the case {w1, w2} = {−1, 1} and {w1, w2} = {1,−1} Case 1: Normals point in opposite direction. Let a1 + a2 = c. Suppose c ≥ 0. Then it can be verified that [
a1 ] + (x) + [ a2 ] + (x) =  c if c ≥ a1(x) ≥ 0 a1(x) if a1(x) ≥ c c− a1(x) if a1(x) ≤ 0.
By hard-sorting requirement, we need all five points in S1∪{0} should be in set {x : a1(x) ∈ [0, c]} and all points in S0 should not be in this set. Now observe that if c = 0, then the set {x : a1(x) = 0} is one dimensional, and therefore can not contain all the points of S1 ∪ {0}. Hence we must have c > 0. It can be seen that this is impossible to achieve by two parallel lines a1 = 0 and a1 = c for the given set up of data points S0 ∪ S1 ∪ {0}. Similarly when c < 0, then it can be verified that
[ a1 ] + (x) + [ a2 ] + (x) =  0 if c ≤ a1(x) ≤ 0 a1(x) if a1(x) ≥ 0 c− a1(x) if a1(x) ≤ c
Again, for hard-sorting, as in the previous case, we need all five points in S1 ∪ {0} should be in set {x : a1(x) ∈ [c, 0]} and all points in S0 should not be in this set which can not be achieved. Now consider case where parity of wi’s is different. When c ≥ 0, it can be verified that
[ a1 ] + (x)− [ a2 ] + (x) =  a1(x)− c if a1(x) ≤ 0 2a1(x)− c if 0 ≤ a1(x) ≤ c a1(x) if a1(x) ≥ c
It is clear that all five points in S1 ∪ 0 can not be on line a1(x) = δ for any constant δ. So this type of function can not hard-sort given points. When c < 0. Then it can be verified that
[ a1 ] + (x)− [ a2 ] + (x) =  a1(x) if a1(x) ≥ 0 0 if 0 ≥ a1(x) ≥ c a1(x)− c if a1(x) ≤ c
For hard-sorting with this type of function, we again need all points in S1 ∪ {0} to be in set {x : a1(x) ∈ [c, 0]} while all remaining points to be outside this set which is not possible to be achieved by any affine function a1. Case 2: a1 − a2 = c. Suppose c ≥ 0. Then it can be verified that
[ a1 ] + (x)− [ a2 ] + (x) =  a1(x) if c ≥ a1(x) ≥ 0 c if a1(x) ≥ c 0 if a1(x) ≤ 0
If c = 0 then [ a1 ] + (x) − [ a2 ] +
(x) = 0 for all x ∈ R2. So this can not hard-sort data. Hence for hard-sorting we definitely need c > 0. Moreover, we need either 1) S1 ∪ {0} ⊂ {x : a1(x) ≤ 0} and S0 ⊂ {x : a1(x) > 0} or 2) S1 ∪ {0} ⊂ {x : a1(x) ≥ c} and S0 ⊂ {x : a1(x) < c}. So essentially the points in S1 ∪ S0 ∪ {0} must be separable by a line. This is not possible. Note that when c < 0, one can write a2 − a1 = −c and write similar functional form for [ a2 ] + −[
a1 ] +
. Now consider case when parity of weights wi’s is same. Again suppose c ≥ 0. Then one can verify that [
a1 ] + (x) + [ a2 ] + (x) =  0 if a1(x) ≤ 0 a1(x) if c ≥ a1(x) ≥ 0 2a1(x)− c if a1(x) ≥ c
Clearly, for hard-sorting we need strict separation by the line a1(x) = 0 which is not possible. When c < 0 then we can write a2 − a1 = −c and we will need strict separation at line a2(x) = 0 which is again not possible. Since in both cases, none of the parity combinations were able to achieve hard-sorting S1∪S0∪{0} w.r.t. S1 ∪ {0}, so we conclude the proof.

heading: A.3.2 PROOF OF PROPOSITION 4.8
text: From Proposition 4.6 we obtain that w1a1 + w2a2 = c is a line irrespective of parity of w1, w2 and any value of c. Define set S+ := {x : a1(x) ≥ 0 and a2(x) ≥ 0}. Then {x ∈ S+ : w1 [ a1 ] + + w2 [ a1 ] +
(x) = c} is a one dimensional set. Now any 3 points in S1 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 S1 can not be in S+ while condition for hard-sorting holds.

heading: A.3.3 PROOF OF PROPOSITION 4.9
text: By Proposition 4.6, we know that w1a1 +w2a2 = c is a line irrespective of parity of weights w1, w2 and value of constant c. Case 1: Parity of w1, w2 is same. Suppose exactly p3, p4 are two points in S1 which satisfy required conditions. Suppose [ a1 ] +
(x) +[ a2 ] + (x) = c for all x ∈ S1. Then a1(pi)+a2(pi) = c, i = 3, 4. Note that c ≥ 0 and 0 ≤ a1(pi) ≤
c, i = 3, 4. We first claim that c > 0. Assume by contradiction, c = 0. In this case a1(p3) = a1(p4) = a2(p3) = a2(p4) = 0. Since p3, p4 are distinct points, this implies that {x : a1(x) = 0} and {x : a2(x) = 0} are the same line and this line passes through points p3 and p4. Since p9 is in affine hull of p3 and p4, we therefore have that a1(p9) = a2(p9) = 0. This clearly violates condition of hard-sorting. Thus c > 0. The observation that c > 0 together with Proposition 4.8 gives us that p1, p2 must be separated from p3, p4 by exactly one of the lines a1 = 0 and a2 = 0. (At least one line because of Proposition 4.8 i.e. we can not allow p1 to be in S+ := {x : a1(x) ≥ 0 and a2(x) ≥ 0} along with p3, p4. At most one line because of observation c > 0, so [ a1 ] + (p1) + [ a2 ] +
(p1) must equals c which is strictly positive quantity. Similar arguments can be made for p2). In essence, we get exactly two sub-cases:
1. Line a1(x) = 0 separates only p1 and a2(x) = 0 separates only p2. Equivalently, a1(p1) < 0 and a2(p2) < 0. Since a1(p1) < 0 ≤ a1(p3) so we conclude a1(p2) < a1(p4). But as noted before, we have a1(p4) ≤ c which implies a1(p2) < c. So [ a1 ] + (p2) + [ a2 ] +
(p2) = a1(p2) < c, contradiction to condition of hard-sorting.
2. a1 = 0 separates both p1, p2 and a2 = 0 separates none of p1, p2. Equivalently, a1(p1) < 0, a1(p2) < 0.[ a1 ] + (pi) + [ a2 ] +
(pi) = a2(pi), i = 1, 2. So a2(pi) = c, i = 1, 2. Hence a2 is constant for all points on line passing through p1, p2. Hence a2(p3) = a2(p4). Hence a1(p3) = a1(p4). Again, since p3 and p4 are distinct points and p9 is on the affine hull of p3 and p4, this implies that a1(p3) = a1(p9) and a2(p3) = a2(p9), and hence p3, p4 and p9 will have the same output, a contradiction to condition of hard-sorting.
Similar arguments can be made about pairs {p1, p2}, {p1, p3} and {p2, p4}. Suppose p2, p3 ∈ S+. Then {x : a1(x) + a2(x) = c} line passes through p2, p3. Note that this line strictly separates p1, p4. So we may assume a1(p4) + a2(p4) > c. Also by Proposition 4.8, p4 must be separated from p2, p3 by at least one of the lines a1 = 0, a2 = 0. So we may assume a1(p4) < 0 ⇒ a2(p4) > c ⇒ [ a1 ] + (p4) + [ a2 ] +
(p4) > c. Contradiction to condition of hardsorting. Similar argument can be made about pair {p1, p4}. Case 2 Parity of w1, w2 is different. Suppose [ a1 ] + − [ a2 ] +
= c. Suppose c > 0. (We will argue c = 0 separately. Arguments for c < 0 will go through in similar fashion by interchanging a1, a2 and replacing c by −c). Suppose p3, p4 ∈ S+ := {x : a1(x) ≥ 0, a2(x) ≥ 0}. It is clear that for hard-sorting a1(x) ≥ c > 0,∀ x ∈ {p1, p2}. So by Proposition 4.8, we must have a2(x) < 0,∀ x ∈ {p1, p2}. This implies a1(x) = c line passes through p1, p2. So a1(p3) = a1(p4) ⇒ a2(p3) = a2(p4). So lines a1 = 0, a2 = 0 are parallel to line passing through p3, p4. Hence [ a1 ] + (p9) − [ a2 ] +
(p9) = c, a contradiction to condition of hard-sorting. Suppose c = 0. Then a1(x)−a2(x) = 0 line passes through p3, p4. Consider q, point of intersection of lines a1 = 0, a2 = 0 (These lines can’t be parallel. Otherwise line a1− a2 = 0 will be parallel to line a1 = 0 and a2 = 0. We know that a1 − a2 = 0 passes through p3, p4. So a1 = 0 and a2 = 0 will be parallel to line passing through p3, p4. This implies p9 will have same output as p3, p4. This is contradiction to condition of hard-sorting. So a unique point, q, exists). Point q trivially lies on line a1 − a2 = 0 or equivalently on the line passing through p3, p4. We claim that p9 /∈ S+. Assume by contradiction that p9 ∈ S+. We know that a1 − a2 passes through p3, p4 and p9 is in affine combination of p3, p4 so a1(p9)− a2(p9) = 0. This implies [ a1 ] +
(p9)−[ a1 ] +
(p9) = 0, a contradiction to condition of hard-sorting. So p9 must not be in S+. Since p3, p4 ∈ S+ and p9 /∈ S+ so we obtain that q must lie on line segment p9p3. Hence lines a1 = 0, a2 = 0 must separate p3, p9. So a1(p9) ≤ 0, a2(p9) ≤ 0 ⇒ [ a1 ] + (p9) − [ a2 ] +
(p9) = 0. Since c = 0, this is contradiction to condition of hard-sorting. Similar arguments can be made about pairs {p1, p2}, {p1, p3} and {p2, p4}. Suppose p2, p3 ∈ S+. Then by Proposition 4.8, either a1(p1) < 0 or a2(p1) < 0. Without loss of generality, we may assume a1(p1) < 0. Since a1(p3) ≥ 0 we get a1(p3) > a1(p1) ⇒ a1(p4) > a1(p2) ≥ 0. Since a1(p4) > 0, by Proposition 4.8, we conclude a2(p4) < 0 ≤ a2(p3)⇒ a2(p1) >
a2(p2) ≥ 0. Now [ a1 ] + (p1)− [ a2 ] + (p1) = −a2(p1) < 0 and [ a1 ] + (p4)− [ a2 ] + (p4) = a1(p4) > 0. So we get a contradiction. Similar argument can be made about pair {p1, p4}.

heading: A.3.4 PROOF OF PROPOSITION 4.10
text: By Proposition 4.6, we know that w1a1 +w2a2 = c is a line irrespective of parity of weights w1, w2 and value of constant c. Case 1: Parity of w1, w2 is same. Suppose [ a1 ] + (x) + [ a2 ] +
(x) = c for all points x ∈ S1 ∪ {0}. We assume c > 0. (We will argue about c = 0 separately). Suppose p1 ∈ S+ := {x : a1(x) ≥ 0, a2(x) ≥ 0}. Then by Propositions 4.8, 4.9, we conclude that all points in x ∈ S1 \ {p1} must satisfy exactly one of the following inequalities: a1(x) ≥ 0, a2(x) ≥ 0. (At most one inequality because of Propositions 4.8, 4.8 i.e. we can not allow pi, i = 2, 3, 4 to be in S+ := {x : a1(x) ≥ 0 and a2(x) ≥ 0} along with p1. At least one inequality because of observation c > 0, so [ a1 ] + (p1) + [ a2 ] +
(p1) must equals c which is strictly positive quantity.) Hence there are two distinct cases to consider:
1. Any two of S1 \ {p1} satisfy a1(x) ≥ 0, a2(x) < 0. Remaining one satisfy a1(x) < 0, a2(x) ≥ 0. So a2(x) ≥ 0 is satisfied by only two points in S1 one of which is p1. By arrangement of points in set S1 it is clear that either 1) a2(pi) ≥ 0, i = 1, 2⇒ a1(pi) ≥ 0, i = 1, 3, 4 or 2) a2(pi) ≥ 0, i = 1, 3⇒ a1(p1) ≥ 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, [ a1 ] + (p3) + [ a2 ] + (p3) = [ a1 ] + (p4) + [ a2 ] +
(p4). Since a2(pi) < 0, i = 3, 4 so we get a1(p3) = a1(p4). This implies a1(p1) = a1(p2). Contradiction to assumptions of case 1.
2. All points in S1 \ {p1} satisfy a1(x) ≥ 0, a2(x) < 0. Then for satisfying conditions of hard-sorting, we must have [ a1 ] + (pi) + [ a2 ] +
(pi) = a1(pi) = c, i = 2, 3, 4. Clearly p2, p3, p4 are not collinear so this is impossible.
Similar arguments can be made about p2, p3, p4 when c > 0. Suppose c = 0 and p1 ∈ S+. Then line a1 = 0, a2 = 0 passes through p1. Moreover [ a1 ] +
(pi) +[ a2 ] +
(pi) = 0, i = 2, 3, 4 implies a1(pi) ≤ 0, a2(pi) ≤ 0, i = 2, 3, 4. Now note that p4 can not lie on the line {x : a1(x) = 0} because otherwise {x : a1(x) = 0} will be line passing through p1, p4 hence strictly separate p2, p3. So either one of p2, p3 will satisfy a1(x) > 0 which is contradiction to the fact that [ a1 ] + (x) + [ a2 ] +
(x) = 0 for all x ∈ {p2, p3}. Similarly p4 can not lie on {x : a2(x) = 0}. Hence a1(p4) < 0, a2(p4) < 0 and a1(p1) = 0, a2(p1) = 0. Since 0, p1, p4 are collinear, we get that a1(0) > 0, a2(0) > 0. But then [ a1 ] + + [ a2 ] +
(0) > 0. This contradicts condition of hard-sorting. Suppose p2 ∈ S+. Then line a1 = 0, a2 = 0 passes through p2. Moreover [ a1 ] + + [ a2 ] + (pi) = 0, i = 1, 3, 4 implies a1(p1) ≤ 0, a2(p1) ≤ 0. So by colinearity of p2, p1, p8 we conclude that a1(p8) ≤ 0, a2(p8) ≤ 0. Then [ a1 ] + (p8) + [ a2 ] +
(p8) = 0 which is contradiction to condition fo hard-sorting. For p3 or p4 while c = 0: arguments similar to that of p2 can be made. Case 2: Parity of w1, w2 is different. Suppose p1 ∈ S+ and [ a1 ] + (x) − [ a2 ] +
(x) = c for all x ∈ S1 ∪ {0}. Assume c > 0. Proof for c < 0 will follow from this case with a1, a2 exchanged and c replaced with −c. (We will argue for c = 0 separately). Since c > 0, we conclude a1(pi) ≥ c > 0, i = 2, 3, 4. By statement of Proposition it implies a2(pi) < 0, i = 2, 3, 4. Then [ a1 ] + (pi) + [ a2 ] +
(pi) = a1(pi), i = 2, 3, 4. Since p2, p3, p4 are not collinear points, so we get contradiction to condition of hard-sorting. Similar arguments will work for p2, p3, p4. Suppose c = 0 and p1 ∈ S+. If a1(p2) > 0 then a2(p2) > 0 but only p1 ∈ S+ so a1(p2) ≤ 0, a2(p2) ≤ 0. Similarly a1(pi) ≤ 0, a2(pi) ≤ 0, i = 3, 4. By Proposition 4.9, we have that either
a1(p4) < 0 or a2(p4) < 0. Without loss of generality, we assume a1(p4) < 0. Since p4, p1, 0 are collinear so a1(0) > 0. Since c = 0 and [ a1 ] + (0)− [ a2 ] +
(0) = c so we conclude that a2(0) > 0. So a1 − a2 = 0 line passes through 0, p1. Note that by collinearity of p3, p1, p5 and ai(p3) ≤ 0, ai(p1) = 0 for i = 1, 2 we obtain a1(p5) ≥ 0, a2(p5) ≥ 0. Similarly by collinearity of p2, p1, p8, we obtain a1(p8) ≥ 0, a2(p8) ≥ 0. So 0, p1, p5, p8 ∈ S+. Moreover [ ai ] +
(x) = ai(x),∀ x ∈ S+. So we get [ a1 ] + (x) − [ a2 ] +
(x) = a1(x) − a2(x) for all x ∈ {0, p1, p5, p8}. Since a1 − a2 = 0 lines passes through 0, p1, it separates p5, p8. So we get contradiction. Suppose p2 ∈ S+ and c = 0. So we have a1(p1) ≤ 0, a2(p1) ≤ 0. By collinearity of p2, p1, p8 we get a1(p8) ≤ 0, a2(p8) ≤ 0 ⇒ [ a1 ] + − [ a2 ] +
(p8) = 0 which is a contradiction to assumption of hard-sorting. Similar arguments can be made about p3, p4.

heading: A.3.5 PROOF OF PROPOSITION 4.11
text: Case 1: Parity of w1, w2 is same. Suppose p1 ∈ S+ := {x : a1(x) > 0}. Let T+ := {x : a2(x) > 0}. Then by Propositions 4.8, 4.9, 4.10, we have a2(p1) < 0. So [ a1 ] + (p1)+ [ a2 ] +
(p1) = c > 0. For hard-sorting, each x ∈ S1 must be on strictly on positive side of exactly one of the lines. So we conclude that S+, T+ is a partition of S1. Note that if there are any three points in set S1 ∩S+ then a1(x) will have at least two distinct values for points in set S1 ∩ S+ because of non-collinearity. For points x ∈ S+ ∩ S1, we have[ a1 ] + (x) + [ a2 ] +
(x) = a1(x). So we have contradiction to condition of hard-sorting. Similarly there can not be any three points in T+ ∩ S1. So both S+, T+ must contain exactly two points from S1. Clearly {p2, p3} or {p1, p4} can not be in S+ or T+. So the partition has to be either 1) {p1, p2}, {p3, p4} or 2) {p1, p3}, {p2, p4}. If 1) then lines a1 = 0, a2 = 0 are parallel to line passing through p1, p2. So [ a1 ] + + [ a2 ] +
(pi) 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 w1, w2 is different. If a1(p1) > 0 then a2(p1) < 0 (By Propositions 4.8, 4.9, 4.10). Then [ a1 ] + (x) − [ a2 ] + (x) = a1(p1) for all x ∈ S1. This implies a1(x) > 0 for all x ∈ S1 ⇒ a2(x) < 0 for all x ∈ S1. Then[ a1 ] + (x) − [ a2 ] +
(x) = a1(x) for all x ∈ S1. But then a1(x) can not be a constant number for x ∈ S1 which yields a contradiction.

heading: A.4 PROOF OF LEMMA 4.12
text: Lemma 4.5 yields that any hard-sorting a1, a2 must satisfy a1(x) ≤ 0, a2(x) ≤ 0 for all x ∈ T1 ∪ {0}. Suppose parity of w1, w2 is different. Since a1 and a2 satisfy hard-sorting of gadget so we have[ a1(x) ] + − [ a2(x) ] +
= c,∀ x ∈ T1. Due to Lemma 4.5, c = 0. Then to fulfill hard-sorting condition, we need [ a1(x) ] + − [ a2(x) ] + > 0∀ x ∈ T0. (Case for “ [ a1(x) ] + − [ a2(x) ] + < 0” will have same proof with all a1 exachanged by a2 in next 3 lines.) This implies a1(x) > 0 for all x ∈ T0. In particular, we note that a1(p7) > 0, a1(p10) > 0. Moreover, a1(p1) ≤ 0 as p1 ∈ T1. But p7, p1, p10 are collinear points so p1 is not separable from p7, p10 by an affine function. So we get a contradiction to the assumption that parity of weights w1, w2 is different.

heading: A.5 PROOF OF COROLLARY 4.15
text: The reduction is similar except the labels need to be changed from R to Rj . 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 wk,1, wk,2 and bias weight wk,0. We can set wk,1 = wk,2 = −1 and wk,0 = 0 for all k ∈ [j] \ {1}. This yields the output 0 at all nodes k ∈ [j] \ {1}, irrespective of the affine functions a1, a2 in the first layer. Now, first node
satisfied to global optimality will yield solution a1, a2, w1,1, w1,2, w1,0. By the reduction, we know that −a1,−a2 after ignoring last two co-ordinates yield solution to 2-affine separability problem.

heading: A.6 PROOF OF THEOREM 3.3
text: We will use result by Edelsbrunner et al. (1986). This work shows that given a set of points {xi}i∈N in Rd we can enumerate all possible partition created by linear separators in O(Nd) time. Suppose we partition [N ] into Q1/Q1 and Q2/Q2 such that a1(x) = 0 separates Q1/Q1 and a2(x) = 0 separates Q2/Q2. We define T1 = Q1 ∩ Q2, T2 = Q1 ∩ Q2, T3 = Q1 ∩ Q2 and T4 = Q1 ∩ Q2. Let z = (a1, a2, w1, w2, w0, θ). Then objective function can be written as
f(z) = ∑ i∈T1 ( θ [ w0 + w1a1(x i) + w2a2(x i) ] + − yi )2 + ∑ i∈T2 ( θ [ w0 + w2a2(x i) ] + − yi )2 + ∑ i∈T3 ( θ [ w0 + w1a1(x i) ] + − yi )2 + ∑ i∈T4 ( θ [ w0 ] + − yi
)2 Now we can partition T1, T2, T3 into T1i, T2i, T3i where i = 1, 2 respectively. For Tj1, ReLU terms in the objective, f , are constrained to be non-negative and for Tj2, ReLU terms are constrained to be non-positive, j = 1, 2, 3. Observe that it suffices to check for θ, w1, w2 = ±1. We will divide the optimization problem in two cases w0 ≥ 0 and w0 ≤ 0. In both cases, we will solve for convex program for all possible cases of θ, w1, w2 ∈ {−1, 1}. So there are totally eight cases for each case of w0. 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 possibleQ1/Q1 andQ2/Q2 which takeO(N
d) time each. Also total number of possible partitions is O(Nd). So total O(N2d) time to enumerate all possible combinations of Q1, Q2. For each enumerated combination, Q1, Q2, we again need to enumerate all possible partitions of Ti which are Ti1/Ti2, i = 1, 2, 3. Using the same result Edelsbrunner et al. (1986), we know that this can be done in O(|Ti|d) = O(Nd) time again. We have to consider all possible combinations of partitions of Ti, hence we need O(N3d) time to enumerate all possible combinations. Since we need to solve O(N3d) convex programs for each choice of Q1, Q2 therefore we need to solve O(N5d) 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 θ, w1, w2 for some value in {−1, 1}. Then objective can be written as
f(z) = ∑ i∈T11 ( θ(w0 + w1a1(x i) + w2a2(x i))− yi )2 + ∑ i∈T21 ( θ(w0 + w2a2(x i))− yi )2
+ ∑ i∈T31 ( θ(w0 + w1a1(x i))− yi )2 + ∑ i∈T4 ( θ [ w0 ] + − yi )2 + ∑ i∈T12∪T22∪T32 (0− yi)2
subject to constraints
a1(x i) ≥ 0, i ∈ Q1
a1(x i) ≤ 0, i ∈ Q1
a2(x i) ≥ 0, i ∈ Q2
a2(x i) ≤ 0, i ∈ Q2
w0 + w1a(x i) + w2a2(x i) ≥ 0, i ∈ T11 w0 + w1a(x i) + w2a2(x i) ≤ 0, i ∈ T12
w0 + w2a2(x i) ≥ 0, i ∈ T21
w0 + w2a2(x i) ≤ 0, i ∈ T22
w0 + w1a1(x i) ≥ 0, i ∈ T31
w0 + w1a1(x i) ≤ 0, i ∈ T32
Moreover, we add constraint w0 ≥ 0 or w0 ≤ 0 and change the [ w0 ] +
term in objective with w0 or 0 respectively. Every program has 2d + 3 variables in a1, a2, w0. Total number of constraints is at most 3N + 1 so we conclude that this program can be solved in poly(N,d) time. Since we enumerate over all possible partitions Q1, Q2 and Ti1, i = 1, 2, 3 hence we conclude that best solution out of all obtained solutions will be globally optimal.

heading: A.7 PROOF OF THEOREM 3.4
text: We will show this for 0/1 classification problem. But same ideas can be applied to a general output labels as well. Lets define S1 := {i : yi = 1} and S0 := {i : yi = 0}. Let v ∈ Rd be a random vector on a unit sphere, generated from a lebesgue measure. We will use the direction v in each node of the first hidden layer of ReLU network. We claim that vTxi, i ∈ [N ] are distinct numbers with probability 1 with respect to the lebesgue measure. Number of hyperplanes(or directions for normal vectors) in Rd that contain two or more data-points
≤ min{d+1,N}∑
i=2
( N i ) ≤ 2N . Since N is finite so there are finitely many directions. Probability of
selecting anyone of these 2N directions from a lebesgue measure on unit sphere is zero. So we get the claim. Now we claim that, at most N nodes are needed in first hidden layer to generate an output f(x) :=∑ j wj [ aj ] +
(x) which hard-sorts the data. Once this is achieved, setting w0, θ is trivial in the following way. Suppose we hard-sorted the data such that if i ∈ S1 then, we will make sure that f(xi) = 1 otherwise f(xi) < 1. This is clearly a hard-sorting solution. We will set w0 := −max
i∈S0 f(xi). Definition of w0
and hard-sorting property of f yields that w0 > −1. We know that w0 + f(xi) ≤ 0, for all i ∈ S0 whereas w0 + f(xi) = 1 + w0 > 0 for all i ∈ S1. After setting θ = 11+w0 it is easy to see that this choice of w0, θ yields the final solution. The only thing that remains to show is that we can obtain such solution aj , wj in polynomial time such that f hard-sorts the data and number of distinct nodes, or equivalently number of distinct functions aj required is at most N . Suppose zi = vTxi. By earlier claim, {zi}i∈[N ] are distinct numbers. Suppose zi are sorted in increasing order i.e. zi+1 > zi then, in one loop over the data, we can find required solution {aj , wj}j∈[J] and J ≤ N . We present an exact procedure to find aj , wj below. Note that data is sorted according to zi. We define z0 := z1 − 1, y0 = 0. Current piece of piecewise linear function f =
∑ j wj [ aj ] + is stored in variable g. In particular, at each iteration f(xi) = g(xi).
• Initialization: We skip all data points until we hit i such that yi = 1. Set a1(x) = 1
zi−zi−1 (v Tx − zi−1), w1 = 1 and g(x) = 0 + w1a1(x). Note that i could be 1 and we have defined z0, y0 so a1(x) is well defined. Without loss of generality, we assume that y1 = 1. Current number of nodes is set in the variable j initialized as j = 1.
• Loop over data: For i = 1 to N-1 – Case 1: If yi+1 = yi = yi−1 then,
skip the next steps and start with i = i+ 1. – Case 2: If yi+1 = yi 6= yi−1 and yi = 1 then,
set aj+1(x) = g(x)− 1, wj+1 = −1, g(x) = 1, j = j + 1. Skip the next steps an start with i = i+ 1
– Case 3: If yi+1 = yi 6= yi−1 and yi = 0 then, skip the next steps and start with i = i+ 1.
– Case 4: If yi+1 6= yi and yi = 0 then, set aj+1(x) = 1−g(xi+1) zi+1−zi (v
Tx − zi), wj+1 = 1, g(x) = g(x) + wj+1aj+1(x), j = j + 1. Skip the next steps an start with i = i+ 1.
– Case 5: If yi+1 6= yi and yi = 1 then, set aj+1(x) = g(x)− 1 + vTx− zi, wj+1 = −1, g(x) = 1 + zi − vTx, j = j + 1. Skip the next steps an start with i = i+ 1.
We claim that in the algorithm presented above, for every iteration i, we compute new function aj in such a way that [ aj ] + (xk) = 0 for all k less than current iteration, say i. We also have
that [ aj ] + (xi) is set in so that newly updated f satisfies f(xi) { = 1 if yi = 1 < 1 otherwise . Finally, newly computed g is an affine function with normal vector which is 1)in direction of −v if yi = 0 and 2) in direction v or 0 when yi = 1. We will prove these facts by induction on i. We will call newly computed g in each case as gnew to distinguish between old and new function, g. Similarly after addition of a new node, the updated f will called as fnew. This is clearly true for i = 1 i.e. a1(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(xk) {
= 1 for k ≤ i and yi = 1 < 1 for k ≤ i and yi = 0 . So aj(x) = f(x)− 1 ≤ 0 for all x ∈
{x1, . . . , xi} as required. Moreover g(xi+1) > 1 because vTxi > vTxi−1 and g(xi) > g(xi−1) then, g must have normal in +v direction. Therefore, we obtain g(xi+1) > g(xi) = 1 because vTxi+1 > vTxi. Hence we conclude that newly added function, aj(x) satisfied aj(xi+1) > 0
so fnew(xk) = f(x) + wj [ aj ] + = { 1 for k = i+ 1 f(xk) for k ≤ i . Finally at x i+1 we have gnew(x) =
f(x) +wjaj(x) = 1 so the normal is 0. This is valid since yi+1 = 1. This proves induction for case 2. For case 4, since yi = 0 so g must be an affine function in−v direction at xi. Since vTxi+1 > vTxi so we obtain g(xi+1) < g(xi) < 1. So 1−g(x i+1)
zi+1−zi is a positive scalar. Moreover, we have v Txk ≤ zi for all k ≤ i. So [ aj ] +
(xk) = 0 for all k ≤ i. Also aj(xi+1) = 1 − g(xi+1) > 0 therefore fnew(x i+1) = f(xi+1) + [ aj ] + (xi+1) = g(xi+1) + [ aj ] +
(xi+1) = 1. Finally, at xi+1 we have that normal vector of gnew must be either in direction ±v or 0 because normal of aj is in direction +v and g has normal either in direction ±v or is 0. Since g(xi) = f(xi) = fnew(xi) < fnew(xi+1) = gnew(x
i+1) therefore we conclude that normal must be in the direction +v. This is valid since yi+1 = 1. This proves induction for case 4. For case 5, since aj(x) = g(x) − 1 + vTx − zi, we can see that aj(xk) ≤ 0 for k ≤ i because vTxk ≤ zi and f(xk) ≤ 1. So we immediately get fnew(xk) = f(xk) for all k ≤ i. Since yi = 1 so g(x) has normal either in direction +v or 0. In both cases, g(xi+1) ≥ 1. So we get that aj(x
i+1) ≥ 0. Hence gnew(xi+1) = g(xi+1) + wjaj(xi+1) = 1 + zi − zi+1 < 1. Finally, at xi+1 we have that normal vector of gnew must be either in direction ±v or 0 because of the form of aj and inductive hypothesis on f . Since gnew(xi) = 1 > gnew(xi+1) so normal must be in −v direction which is valid since yi+1 = 0. This proves induction for case 5.
Since induction holds for all i so f(x) = ∑ j∈J wj [ aj ] + (x) satisfies f(xk) = { 1 if yk = 1 < 1 if yk = 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, aj are affine functions so there addition reduces to addition of vectors which can be done efficiently.

Review summaries:
The main result of this work is to prove that a two-layer neural network with 2 hidden neurons in the first layer and 1 hidden neuron in the second layer is NP-hard to train when all activation functions are ReLU. Similar results with the hard-thresholding activation function were proved by Blum & Rivest in 1988. The main proof consists of a reduction from the 2-hyperplane separability problem which was known to be equivalent to NNs with hard-thresholding activation functions.