Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete
Authors: Daniel Bertschinger
Christoph Hertrich
Paul Jungeblut
Tillmann Miltzow
Simon Weber
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural Network Training
Computational Complexity
Existential Theory of the Reals
Algebraic Universality
Empirical Risk Minimization
TL;DR: We show that training even simple neural network architectures is more difficult than solving NP-complete problems.

Abstract: We consider the algorithmic problem of finding the optimal weights and biases for a two-layer fully connected neural network to fit a given set of data points, also known as empirical risk minimization. We show that the problem is $\exists\mathbb{R}$-complete. This complexity class can be defined as the set of algorithmic problems that are polynomial-time equivalent to finding real roots of a multivariate polynomial with integer coefficients. Furthermore, we show that arbitrary algebraic numbers are required as weights to be able to train some instances to optimality, even if all data points are rational. Our result already applies to fully connected instances with two inputs, two outputs, and one hidden layer of ReLU neurons. Thereby, we strengthen a result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021]. A consequence of this is that a combinatorial search algorithm like the one by Arora, Basu, Mianjy and Mukherjee [ICLR 2018] is impossible for networks with more than one output dimension, unless $\text{NP} = \exists\mathbb{R}$.

Training Fully Connected Neural Networks is 3R-Complete
Daniel Bertschinger
Christoph Hertrich"
Department of Computer Science
Department of Mathematics
ETH Zurich
London School of Economics and Political Science
Zurich, Switzerland
London, United Kingdom
daniel. www.ssrhiheeerriinn... .ttz.
c. w.hherrtchhhsee ac.uk
Paul Jungeblut
Tillmann Miltzow
Institute of Theoretical Informatics
Department of Information and Computing Sciences
Karlsruhe Institute of Technology
Utrecht University
Karlsruhe, Germany
Utrecht, The Netherlands
p jug edu
t. t.miltzow@uu. nl
Simon Weber
Department of Computer Science ETH Zurich
Zurich, Switzerland
simon. weber@inf ettz. ch
Abstract
We consider the algorithmic problem of finding the optimal weights and biases for two-layer fully connected neural network to fit given set of data points, also known as empirical risk minimization. We show that the problem is 3R-compeete. This complexity class can defined as the set of algorithmic problems that are polynomial-tin -immi equivalent to finding real roots of multivariate polynomial with integer coefficients. Furthermore, we show that arbitrary algebraic numbers are required as weights to be able to train some instances to optimality, even if all data points are rational. Our result already applies to fully connected instances with two inputs, two outputs, and one hidden layer of ReT.U neurons. Thereby, we strengthen a result by Abrahamsen, Kleist and Miltzow [NcurIPS 2021]. A consequence of this is that combinatorial search algorithm like the one by Arora, Basu, Mianjy and Mukherjee [ICLR 2018] impossible for networks with more than output dimension, unless NP ER.
Introduction
The usage of neural networks in modern computer science is ubiquitous. They are arguably the most powerful tool at our hands in machine learning [42]. One of the most fundamental algorithmic questions asks for algorithmic complexity to actually train neural network. For arbitrary network architectures, Abrahamsen, Kleist and Miltzow [3] showed that the problem is 3R-complete already for two-layer neural networks and linear activation functions. The complexity class 3R defined the family of algorithmic problems that are polynomial-time -immiill-immeee equivalent to finding real roots of
Mooeed to Université Libre de Bruxelles, Belgium, and Universtiit Frankfurt, Germany, after submission of this article.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

multivariate polynomials with integer coefficients. Under the commonly believed assumption that EIR strict superset of NP, this implies that training neural network is harder than NC-coeleete problems.
The result by Abrahamsen, Kleist and Miltzow [3] has one major downside, namely that the network architecture is adversarial: The hardness inherently relies on choosing a network architecture that is particularly difficult to train. The instances by Abrahamsen, Kleist and Miltzow could be trivially trained with fully connected neural networks. This stems from the fact that they use the identity function as the activation function which reduces the problem to matrix factorization. While intricate network architectures, e.g. convolutional and residual neural networks, pooling, autoencoders and generative adversarial neural networks are common in practice, they are usually designed in way that facilitates training rather than making it difficult [42]. We strengthen the result in [3] by showing IRR-compeeteness for fully connected two-layer neural networks. This shows that AIR-hardness does not stem from one specifically chosen worst-case architecture but is inherent in the neural network training problem itself. Although in practice a host of different architectures are used, fully connected two-layer neural networks are arguably the most basic ones and they are often part of more complicated network architectures [42]. We show hardness even for the case of fully connected two-layer ReLU neural networks with exactly two input and output dimensions.
Remarkably, with only one instead of two output dimensions, the problem is in NP. This follows from a combinatorial search algorithm by Arora, Basu, Mianjy and Mukherjee [6]. Our result explains why their algorithm was never successfully generalized to more complex network architectures: adding only a second output neuron significantly increases the computational complexity of the problem, from being contained in NP to being complete for FR.
To achieve our result, our reduction follows a completely novel approach compared to the reduction in [3]. Instead of encoding polynomial inequalities into an adversarial network architecture, we make use of the underlying geometry of the functions computed by two-layer neural networks and utilize the fact that their different output dimensions have nonlinear dependencies.
Outline. We start by formally introducing neural networks, the training problem, and the existential theory of the reals in Section 2. Thereafter, we present our main results in Section 3. In Section 4 we provide different perspectives the strengths and limitations. We cover further related work in Section 5. Finally, we finish the main part of the paper by presenting the key ideas we use to prove our result in Section 6. The complete proof details are contained in the supplementary material.
how interpret our findings, including an in-depth discussion of
2 Preliminaries
In this section we discuss the necessary definitions and preliminaries related to neural network training and the complexity class EIR.
Neural Networks and Training. All neural networks considered in this paper have a very simple architecture, For ease of presentation, we therefore do not define neural networks and their training problem in full generality here. Instead we restrict ourselves to the simple architectures we need.
Definition 1 (Pully Connected Two-Layer Neural Network). A fully connected two-layer neural network N = (SU H UT, E3) is a directed acyclic graph (the architecture) with real-valued edge weights. The vertices, called neurons, are partitioned into the inputs S. the hidden neurons Il and the outputs T. All possible edges from S' to H as well as all possible edges from HI to T are present. Additionally, each hidden neuron has a real-valued bias and an activation function (R + R))
The probably most commonly used activation function [6, 37, 42] is the rectified linear unit (ReLU) defined as ReLU: R + R, x + max(0, z). See Figure for a small fully connected two-layer ReLU neural network.
Given a neural network architecture N as defined above, assume that we fixed an ordering on S and T. Then N realizes a function f(, O) : IR ii + R| where θ denotes the weights and biases that parameterize the function. For x E RISI we define ʃ(- +) inductively: The i-th input neuron forwards the i-th component of to all its outgoing neighbors. Each hidden neuron forms the
2

---

input
output
hidden
Figure 1: A fully connected two-layer neural network as studied in this paper. The symbol inside the hidden neurons expresses the ReLU activation function.
weighted sum over all incoming values, adds its bias, applies the activation function to this sum and forwards it to all outgoing neighbors. An output neuron again forms the weighted sum over all incoming values but does not add a bias and does not apply any activation function. Definition (TRAIN-F2NN). Training a fully connected two-layer neural network the following decision problem, denoted by TRAIN-F2NN:
Input: A 5-tuple (N, D, c),, where
(SUH HU, is the network architecture, ş I + R is an activation function to be used at all neurons in the hidden layer,
is a set n data points of the form (x; E Q x Q!TI.
7 Q2o is the target error, and
|21 x g
R2 a loss function.
Question: Are there weights and biases θ such that E(ED)D (z 0), S 7
The data points D the target error y are part the input, which has finite length (in some chosen encoding). We restrict them to be rational numbers because these are straightforward to encode by noting their numerator and denominator in binary, in contrast to much more complicated encodings required for arbitrary (algebraic) real numbers.
We further require that the loss function is honest, meaning that returns zero if and only if the data is fit exactly. We will see that this is the only requirement on the loss function to prove -lR-hardness of the zero-error case (y= = 0).
Existential Theory of the Reals. The complexity class HR (pronounced as "ER") has gained lot of interest in recent years. It is defined via its canonical complete problem ETR (short for Existential Theory of the Reals) and contains all problems that polynomial-ting many-one reduce to it. In an ETR instance we are given an integer n and sentence of the form
,X,,..., X, E IR
X,),,
where is well-formed and quantifier-fre free formula consisting of polynomial equations and in- equalities in the variables with integer coefficients encoded binary, and the logical connectives (A, V. JJ. The goal is to decide whether this sentence is true. As an example consider the formula pp(, Y) = x y < Y2 > 2X² 1; among (infinitely many) other solutions, (p(0, 0)
evaluates to true, witnessing that this is yes-instance of ETR. It is known that
NP 3I C PSPACE
and it is widely believed that both inclusions are strict. Here the first inclusion follows because a SAT instance can easily be expressed equivalent ETR instance [83]. The second inclusion is highly non-trivial and follows from a result by Canny [17].
Note that the complexity of problems involving real numbers was studied in various contexts. To avoid confusion, let us emphasize that the underlying machine model for 3R (over which sentences need to be decided and where reductions are performed in) is the standard binary word RAM (or equivalently, a Turing machine), just like for P. NP, and PSPACE. It is not the real RAM [33] or the Sein--SubbSmaal model [13].
3

---

3 Results
We are now ready to provide the formal statements of our results. The main result as follows:
Theorem 3.
The problem TRAIN-F2NN 3R-comleete, even if:
There are only two input neurons.
There are only two output neurons.
The number of data points is linear the number of hidden neurons.
The data has only 13 different labels.
The target error "y 0.
The ReLU activation function is used.
Let us note that all of the restrictions in Theorem together describe a special case of the general training problem (Definition 2). Proving that this special case is 3lR-hard also implies 3R-hardness for the general problem, for example with more input/output neurons, more data points, more labels, arbitrary 7 2 and possibly different activation functions.
Apart from settling the precise computational complexity status of the problem to train fully-connected neural networks,
result implies that any approach solve TRAIN-F2NN to global optimality must involve more sophisticated methods than those used for typical NP-copllete problems.
Additionally, our reduction to prove ER-hardness also implies algebraic universality:
Theorem 4. Let a E R be an algebraic number. Then there exists an instance of TRAIN-F2NN, which has solution if the weights and biases @ are restricted Q[ac), but solution when the weights and biases O are restricted to a field E not containing a.
Here, Q[a] is the smallest field extension of Q containing a. This means that for some training instances all global optima require irrational weights even if all data points are integral.
Algebraic universality is known to hold for various AlR-complete problems [4], however this is not an automatism: Algebraic universality cannot occur in problems where the solution space is open, which for example is the case in some problems of recognizing certain intersection graphs [18, 57].
Discussion
In this section, we discuss our results from various perspectives, pointing out strengths and limitations.
Implications ER-Completeness. is widely believed that NP ç 3R. From a theoretical standpoint, proving IR-completeness of an NP-hard problem is therefore a valuable contribution because we are interested in the exact complexity of important algorithmic problems. Although this concerns only the worst case complexity, proving 3R- complleetssssss also hints at the difficulties that need to be overcome when designing algorithms for the considered problem. For example, the continuous solution space of co-copllete problems presents an algorithmic challenge. This is in contrast to problems NP with a discrete or discretizable solution space, which can often be solved well by extremely optimized aff-the-shelf tools like SAT- MIP-solvers. No such general purpose tools are available for 3R-complete problems.
However, let stress that 3R JR-completeness does not rule out hope for good heuristics: The JRR- complete art gallery problem can be solved well practice via custom heuristics, some of these also in combination with integer programming solvers [24]. Under additional assumptions, performance guarantees can be proven [48]. However, these heuristics are specifically tailored towards the art gallery problem. Identifying reasonable assumptions for other 3IR-complet problems in order to obtain good heuristics (possibly even with performance guarantees) is an important open question.
One meta- heea-heu that can often be used to get "good" solutions for 3R- -R-complete problems is gradient descent. Probably the most prominent example in this context is training neural networks, where a bunch of different gradient descent variants powered by backpropagation are nowadays capable of training neural networks containing millions of neurons. general, we do not get any approximation or runtime guarantees when using gradient descent, but under the right additional assumptions proving such guarantees sometimes possible [15]. Gradient descent has also been applied to RR-comllete problems from other areas, for example to graph drawing [5]. Still though,

---

these gradient descent approaches are tailored towards the specific problem at hand. It would be very desirable to have general purpose solvers, similar to SAT- or MIP-solvers for problems in NP.
Relation to Learning Theory. In this paper we purely focus on the computational complexity of empirical risk minimization, that is, minimizing the training error. In the machine learning practice, one usually desires to achieve low generalization error, which means to use the training data to achieve good predictions on unseen test samples.
To formalize the concept of the generalization error, one needs to combine the computational aspect with statistical one. There are various models to do in the literature, the most famous one being probably approximately correct (PAC) learnability [80, 87]. While empirical risk minimization and learnability are two different questions, they are strongly intertwined; see Section 5 for related work in this context. Despite the close connections between empirical risk minimization and learnability, to the best of our knowledge, the -laahrddesss of the former has no direct implications on the complexity of the latter. Still, since empirical risk minimization is the most common learning paradigm in practice, our work is arguably also interesting the context of learning theory.
Required Precision of Computation. An implication of 3R-hardness of TRAIN-F2NN is that for some instances every set of weights and biases exactly fitting the data needs large precision, actually a superpolynomial number of bits to be written down. The algebraic universality of TRAIN- F2NN (Theorem 4) strengthens this by showing that exact solutions require algebraic numbers. This restricts the techniques one could use to obtain optimal weights and biases even further, as it rules out numerical approaches (even using cubitrary-precistie
arithmetic), and shows that symbolic computation is required. In practice, we are often willing to accept small additive errors when computing @)) and therefore also do not require to be of such high precision. In other words, rounding the weights and biases θ to the first "few" digits after the comma may be sufficient. This might allow to place the problem of approximate neural network training NP. Yet, we are not aware of such proof and we consider it an interesting open question to establish this fact thoroughly. Let us note that a similar phenomenon appears with many other -IR-complete problems [33]: While an exact solution æ requires high precision, there is an approximate solution 전 close to that needs only polynomial precision. However, guessing the digits of the solution in binary is in no way a practical algorithm to solve these problems. Moreover, historically, -IR-coopleteness seems to be strong predictor that finding these approximate solutions is difficult in practice [25, 33J. Therefore, we consider coppllelssssssss to be a strong indicator of the theoretical and practical algorithmic difficulties to train neural networks.
Related to this, Bienstock, Muñoz, and Pokutta [9] use the above idea to discretize the weights and biases to show that, in principle, arbitrary neural network architectures can be trained to approximate optimality via linear programs with size linear in the size of the data set, but exponential in the architecture size. While being an important insight, let us emphasize that this does not imply NP-membership of an approximate version of neural network training.
Number of Input Neurons. In practice, neural networks are often trained on high dimensional data, thus having only two input neurons is even more restrictive than the practical setting. Note that we easily obtain hardness for higher input dimensions by simply placing all data points of our reduction into a two-dimensional subspace. The precise complexity of training fully connected two-layer neural networks with only one-dimensional input and multi-dimensional output remains unknown. While this setting does not have practical relevance, we are still curious about this open question from purely mathematical perspective.
Number of Output Neurons. As discussed earlier, if there is only one output neuron instead of two, then the problem known to be contained in NP [6]. Our reduction can easily be extended to the case with more than two output neurons by padding all output vectors with zeros. Thus, the complexity classification is complete with respect to the number of output neurons.
Number of Hidden Neurons. Consider the situation that the number m of hidden neurons is larger than the number n of data points. If there are no two contradicting data points (x1, y1) and (#2, V/) with = 22 but y1 # y2, then we can always fit all the data points exactly [91]. Thus, we need at least a linear number of data points in terms of m to be able to get TRR-comleteeess.. While we already achieve linear number, wonder whether our result could be strengthened further by
5

---

showing cR--ooplettenes with n S (1 + E E)m, for every fixed E. Note that by adding additional data points, the ratio between n and m can be made arbitrarily large. Thus our reduction holds also for all settings in which is (asymptotically) much smaller than
Number of Output Labels. The number of labels, that is, different values for E Q77i in the data set D, used in our reduction is just 13. small set of possible labels shows relevance of our result to practice, where we are often confronted with large number of data points but a much smaller number of labels, for instance, in classification tasks. The set of labels used by us is
{(-2.6), (-1,-1), (-1.0), (0,-1), (0,0), (0.3), (2.2), (3.3), (3,6), (4.4), (6,-2), (6,6), (10.10))
If all labels are contained in a mie-dimeniional affine subspace the problem is in NP, then they can be projected down to one-dimensional labels and the problem can be solved with the algorithm by Arora, Basu, Mianjy and Mukherjee [6]. As any two labels span one-dimensional affine subspace, the problem can only be 3R-hard for at least three different affinely independent output labels.
We think it is not particularly interesting to close the gap between 13 and 3 output labels, but it would be interesting to investigate the complexity of the problem when output labels have more structure. For example, in classification tasks often uses one-hot encodings, where for & classes, a k-dimensional output space is used and all labels have the form (0...., 0, 1, 1,O,,..,,,, 0). this case, at least three output dimensions needed obtain three different labels.
Note that in
Target Error.
For simplicity, we show hardness for the case with target error 7 = 0. However, in difficult to see that we can
practice it is generally not required to fit the data exactly. It is easily modify the value of y by adding inconsistent data points that can only be fit best in exactly one way. The precise choice of these inconsistent data points heavily depends on the loss function. In conclusion, for different values of y, the decision problem does not get easier.
Activation Functions. Let us point out that the ReLU activation function is currently still the most commonly used activation function in practice [6. 37, 42]. Our methods are probably easily adaptable to other piecewise linear activation functions, such as leaky ReLUss Having said that, our methods are not applicable to other types of activation functions, such as Sigmoid, soft ReLU or step functions. We want to point out that TRAIN-F2NI (and even training of arbitrary other architectures) is in NP in case step function is used the activation function [56]. For the Sigmoid and soft ReLU function it is not even clear whether the problem decidable, as trigonometric functions and exponential functions are not computable even the real RAM 70).
Lipschitz Continuity and Regularization. The set of data points created in the proof of The- orem 3 is intuitively very tame. We formalize this by proving that for yes-instances there exists a θ such f(- θ) is Lipschitz continuous for a small Lipschitz constant L (see Remark 23 in the supplementary material for details). This is also related to overfitting and regularization [43], the purpose of the latter being to prefer simpler functions over more complicated ones. Being Lipschitz continuous with small Lipschitz constant essentially means that the function is pretty flat. It is particularly remarkable that we can show hardness even for small Lipschitz constants since Lipschitz continuity has been a crucial assumption in several recent results about training and learning ReLU networks, for example in [9, 20, 38].
Other Architectures. While we consider fully connected two-layer networks as the most important case, we are also interested in hlk--hrddness results for other network architectures. Specifically, fully connected three-layer neural networks and convolutional neural networks are interesting. While is hard to imagine that more complicated architectures are easier to train, formal proof of this intuition would strengthen our result and show that ER- -RR-ooplltteness is a robust phenomenon, in other words independent of choice of specific network type.
5 Further Related Work
Complexity of Training Neural Networks. It is well-known that minimizing the training error of a neural network a computationally hard problem for large variety of activation functions and architectures [80]. For ReLU networks, NP- hardnssssss, parameterized hardness and inapproximability

---

results have been established even for the simplest possible architecture consisting of only a single ReLU neuron [14. 27, 35, 40]. While all these results require non-constant input-dimension. Froese and Hertrich [34] showed that it is also NP-hard to train a two-layer ReLU network with input dimension two and output dimension one. On the positive side, the seminal algorithm by Arora, Basu, Mianjy and Mukherjee [6] solves empirical risk minimization for two-layer ReLU networks and one-dimensional output to global optimality, placing the problem in NP. was later extended to more general class of loss functions by Froese, Hertrich and Niedermeier [35]. The running time is exponential in the number neurons in the hidden layer and in the input dimension, but polynomial in the number of data points if the former two parameters are considered to be a constant. This NP- containmenn of TRAIN-F2NN with one-dimensional output is in sharp contrast to our co-completeness result for two-dimensional outputs.
While minimizing training and generalization errors are different problems, the hardness of the former also imposes challenges on the latter. Strategies to circumvent hardness from the perspective of learning theory include allowing improper learners, restricting the type of weights allowed in a neural network, or imposing assumptions on the underlying distribution. For example, Chen, Klivans and Meka [20] show fixed-parameter tractability of learning a ReLU network under some assumptions including Gaussian data and Lipschitz continuity of the network. We refer to [7, 19, 28, 38, 41, 39] as a non-exhaustive list of other results about leamabiiyyy of ReLU networks in different settings.
Expressivity of ReLU Networks. It is essential for our reduction to understand the classes of functions representable by certain ReLU network architectures. So-called universal approximation theorems state that single hidden layer (with arbitrary width) is already sufficient to approximate every continuous function on a bounded domain with arbitrary precision [22, 52]. However, deeper networks require much fewer neurons to reach the same expressive power, yielding a potential theoretical explanation of the dominance of deep networks in practice [6. 31, 45, 47, 58, 67, 69, 72, 85, 86, 89]. Other related work includes counting and bounding the number of linear regions [46, 64, 65, 68, 69, 79), classifying the set of functions exactly representable by different architectures [6, 26, 44, 49, 50, 51, 66, 92], or analyzing the memorization capacity of ReLU networks [88, 90, 91]. Huchette, Muñoz, Serra, and Tsay [53] provide a survey on the interactions of neural networks and polyhedral geometry, including implications on training, verification, and expressivity.
Existential Theory of the Reals. The complexity class न|R gains its importance by numerous important algorithmic problems that have been shown to be complete for this class in recent years. The name 3R was introduced by Schaefer in [73] who also pointed out that several NP-hardness reductions from the literature actually implied 3l8-hardness. For this reason, several important :IR-completeness results were obtained before the need for a dedicated complexity class became apparent.
Common features of co-cllelleee problems are their continuous solution space and the nonlinear relations between their variables. Important co-colpltssssss results include the realizability of abstract order types [63, 83] and geometric linkages [74], as well as the recognition of geometric segment [57, 60], unit-disk [55, 61]. and ray intersection graphs [18]. More results appeared in the graph drawing community [30, 32, 59, 75], regarding polytopes [29, 71], the study of Nash- equílibria [8, 10, 11, 36, 76], matrix factorization [21, 78, 81, 82], continuous constraint satisfaction problems [62]. In computational geometry, we would like to mention the art gallery problem [2, 84) and covering polygons with convex polygons [1].
Recently, the community started to pay more attention to higher levels of the real polynomial hierarchy, which also capture several interesting algorithmic problems [12, 16, 23, 30, 54, 77].
6 Proof Ideas
To show 3R-hardness, we reduce from classical version of ETR called ETR-INV. An instance of ETR-INV consists of real variables and a conjunction of constraints in these variables, where each constraint is either and addition constraint X + Y Z or an inversion constraint X Y = 1. Given such an instance, we construct a TRAIN-F2NN instance that models the variables and whose training corresponds to satisfying all addition and inversion constraints.
7

---

Variables. A natural candidate for encoding variables are the weights and biases of the neural network. However, those did not prove to be suitable for our purposes. The main problem with using the parameters of the neural network as variables is that the same function can be computed by many neural networks with different combinations of these parameters. We are not aware of an easy way to normalize the parameters.
To circumvent this issue, work with the functions representable by fully connected two-layer neural networks directly. We frequently make use of the geometry of these functions, For now, is only important understand that each hidden ReLU neuron encodes continuous piecewise linear function with exactly two pieces (both of constant gradient). These two pieces are separated by so-called breakline. Now, if we have m middle neurons, their individually encoded functions add up such that the function computed by the whole neural network is continuous piecewise linear function with at most m breaklines. Between these breaklines all pieces of the function have constant gradient.
To keep things simple for now, let us first consider a neural network with only one input and one output neuron. We place a series of data points (I;, Mi) E IR2 as seen in Figure 2. All continuous piecewise linear functions f(-, θ) computed by neural network with only four hidden neurons (i.e., only four breaklines and therefore at most five pieces) that fit these data points exactly must be very similar. fact, they can only differ in one degree of freedom, namely the slope of the piece going through point p. In our construction, this slope represents the value of a variable. The whole set of data points enforcing this configuration is called a variable gadget.
data point
y
Figure 2: The value of f(, θ) is fixed (black part), except for the segment through data point p. The red, orange and blue segments are just three out of uncountably many possibilities. Its slope can be used encode a real-valued variable.
Linear Dependencies. The key insight for encoding constraints between variables is that we can relate the values of several variable gadgets by data point: By placing data point p at location where several variable gadgets overlap, each of the variable gadgets contributes its part towards fitting p. The exact contribution of each variable gadget depends its slope. Consequently, if one variable gadget contributes more, the others have to proportionally contribute less. This enforces linear dependencies between different variable gadgets and can be used to design addition and copy gadgets.
To be able to intersect multiple variable gadgets, we need second input dimension. Each variable gadget as seen Figure is now extended into a stripe IR, with Figure 2 showing only an orthogonal cross section of this stripe. See Figure for two intersecting variable gadgets. Much of the technical difficulties lie the subtleties to enforce the presence of multiple (possibly intersecting) gadgets using finite number of data points.
To construct an addition gadget we need be able to encode linear relations between three variables. In R²2 three lines (or stripes) usually do not intersect in single point. Thus, for addition we have to carefully place them to guarantee such a single intersection point. This might involve creating copies of variable gadget, which is a linear relation between just two variable gadgets.
Inversion Constraint. Within only single output dimension, we are not able to encode nonlinear constraints [6]. We therefore add second output dimension, which implies that the neural network

---

Figure 3: Two variable gadgets (slopes of the blue and red regions encode the values), Point p lies in the intersection of both and can encode linear relationship between them.
represents two functions (' θ) and (² Consequently, we are allowed to use data points with two different output labels, one for each output dimension.
One important observation is that the locations of breaklines of f f(. (fi O), f2(- +))
only depend on the weights and biases in the first layer of the neural network. Thus, every breakline is present in both functions f and f² except if the weight to the corresponding output neuron is zero. This connects the two output dimensions a way that we can encode nonlinear constraints.
We define an inversion gadget (realizing the constraint X Y 1), which also corresponds to stripe in R², For simplicity, we only show a cross section here, see Figure 4. In each output dimension individually, the inversion gadget looks exactly like variable gadget. The inversion gadget therefore be understood as a variable gadget that carries two values.
We prove that by allowing only five breaklines in total, function f can only fit all data points exactly f and f share three of their four breaklines (while both having one "exclusive" breakline each). This enforces nonlinear dependency between the slopes of f and f². By choosing the right parameters, this nonlinear relation models exactly an inversion constraint.
Data points:
both dimensions equal
Dimension
P
Dimension
Figure 4:
Data points y and have different labels the two output dimensions, enforcing that the slopes of the red and the blue pieces are related via nonlinear dependency.
Reduction. Let us illustrate the reduction by giving a simple example. Note that this is not yet the "complete picture", which follows in the supplementary material. We start with the ETR-INV instance that to decide whether the following sentence
,X X2, X3, X4 E IR (X, + X₂ X3) A (X: + X; = AX) X² =) X3
true. This instance has four variables X, X2, X3, X, and four constraints: additions and two inversions. Recall that every gadget corresponds to stripe in the input space IR_ See Figure 5 for the following construction (for better readability the stripes drawn lines).
For each variable we add a variable gadget. We place all of these such that their correspond- ing stripes parallel and do not overlap, see the horizontal lines in Figure 5.
For each addition constraint we introduce three new variable gadgets, one per involved variable. We place these such that they have common intersection point while also intersecting their corresponding variable gadget. In Figure see the two bundles to the left. A data point at the triple intersection enforces the addition constraint, while data points labelled - encode that the values of the two intersecting variable gadgets are equal.
Lastly, we add an inversion gadget for each inversion constraint and place it such that intersects the variable gadgets of the two involved variables. See the two dashed lines in

---

Figure 5. Data points labelled output dimension are equal.
enforce that the values stored in the first (second)
X =1
X1 + X3- =
=0
X1
X2
X3 =0
X4 X3
X1
X2
X3
X4
Figure 5: Overview of the global arrangement of the gadgets.
To see that above reduction correct, assume that the sentence in the ETR-INV instance is indeed true. Then there exists real values for the four variables and these values be used as the slopes of their corresponding variable gadgets. By the correctness of the individual gadgets (which is to be proven in the supplementary material) it follows that each data point is fit exactly.
Conversely, if all data points are fit exactly, then the correctness of the gadgets implies that the slopes of the variable gadgets give solution the ETR-INV instance. Intuitively, this holds because the addition and inversion constraints are encoded exactly by the gadgets of our construction.
Outline of the Supplementary Material. We sketch 3IR-membership of TRAIN-F2NN Ap- pendix A before turning to 3R-harddnes in Appendix B. As Appendix B is by far the longest part of the paper. further broken down into several parts: After short reduction overview, we describe suitable abstractions to make defining and analyzing the gadgets easier. Then we introduce the gadgets formally one by one and in isolation before finally putting everything together. We finish the section by proving correctness of our reduction. Finally, we prove algebraic universality in Appendix C.
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 ScalcOpt-75748) and ForEFront-6155640) Tillmann Miltzow is generously supported by the Netherlands Organisation for Scientific Research (NWO) under project numbers 016. Veni. 192.250 and VI. Vidi..i.11 11.1.213.5500 Simon Weber is supported by the Swiss National Science Foundation under project no. 204320.
References
[1] Mikkel Abrahamsen. Covering Polygons is Even Harder. Nisheeth K. Vishnoi, editor, 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pages 375-386 2022. doi: 10. 1109/F0CS52979. 2021. 00045.
[2] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow. The Art Gallery Problem is IR-complete. Journal of the ACM, 69(1):1-70, 2022. doi :1. 1145/3486220.
[3] Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training Neural Networks is ER- complete. In Mare A. Ranzato. Alina Beygelzimer, Yann Dauphin, Percy S. Liang, and Jennifer W Vaughan, editors, Advances in Neural Information Processing Systems (NeurIPS 2021), volume 34, 2021.
[4] Mikkel Abrahamsen and Tillmann Miltzow. Dynamic Toolbox for ETRINV. arXiv preprint,
2019. arXiv:1912.00 08674.
[5] Reyan Ahmed, Felice De Luca, Sabin Devkota, Stephen Kobourov, and Mingwei Li. Graph Drawing via Gradient Descent, (GD)², . In David Auber and Pavel Valtr, editors, Graph Drawing
10

---

and Network Visualization (GD 2020), volume 12590 of Lecture Notes in Computer Science, pages 3-17. 2020. doi 10. 1007/978--111 1---3-000766------
[6] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding Deep Neural Networks with Rectified Linear Units. International Conference on Learning Repre- sentations (ICLR 2018), 2018.
[7] Ainesh Bakshi, Rajesh Jayaram, and David P. Woodruff. Learning Two Layer Rectified Neural Networks in Polynomial Time. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Shioty- Conference on Learning Theory (COLT 2019), volume 99 of Proceedings of Machine Learning Research, pages 195-268, 2019.
[8] Marie L. T. Berthelsen and Kristoffer A. Hansen. On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. In Dimitris Fotakis and Evangelos Markakis, editors, International Symposium on Algorithmic Game Theory, volume I 1801 of Lecture Notes in Computer Science, pages 153-167, 2019. doi 10070978- 3- 0030-3047-77
[9] Daniel Bienstock, Gonzalo Muñoz, and Sebastian Pokutta. Principled Deep Neural Network Training through Linear Programming. Discrete Optimization, 49, 2023. doi taii:hhtt///cee //doi erg/10. 1016/01///// www.sstt. 2023. 100795.
[10] Vittorio Bilò and Marios Mavronicolas. A Catalog of EXISTS-R-Compler Decision Problems About Nash Equilibria in Multi-Player Games. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Leibniz International Proceedings in Informatics (LIPles), pages 17:1-17:13, 2016. doi 10::00..00 /230//
LIPICs STACS. 2016.. 17.
[11] Vittorio Bild and Marios Mavronicolas.
Sintentiil-R-Compple Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games. In Vollmer Heribert and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:14, 2017. doi: 4230/LIPIcs STACS 2017 .13.
[12] Manon Blanc and Kristoffer A. Hansen. Computational Complexity of Multi-player Evolution- arily Stable Strategies. In Rahul Santhanam and Daniil Musatov, editors, Computer Science- Theory and Applications (CSR 2021), volume 12730 of Lecture Notes in Computer Science, pages 1-17, 2021. doi: 10. 1007 09000/97773-00 3/1///888-0---------1- -00--79416-331
[13] Lenore Blum, Mike Shub. and Steve Smale. On Theory of Computation and Complex- ity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Ma- chines. Bulletin of the American Mathematical Society, 21:1-46, 1989. doi:10.10$0 00273-0979-1989-11 15750-9.
[14] Digvijay Boob, Santanu S. Dey, and Guanghui Lan. Complexity of Training ReLU Neural Network. Discrete Optimization, 44(1), 2022. doi: 10: 1016// disopt. 2020 100620.
[15] Alon Brutzkus and Amir Globerson. Globally Optimal Gradient Descent for ConwNet with Gaussian Inputs. In Diona Precup and Yee W. Tch, editors, Proceedings of the 34th International Conference on Machine Learning (ICML 2017), volume 70 of Proceedings of Machine Learning Research, pages 605-614, 2017.
[16] Peter Bürgisser and Felipe Cucker. Exotic Quantifiers, Complexity Classes, and Complete Problems. Foundations of Computational Mathematics, 9(2): 170, 2009. doi 1007 8 102088007-90006-
[17] John Canny. Some Algebraic and Geometric Computations in PSPACE. In STOC '88: Proceed- ings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 460-467, 1988.
:o1:10. 11 1145/62115 /145//2211.. 02212.62227.
[18) Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber. Intersection Graphs of Rays and Grounded Segments. Journal of Graph Algorithms and Applications, 22(2):273-294, 2018. doi 10. 7155/jgaa.00 00470.
[19] Sitan Chen, Aravind Gollakota, Adam R. Klivans, and Raghu Meka. Hardness of Noise-Free Learning for Two-Hidden Hoo-Hidden-Laeer Neural Networks. arXiv preprint, 2022. arXiv: 2202. 05258.
[20] Sitan Chen, Adam R. Klivans, and Raghu Meka. Learning Deep ReLU Networks Fixed- Parameter Tractable. In Nisheeth K. Vishnoi, editor, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 696-707, 2022, doi 10. 1109 11110//FCS52977 2021.00073
11

---

[21]
Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell. On Restricted Nonnegative Matrix Factorization. In Ioannis Chatzigiannakis, Michael Mitzen- macher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPles), pages 103:1-103:14, 2016. doi: 1...1.44300110 4230/LIPIcs.
ICALP. 2016.
[22] George Cybenko. Approximation by Superpositions of a Sigmoidal Function. Mathematics of Control, Signals and Systems, 2(4):303-314, 1989. doi: : 10. 1007/BFO2551274
[23]
Julian D' D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine. and James Worrel. On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semi- algebraic Sets. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Sym- posium Mathematical Foundations of Computer Science (MFCS 2021), I), volume 202 of Leibniz International Proceedings in Informaties (LIPles), pages 33:1-33:21, 2021. doi:
10. 2.0.4230/110 4230/LIPICs. 2021 33.
[24] Pedro J. de Rezende, Cid C. de Souza, Stephan Friedrichs, Michael Hemmer, Alexander Kröller, and Davi C. Tozoni. Engineering Art Galleries. In Lasse Kliemann and Peter Sanders, editors, Al- gorithm Engineering: Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 379 417. Springer, 1 edition, 2016. doi: 10. 100./000///000000 9- 3-18--3-19----1 494-7997-
[25] Argyrios Deligkas, John Fearleyy Themistoklis Melissourgos, and Paul G. Spirakis. Ap- proximating the Existential Theory of the Reals. Journal of Computer and System Sciences, 125: 105:106-128, 2022. doi : 10. 1016/ jess. 2021 11.002.
[26] Steffen Dereich and Sebastian Kassing. On Minimal Representations of Shallow ReLU Net- works. Neural Networks, 148:121-128 2022. doi: 1016/J neunet. 2ww.et..222.... 01.2.00.10 01.006.
[27] Santanu S. Dey, Guany Wang, and Yao Xie. Approximation Algorithms for Training One- Node ReLU Neural Networks. IEEE Transactions Signal Processing, 68:6696-6706 2020. doi: 10. 1109 2020.3039933
[28] Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R. Klivans, and Mahdi Soltanolkotabi. Approximation Schemes for ReLU Regression. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference Learning Theory (COLT 2020), volume 125 of Proceedings of Machine Learning Research, pages 1452-1485, 2020.
[29] Michael G. Dobbins, Andreas Holmsen, and Tillmann Miltzow. A Universality Theorem for Nested Polytopes. arXiv preprint, 2019. arXiv: 02213.
[30] Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Pawet Rzažewski. Completeness for the Complexity Class AER and Area-Universality. Discrete & Computationnal Geometry, 2022. doi: 10. 1007/8004540022 020-44-22200081--00
[31] Ronen Eldan and Ohad Shamir. The Power of Depth for Feedforward Neural Networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory (COLT 2016), volume 49 of Proceedings of Machine Learning Research, pages 907-940, 2016.
[32] Jeff Erickson. Optimal Curve Straightening is ER-Complete. arXiv preprint, 2019. arXiv: 1908. 09400.
[33] Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow. Smoothing the gap between NP and ER. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1022-1033, 2020. doi: :10. 1ww11119900/// /FCC446000000. 2020. 00099.
[34] Vincent Froese and Christoph Hertrich. Training Neural Networks is NP-Hard in Fixed Dimen- sion. arXiv preprint, 2023. arXiv: 2303. 17045.
[35] Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality. Journal of Artificial Intelligence Research, 74, 2022. doi 10. 1613/jair...../ 1. 13547.
[36] Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. 3R-Completeness for Deci- sion Versions of Multi-Player (Symmetric) Nash Equilibria. ACM Transactions on Economics and Computation, 6(1):1:1-1:23, 2018, doi: 10.
12

---

[37] Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep Sparse Rectifier Neural Networks. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Infelligence and Statistics (AISTATS 201 I), volume 15 of Proceedings of Machine Learning Research, pages 315-323, 2011.
[38] Surbhi Goel, Varun Kanade, Adam R. Klivans, and Justin Thaler. Reliably Learning the ReL.U in Polynomial Time. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory (COLT 2017), volume 65 of Proceedings of Machine Learning Research, pages 1004-1042, 2017.
[39] Surbhi Goel and Adam R. Klivans. Learning Neural Networks with Two Nonlinear Layers in Polynomial Time. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty- Second Conference on Learning Theory (COLT 2019), volume 99 of Proceedings of Machine Learning Research, pages
2019.
[40] Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, and Daniel Reichman. Tight Hardness Results for Training Depth-2 ReLU Networks. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPics), pages 22:1-22:14, 2021. doi:10. 1......3///IIIce.. . 2021 .2.
[41] Surbhi Goel, Adam R. Klivans, and Raghu Meka. Learning One Convolutional Layer with Overlapping Patches. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning (ICML 2018), volume 80 of Proceedings of Machine Learning Research, pages 1783-1791, 2018
[42] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
http://www.deeplee. www.deeeeaaannnnooo..... org.
[43] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J. Cree. Regularisation of neural networks by enforcing Lipschitz continuity. Machine Leurning, 110(2):393-416, 2021. doi:
10. 10.1007/s10994--00 000---020005555 00000005999...
[44] Christian Haase, Christoph Hertrich, and Georg Loho. Lower Bounds on the Depth of Integral
ReLU Neural Networks via Lattice Polytopes. In The Eleventh International Conference on Learning Representations (ICLR 2023), 2023. URL:
2mvALOAWaxY.
[45] Boris Hanin. Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations. Mathematics, 7 7(10):992119,, 2019. doi: 1...3390/mmm/ #3900matth700099..
[46] Boris Hanin and David Rolnick. Complexity of Linear Regions in Deep Networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning (ICML 2019), volume 97 of Proceedings of Machine Learning Research,
pages 260,-260, 2019.
[47] Boris Hanin and Mark Sellke. Approximating Continuous Functions by ReLU Nets of Minimal Width. arXiv preprint, 2018. arXiv: 1710. 11278.
[48] Simon B. Hengeveld and Tillmann Miltzow. A Practical Algorithm with Performance Guar- antees for the Art Gallery Problem. In Kevin Buchin and Éric Colin de Verdière, ed- itors, 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPlcs), pages 44:1-44:16, 2021. doi:10. 4230/LIPICs. SoCG. 2021 44.
[49] Christoph Hertrich, Amitabh Basu, Marco Di Summa, and Martin Skutella. Towards Lower Bounds on the Depth of ReLU Neural Networks. In Marc A. Ranzato, Alina Beygelzimer, Yann Dauphin, Percy Liang, and Jennifer W. Vaughan, editors, Advances in Neural Information Processing Systems (NeurIPS 202/), I), volume 34, 2021.
[50] Christoph Hertrich and Leon Sering. ReLU Neural Networks of Polynomial Size for Exact Max- imum Flow Computation. In The 24th Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), 2023.
[51] Christoph Hertrich and Martin Skutella. Provably good solutions to the knapsack problem via neural networks of bounded size. INFORMS Journal on Computing, 3565) 2023. doi: 10: 1 / ijoc. 2021. 0225.
[52] Kurt Hornik. Approximation Capabilities of Multilayer Feedforward Networks. Neural Net- works, 4(2):251-257, 1991. doi: 10. 1016100936110000 0088 (91) 90009-TT
13

---

[53] Joey Huchette, Gonzalo Muñoz, Tiago Serra, and Calvin Tsay. When Deep Learning Meets Polyhedral Theory: Survey. arXiv preprint, 2023, arXiv:2305. 00241.
[54] Paul Jungeblut, Linda Kleist, and Tillmann Miltzow. The Complexity of the Hausdorff Distance. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry (SoCG 2022), volume 224 of Leibniz International Proceedings in Informatics doi: : 10. 4230/LIPIca SoCG. 2022. 48.
(LJPles), pages 48: 18:1-48:17, 2022.
[55] Ross Kang and Tobias Müller. Sphere and Dot Product Representations of Graphs. Discrete & Computational Geometry, 47(3):548-566 2012. doi: 10. 1070000000044001222-1-100 9394-8..
[56] Sammy Khalife and Amitabh Basu. Neural networks with linear threshold activations: structure and algorithms. In Karen Aardal and Laura Sanità, editors, International Conference on Integer Programming and Combinatorial Optimization (IPCO 2022), volume 13265 of Lecture Notes
in Computer Science, pages 347-360, 2022. doi 10. 1007 00000/997-330 3 031-009000----2
[57] Jan Kratochvil and Jifí Matoušek. Intersection Graphs of Segments. Journal of Combinatorial Theory, Series B, 62(2):289 315, 1994, doi :0. 1006 jetp. 1994. 1071.
[58] Shiyu Liang and Rayadurgam Srikant. Why Deep Neural Networks for Function Approxima- tion? In International Conference on Learning Representations (ICLR 2017), 2017.
[59] Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal. The Complexity of Drawing a Graph in Polygonal Region. Journal of Graph Algorithms and Applications, 26(4))421 446, 2022. doi 10. 7155/ (155// j062. 00602.
[60] JiHí Matoušek. Intersection graphs of segments and ER. arxiv preprint, 2014. arXiv: 1406. 2636.
[61] Colin McDiarmid and Tobias Müller. Integer realizations of disk and segment graphs. Journal of Combinatorial Theory, Series B, 103(1):114-143, 2013. doi: :00 10100.0010../31 jctb. wec.tb.001..... 2012.09. 004.
[62] Tillmann Miltzow and Reinier Schmiermann. On Classifying Continuous Constraint Sat- isfaction Problems. In Nisheeth K. Vishnoi, editor, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 781-791, 2022. doi: 10. 109/FFCS52999. 2021. 2001.00081. 00081.
[63] Nikolai E. Mněv. The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytopes Varieties. In Oleg Y. Viro and Anatoly M Vershik, editors, Topology and Geometry Rohlin Seminar, volume 1346 of Lecture Notes in Mathematics, pages 527-543. Springer, 1988. doi: 10. 1007/BF60082792.
[64] Guido Montúfar, Yue Ren, and Leon Zhang. Sharp Bounds for the Number of Regions of Maxout Networks and Vertices of Minkowski Sums. SIAM Journal on Applied Algebra and Geometry, 6(4):618-649, 2022. :00. 1 /211141699.
[65] Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the Number of Linear Regions of Deep Neural Networks. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil Lawrence, and Weinherger Kilian Q., editors, Proceedings of the 27th International Conference on Neural Information Processing Systems (NeurIPS 2014), volume 2, pages 2924-29333 2014.
[66] Anirbit Mukherjee and Amitabh Basu. Lower bounds over Boolean inputs for deep neural networks with ReLU gates. arXiv preprint, 2017. arXiv: 1711.03073......
[67] Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning (ICML 2018), volume 80 of Proceedings of Machine Learning Research, pages 3740-3749, 2018
[68] Razvan Pascanu, Guido Montúfar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise linear activations. In International Conference on Learning Representations (ICLR 2014), 2014.
[69] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the Expressive Power of Deep Neural Networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning (ICMI. 2017), volume 70 of Proceedings of Machine Learning Research, pages 2847-2854, 2017.
14

---

[70] Daniel Richardson. Some Undecidable Problems Involving Elementary Functions of a Real Variable. The Journal of Symbolic Logic, 33(4):514-52) 520, 1969. doi : 10. 2307/2271358.
[71] Jürgen Richter-Gehve and Günter M. Ziegler. Realization Spaces of 4-Polytopes are Univer- sal. Bulletin of the American Mathematical Sociery, 32(4):403-412, 1995. :o1:10.. 1090/
[72] Itay Safran and Ohad Shamir. Depth-Wides Tradeoffs in Approximating Natural Functions with Neural Networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Leurning (ICML 2017), volume 70 of Proceedings of Machine Learning Research, pages 2979-2987, 2017.
[73] Marcus Schaefer. Complexity of Some Geometric and Topological Problems. In David Eppstein and Emden R. Gansner, editors, GD 2009: Graph Drawing, volume 5849 of Lecture Notes in Computer Science, pages 334-344, 2010. doi: :00:100..0 1007/998--3642222 648-11055---1-------- 0_32.
[74] Marcus Schaefer. Realizability of Graphs and Linkages, pages 461-482. Thirty Essays Geometric Graph Theory. Springer, 2013, doi: 10. 1t11:/9778--411--11111
[75] Marcus Schaefer. Complexity of Geometric k-Planarity for Fixed k. Journal of Graph Algo- rithms and Applications, 25(1):29 41, 2021. doi: 10. 70...15/jaaa.... 00548.
[76] Marcus Schaefer and Daniel Štefankovič. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals. Theory of Computing Systems, 60:172-193, 2017. doi: 10. 1007/
500224-015-9662-0
[77] Marcus Schaefer and Daniel Štefankovič. Beyond the Existential Theory of the Reals. arXiv preprint, 2022. arXiv: 00571.
[78] Marcus Schaefer and Daniel Štefankovič. The Complexity of Tensor Rank. Theory of Computing Systems, 62(5): 161-1174, 2018. doi :0. 00000000022000000000000000000000 -11----0----9------
[79] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and Counting Linear Regions of Deep Neural Networks. In Jennifer Dy and Andreas Krause, editors, Pro- ceedings of the 35th International Conference on Machine Learning (ICML 2018), volume 80 of Proceedings of Machine Learning Research, pages 4558-4566, 2018.
[80] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. doi: : 10. 1017 1011718007711007998800
[81] Yaroslav Shitov. A Universality Theorem for Nonnegative Matrix Factorizations. arXiv preprint, 2016. arXiv: 1606. 09068.
[82] Yaroslav Shitov. The complexity of positive semidefinite matrix factorization. SIAM Journal on Optimization, 27(3): 2017. doi: : 10. 1137/ 0110//61108066....
[83] Peter W. Shor. Stretchability of Pseudolines is NP-Hard. In Peter Gritzmann and Bernd Sturmfels, editors, Applied Geometry And Discrete Mathematics, volume 4 of DIMACS Series Discrete Mathematics and Theoretical Computer Science, pages 531-554, 1991, doi:
10. 1090/ 1090//imaas//////eaaccoccccooost dimacs//d0/// 0004/41.
[84] Jack Stade. Complexity of the Suardryg Art Gallery Problem. arXiv preprint, 2022.
arXiv: 2210. 12817.
[85] Matus Telgarsky. Representation Benefits of Deep Feedforward Networks. arXiv preprint, 2015. arXiv: 08101.
[86] Matus Telgarsky. Benefits of depth in neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Anmual Conference on Learning Theory (COLT 2016), vol- ume 49 of Proceedings of Machine Learning Research, pages 1517-1539, 2016.
[87] Leslie G. Valiant. A Theory of the Learnable. Communications of the ACM, 1984. doi: 10. 1145/19659 1972.
[88] Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the Optimal Memorization Power of ReLU Neural Networks. In International Conference Learning Representations (ICLR 2022), 2022.
[89] Dmitry Yarotsky. Error bounds for approximations with deep ReL.U networks. Neural Networks, 94:103-114, 2017. doi : 10. 1016/j neunet. 2017. 0117.07.0 002..0..
15

---

[90] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small ReLU networks are powerful memorizers: tight analysis of memorization capacity. In Hanna Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Buc, Emily Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems (NeurIPS 2019), volume 32, 2019.
[91] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding Deep Learning (Still) Requires Rethinking Generalization. Communications of the ACM, 64(3):177-115, 2021. doi:10. 1144//444//447
[92] Liwen Zhang. Gregory Naitzat, and Lek-Heng Lim. Tropical Geometry of Deep Neural Networks. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning (ICML 2018), volume 80 of Proceedings of Machine Learning Research, pages 3824-5832, 2018.
16


Reviews:
[{"review_id": "mVZV5XUiHt", "reviewer": "Reviewer_2pEa", "summary": "This paper strengthens a result by Abrahamsen, Kleist and Miltzow [Neurips 21] by showing that empirical minimization problem of two-layer neural network is \\exist R-hard. They further show that arbitrary algebraic number is required as optimal weights even with rational data points. The example include a ReLU neural network with two inputs and two outputs. \n", "questions": "See weakness.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is well-written and the related works have been discussed in great details.\n- The reduction of training two-layer neural network to ETR-INV is novel.\n- The construction of inversion gadget in appendix B.3.4 is quite interesting to learn.", "weaknesses": "- Definition 1 which defines neural networks from a directed acyclic graph seems to be redundant as the paper is devoted to analyze a two-layer fully connected neural networks, whose structure is much simpler.\n- The structure of the paper can be improved. The majority of the papers is to introduce definitions and discussing related works, while the main proof idea only starts at page 7. It would be better if the authors can elaborate on the proof idea. From my perspective, the main theoretical contribution in this paper is the reduction of training two-layer neural network to ETR-INV, while the details how they are achieved are largely left in the appendix. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for carefully reading and assessing our paper and for the valuable feedback.\n\nOur definition of neural networks as directed acyclic graphs is in line with the definition by Abrahamsen, Kleist and Miltzow (NeurIPS 21) whose result we strengthen. While this generality makes sense in their case (their reduction crucially depends on which \"edges\" are present), we agree that the definition in our fully connected setting can be simplified significantly and we plan to do so in the revision.\n\nWe consent that our main contribution is the reduction from ETR-INV to training two-layer neural networks, thereby proving ER-hardness. Regarding the structure of the main body, we plan to enhance the proof ideas section, especially concerning the interplay of the gadgets as well as the equivalence of the training problem and the ETR-INV instance (this was also suggested by other reviewers).\n\nUnfortunately, we see no way to incorporate all details of the reduction into the main body without sacrificing clarity. In our opinion, a thorough review of the related work and a detailed discussion of the strengths and weaknesses should be placed prominently in the paper as they are probably more interesting to a wider audience than the details of the proof."}, {"review_id": "LjnkaT93p1", "reviewer": "Reviewer_QSnu", "summary": "This paper shows that training a neural network with two input neurons and two output neurons is ER complete where ER stands for the existential theory of the reals.", "questions": "What happens to the hardness result if we only consider neural networks with limited precision? Say any weight or bias is represented by at most 10 bits?", "limitations": "I think one of the biggest issues is not addressing the success of gradient-based optimization in the paper. \nThe authors might want to talk more about improper learning which are typically used and make the learning task easier. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A new idea (reduction) to prove hardness result. The paper is generally well written and provides a good cover of the (dense) related work.", "weaknesses": "In the end, the results in the paper point more to the limitation of current computational hardness results than to the limitation of deep learning. The task of finding the exact minimizer and the inability to prove hardness results for the approximate case diminish the relevance of the results to modern ML. Personally, I'm not a fan of ER but I think the reductions could find uses elsewhere. \nThe paper is somewhere between \"accept\" to \"weak accept\" and I'm willing to raise the score if the authors provide convincing responses. \n\nThere are several issues with the writing such as:\n1) Definition 2 is very cumbersome. Consider shortening it as it done in the Blum Rivest paper. \n2) \"However, when using gradient descent\n we usually do not get any guarantees on the quality of the obtained solutions or on the time it takes to\n compute them [30]\". This is misleading as there are many (proven) results about GD finding the global minimum. [30] is one example one GD does not work well, but there are many other results for which it does work well such as \"Globally optimal gradient descent for a convnet with gaussian inputs\".\n3) \"Thus it would be very desirable to use other methods, like SAT- or mixed-integer\nprogramming solvers that are reliable and widely used in practice for many NP-complete problems.\"\nWhat does \"reliably\" mean here? I'm sure that there are bad examples for these heuristics just as there are for GD.\n4) The elephant in the room which the authors largely ignore is the huge success of gradient-based optimization in training neural networks with tens of millions of neurons.\n5) Definition 1 is strange. Consider using the standard matrix notation for neural networks. \n6) There seems to be a redundancy between the average case analysis paragraph and the \"Let us stress\" paragraph.\n7) I would put still more effort in explaining the ideas behind the main reduction and exemplifying it with a small example. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for carefully reading and assessing our paper and for the valuable feedback.\nWe also thank you very much for the detailed list of suggestions to improve the presentation of our paper, which we happily take into account. See below for some detailed responses:\n\n1+5: We agree and plan to simplify the definitions as we do not need the full generality in our fully connected two-layer setting. (This was also suggested by another reviewer.)\n\n2: This is a good point and we will refine our discussion here to also include the positive examples. In fact, it is a very interesting research question how/whether these proven positive examples for GD can be used for other, more geometric ER-complete problems.\n\n3: What we mean by \"reliably\" is that they always terminate with an optimal solution in finite (but sometimes exponential) time. They are not just heuristics, in contrast to GD (in the general case, acknowledging the positive examples mentioned by the reviewer in the previous question). So, for SAT-solving or MIP, there are no \"bad examples\" in terms of solution quality. There are just \"bad examples\" in terms of running time, but for many problems also these examples are rare. We agree that \"reliable\" is not a good term here and will revise this discussion in the final version.\n\n4: You are right that this deserves a more prominent discussion. We plan to extend the discussion in Section 4 (Implications of ER-Completeness) to make this more explicit and to stress that our results are of a purely theoretical nature. As we say, neither does ER-hardness rule out successful heuristics nor does ER-membership directly lead to good off-the-shelf solution strategies. We are still convinced that a thorough understanding of the theoretical worst-case complexity of the training problem is a highly important contribution to the field. After all, a good theoretical understanding of the \"exact training\" case may also inspire future work to better understand \"approximate training\".\n\n6: Good find. We fix this when incorporating your suggestions regarding (4).\n\n7: Enhancing the proof ideas section was suggested by other reviewers as well, especially concerning the interplay of the gadgets and the equivalence of the training problem and the ETR-INV instance.\n\nSome thoughts regarding your question about limited precision:\nThis is a very good question and we discuss it a little bit in Section 4 (\"Required Precision of Computation\"). From a purely theoretical point of view, we suspect that limiting each weight and bias by 10 bits would lead to NP-membership, as these bits could be \"guessed\" by a nondeterministic Turing machine. But we did not investigate this thoroughly and have no formal proof of this claim.\nFrom a less (but still) theoretical perspective, potential membership in NP of the approximate version could spark hope that off-the-shelf tools like SAT- or ILP-solvers would be applicable. A naive approach (and we do not know of anything better) requires one Boolean variable per bit for each weight/bias. This does not seem viable, especially compared to the widely used and successful GD-based approaches.\nTo conclude: This restriction would break our ER-hardness reduction (ER-hardness and high precision often go hand-in-hand) but also not immediately lead to new approaches for training in practice.\n"}, {"review_id": "C5dwk2aEhI", "reviewer": "Reviewer_LVwc", "summary": "The paper proves ER-completeness of training (empirical risk minimization) a fully connected two-layer ReLU network with two inputs and two outputs. The result contributes to the understanding of theoretical complexity of neural network training at an important, fundamental level. The authors also did a good job explaining the intricacies of the achieved type of hardness result with respect to implications and applicability in the broader neural network training context. The true main, and (unavoidably) very technical part of the paper, i.e., the actual proofs, are delegated to a \"supplementary material\" document that is twice as long as the \"main\" paper. \n\n-- update: I have read and acknowledged all other reviews and the authors rebuttals, see discussion. --", "questions": "It seems that, while generally helpful, the proof outline in the \"main\" paper does not quite bring across why the reductions works. It is well-written and enables one to grasp the general concepts (gadgets etc) used for the reduction, but perhaps the authors could add some clarification with respect to the \"crucial\" step, i.e., why their encoding can be shown to answer the ETR instance if and only if the Train-F2NN problem can be fitted with 0 loss?", "limitations": "The authors adequately commented on applicability/meaning of their result and, thus, its inherent limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The result of this paper constitutes and important and fundamental contribution to the understanding of the complexity of training neural networks (to global optimality). Besides the main result itself, the paper's strength lie in its clarity of presentation and the discussion of context, limitations and implications.", "weaknesses": "It appears to have become common practice to submit papers to NeurIPS (and ICML) whose actual, main content is put in a separate \"Supplementary Material\" document whose length far exceeds that of the supposed main paper. Unfortunately, this paper is no exception. I consider this a weakness because this format bears the danger of the formally most important parts of the work not being reviewed thoroughly due to the short review period and high review load of reviewers at these conferences. I cannot exclude myself from this -- I simply did not have the time to rigorously check all the details in the long supplementary document, and therefore cannot give a definitive answer regarding the proofs' correctness beyond \"believing\" everything appears to be in order. In this regard, I cannot help but wonder if a full journal paper would not be the better way to publish results that simply do not fit into the 9-page limit...", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for carefully reading and assessing our paper and for the valuable feedback.\n\nAs other reviewers had similar suggestions, we plan to enhance the proof ideas section, especially concerning the interplay of the gadgets as well as the equivalence of the training problem and the ETR-INV instance.\n\nTo answer your concrete question, in our reduction, the slopes of some linear pieces of the neural network correspond to (real-valued) variable assignments of the ETR-INV instance. The gadgets ensure that all the constraints of the ETR-INV instance are satisfied. Hence, there exists a satisfying assignment for the ETR-INV instance if and only if there exists a piecewise linear function with the correct slopes, which in turn happens if and only if the training problem admits a zero-error solution. This is the concluding step of the reduction.\n\nIn principle, we share your concerns about the publication culture and review process for complicated theoretical results at conferences like NeurIPS. However, these conferences are the venues with the highest visibility in the ML community and therefore submitting and publishing there is the best way to disseminate and advertize important results in a timely manner. From our perspective, this also applies to important theoretical results, even if they require long appendices. Of course, since there is no way of incorporating all the technical details into the main part, we gave our best to provide context and intuitions in the main paper and will, as promised above, improve this further using the constructive feedback from the reviews."}, {"review_id": "5rLj1gUl3g", "reviewer": "Reviewer_64NS", "summary": "The paper investigates the algorithmic complexity of training fully connected ReLU neural networks. It is shown that perfectly fitting two-dimensional data by even a one-hidden layer network with two output neurons is $\\exists\\mathbb{R}$-complete, namely it is as hard as finding the roots of a multivariate polynomial with integer coefficients.\n\nThe paper is well-composed and easy to read, and the findings are interesting even though they are somewhat limited as elaborated in the strengths/weaknesses sections. Overall, my opinion of this paper is positive and I believe it merits acceptance.", "questions": "- Line 84: Why do you assume that $\\gamma$ is rational and not real?\n\n- Line 109: The theorem statement says that the problem is hard \"even\" if certain conditions are met. I find this statement very confusing. It sounds like you can replace \"There are exactly two\" with \"There are only two\" to make it clearer. Similarly, I would change \"The number of hidden neurons is a constant fraction of the number of data points.\" with \"The number of hidden neurons is only a constant fraction of the number of data points.\". Lastly, it seems like the last two items are a necessary condition rather than an \"even\" statement. Specifically, solving for $\\gamma=0$ is at least as hard as approximating to some other $\\gamma>0$, so it doesn't make sense to use state in line 109 that this holds \"even if\". Likewise, the assumption of using a ReLU activation is a necessary condition in the analysis from what I understand so this item also does not belong following an \"even if\" statement. Am I missing something? If so, please clarify the theorem statement.\n\n- Paragraph starting with line 226: It is mentioned that we can add inconsistent data points to modify the value of $\\gamma$. Do you mean that this allows us to show a reduction from the $\\gamma=0$ case to a general $\\gamma>0$ case, and thus the two problems are equivalent? Please clarify.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- Very well-written and easy to follow. It is evident that the authors have put a lot of effort into composing this paper and thoroughly discussing its results, impact and drawbacks.\n\n- The results in this paper are interesting and may suggest that training neural networks is strictly harder (assuming a somewhat acceptable complexity theory hypothesis) than problem in NP. This indicates that certain practices make the worst-case complexity of real-world problems much harder, but the problems are nevertheless solved efficiently. As motivation for future work, it is interesting to study how changing these practices might affect the efficacy in which neural networks are being trained.", "weaknesses": "- The paper studies the problem of perfectly fitting the data, while in practice we are interested in getting the training error to become sufficiently small.\n\n- The paper assumes that the learning problem requires classifying at least 13 classes that are two dimensional and are not linearly dependent. While I agree with the authors' claim that the gap between 3 and 13 classes seems immaterial, I still find the two-dimensional output requirement very limiting. This is due to the fact that we can always re-encode the target classes in a different manner which circumvents $\\exists\\mathbb{R}$-completeness. E.g., we can just encode the classes using the naturals $1,2,\\ldots$. The authors point out that a common practice is to use $k$-dimensional standard unit vectors to encode $k$ different classes which may still imply $\\exists\\mathbb{R}$-completeness, but the study of this is left to future work. To summarize this weakness, the paper cannot currently rule out the possibility that common practices circumvent $\\exists\\mathbb{R}$-completeness entirely.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for carefully reading and assessing our paper and for the valuable feedback.\n\nWe agree that our reduction only works for perfect fitting of the data and two-dimensional outputs, as we also discuss in the paper. While the first property is inherent to the nature of the existential theory of the reals, we would like to comment further on one- vs. multi-dimensional outputs. From our perspective, it is very unusual to encode several classes with one-dimensional naturals $1,2,\\dots$, since this creates an unnatural and unintended artificial ordering on the classes. We are not aware of this being a common practice. In fact, in practice, one does not only want to distinguish finitely many classes, but also obtain probabilities of data points belonging to the different classes. This naturally calls for one output dimension per class and underlines why people tend to use one-hot encodings in practice. Therefore, multiple output dimensions are practically highly relevant, and we show hardness for this case, even though it remains an open question whether the hardness can be achieved with only one-hot encoded labels. \n\nAnswers to the questions:\n1) Requiring $\\gamma$ to be rational is just a technical limitation. As we consider computational complexity in the Turing machine model, a problem instance (including $\\gamma$) must be encoded onto the tape of the machine. For rational numbers this is straight-forward, for other real (algebraic) numbers much more involved encodings are necessary: A complication that we want to avoid in favor of simplicity.\n\n2) Thank you very much for the very good suggestions to improve the wording!\nRegarding the last two items ($\\gamma = 0$ and the ReLU activation function), we see that the wording should also be improved. Let us try to clarify: We intend to express that the general decision problem (where an arbitrary $\\gamma$ and possibly different activation functions on every neuron are specified as part of the input instance) is ER-hard by showing that a special case ($\\gamma = 0$ and ReLU everywhere) is already hard.\nFocusing on the activation function for now, we might also state that the training problem is ER-hard for any class of activation functions that contains ReLU, for example piecewise linear functions. Of course, this does not allow us to easily say something about the hardness of other special cases like some specific piecewise linear function other than ReLU. In the \"Activation Function\" paragraph in Section 4, we discuss for which types of activation functions we expect a similar argument as ours to work.\n\n3) The two cases $\\gamma=0$ and $\\gamma>0$ are not equivalent. Usually, $\\gamma>0$ is the harder case, so showing hardness for $\\gamma=0$ (as we do in this paper) is stronger. There are in fact settings where there is a difference in complexity, e.g., in the case of a single hidden ReLU neuron, the $\\gamma=0$ case is in P [40], but the $\\gamma>0$ case is NP-hard [26, 34, 40] (reference numbering as in our original submission). As we mention in the paper, intuitively, a reduction from the $\\gamma=0$ case to the $\\gamma>0$ case can be achieved by adding inconsistent data points to the instance such that a (a priori known) positive error is unavoidable. To make such a reduction formal, one needs to introduce (mild) additional conditions on the loss function: for example, the loss function needs to satisfy some kind of monotinicity and preserve small encoding sizes in the bit model. Despite being mild and satisfied by most loss functions that are computable on the real RAM, these conditions are somewhat technical, which is why we decided not to go into detail here in the paper."}]

Author rebuttal:

Meta-review: This paper proves ER-hardness results for optimally training two-layer neural network architectures. Although there are some limitations to this type of worst-case analysis of machine learning problems, these limitations are clearly discussed in the paper. More generally, the reviewers generally found this work, including its relation to previous work, to be reasonably well-explained and the technical contribution of this work to be novel. Based on this, I recommend acceptance.
Decision: Accept (poster)