Training Neural Networks is ER-complete
Authors: Mikkel Abrahamsen
Linda Kleist
Tillmann Miltzow
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural networks
complexity
hardness
existential theory of the reals
ER-hardness
NP-hardness.

Abstract: Given a neural network, training data, and a threshold, finding weights for the neural network such that the total error is below the threshold is known to be NP-hard. We determine the algorithmic complexity of this fundamental problem precisely, by showing that it is $\exists\mathbb R$-complete. This means that the problem is equivalent, up to polynomial time reductions, to deciding whether a system of polynomial equations and inequalities with integer coefficients and real unknowns has a solution. If, as widely expected, $\exists\mathbb R$ is strictly larger than NP, our work implies that the problem of training neural networks is not even in NP.
	
Neural networks are usually trained using some variation of backpropagation. The result of this paper gives an explanation why techniques commonly used to solve big instances of NP-complete problems (such as SAT solvers, IP solvers, local search, dynamic programming, etc.) seem to be of no use to this task.


Training Neural Networks is 3R-complete
Mikkel Abrahamsen University of Copenhagen miab@di..m ku. dk
Linda Kleist Technische Universtität Braunschweig kleist@ibr. cs. wa.tu-bs.c de
Tillmann Miltzow Utrecht University t m.miltzoouuu nnl
Abstract
Given neural network, training data, and threshold, finding weights for the neural network such that the total error is below the threshold is known to be NP-hard. We determine the algorithmic complexity of this fundamental problem precisely, by showing that it is -R-complete. This means that the problem is equivalent, up to polynomial time reductions, to deciding whether system of polynomial equations and inequalities with integer coefficients and real unknowns has solution. If, widely expected, 3R is strictly larger than NP, work implies that the problem of training neural networks is not even in NP.
Neural networks are usually trained using some variation of backpropagation. The result of this paper offers an explanation why techniques commonly used solve big instances of NP-complete problems seem not to be of use for this task. Examples of such techniques are SAT solvers, IP solvers, local search, dynamic programming, name a few general ones.
Introduction
Training neural networks is a fundamental problem in machine learning. An (artificial) neural network is brain-inspired computing system. Neural networks modelled by directed acyclic graphs where the vertices are called newron;; for an example consider Figure !
In this paper, we show that it is 3R-complete to decide if there exists weights and biases that will result in a cost below given threshold. Loosely speaking, the complexity class 3IR is defined as problems that are equivalent to deciding whether system of polynomial equations and inequalities and many real unknowns has solution, and it known that NP 3R C PSPACE, although none of these inclusions are known to be strict.
We
ba
Wa
Wy
b2
W6
W
b5
Figure 1: (left) The architecture of neural network with one layer of hidden neurons. As an example training problem, we are given the data points D {11, 2, 1, (3, 2, 1;2, 4, 6)]. the identity the activation function yp for every neuron, the threshold 6 = 10, and the mean of squared errors as cost function. Are there weights and biases such that the total cost below 8? (right) The architecture of an example instance of R RESTRICTED TRAINING. Further, the input consists of the data points dj = (0, 1, 1; 1, and dg = (2, 1, 0: ?, 0). the activation function ppx) = æ. the threshold 6 7, and the Manhattan norm (ll IIx) as the cost function. If we set the weights to
(x, y, z) = (1, 0, -1 1). we easily compute a total error of 4 + = 6, which is below the threshold of
Thus (x. 2) =)= (1, 11) is valid solution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

It is already well known that training neural networks is NP-hard, so one might wonder what we learn from the cooclollesss There exists a large variety of tools for approaching Nomomeeee problems: SAT solvers, IP solvers, local search, dynamic programming. divide and conquer, prune and search, tree-width based algorithms, or even brute force approaches. Note that local search refers to technique where the solution is locally changed combinatorially in small number of components and thus, local search is not related to gradient descent.
In contrast, all research (we are aware of) that actively tries to train neural networks uses variants of backpropagation. Many of the fast and reliable off-the-shelve algorithms solving large instances of NP-complete problems optimally are easy to use, fast, need little to no fine-tuning, and are able to give negative certificates. This makes them much better than backpropagation. So one wonders why backpropagation works better for training neural networks than these strong techniques?
Our result offers the following answers. Assuming NP + नर widely believed, 3RRhhardness gives a strong argument that techniques working for NP-complete problems will not work for training neural networks. As a consequence, our work offers explanations for the observed good experiences with backpropagation when compared to the classical methods.
Neural networks have shown to be superior for solving very complicated tasks, for instance in the context of natural language processing or image recognition. In order to model languages or recognize images, discrete structures (e.g., structures avoiding the use of floating points) are much easier to understand and manipulate and thus in principle preferable over neural networks. This raises the question why do not use discrete structures like formal grammars in order to describe languages rather than neural networks. So far, we can only reason as follows: Modelling languages using grammars was tried over decades but neural networks outperform formal grammars on all benchmark tasks, Yet, it leaves the question lingering: Have we maybe just not tried hard enough to model image processing and other problems by discrete structures? As mentioned before, it widely believed that -R-comllet problems are strictly more difficult than NP-complete problems. In particular, IIR-comllee problems are more expressible and go beyond discrete structures, as they have an inherently continuous nature. In this sense, the fact that training neural networks is complete for EIR indicates that neural networks are a more powerful tool than any purely discrete structures, as they are able to model much richer objects.
While CRR-oomlesssssss gives an interesting perspective on training neural networks, we should also keep the followings facts in mind when interpreting.
Limitations.
In order to prove hardness, we carefully choose the architecture of our neural network to get an instance that is particularly difficult to train. practice, one would often use a fully connected neural network. It remains an interesting question if this is also ARR-comleete (see also Section 4b.
In practice, one might not care about finding the exact optimum when training neural network. For instance, we could ask for a solution that gives a training error of at most OPT + c. Here, OPT the minimum training error and 5 0 a small input parameter. We do not know if this version is also hard.
We show that the problem of exact cost minimization is RR-ooppete. This presupposes that we do all calculations exactly when evaluating the network on an input vector. In practice floating point numbers of 32 bits, or even as little as 8 bits [39], are used, which naturally limits the precision of all calculations. Hence, our result does strictly speaking not imply hardness of the problem from practical perspective.
Given these limitations, we think that it is appropriate to regard EI- co-comllesssess of the training neural network problem as an indication of its practical difficulty, but not as an ultimate truth. Similar limitations hold for many other algorithmic complexity results.
1.1 Definition of the training problem
The source nodes of the graph representing a neural network are called the inpul neurons and the sinks are called outpul neurons, and all other neurons are said to be hidden. A network computes in the following way: Each input neuron 8 receives an input signal (a real number) which is sent through all out-going edges to the neurons that points to. A non-input neuron receives signals through the

---

incoming edges, and then processes the signals and transmits a single output signal to all neurons that a points to. The values computed by the oulput neurons are the result of the computation of the network. A neuron v evaluates the input signals by so-called activation function Se- Each edge has a weight that scales the signal transmitted through the edge. Similarly, each neuron often has bias by that is added to the input signals. Denoting the unweighted input values to neuron V by x E IR* and the corresponding edge weights by w E R then the output of v is given by (P x) + b.).
During training process, the network is fed with input values for which the true output values are known. The task is then to adjust the weights and the biases so that the network produces outputs that are close to the ground truth specified by the training data. We formalize this problem in the following definition.
Definition (Training Neural Networks). The problem of training neural network (NN-TRAINING)
has the following inputs explained above:
A neural network architecture N N= -V, where some S are input neurons and have in-degree 0 and some T C V output neurons and have out-degree 0,
an activation function yp - for each neuron v E V V.V. a cost function e: RR212")
R20
threshold 5 2 0, and
a set of data points D C R|S
Here, each data point d E D has the form d = "c....., V1..... MTT)), where x(d) = (#1....,ā[s) specifies the values to the input neurons and y (d) = (y Myri are the associated ground truth output values. If the actual values computed by the network are y'dd) = (V1...., F/r1)
then the cost is c(y(d), y'))). The total cost is then
C(D) = Σ y'y(d).
DED
We seek to answer the following question. Do there exist weights and biases of N such that C(D) S 8?
We say that a cost function is honest it satisfies that c(y(d), y'd)) = if and only if yd) = y' (d). An example of an honest cost function is the popular mean of squared errors:
T
cly(d) =
(3) 1222
1.2
The Result
As our main result, we determine the algorithmic complexity of the fundamental problem NN- TRAINING.
Theorem 2. NN-TRAINING is 3R-complete, even if
the neural network has only one layer of hidden neurons and three oulput neurons, all neurons use the identity function vp(x) as activation function,
any honest cost function c is used,
each data point is in {0, 1119++171,
the threshold 8 is O, and
there are only three output neurons.
Organization We show that ON-TRRINNNG is contained in 3R in Section and prove its hardness in Section 3 We also discusses how our proof could be modified to work with the ReLu activation function. Section 4 contains discussion and open problems. In the remainder of the introduction, familiarize the reader with the complexity class ER, discuss the practical implications of our result, and give overview of related complexity results neural network training.
3

---

1.3 The Existential Theory of the Reals
In the problem ETR, we are given a logical expression (using A and v) involving polynomial equalities and inequalities with integer coefficients, and the task is to decide if there exist real variables that satisfy the expression. One example is
7or y TR: (x² + n² 6x 4y + 13) 4y + +2² Gy²² 0A(2 2 24 > 1).
+ 2x 4y +
This is yes instance because (x. y) (3 is solution. Due to deep connections to many related fields, ETR is a fundamental and well-studied problem in Mathematics and Computer Science. Despite its long history, we still lack algorithms that can solve ETR efficiently in theory and practice. The Existential Theory of the Reals, denoted by 3R, is the complexity class of all decision problems that are equivalent under polynomial time many-one reductions ETR. Its importance is reflected by the fact that many natural problems are -IR-complete. Famous examples from discrete geometry are the recognition of geometric structures, such as unit disk graphs 29 segment intersection
graphs (28), stretchability [32] 37), and order type realizability (28). Other -om-ccpeeete problems
are related to graph drawing 27 statistical inference 9 Nash-Equilibria 20] 77. Geometric-
embeddability of simplicial complexes
4 geometric packing [5], the art gallery problem [3] non-
negative matrix factorization [36,, continuous constraint satisfaction problems [31 and geometric
linkage constructions [. We refer the reader to the lecture notes by (28] and surveys by [35 and 33
for more information on the complexity class ERR.
As mentioned before, establishing FRR-completeness of a problem gives us a better understanding of the inherent difficulty of finding exact algorithms for it. Problems that 3RR-oopleee often require irrational numbers of arbitrarily high algebraic degree or doubly exponential precision to describe valid solutions. These phenomena make it hard find efficient algorithms. We know that NP C 3R C PSPACE [2), and both inclusions are believed to be strict, although this remains an outstanding open question in the field of complexity theory. In a classical view of complexity, we distinguish between problems that we can solve in polynomial time and intractable problems that may not be solvable in polynomial time. Usually, knowing that a problem is NP-hard is argument enough to convince us that we cannot solve the problem efficiently. Yet, assuming NP & AR, 3IR-hardness proves the limitations of NP methods. To give a simple example, NP-complete problems can be solved in a brute-force fashion by exhaustively going through all possible solutions. Although this method not very sophisticated, it is good enough to solve small sized instances. The same is not possible for -lR-coeelete problems due to their continuous nature. As a second example, the difficulty of solving 3l -lmmplteee problems is nicely illustrated by the problem of placing eleven unit squares into minimum sized square container without overlap. Whether given square can contain eleven unit squares can be expressed as an foR-formula of modest size, so if such formulas could be solved efficiently, would know the answer (at least to within any desired accuracy). However, it is only known that the sidelength is between 2 + 4/V5 3.788 and 3.878 (1].
1.4 Previous Hardness Results for NN-TRAINING
has been known for more than three decades that is NP-hard to train various types of neural networks for binary classification (8] 30, 255, which means that the output neurons use activation functions that map to {0, The first hardness result for networks using continuous activation functions appears be by Jones (24), who showed harhhess of training networks with two hidden neurons using sigmoidal activation functions and one output neuron using the identity function.
Hush [23] and Šima [38] showed hardness of training networks with no hidden neurons and a single output neuron with sigmoidal activation function. The latter paper contains an informative survey of the numerous hardness results that were known at that time.
Recently, the attention has been turned to networks using the so-called ReLU function [x] max (0, 2 as activation function due to its extreme popularity in practice. Goel et al. (22 and Dey et al. [15] showed that it is even NP-hard to train a network with no hidden neurons and a single output neuron using the ReLU activation function. For hardness on other simple architectures using In order to prevent overfitting, we may stop training early, although the costs could still be reduced further. the context of training neural networks, overfitting can be regarded as secondary problem, as the problem only emerges after we have been
the ReI.U activation function, see [1] 10 6

---

able to train the network on the data at all. Thus, none of the complexity theory papers on this subject address overfitting,
Besides training neural networks, there exist other NP-hard problems related to neural networks, e.g.. continual learning [26]. Some of these training problems
only NP-hard, but also contained in NP, implying that they are NP-complete. For instance, consider fully-connected network with one hidden layer of neurons and one output neuron, all using the ReLU activation function. Here, it not hard to see that the problem of deciding if total cost = 0 can be achieved is in NP. We will show that the network does not need to be much more complicated before the training problem becomes EIR co-moeeeee even when ó = O. Because it is easy to add inconsistent data points, one can also use our reduction to show 3R-hardness for any threshold 8 >> 0.
2 Membership
In order prove that NN-TRAINING is 3R-cooplete, we show that the problem is contained in the class FIR and that it is 3R-hard (just as when proving NP-completeness of a problem). The first part is obtained by proving that NN-TRAINING can be reduced to ETR, while the latter is to present reduction in the opposite direction. To see that NN-TRAINING E IRR, we use recent result by Erickson al. [18]. Given an algorithmic problem, real verification algorithm A has the following properties. For every yes-instance I, there exists a witness w consisting of integers and real numbers. Furthermore, (1, w) can be executed on the real RAM in polynomial time and the algorithm returns yes. On the other hand, for every no- instance I and any witness w the output AI, w) is no. [18] showed that an algorithmic problem is in 3R if and only if there exists a real verification algorithm. Note that this is very similar to how NP-membership is usually shown. The crucial difference is that a real verification algorithm accepts real numbers as input for the witness and works on the real RAM instead of the integer RAM.
It remains to describe a real verification algorithm for NN-TRAINING. As witness, we simply describe all the weights of the network. The verification then computes the total costs of all the data points and checks if it is below the given threshold 6. Clearly, this algorithm can be executed in polynomial time on the real RAM. Note that if the activation function is not piecewise algebraic, e.g.. the sigmoid function (fx) 1/1+e =, it is not clear that we have 3R- meeemmrebrsipp as the function is not supported by the real RAM model of computation [18]. Specifically, Richardson's 's theorem states that computations involving analytic functions may be undecidable [33
Reduction
In the following, we describe a reduction from the EIR-hard problem ETR-INV NN-TRAINING. As a first step, we establish 3RR-haddees of ETR-INV using previous work. As the next step, define the intermediate problem RESTRICTED TRAINING. In the main part of the reduction, we describe how to encode variables, subtraction operations as well as inversion and addition constraints in RESTRICTED TRAINING. Finally, we present two modifications that enable the step from RESTRICTED TRAINING to NN- NN-TRAINING.
3.1 Reduction to ETR-INV-EQ
In order to define the new algebraic problem ETR-INV-EQ, we recall the definition of ETR-INV. An ETR-INV formula + = (2 xn)) is a conjunction (Am C)) of m 2 0 constraints where each constraint C, with variables x, y. 2 E (I1,...,,f, .n has one of the forms
y
x r.y=
The first constraint is called an addition constraint and the second is an inversion constraint. An instance I of the ETRINNV problem consists of an ETR-NNV formula T. The goal is to decide whether there are real numbers that satisfy all the constraints.
Abrahamsen et al. (5] established the following theorem. Note that their definition of ETR-INV formulas asks for number of additional properties (e.g., restricting the variables to certain ranges) that we do not need for our purposes, so these can be omitted without affecting the correctness of the following result.
5

---

Theorem A (5), Theorem 3). ETR-INV is ER-compeete
For our purposes, we slightly extend their result and define the algorithmic problem ETR-INV-ER in which each constraint has the form
y
0.
We call constraint of the above form a combined constraint, as it is possible express both inversion and addition constraints using combined constraints. To see that ETR-INV ITR-INN-EQ also clR-complete, show how to transform instance of ETR-INV into instance of ETR-IN that we can assume that every variable contained in at least one addition constraint; otherwise, we add a trivially satisfiable addition constraint, i.e., consider the case that a variable of & appears in (at least) two inversion constraints, i.e., there exist two constraints of the form y1 1 and x 1/2 1. This implies y1 y/2 and we can replace all occurrences of 1/2 by 1/1 Thus, we may assume that each variable appears in at most one inversion constraint. Now, if there is an inversion constraint x y 1, we replace all occurrences of y (in addition constraints) by z_1 In this way. the inversion constraint becomes redundant and we can remove it. We are then left with collection of combined constraints. This proves =IZ-completeness of ETR-INV-EQ.
First, note
for
variable y. Furthermore,
3.2 Reducing ETR-INV-EQ to RESTRICTED TRAINING
In the following, we reduce ETR-INV-EQ to NN-TRAINING, We start by defining the algorith- mic problem RESTRICTED TRAINING which differs from NN-TRAINING in the following three properties:
Some weights and biases can be predefined in the input.
The output values of data points may contain question mark symbol '?"
When computing the total cost, all output values with question marks are ignored.
Figure displays an example of such instance.
In the rest the reduction, we will use the identity as activation function, and threshold d = 0. The reduction works for all honest cost functions.
High-level Architecture. The overall network consists of two layers, as depicted in Figure | Note that these layers are nor fully connected. Some weights of the first layer will represent variables of the ETR-INV-EQ; other weights will be predefined by the input and some will have purely auxiliary purposes. Furthermore all biases are set O.
3.2.1 The Gadgets
In the following, we describe the individual gadgets represent variables, addition and inversion. Then we show how we combine these parts. Later, we modify the construction to remove preset weights, biases and question marks. At last, we will sketch how this reduction can be modified to work with ReLU functions as activation functions.
Subtraction Gadget. The subtraction gadget consists five neurons, four edges, two prescribed weights and one data point. See Figure (left) for an illustration of the network architecture of the
Figure 2: (left) The architecture of the subtraction gadget. The data point d = 11,1;0) enforces that the constraint -y
(right) The architecture of the inversion gadget. The data points di (0, 1,0; 1) and d2 (1, 0, 1;0) enforce y and 0, respectively, implying that y 1.

---

subtraction gadget. The data point d' = (1, 1) enforces that the constraint = as can be easily calculated.
Inversion Gadget. The purpose of the inversion gadget is to enforce that two variables are the inverse of one another. consists of six vertices, five edges, two prescribed weights and two data points; for an illustration of the architecture see Figure 2 (right). A simple calculation shows that the data point d1 = (0. 1, 0; 1) enforces the constraint y 2 = 1, while the data point d2 = (1, 0, 1:0) enforces the constraint
= 0. It follows that y 1.
Variable Gadget. For every variable, we build a gadget such that there exist four weights on the first layer with the values x, -x, -1/x.
The variable-gadget is combination of two subtraction gadgets and one inversion gadget. In total has five input neurons, four middle neurons and two output neurons, see Figure 3 for an illustration of the architecture and the initial weights. We denote the input neurons by $1,..., 85. We denote the output neurons by a, b. The output neuron is drawn twice for clarity of the drawing. We have the data points dj = d4 (0, 0, 1;
?), d2 = (0, 0, 1, 1, 0,0, ?), d3 = (0,0, 1, 0; 1), and
The data point dj enforces w =z see this note that the output neurons with a question mark symbol are irrelevant. Similarly, input neurons with O-entries can be ignored. The remaining neurons form exactly the subtraction gadget. Analogously, we conclude that y = -2, -, using data point d2- From the data point d3. we infer that y 1. We infer x. using d4, We summarize our observations the following lemma.
Lemma (Variable- (Variable-Gadeet), The variable gadget enforces the following constraints on the weights x y = 1/x, and -1/x.
C+0
0-0
a
82
83
a
O+0
S4
0x0
0+0
Figure 3: (left) The variable gadget. (middle) A schematic drawing of three combined variable gadgets. While the two output neurons of all gadgets identified, all other neurons remain distinct. (right) For every '?' in a data point d, we add two more vertices and edges to the neural network.
Combining Variable Gadgets. Here, we describe how to combine n variable gadgets. For the architecture, identify the two output neurons of all gadgets; all other neurons remain distinet. Figure 3 gives a schematic drawing of the architecture for the case of n = 3 variables. Additionally, construct four data points as described for the
construct 4n data points. For each variable, variable gadget; the additional input entries are set to 0. In this way, we represent all n variables of an ETR-INV-EO formula. Furthermore, for each variable v, have edges from the first to the second vertex layer, with the values -r, 1/2, and - 1/1r, see Lemma 3
Combined Constraint. For the purpose of concreteness, we consider the combined constraint C 0, where each is either the value of some variable,
of an ETR-INV-ER instance w W2 + its inverse, its negative or negative inverse. Then, by construction, there exists weight in the combined variable gadget for each wi Figure 4 depicts the network induced by the edges and the output vertex a; in particular, note that all the edges with weights w; are connected to a, as can also be checked in Figure 3
7

---

22
m7
4
22
Figure 4: (left) There are three weights encoding wi, W2, and w3- They are all connected to the output vertex (right) For each middle neuron m, add input neuron and the edges and mg with weights 21 and 22.
In order to represent the constraint C, we introduce data point d(C)) It has input entry exactly at the input neurons of W1, W2, and Wy; otherwise it is O. Its output is defined by 0 for and '?' for b. Thus d(C) enforces the combined constraint C. Note that enforcing the combined constraints does not require alter the neural network architecture to modify any of these weights.
3.2.2 Removing Fixed Weights
Next, we modify the construction such that we do not make use of predefined weights. To this end, we show how enforce edge weights of +1. Recall that, by construction, all predefined weights are either +1 or 1 and that the neural network architecture has precisely two layers. Furthermore, by construction, every middle neuron is incident least one edge with a weight that is specified by the input.
Globally, we add one additional output neuron q- For each middle neuron m, perform the following steps individually: We add one more input neuron 8 and insert the two edges sm and mg. We will show later that the weights 21 and 22 on the two new edges can be assumed be 1 as depicted in Figure 4 We modify all previously defined data points such that they have output "?' for output neuron q. They are further padded with zeros for all the new input neurons.
Furthermore, we add one data point d(m) with input entry for and O otherwise, and output entry 1 for q and ??' otherwise. This data point ensures that neither 21 22 are 0.
Next, we describe a simple observation. Consider single middle neuron m, with incoming edges and outgoing edges. Let us denote some arbitrary input by layer by w (wi...., w/k ), and the weights the second layer by w = (71, Wi). We consider all vectors to be columns. Then, the output vector for this input is given by (a, w) W. where (;, denotes the scalar product.
.ul,)...aa). the weights on the first
Let # 0 be some real number. Note that replacing w by w = = w and w by w' -1/a- w does not change the output.
Observation 4. Scaling the weights of incoming edges of middle neuron by a + 0 and the weights of outgoing edges by a does not change the neural network behavior.
This observation can be used to assume that some non-zero weight equals! because we can freely choose some * 0 and multiply all weights as described above without changing the output. In particular, for the middle neuron m, we may assume that 21 = 1, see Figure Here, we crucially use the fact that 21 is not zero. This standard technique is often referred to normalization. Moreover, by the data point d(m), we can also infer that the weight equals 1, as we know 21 22 =
With the help of the edge weights the weight some other edge e incident to m that we wish to fix the value (the case of is analogous). We describe the case that for some output neuron t the edge mt is outgoing edge m, the case an incoming edge is analogous. See Figure for an illustration. We add a new data point d, with output entries being 1 for and "?' otherwise and input entries being I for and 0 otherwise. Given that 21 = 1, the data point implies that 2 = as well.
22 1, we are able to set more weights to +1. 1et z denote
3.2.3 Free Biases
In this section, we modify the input such that we do not make use of the biases being set zero. First note that a function f representing certain neural network, might be represented by several weights

---

and biases. To be specific. let b E I the bias of a fixed middle neuron m. Denote by 21,..., 2g the
weights of the outgoing edges of m and bi..... ..... by the biases of the corresponding neurons. We can replace these biases as follows: we replace b by b' = 0 and b, by b/g b; + 2, b. We observe that the new neural network represents exactly the same function f. Note that we used here explicitly the fact that the activation function is the identity. This may not be the case for other activation functions. From here on, we assume that all biases in the middle layer are set to zero.
It remains to ensure that the output neurons are zero as well. We add the additional data point d= (0. 0) that is zero on all imputs and outputs. The value of the neural network on the input is precisely the bias of all its output neurons. As our threshold is zero and the cost function is honest, we can conclude that the biases on all output neurons must be zero as well. We summarize this observations as follows.
Observation 5. All biases can be assumed to be zero.
3.2.4 Removing Question Marks
To complete the construction, it remains to show how to remove the question marks from the data points. We remove the question marks one after the other. For each data point d and every contained symbol "?', we add an input neuron, a middle neuron, the edge between them and the edges from the input neuron to the output neuron containing the considered symbol '?' in d, see Figure 3 for schematic illustration.
Due to the additional input entry for the added input neuron, we need to modify all data points slightly. In d, we set the additional entry to 1; for all other data points, we set it to O. Moreover, we replace the considered symbol '?" in d by the entry 0.
We have to show that this modification does not change the feasibility of the neural network. Clearly, the output entries of d with the question mark can now be freely adjusted using the two new edges. At the same time no other data point d' can make use of the new edges as the value for the new input neurons equals to 0.
This finishes the description of the reduction. Next, we show its correctness.
3.3 Correctness
Let be an IIR-INV-EQ instance on n variables. We construct an instance I of NN-TRAINING as described above. First note that the construction is polynomial in n in time and space complexity. To be precise, the size of the network is O(n), the number of data points O(n), and each data point has a size in On)) Thus, the total space complexity is in Onz)). Because no part of the construction needs additional computation time, the time complexity is also in O(n²).
We show that d has a real solution x² E R" if and only if there exists a set of weights for I such that all input data are mapped to the correct output.
Suppose that there exists a solution x' E R satisfying all constraints of T. We show that there weights for that predict all outputs correctly for each data point. By construction, for every variable x, there exist edge weights x, -x, 1/2,-1 -1/r. We set these weights to the value of x given by x². Moreover, we prescribe all other weights as indented by the construction procedure; e.g., 1 for the prescribed weights. By construction and the arguments above, all data points are predicted correctly by the neural network. Specifically, all the data points introduced for the combined constraints are correctly predicted, as x" satisfies +.
For the reverse direction, we suppose that we given weights for all the edges of the network in I. By Section 3.2.3] we can assume that all biases are zero without changing the function that is represents by the neural network. By Observation 4 we may normalize the weights without changing the behaviour of the neural network. Consequently, we can assume that all the weights prescribed for the RESTRICTED TRAINING problem. By Lemma 3 there exist edge weights that consistently encode the variables. Thus, we use the values of these weights to describe a real solution xx that satisfies $. Due to the data points introduced for the combined constraints, we can conclude that all combined constraints of t are satisfied.
This finishes the proof of Theorem 2

---

4 Conclusion
Training neural networks is undoubtedly fundamental problem in machine learning. We present clean and simple argument to show that NN-TRAINING is complete for the complexity class EIR, Compared to other prominent -RRhhrddeess proofs, such as [4 or [S our proof is relatively accessible. Our findings illustrate the fundamental difficulty of training neural networks. At the same time, we give an indication on why neural networks can very powerful tool, since we prove neural networks to be more expressive than any learning method involving only discrete parameters or linear models: practice, neural networks proved useful to solve problems that cannot be solved by combinatorial methods such ILP solvers, SAT solvers, or linear programming. and our work gives a reason why (at least under the assumption that NP * =IR).
In our reduction, we carefully choose which edges should be part of our network to obtain an architecture that is particularly difficult to train. In practice, connected network, where each neuron from one layer has an edge to each neuron of the next. It thus an exciting and challenging open problem for future research to find out if training fully connected neural network with one hidden layer of neurons is also IR-complete which we expect to be the case. We formulate the following conjecture.
common use a simpler fully
Conjecture 6. NN-TRAINING is IR-complete, even fully connected networks with one hidden layer and ReLU activation functions.
Note that as mentioned in Section I.4 this requires at least two output neurons, as the problem is otherwise in NP (when using ReLU or identity activation functions).
Acknowledgments. We thank Frank Staals for many enjoyable and valuable discussions. We thank Thijs van Ommen for helpful comments on the write-up. We thank anonymous reviewers for their helpful comments and questions.
Mikkel Abrahamsen is part of Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582. Linda Kleist is supported by postdoe fellowship of the German Academic Exchange Service (DAAD). Tillmann Miltzow is generously supported by the Netherlands Organisation for Scientific Research (NWO) under project 016. Vew...19.255.....
10

---

References
[1] Zachary Abel, Erik Demaine, Martin Demaine, Sarah Eisenstat, Jayson Lynch, and Tao Schardl. Who needs crossings? Hardness of plane graph rigidity. In 32nd International Symposium Computational Geometry (SoCG 2016), pages 3:1-3:15, 2016.
[2] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. Irrational guards are sometimes needed, In SOCG, pages 3:1-3:15, 2017.
[3] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The gallery problem is -R-comlett.. In STOC, pages 65-73, 2018. to appear JACM.
[4] Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Geometric embeddability of com- plexes ][&-oomlleee. wxXi:22008.02585 2021.
[5] Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. framework for EIR-completeness of two-dimensional packing problems. FOCS, 2020.
[6] Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks polynomial time. In Proceedings of the Thirty-Secone Conference on Learning Theory (COLT 2019), pages 195-268, 2019.
[7] Vittorio Bilò and Marios Mavronicolas. A catalog of 3--coplette decision problems about Nash equilibria in multi multi-player games. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), 2016.
[8] Avrim L. Blum and Ronald L. Rivest. Training 3-node neural network is NP-complete. Neural Networks, 5(1):117-127, 1992.
[9] Tobias Boege. Incidence geometry in the projective plane via almost-principal minors of symmetric matrices. arXiv preprint arXiv:2 2021.
[10] Digvijay Boob, Santanu S. Dey, and Guanghui Lan. Complexity of training ReLU neural network. Discrete Optimization, 2020. In press.
[11] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for ConvNet with Gaussian inputs. In Proceedings of the 34 th International Conference on Machine Learning (ICM)2011), 2017.
[12] John Canny. Some algebraic and geometric computations in PSPACE. In Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988), pages 460-467. ACM, 1988.
[13] Jean Cardinal. Computational geometry column 62. SIGACT News, 46(4):69-78, 2015.
[14] Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber. Intersection graphs of rays and grounded segments. In International Workshop on Graph- Theoretic Concepts in Computer Science, pages 153-166. Springer, 2017.
[15] Santanu S. Dey, Guanyi Wang, and Yao Xie. Approximation algorithms for training one-node ReLU neural networks. IEEE Transactions on Signal Processing, 68:6696-6706, 2020.
[16] Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Pawel Rzgiewski. coopplpeteesssss and area-universalltty ArXiv 1712.05142, 2017.
[17] Michael Gene Dobbins, Andreas Holmsen, and Tillmann Miltzow. universality theorem for nested polytopes. arXiv, 1908,02213, 2019.
[18] Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow. Smoothing the gap between np and er. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 1022-1033. IEEE, 2020.
[19] Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality. arXiv preprint UrXiv:2105.088 2021.
11

---

[20] Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. ETR compleeelss for decision versions of player (symmetric) Nash equilibria. Proceedings of the 42nd International Colloquium on Automaia, Languages, and Programming (ICALP 2015), part I, pages 554-566, 2015.
[21] Thierry Gensane and Philippe Ryckelynck. Improved dense packings of congruent squares in square. Discrete & Computational Geometry. 34(1)997-109, 2005.
[22] Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training 2epth-2 ReLU networks, 2020. Preprint http:::/ttttttttaae http:aawwww.....aaa.a/aaaa wrrg/abs//0111 13550
[23] Don R. Hush. Training a sigmoidal node is hard. Neural Computation, 11 11(5):1249-126)) 1999.
[24] L. K. Jones. The computational intractability of training sigmoidal neural networks. IEEE
Transactions on Information Theory. 43(1):167-173, 1997.
[25] Stephen Judd. On the complexity of loading shallow neural networks. Journal of Complexity, 177-1177- 1988.
[26] Jeremias Knoblauch, Hisham Husain, and Tom Diethe. Optimal continual learning has perfect memory and is NP-hard. In Proceedings of the 37th International Conference Machine Learning (ICML 2020), pages 5327-5337, 2020.
[27] Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal. The complexity of drawing graph in a polygonal region. International Symposium on Graph Drawing and Network Visualization, 2018.
[28] Jifí Matoušek. Intersection graphs of segments and 3R, 2014. Preprint, https://arxx: abs/1406. 2636
[29]
Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs. Journal of Combinatorial Theory, Series B, (03(1):114-143 2013.
[30] Nimrod Megiddo. On the complexity of polyhedral separability. Discrete & Computational Geometry, 344):325-337, 1988.
[31] Tillmann Miltzow and Reinier F. Schmiermann. On classifying continuous constraint satisfaction problems. Arxiv, abs/aa00.02202222 2021. FOCS 2021.
[32] Nicolai Mnëv. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Oleg Y. Viro, editor, Topology and geometry Rohlin seminar, pages 527-543, 1988.
[33] Dan Richardson and John Fitch. The identity problem for elementary functions and constants. In Proceedings of the international symposium on Symbolic and algebraic computation, pages 285-290, 1994.
[34] Jürgen Richter-Gebee and Günter M. Ziegler. Realization spaces of 4-polytopss are universal. Bulletin of the American Mathematical Society, 32(4):403-413 1995.
[35] Mareus Schaefer. Complexity of some geometric and topological problems. In Proceedings of the 17th International Symposium Graph Drawing (GD 2009), pages 334-344, 2009.
[36] Yaroslav Shitov. A universality theorem for nonnegative matrix factorizations. ArXiv 1606.09068, 2016.
[37] Peter W. Shor. Stretchability of pseudolines is hardard. In Peter Gritzmann and Bernd Sturmfels, editors, Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of DIMACS- Seriey in Discrete Mathematics and Theoretical Computer Science, pages 531-554. American Mathematical Society and Association for Computing Machinery, 1991.
[38] Jiff Šima. Training single sigmoidal neuron hard. Neural computation, 14(11):209-2278. 2002.
12

---

[39] Naigang Wang. Jungwook Choi, Daniel Brand, Chia- Yu Chen, and Kailash Gopalakrishnan. Training deep neural networks with 8-bit floating point numbers. Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS 2018), page 7686-7695, 2018
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "o2QGHDejF0T", "reviewer": "Reviewer_hUB1", "summary": "This paper proves ETR-hardness of the problem of training a neural network to achieve a loss below a given threshold. \nETR complete problems are believed to be harder to solve than NP-complete problem, hence the results strengthen existing hardness results for training neural networks. The proof is via a reduction to the problem of deciding whether a polynomial equation with integer coefficients has a solution over the reals. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While the ETR hardness results are nice, I believe the conclusions made by the authors are misleading. The authors claim that  SAT-solving methods will not work well for training (and have not worked well in the past). This is not true: see for example the influential: \"Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks\". The suggestion that learning discrete structures such as grammars or Automates is easier than learning NN also does not fair well with the experience in ML, where training an NN is usually much easier than learning discrete models. The idea that NP-complete problems are \"easy\" and ETR problems are \"hard\" is strange. Both worst-case hardness results should imply intractability. The authors should spend more on discussing the worst case nature of their hardness results. Also the authors should be more careful in using the term local search (and claiming it will not work for training). After all, gradient based optimization is a local search  method. \nAdditionally, the paper proves hardness results for NN architectures that are rarely used in practice. Extending the results to more popular architectures (such as fully connected ones) would strengthen the results.   Another is to use ETR solvers to get algorithmic results in training neural networks. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "clmoS3uyNZz", "reviewer": "Reviewer_GFLf", "summary": "It is known that training neural networks is NP-hard, and this work makes a further attempt by studying the ER-hardness of the problem. The definition of 'neural network training' used in the proof of this paper is: do there exist weights such that the neural net maps every data input to corresponding output? This work proves that training neural networks is ER-complete, which is believed to be harder than NP.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\n\nIt seems that this paper is the first to study the ER-hardness of training neural networks. So, good originality as far I see.\n\n**Quality**\n\nI find no errors in the proofs, and the overall quality is good in my opinion. However, I do find some arguments not well supported.\n\n1. It is claimed in the abstract (line 1-4) that this paper proves that finding weights such that *the error is below a threshold* is ER-complete. However, theorem 2 requires *the error is 0*. Is it easy to extend theorem 2 to 'below a threshold'? If yes, then it should be discussed somewhere. If no, then the claim in the abstract is not appropriate.\n2. In line 188, it is stated that some additional properties of the original ETR-INV can be ignored without affecting the correctness of the theorem A. Given that it is a theorem, I think it should be provided with proof.\n3. There are three major differences between the regular neural networks and the neural networks used in this paper, i.e., (1) the neural network architectures considered in this paper are carefully constructed; (2) the activation function is always identity; (3) perfect mapping (zero error) is considered, rather than below a threshold. I appreciate the authors address the first limitation with a discussion about the ReLU activation. However, it is still interesting to see more discussion about the other two limitations. Rigorously speaking, to make *\"Training Neural Networks is ER-complete\"* such a title, it is expected that the above three limitations are fully discussed, if not solved.\n\n**Clarity**\n\nOverall the paper is well written, but I do have some complaints about how the proof is structured. For example, summarizing section 2 with a lemma may improve the clarity. \n\n**Significance**\n\nThe hardness of training neural networks is fundamental and surely interesting. Proving it to be ER-complete is indeed a further step from NP-hard. However, the three limitations discussed above bring down the significance of this paper to some extent. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I appreciate that the authors provide some discussion on the limitation of the activation function. It would be much better if the architecture limitation and the threshold limitation are discussed in details. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "Xt0Rxt9aCVf", "reviewer": "Reviewer_CGEk", "summary": "The authors showed that the training of neural networks is $\\exists\\mathbb{R}$-complete, which implies the reason that techniques commonly used for solving large NP-complete problems do not work for neural network training.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ The authors partially answered the question of why backpropagation works better for training neural networks than those methods commonly used for NP-complete problems.\n+ The authors determined the algorithmic complexity of nn-training.\n\nWeaknesses:\n+ The main result assumes that the activation function $\\phi(x)$ is the identity function, while the most commonly used activation is practice is ReLU. It would be interesting to show that Conjecture 6 is true.\n+ As the authors already mentioned, it is interesting to see if training fully-connected neural networks can also fall into the category of $\\exists\\mathbb{R}$-complete.\n\n\nCorrectness:\n+ The paper has no false claim to the best of my knowledge.\n\nClarity:\n+ The overall structure of this paper is clear.\n\n*After Rebuttal*\n\nI have read through other reviews, and I agree that the notion of training in the paper is not as convincing as I originally thought it would be. However, I also agree with g6Te that there may be interesting and sound techniques established. I change my score to 6.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "Qd0fQ892WpG", "reviewer": "Reviewer_g6Te", "summary": "This paper proves that THE \"Neural Network Training\" problem is complete in a complexity class called ETR that is believed to be strictly larger than the class NP. Thus, it establishes a stronger hardness result than the well-known NP-Hardness for the problem, and shows that the problem is, in fact, probably not NP-Complete.\n\nETR stands for Existential Theory of the Reals and it can be thought of as a continuous analog of NP. The canonical complete problem for this class is similar to SAT by instead of boolean clauses we have algebraic constraints, and instead of a satisfying boolean assignment to the variables we are looking for an assignment of real values.\n\nThe result is proved by:\n(1) Proving containment in ETR: this is the easy direction and follows from known methods for proving containment in ETR.\n(2) Proving ETR-Hardness via a reduction from the canonical ETR problem. This is done by simple but clever gadgets that encode algebraic constraints with neural networks and data points.\n\nThis result is proved even for very restricted settings of the NN-Training problem, with one hidden layer and standard activation functions and so on.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this is a great submission giving a strong and fundamental theoretical result about the core problem of \"NeurIPS\" and ML. Moreover, as the authors explain, this theoretical result comes with some conceptual message: it sheds light on why neural networks are more expressive than other discrete structures, and on why SAT-solvers and other methods that are useful against NP-complete problems in practice, are not as effective against NN-Training (because it is not NP-complete!).\n\nFrom a technical perspective the proof is not difficult but it requires some work and familiarity with recent progress on proving ETR completeness; a topic that is rather active these days in the theory community.\n\nThe paper is very well-written and provides clear motivations and explanations for a wide audience. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that the problem of (**exact**) empirical risk minimization (ERM) in linear neural networks is ETR-Complete. The result is technically innovative, and interesting. Nevertheless it was felt by the reviewers that some of the conclusions made by the authors are misleading, and not very convincing. 

While exact solving of the ERM objective is an interesting question, there is a crucial gap between ERM and training -- which normally refers to learning good parameters of the model that obtain small *excess* risk. Because of that, it is normally justified to find an $\textrm{OPT}+\epsilon$ solution for ERM. This is justified because $\epsilon$ error is incurred anyway due to statistical uncertainty. Moreover, in any reasonable model (where solution of the ERM can begin to lead to some generalization guarantees) finding an $\textrm{OPT}+\epsilon$ is regarded NP hard (by standard discretization/packing/covering and union bound arguments).

If the authors want to draw conclusions on the hardness of training from hardness of ERM solving, they would need to further justify this. In the final revision please tone down the last paragraphs in the introduction, and discuss the difference between *exact* ERM and training, as well as address other reviewers comments.
Decision: Accept (Poster)