Training Neural Networks is NP-Hard in Fixed Dimension
Authors: Vincent Froese
Christoph Hertrich
Venue: NeurIPS 2023 poster (2023)
Keywords: Computational Complexity
Neural Network
Rectified Linear Unit
Empirical Risk Minimization
Parameterized Complexity
TL;DR: We solve several open questions about the computational complexity of training two-layer neural networks.

Abstract: We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and linear threshold activation functions. Albeit the computational complexity of these problems has been studied numerous times in recent years, several questions are still open. We answer questions by Arora et al. (ICLR 2018) and Khalife and Basu (IPCO 2022) showing that both problems are NP-hard for two dimensions, which excludes any polynomial-time algorithm for constant dimension. We also answer a question by Froese et al. (JAIR 2022) proving W[1]-hardness for four ReLUs (or two linear threshold neurons) with zero training error. Finally, in the ReLU case, we show fixed-parameter tractability for the combined parameter number of dimensions and number of ReLUs if the network is assumed to compute a convex map. Our results settle the complexity status regarding these parameters almost completely.

Training Neural Networks is NP-Hard in Fixed Dimension
Vincent Froese
Algorithmics and Computational Complexity
Faculty IV, TU Berlin
Berlin, Germany
Sincent..roossetu-beellll
Christoph Hertrich"
Department of Mathematics
London School of Economics and Political Science London, UK
c. wwwhrrichhseeeeco ac. uk
Abstract
We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, sidering ReLU and linear threshold activation functions. Albeit the computational complexity of these problems has been studied numerous times recent years, sev- eral questions are still open. We answer questions by Arora et al. [2018, ICLR] and Khalife and Basu [2022, IPCO] showing that both problems are NP-hard for dimensions, which excludes any polynomial-ting algorithm for constant dimension. We also answer a question by Froese [2022, JAIR] proving W[1]-hardness for four ReLUs (or two linear threshold neurons) with zero training eтror. Finally, in the ReLU case, we show fixed-parameter tractability for the combined parameter number of dimensions and number of ReLUs if the network is assumed to compute a convex map. Our results settle the complexity status regarding these parameters almost completely.
Introduction
Neural networks with rectified linear unit (ReLU) activations are arguably one of the most fundamental models in modern machine learning [Arora al., 2018, Glorot al., 2011, LeCun et al., 2015]. To use them as predictors network) and then optimizes the weights and biases such that the network performs well on some known training data, with the hope that it will then also generalize well to unseen test data. While the ultimate goal applications generalization, empirical risk minimization (that is, optimizing the training error) is important step in this pipeline and understanding its computational complexity is crucial to advance the theoretical foundations of deep learning.
unseen data, one usually first fixes an architecture (the graph of the neural
In this paper, we aim to understand how the choice of different meta- meta-parameters, like the input dimension and the width of the neural network, influences the computational complexity of the training problem. To this end, we focus on two-layer neural networks, which can be seen as the standard building block also for deeper architectures.
Moved to Université Libre de Bruxelles, Belgium, and Goethe- Universittt Frankfurt, Germany, after submission of this article.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

W1
271
b1
02
W2
b2
Wk
bk
Neural network architecture we study in this paper: After the input layer (left) with d input neurons, we have one hidden layer with ReLU neurons and single output neuron without additional activation function.
Figure 1:
Formally, two-layer neural network (see Figure 1) with d input neurons, k hidden ReLU neurons, and single output neuron computes map
k
Φ: Rd +
((x)
= Σ Calw, x by]+,
j=1
where w, E [d and a, E 1] are the weights between the layers, by are the biases at the hidden neurons, and [x+++ == max(0, x)) is the rectifier function. Notice that restricting aj {-1, 1 is without loss of generality because we can normalize by pulling any nonnegative factor into w, and by. We also study neural networks with linear threshold activation in Section
Given training data X1, x1,..., X,, E Rd with labels yI,.... R, the task training such network is to find wj. bj, and aj for each j E [k] such that the training error > L()(x,), y:) for given loss function L:
-> RR Rx00 is minimized. Throughout this work, we assume L: TR + Rgo to be any loss function with [(x, = 0 < y. Formally, the decision version of two-layer
ReLU neural network training is defined as follows:
2L-RELU RRELU-NN-TRAINCE
Input:
Data points (1,,8),..... (Xn, Un) E IRd x IR, number k E N of ReLUs, and a target error Rg0.
Question:
Are there weights Wi,...; W* E Rd, biases bi....,yy by IR and coefficients
al...., 0g E 1 such that
Σ
Σ aslw, + byl+, vi) ??
Note that in the wver-parameterized case where k 2 n, the network can exactly fit any input points? (achieving training error = 0) |Zhang et al., 2021, Theorem 1]. Thus, we henceforth assume that & <
2L-RELU-NN COUU-NNTRRAE TRAIN(L) known be hP-dard [Dey et al., 2020, Goel et al., 2021], but all known reductions require the input dimension to be part of the input. The current oftte-of-the-nn exact algorithm for convex loss by Arora al. [2018] and runs O22"n poly(L)) time, where is the input bit-length.
As regards the computational complexity of 21-RELL-NNN-TRANNG Arora al. [2018] posed the question(s) whether a running time
"thut is polynomial in the data size and/or the number of hidden nodes, assuming that the input dimension is a fixed constant"
is possible. That is, they asked two questions. The first corresponds to the "and" statement, which can be phrased follows:
Assuming that yi yj whenever Xj-

---

Question 1: Is there an algorithm running in (nk) (L) time for some function f?
In other words, the question is whether 21-RELU-NN-TRRINNC) is in the complexity class XP when parameterized by d. The second question corresponding to the "or" statement can then be interpreted as
Question 2: Is there an algorithm running in n g(k, d) (L) or k( g(n, d) poly(L) time for some functions f and g?
We observe that the second running time is clearly possible since k < holds by assumption, and hence the algorithm by Arora et al. [2018] runs in g(n, d) (oly(L) time. Hence, it remains open whether n (d) g(,, d) poly(L) time is possible, which is equivalent to (uniform) exeddparamettr tractability with respect to k for every constant d.
Clearly, Question 1 the stronger statement, that is, a positive answer implies positive answer to Question 2. Arora et al. [2018] 8] conclude with
"esolving this dependence on network size would be another step towards clarify- ing the theoretical complexity of training ReLU DNNs and is good open question for future research, in our opinion."
Note that Froese et al. [2022] proved that, for l: = 1, there is no algorithm running in (d)) time unless the Exponential Time Hypothesis fails. Hence, this result already partially answered the two questions above by excluding any algorithm running in no(d)) g(d, k) poly (L) time.
Our Contribution. In this paper, we answer Question 1 negatively by showing NP-hardness for d = 2 in Theorem 1, indicating that we cannot get rid of the exponential dependence on the network size in the algorithm by Arora et al. [2018] even if the dimension is fixed. As regards Question 2, we further exclude (assuming the Exponential Time Hypothesis) any algorithm running in time n add) gdd, k) poly L) even for the case y 0 and prove wrridehardness with respect to d for k = 4 (Theorem 6), which answers an open question by Froese et al. [2022].
We also obtain analogous hardness results if linear threshold activation functions are used instead of ReL.U.. As in the ReLU case, it is well-known that training linear threshold networks is NP- hard [Blum and Rivest, 1992, Khalife and Basu, 2022]. The running time of the state-of-the-ar algorithm due to Khalife and Basu [2022] is polynomial in for fixed d and k; but exponential in the latter two parameters. Khalife and Basu [2022] posed an analogous question to Question I for linear threshold networks, which we answer negatively in Corollary 7, excluding a polynomial running time even for fixed dimension. We also show that we cannot expect fixed-parane parameter tractability with respect d even for
(Corollary 8) and also not for
and ? (Corollary 9).
On the positive side, we give an algorithm running in 20(k2d) poly(k, L) time for ReLU neural networks if = 0 and the function computed by the network is assumed to be convex (Theorem 10). Note that this rumning time yields exed-parameter tractability with respect to & for every constant and thus answers Question 2 positively for this restricted special case. We would like to emphasize that we do not expect this algorithm have any practical relevance. We rather see its value in being a puzzle piece for understanding the computational complexity of the training problem.
Implications and Limitations. In the following we provide brief discussion of the implications and limitations of our results from various perspectives.
Input Dimension. Theorem I implies that fixed d 2 2. The frowwad reduction simply pads all the input vectors with zeros. Similarly, Corollary 7 holds for every fixed d > 2.
MABBLU-NN-TRANN is in fact NP-hard for every
Target Error. The hardness results Theorems and 6 and Corollaries and 9 also hold for every fixed 2 0. The reduction is trraight-forward by introducing set of incompatible data points which force the network to incur an additional error of y. For our positive result Theorem 10, however, there
is indeed a difference in the complexity between the two cases 7 = 0 and 7 > 0. While we show fixed-parameter tractability for 7 = 0, the same problem Whlld for 7 > O, already in the case
k 1 [Froese al., 2022].
3

---

Number of ReLUs. It not too difficult to see (although it requires some work) that our particular reduction Theorem can be extended any k 2 4 by introducing more data points far away from the existing data points which enforce the usage of additional ReLUs which then cannot be used to fit the data points of the actual reduction. Therefore, Theorem 6 holds for every fixed k 2 4. Similarly, Corollary 8 holds for every fixed k 2 1 and Corollary 9 holds for every fixed k 2 2.
Other Activation Functions. Our hardness results hold for the piecewise linear ReLU activation function and the piecewise constant linear threshold activation function. Extending them to other piecewise linear or constant activation functions like leaky ReLU or maxout should be straight- forward. However, achieving analogous results for smooth activation functions like sigmoids probably requires fundamentally different techniques and is beyond the scope of this paper.
Training vs. Learning. Our results are concerned with the problem of minimizing the training error. While this is inherently different from minimizing the generalization error, there are indeed deep connections between these two problems [Shalev-Shwartz and Ben-David, 2014]. In particular, as pointed out by Goel et al. [2021]. hardness of training implies hardness of proper learning if one permits arbitrary data distributions. However, such hardness results can often be overcome by either posing additional assumptions on the data distributions or switching to more general learning paradigms like improper learning [Goel et al., 2017].
Exact Approximate Training. In practice, it arguably often suffices to train neural network to approximate instead of exact optimality. The results in this paper are concerned with solving the training problem to exact global optimality. However, since Theorems and 6 and Corollaries 7 and 9 already hold for training error = O, they even rule out the existence of approximation algorithms with any multiplicative factor. We conceive that for appropriate notions of additive approximation (see, c.g., Goel et al. [2021J), our reductions can also be used to show hardness of additive approximation. However, this would significantly increase the technical complexity of the analysis and is therefore beyond the scope of this paper. We leave it as an open research question analyze the influence of meta-parameters like input dimension and number of hidden neurons on additive approximation of the training problem.
Related Work. Dey et al. [2020] and Goel et al. [2021] showed NP-hardness of 2I.-REL.
TRAIN(C) for l = 1, but require non-constant dimension. For target error 7 = 0, the problem is NP-hard for every constant k 2 2 and polynomial-tin timoe solvable for k = 1 [Goel et al., 2021]. Goel et al. [2021] provide further conditional running time lower bounds and (additive) approximation hardness results. Froese et al. [2022] considered the parameterized complexity regarding the input dimension d and proved Warn-hasd and an ETH-based running time lower bound of ((d) for k = 1.
Boob et al. [2022] studied networks where the output neuron also is ReLU and proved NP-hardness (and implicitly W[1] whrrddessssss with respect to d) for & = 2 and = O. Bertschinger et al. [2022] showed that training 2-layer ReLU networks with two output and two input neurons (IR2 - IR is complete for the class 3IR (existential theory of the reals) and thus likely not contained in NP. This also implies NP-hardness, but note that contrast to our results, their reduction does not work for one-dimensional outputs. Their result strengthens a previous result by Abrahamsen et al. [2021] who proved 3IR completeeess for networks with specific (not fully connected) architecture. Pilanci and Ergen [2020] showed that training 2-layer neural networks can be formulated as a convex program which yields a polynomial-time
algorithm for constant dimension d. However, they considered a regularized objective and their result requires the number & of hidden neurons to be very large (possibly equal to the number n of input points) and hence does not contradict our NP-hardness result for d = 2.
To study the computational complexity of training ReLU networks, a crucial ingredient is to know the set of (continuous and piecewise linear) functions precisely representable with a certain network architecture. This is well-understood for two-layer networks [Arora et al., 2018, Bertschinger et al., 2022, Dereich and Kassing, 2022], but much trickier for deeper networks [Haase et al., 2023, Hertrich and Sering, 2023, Hertrich et al., 2021]. Similar to the study of ReLU networks by Arora et al. [2018], Khalife and Basu [2022] studied the expressiveness and training complexity for linear threshold activation functions. For an extensive survey on intersections of deep learning and polyhedral theory, we refer to Huchette et al. [2023].

---

2 Preliminaries
Notation. For n E N. we define [n] (l....,,. n.. For X C CR,, we denote by (X) the affine hull of X and by dim(X) the dimension of (X).
Parameterized Complexity. We assume basic knowledge on computational complexity theory. Parameterized complexity is multivariate approach to analyze the computational complexity of problems [Downey and Fellows, 2013, Cygan et al., 2015].
An instance (x, k) of a parameterized problem L C Σx x N is a pair with x E Σ" being a prob- lem instance and & E N being the value of a certain parameter. A parameterized problem L is -rred-prrameter tractable (fpt) (contained in the class FPT) if there exists an algorithm deciding whether (x, k) E L in fkk . |xr (0(()) time, where f is a function solely depending on k. Note that a parameterized problem in FPT is polynomial-time solvable for every constant parameter value where, importantly, the degree of the polynomial does not depend on the parameter value. The class XP contains all parameterized problems which can be solved in polynomial time for constant parameter values, that is, in time (k) |ar|o(k)) It is known that FPT Ç XP. The class W[1] contains parameterized problems which are widely believed not to be in FPT. That is, a W[rr- problem (e.g. CLIQUE parameterized by the size of the sought clique) is not solvable in f(k) |x] (01) time. is known that FPT C W[1] S XP.
W[l]-hardness is defined via parameterized reductions. A parameterized reduction from L L' an algorithm mapping instance (ar, k) in f(k) |x: ((1) time to instance (1', k') such that k S gk) for some function g and (z, k) E L if and only if (a', ke', E L'.
Exponential Time Hypothesis. The Exponential Time Hypothesis (ETH) [Impagliazzo and Paturi, 2001] states that 3-SAT cannot be solved in subexponential time in the number n of Boolean variables in the input formula, that is, there exists a constant e > 0 such that 3-SAT cannot be solved in O(20) time.
The ETH implies FPT W[]] [Cygan et al., 2015] (which implies P o NP). In fact, ETH implies that CLIQUE cannot be solved in p(k) -n time for any function p. where k is the size of the sought clique and is the number of vertices in the graph [Cygan al., 2015].
Geometry of 2-Layer ReLU Networks. For proving our results, crucial to understand the geometry of a function Φ: Fd + IR represented by a two-layer ReLU network. Here, we only discuss properties required to understand our results and refer to Arora al. [2018], Bertschinger al. [2022], Dereich and Kassing [2022] for additional discussions in this context. Such a function ø continuous and piecewise linear function. Each hidden neuron with index E [k] defines a hyperplane Wj x by 0 in Idd These & hyperplanes form hyperplane arrangement. Inside each cell of this hyperplane arrangement, the function ø is affine. The graph of ø restricted to such a cell called a (linear) piece of Φ.
Consider a hyperplane H from the hyperplane arrangement. Let w be an orthonormal vector of H and let J _ [k] be the non-empty subset of indices of neurons which induce precisely H. Note that wj is scaled version of for each E J. Let E Rd be a point on Ii which does not lie on any other hyperplane in the arrangement. There are exactly two d-dimensional cells in the arrangement containing one on each side of H. The difference of the directional derivatives of the corresponding two pieces of & in the direction of w is exactly ΣSE, az /llwwll- In particular, this is independent of x and therefore constant along H. If this value is positive. we say that H is a conver hyperplane of ó. If it is negative, we say that H is concave hyperplane of é. Note that this matches with Φ being convex or concave locally around every point x E H which does not belong to any other hyperplane in the arrangement. Moreover, point E Rd is called a convex (concave) breakpoint of & if it lies exclusively on one convex (concave) hyperplane of Φ.
One important observation we will heavily use is the following: If we know that o originates from a 2-layer neural network with & hidden neurons and we know that we need indeed & distinct hyperplanes to separate the pieces of o, then each hyperplane must be induced by exactly one neuron (and not several). Then the hyperplane corresponding to the j-th neuron convex if and only if a, > 0 and concave if and only if a, < O. For input dimension d = 2, each of the hyperplanes in the arrangement
5

---

is actually line in IR?. We call such line breakline and define convex and concave breaklines accordingly.
NP-Hardness for Two Dimensions
In this section we prove our main result that RRELU-NN-TRAING is NP-hard for two dimensions, thus excluding any running time of the form (nk))T(d)
Theorem 1. RERL--NNN--AAAE
is NP-hard even for d = 2 and 0.
We give a polynomial-time reduction from the following NP-complete problem [Garey and Johnson, 1979].
POSITIVE ONE-IN-THRED 3-SAT (POITS)
Input:
A Boolean formula F in conjunctive normal form with three positive literals per clause.
Question:
Is there a truth assignment for the variables such that each clause in has exactly one true literal?
Our construction will be such that the function represented by the neural network is equal zero everywhere except for finite set of "stripes", in which the function forms a levee (see Definition 2), that is, when looking a cross section, the function goes up from 0 to I, stays constant for while, and goes down from I to 0 again. See Figure 2 (right) for top view of levee and Figure for cross section of a levee.
Definition 2. levee with slope s (centered at the origin) the function fs: R.2 + with
0,
x22 801 if I - 821 S 1,
2 2,
1,
fe(11,22) =
(I)
+ 222 50
if x2 5
E 2, 2
- + 83
xf
5
E 1
Observation 3. A levee fo is a continuous, piecewise linear function with two convex and two concave breaklines. It can be realized with four ReLUs as follows:
(2) = [22 1 + 2|+ 1 801
1]+
[x2
8.1 1|+ 1x2 801
2]
Similar levees have been used by Bertschinger et al. [2022] to prove 3R-completeness of neural network training, however, in a conceptually very different way. their work, levees encode variable values via the slopes of the function on the non-constant regions of the levee. In contrast, in our reduction, we encode discrete choices via rotation of the levees, that is, via the slopes of the breaklines in the two-dimensional input space.
Selection Gadget. We describe a gadget allowing us to model discrete choice between & many possibilities (levees). An illustration of the selection gadget is given in Figures 2 and 3.
Each the different choices corresponds to one of l different slopes 8 < 82 < ... < 8g. The gadget consists of a total of 29 + 26 many data points with labels in {0, 1/3, 2/3, 1). The precise position of the data points is described in Appendix A.
It is not too difficult to verify that a levee with slope s;, E [e]. fits all data points of a selection gadget. We omit the simple but tedious calculations here. More intricately, the following lemma shows that a selection gadget indeed models a discrete choice between exactly possibilities. The technically involved proof of the lemma is deferred Appendix
Lemma 4. Let f: E²2 E be continuous piecewise linear function with only four breaklines that fits all the data points of the selection gadget. Then, f = for some E [e].
Combining Multiple Selection Gadgets. Having constructed and understood single selection gadget, the next step is to use multiple of these gadgets simultaneously. To this end, we will "stack multiple selection gadgets upon each other along the axisx. The precise construction and formal proof of the following lemma are contained in Appendix A.

---

372
10
200
Figure 2: Illustration of the selection gadget with and 81 11 82 0, 83 Both figures
show the 21 -ll-pe while the y-coordinate is indicated via the darkness of the gray color. The left picture shows all data points belonging to the gadget as well as the breaklines the three possible levees fitting the data points. In addition to these features, the right picture shows levee with slope 82 as one three possibilities to the data points of the gadget.
312
Figure 3: Cross section of the selection gadget along the æ2 æ2-axis. The data points of the gadget force the function f to attain the shape of levee.
Lemma 5 (Informal version of Lemma 11). Suppose m selection gadgets are placed along the axisxxs with sufficient distance to each other. Then the unique way of fitting all these gadgets with a single continuous piecewise linear function f: R22 R with at most 4m breaklines is selecting exactly one levee for each of the m gadgets and summing up the corresponding functions.
Global Construction. We are now ready to describe the overall layout of the reduction.
For given formula F = C1 A C2... A C. with variables v..-... Uns we construct data points in TR22 x IR such that they can be fitted exactly with k 4(m + n) ReLUs and only if is yes-instance of POITS. See Figure 4 for an illustration. Our construction consists of m selection gadgets, namely one for each clause and one for each variable, and 3m further data points. Each of the selection gadgets corresponding to clause determines which literal of this clause we choose to true. Each of the n selection gadgets corresponding to a variable determines whether this variable is true or false. The 3m remaining data points ensure that these choices are consistent. More precisely, if the r-th literal of clause C₁ is U, then we introduce a data point Pj.r with label the intersection of the levee corresponding to the r-th choice in Cj and the levee corresponding to setting Uj to false. This makes sure that the r-th literal Cj is selected if and only v, is set to true.
at
Sketch of the proof of Theorem 1. Our detailed proof in Appendix A starts by showing that the data points Pj.r are indeed positioned such that they only interfere with the two intended levees and no other selection gadgets (Lemma 12). Then, for given instance of POITS, we construct instance of CEEEELU-NN-TAAAE (C) as described above. Making use our lemmas and Observation we show that the possible solutions of POITS are in one-to-one correspondence to the possible solutions of 2L--RELU-NN-TRRR (R)IN(( which decompose into sum of levees. This finishes the reduction.
D

---

Ca
C2
C1
172
122
174
144
Figure 4: Global construction layout for the reduction from POITS to EE--REL-NNN--AAANE The figure shows the construction for the instance (Vs V 04 V es) A (14 V Us V 02) A (us 02 V v1). The vertical dotted line is the a2-axis along which place all the selection gadgets. Each gadget is depicted with a black square. Each solid gray line depicts one possible levee. Each gray circle depicts data point Pj.r with label one. The picture the right additionally shows one possible solution to the given instance. Indeed, choosing levees corresponding to the solid black lines selects exactly levee per selection gadget and exactly one levee passing through each of the nine additional data points. This corresponds to the truth assignment V3 = true and U4 02s = false.
W[1]-Hardness for Four ReLUs
We show that fixed- parameter tractability with respect to d is unlikely even for target error zero and four ReLUs, In fact, we prove a running time lower bound of n ((()) based on the ETH.
Theorem 6. UL-RELU-NNN-RRISS not solvable in p(d)nc(d) Poly(L) time (where L is the input bit- bit-length) for any function assuming the ETH.
with k 4 and
is W-I]-hard with respect to d and
We prove Theorem with a parameterized reduction from the 2-HYPERPLANE SEPARABILITY problem (see Appendix B).
2- HYPERPLANE SEPARABILITY
Input:
Two point sets Q and P in Rdd Are there two hyperplanes that strictly separate Q and P?
Question:
Here, two hyperplanes strictly separate and P if, for every pair (q, p) Q x P. the open line segment qp is intersected by at least one hyperplane and no point from Q PUPI is contained in any of the two hyperplanes. Giannopoulos al. [2009] showed that this problem is W[1]-hard with respect to d and not volvable in p(d)mo(d) poly(T) time assuming the ETH (where m IQ PI and L is the instance size). The idea of our reduction is that a separating hyperplane can be realized by two ReLUs approximating a "step function". To this end, we add some auxiliary points Q P to ensure the separating behaviour of the ReLUs.
Hardness Results for Linear Threshold Activations
nowadays less popular, but more classical activation function than ReLU is the linear threshold function & + 11 [=>00)- We define
as the decision version of the training problem for linear threshold functions. is defined exactly as 21-RELU-NN-TRAINC with two
modifications: first, the ReLU function [z]+ + is replaced with (=>0), and second, we do not assume aj (-1,1) 1} anymore because the normalization used in the ReLU case does not apply here. Instead we allow arbitrary a, R.
As in the ReL.U case, the crucial ingredient to study the training complexity of linear threshold networks is their geometry. To this end, observe that every function represented by 2-layer linear

---

threshold network is piecewise constant, where the pieces emerge from the hyperplane arrangement defined by the k hyperplanes corresponding the hidden neurons. Since our reductions for the ReLU case always use two ReLUU to approximate "step functions" from 0 to 1 and from 1 to O, it is easy to adapt the reductions to the linear threshold case.
Corollary 7.
NP-hard even for and O.
Proof. We reduction analogous to the one in the proof of Theorem 1. Instead of sum of levees, we use a sum of "stripes" within which the function attains value 1. With this idea, it is straight-forward to build selection gadgets and analogous global construction. Note that the number & of required linear threshold neurons is only = 2(m + n) for POITS instance with m clauses and variables because each stripe can be realized with two linear threshold neurons instead of the four ReLUs required to build a levee.
For the sake of completeness, we note that also the W[l]-hardness result by Froese et al. [2022] extends to linear threshold functions. To this end, consider the & fo-loss ( (" y) yl". where g simply counts the non-zero components of I y-
For each p E [0, xox, 3L-LT-NN-TRAINN"" with h: NP-hard, W[1]-hard with respect to and not solvable in p(d) poly(L) time (where L is the input bit-length) for any function assuming the ETH.
Corollary 8.
Proof. Having careful look into the reduction from MULTICOLORED CLIQUE by Froese et al. [2022], it turns out that the single ReLU neuron used in this reduction can be replaced by linear threshold neuron without changing the logic of the reduction.
Finally, also Theorem 6 finds its analogue for the linear threshold case.
Corollary 9. BL-LT-NN-TRAINC with k = 2 and y = O is W[1]-hard with respect to d and not solvable in p(d))o(d)) poly (L) time (where L is the input bit-length) for any function p assuming the ETH.
Proof. The proof is analogous (even much easier than) the one of Theorem 6. Instead of two ReL.Us to realize step of height one, we can simply use one linear threshold neuron (which is why we obtain hardness already for = 2 in this case). Note that we do not even need to introduce additional data
points, that is, we obtain much more direct reduction from 2- 2-HYPERPLANE SEPARABILITY. O
6 An Algorithm for Exact Fitting in the Convex Case
Contrasting the previous hardness results for DI-RELU-NN-TRRIINC) we now consider the tractable special case where all coefficients aj are 1. this case (called 2L-RELU-NN DL-RELU-NN-TRAINCE TRAIN(2) the neural network realizes convex continuous piecewise linear function with at most 2 distinct (affine) pieces. We show fixed pred-pprameter tractability for the parameter d+ if 0 (see Appendix C).
Note that, for 7 O, W[l]-hardness with respect already holds for Froese al. [2022].
Theorem 10. WAREELL-NNNTRRIN(CC can be solved in 20(224) poly(k, L) time for y 0, where L is the input bit-length.
The proof idea is that the convexity of ó allows for branching algorithm assigning the input data points to the 2 pieces of á. We note that Theorem 10 analogously holds for the concave case where aj -1 1 for all j E [k). However, if positive and negative coefficients aj are allowed, then our search tree approach does not work due to non-convesee non-convexity. Indeed, Theorem 6 implies that this approach cannot work already for & 4. It is unelear whether this issue can be resolved for k or ==
7 Conclusion
We closed several gaps the literature regarding the computational complexity of training two-layer neural networks. Our results give some insight into the geometry of functions realized by such

---

networks and yield a better understanding of their complexity and expressiveness. We thereby settled the border of computational tractability almost completely. The remaining open questions are the following:
Is the problem with d = 2 in FPT when parameterized by k? This is open for both ReL.Us and linear thresholds. Note that W[1] Whaardndsssss with respect k for any constant d would answer Question 2 negatively.
Is the case ? = 0 and & E ( in FPT with parameter for ReLUs?
In broader context, open directions are further study the computational complexity in appropriate approximate settings, draw further conclusions on generalization, and understand deeper network architectures.
Acknowledgments and Disclosure of Funding
Christoph Hertrich is supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreements Scale0pt-757481 and ForEFront-615640),
References
M. Abrahamsen, L. Kleist, and Miltzow. Training neural networks -IR-complete. In Advances in Neural Information Processing Systems 35 (NeurIPS '21), pages 18293-18306, 2021.
R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. In Proceedings of the 6th International Conference on Learning Representations (ICLR 18). OpenReview.net, 2018
D. Bertschinger, C. Hertrich, P. Jungeblut, T. Miltzow, and S. Weber. Training fully connected neural networks is =locomplete. CoRR, abs/2204.01366 2022.
A. L. Blum and R. L. Rivest. Training a 3-node neural network is NP-complete. Neural Networks, (1):117-127, 1992.
D. Boob, S.S. Dey, and Lan. Complexity training ReLU neural network. Discrete Optimization, 44(Part 1):100620, 2022.
M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov. D. Marx, M. Pilipezuk, M. Pilipezuk, and S. Saurabh. Parameterized Algorithus. Springer, 2015.
Dereich and S. Kassing. On minimal representations of shallow ReLU networks, Neural Networks, 148:121-122 128, 2022.
S. S. Dey, G. Wang, and Y. Xie. Approximation algorithms for training one-node ReLU neural networks. IEEE Transactions on Signal Processing, 68:6696 6706, 2020.
R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013.
V. Froese, C. Hertrich, and Niedermeier. The computational complexity of ReLU network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74:1775- 1790, 2022.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman and Company, 1979.
P. Giannopoulos, C. Knauer, and G. Rote. The parameterized complexity of some geometric problems in unbounded dimension. In Parameterized and Exact Computation, 4th International Workshop (IWPEC '09), volume 5917 of LNCS, pages 198-209. Springer, 2009.
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS 11)), volume 15 of JMLR Proceedings, pages 315-323. JMLR.org, 2011.
10

---

S. Goel, V. Kanade, A. R. Klivans, and J. Thaler. Reliably learning the ReLU in polynomial time. In Proceedings of the 30th Conference on Learning Theory (COLT '17), volume 65 of PMLR, pages 1004-1042. PMLR, 2017.
S. Goel, A. R. Klivans, P. Manurangsi, and D. Reichman. Tight hardness results for training depth-2 ReLU networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS '21), volume 185 of LIPlcs, pages 2021.
14. Schloss Dagstuhl Leibniz-Zentrum für Informatik,
C. Haase, C. Hertrich, and G. Loho. Lower bounds on the depth of integral ReLU neural networks via lattice polytopes. In Proceedings of the Eleventh International Conference Learning Representations (ICLR '23), 2023.
C. Hertrich and L. Sering. ReLU neural networks of polynomial size for exact maximum flow computation. In The 24th Conference on Integer Programming and Combinatorial Optimization (IPCO 233, 2023. Accepted for publication.
C. Hertrich, A. Basu, M. Di Summa, and M. Skutella. Towards lower bounds on the depth of ReLU neural networks. Advances in Neural Information Processing Systems, 34:3336-3348, 2021.
Huchette, G. Muñoz. T. Serra, and C. Tsay. When deep learning meets polyhedral theory: A survey. CoRR, abs/2305. 002411, 2023.
R. Impagliazzo and R. Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001.
S. Khalife and A. Basu. Neural networks with linear threshold activations: structure and algorithms. In The 23rd Conference on Integer Programming and Combinatorial Optimization (IPCO '22). pages 347-360, 2022.
Y. LeCun, Y. Bengio, and G. Hinton. Deep learning, Nature, 521(7553):436-444 2015.
M. Pilanci and T. Ergen. Neural networks are convex regularizers: Exact polynomial-tine convex optimization formulations for two-layer networks. In Proceedings of the 37th International Conference Machine Learning (ICML 200), volume 1 19 of Proceedings of Machine Learning Research, pages 7695-7705. PMLR, 2020.
S. Shalev-Shwart, and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.


Reviews:
[{"review_id": "rQ74XTUm8c", "reviewer": "Reviewer_T5Uz", "summary": "This paper focuses on two layer neural networks with ReLU or linear threshold activations. The authors show that considering the input dimension (dimension of the data as a constant) equal with 2, there is no polynomial algorithm with respect to the number of data (n) and hidden nodes (k, k<n) that decides whether there exist weights that achieve zero training error. The second result indicates that there is no algorithm with dependence $n^{o(d)}$ on $n$ and arbitrary dependence on $k,d$. Furthermore, if $k=4$ the authors prove $W[1]-$hardness with respect to $d$. Similar results are obtained for the case of threshold activations. Finally, they provide an algorithm, independent of $n$ if the target function is convex. ", "questions": "Considering Theorem 1, is there some more tight characterization when $d> 2$ and the inputs are not sparse?", "limitations": "The authors have addressed the limitations and this work has no negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is in general well-written. It closes some gaps regarding hardness results for deciding whether there exist weights on a neural network that achieve a small or zero training loss. The authors show that even when the target is zero error, the problem is NP-hard for $d=2$ and thus for any $d\\geq 2$ (since we can simply zero pad and thus ignore the rest of the $d-2$ points (Theorem 1). They also prove that for $k=4$ and zero training error the problem is $W[1]$-hard with respect to the parameter $d$. Their results also hold for the case of linear threshold activations. They finally show that for the case that the target functions is convex, meaning the second layer has weights all equal to one, they show that the problem is fixed-parameter tractable (FPT), when the targeted error is exactly zero. It was already known that for the case of non-zero error, positive error the decision problem is $W[1]$-hard.\n", "weaknesses": "Considering the last result (theorem 10) I am not sure what it adds to our understanding, it will be rare to encounter a convex problem a providing an algorithm to decide whether it is solvable it's not very useful, since we know that a convex function will have a global minimum and that it can be found through classical methods like gradient descent. The authors have already acknowledged that this algorithm will not have any practical relevance, but I also think its contribution as a theoretical result marginal.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review.\n\nWe agree that the algorithm for the convex case is unlikely to be useful in practice.\nFrom a theoretical side, this result is interesting since it gives a partial positive answer to the open Question 2.\nIt is thus a step towards resolving this question and shows that the inherent hardness stems from the case when both positive and negative weights occur in the last layer.\nBesides this, the algorithmic ideas might be inspiration for solving other similar tasks.\n\nAnswering your question, for $d>2$, the problem is known to be NP-hard even for a single ReLU with non-sparse inputs (see e.g. Goel et al.)."}, {"review_id": "KmKKnS4bCb", "reviewer": "Reviewer_pi8Y", "summary": "This paper mainly studies the complexity of training two-layer ReLU networks when they are not over-parameterized. Specifically, the authors prove that training a two-layer ReLU network to zero or arbitrary loss value is NP-hard when the input dimension $d\\geq 2$. This result answers an open question (Question 1) posed by Arora et al. (2018) negatively by proving the NP-hardness. On the other hand, by assuming the exponential time hypothesis, the paper also partially answers a more general question of whether a running time that is polynomial in the data size or the number of hidden nodes (Question 2). The paper also provides a positive answer to Question 2 when the ReLU network is assumed to compute a convex function.", "questions": "1. Line 35: In the case when $\\gamma$ is strictly positive, are there any extra assumptions imposed on the loss function? The only assumption on the loss function $\\ell(x,y)=0$ iff $x=y$ is fairly general. It would be more convincing if the authors could clarify more about the loss function.\n\n2. Would it yield the same conclusion as Theorem 1 if a regularizer (e.g., weight decay or L1) is added to the loss function ($k<n$)?\n\n3. Would it be possible to consider some assumptions on architectures that give a polynomial-time algorithm for training a two-layer ReLU network?", "limitations": "The authors have addressed some of the limitations of this work in the text. Other limitations in my view are the gaps between the settings of the problem and the training of ReLU networks in practice. For example, one may be able to make some assumptions on architectures, regularizations, and properties of data to derive a polynomial-time training algorithm. However, given that the main purpose of this paper is to answer the open questions, discussions on these aspects may be skipped or minimized.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The novelty of the paper is clear. It provides answers to open questions on the complexity of training two-layer ReLU networks. Therefore, the results seem to be significant. The presentation is concise and easy to follow. I enjoy reading the paper.", "weaknesses": "Usually, there are symmetries and redundancies in the dataset. It would be more convincing and realistic if the authors could give some insights on how to leverage these available properties to develop efficient training algorithms. In practice, training a two-layer ReLU network is very efficient. Hence, I feel the settings in this paper seem to be a bit unrealistic. My concern is that it seems hard to apply these results to make a positive impact on our machine learning community. One possible way to address this is to discuss assumptions on different aspects (e.g., architectures) to make training tractable or even efficient. This work focuses on two-layer ReLU networks, but it would be interesting to give insights into extending the results to networks with multiple layers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review.\n\nOur goal was to settle the complexity of the training problem in the general case (without further assumptions on the input), which turned out to be hard. We agree with you that this is a worst-case result, which does not necessarily reflect practical conditions, but we are convinced that such results belong to an important fundamental understanding of the training problem.\nIndeed our hardness results hold for a very simple restricted setting which makes them even stronger (e.g. for more than two layers, the problem can be expected to be at least as hard).\nAs regards impact, our results yield a better theoretical understanding of the power and expressiveness of ReLU networks and settle the complexity status almost completely.\nMoreover, our results can be seen as a justification for making certain assumptions on the input data in order to achieve polynomial time (since without any assumptions, polynomial time is provably unlikely). \n\nAdressing your questions:\n\n1. There are no further assumptions on the loss function (also not for $\\gamma > 0$).\nOur results hold for any loss that satisfies the described condition.\nHence, we only make a weak assumption on the loss, which makes our results in fact stronger.\n2. It is not clear whether Theorem 1 also holds for regularized loss.\nIt might still hold as long as the regularization does not prevent building levees as we do in our construction.\n3. For unbounded dimension, the problem is already known to be NP-hard even for a single hidden neuron.\nIn fixed dimension, the problem becomes polynomial-time solvable if the number of hidden neurons is also constant (but this is not very interesting).\nSince a network with two layers is already a very simple architecture, it might be tough to find a meaningful restriction that allows polynomial-time training."}, {"review_id": "mH57Ozjjb6", "reviewer": "Reviewer_bRY2", "summary": "The authors show that learning a 2-layered neural network with ReLU activation function, in an underparameterized regime, is NP-hard when the training error is 0. Specifically, they highlight that such learning cannot be accomplished in time complexity dependent on $k^{f(d)}$, where $k$ is the number of neurons in the layer and $d$ is the input dimension. Their main technique is a reduction from the NP-complete problem of POSITIVE ONE-IN-THREE SAT. In their reduction, they strategically position selection gadgets (corresponding to clauses, variables in POITS, and additional data points) along the y-axis, ensuring sufficient spacing between them. This construction can be represented by a piecewise linear function or a combination of ReLUs if and only if it implies a true instance of POITS.\n\nThey also show W[1]-hardness with respect to $d$ for $k = 4$ by reducing the problem to 2 HYPERPLANE-SEPARABILITY. This problem determines whether two given point sets can be strictly separated by two hyperplanes. Additionally, they prove that linear thresholding for 2-layered neural networks is also NP-hard, with a similar reduction as proposed for ReLU activations. Finally, they propose a branching algorithm for learning a 2-layered neural network, which has exponential time complexity with respect to $k$ and $d$.", "questions": "* When you mention \"full dimensional cells,\" are you referring to cells of dimension $d$?\n* In order to prevent the other hyperplanes from becoming convex or concave, does the breakpoint $\\mathbf{x}$ need to lie exclusively on one hyperplane?", "limitations": "The authors discuss various approaches to extend their construction to obtain similar results in higher input dimensions beyond 2, for a fixed training error $\\ge 0$ and for more than 4 ReLUs for the W[1] hardness result. Additionally, they address the possibilities of extending to piecewise linear ReLU and piecewise constant linear thresholding activations and also acknowledge that their techniques might not be applicable to smooth activations. \n\nFinally they address two interesting open questions: 1. Results for the task of minimising generalization error instead of training error and 2. Training neural networks for approximate optimality. ", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The authors have effectively motivated the problem and provided a good background for the problem. The part where they describe the geometry of $\\phi$ and define the concept of a levee, accompanied by illustrative figures, was particularly informative and interesting. ", "weaknesses": "The variable $\\ell$ seems to be overloaded, as it is used for both the loss function and the number of possible levees. This can be confusing when it is introduced again in the selection gadget.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review.\n\nWe will fix the issue with the variable $\\ell$.\n\nYes, \"full-dimensional\" means $d$-dimensional. We will make this precise.\n\nYes, a breakpoint lies on only one hyperplane. We will fix this."}, {"review_id": "GL1jQiLaHD", "reviewer": "Reviewer_2aQG", "summary": "The authors analyze the fpt of training NN. Their main result is that finding a global minimum is hard even for fixed dimension. ", "questions": "What is the best running-time dependency in term of k when can expect for fixed dimension? What is the running time of the fastest exponential algorithm for learning shallow ReLUs? Thresholds? Are their improvements for the running time of the algorithm of the Arora et al., paper?\n\n", "limitations": "Proving hardness results for low dimension. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the direction of studying the FPT of training NN. The reductions are new to the best of my knowledge and could find further applications. \n", "weaknesses": "The authors mention generalization a few times. However, the setting considered is completely detached from generalization.\nFor fixed dimension the sample complexity of the learning problem is fixed and hence can be solved trivially. A more general concern is that low dimension is a rarity in ML applications. In this regard, the number of neurons k seems to be much more interesting. \n\n\"We assume basic knowledge on computational complexity theory.\" I think this sentence can safely be removed. \n\nThere is a large literature on what can and cannot be done efficiently with respect to learning thresholds that the authors ignore.\nOne example is:\n\"Adam Klivans and Pravesh Kothari. Embedding hard learning problems into gaussian space\" and various other papers (regarding learning ReLUs) by Kane and Diakonikolas. While the hardness in these is not NP-hardness, they should be mentioned nevertheless. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review.\n\nIndeed our paper is not concerned about generalization.\nThe goal is to understand the complexity of training in fixed dimension (which was an open question).\nNote that hardness for few dimensions implies hardness for arbitrary dimensions (as we explained) and is thus a stronger result.\nAs regards the number $k$ of hidden neurons, hardness is already known for a single neuron.\nWe additionally show W[1]-hardness w.r.t. $d$ for 4 hidden neurons with zero training error.\n\nThank you for pointing out the papers from the literature.\nWe consider adding them to our references for the final version.\n\nAs regards your questions, note that our hardness results prove that the algorithm by Arora et al. is essentially optimal, that is, $n^{dk}$ is best possible in general (also for linear threshold activation). However, for the convex case, we give an improved algorithm running in $2^{O(k^2d)}$ time.\nThe best running time regarding $k$ for fixed $d$ is still open (Question 2). A running time of $f(k)\\textrm{poly}(n)$ might be possible. This is our major open question."}]

Author rebuttal:

Meta-review: This paper studies several computational complexity problems in training two-layer neural networks. The results are solid and address important questions related to the computational hardness of neural networks. All reviewers have recommended acceptance.
Decision: Accept (poster)