New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
Authors: Cornelius Brand
Robert Ganian
Mathis Rocton
Venue: NeurIPS 2023 poster (2023)
Keywords: neural network training
computational complexity
ReLU networks
Linear networks
TL;DR: We identify novel tractable classes for optimally training neural networks with linear or ReLU activation functions.

Abstract: In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains limited even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, little progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art.

New Complexity-Theoretic Frontiers of Tractability for Neural Network Training
Cornelius Brand
Robert Ganian
Algorithms & Complexity Group
Algorithms & Complexity Group
Vienna University of Technology
Vienna University of Technology
Favoritenstraße 9-1 I, 1040 Vienna, Austria cbrand@ac. tuwien. ac
Favoritenstraße 9-11, 1040 Vienna, Austria rgani an an@gmail. com
Mathis Rocton
Algorithms & Complexity Group Vienna University of Technology
Favoritenstraße 9-11, 1040 Vienna, Austria mrocton@ac. tuwien.e.. ac,at at
Abstract
In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification novel polynomial-ting tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and U-activateed neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of 1, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.
Introduction
Neural networks prominent tool in contemporary machine learning, one which has found ubiquitous appli- cations throughout modern computer science (Goodfellow et al.) 2016). A neural network (cf. Figure [] can be thought of directed acyclic network consisting of sources (typically called impul nodes), and w remaining nodes, which we partition into output neurons (the sinks) and hidden neurons (all other nodes in the network, typ- ically organized into layers).
i
7/1
1/2
1/3
Given the prominence of neural networks, is surprising that-in spite of recent efforts-relatived little is known about complexity-theoe theoretic upper bounds for the funda-
Figure 1: A neural network with two lay- of hidden, ReLU-activated neurons, computing function f R + R
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

mental problem of Neural Network Training (NNT): given a network and a training data set containing m samples, compute weights and biases that best fit the training data - This contrasts recent advances leading to novel algorithmic upper bounds as well as extensive complexity-theoren
landscapes for many other problems arising in machine learning and neural network research, including, e.g.. princi- pal component analysis (Simonov et al., 2019 Dahiya et al. 2021), clustering (Ganian et al. (022). Bayesian network learning (Ordyniak & Szeider, 2013 3) Ganian & Korchemna 2021 Grüttemeier &
Komusiewicz 2022) and matrix completion (Ganian et al. 2018).
Naturally, the complexity of solving NNT to optimality strongly depends on the activation function used in the network as well as on what kind of restrictions are placed on the structure of the network, but-as as we will frontiers of polynomial-time tractability. The Rectified Linear Unit (ReLU) activation function is a natural first choice to consider for a complexity-theoe -theoretty investigation; over the past years, it has become the most popular and widely studied activation function used in neural networks (Gao et al. 2020). Goel, Klivans, Manurangsi and Reichman (202T) recently established that the Neural Network Training problem with ReLU activation functions (RELU-NNT) is NP-hard, even when restricted to networks with no hidden neurons, meaning that RELU-NNT is computationally intractable when no further restrictions are placed on the network. In fact, an even more recent reduction shows that RELU-NNT is also complete for the complexity class ER when restricted to complete networks (Bertschinger et al., 2022) with precisely two input nodes and two output neurons, as opposed to networks with arbitrary structure. Moreover, the problem was shown to be hard for the complexity class W[1] (Froese et al.) 2022) when parameterized by n and also intractable for instances of fixed dimension Froese & Hertrich (2023).
even in the best studied and simplest cases we lack an understanding of the
While these results seem discouraging at first, an immediate question that arises is whether we can at least efficiently train "small" networks? In particular, what is the complexity of RELU-NNT (as well as other variants of NNT) when restricted to networks where n, w, or both are (fixed but arbitrary) constants? Here we find a stark contrast between the extensive body of research on the complexity of other natural meta-problems and how little is known for (RELU-)NNT. Indeed, while recent reductions immediately rule out polynomial-tin time tractability for networks with constant (Abrahamsen et al. 2021; Froese et al.] 2022) or constant (Bertschinger et al. 2022), the complexity of RELU-NNI -NLU-NNTiN in the base case where both n and w are bounded by a constant (i.c., when training constant-size networks) is prominent open question in the field. The best partial answer we had so far for this high-profile question lies in the seminal work of Arora, Basu, Mianjy and Mukherjee (2018) (see also the follow-up work of Boob, Dey and Lan (2022), who developed polynomial-tine algorithm that can solve RELU-NNT for constant-size networks with a single layer of hidden neurons and one output neuron.
Naturally, the study of NNT is also relevant for other popular activation functions such as the Sigmoid or fanh-hooevert these seem even less amenable to contemporary algorithmic techniques than ReLUs, On the other hand, there exists a class of fundamental activation functions for which the training problem turns out to be casier than for ReLUs: linear functions. Linear-activatee networks have been considered in numerous settings as well as theoretical examples (Abrahamsen et al. 2021 Cowley & Pillow 2020 Panigrahi et al. (020) and can in many ways be viewed as the "baseline" choice for considering the complexity of neural network training. Indeed, unlike for RELU-NNT, it not difficult to show that LIN-NNT (i.e., NNT with linear activation functions) polynomial-time tractable for any network of bounded (i.e., constant) size, but is known to be RR-complete for general networks (Abrahamsen et al. 2021) (see also Section B). However, the complexity of LIN-NNT for general networks with bounded w wii.e. with constantly many hidden and output neurons-remenn open.
Contributions. While several papers have recently provided lower bounds for NNT (Abrahamsen cct al. 202T Froese et al., [2022] Bertschinger et al.) (0022), much less progress has been made towards pushing the frontiers of tractability of the problem. In this paper, we remedy this by providing new algorithmic upper bounds that supersede the previous state of the art for RELU-NNT and LIN-NNT.
Formal definitions are provided in the Preliminaries.
*Consider, e.g.. Lenstra's 's celebrated theorem for solving Integer Linear Programs with constantly many variables (Lenstra & Jr. 1983) and the multitude of improvements of that initial result (Kannan 1987 Frank & Tardos 1987 Ganian & Ordyniak 2019 Brand et al. (021]). or Schaefer's famous dichotomy theorem for Boolean CSPs (Schaefer 1978) and its more recent generalization to Sounded-domale CSPs (Bulatov] 2017).

---

As our first major contribution, we establish the polynomial -ime tractability of RELU-NNT for all constant-size networks satisfying the property that all hidden neurons have out-degree at most 1. We remark that while this condition is trivially satisfied by every neural network that can be handled by the aforementioned algorithms (Arora et al., 2018 Boob et al., 2022), our result may also be applied to much more general networks and in particular can support more than one output neuron and multiple hidden layers. The algorithm underlying our result can also deal with networks combining ReLU and linear activation functions. Moreover, its running time matches the recent algorithmic lower bound of Froese et al. (2022) for single-neuron architectures, meaning that is essentially optimal in that setting.
One remarkable consequence of our exact algorithm for RELU-NNT is that allows us to formulate a procedure which can effectively deal with every constant-size network architecture (even those not satisfying the restriction on the out-degree of hidden neurons). particular, we show that every constant-size Rel.U-activate
network architecture can be transformed into a new network architecture which (1) at least as expressive as the original architecture, and (2) can be trained in polynomial time. Crucially, the depth of the new architecture remains the same and its size depends solely on the size of the original architecture.
Next, we turn to the simpler setting of training neural networks with linear activation functions, i.e. LIN-NNT. Recall that here, we are dealing with networks containing a bounded number of hidden/output neurons, but potentially large number of input nodes. Once we depart from the case of architectures with complete connections between consecutive layers (which can be solved by a direct application of linear regression), training neural networks to optimality on a given data set is known to be hopelessly hard (Abrahamsen et al. 202T) unless the admissible architectures/data are restricted to highly specialized scenarios, such as those with single output neuron (see Section 3 As our second contribution, we identify a general data throughput condition that allows us to circumvent the aforementioned intractability and guarantee the polynomial-time tractability of LIN-NNT. In particular, we say that a network admits an untangling a subset of its nodes can partitioned into connected blocks one for each output and input node-such that:
la. each input node is the sole source of an input-block: lb. each output node the sole sink of an output-block; and 2. the adjacencies between blocks reflects reachability between inputs and outputs.
Intuitively, an untangling can be seen as a backbone in a network where each block either aggregates information from a source into sink. While it may not be obvious from the definition at first glance, not only do single-output (as well as single-input) neural networks admit a trivial untangling, but so do many other network architectures one may consider. To exploit our notion of untanglings, we obtain an algorithm that solves LIN-NNT in polynomial time whenever the network comes with an untangling. We combine this result with a procedure that computes an untangling (or determines that none exists) in linear time on all architectures with a constant number of hidden neurons, and provide a different linear-time procedure find untanglings on architectures of constant treewidth (Robertson & Seymour
1983 Bodlaender 2016).
2
Preliminaries
Graphs. We assume basic knowledge of graph terminology (Diestel 2012). The graphs considered in this paper are assumed to be directed, that is, graph is pair G = (V, F)), where V is set of vertices and E' a set of directed edges. For vertex v. the vertices u such that there is an edge (u, v) in É are called the in-neighbors of v; correspondingly, the set of in-neighbors is the in-neighborhood of v. The notions of of out-neighbors and out-neighborhood are defined symmetrically. The in-degree and out-degree of a vertex is the size of its in- and nighhoogbboroood, respectively. For vertex subset X C V. we denote by G[X] the graph induced on X.
Neural Networks. The protagonists of this article are neural networks, which are acyclic graphs endowed with additional information. In particular, the architecture of a neural network N is a directed acyclic graph = (V, E) where the nodes are called neurons. We refer to nodes with no incoming edges as input nodes, while those with no outgoing edges are called output neurons. All other nodes are called hidden neurons. We refer to edges as deep when they are not incident to an input node. Typically, one assumes that the hidden neurons partitioned into layers defined by their
3

---

shortest distance to an input node, where hidden neuron in layer i only has in-neighbors in layer i and out-neighbors in layer 1.
In addition to its neural structure, /V defined by assigning a bias by E lR for each non-input neuron and a weight de R for each edge e. Furthermore, we fix an activation function a RR - R for the entire neural network. To formally map the data dimensions onto the input and output nodes in an architecture, we will assume that these nodes come with an implicit predetermined ordering.
A neural network defined as above computes a function fx : IK + R", where n is the number of input nodes, and d the number of output neurons of N.. To define fx. say for each neuron e that it computes a function f. R" + R, which is inductively defined as follows: The function computed at the i-th input node is the coordinate projection I,₃ R - R, (I1..... ..) + 2,. For non-ing non-input neuron, let U1, , U2 be the in-neighborhood of v, again in some arbitrary, but fixed order, and let a, be the vector of weights (d..e))=1,.... in the same order. Furthermore, let y. (y1, (y1,--.. Vt be the values of the functions computed at the neuron ni, respectively- that is, Y = So. (T1, Fn). Then, v computes (aa Ye + b.). The function computed by the neural network N itself then given by (for (Z1,..., In). [o (Z1, In)), where 01...., Od are the output neurons of.
Clearly, the function computed by A depends, among other things, on the employed activation function. Here we will consider two specific and well-studied choices for a, namely ReLU and linear activations. It is well known that, without loss of generality, these can be assumed to be ozz)) (i.e.. the identity) for linear activations and (z)) = max max x} for ReLU activations (Goodfellow et al. 2016). We will also employ the notation x + max (0, 2)
Training Neural Networks. The task of training a neural network is to, given an architecture and activation, compute a set of weights as well as biases, such that the function computed by the resulting neural network approximates in the best possible manner a given set of training data, that is, a given set of samples (xr, y) where x and y are vectors of the appropriate dimension for the network architecture.
More formally, the input to the o-NNT problem is an architecture G EV) and data points D S R" x Rd, where is the number of imput and d the number of output neurons of the architecture. For every setting a of all edge weights as well as b of all biases, this fully determines a neural network No., that in turn computes a function Sa,b [Na..- The task is then to output a weight a. for every edge e in G as well as a bias b, for every neuron such that the function computed by the resulting neural network Na.b minimizes, among all such choices of and b, the &2- fz-loss function La(a, =(( ((=)))))
lly" fa,((*") (12, where || ||2 is the standard Euclidean norm.
Note that the problem formalization in particular entails that we do not regard the type of activation function as part of the input, whereas the network architecture is part of the input by default. This either matches or generalizes previous formalizations of the problem (Arora et al. 2018 Abrahamsen al. 202T Goel et al., 202T Froese et al., 2022 Bertschinger et al. 2022). We will denote the problems of training neural networks for linear and ReLU activations as LIN-NNT and RELU-NNT, respectively, and the analogous problem where the network contains both linear and ReLU activation functions as MIXED-NNT. Furthermore, while the definition of o-NNT implies that solution is one which minimizes the Ez-loss function, we will also sometimes call these "optimal solutions" " for emphasis. Last but not least, throughout the article assume that [D] > since the case where |D] < 1 is trivial.
3 Synopsis of Known Results
Neural network training is a vast area of research that has received an immense amount of attention both the theoretical as well as the empirical side. In order put results into context, we survey the complexity-theorete understanding of linear and ReL.U neural network training.
Linear Activation. the simplest case of LIN-NNT where we assume the size of the whole architecture to be upper-bounded by a constant, it is known that the problem can be expressed as constant-size system of polynomial inequalities which can be solved in polynomial time, e.g., via the seminal work of Tarski (1951).

---

On the other hand, LIN-NNT is known to be intractable even if the number of output neurons is upper-bounded by a fixed constant; in fact, the problem was shown to be ER-hard even when the number of output neurons is fixed to 3 (Abrahamsen et al. (021).
One intermediate case between the general and fixed-size fixed-dimension networks is when the network architecture is unrestricted in size but has a special structure, namely, where all edges between layers of nodes exist. In this case, LIN-NNT can be solved in polynomial time by direct application of multidimensional linear regression (Velu & Reinsel 2013).
The preceding discussion leaves open variety of possible directions, such the complexity of training networks that are not necessarily fully connected. but constrained to have two or even single output neuron. On the other hand, one may ask what happens if we consider only the number of hidden neurons to be bounded by a constant, without restricting the number of input nodes and output neurons. Our results deal with intermediate case that captures, among other things, the easy case of single-output networks, as well as some more general networks with a constant number of hidden neurons, In particular, we will formulate a technical condition-whether or not the architecture can be untangled-thal will allow us to train such networks with linear activations in polynomial time.
Rectified Linear Activation. Recent results from computational complexity theory provide strong lower bounds on the inherent difficulty of the problem of neural network training with ReLU activation functions, already highly restrictive architectures. Indeed Goel et al. (2021) and independently Dey et al. (2020) have proven that, under standard complexity assumptions, even training a single ReLU-activated neuron with n input nodes cannot be accomplished in time polynomial in n and the size of the training set D; see also the related lower bounds of BBertschinger et al. (2022).
A seminal algorithmic result is that of Arora et al. (2018) for training shallow networks consisting of one layer of hidden ReLU neurons and a single output neuron equipped with a linear activation function. Their algorithm runs in time [D] (w-n), where D is the training set, n the number of input nodes and w the number of other nodes in the architecture. [Boob et al. (2022) showed that the same approach can be used to handle cases where the output neuron is equipped with a ReLU activation function as well. Froese et al. (2022) have shown that this running time dependency on in the exponent of D is asymptotically optimal even for single hidden neuron, ruling out algorithms running time, e.g., 2" ()(")) for this basic case.
is major open problem to extend the techniques of Arora et al. (2018) to general deep networks- in particular, the complexity of RELU-NNT when restricted to networks whose size is upper-bounded by an arbitrary but fixed constant is wide open. Our work shows that it is nevertheless possible to identify much more general set of architectures than those covered by the aforementioned results Arora et al. 2018 Boob et al. 2022) for which RELU-NNT is polynomial-time solvable.
4 Training ReLU Networks
In this section, we establish our tractability results for ReLU-activvted neural network training when each hidden neuron has out-degree at most 1, As our first step, we prove that in such instances the weights in the hidden layers can be discretized to only two values.
Lemma 1. For any ReLU network N and for any hidden neuron u with precisely one out-neighbor w, there is ReLU network N with the same architecture such that fN JN- and a' E (-1,1) 1). Moreover, the only parameters in which N and N* differ are the weights of the edges incident to u and the bias of
Proof Sketch. Let (wz)s be the (non-empty) family of predecessors of u, and its only successor. To obtain N we construct new set of weights and biases at u, where sgn(x) is the sign function:
Vi, a = awya (Qwol
b = by |
a sgn(aww) if = 0)
All other weights in * remain the same as in N. To complete the proof, it suffices to show that JN = fN- holds by using the fact that the ReLU function commutes with multiplication with non-negative factors.
D
5

---

By iteratively applying Lemmal] [ we obtain:
Lemma 2. Let N be a ReLU struciure such that every hidden neuron has out-degree 1. Then there exists an optimal solution RELU-NNT such that all deep edges have weights in {1,-11,
Lemma] 2 will later allow us to reduce our search space for RELU-NNT by only needing to consider two options for the weights of each deep edge. We note that Maass (197) employed a related idea.
Partitioning by Hyperplanes. The other key argument used to reduce the search space further concerns the way ReLU neurons partition the training set into a "dead area" (i.e., the elements where the linear unit is rectified) and an "active area" (where the unit behaves as a linear function). More precisely, given a data set D and a ReLU-activated neuron u, we say that u partitions D into an active area D I.. which contains all data points for which fu outputs value greater than zero, and dead area D D D us which contains all data points for which fu outputs zero.
As base case, let us consider a neuron u in the first hidden layer of a neural network and let a be the vector of weights for the edges from the input nodes to u, where non-edge would be represented as a weight of O. As a trivial upper bound, there are in general at most 2 ways u can partition D into an active and dead area, which provides a trivial upper bound for an algorithm enumerating all such partitions. However, we have that fu (D;) = (a? Dj + by)+ J for each data point D) E D and moreover a?! x + b, defines hyperplane in an n--iiennsoona space. This allows us to obtain an algorithm with a better running time bound for enumerating the partitions of the point set that is inspired by a result of Megiido (1988).
Lemma 3. Let D C R be a finite set of points. Then, the set of partitions 11 ((A,B) AUB D and A, B are separated by hyperplane] can be enumerated in time (()))
Remark. A similar result was claimed and used by Arora et al. 2018 Page 14) in their algorithm for dealing with CELU-NNT restricted to a special case of the setting treated in this section. However, the argument presented there seems to be incomplete. In particular, it makes the claim that "the total
number of possible hyperplane partitions of set of size D in IR is at most ((2)), which is imprecise (consider, c.g., D = r2). Moreover, the book listed as reference for bounding the total number of possible hyperplane partitions does not provide an algorithm for enumerating these efficiently, and enumeration is required for both our result and the result claimed in Arora et al. (2018). A bound on the number of such partitions can be attributed to Harding (967). but that does not yield efficient enumeration either. If the points are known to lie in general position, efficient enumeration could be carried out via translation to hyperplane arrangements followed by an application of the results of Edelsbrunner et al. (1986); however, in our setting we cannot guarantee that these lie in general position, necessitating our stand-alone proof of Lemma 3 above (which we believe to be also of general interest).
The considerations preceding Lemma not immediately translate to neurons that are deeper than in the first layer, since the inputs to these activation functions are obtained by non-linear transformations of D. Nevertheless, we prove that it is also possible to derive an upper bound for neurons beyond the first hidden layer if we are provided information about the partitions of neurons in previous layers.
Lemma 4, Let D be a set of data points, u. be a ReLU newron, F be the set of all neurons on paths from input nodes to u, and x [F). Given for each E F, we can upper-bound the number of distinct active areas Dlv, C D over all networks consistent with the given selection of (D), / F} by (n-22),, and it is possible to enumerate a superset of these in time (n)22)
We now show how solve RELU-NNT in polynomial time for each fixed value of n and w:
Theorem 5. There is an algorithm that, given an instance (G, D) of RELU-NNT such that every hidden neuron of the structure has out-degree exactly 1, and the data points are encoded using I. bits overall, computes the global optimal solution in time D) ((n-w-2"), poly(T.)
Proof Sketch. The algorithm begins by exhaustively branching to determine the weight of each deep edge, which requires us to consider at most 2n options view of Lemma? 2 Once the weights of the deep edges are fixed, we branch to determine how each hidden and output neuron partitions the training set. For this to work, we need to process layers consecutively- we only branch on the possible partitions for one neuron after we have chosen the partitions for all of its hidden in ne-neighbors.

---

For each such neuron, we enumerate all feasible partitions of D using Lemma and branch over the possibilities. For a given partition, we create a set of inequalities that are satisfied only if each element of D indeed is affected by u according to the partition. Once partition has been chosen for all neurons, the function computed by the resulting neural network N for each neuron is fixed save for the weights of edges adjacent to input nodes, and the biases. We will optimize over all these free variables by constructing an instance of the QUADRATIC OPTIMIZATION problem, whereas we optimize (a b) subject to the set of constraints obtained when partitioning the neurons. The obtained instances of QUADRATIC OPTIMIZATION can be solved in time polynomial in the number of variables and constraints, well the bitlengths of the datapoints, e.g., by using the ellipsoid method Pang 1983 Kozlov et al. 1979).
Note that the proof of Theorem 5 can be directly extended to also include architectures where some of the hidden or output neurons use a linear activation function instead of ReLU.. Indeed, we need not guess partition for the neuron and hence not construct constraint in the quadratic program, and furthermore we may treat a linear neuron the same way as an activated ReLU in the following layer. This yields the following theorem, which generalizes the tractability results of both Arora et al. (2018) and Boob et al. (2022).
Corollary 6. There is an algorithm that, given an instance (G, D) of MIXED-NNT such that every hidden neuron of the structure has out-degree 1, and the data points are encoded using L bits overall, computes the global optimal solution in time ID ((n-w-2)) pollyL).
5 Blowing Up a Neural Network
The tractability results of Arora et al. (0188) on constant-width shallow ReL.Unetwookss raise the natural question of whether it is possible to (efficiently) perform depth reduction on deeper networks, so to reduce given (deep) instance for RELU-NNT to a tractable (e.g., shallow) special case. It is widely conjectured that this is not possible in general without sacrificing some quality of the solution (see, e.g., Hertrich (2022). Conjecture 1. and Haase et al. (2023); Hertrich al. (202T)) Among others, it is widely believed that there are functions that are efficiently computable by depth-3 but not by depth-2 a-ativvvee neural networks (Eldan & Shamir 2016). and similar results were also shown for deeper networks (Cohen et al., 2016: [Tllgrsky| 2016))
While these results essentially rule out performing depth reduction without a negative impact on the accuracy, our tractability results in Section 4 allow us to approach the question from a different angle. In partieular, show that it is possible to transform an arbitrary constant-size Rel.U-activated deep neural network architecture into one of the same depth which is (1) at least as powerful as the original architecture, (2) guaranteed admit polynomial-tin training, and (3) upper-bounded in size by a function of the size of the original architecture
To explain the construction, we start again with the base case of a single neuron. More precisely, let be a single ReLU-activated (hidden) neuron with n inputs and d outputs, and say the weights on the input edges are d1..... azz the weights the output edges are a' .i...., d'z.- and the bias at the hidden neuron is b. Now consider a new network with a single layer of ReLU-neurons which consists of d Rel.U-activated neurons v1,...,, Va, where every v, is connected to all inputs with the same weights a1.-..,, Gn as before. Furthermore, each v; has a single output edge with weight df. We call this network the blow-up of N. Let first establish that this blow-up has the desired property:
Lemma 7. Let N be neural network with single RelU--cctivteed hidden neuron before, and let N' be its blow-up. Let fN. IR" + gd be the functions computed by N and N', respectively. Then, fN fNr holds.
This procedure can be generalized to blow up an arbitrary ReLU-activated neural network, regardless of the number of its layers.
With a slight abuse of notation, we will also refer to the blow-up of a given network architecture G (that is. one without weights and biases) as the architecture of the blow-up of an arbitrary neural network with architecture G, and the process for obtaining the blow-up an architecture is the very
'e remark that such a transformation can be trivially provided for linearly- activated network architectures. since -IN-NNTi is polynomial-ting solvable on complete networks. We also explicitly note that changing the architecture is not always desirable or even possible.
7

---

same as for weighted network (ignoring any weights). We now turn to establishing the properties of blow-ups with respect to RELU-NNT.
Proposition 8. Let G be an arbitrary architecture and let G' be its blow-up. Furthermore, let LD and D be the loss functions associated with G and G', respectively. Then, for any weights o, on G and the minimizer a", bb of T.D on G', we have D bb)) S L.((a,
The size of the blow-up of a network with a constant number of hidden neurons behaves as follows. Proposition 9. Let be neural network with E layers of À 2 2 hidden neurons each, and o output neurons. Then the blow-up of N has at most b S o- X x hidden neurons, and at most X neurons its first hidden layer. If X 1, we have b S o.
Recalling Theorem 5 from Section we now directly obtain:
Theorem 10. There is an algorithm that
takes as inpul instance (G, D) of RELU-NNT where G has depth e, n input nodes, output neurons and at most À hidden neurons per layer,
computes the blow-up G' of G and optimal solution to RELU-NNT (G', D), and
runs in time (1)"(1))2") where (e x
Observe that the running time in Theorem 10 polynomial for every architecture of constant size and essentially tight with respect the lower bound of Froese et al. 2022) for architectures with single hidden neuron. In combination with Proposition 8 this implies a polynomial-tne -imm algorithm which transforms arbitrary constant-size architecture into new one which has already been solved to optimality, with no sacrifice in either accuracy or depth.
We remark that the procedure described in this section can be seen as a rough analogue improper learning learning theory in that involves change of the hypothesis class. In particular, while prove that our blow-up procedure does not increase the training error, it might increase the generalization error of empirical risk minimization in learning settings. We also point out that a similar procedure was described in earlier work of Maass, albeit in it was applied in different context Maass (197)).
Training Linear Networks
Untanglings of Linear Networks. As discussed in Section 3 the complexity of LIN-NNT is open when restricted to architectures with arbitrarily many input nodes while considering the number of other nodes in the network be fixed by constant, and very few classes of architectures are known to admit polynomial-time training for linear activations. Here, we identify a general substructure of the architecture which, when present, guarantees the polynomial-time solvability of LIN-NNT.
Specifically, an untangling of an architecture G= (V, E) with input nodes T $1,..,, and output nodes 2/, .... My is a partitioning II (B, Ci,,, Di.... D3) such that:
Each G CC], < i < a contains z; as its only source;
Each G D2). 1 < j < 3 contains yy as its only sink; and
For each x; and yy. if yj is reachable from 2; G, there exist s C2 and f E D, such that E.
As the first result in this section, we will show that if one is given network architecture along with an untangling, it is possible solve LIN-NNT in polynomial time. Towards this, we observe that since all transformations in such networks are affine, is possible to assume without loss of generality that non-zero biases are only present on output neurons. Indeed, one can slide the biases along the edges in the network towards the output neurons, and if we multiply them by the weights of edges met along the way, the computed function does change. As an example, given edge with weight a from a neuron associated with bias by o 0 to neuron associated with bias b,, we can alter the biases by setting by == and bj b1 + a1 b2 since a1 (x + b2) + b1 01 x + (b1 ai b2). Applying this iteratively along all the edges of a network yields:
Observation 11. For each neural network Na. with linear activation functioion,unccionns, there exists a neural network Na, such that b' is non-zero only on the output neurons and fN.., fN.,s'"
Observation allows to proceed towards establishing the claimed tractability result.

---

Theorem 12. LIN-NNT can be solved in time poly(ID) + [V]) if an untangling of the architecture G = (V,E) is provided as part of the input.
Computing Untanglings. Given Theorem 12 the natural next question concerns the complexity of actually computing an untangling in a neural network. The aim of this section is to provide a comprehensive answer to that question. As first result, we prove that deciding whether given architecture has an untangling is, in general, intractable.
Theorem 13. Deciding whether a given architecture G has an untangling is NP-hard.
Sketch. We provide a polynomial reduction from the NP-hard DOMINATING SET 3- PARTITIONING problem (Heggernes & Telle 1998): Given an undirected graph H (V, E), decide whether its vertex set can be partitioned as V A1 U Ag U A3 such that A1, and A3 are all dominating sets of H. Here, dominuting set of a graph is subset X of its vertices such that every vertex v is either in itself, or adjacent to some w E X; we say that such w dominates v.
Let H = (V, E)) be an undirected graph. We first describe how to transform H into an architecture G such that G has an untangling if and only if H can be partitioned into three dominating sets. G is constructed as a threc-layered architecture, that is, with vertex set L1 U L2 U L3. where L1 = {d1, d2, da}. L2 V. and L3 consists of [V| + disjoint copies of V, that is, La = 11 Additionally, G has all possible edges from L1 to L2, and v E Lg has an edge towards (1) E Lg in G if and only if u = v or e was adjacent to u in H. To complete the proof, it suffices to establish that every untangling in G' implies partitioning of H into three dominating sets, and vice-versa that every such partitioning of H guarantees that there is an untangling in G.
U.Ev(u())
While negative, the intractability of computing an untangling in a general architecture is far from unexpected. For our next result, we take aim at the restriction of LIN-NNT where the architectures have an arbitrary but fixed bound on the number of hidden neurons- a case which is notable not only due to the fact that the target architectures will typically be much smaller than the training set, but also because its complexity remains open (cf. Section (3). We show that under this restriction, the problem of determining whether the architecture has untangling is solvable in linear time.
Theorem 14. There is algorithm which either computes an untangling in a given architecture G = (V,E) with k hidden neurons in time (R()). [V), or correctly determines that none exists.
Proof Sketch. Let W C V be the set of hidden neurons in G. We begin by exhaustively branching over all of the at most ((O()) partitionings of W into sets II' (B, "O,,C,,..C, Di...., D's) (for all choices of a and 3, both of which are trivially upper-bounded by k)). For each such choice of IT', the algorithm then proceeds by determining whether it can be extended to an untangling of G' by adding an input node to each C% S i a, an output neuron to each D', 1 S. j S 3, and keeping all remaining input nodes and output neurons as singletons in the untangling. in way which satisfies the reachability constraint of an untangling. To this end, we will employ a further set of exhaustive branching rules which will iteratively assign singleton output neurons and input nodes to the sets in II'. Intuitively, whenever we identify that an input node is missing a connection to an output node (due to at least one of these not being assigned to part in II'), we exhaustively branch over all ways one of these two neurons can be assigned to part in II'.
As our final result, in the next Theorem 15 we show that is also possible to compute untanglings in linear time even on architectures with many hidden neurons, provided that such architectures are "well-structured" in a theerrtcccctccc sense. In particular, we show that this holds for architectures which are tree-like in the sense of having bounded treewidth: highly established structural graph parameter which measures how tree-like graph is (Robertson & Scymour 1983). Specifically, here we consider the treewidth of the underlying undirected graph, i.e., the simple graph obtained by replacing each directed edge in the architecture by an undirected one.
To put Theorem 15 into context, we remark that the proof is based on application of Courcelle's s well-known Theorem (Courcelle, 1990) and hence a definition of treewidth will not be required for an exhibition of the result or its proof: instead, we refer to the multitude of existing surveys and materials on the topic (Courcelle & Engelfriee| 2012)] Bodlaender] 2016). We remark that the result is incomparable to Theorem [4] while it can easily be shown that every architecture with k hidden

---

neurons also has treewidth at most k and hence Theorem 15 can be applied to strict superclass of architectures, the running time guaranteed here has a nonelementary dependency on the treewidth of the graph (as opposed the kO(k) dependency in Theorem 14).
Theorem 15. Let t be arbitrary but fixed integer. Given architecture G (V, E) of treewidth at most 1, it is possible to compute an untangling (or correctly determine that none exists) in time f(t) [V] for computable function f.
7 Concluding Remarks
We have examined the theoretical boundaries of computational tractability for training neural networks both for the fundamental cases ReLU and linear activations, complementing a flurry of recent
results establishing increasingly stronger lower bounds for network training. Our results generalize recent algorithms for optimal ReLU-activated network training (Arora et al. 2018 Boob al. (2022) and are among the first to identify non-trivial class of linear-activated architectures admitting polynomial-time training.
A natural direction for future work is to examine the extent to which the identified islands of tractability can be generalized before stepping into intractable territory. long-term goal is obtain a clear cutoff between intractable and tractable cases of network training. We conclude with three specific questions directly arising from our results:
1. Is LIN-NNT polynomial-tin -immee tractable when restricted to constant-treewidth architectures?
2. Is it possible to solve RELU-NNT for constant-size architectures containing hidden neurons with out-degree greater than 1?
3. Can the obtained results be generalized other loss functions?
Acknowledgments and Disclosure of Funding
The authors confirm that there are no competing interests. We acknowledge support by the Austrian Science Fund (FWF, START Project Y Y1329). Mathis Rocton further acknowledges support by the European Union's Horizon 2020 research and innovation COFUND programme (LogiCS TUWien, grant agreement No 101034440).
References
Abrahamsen, M., Kleist, L., and Miltzow, T. Training neural networks is er-complete. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference ral Information Processing Systems 2021, NeurIPS 2021, December 6-14. 2021, virtual, pp. 18293-18306. 2021. URL https: //tpcee///rocceiingg neurips cttccc//ppppa wwcc/appr//000/ haaper/2021hhah/ 9813b277ee02886 (rt.)//26677000011ooeeeeeeeeeee2 aas.earrrr.aeeeteteaaaaaaa.aaa. Abstract.html
Neu-
Arora, R., Basu, A., Mianjy, P., and Mukherjee, A. Understanding deep neural networks with rectified linear units. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018, URL https: //tt:re///peerevee wetttfoumtidddeeeeeeem
Bertschinger, D., Hertrich, C., Jungeblut, P., Miltzow, T., and Weber, S. Training fully connected neural networks is ar-complete. CoRR, abs/2204.01363 2022. doi: 10.48550KKXX..22044.1166 URL httph:tt //doi. org/ 48550 w2wp://wwwww........... 01368
Bodlaender, H. I.. Treewidth of graphs. In Encyclopedia of Algorithms, pp. 2255-2257. 2016. doi: 10.
URL http:://loo..ogg//000000//111111
431
Boob, D., Dey, S. S., and Lan, G. Complexity of training relu neural network. Discret, Optim., 44 10art):100620, 2022. doi: 10. d00. 100620.. URI,tttps ://ooi ottp//..///0/......1
disopt 2020. 100620
10

---

Brand, C., Koutecký, M., and Ordyniak, S. Parameterized algorithms for milps with small treedepth. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty- -hird Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 12249-12255 AAAI Press, 2021. URL httptt//s////js aaai org/ index. Catp/AAA//rraa articl/ view/17454
Bulatov, A. A. A dichotomy theorem for nonuniform esps. In Umans, C. (ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. pp. 319-330. IEEE Computer Society, 2017. doi: 00.1109/FOCS.2017..11 URL
https://doi org/ 10. 1109/FOCS. 2017.37
Cohen, N., Sharir, O., and Shashua, A. On the expressive power of deep learning: A tensor analysis. In Feldman, V.. Rakhlin, A., and Shamir, O. (eds.), Proceedings of the 29th Conference Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pp. 1998-28..40 JMLR.org, 2016. URL htt::pp::/proooto http::/pproceedinngg mlr press/v45 h4tp///e/////6/6////////// html
cohen16.
Courcelle, B.
The monadic second-order logic of graphs recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. doi: 10. 10.111//099055400099990000000000 10. 10.10006/890-555 5401 (90) 90043-H
httpss://///o org/
Courcelle, B. and Engelfriet, J. Graph Structure and Monadic Second-Orden Logic A Language- Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. ISBN 978-0-521-88 00-5211-8833311 URL http:// wwabbbriigg.orgggf.g..
knowledge/isbn/ tte.ettt55555. /ttp///teeem5777//111//e 1oc.stef_oocaleff___
Cowley, B. and Pillow. W. High-contrast "gaudy" images improve the training of deep neural network models of visual cortex. In Larochelle, H., Ranzato, M., Hadsell, R., Bal- can, M., and Lin, (eds.), Advances Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL Abstract............ httm wew.eddd000offdfdooo wo1.://6cc111111111233--3-13
Dahiya, Y., Fomin, F. V., Panolan, F., and Simonov, K. Fixed-parameter and approximation algorithms for PCA with outliers. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International
Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2341-2351. PMLR, 2021. URL http:// proceedings mlr, wttppppwsseeeeepeppt.ppp datay//1aahaa221bbbb html
Dey, S. S., Wang, G., and Xie, Y. Approximation algorithms for training one-node relu neural networks. IEEE Trans. Signal Process., 68:6696-611 6706, 2020. doi: 10.1 101109/TSP22220.039936 URL https://doi. org/ 10. 1109/TSP. 2020 3039360
Diestel, R. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. ISBN 978-3-642-14278--
Edelsbrunner, H., O'Rourke, J., and Seidel, R. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput., 15(2):341-363 1986. doi: 10.1137/0215022 URL https |
ordoi.org/1..o 1137/1177000 /0215024
Eldan, R. and Shamir, O. The power of depth for feedforward neural networks. Feldman, V., Rakhlin, A., and Shamir, O. (eds.), Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference
Proceedings, pp. 907-940. JMLR.org, 2016. URL http://prooceddings mlr...mr........ www.mmlr.rreeee pwt.sp//esss.. el html
Frank, A. and Tardos, É. An application of simultaneous diophantine approximation in combinatorial optimization. 7(1):49-65, 1987.
Froese, V. and Hertrich, C. Training neural networks np-hard fixed dimension. Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing
Systems 2023, NewrIPS 2023, 2023. URL U httttt:p/////i: http://..ooo/.....o/ 48550/ arXiv. 2303. 17045 to appear.

---

Froese, V., Hertrich, C., and Niedermeier, R. The computational complexity of relu network training parameterized by data dimensionality. J. Artif. Intell. Res., 74:1775-1790, 2022. doi: 10.16133jair. 1.3///rr....1344... URL https::/ddoi. 1ttp///0.1113////1 1613/ 1.14547
Ganian, R. and Korchemna, V. The complexity of bayesian network learning: Revisiting the superstructure. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, vir- tual, pp. 430-442, 2021. URL https::/proceed:: 0000952298800/366001100000aaa2.2
neurips. cc/ patppppppp//aaaaaaaaaapaa html
Ganian, and Ordyniak, S. Solving integer linear programs by exploiting variable-constrain interactions: A survey. Algorithms, 12(12):248, 2019. doi: 10.3390/a1212224,, URL https
//doi. wttpr//....39//11110 000.3/3//
Ganian, R., Kanj. I. A., Ordyniak, S., and Szeider, Parameterized algorithms for the matrix completion problem. In Dy. J. G. and Krause, A. (eds.). Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsnn Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1642-1651. PMLR, 2018. URL
v80/ mlr. press/v800 /atps//////gaaaa8... ganian18a... html
Ganian, R., Hamm, T., Korchemna, V., Okrasa, K., and Simonov, K. The complexity of k-means clustering when little is known. In Chaudhuri, K., Jegelka, S., Song, L.,, Szepesvári, C., Niu, G., and Sabato, (eds.), International Conference on Machine Learning. ICML 2022, 17-23 July 2022. Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 6960-6987. PMLR, 2022. JRt.jtttps:/pproceeiing .mr.g.gssmm.....mm.............r htt...prees//v11111 http://v2/gggggaaaaaaaaa gangganniinnn wnw.annna...aaaamamam.aaa.aa.a html
Gao, H., Cai, L., and Ji, S. Adaptive convolutional relus. In The Thirth-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY. USA, February 7-12, 2020, pp. (9914-3921 AAAI Press, 2020. URL Jnttss//:// aaai waai.org///aaaaaaa.......a.o...a index.dexx... phtp/AAA//artiilee/eaeeeeeeeeeee
Goel, S., Klivans, A. R., Manurangsi, P., and Reichman, D. Tight hardness results for training depth-2 relu networks. In Lee, J. R. (ed.), 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8. 2021, Virtual Conference, volume 185 of LIPIcs, pp. 22:1-22:144 14. Schloss Dagstuhl Leibniz-Zentruu
für Informatik, 2021. doi: 1.42300LLPP.c.IITSSS2222...... URL
Sttps:///aos org 10. 4230/LIPICI. ITCS. 2021.
Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning. MIT Press, 2016.
URL http
7/www www.deeeplearningbook. org/
Grüttemeierr N. and Komusiewicz, C. Learning bayesian networks under sparsity constraints: A parameterized complexity analysis. J. Artif. Intell. Res., 74:1225-1267, 2022. doi: 10. 10.1613/jair.1. 13138. URL hhttps://doi: orgo http://0..113/jrr...r.. 1.1138
Haase, C., Hertrich, C., and Loho, G. Lower bounds on the depth of integral relu neural networks via lattice polytopes. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL httpt:::://pepreieeettt net/ pdf 2
Harding, E. F. The number of partitions of set of points in k dimensions induced by hyperplanes. Proceedings of the Edinburgh mathematical society, 15(4):285-25) 2899, 1967.
Heggernes, P. and Telle, A. Partitioning graphs into generalized dominating sets. Nordic J. of Computing, 5(2): 142, jun 1998. ISSN 1236-6064.
Hertrich, C. Facets of neural network complexity. PhD thesis, Technical Univer- sity of Berlin, Germany, 2022. URL.
org/ urn nbn de:
I-202033011889125500777
12

---

Hertrich, C., Basu, A.. Summa, M. D., and Skutella, M. Towards lower bounds on the depth of relu neural networks. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Con- ference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 3336-3348, 2021. U htt.://seeeee22afeeeeeeaaaaaaaaa
neurips. cc/ httppppppe/////////// Abstract. html
Kannan, R. Minkowski's convex body theorem and integer programming. Math. Oper. Res., 12(3):
415-440, 1987.
Kozlov, M. K., Tarasov, S. P., and Khachiyan, L. G. Polynomial solvability of convex quadratic programming. In Doklady Akademii Nauk, volume 248, pp. 1049-1051. Russian Academy of Sciences, 1979.
Lenstra, H. W. and Integer programming with a fixed number of variables. Math. Oper. Res., 8(4): 538-548, 1983.
Maass, W. Bounds for the computational power and learning complexity of analog neural nets. SIAM J. Comput., 26(3):708-32. 1997. doi: 1011137/000733999356411 URL https 1 /1111///0007773999956666111
Megiddo, N. On the complexity of polyhedral separability. Discret. Comput. Geom., 3:325-337,
1988. doi: 10. 10.1007/BF0218899 URL
Ordyniak, S. and Szeider, S. Parameterized complexity results for exact bayesian network structure learning. J. Artif. Intel. Res., 46:263-302, 2013. doi: 10.1613/jair.7444. URL https://doi org/10. 1613/jairz .37444444
Pang. J.-S. Methods for quadratic programming: A survey. Computers & Chemical Engineering, 7 (5):583-594, 1983.
Panigrahi, A., Shetty, A., and Goyal, N. Effect of activation functions on the training of overparametrized neural nets. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https
//openreview peet/forumidd-rkgttee
Robertson, N. and Seymour, P. D. Graph minors. i. excluding forest. J. Comb. Theory, Ser. B, 35(1): 39-61, 1983.
Schaefer, T. The complexity of satisfiability problems. In Lipton, R. J., Burkhard, W. A., Savitch, W. J., Friedman, P., and Aho, A. V. (eds.), Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, Califormia, USA, pp. 216-226 ACM, 1978. doi: 10.1 10.1145/800133. 804350. URL https: wttp://oii.ooo org 10. 0144/8001133 804350
Simonov, K., Fomin, F. V., Golovach, P. A., and Panolan, F. Refined complexity of PCA with outliers. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 5818 1128...86...111 PMLR, 2019. URL http://proceeding mlr. www...rresst...... wwwps//9s////// simonovi9a. html
Tarski, A. A Decision Method for Elementary Algebra and Geometry:
Prepared for Publication with the Assistance of J.C.C. McKinsey. RAND Corporation, Santa Monica, CA, 1951.
Telgarsky, M. benefits of depth neural networks. In Feldman, V., Rakhlin, A., and Shamir. O. (eds.). Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pp. 1517-1539. JMLR.org, 2016. URL http:http:pppete http:tttt/prcceeiing.
mlr. wwwps/eevaaaeeee www/tt/gggeggllll.e.ee html
Velu, R. and Reinsel, G. C. Multivariate reduced-rank regression: theory and applications, volume 136. Springer Science & Business Media, 2013.
13


Reviews:
[{"review_id": "gmmRYNIQSp", "reviewer": "Reviewer_Yud1", "summary": "This paper investigates the theoretical complexity of finding the global optimal solution of ReLU networks and linear networks. Specifically, it first considers a specially designed neural network, each hidden neuron of which has only one outgoing edge. By using the homogeneity of the ReLU function, it reparameterizes this network such that all the weights (except the first layer ones) are either -1 or +1 (i.e., moves the absolute values into the first layer weights). In this way, it shows that it is possible to find the global optimal by enumerating the partitions of the data space, with time complexity that is polynomial in the dataset size (but not polynomial in network size). It also shows that a normal fully-connected neural network can be “blown up” to one with the above special design (out-degree = 1 for each neuron), by replicating hidden neurons that have multiple out-going edges.", "questions": "No further questions", "limitations": "limitation is not discussed in the main text", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The obtained time complexity of finding the global optimal is polynomial in the dataset size. \n\nThis paper handles multi-layer ReLU/linear neural networks, while prior works only obtain similar results on one-hidden layer networks.", "weaknesses": "The main trick of this paper is to consider those variables (e.g., network width, depth, input dimension etc) in which the time complexity is exponential or greater as constants, so that the time complexity can be *stated as* polynomial – in the remaining variable (i.e., dataset size). I don’t think this is a clever trick, as it does not solve the problem at all. Note that the complexity is far greater than polynomial (or even than exponential) in the other variables, for width $w$ it is $|D|^{w2^w}$, and for depth it is larger than $|D|^{2^{\\lambda^l}}$. \n\nGiven this large complexity in width and depth, the result of time complexity has little to no usefulness for practice. \n\nThe paper only focuses on the time complexity, while ignoring the space complexity – memory costs. Note that the blowing up procedure requires much more space complexity, which is exponential in depth. Recall that a neural network without blowing-up only requires space which is linear in depth. This huge memory cost is a drawback of the analyzed training algorithm, and should be considered and analyzed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to point out two potential misunderstandings related to the purpose and scope of the article. Indeed, we do obtain polynomial-time algorithmic upper bounds under the assumption that certain parameters of the input (such as the size of the architecture) are fixed to be constants. However, as previous work has shown and as has been elaborated on in depth in the paper, this is mathematically proven to be simply unavoidable (see the discussion on lines 191-204); in this sense, our results even provide essentially optimal running time upper-bounds. The emphasis of the paper is very clearly positioned on pushing the complexity-theoretic frontiers of tractability, and it most certainly is not our intention to generate the impression of attempting to further the state-of-the-art of Neural Network Training in practice.\n\nThe second point of concern - and perhaps the more severe misunderstanding - lies in the characterization of our algorithmic results as a “trick” where one simply hides the exponential dependencies in the algorithms. This is not the case; the article is very explicit concerning which parts of the input are considered to be fixed. Crucially, there exists a vast literature on complexity-theoretic tractability results on problems that focus entirely on the theoretical study of the boundaries of tractability under the assumption of certain “variables” of the input being fixed. Not only are there many such publications at NeurIPS and related venues every year (see the discussion of related work in the second paragraph of the article), but this fundamental idea is pervasive throughout computer science and in fact forms the central concept of the subfield of parameterized complexity. In fact, the criticism raised here could be used to automatically dismiss, among others, each of the articles cited in that paragraph, and hence we believe it to be unjustified.\n\nRegarding the final point, while a detailed space-complexity analysis is beyond the scope of the paper, we do agree that it is interesting and will make sure to mention the fact that the blow-up procedure has an impact on the space complexity of the problem in the final version."}, {"review_id": "UoHLBzc9zL", "reviewer": "Reviewer_SU6D", "summary": "This paper studies the computational complexity of training linear and ReLU neural networks. Under assumptions such as the squared loss and the out-degree of every hidden neuron being exactly one, the authors prove that there exists an algorithm such that the global optimal solution can be computed in polynomial time for the linear and ReLU networks when the input dimension and the number of hidden neurons are fixed. To better understand the tractability of training linear networks, the idea of untangling is proposed and used to develop the existence of a polynomial-time algorithm for training linear networks. Although deciding whether a given architecture has an untangling is NP-hard in general, the authors prove that the complexity of determining this property for linear networks is linear time. They also provide a complexity result for computing an untangling of an architecture of bounded treewidth.", "questions": "1. The squared loss is assumed in this work. Would it be possible to extend it to convex loss functions?\n2. Usually, there are symmetries in the dataset. Would it be possible to leverage the symmetries or redundancies in the data and reduce the bounds? Would it be possible to apply that to drop some strong assumptions on the architecture and still maintain the polynomial complexity?\n3. Do you need the number of bits of the input in the bounds? What computational models are you assuming?\n", "limitations": "The authors point out two questions at the end as possible future directions. However, due to the unrealistic assumptions mentioned above, there are strong limitations to applying the results to applications. Although this is a purely theoretical paper, I still think it would be a good idea to describe possible workarounds of the assumptions and how the current results could be impactful to machine learning problems.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The novelty of this paper is clear. First, it ensures the existence of a training algorithm for linear and ReLU networks that achieves global optimal solutions in polynomial time under a different assumption compared to previous work. Second, the idea of untangling is proposed as a new assumption for studying these networks. These contributions could open up a new angle for studying the training complexity of ReLU and linear networks. The paper is well-written, and I enjoy reading the paper.", "weaknesses": "In my view, the assumptions are the main weaknesses of this work. The out-degree being 1 and the untangling of architecture are unrealistic assumptions. Deep neural network models in practice do not satisfy these assumptions. Second, finding the global optimal solution seems to be unnecessary. Usually, we would avoid getting to the global optimal solution because of overfitting. Third, when a machine problem is given, we only have the dataset so the number of hidden neurons $w$ is unknown. Based on these reasons, it seems hard to apply the results in this paper to applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are indeed well aware that the tractability results obtained in the article are of theoretical interest, and that real-life networks are unlikely to satisfy the stated structural properties. Even the tractability for general bounded-size ReLU-NNT architectures obtained in Section 5 are not likely to be of practical significance. Instead, the article follows up on a fundamental and well-established line of work that aims at understanding the theoretical boundaries of tractability (in the complexity-theoretic sense) for Neural Network Training. \n\nRegarding the three questions:\n1) The main bottleneck for such an extension lies in solving the resulting convex program; in the case considered in the article (the commonly used squared loss function), this is a constrained least-squares problem, which is polynomially solvable. In the more general convex case, this still seems possible, but the arguments become more intricate and would involve considerations about machine precision and approximation that would obscure the main conceptual message. We will add a corresponding remark to the paper.\n2) Indeed, it might be possible to study how the structure of the training set itself affects the complexity of the problem. However, to get rid of the exponential dependencies in the architecture parameters, one would have to show that the known hardness results (for an arbitrary training set) weaken or collapse when assuming specific structure. It is an interesting question that could point towards follow-up work.\n3) This is indeed an oversight on our part. We’re assuming a standard Word-RAM model of computation, and the bit complexity does enter in our bounds in the same way that it does for the quadratic optimization methods used; we are grateful to this reviewer and Reviewer 3t5Y for pointing this out. We will of course update the running time bounds in the final version, and remark that this minor change (by a polynomial factor) does not affect the article’s contribution.\n\nFinally, we will expand the conclusion by highlighting that it would be useful to understand how one could avoid the strict prerequisites for our tractability results in more practical settings. "}, {"review_id": "cfKsgHIqFw", "reviewer": "Reviewer_t5Nf", "summary": "The paper studies algorithms for exact minimization of quadratic loss over ReLU and linear neural networks when the total number of neurons is a fixed constant. The results can be divided into two parts:\n\n* A polynomial time algorithm for a fixed size ReLU/linear network, when it has the following structure: 1) One layer of neurons with arbitrary edges between inputs and those neurons. 2) A tree of neurons (i.e., every neuron has out-degree one) on top of that. More precisely, the algorithm runs in time $|D|^{O(nw 2^w)}$, where $|D|$ is size of the dataset, $n$ number of inputs, and $w$ total number of hidden and output neurons.\n\n* A polynomial time algorithm for a (possibly large) linear network whenever all hidden neurons can be collapsed (like in a graph minor) onto inputs and outputs such that the resulting bipartite graph is equal to the connectivity graph between inputs and outputs. So, it's some sort of condition that says that the graph has a \"simple\" connectivity structure. This pattern of connectivity needs to be known to the algorithm, the authors prove that it is in general NP-hard to find it.\n\nIn both of these settings polynomial-time algorithms are already known for the most natural subcases (for example, one fully connected layer in the ReLU case).", "questions": "Line numbers are for the extended version from the supplement.\n\n* I admit this is a matter of opinion, but the title seems a bit over the top. I would suggest to make it more informative.\n\n* remark after lemma 3, I think it is great that you worked out the details of this enumeration problem. But as a point of feedback, parts of this remark read to me as unnecessarily hostile.\n\n* line 372, typo \"we the set\"\n\n* Corollary 6, technically you never defined \"MIXED-NNT\".\n\n* proof of Theorem 12, you call inputs/outputs $x$ and $y$, but then you switch to $n$ and $o$. also in paragraph starting in line 547, I would double-check the transposition symbols. \n\n* proof of Theorem 13, I found it frustrating that $D_i$ and $D_j$ denote very different objects in this proof.", "limitations": "see above", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "* The topic is interesting and relevant. As the authors point out, we know surprisingly little even about simple cases of this basic problem.\n\n* The paper is clearly written, including the context and exhaustive discussion of related work. It was a pleasure to read.\n\n* A lot of attention was paid to careful and correct explanations in the proofs.", "weaknesses": "It is not clear how many interesting new cases these theorems cover. I did not feel the results and proofs were particularly surprising. For example, the ReLU proof quite heavily (but skillfully) relies on previously used enumeration of hyperplane partitions. And the tree structure in the ReLU theorem does not look very relevant to practical architectures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding the perceived weaknesses of our results, the class of networks where our algorithmic upper bound applies can indeed be considered as restrictive, but from a fundamental network-structural viewpoint we believe them to be a significant step beyond the previous state of the art. All results to date simply seem to suggest that solving NNT is a very difficult problem from the complexity-theoretic viewpoint, and in view of the strong existing lower bounds it is perhaps unrealistic to expect tractability for very general classes of networks (see also the comments of Reviewer 3t5Y).\n\nThank you for all the individual comments; we provide responses to these below. \n1) If the reviewers believe the title to be too strong or unspecific, we will of course change it in the final version.\n2) We never intended this to sound hostile, but after reading the text again we understand that it could have come across as such. We will carefully reformulate this part to fix this.\n\nPoints 3-6) will be fixed in the final version.\n"}, {"review_id": "r9wsMzh88E", "reviewer": "Reviewer_3t5Y", "summary": "This paper studies the computational complexity of empirical risk minimization (ERM) for neural networks, that is, given an architecture and training data points, find weights and biases of a global minimum of the training error. The problem is well-known to be NP-/ER-/W[1]-hard already in very easy special cases. This paper identifies a bunch of cases in which it can still be solved in polynomial time, namely in each of the following cases:\n- for ReLU networks with all hidden neurons having out-degree one, if the size of the NN is regarded as a fixed constant,\n- for an improper ReLU learning setting, leading essentially to the case of the first bullet point by blowing up the architecture,\n- for linearly activated NNs if they fulfill a certain structural property.\n\nMoreover, the authors analyze the computational complexity of determining whether a linearly activated NN satisfies the structural property mentioned in the third bullet point.", "questions": "No particular questions, but I invite the authors to reply to any of the comments I've made if they disagree.", "limitations": "All statements are mathematically rigorous and all assumptions properly stated.\n\nThe authors should mention that the blow-up in Section 5 might heavily increase the generalization error in learning settings, see my respective comment above.\n\nThe authors should point out more clearly that the purpose of the provided algorithms is purely theoretical, see my first point in \"weaknesses\".\n", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Given the significance and hardness of the problem, finding tractable special cases is a very important contribution to the theory of machine learning. This paper provides a decent starting point (building upon Arora et al. (2018)) and hopefully initiates further research towards this goal.\n- The paper is mathematically very well-written. It even cleans up with some vagueness in previous work (see Remark after Lem. 3).\n- The paper also is very precise in surveying the previous literature on computational complexity of ERM for NNs.", "weaknesses": "- The obtained algorithms are only of theoretical interest because (i) the tractable special cases are rather unrealistic, (ii) the running times have still high dependencies on \"fixed\" constants, and (iii) this work focusses purely on minimizing the training error and neglects learning / generalization. So the paper should really be seen as fundamental theoretical research rather than pushing the frontiers of what we can do in practice. As such, I think it is of significant value.\n\nApart from this, I have many minor comments as below. None of them is a reason to downvote for me, but I urge the authors to carefully work on them for the next version:\n\n- My impression is that the abstract is not very informative. Instead of spending too much effort on motivating the results there (see also my next comment), it would be better to be more precise of what this paper actually proves (why not simply state the main results?).\n- While I believe the paper makes important contributions (as outlined above), I am quite unhappy with the way the results are pitched, e.g. already in the abstract, and in lines 17-20, and other places where the authors claim that so little is known about the complexity of NN training. Yes, it is true that not many positive results have been achieved for pure empirical risk minimization, but this is for a good reason: the problem simply IS really hard in the worst-case, and this has been studied thoroughly. While I do agree that finding tractable special cases is an important research contribution, I believe that this will always only be possible for very special cases and therefore disagree with staging this as such a \"huge\" gap in the literature.\n- a recent preprint you might not be aware of is: Froese, Hertrich: \"Training Neural Networks is NP-Hard in Fixed Dimension\" (https://arxiv.org/abs/2303.17045). This includes a multitude of new stronger hardness results for both ReLU (and linear threshold) networks. I think you should cite this in line with other negative complexity results you already cite, like (Arora et al., 2018; Abrahamsen et al., 2021; Goel et al., 2021; Froese et al., 2022; Bertschinger et al., 2022). In particular in line 52, for the constant n case, the Bertschinger et al. (2022) result relies on multi-dimensional outputs. The new preprint suggested above shows that NP-hardness can already be achived with a single-dimensional output (and still only 2-dimensional input).\n- line 65: \"it is not difficult to show that LIN-NNT is poly-time tractable for any network of bounded size\": why is this the case? can you please elaborate? And does it depend on whether the NNs are fully-connected or not?\n- lines 68-69: are you referring to arbitrary n but constant w here? If so, please make the arbitrary dependence on n more explicit.\n- lines 90 and beyond: are you still talking about fixed size?\n- line 278: \"save\" -> \"except\"?? (or I completely misunderstand this sentence)\n- line 282: the ellipsoid method is NOT polynomial in the number of variables and constraints. In fact, its time complexity depends on the bit-length of the encoding of the input. It is what people call \"weakly polynomial\" and there is no strongly polynomial time algorithm known, even for the special case of linear programming. This also affects the running time of the overall algorithm. It should be something like $|D|^{\\mathcal{O}(nw2^w)}\\cdot\\mathrm{poly}(L)$, where $L$ is the bit-length of the encoding of all data points. Please fix this everywhere in the paper where you state running times involving a quadratic program (for example, this also applies to Thm. 12).\n- line 297: in addition to the cited thesis, you should probably also cite the paper the thesis is based on (Hertrich, C., Basu, A., Di Summa, M., & Skutella, M. Towards lower bounds on the depth of ReLU neural networks. NeurIPS 2021.) and additionally the following paper making significant progress towards proving the conjecture: Haase, C. A., Hertrich, C., & Loho, G. Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes. ICLR 2023.\n- line 305: point (2): \"polynomial-time training\" is very misleading here, this is only true if the architecture size is regarded as a fixed constant!\n- general comment about Section 5: what you are doing here is known as improper learning in the learning theory community. You should probably mention the term and compare to the respective literature. In particular, while you prove that your blow-up procedure does not increase the training error, such a move might heavily increase the generalization error of empirical risk minimization in learning settings. You should mention this!\n- line 348: Are you a \"such that\" missing at the end of this line?\n- line 379: d3 -> d_3", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the encouraging (and very helpful) feedback, and completely agree that obtaining an understanding of the fundamental complexity of neural network training is an important part of machine learning. The article improves our understanding of the boundaries of tractability of the problem in the complexity-theoretic sense, and as such the algorithms are - as you correctly mentioned - indeed of theoretical interest. \n\nPlease find our responses to the individual minor comments below.\n\nAd 1) and 2), we will reformulate the abstract and the relevant parts of the introduction in a way which is more informative and better highlights the state of knowledge about the problem (and, among others, we will tone down the claims about the “huge gap” in the literature).\n\n3) Thank you for the interesting reference - we will incorporate it into our discussion. This also applies to the reference provided in point 9).\n\n4) This is elaborated on in lines 172-175 (and even more details are provided in the appendix).\n\n5) Yes indeed; we will make this clearer in the final version of the article.\n\n6) No, when we switch to Lin-NNT we start by considering the general setting, without any conditions on the input dimension nor the number of hidden (or output) neurons. During our discussion (and specifically on line 109), however, we consider the case of having a bounded number of hidden neurons in order to compute the untangling of an architecture.\n\n7) We believe both are correct, but will reformulate to “except”.\n\n8) This is indeed an oversight on our part. We’re assuming a standard Word-RAM model of computation, and the bit complexity does enter in our bounds in the same way that it does for the quadratic optimization methods used; we are grateful to this reviewer and Reviewer SU6D\nfor pointing this out. We will of course update the running time bounds in the final version, and remark that this minor change (by a polynomial factor) does not affect the article’s contribution.\n\n9) See above.\n\n10) The architecture size (after blow-up) is a function of the initial architecture size, which is fixed, so we indeed are using fixed size architecture here. However, to improve clarity, we will reformulate this sentence to emphasize that the size is fixed.\n\n11) Thank you, we will mention this.\n\nAd 12) and 13), both of these typos will be fixed in the final version."}, {"review_id": "wU4S7xNKzh", "reviewer": "Reviewer_boAZ", "summary": "The paper studies the neural network training problem for ReLU and linear networks. They show new settings where the problem can be solved in polynomial time. They provide two main contributions: \n- For ReLU networks, they give a polynomial-time algorithm for training constant-size networks where the out-degree of all hidden neurons is $1$. This extends similar previous results for depth-$2$ networks. They observe that every constant-size network can be transformed into a network with the above structure. \n- For linear networks, they identify a condition, called untangling, that allows for efficient learning if the untangling is given. Finding an untangling is NP-hard in general, but if the network has a constant number of hidden neurons or a constant treewidth, then it can be found in linear time.", "questions": "See the “weaknesses” section.", "limitations": "The authors discussed the limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The neural network training problem is a natural question that has been studied in several prior works. This paper makes a further step towards understanding when this problem can be solved efficiently, for both linear and ReLU networks.\nAlso, the paper is well-written.  ", "weaknesses": "My comments are regarding the result on ReLU networks:\n- The result requires out-degree of exactly $1$ for all hidden neurons. It is indeed more general than the results of Arora et al. 2018 and Boob et al. 2022, but the family of networks covered by the new result and not by the previous ones is somewhat restricted. The authors show that every constant-size network can be transformed into a network with the above structure, but it is not clear to me what the implications of the ability to solve the problem for the transformed network are. It would be helpful if the authors elaborated further on the motivation for this transformation.\n- I am trying to understand what are the main technical differences between the current result and Arora et al. 2018, and what are the main non-trivial steps. I would be happy if the authors elaborate more on this issue. Below I provide some comments in this respect: \n    - Regarding Lemmas 1 and 2: The idea of “pushing the weights backward” in ReLU networks with out-degree $1$ of each neuron (i.e., making all weights in {-1,0,1} in all layers except for the first layer) is not new. It was done, e.g., in [1].\n    - Regarding Lemma 3: The authors compare it to Arora et al. in the Remark, and claim that both the bound on the number of partitions and the efficient enumeration method are essentially new. I actually believe that the $|D|^{O(n)}$ bound on the number of partitions follows immediately from the Sauer–Shelah lemma (do you agree?). I don’t know whether an efficient enumeration algorithm was previously known. Is it the main technical contribution in this result?\n    - Regarding Lemma 4: I believe that the Sauer–Shelah lemma can give a tighter bound here (namely, $|D|^{O(n \\cdot \\text{poly}(x))}$). Again, I don’t know regarding efficient enumeration.\n    - Given Lemmas 1-4, the proof of Theorem 5 becomes similar to the result from Arora et al., right?\n    - The result in Section 5, namely, transforming networks to larger ones with out-degree $1$, is a trick that was also used in prior works. As far as I understand, this is exactly Remark 2.2. from [1]. \n- Typo in line 215: should be $a_{u,w}^*$.\n\n[1] Maass, Wolfgang. \"Bounds for the computational power and learning complexity of analog neural nets.\" Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. 1993.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding our results on ReLU networks, the class of networks where our algorithmic upper bound applies can indeed be considered as restrictive - especially when one views it from the perspective of practical applications. However, from a fundamental graph-structural viewpoint, we believe that being able to solve architectures that have an out-degree of 1 is significantly more general than the previously established tractability result for the 3-layer architectures with a single output neuron considered by Arora et al. 2018, and the proof of our result does not straightforwardly follow from the previous state of the art. \n\nAs for motivating our result that “every constant-size network can be transformed into a network with the above structure”, we believe this is indeed of significant theoretical interest. Essentially, while the first result identifies a tractable subclass of fixed-size ReLU architectures, this latter result allows us to say something about *every* arbitrary fixed-size ReLU architecture. In particular, while solving NNT on such architectures is intractable in the complexity-theoretic sense, we show that one can transform the architecture into one that is at least as powerful while also being tractable. From a foundational perspective, we believe the existence of such a transformation to be somewhat surprising and not at all obvious. That being said, the result follows as somewhat of a corollary to our first algorithmic result and hence we would be willing to de-emphasize it if the reviewers prefer.\n\nWe believe that the main technical challenge that sets apart our first result from the previous result of Arora is that here we had to provide an efficient enumeration algorithm which can be applied inductively even for hidden nodes that lie deeper in the architecture; this can be seen as a “supercharged” version of the result they used in their setting. (As we note in the article, we also put this result on more solid theoretical footing.) While we are aware of several ways one could bound the number of such partitions, our algorithm requires us to efficiently enumerate them. Moreover, we would like to note that the article provides not only novel algorithmic upper bounds for ReLU-NNT but also for Lin-NNT; we believe these to also be an important contribution. \n\nFinally, thank you for the reference to [1]; we will incorporate it into our discussion in the final version of the article. We remark that while their construction is closely related to ours, the results and proofs obtained in [1] do not allow us to skip any of the steps in our proofs.\n"}]

Author rebuttal:
We thank all reviewers for their feedback and insightful comments. Detailed responses to individual questions and potential misunderstandings are provided as separate comments to each review.

Meta-review: The paper provides new computational complexity upper bounds for empirical risk minimization (ERM) of special families of neural networks. This problem is well-known to be NP-hard in the general case. The main contribution is to isolate special cases where polynomial time algorithms for ERM are possible:

* constant-size ReLU neural networks with hidden neurons having out-degree one;
* linear neural networks that obey a property called "untangling"; if the networks have constant treewidth, this property can be verified in linear time.

Most reviewers appreciated the technical contributions of the paper. However, during the discussion phase, concerns were raised about the utility of the bounds (technically, the algorithms are only fixed-parameter tractable). The issue of memory cost blow-up was also raised. The authors are encouraged to highlight (and address) these limitations while preparing the final version.
Decision: Accept (poster)