The Computational Complexity of Training ReLU(s)

Our Results

We prove both hardness results as well as algorithmic results for training a single ReLU as well as depth-2 ReLUs with $k$ units. In terms of hardness, we prove NP-hardness results for the ReLU training problem showing that this problem is hard even for a single ReLU, not only to solve exactly but also to approximate (Section 2). In Section 3, we prove that, in contrast to the case of single ReLU, training 2 ReLUs is NP-hard even in the realizable caseFor completeness we provide a proof in Appendix B that training a single ReLU can be done in polynomial time in the realizable case.. We remark that this latter result also yields, as an immediate corollary, NP-hardness for training networks considered in [BDL18]. Our proof is shorter and arguably simpler than the proof appearing in [BDL18] altough their result also applies to the case of $k>2$ whereas ours hardness result only applies when $k=2$.

On the algorithmic side, we show, in Section 4, that depth-2 ReLUs can be properly (agnostically) learned in time $2^{(k/\epsilon)^{O(1)}}n^{O(1)}$ provided that the inputs and weights of the units belong to the unit ball (see Section 4 for precise learning-theoretic definitions). To the best of our knowledge, only improper learning algorithms were known before [GKKT17]. The insight here is very simple: standard generalization bounds (similar to those used in [GKKT17]) imply that it suffices to consider only $(k/\varepsilon)^{O(1)}$ samples. We then observe that the algorithm of [ABMM18] runs in exponential time in the number of samples. Putting these together immediately results in the proper learning algorithm.

We additionally show that, when the coefficients $\alpha_{j}$’s are all positive, they can be reliably properly learned (see Subsection 4.5 for more details) in similar running time. For the reliable model, we need to also take the advantage of the biases to ensure that there are few false positives. We remark here that Goel et al. [GKKT17] did not allow bias in their ReLUs and hence our algorithm for the reliable model would still be improper for their setting; nevertheless, our output (ReLUs with biases) is still arguably simpler than that of [GKKT17] (which is a “clipped” of a low degree polynomial). We note that, similar to [GKKT17], our algorithms work also for more general loss functions, as long as they are convex and $O_{k}(1)$-Lipschitz; we only focus on the squared loss for the simplicity of presentation.

Our lower bounds and algorithms contribute to the quest to understand how neural networks can be trained efficiently despite NP-hardness results. Specifically, while we prove NP-hardness results for training ReLUs, our learning results (paralleling those of [GKKT17] for improper learning) show that efficient trainingA proper learning algorithm immediately yields a polynomial time training algorithm with $\varepsilon$ additive error for any constant $\varepsilon>0$ (i.e., an additive PTAS). (up to small additive errors) is possible when weights and inputs of bounded norms are concerned. The exponential dependency of our algorithms on $k/\epsilon$ makes them impractical, and we believe it is of interest to find faster algorithms for properly learning ReLUS.

Hardness of Training a Single ReLU

We start by showing NP-hardness of training a single ReLU:

ReLU training problem for a neural network consisting of a single ReLU is NP-hard.

For the simplicity of exposition, we will assume in all our hardness proofs (in this section and Section 3) that the biases are equal to zero. In Appendix A, we explain how our proofs can be easily extended to handle non-zero biases.

We reduce the set cover problem to the training ReLU problem. Recall that, in the set cover problem, we are given a set $U=\{1,\ldots,N\}$ along with a family $\mathcal{S}=\{S_{1},\ldots,S_{M}\}$ of $M$ subsets of $U$. Our goal is to determine if one can choose $k$ subsets from $\mathcal{S}$ whose union equals $\mathcal{S}$. Set cover is well known to be NP-hard.

We consider a ReLU with $n=M+2$ variables. For each $S_{i}\in\mathcal{S}$, we have a variable $w_{S_{i}}$. We also have two dummy variables $w_{1}$ and $w_{\epsilon}$. Let $\alpha_{1}=1$ and $\epsilon=0.01/m^{2}$.

We introduce the following training points. First, for each $i\in U$, add an $(M+2)$-dimensional vector having $1$ for the coordinate corresponding to the dummy variable $w_{1}$, $1$ in all coordinates that correspond to a subset in $S$ containing $i$ and to all other coordinates. We label this vector by . This labeled data point corresponds to the constraint

Second, for every $j\in[M]$, add an $(M+2)$-dimensional vector having $1$ in the $S_{j}$-th location, $1$ in the coordinate corresponding to $w_{\epsilon}$ and for all other coordinates. We label it by $\epsilon$. This corresponds to

We then add a vector having $1$ in the coordinate corresponding to $w_{1}$ and elsewhere. We label these vectors by $1$. This corresponds to

We also add $(k+1)$ vectors having $1$ in the coordinate corresponding to $w_{\epsilon}$ and elsewhere. We label these vectors by $\epsilon$. These vectors correspond to $(k+1)$ copies of the constraint

Finally, we set the target error to be $\epsilon^{2}k$ where $k$ is the target value in the set cover instance. Clearly, this reduction runs in polynomial time.

We now prove the correctness of this reduction.

(YES Case) Assume that there is a set cover of size $k$ consisting of the subsets $S_{j_{1}},\ldots,S_{j_{k}}$ in $\mathcal{S}$. Assigning $w_{S_{j_{1}}}=w_{S_{j_{2}}}=\ldots=w_{S_{j_{k}}}=-1,w_{1}=1$, $w_{\epsilon}=\epsilon$ and to all other variables results in an error of $\epsilon^{2}\cdot k$. This is because exactly $k$ of the constraints from (3) are violated and each violated constraint contributes $\epsilon^{2}$ to the squared error. All other constraints are satisfied.

(NO Case) Suppose contrapositively that there is a weight vector $\mathbf{w}$ that results in an error of at most $\epsilon^{2}k$. First, observe that $w_{1}\geq 0.9$; otherwise, the squared error from (4) is more than $(0.1)^{2}\geq\epsilon^{2}k$. Observe also that $w_{\epsilon}\leq 0.2/m$; otherwise, the squared error from (5) must be more than $(0.2/m-\epsilon)^{2}\geq(0.1/m)^{2}>\epsilon^{2}k$. Moreover, notice that $w_{\epsilon}$ must be non-negative, since otherwise the $(k+1)$ copies of (5) must incur total error of $(k+1)\epsilon^{2}>\epsilon^{2}k$.

Our main observation is that the family $\mathcal{S}_{<-w_{\epsilon}}=\{S_{j}:w_{S_{j}}<-w_{\epsilon}\}$ is a set cover. The reason is as follows: if there is an element $i\in U$ that is not covered by $\mathcal{S}_{<-w_{\epsilon}}$, then $\sum_{i\in S_{j}}w_{S_{j}}\geq-w_{\epsilon}\cdot m\geq-0.2$, which means that the corresponding constraint (2) for $i$ will incur already a squared error of at least $(0.7)^{2}>\epsilon^{2}k$ (recall that $k$ is no larger than $m$). Thus, the observation follows.

The last step of the proof is to show that the family $\mathcal{S}_{<-w_{\varepsilon}}$ contains at most $k$ subsets. To see that this is the case, observe that, for every $S_{j}\in\mathcal{S}_{<-w_{\varepsilon}}$, we have $[w_{\epsilon}+w_{S_{j}}]_{+}=0$, meaning that the corresponding constraint (3) incurs a squared error of $\epsilon^{2}$. Since the total squared error is at most $\epsilon^{2}k$, we can immediately concludes that at most $k$ subsets belong to $\mathcal{S}_{<-w_{\varepsilon}}$.

Thus, $\mathcal{S}_{<-w_{\varepsilon}}$ is a set cover with at most $k$ subsets, which completes the NO case of the proof. ∎

We remark that the above proof (and also that of Theorem 2 below) also works for the case where $\alpha_{1}$ is treated as an unknown. This is because, if $\alpha_{1}=-1$, then the error incurred in (4) (resp. in (8) below) already exceeds the target error. Thus, it must be that $\alpha_{1}=+1$.

The reduction above coupled with the fact that set cover is hard to approximate within a factor $O(\log|U|)$ [Fei98] immediately implies that the problem of approximating the minimum training error to within a factor of $O(\log(nm))$ is also hard. In this subsection, we will substantially improve this inapproximability ratio to an almost polynomial (i.e. $(nm)^{1/\text{poly}\log\log(nm)}$) factor:

Given an instance of the single ReLU training problem, it is NP-hard to approximate the minimum squared error to within a factor of $(nm)^{1/(\log\log(nm))^{O(1)}}$.

To prove Theorem 2, we will reduce from the Minimum Monotone Circuit Satisfiability problem, which is formally defined below.

A monotone circuit is a circuit where each gate is either an OR or an AND gate. We use $|C|$ to denote the number of wires in the circuit.

In the Minimum Monotone Circuit Satisfiabilityi (MMCSi) problem, we are given a monotone circuit of depth $i$, and the objective is to assign as few Trues as possible to the input wires while ensuring that the circuit is satisfied (i.e. output wire is evaluated to True).

For any monotone circuit $C$, we use $\operatorname{OPT}_{\textsc{MMCS}}(C)$ to denote the optimum of the MMCS problem on $C$, i.e., the smallest number of input wires need to be set to True so that $C$ is satisfied.

The hardness of approximating MMCS has long been studied (e.g. [ABMP01, DS04]). By now, this problem is known to be NP-hard to approximate to within a factor of $|C|^{1/(\log\log|C|)^{O(1)}}$:

$\textsc{MMCS}_{3}$ is NP-hard to approximate to within $|C|^{1/(\log\log|C|)^{O(1)}}$ factor.

Dummy Variable Constraint. We add the following constraint

Input Wire Constraint. For each input wire $i$, we add the constraint

Output Wire Constraint. For the output wire $o$, we add the constraint

OR Gate Constraint. For each OR gate with input wires $i_{1},\dots,i_{k}$ and output wire $j$, we add the constraint

AND Gate Constraint. For each AND gate with input wires $i_{1},\dots,i_{k}$ and output wire $j$, we add the following $k$ constraints:

We will now show that the minimum squared training error is exactly $\operatorname{OPT}_{\textsc{MMCS}}(C)\cdot\varepsilon^{2}$. First, we will show that the error is at most $\operatorname{OPT}_{\textsc{MMCS}}(C)\cdot\varepsilon^{2}$. Suppose that $\phi$ is an assignment to $C$ with $\operatorname{OPT}_{\textsc{MMCS}}(C)$ Trues that satisfies the circuit. We assign $w_{\epsilon}=\epsilon$, and, for each wire $j$, we assign $w_{j}$ to be 1 if the wire $j$ is evaluated to be True on input $\phi$ and 0 otherwise. It is clear that every constraint is satisfied except the input wire constraints (7) for the wires that are assigned to True by $\phi$. There are exactly $\operatorname{OPT}_{\textsc{MMCS}}(C)$ such wires, and each contributes $\varepsilon^{2}$ to the error; as a result, the training error of such weights is exactly $\operatorname{OPT}_{\textsc{MMCS}}(C)\cdot\varepsilon^{2}$.

Next, we will show that the minimum squared training error is at least $\operatorname{OPT}_{\textsc{MMCS}}(C)\cdot\varepsilon^{2}$. Suppose for the sake of contradiction that the minimum error $\delta$ is less than $\operatorname{OPT}_{\textsc{MMCS}}(C)\cdot\varepsilon^{2}$. Observe that, from $\operatorname{OPT}_{\textsc{MMCS}}(C)\leq|C|$ and from our choice of $\varepsilon$, we have

Consider an assignment $\phi$ that assigns each input wire $i$ to be True iff $w_{i}\geq w_{\epsilon}$. The following proposition bounds the weight of every False wire.

For any wire $j$ at height $h$ that is evaluated to False on $\phi$, $w_{j}\leq(2|C|)^{h}\cdot(\varepsilon+\sqrt{\delta})$.

Note that we define the height recursively by first letting the heights of all input wires be zero and then let the height of the output wire of each gate $G$ be one plus the maximum of the heights among all input wires of $G$. The proof of this proposition, which is based on a simple induction, is deferred to Appendix C.

Now, consider the output wire $o$. We claim that $o$ must be evaluated to True on $\phi$. Otherwise, Proposition 5 ensures that $w_{o}$ is at most

where the second inequality comes from our choice of $\varepsilon$. This would mean that the squared error incurred in (8) is at least $0.81>\delta$. Thus, it must be that $\phi$ satisfies $C$.

Moreover, since $\phi$ assigns each input wire $i$ to be True iff $w_{i}\geq w_{\epsilon}$, each input wire that is assigned True incurs a squared error of $\varepsilon^{2}$ from (7). Thus, the number of input wires assigned True is at most $\frac{\delta}{\varepsilon^{2}}<\operatorname{OPT}_{\textsc{MMCS}}(C)$, which is a contradiction as we argued that $\phi$ satisfies $C$. ∎

Observe that, in both Theorem 4 and Theorem 1, the target squared error tends to zero as the dimension tends to infinity. However, this is not an issue: if the norms of the sample vectors are not required to be bounded, then we can simply multiply them by any factor to make the error arbitrarily large. On the other hand, our learning algorithm below implies that, when the norms of samples and weights of ReLUs are bounded, we can approximate the minimum training error for $k$ ReLUs up to an additive error of $\epsilon$ in time $2^{(k/\varepsilon)^{O(1)}}\cdot poly(n)$.

NP-hardness of Training Two ReLUs

We next prove that, for two ReLUs, not only the training problem is NP-hard, but it is NP-hard to even determine whether the samples are realizable. (We remark that this also rules out any multiplicative approximation for the training problem with two ReLUs.) This is in contrast with the single ReLU case, where the realizable case is easy to solve (see Appendix B).

It is NP-hard to determine, given labeled samples of a network consisting of two ReLUs, whether it is possible to assign weights to the units such that the training error is .

We reduce from the 3SAT problem. Recall that, in the 3SAT problem, we are given 3CNF formulas with $M$ clauses on $N$ Boolean variables $X_{1},\dots,X_{N}$ and we would like to determine whether there exists an assignment that satisfies the formula.

The reduction proceeds as follows. Let $n=N+1$ and $m=2N+M+1$. We view the $n$-th coordinate of each sample as a coefficient of dummy variables which we will refer to as $v^{1}$ ($=w^{1}_{n}$) and $v^{2}$ ($=w^{2}_{n}$). Moreover, let $\alpha_{1}=\alpha_{2}=1$.

The first sample has only one non-zero coordinate corresponding to $v$ which is set to one and has label $4$, i.e., this corresponds to

Next, for every variable $X_{i}$, we add constraints

Finally, for each clause $C_{j}=(b_{1}\vee b_{2}\vee b_{3})$, we add a constraint as follows. For $p=1,2,3$, let $X_{i_{p}}$ denote the variable corresponding to the literal $b_{p}$; moreover, let $n_{p}$ be +1 if the literal is positive and -1 otherwise. We then add the following constraint for this clause:

The reduction clearly runs in polynomial time. Next, we argue the correctness of the reduction.

(YES Case) We will start with the YES case. Suppose that the formula is satisfiable. That is, there exists an assignment $\phi:[N]\to\{0,1\}$ that satisfies all clauses. Set $v^{1}=1,v^{2}=3$ and, for every $i\in[N]$, $w^{1}_{i}=2\phi(i)-1$ and $w^{2}_{i}=1-2\phi(i)$. It is easy to verify that all constraints are satisfied, i.e., that the samples are realizable by a sum of two ReLUs with boolean weights.

We remark that, once again, the hardness in Theorem 6 applies even to the case where $\alpha_{1},\alpha_{2}$ are treated as unknowns. Specifically, (13) and (14) already enforce both $\alpha_{1}$ and $\alpha_{2}$ to be positive.

Learning ReLUs

Another model we consider is the reliable agnostic learning model; in the real-valued setting, this model was first defined in [GKKT17], based on the model of [KKM12] for the standard PAC learning model. Informally speaking, reliability puts more emphasis on false positives, i.e., $(\mathbf{x},y)$ supported on $\mathcal{D}$ such that $y=0$ but $h(\mathbf{x})>0$. The additional requirement is that such false positives should only happen with probability $\leq\varepsilon$. (For motivations of the model, see e.g. [GKKT17].)

where $\mathcal{L}_{=0}(h;\mathcal{D})=\Pr_{(\mathbf{x},y)\sim\mathcal{D}}[h(\mathbf{x})>0\wedge y=0]$ is the probability of false positive, and $\mathcal{C}^{+}(\mathcal{D})=\{c\in\mathcal{C}\mid\mathcal{L}_{=0}(c;\mathcal{D})=0\}$ denote all functions in the concept class that (with probability 1) do not admit any false positives. Similar to before, we say that $\mathcal{A}$ is proper if $h\in\mathcal{C}$.

Before we move on, we remark that, in the reliable model, the error $\mathcal{L}(h;\mathcal{D})$ is only compared to $\mathcal{L}(c;\mathcal{D})$ for $c$ that does not admit any false positives, unlike in the (non-reliable) agnostic learning model where all $c\in\mathcal{C}$ are considered. In other words, the fact that a concept class $\mathcal{C}$ is reliably agnostically learnable does not necessarily imply that it is agnostically learnable. It is also not hard to verify that the fact that a concept class $\mathcal{C}$ is agnostically learnable does not imply that it is reliably agnostically learnable.

We now proceed to state our results. The concept classes we consider are the classes of sums of $k$ ReLUs, where each weight vector has norm at most one, and the distribution $\mathcal{D}$ is allowed to be any distribution on the unit ball. More specifically, the class ReLU$(n,k)$, which represent the sums of $k$ ReLUs, is defined as follows:

Let ReLU$(n,k)$ denote the class $\{\textsc{relu}_{\mathbf{w}^{1},\dots,\mathbf{w}^{k}}^{b_{1},\dots,b_{k}}\mid\mathbf{w}^{1},\dots,\mathbf{w}^{k}\in\mathcal{B}^{n},b_{1},\dots,b_{k}\in\}$.

We show that, for any fixed number of ReLUs $k$ and error parameter $\varepsilon>0$, the class above can be efficiently agnostically properly learned (both reliably and non-reliably), as stated below.

Observe that both Theorems consider learning the sum of $k$ ReLUs, i.e., when $\alpha_{1}=\cdots=\alpha_{k}=1$. For Theorem 7, the same result holds for arbitrary coefficients (with a similar proof). This theorem can be further generalized to the case where the coefficients $\alpha_{1},\dots,\alpha_{k}$ are unknowns with only $2^{k}$ multiplicative overhead to the running time, by enumerating all $\alpha_{1},\dots,\alpha_{k}\in\{\pm 1\}$. On the other hand, it is unclear how to extend the algorithm in Theorem 8 to work for negative coefficients; however, we note that it is not even clear whether “reliable” makes sense in this case, since the predicted values can take negative values.

Our results above should be compared to those of [GKKT17] who showed similar results, except that their algorithm is improper: their output is a (“clipped” of) low-degree polynomial, as opposed to sums of ReLUs (which our algorithm outputs). While our algorithm is advantageous to theirs in this sense, theirs is fasterWe do not attempt to optimize our running time, for the sake of simplicity. Nevertheless, it is clear that our approach cannot go beyond $2^{O(k^{2}/\varepsilon^{2})}\cdot(n/\delta)^{O(1)}$ time, which is still slower than the algorithms of [GKKT17]. and extends to a larger class of networks.

Our proof is simple. It first applies generalization bounds (similar to [GKKT17]) which implies that it suffices to take $(k/\varepsilon)^{O(1)}$ samples and solve (even approximately) the training problem on these samples. Hence, by invoking the algorithm from Arora et al.’s work [ABMM18] (see Lemma 12), we immediately get Theorem 7.

To ensure the reliability guarantee (Theorem 8), we do not immediately output the minimizer $h$ from Arora et al.’s algorithm. Rather, we “shift” the biases by subtracting them with a small number. By doing so, for any $\mathbf{x}$ such that $y=0$ and $h(\mathbf{x})$ is non-zero but not too large, the modified hypothesis makes sure that $(\mathbf{x},y)$ is not a false positive (see (19) below). This is a difference between our proof and the one used in [GKKT17] where all biases are assumed to be zero and hence they need to “clip” their hypothesis instead. This is also where we need the positivity of $\alpha_{j}$’s; if $\alpha_{j}$’s are allowed to be negative, it could be that $h(\mathbf{x})$ is small but it remains non-zero after bias shifts.

2 Generalization Bounds

Before we get to our proofs, we state the necessary generalization bounds; these are exactly the same as those used in [GKKT17]. (See Section 2.5 there.)

where $\mathcal{R}_{m}(\mathcal{F})$ is the Rademacher complexity of $\mathcal{F}$.

Let $\mathcal{X}\subseteq\mathcal{B}^{n}$ and $\mathcal{W}=\{\mathbf{x}\mapsto\left<\mathbf{x},\mathbf{w}\right>\mid\|w\|_{2}\leq 1\}$. Then, $\mathcal{R}_{m}(\mathcal{W})\leq\sqrt{\frac{1}{m}}$.

3 Arora et al.’s Training Algorithm

Another ingredient is the algorithm of [ABMM18], which runs in time $m^{O(kn)}$ and output the optimal training error (to within arbitrarily small accuracy). We observe that, for $m\ll n$, the running time becomes $2^{km}\cdot poly(n,m,k)$ which is even faster:

Since the result stated here is slightly different than the version in [ABMM18], we sketch its proof in Appendix D.

4 Properly Learning ReLUs

We now proceed to prove Theorem 7. When we invoke the algorithm from Lemma 12, we will ignore the accuracy parameter $\beta$ and pretend that the algorithm output an actual optimal solution. This is with out loss of generality as in the applications below we can always set $\beta$ sufficiently small such that it becomes negligible. We only choose to ignore it because the proof is much cleaner this way.

First, let us describe the algorithm. Given samples $S=\{(\mathbf{x}_{i},y_{i})\}_{i\in[m]}$ whereIf there are more than $m$ samples, just consider $m$ of them.

we use the algorithm in Lemma 12 to solve for $\mathbf{w}_{1},\dots,\mathbf{w}_{k},b_{1},\dots,b_{k}$ that minimizes the training error. Then, output the hypothesis $h=\textsc{relu}_{\mathbf{w}_{1},\dots,\mathbf{w}_{k}}^{b_{1},\dots,b_{k}}$.

Clearly, the algorithm is a proper learning algorithm (i.e. $h\in$ ReLU${}_{\alpha_{1},\dots,\alpha_{k}}(n,k)$). Furthermore, it runs in time $2^{km}poly(n,m)=2^{O(k^{5}/\varepsilon^{2})}poly(n,1/\delta)$.

Thus, we are left to bound the error $\mathcal{L}(h;\mathcal{D})$. Observe that, from Theorems 10 and 11, we have $\mathcal{R}_{m}(\text{ReLU}(n,1))\leq\frac{2}{\sqrt{m}}$. Hence, from Fact 1, we have $\mathcal{R}_{m}(\text{ReLU}(n,k))\leq\frac{2k}{\sqrt{m}}$. Since the squared loss function is $(4k)$-Lipschitz and $(4k^{2})$-bounded in $[0,2k]^{2}$, Theorem 9 implies that the following holds for all $f\in\text{ReLU}(n,k)$ with probability at least $1-\delta$:

For any $c\in\text{ReLU}(n,k)$, since $h$ minimizes the training error,

5 Properly Reliably Learning ReLUs

Again, we start with our algorithm. Given samples $S=\{(\mathbf{x}_{i},y_{i})\}_{i\in[m]}$ where

We use the algorithm from Lemma 12 to solve for $\mathbf{w}_{1},\dots,\mathbf{w}_{k},b_{1},\dots,b_{k}$ that minimizes the training error for the $m$ samples subject to the additional constraints that, for every sample $\mathbf{x}_{i}$ with $y_{i}=0$, we have $\sum_{j=1}^{k}[\left<\mathbf{w}_{j},\mathbf{x}_{i}\right>+b_{j}]_{+}=0$. Then, let $b^{\prime}_{j}=\max\{-1,b_{j}-\gamma\}$ for all $j=1,\dots,k$ where $\gamma=\frac{\varepsilon}{12k^{2}}$ and output the hypothesis $h_{\text{shifted}}=\textsc{relu}_{\mathbf{w}_{1},\dots,\mathbf{w}_{k}}^{b^{\prime}_{1},\dots,b^{\prime}_{k}}$.

This is clearly a proper learning algorithm and runs in $2^{km}poly(nm)=2^{O(k^{7}/\varepsilon^{4})}poly(n/\delta)$ time.

Thus, we are left to bound the loss. To do so, first recall (from the proof of Theorem 7) that $\mathcal{R}_{m}(\text{ReLU}(n,k))\leq\frac{2k}{\sqrt{m}}$. Recall also that, for reliable learning, we need to bound two losses:

For convenience, let $h=\textsc{relu}_{\mathbf{w}_{1},\dots,\mathbf{w}_{k}}^{b_{1},\dots,b_{k}}$ be the minimizer before bias shifts.

Observe that, if $h(\mathbf{x})\leq\gamma$, then the bias shifts ensure that $h_{\text{shifted}}(\mathbf{x})=0$; this is because $h(\mathbf{x})\leq\gamma$ implies that $\left<\mathbf{w}_{j},\mathbf{x}\right>+b_{j}\leq\gamma$ for all $j\in[k]$, which means that $\left<\mathbf{w}_{j},\mathbf{x}\right>+b^{\prime}_{j}\leq 0$. (Note that this is the place where we need positivity of $\alpha_{j}$’s.) As a result, we have

Combining (19) and (18), we can conclude that the following holds with probability $1-\delta/2$:

where the last inequality also comes from the fact that $h(\mathbf{x}_{i})=0$ for all $i$ with $y_{i}=0$, i.e., $\hat{\mathcal{L}}_{\gamma\text{-cont}}(h;S)=0$.

Bounding ℒℒ\mathcal{L}.

Notice that, for any $\mathbf{x}\in\mathcal{B}^{n}$, $|h(\mathbf{x})-h_{\text{shifted}}(\mathbf{x})|\leq k\cdot\gamma$. Since the squared loss function is $(4k)$-Lipschitz in the domain $[0,2k]^{2}$, it holds that

Finally, let $c$ be any function in ReLU$(n,k)$ such that $c(\mathbf{x})=0$ for all $(\mathbf{x},y)$ in the support of $\mathcal{D}$ such that $y=0$. From how $h$ is computed, we must have

By combining the above bounds, the following holds with probability $1-\delta/2$:

which, together with (20), completes our proof. ∎

Acknowledgments

We are indebted to Adam Klivans for useful comments on an preliminary version of this work and for his suggestion to study the bounded norm case. We thank Amir Globerson and Amit Daniely for helpful discussions. We thank an anonymous reviewer for pointing out an error in a previous version of this work.

References

Appendix A Dealing with Biases In NP-hardness Proofs

As stated earlier, the proofs for NP-hardness results in the main body of the paper assumes that the biases $b_{1},\cdots,b_{k}$ are all zeros. However, all NP-hardness results apply even for unknown $b_{1},\dots,b_{k}$, with little to no change. We elaborate on this below.

For Theorem 1, the same reduction establishes NP-hardness result when there is a bias variable $b_{1}$ in the ReLU. In the YES case, we can simply set $b_{1}$ to . In the NO case, we can get an assignment with the same squared error and no bias by replacing $w_{\epsilon}$ by $w_{\epsilon}-b_{1}$ and $w_{1}$ by $w_{1}-b_{1}$, and thereafter use the same arguments as in the proof of Theorem 1.

A.2 NP-hardness of Training Two ReLUs

For Theorem 6, we need to add two dummy variables $v^{1}_{\text{dummy}}$ and $v^{2}_{\text{dummy}}$, and add the following constraints

The YES case proceeds the same as before, by additionally setting $v^{1}_{\text{dummy}}=1,v^{2}_{\text{dummy}}=-1$ and $b_{1}=b_{2}=0$. In the NO case, these constraints force $b_{1}$ and $b_{2}$ to both be zero. The rest of the proof remains unchanged.

A.3 NP-hardness of Approximating Training Error of a Single ReLU

For Theorem 2, we add a dummy variable $v_{\text{dummy}}$, and add the following constraints:

Again, it is simple to see that the minimum training error is at most is at most $\operatorname{OPT}_{\textsc{MMCS}}(C)\cdot\varepsilon^{2}$, by additionally setting $v_{\text{dummy}}=1$ and $b_{1}=0$.

The other direction of the proof (i.e. that the minimum training error is at least $\operatorname{OPT}_{\textsc{MMCS}}(C)\cdot\varepsilon^{2}$) is more delicate. First, one needs to observe that $|b_{1}|$ cannot be more than $2\sqrt{\delta}$; otherwise, one of the three additional constraints must contribute to more than $\delta$ to the training error. Then, we can once again use induction as before to prove a statement similar to Proposition 5, except that the bound will now be $(2|C|)^{h}\cdot(\varepsilon+3\sqrt{\delta})$. The rest of the proof proceeds as before. Once again, we will be able to conclude that $\phi$ assign less than $\operatorname{OPT}_{\textsc{MMCS}}(C)$ input wires to True but satisfies the circuit, which is a contradiction.

Appendix B Training a Single ReLU in the Realizable Case

Here we demonstrate that training a single ReLU in the realizable case can be done in polynomial time using linear programming. The key observation is the following.

Consider a system $\Lambda$ of $m$ equalities of the form $[\langle{\mathbf{v}_{i}},{\mathbf{x}}\rangle]_{+}=c_{i}$ where $\mathbf{v}_{i}$ are fixed $n$-dimensional vectors and $\mathbf{x}$ is an $n$-dimensional vector composed of the variables $x_{1},\ldots,x_{n}$. Then there is a polynomial time algorithm in $n,m$ and the binary representation of the numbers in $v_{i},c_{i}$ to determine if $\Lambda$ is feasible, and, in the feasible case, output an assignment to the $x_{i}$’s satisfying all equalities in $\Lambda$.

We show how to transform each equality to a linear equality or inequality. Consider $[\langle{\mathbf{v}_{i}},{\mathbf{x}}\rangle]_{+}=c_{i}$. If $c_{i}<0$ then the inequality is not satisfied by any assignment and $\Lambda$ has no solution. If $c_{i}>0$ then replace the equality by $\langle{\mathbf{v}_{i}},{\mathbf{x}}\rangle=c_{i}$. If $c_{i}=0$ then replace the equality by $\langle{\mathbf{v}_{i}},{\mathbf{x}}\rangle\leq 0$. Since transforming the equalities to linear (in)equalities can be done in polynomial time and as we can decide whether a system of linear inequalities over the reals is satisfiable in polynomial time using linear programing, the claimed statement follows. ∎

Recall a training sample $\{(\mathbf{x}_{i},y_{i})\}_{i\in[m]}$ of a single ReLU is called realizable if there exists a choice of weights $w_{i},i\in[n]$ and a bias $b$ such that $[\langle{\mathbf{x}_{i}},{\mathbf{w}}\rangle+b]_{+}=y_{i}$ for all $i\in[m]$. Hence, the above lemma immediately implies that the training problem for a single ReLU can be solved in polynomial time for realizable samples.

Appendix C Missing proof of Proposition 5

Recall that we have the following constraints in our training sample:

Dummy Variable Constraint. We add the following constraint

OR Gate Constraint. For each OR gate with input wires $i_{1},\dots,i_{k}$ and output wire $j$, we add the constraint

AND Gate Constraint. For each AND gate with input wires $i_{1},\dots,i_{k}$ and output wire $j$, we add the following $k$ constraints:

We will prove by induction on the height $h$.

Base Case. Consider any input wire $i$ (of height 0) that is assigned False by $\phi$. By definition of $\phi$, we have $w_{i}<w_{\epsilon}$. Note that $w_{\epsilon}$ must be at most $\varepsilon+\sqrt{\delta}$, as otherwise the squared error incurred in (24) is already more than $\delta$. Thus, we have $w_{i}\leq\varepsilon+\sqrt{\delta}$ as claimed.

$j$ is an output of an OR gate. Let $i_{1},\dots,i_{k}$ be the inputs of the gate. Since $j$ is evaluated to False, $i_{1},\dots,i_{k}$ must all be evaluated to False. From our inductive hypothesis, we have $w_{i_{1}},\dots,w_{i_{k}}\leq(2|C|)^{h-1}\cdot(\varepsilon+\sqrt{\delta})$. Now, observe that $w_{j}$ can be at most $\sqrt{\delta}+w_{i_{1}}+\cdots+w_{i_{k}}$, as otherwise the squared error incurred in (25) would be more than $\delta$. As a result, we have

$j$ is an output of an AND gate. Let $i_{1},\dots,i_{k}$ be the inputs of the gate. Since $j$ is evaluated to False, at least one of $i_{1},\dots,i_{k}$ must all be evaluated to False. Let $i$ be one such wire. Observe that $w_{j}$ can be at most $\sqrt{\delta}+w_{i}$, as otherwise the squared error incurred in (26) would be more than $\delta$. Hence, we have

where the second inequality comes from the inductive hypothesis.

In both cases, we have $w_{j}<(2|C|)^{h}\cdot(\varepsilon+\sqrt{\delta})$, which concludes the proof of Proposition 5. ∎

Appendix D The Running Time of Arora et al.’s Algorithm

[ABMM18] gives a simple algorithm that runs in time $n^{O(km)}$ and outputs the optimal training error (to within arbitrarily small accuracy). Below, we observe that their algorithm also yields an $2^{km}\cdot poly(n,m,k)$ time algorithm; we use this running time guarantee for agnostically learning depth-2 networks of ReLUs. Before we proceed to the statement and the proof of the algorithm, we remark that, our NP-hardness proof for 2 ReLUs in fact also implies that, assuming the Exponential Time Hypothesis (ETH) [IP01, IPZ01]ETH states that 3SAT with $n$ variables and $m=O(n)$ clauses cannot be solved in $2^{o(n)}$ time., the training problem for 2 ReLUs cannot be done in $2^{o(m)}$ time. Hence, the dependency $m$ in the exponent is tight in this sense.

up to an additive error of $\delta$. We assume the bit complexity of every number appearing in the coordinates of the $x_{i}$’s and $y_{i}$’s is at most $C$. Furthermore, there is an algorithm with the same running time up to polynomial factors that finds $\mathbf{w}_{1},\dots,\mathbf{w}_{k}\in\mathcal{B}^{n},b_{1},\dots,b_{k}\in$ subjects to an additional constraint that $\sum_{j\in[k]}[\left<\mathbf{w}_{j},\mathbf{x}_{j}\right>+b_{j}]_{+}=0$ for all $i$ such that $y_{i}=0$.

For each ReLU term $[\left<\mathbf{w}_{j},\mathbf{x}_{i}\right>+b_{j}]_{+}$ guess whether it equals or $\left<\mathbf{w}_{j},\mathbf{x}_{i}\right>+b_{j}$ and replace the term in the error function accordingly. Furthermore, if the guess $[\left<\mathbf{w}_{j},\mathbf{x}_{i}\right>+b_{j}]_{+}=0$ was made then add the linear constraint $\left<\mathbf{w}_{j},\mathbf{x}_{i}\right>+b_{j}\leq 0$. Else, add the linear constraint $\left<\mathbf{w}_{j},\mathbf{x}_{i}\right>+b_{j}\geq 0$. Finally add the constraints $-1\leq b_{i}\leq 1,\|\mathbf{w}_{i}\|_{2}\leq 1$ for all $1\leq i\leq k$. After all guesses are made we get a convex quadratically constrained quadratic program (QCQP). It is well known that such a convex optimization problem can be solved in time polynomial in $n,m,1/\delta,C$ using a separation oracles and the ellipsoid algorithm (see for example, [B+15], section 2.1). Since the number of guesses is at most $(2^{m})^{k}$, the claim follows. For the second part of the lemma, simply substitute the constraint $\sum_{j\in[k]}[\left<\mathbf{w}_{j},\mathbf{x}_{i}\right>+b_{j}]_{+}=0$ according to the guesses made and add the resulting linear constraint. The claim follows. ∎