Tractability via Low Dimensionality: The Parameterized Complexity of Training Quantized Neural Networks
Authors: Robert Ganian
Frank Sommer
Manuel Sorge
Venue: ICLR 2026 Poster (2026)
Keywords: treewidth
parameterized complexity
quantized neural networks
ReLU networks
Primary area: learning theory
TL;DR: We study the classical and parameterized complexity of training quantized neural networks and obtain new upper as well as lower bounds for the problem.

Abstract: The training of neural networks has been extensively studied from both algorithmic and complexity-theoretic perspectives, yet recent results in this direction almost exclusively concern real-valued networks. In contrast, advances in machine learning practice highlight the benefits of quantization, where network parameters and data are restricted to finite integer domains, yielding significant improvements in speed and energy efficiency. Motivated by this gap, we initiate a systematic complexity-theoretic study of ReLU Neural Network Training in the full quantization mode. We establish strong lower bounds by showing that hardness already arises in the binary setting and under highly restrictive structural assumptions on the architecture, thereby excluding parameterized tractability for natural measures such as depth and width. On the positive side, we identify nontrivial fixed-parameter tractable cases when parameterizing by input dimensionality in combination with width and either output dimensionality or error bound, and further strengthen these results by replacing width with the more general treewidth.

TRACTABILITY VIA Low DIMENSIONALITY: THE PARAMETERIZED COMPLEXITY OF TRAINING QUANTIZED NEURAL NETWORKS
Robert Ganian
Algorithms and Complexity Group, TU Wien, Vienna, Austria rganian@gmail. com
Frank Sommer
Institute of Computer Science, Friedrich Schiller University Jena, Germany frank. wommmrruni-iaee -eanaddeee.dee
Manuel Sorge
Algorithms and Complexity Group, TU Wien, Vienna, Austria Manuel.sorgent tuwien.c. ac.at
ABSTRACT
The training of neural networks has been extensively studied from both algorith- mic and complexity-theorets perspectives, yet recent results in this direction al- most exclusively concern real-valued networks. In contrast, advances in machine learning practice highlight the benefits of quantization, where network parame- ters and data are restricted to finite integer domains, yielding significant improve- ments in speed and energy efficiency. Motivated by this gap. we initiate a sys- tematic complexity-theorete study of ReLU Neural Network Training in the full quantization mode. We establish strong lower bounds by showing that hardness already arises in the binary setting and under highly restrictive structural assump- tions on the architecture, thereby excluding parameterized tractability for natural measures such depth and width. On the positive side, identify nontrivial fixed fixed-paramesd parameter tractable cases when parameterizing by input dimensionality combination with width and either output dimensionality error bound, and fur- ther strengthen these results by replacing width with the more general treewidth.
INTRODUCTION
crucial task tied to the use of neural networks their training. On a high level, this training task can be characterized follows: given neural network architecture G and a data set D of input- output pairs, compute weights and biases of G which minimize the eттоr achieved by the network on D. While we have powerful heuristics for solving this problem (Sze et al., 2017: Li al., 2022), it also exhibits highly interesting behavior on the cumplexity-theoretice level and has been studied from this perspective
series of recent foundational papers (Dey et al., 2020: Abrahamsen al., 2021; Goel et al., 2021; Boob et al., 2022; Froese & Hertrich, 2023; Bertschinger et al., 2023; Brand al., 2023). detailed discussion of the state of the art is deferred to the end of this section; nevertheless, it will be useful to note that for crisper complexity analysis one typically considers the equivalent decision formulation of the problem -ic., where the input also includes an error bound & and the algorithm is allowed to output "no" if such error bound cannot be achieved by any combination of weights and biases.!
'Technically, in decision problems one is not required to output the weights and biases for positive instances; however, every algorithm obtained mentioned in this article is constructive and capable of doing We note that the optimization task he reduced the decision formulation via trivial search routine on f.

---

A common feature of all the above-mentioned complexity-theoretee works targeting the above NEURAL NETWORK TRAINING (NNT) problem is that they assume the numbers occurring in the network to be reals. This is natural perspective that matches the classical formalization of neural networks. However, a series of recent advances have shown that one can significantly improve speed and energy efficiency by quantizing the neural network, i.e., forcing the numbers to lie in specified domain of integers (Kilic et al., 2022). For example, Wang et al. (2025) recently showed that one can achieve accuracy results comparable the real-valued setting when quantizing to 4 bits, i.e., with a domain size of 16; see also the preceding works of Yang et al. (2020) and Lin et al. (2022). Other works have also considered even stronger degrees of quantization, such as using binary domains (Lin et al., 2017; Zhu et al., 2019; Liu et al., 2020). In fact, several different methods have been developed to obtain high-quality quantized neural networks such as uully-quantized training (Zhou et al., 2016), mixed-preciss training (Micikevicius et al., 201 80, post-training quantization (Banner et al., 2019), and quantization-awatt aware training (Jacob et al., 2018).
Yet, the recent developments outlined above are not at all reflected in our understanding of the underlying foundational problem: neither the complexityttheorete lower bounds (Dey et al., 2020; Abrahamsen et al., 2021; Goel et al., 2021; Froese & Hertrich, 2023; Bertschinger et al., 2023), nor the algorithms underpinning our upper bounds for solving the training problem (Arora et al., 2018; Boob et al., 2022; Brand et al., 2023) can be translated into the quantized setting. We note that this does not seem to be merely the case of a missing "bridge" that would allow one to translate knowledge from one setting to the other-the training problem in the real-valued setting is 3R- complete (Abrahamsen et al., 2021; Bertschinger et al., 2023) but with quantization it is easily seen to lie in NP (see Section 2). pointing to fundamental difference between the two settings. Until now, we lacked any complexity thheoretcc study targeting NNT in the fully quantized setting.
The aim of this article is to fill the aforementioned gap by developing a comprehensive understanding of QUANTIZED RELU-NNT (see Section 2 for formal details and discussion of the error bound);
d- QUANTIZED RELU-ACTIVATE NEURAL NETWORK TRAINING (d-QNNT)
Input:
An architecture G with input and w output nodes, multiset D of d d-quantized data points, and an eтror bound &.
Output: A d-quantized neural network G over G such that the error of D on G is at most f,
or correct conclusion that no such network exists.
We remark that here focus on the ReLU activation function, as it is widely used in practice and has been the target of almost all foundational studies of non-quantized NNT to date (Dey et al., 2020; Abrahamsen al., 2021; Goel et al.,, 2021; Boob al., 2022; Froese & Hertrich, 2023; Bertschinger et al., 2023; Brand et al., 2023). Our results include not only lower bounds, but also the identification of tractable cases via the development of theoretical algorithms. All our lower bounds apply already to the simplest binary quantization, while our tractability results hold for arbitrary choices of the quantization constant d.
In order to construct a more detailed complexity map of d-QNNT, we perform our analysis also tak- ing into account the parameterized complexity paradigm (Cygan et al., 2015; Downey & Fellows, 2013) which associates problem instances with a suitably defined parameter, i.e., numerical mea- sure that captures various aspects of the instance. In the classical perspective, one would typically ask whether restricting the parameter & to constant allows to solve instances in time polynomial w.r.t. the input size n. By contrast, the most desirable notion of tractability in the more refined pa- rameterized paradigm is in time (k) n (11 for some computable function f. To exclude inclusion in FPT, one can either show that the problem is W[1]- or W[2]-hard (which still allows for the existence of algorithms running time, e.g., n (kk),, or NP-hard for a fixed value of k.
tractability (FPT), meaning that the problem can be solved
Contributions. For convenience, Figure provides mindmap of results that is intended to com- plement the description of our contributions.
Well-studied properties of the architecture G that might, first glance, seem as natural choices for parameters are its depth (the number of hidden layers) and width (the size of the largest hidden layer)-a direction which we explore in our first set of contributions.
2

---

tw a + Theorem 5
tw aata- F Theorem 6
[+A Theorem 2
+ 1 + width + depth
+ width + depth Theorem 3
a + i depth
Theorem 1
Theorem
parameter
FPT
W[2]-hard
NP-hard
reference
Figure 1: Overview of our results for d-QNNT. A combined parameter p consisting of single pa- rameters Pl, P2.33 Pa has an edge to a lower combined parameter if dropping one of the single parameters ps yields hardness. We use to denote the maximum degree of any neuron. Our main open question concerns the complexity w.r.t. w-see the Technical Overview and Section 5.
As a baseline result, we exclude any notion of parameterized tractability w.r.t. these two measures even when combined with the enror bound E and the output dimensionality In particular, in Theorem we show that 2- 2-QNNT remains NP-hard even when restricted to instances where & = 0, there is only single output node and no hidden layer-a result which shows that even training very simple quantized architectures is computationally intractable and forms a counterpart to the well- known intractability of training single neuron in the non-quantized setting (Goel et al., 2021; Dey et al., 2020). Naturally, the reduction underlying Theorem relies on the single output neuron having large indegree- however, in our second Theorem we establish the NP- Na-hardness of 2- 2-QNNT even on constant-degree architectures with a single hidden layer and é = 0. This latter result can be seen as a constant-degree counterpart to the ER-hardness of training shallow non-quantized networks to optimality (Abrahamsen et al., 2021).
While the above lower bounds paint a negative picture of the complexity of d d-QNNT, there is a silver lining: both reductions inherently require the input dimensionality to be large. As our second set of contributions, we show that parameterizing by a enables fixed-parameter neural network training in the quantized setting-but only when combined with additional restrictions. In particular, our results imply that for every fixed d, d-QNNT is fixed peeed-prrmmter tractable w.r.t. the combined parameterizations:
1. input dimensionalityy a, the width of G and output dimensionality w (Corollary 2);
2. input dimensionality a, the width of G and the error bound & (Corollary 1).
The above results naturally lead to the question of whether all of the parameters are required to achieve fixed-paramed tractability- in other words, could any of the parameters be dropped from the statement? For a, we already know that this is not the case: Theorem 1 rules out polynomial-time algorithms even if the width, and l are small constants.
Given the fact that both positive results rely on parameterizing by the width and a, it would be tempting to think that d-QNNT is fixed-parameter tractable w.r.t. a and the width alone-i.e.. that the third parameter can be dropped in both statements. As our third contribution, in Theorem rule this out by establishing the W/2]-hardness of 2-QNNT w.r.t. even on networks with no hidden layer. This means that neither w, nor & can be dropped from our algorithmic upper bounds.
The above considerations leave the width as the only possible "weak point" in Corollaries and 2. As our fourth contribution, we show that-at least if one wishes to preserve both positive results- it neither possible drop the width, nor replace it with the depth of G. In particular, our Theorem shows that 2-QNNT is NP-hard even when 2, there is a single hidden layer and & = 0.
While the width cannot be dropped or replaced by depth, our final fifth contribution we show that Corollaries and 2 can be strengthened: in particular, we prove that the results hold even if one replaces the width of architecture G with its treewidth tw(G) (Robertson Seymour, 1984). The latter is well-established measure of the tree-likeness of graph; architectures with hidden neurons it never exceeds the width, but can be arbitrarily smaller. For example, an architecture consisting of layers whose width alternates between small and large will have large width, but small treewidth. Thus, while non-trivial to prove, the following two results supersede and directly imply Corollaries and 2:
1. d-QNNT is fixed- -eremmeeeeeerr tractable w.n.t. a + tw(G) + w (Theorem 5);
2'. d-ONNT is fixed-paramed tractable w.r.t. tw(G) (Theorem 6).
3

---

Technical Overview. To obtain our lower bounds, we develop targeted reductions from a variety of problems, including BOOLEAN SATISHIABILITY, HITTING SET, and SET COVER. While each of the reductions is distinct, the constructed architectures often very dense and have simple graph structures. In other words, our results show that the difficulty of training in the quantized setting does not stem from the complexity of the architecture, but rather from the presence of high-dimensional data on the input or output. In fact, the main open question arising from our work is whether the con- verse is true: can we efficiently solve instances of d-QNNT with possibly complicated architectures, but constant input and output data dimensionality (i.e., + w)?
For our positive souult--seccficallyy Theorems 5 and the main technical difficulty is that the trained n-node networks could contain hidden neurons with ((n) incoming ares from the pre- ceding layer that have non-zero weights. Indeed, it is not difficult to construct instances with such polutions-and yet the dynamic programming techniques that form the cornerstone of most treewidth- based algorithms are incapable of efficiently searching for them. To deal with this issue, make a detour and first establish structural insight that we believe is of independent interest: every YES- instancee of d-QNNT admits at least one solution where the number of activated ares en- tering any node is poperebounded by function of the parameters. This is formalized in Lemma 1, and relies on an involved proof that builds on Steinitz' Lemma.
Full proofs and details deferred the Full version, which can be found in the supplemental material, are marked with (x).
Related Work. Beyond the related articles mentioned in the second paragraph, several of the ear- lier works in the field also studied (the complexity of) NNT in the partially quantized setting (Judd, 1988; Blum Rivest, 1992; Parberry, 1992; Courbariaux et al., 2015; Zhu et al., 2017) or with different activation functions (Judd, 1990; Schmitt, 2004; Doron-Arad, 2025). In particular, the NP-hardness of 2-QNNT can be inferred from the reduction in the seminal work of Judd (1990, Theorem 24) on training Boolean neural networks with AND and OR gates, and separately also from the reduction in Schmitt (2004, Theorem 7) using linear threshold activation functions. How- ever, our Theorems 1 to 4 obtain lower bounds in conjunction with additional restrictions the inputs that are required for our parameterized lower bounds. Crucially, we are aware of neither any in-depth multivariate complexity analysis in this setting, nor any works directly targeting the complexity of quantized neural network training with ReLU activation functions. (+)
2 PRELIMINARIES
For an integer d 2 1, we define the d-quantized integer domain Ze as f2 E Z 1
[1=1]), that is, Z, = (0. 1). Z,3 0, 1). Z4 = 0,,,0, 1, and so forth?. The d-domain Rei.U activation function ReI.U, Za Z.a is the restriction of the well-known rectified linear unit to that is, all negative values are mapped to 0 while on positive values ReL.U, is the identity except that inputs outside of E.a become max Zda-
We say that a network architecture is a directed acyclic graph (a DAG) G whose vertex sets are partitioned into layers, where layer 0 consists solely of sources, and such that an arc ab may only go from a vertex in layer i (for i E N) to vertex in layer i ++1 and all sinks lie in the same layer. We will refer to the sources and sinks the input and output neurons of G, respectively, while all other nodes of G are referred to as hidden neurons. We assume that the sources are equipped with fixed ordering, and the same also for the sinks. The maximum size of a layer with only hidden neurons is called the width of G, while we refer to the number of layers as the depth of G.
Let us fix a d-quantized integer domain Z.. A neural network G over an architecture G a tuple (G, wei wht, bias) where the weight function weight assigns each arc of G weight from Za. and the bias function bias assigns each non-source node of G bias from Z.z. Let the number of input and output neurons of G be and w. respectively. The evaluation of an input data vector I' E (Z,)a a is a mapping of which assigns each node of G a value (or activation) computed as follows:
"Our model matches, e.g., the so-called "EIM2" format of the 4-bit floating point standard FP4. Other low-bit number encodings have also been considered in the quantized setting (Wang et al., 2025), but we focus our exposition this theoretically cleanest model. While we do not formally prove this, all obtained results seem readily carry over different low- number encodings with only minor modifications to the proofs.
4

---

The i-th imput neuron receives the value æ[i]; For each neuron v E V(G) with predecessors 21,...,, Egg we set its value as² ReLUa((CiE)g f(z)- neight(zz;)) - bias(t)).
The imput to ReLU, above is sometimes called the pre-activation value. Given a data point p E D, say that neuron is active in G if in the evaluation of p. the neuron g receives positive activation; otherwise, it is inactive. We denote the restriction of f to the output nodes, represented vector of integers in (Za) ordered by the output neurons, as the output of the neural network on E. In the training setting, we will be dealing with d-quantizzd data points from (Z.a) x (Za)"² The error of a multiset of such data points is equal the number of misaligned data points, i.c., the number of pairs (z. 37) in the multiset such that the output of (G, we i iggt, bias) on I differs from y. With these definitions in place, we study d- d-QNNT as formalized in Section
d- d-QNNT is in NP (a certificate consists of linear number of integers from Ea), which contrasts the cocooppeess of the training problem in the non-quantized setting. In the non-quantized setting, one typically uses a wide variety of loss functions tailored to real-valued errors such as E2 (Brand et al., 2023) here, we focus on a simple error count (as also used, e.g., by Judd (1990)) in order to facilitate cleaner analysis. The majority of our proof's could nevertheless be directly and straightforwardly translated to other loss functions (this is easiest to see for Theorems 1, 2,2,4, 4, 5).
Treewidth. A tree decomposition T of an undirected graph G (or the underlying undirected graph of a directed graph) is a pair xI, where T is a tree and X is function that assigns each tree node t set x(t) S V (G) of vertices such that the following conditions hold: (P1) for every edge E E(G) there tree node such that e S X(t); and (P2) for every vertex v E V(G), the set of tree nodes with v E x(t) induces non-empty subtree of T. The sets x(t) are called bags of the decomposition T, and x()) is the bag associated with the tree node I. The width of a tree decomposition (T, x) is the size of largest bag minus 1. The treewidth of a graph G, denoted by (G),,, the minimum width over all tree decompositions of G.
A detailed treatment of parameterized complexity and treewidth is provided in the appendix (x).
3 LOWER BOUNDS FOR d- d-QNNT
In this section, we show that 2-QNNT remains intractable in highly restrictive settings. First, in Theorem I, we establish NP-hardness even if the architecture has no hidden neuron, only one out- put neuron, and for training without error. Note that Theorem 1 implies NP-hardness even when the combined parameter width + depth + w is upper-bounded by constant. Naturally, the corre- sponding reduction requires the output neurons to have an arbitrarily large degree. One could hence hope that architectures with constant maximum degree can be trained efficiently. In Theorem we show that this is not possible by establishing NP-hardness for this setting.
In both the reductions that underlie Theorems 1 and 2 the number of input neurons is large and in particular not upper-bounder bounded by function of the parameters. Hence, one could hope that small or even constant number of inputs allows for efficient training. We show that this not the case either. First, in Theorem 3, we provide W[2]-hardness for even if there is no hidden layer. Second, in Theorem 4, we show that 2-QNNT remains hard even if there are only 2 inputs and 1 hidden layer. Altogether, these results yield the lower bounds depicted in Figure 1.
Theorem (+). 2-QNNT is ND-hard even when restricted instances where é 0 and architec- tures with single output neuron and no hidden neuron.
Proof Sketch. We provide reduction from the NP-hard EXACT SET COVER problem (Karp, 1972)
where the input consists of universe U, and family F of subsets over U. The goal is to find subset S C F such that S is a partition of U, that is, 1) UsES S = U and 2) S n SS = 0 for each S S2 S.
We construct an equivalent instance / of 2-QNNT as follows; see Figure 2 for an illustration. Description of the architecture G. Abusing notation, for each set F E F create a set input
'We note that the bias is subtracted instead of added to the result due to the fact that, in the Goolean-domant case, subtracting allows the hias to actually interact with the weights (see also Kilic et al. (2022)). For larger domains, the distinction is inconsequential since we can flip the sign of the bias.
5

---

cupput layer
Exput layer
Figure 2:
An illustration of the reduction behind Theorem for the universe = [6] and the set family F with sets S (1, 5), S2 = (2, S3 (1, S4 (2,5), S5 = {3, , {6) with an exact set cover S = [Si. S2, Sa J. In the solution corresponding to S, each red are has weight 0 and each blue are has weight 1. The orange number is the bias of the output neuron.
S1
84
output layer
input layer
Figure 3: An illustration of the reduction behind Theorem 3 for the universe U = [6] and the set
family FF with sets S = {1, 5), {2,3). S3 {1,6), S4 52, S {3, 5), Se {6} and k = 3 and with a hitting set S = (2, 63. In the solution corresponding to S, inputs pl. and Ps are associated with elements 2, 5 and 6, respectively. Moreover, each red are has weight 0 and each blue are has weight 1. The orange numbers are the biases of the output neurons.
neuron F. Moreover, add 3 more dummy input neurons S*, Iy, and I2, respectively. Finally, add one output neuron z and add an are from each input neuron to the unique output neuron z. Description of the data set. For each element E U add two element data points: d' and d:: both have value in each input corresponding to a set containing u and value 0 in dummy inputs ø1 and 22- Moreover, d' has value 0 in dummy input S* and value 0 in output z, and de has value in dummy input 5* and value in output z. Finally, we add three further data points: dummy data points døi, d10, and dj1- All three have value 0 in each set input and in dummy input S Moreover, doi has values 2 = 0, 12 1 and output value O, d1o has values ø1 = 1, = and output value O, and d1 has values 21 1, 22 and output value
Finally, we set f = 0. To complete the proof, it remains to establish correctness. (+)
We note that one could also obtain Theorem by carefully adapting the hardness proof of Schmitt (2004, Theorem 7) our setting. However, the reduction we provide here simpler, self-contained, and additionally also implies W[L]-hardness with respect to the number of arcs with weight one in the solution. We continue by stating the hardness for constant-degree architectures; since this result not central to complexity landscape (see Figure 1), defer its proof to the appendix.
Theorem (+). 2-QNNT is NP-hard even when restricted to instances where architectures with only one hidden layer, maximum outdegree 3, and maximum indegree
|D] s 4, and
Next, we establish W-hardness w.t.t the number a of inputs even there no hidden layer.
Theorem (*), Even if the network has no hidden neuron, 2-QNNT is W[2]-hard when parameter- ized by the number of input nodes, even when restricted to architectures with hidden neurons.
Sketch. Sketch. We present reduction from the HITTING SET (HS) problem where the input consists of universe U, family F of subsets over U, and an integer k. The goal is to find a subset S C U (called hitting set) of size & such that S contains least one element of each in the family, that is, S. F + for any F E F. HS is W[2]-hard parameterized by k (Cygan et al., 2015).
We construct an instance of 2-QNNT as follows. For an illustration, see Figure 3.
Description of the architecture G. We create & input neurons . Pe. Abusing notation, for each set F' we create one set output neuron F. We add arcs between every input and output neuron. Description of the data set. For each element u. U we add k element data points d; d:..... di. Element u data point d' has value in input p; and value in each other input. Moreover, d; has value in each set output F such that F. Thus, d', has value 0 in each set output F' such that u & F'. Observe that the is element u data points all have the same output but they have pairwise different inputs. Then, add verifier data point d' which has value 1 in each input and in each

---

ouuput layer
hidden layer
spput layer
Figure 4: An illustration of the reduction behind Theorem for the formula with clauses ei I1 V 2g V F3, C2 = 21 V Σz V 24, 21 V bg V ΣΑ. and assignment A with { 24) + true and { va + false. an optimal solution all arcs have weight 1. The biases of of solution corresponding to A are shown in orange.
V I3 V 24 with a satisfying
output. In the following, we say that two data points d1 and d2 have the same type if the input values of dj and d2 are pairwise identical. Note that we have exactly + distinct types of data points.
Finally, we set E = k- (1U1 | 1). To complete the proof, remains to establish correctness. (+)
For our fourth lower bound, we use a "compressed" version of the construction behind Theorem to obtain NP-hardness for only 2 input nodes and data points.
Theorem (+). 2-QNNT is NP-hard even if 2, l 0, [D] 3, and depth 1.
Proof Sketch. We present reduction from 3-SAT (Karp, 1972), where one is given CNF for- mula & on variables .I.....,,, Zn and
m clauses each consisting of precisely three literals.
We construct equivalent instance I of 2- R-QNNT as follows; see Figure 4 for an illustration. Description of architecture G. We create two imput neurons 21 and 22. For each of the two literals of variable 2; with [n]. we create two hidden neurons I; and I; associated with variable Thus, we create 2n hidden neurons. Moreover, we create a variable outpul neuron v; associated with variable for each variable z;. Also, we add one clause oulpul neuron cj for each clause of h. Thus, we create n n++MM m output neurons. We add an are from each input neuron to each hidden neuron. Next, add the variable output neuron Y; associated with variable T;- Finally, for each clause Cj consisting of literals P1, P2, and Ps. add the ares (Ph, (j) for each h E [3].
from each of the two hidden neurons 2; and associated with variable to
Description of data set. Here, we use the notation (z1, 22) + (V,C) for the data points, where and 22 are numbers referring to the inputs, and V and C vectors referring to the outputs. More precisely, V has length n, and the i-th entry corresponds to the variable output neuron e, and C has length m, and the j-th entry corresponds the clause output neuron cy. Whenever we put in any of the three vectors, we mean that all corresponding outputs receive value 0 or 1, respectively.
We add data points: (1) The verifier data point with (L,0) + (0, 1), (2) the verifier data point with (0, 1) + (0, 1), and (3) the choice data point with (1,1) ~ (1, Finally, we set f == 0.
Intuition. Recall that we say that given a data point p neuron q is active if the evaluation p. the neuron receives a positive activation; otherwise, it is inactive. The idea is that when considering verifier data point, the active hidden neurons correspond to satisfying variable assignment. We achieve this with the variable output neurons: If both hidden neurons and associated with variable 2₁ are active for the verifier data point, then since the value of the variable output neuron v associated with needs to be 0 and since and are the unique neighbors of v; this then implies that the value of v; for the choice data point also O, and not as desired, yielding an error.
To complete the proof, it remains to the above intuition to formally establish conrectness. (*)
4 FIXED-PARAMETE TRACTABILITY
In this section prove our tractability results for parameter combinations that include the width, treewidth, and number a of input neurons. We begin by showing a structural result (Lemma 1) that states that there is always solution that has upper-bounded degree in the sense that, for

---

each neuron, there is only bounded number of incoming ares with nonzero weights. We then use Lemma to prove tractability of d-QUANTIZED RELU-ACTIVATED NEURAL NETWORK TRAINING (d-QNNT) without error with respect to the treewidth and number a of imput neurons (Lemma 3). Then we show how to lift this result to training with nonzero error bounds and how the treewidth results imply the corresponding results for the width.
Consider a neuron v in a neural network. Define the non-zero in-neighbors of v to be the in- neighbors u of o such that weight(wo) o O. The non-zero indegree of is the number of non-zero in-neighbors.
Lemma 1 (+). Let G be an architecture and D a data set with p distinct input vectors. If there is neural network over G with zero error DD then there is a neural network G over G with zero error on DD such that for each neuron v in G the number of non-zero in-neighbors of v is at most (dp))(p)
We prove Lemma 1 by using Steinitz' Lemma, stated as follows.
Lemma 2 (Steinitz' Lemma (Steinitz, 1913; Sevast janov, 1994)). Let || |l be an arbitrary norm on F. Let " Im E Rd such that Lie(m) 2, 0 and for each E [m]] we have ||= S 1. Then there exists a permutation л E Sm such that all prefix sums have norm most d. That is, for each k E [m]] we have 11 ||Zje(m Tx(5)| S d.
Proof Sketch for Lemma 1. Consider a neuron v in a solution network. We can collect the activations of v for each input vector in a vector ğ (Zu)². Assume for simplicity that we don't 't have ReLU activations and instead simply pass through the weighted sum of the activations of the in-neighbors and, furthermore, each of the summed activations is in (Za)². Then, 8' is small-norm vector and it is obtained as a sum of small-norm vectors. Steinitz' Lemma tells us that we can reorder the vectors such that each prefix sum has small norm. This means that, if there are many non-zero in-neighbors to v, then at least one prefix sum occurs twice. This means that the vectors in between these two identical sums sum to zero and we can simply set their corresponding are weights to zero without changing the activation of v. Care must be taken to preserve the ReLU activations and boundaries of (Za)² and to ensure that all vectors in the sum have small norm.
We next show how the degree bound above can be used to efficiently train neural networks for low-treewidth architectures and small number of input neurons. We will use dynamic program over a tree decomposition. Essentially this means that we need to maintain for small separators what the status of partial solutions on one side, say the left side, of the separator is and this status needs to be encoded in a small number of states. Consider neuron in such a separator. We want to maintain as a state of the partial solution which pct-vaiiittion values has already received on the left side of the separator. If the non-zero indegree of solution is large, then we may have already seen an unbounded number of negative pre-activation values, but on the right side we may still see equally large number of positive pre-activation values, in total summing in Za. To properly maintain the activation of v, we would thus need to maintain unboundedly large pre-activation values, leading contrast, using the indegree bound established in Lemma 1, we can assume that the sums of pre- activation values are bounded and only look for such solutions.
small value
large, unbounded number of
states. In
Lemma 3 (x). d-QNNT with E is FPT w.r.t. the treewidth G and the number of input nodes.
Proof Sketch. Let (G, a., w, d, D, 0) be an instance of d-QNNT with error bound = 0 and a input nodes (i.e., neurons). Let X be the set of distinct input vectors in D and tw be the treewidth of the input architecture G. First, we compute a tree decomposition T = (T, of the underlying undirected graph of the architecture G that has width at most 2tw + 1 (Korhonen, 2022). We then proceed by dynamic programming on T. Without loss of generality, there are at most d" different input vectors (otherwise either there are multiple pairs of equal pairs of input and output vectors, of which we can drop one arbitrarily, or one input vector is associated with two different output vectors, and we have trivial no-instance). Thus, by Lemma we know that, if there is solution (odd")
neural network, then there is solution with non-zero indegree at most (d(d)))o(d')) We hence try to find solution with non-zero indegree most some integer A == (lad") (Indeed, we won't 't enforce this indegree bound, but we are guaranteed to find a solution, potentially with larger non-zero indegree, if there is one.)
8

---

Partial neural networks and evaluations thereof. To define the dynamic-prose programming table, need to define what partial solution is for the part of the architecture we have already seen in the dynamic program. Let W S V(G). A W W-partial neural network over architecture G is a tuple (G, we ght, b bias), where we ght and b a are defined in the same way as for neural networks except that the domain of bias is W and the domain of we i ght. is the set of ares of G with both endpoints in W. Note that the activation value for neuron V on a certain input vector is defined for each path P in G from an input neuron to all biases and weights of neurons and ares on P are defined. Below we will additionally refer to activation values for further neurons based on assuming that they receive certain given weighted activation values from in-neighbors where biases or weights are not defined. More precisely, for W-partial neural network, consider an input vector of those whose in-neighbors are not all contained
x. For some neurons v, including we additionally specify the weighted activation value future(2;, v) that they receive from the in- neighbors not contained in W. This sufficient to compute the activation values (as defined for non-partial neural networks) for all neurons in W, based assuming the values fut (zz, v). Below we will omit explicit mention of this assumption when referring to the activation values as long it is clear from the context.
W,
The dynamic programming table. Below, for a node t E V(T) in the tree decomposition we define V, to be the union of all bags of nodes that are either or descendants of t in T' The dynamic- programming table D is defined as follows. (Recall that X' is the set of input vectors.) Consider a node E (T) in the tree decomposition, function bias: X(t) + Zu assigning a bias to each neuron in t's bag, function wei sht: {(u, v) E E(G) u, v x(t) + Zs assigning a weight to each are in ('s bag, a function seen: X of pre-activation values received from neurons in V,, and a function future: X x x(t) - Bes assigning each neuron in bag a set of pre-activation values to received from neurons in V\V. We put D[t, bias, weight, seen, future] 1 if there is a V--prriill neural network G over G with the following properties, where all references to activation values are with respect to G:
x()) - ZAA assigning each neuron l's bag a set
(i) For each neuron v in x()) its bias in G is bias(v), and for each are (u,v) E B(G) with u. v E xt) the are weight in G is weight (u, v).
(ii) For each imput vector æ E X, assuming that for each neuron x(t) the pre-activation value received from in-neighbors in V(G) \ V is future(r, v), then for each neuron v E x(t) the pre-activation value received from in-neighbors in V; is seen(x, v).
(iii) For each input vector x E X, for each imput neuron in V/2 x(t) the activation value is exactly the one specified in æ.
(iv) For each input-output pair (I, y). for each output neuron E V/2 (x(t), the activation of on input x is exactly as specified in y.
If there is no such neural network G then we put Dlt, bias, weight, seen, future] = 0.
The computation of the table D) for each node of T and the running time in the appendix.
Instances with nonzero error bounds can be reduced to the E = 0 setting in order to apply Lemma 3. Theorem (+). d-QNNT is FPT wrt. the treewidth of G. the number a of input dimensions, and the number w of output dimensions.
Theorem 6 (+). d-QNNT is FPT w.r.t. the treewidth of G, the number of input dimensions, and the error bound
Finally, we show that the treewidth can be replaced by the width. If there is at least one hidden layer, then we can show that indeed the width is an upper bound for tw and Theorems 5 and 6 directly apply. Otherwise, we design two simple ad-hoc strategies that learn the neural networks optimally.
Corollary (+). d- d-QNNT FPT with respect to a + L width.
Corollary (+). d-QNNT FPT with respect to a + w + width.
5 CONCLUDING REMARKS
Our work initiates the study of fully quantized ReLU neural network training from the classical as well parameterized complexity perspectives. We show that the problem remains NP-hard even

---

in highly restricted settings, but also provide positive results through the identification of non-trivial -ardmmerreettr tractable fragments. We remark that the latter outcome contrasts the state of the art for neural network training in the non-quantized setting. Indeed, in spite of being targeted by several recent complexity-theorete studies (Dey et al., 2020; Abrahamsen et al., 2021; Goel et al., 2021; Boob et al., 2022; Froese & Hertrich, 2023; Bertschinger et al., 2023; Brand et al., 2023), to date we do not know single non-trivial" parameterization that yields fixed-parameter tractability for training non-quantized neural networks. Moreover, we believe that settling the parameterized complexity of d- d-QNNT w.r.t the input and output dimensionality (i.e., + w) will require insights beyond the current state of the art and pose this as the main open question arising from our work. Other important avenues of future work include whether our results can be extended to distillation, and whether they could be used to obtain more efficient empirical algorithms.
ACKNOWLEDGMENTS
Robert Ganian acknowledges support by the Austrian Science Fund (FWF projects 10.55776/Y1329 and 10.55776/C0E12).
Frank Sommer was supported by the Alexander von Humboldt Foundation and partially by the Carl Zeiss Foundation, Germany, within the project "Interactive Inference".
REFERENCES
Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training neural networks is er-complete. In Proceedings of the Thirty- Anmual Conference on Neural Information Processing Systems (NeurIPS '21), pp. 18293-18306. 2021. URL https: http://etcccccccccceeec/pccc.csc / 981
nwwrips...... cc/ paper/2021/ httpe//0000/aaaaa111100000000003 00010000000088000000000000000000
.html.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In Proceedings of the 6th International Conference on Learn- ing Representations (ICLR '18. OpenReview.net, 2018. URL https: http:///eeneeeeeeeeeeeeeeeeeeeep neet/
forum?id-B13
Ron Banner, Yury Nahshan, and Daniel Soudry. Post training 4-bit quantization of con- volutional networks for rapid-deployment. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), Proceedings of the 32nd Annual Conference on Neural Information Processing Sys- tems Advances in Neural Information Processing Systems (NeurIPS 2019), pp. 7948- 7956, 2019. URL (066213344ddeeeecccccccc 4088223399ccc3330315500000aaaaa.
watsscccpappeee ccc/papprr/219/haasse Abstract html.
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks is Ir-complete. In Proceed- ings of the Thirty-Seventh Anmual Conference on Neural Information Processing Systems nips. ee cc/paper saaper_filess files/pppplpe pappp/2023/////////////////233// Conferenoeeeeeeeeeeee htmll.
(NeurIPS '23), 2023. URL
Avrim Blum and Ronald L. Rivest. Training 3-node neural network is np-complete. Neural Networks, 17-):1 1992. doi: 10.1016/508971 66500899--00000030000033 URL https::t///////t //doi. hTg/100.016//008 6080 (05) 80010-3.
Digvijay Boob, Santanu S. Dey, and Guanghui Lan. Complexity of training relu neural network. Discret. Optim., 44(Par)::006200, 2022. doi: 10.1016/J. Di0......SOOO..222.0000000 100620. URL https: 10. 1tt.......oopp..o.......o..... 20....
Comelius Brand, Robert Ganian, and Mathis Rocton. New complexity fron- Proceedings of the Thirty-
tiers of tractability for neural network training. Seventh Annual Conference on Neural Information Processing Systems (NeurIPS '23), 2023. URL http:://papeet .ni.s.nips...................e.. Abstract ott.://eeeee.ccocaaaaaaaaarrttrr html.
'By non-trivial, we mean that the parameter does not simply bound the input size.
10

---

Matthieu Courbariaux, Yoshua Bengio, and Jean-Pierre David. Binaryconnect: Training deep neural networks with binary weights during propagations. In Proceedings of the Twenty- Ninth Annual Conference
Neural Information Processing Systems (NeurIPS '15), pp. 3123-3131, 2013. URL. ptttpss///rrocceednss...oo 3e (ecccclf999e22555 (ewdd2591ddfffooooe 22222
wwtpccpppppp.eeeeee html.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipezuk, and Saket Saurabh. Purameterized Algorithms. Springer, 2015. doi: 10. 10:1007997-33-11-222255 978-3-31 9- 21275-3.
URL https: /tte://///iii////oo////////ee/ //t///.....//11101.....77
Santanu S. Dey, Guanyi Wang. and Yao Xie. Approximation algorithms for training one-node relu neural networks. IEEE Trans. Signal Process., 68:6696-6706, 2020, doi: 10.1109/SP..200. 3039360. URL https::////o /tt::///ooiiie org/ 1109/ TSP 2020 3039360.
llan Doron-Arad. On the hardness of training deep neural networks discretely. In Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI '25), pp. 16363-16371. AAAIPres: 2025. doi: 10.1609/AAALVV291553333 aaai. www.11........ 33797..33797. 33797.
Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity, Texts in Computer Science. Springer, 2013, doi: org/10. 10t.10000797-11 1-777---4447--5--1111
URL https: //doi.
Vincent Froese and Christoph Hertrich. Training neural networks is np-hard in fixed dimension. In Proceedings of the Thirty-Seventh Annual Conference on Neural Information Processing Systems
(NeurIPS 23), 2023. URL
nips. cc/ seaaper_filessppppee http://ttttt7--tttttt-------e--e Abstract-Cooference htmm.
hash/ 1aaas/9848..03333555311111110110
Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness re- sults for training depth-2 relu networks. In Proceedings of the 12th Innovations in Theoreti- cal Computer Science Conference (ITCS '2/), volume 185 of LIPles, pp. 22:1-22:14. Schloss DTS.0/LIPICS..TSSS20000.
Dagstuhl Leibniz-Zentrum für Informatik, 2021. doi: https: /ww.//oiii./////// . org/10....00 4230 LII Ics. I ICS. 2021. 22.
URL
Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang. Andrew G. Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neu- ral networks for efficient integer-arithmeticonnly inference. In Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2018), pp. 2704 2713. Computer Vision Foundation IEEE Computer Society, 2018. doi: 10.1109/CVPR. 2018.00286. URL h /otptaccp////eecccssssssssssssss thecvf com Jacob Quant Jacob_Quant iiaiiinaiiiniii and Twwannnnaninnaaaaaaaaaaaaanaaaee _t_____vp_________________ Cewp_ccVc_________e_______ 2010__2211____11 html.
J. Stephen Judd. On the complexity of loading shallow neural networks. J. Complex. 4(3):177- 192. 1988. doi:
URL
1016/
1885-064X3 (88) 90019-2.
J. Stephen Judd. Neural network design and the complexity of learning. Neural network modeling and comnectionism. MIT Press, 1990. ISBN 0-262-110044
Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of symposium on the Complexity of Computer Computations, The IBM Research Symposia Series, pp. 85-103. Plenum Press, New York, 1972. doi: 10. 10.1007/978-11 1-77888---444-001-2- 99. URL https: //doi.
org/10. 1007 978 684 2001-2_9.
Kordag Mehmet Kilic, Jin Sima, and Jehoshua Bruck. On algebraic constructions of neural networks with small weights. In Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT 22), pp. 3007-3012. IEEE, 2022. doi: 2022. bttps:://dof htt.r///...10////555101110 9881556640222222.4444 9834401.
URL
Tuukka Korhonen. A ings of the 62nd IEEE Anmual Symposium Foundations of Computer Science (FOCS '27), pp- 184-192. IEEE, 2022. doi: 20.1109/F 1.0026. URL https: //ooi. org/10. 10. 1109 #109/FOCS52979, 2021 00026.
time 2-approximation algorithm for treewidth. In Proceed-

---

Zewen Li, Fan Liu, Wenjie Yang, Shouheng Peng, and Jun Zhou. A survey of convolutional neural networks: Analysis, applications, and prospects. IEEE Trans. Neural Networks Learn. Syst., 33 (12):6999-7019, 2022. doi: 10.
URL https: /tt////oiio org/10. 10.
1109/TNNISS 2021 3084827.
Xiaofan Lin, Cong Zhao, and Wei Pan. Towards accurate binary convolutional neural network. In Proceedings of the Thirthy-First Annual Conference on Neural Information Processing Systems 2017. URL battps::/ppocceedinngg neurips. cc/ccc//pp/e cc/paper/
(NeurIPS 17). Pp. F300 -tstaaaaaattttacaataaaaat.ta.at .tml.. 2017 hw77//ahh//ie haasshbllaaa 9b31
Yang Lin, Tianyu Zhang, Peiqin Sun, Zheng Li, and Shuchang Zhou. Fq-vit: Post-training quanti- zation for fully quantized vision transformer. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI '22), pp. 1173-1179 1779 ijcai.org, 2022. doi: 10.24966/UCAA22222/166 URL https: /ttp////oiii/ org/ 10. 11111..2493335 229434322222 /ttp://2aaa.22221211/22 202221644
Chunlei Liu, Wenrui Ding. Yuan Hu, Xin Xia, Baochang Zhang, Jianzhuang Liu, and David S.
Doermann. Circulant binary convolutional networks for object recognition. IEEE J. Sel. Top. Signal Process., 14(4):884-893 2020. doi: 10. N0.1109///SSSP22000229999 29..9991......166..... URL https:// doi. doi.org/110 1.../oo///............ 110111111001 109/JSTSP 2020 2969516. 6.
Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory F. Diamos, Erich Elsen, David Gareía, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, and Hao Wu. Mixed precision training. In Proceedings of the 6th International Conference on Learning Representa- tions (ICLR 2018). OpenReview.net, 2018. URL htwphttpssoccmm h /oppnrevieeeeeeeeeeeeeeeeeeeeeee net forum?id= r1gs9JJRR,
Ian Parberry. On the complexity of learning with small number of nodes. In Proceedings of the International Joint Conference on Neural Networks, volume 3, pp. 893-898, 1992.
Neil Robertson and Paul D. Seymour. Graph minors. III. planar tree-width. J. Comb. Theory B, 36 (1):49 64, 1984. doi: 11101600995-895668899900011 URLhttps://aci.orgg 1016/ 0955-8956 (84 90013-3.
Michael Schmitt. Some dichotomy theorems for neural learning problems. J. Mach. Learn. Res., 5:891-912, 2004. URL https: // ht/mmmmm.ooo/ org/ wwtggpppps//volleee wtt.///ll////l/eem wtt.:/meee//t.t///00 schmitt04a/ schmitt04a.pol pdf.
Sergey Vasil' Sevast janov. On some geometric methods in scheduling theory: A survey. Discret. Appl. Math., 55(1):59-82, 1994. doi: (00160066--188((9)9000)
URL https:
(94) 90036-1.
Ernst Steinitz. Bedingt konvergente Reihen und konvexe Systeme. Journal für die reine und ange- wandte Mathematik, 143:128-176 176,, 1913. doi:
Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel Emer. Efficient processing of deep neural networks: A tutorial and survey. Proc. IEEE, 105(12):2295-2333 2017. doi: 10.1 109/JPOC. 2017.2761740. URL https: /ttp//oii.co ort.1...111.....0 1109/ /Pw////...../C// 0017.2667740.
Ruizhe Wang, Yeyun Gong, Xiao Liu, Guoshuai Zhao, Ziyue Yang. Baining Guo, Zhengjun Zha, and Peng Cheng. Optimizing large language model training using FP4 quantization. In Proceed- ings of the Forly-Second International Conference on Machine Learning (ICML '25), Proceedings of Machine Learning Research. PMLR, 2025. URL https: https://openzeviiee wpwpr/vieneeeeeeee/e/ee net/ forum? Id-uK7JArZE. to appear.
Zhaohui Yang, Yunhe Wang. Kai Han. Chunjing Xu, Chao Xu, Dacheng Tao, and Chang Xu. Searching for low-bit weights in quantized neural networks. Proceed- ings of the Thirty-Fourth Annual Conference Neural Information Processing Systems (NeurIPS '20), 2020. URL stttp:://proceedingg wwwrineu.ec.mmm wwwp:rppps.ccppppp/2//2. TeeeseeeeTT.eeoccaaaaaaeaeeddaa www.rrabbbbbbbbbbbaaa.......ca.. Abstract.
Shuchang Zhou, Zekun Ni, Xinyu Zhou, He Wen, Yuxin Wu, and Yuheng Zou. Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients. CoRR, abs/ 1606.06160, 2016. URL http: / rxiv. wwwii.ooo//aal.o.. /rgg/as/////eeee 606. 06160.
12

---

Chenzhuo Zhu, Song Han, Huizi Mao, and William J. Dally. Trained temaay quantization. In Proceedings of the 5th International Conference on Learning Representations (ICLR '17). Open- Review.net, 2017. URL https:/ http://pnneeeeeeeeeeeooooreeaaaa
Shilin Zhu, Xin Dong, and Hao Su. Binary ensemble neural network: More bits per network or more networks per bit? In Proceedings of the IEEE Conference on Computer Vision and Computer Vision Foundation IEEE, 2019. tww.aacccssss.cc.....c..ee
Pattern Recognition (CVPR '19), pp.
doi: 11109/CCPR.2001.000006. URL httl::://ppeacceseee thecvf. com/ content_ CVPR (WPR_2019/htm1// Bttp:/hhu__niaaaeee Enseemleeeeeee... Beatmnbeeeeuuaalaeeeeeeee _ Wewtweeeetwrrtteee. Mwwewwooooo_rr_--------- Network_or M 2a1PR__219__pp00 p_pprer..ppp_. html.
Barrs_More_Bttpperrrrreee _itts_per_
13


Reviews:
[{"review_id": "4XVOadrHDQ", "reviewer": "Reviewer_VvcW", "summary": "This paper studies the fixed-parameter tractability (FPT) of training quantized neural networks (namely networks with all weights discretized to a certain grid). The basic question is as follows: given a certain neural network architecture (with ReLU activations), discretization level, and dataset, is it feasible to check whether there is a neural network (of that architecture and discretization) achieving low error on that dataset? The fixed-parameter setting is obtained when we \"fix\" certain parameters (such as depth, width, input dimension, output dimension, etc, and combinations thereof) to be bounded by $k$ and ask whether there is at least an algorithm running in time $f(k) n^{O(1)}$ for some function $f$. As there are many ways to parameterize a neural network, there are many variants of this question. This paper makes significant progress towards answering most natural variants. For example, one of the main results is that the problem is indeed FPT with respect to width + input dimension + output dimension. However, it is _not_ FPT with respect to just width + input dimension. Many other combinations are considered in the paper, and it gives a fairly comprehensive set of results detailing this complexity-theoretic landscape. It is worth noting that the landscape for the real-valued version of this problem (i.e., not quantized) is not quite as rich; the real-valued version is known to be complete for the large class $\\exists \\mathbb{R}$, whereas the quantized version necessarily lies in NP.", "questions": "1. It would be really useful to have a more detailed discussion of what makes this problem different from two closely related ones: (a) training real-valued networks, and (b) Boolean satisfiability problems (esp circuits or CSPs). It feels like this problem (training quantized neural networks) has flavors of both, and it would be good to understand exactly what techniques do and do not carry over, and where novel ideas are really needed.\n2. Probably the most common way in which quantized neural networks are actually obtained is through distillation, i.e. quantizing a higher-precision model. I am curious if the authors have thoughts about this and whether this might make the problem different. For example, consider the problem where the dataset is assumed to be realizable by a network of quantization level poly(d) (or even real-valued), and the question is to check whether there is a network of quantization level d that realizes it. Basically, trying to model the distillation setting.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Understanding the complexity of training quantized neural networks is a natural and timely theoretical question. The authors have made a commendable effort to map out the FPT landscape of this problem fairly comprehensively. The techniques in the work may be of technical interest to others in this area, especially the use of Steinitz's Lemma to enable some key simplifications. (However, note that I was not able to verify all the proofs carefully.)", "weaknesses": "My concern with this paper is that the core problem, while natural in a complexity-theoretic sense, is also quite theoretical and stylized. It is subject to all the usual criticisms of worst-case complexity theory, and as such feels unlikely to have much bearing on training quantized neural networks in practice. This is fine --- I do think the contributions are worthwhile from a complexity-theoretic point of view, and I do understand that such topics have a place in the machine learning literature. I just wonder if a better audience for this particular set of results might be found at say COLT or CCC rather than ICLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cOak3FjNMF", "reviewer": "Reviewer_hBha", "summary": "This paper studies theory for quantized neural networks, i.e., whose weights are stricted to be integers.\nThey show various hardness results for the problem of determining whether there exists weights that achieves performance better than some threshold.\nThey also show tractability in terms of the tree-width of the underlying graph of a neural network architecture.", "questions": "I don't understand the sentence on Line 468-469. How does the tree width becomes replaced with (ordinary) width?\n\nAs ell becomes larger, the problem should become easier. Is this correct? I'm not understanding how ell is used alongside with other parameters like the width which makes the problem harder when the width grows larger.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "They consider feed-forward neural net architectures that is not just the fully-connected nets. rather, they allow \"sparser\" connections.\nFor many of the hardness results, simple architectures (i.e., low depth) already already lead to hard problems.\nDiscovery of tree-width and connection to tractability for QNNs is also interesting.", "weaknesses": "There isn't a lot of intuition for why small tree-width neural networks. what do those graphs look like? It'd be useful if there is more small scale examples e.g., like the one from Figure 4, but for small tree-width architectures.\n\nSince small tree-width architectures are tractable, it'd be nice to see some experiments on say the two-moon dataset. this will help answer: are small tree-width neural networks useful?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2lkysOqTUC", "reviewer": "Reviewer_D5xX", "summary": "This paper provides a foundational study of the computational and parameterized complexity of quantized neural network training (QNNT). They prove that training remains NP-hard in general but identify tractable cases when parameterized by input dimension combined with width, error bound, or treewidth. Central to their approach is a structural lemma derived from Steinitz’ Lemma, which limits the number of relevant input connections per neuron, enabling dynamic programming–based fixed-parameter tractable algorithms.", "questions": "- To what extent can the results in this paper be leveraged for actual algorithmic design in quantized training?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This is the first rigorous parameterized complexity analysis of quantized neural network training.\n\n- The authors establish NP-hardness and W[2]-hardness for even extremely constrained architectures (binary weights, single hidden layer), demonstrating the robustness of the hardness landscape.\n\n- It bridges machine learning and complexity theory, setting a precedent for similar analyses in quantized deep learning settings.", "weaknesses": "- The connection to practical quantized training algorithms such as quantization-aware training (QAT), could be discussed more deeply. The current presentation is fully theoretical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)