OpenNovelty.org

Tractability via Low Dimensionality: The Parameterized Complexity of Training Quantized Neural Networks

ICLR 2026 Conference SubmissionAnonymous Authors
OpenReview Score: 6.7Download Report PDF
treewidthparameterized complexityquantized neural networksReLU networks
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.

Disclaimer
This report is AI-GENERATED using Large Language Models and WisPaper (A scholar search engine). It analyzes academic papers' tasks and contributions against retrieved prior work. While this system identifies POTENTIAL overlaps and novel directions, ITS COVERAGE IS NOT EXHAUSTIVE AND JUDGMENTS ARE APPROXIMATE. These results are intended to assist human reviewers and SHOULD NOT be relied upon as a definitive verdict on novelty.
NOTE that some papers exist in multiple, slightly different versions (e.g., with different titles or URLs). The system may retrieve several versions of the same underlying work. The current automated pipeline does not reliably align or distinguish these cases, so human reviewers will need to disambiguate them manually.
If you have any questions, please contact: mingzhang23@m.fudan.edu.cn

Overview

Overall Novelty Assessment

The paper establishes parameterized complexity results for training quantized ReLU networks, contributing both hardness and tractability findings. It resides in the Parameterized Complexity Analysis leaf under Complexity-Theoretic Foundations, where it is currently the sole paper in that specific leaf. This positioning reflects a relatively sparse research direction: while the broader taxonomy encompasses eight papers across multiple branches, the parameterized complexity perspective on quantized training remains underexplored. The taxonomy reveals that most related work either addresses general computational hardness without parameterization or focuses on algorithmic and hardware-oriented methods rather than fine-grained complexity analysis.

The taxonomy structure shows that neighboring work divides into three main branches. Complexity-Theoretic Foundations contains sibling leaves on General Computational Hardness and Discrete Neural Network Theory, which establish fundamental intractability results and theoretical properties of discrete networks but do not employ parameterized analysis. Algorithm Design and Training Methods develops practical low-precision training strategies and gradient estimation techniques, explicitly excluding complexity-theoretic analysis. Hardware-Oriented Inference Optimization targets deployment efficiency rather than training complexity. The paper's focus on parameterized tractability via structural parameters like treewidth and dimensionality distinguishes it from these neighboring directions, which either lack parameterization or emphasize empirical performance over theoretical boundaries.

Among the 22 candidates examined, the contribution on fixed-parameter tractability via input dimensionality combined with width and output/error parameters shows one refutable candidate out of ten examined, suggesting some overlap with prior parameterized approaches. The other two contributions—strong lower bounds for quantized training and tractability results using treewidth—each examined ten and two candidates respectively, with no clear refutations found. The limited search scope means these statistics reflect top semantic matches rather than exhaustive coverage. The lower bounds contribution appears more novel within this sample, while the dimensionality-based tractability result encounters at least one overlapping prior work among the candidates reviewed.

Given the limited search of 22 candidates and the sparse population of the Parameterized Complexity Analysis leaf, the paper appears to occupy a relatively underexplored niche. The taxonomy context suggests that while quantized network training has received attention from algorithmic and hardware perspectives, the systematic parameterized complexity treatment remains less developed. The analysis captures top semantic matches but does not claim exhaustive field coverage, leaving open the possibility of additional related work outside the examined candidate set.

Taxonomy

Core-task Taxonomy Papers
8
3
Claimed Contributions
22
Contribution Candidate Papers Compared
1
Refutable Paper

Research Landscape Overview

Core task: parameterized complexity of training quantized neural networks. The field structure suggested by the taxonomy divides into three main branches. Complexity-Theoretic Foundations investigates the fundamental computational hardness of training networks with discrete or low-precision parameters, often drawing on classical complexity theory and parameterized analysis to identify which problem features make training tractable or intractable. Algorithm Design and Training Methods focuses on practical techniques—such as gradient approximation schemes, progressive quantization strategies, and specialized optimizers—that enable effective learning despite discrete constraints. Hardware-Oriented Inference Optimization emphasizes deployment considerations, exploring ultra-low precision representations and efficient inference architectures that exploit quantization for speed and energy savings. Early theoretical work like Complexity Discrete Neurocomputing[6] and Discrete Mathematics Neural Networks[7] laid groundwork by characterizing discrete neural computation, while more recent efforts such as Hardness Training Deep Discretely[1] and High Accuracy Low Precision[2] bridge theory and practice by analyzing training difficulty and demonstrating that carefully designed low-bit schemes can preserve accuracy. Particularly active lines of work contrast algorithmic innovation with rigorous complexity analysis. On one hand, methods like Progressive Low Precision Networks[8] and Wrapnet Ultra Low Precision[4] push the envelope of how few bits suffice for competitive performance, often relying on heuristic training tricks and empirical validation. On the other hand, studies such as Bias Variance Binary Gradients[5] and Hardness Training Deep Discretely[1] probe the statistical and computational trade-offs inherent in discrete optimization, revealing when and why quantized training becomes hard. The original paper, Tractability via Low Dimensionality[0], sits squarely within the Complexity-Theoretic Foundations branch, offering a parameterized lens that identifies low-dimensional structure as a key to tractability. Compared to Hardness Training Deep Discretely[1], which emphasizes worst-case intractability, Tractability via Low Dimensionality[0] highlights positive algorithmic results under restricted parameterizations, thereby complementing the broader landscape of hardness and approximation results in quantized network training.

Claimed Contributions

Strong lower bounds for quantized ReLU neural network training

The authors prove that training quantized ReLU neural networks remains NP-hard even in the binary (2-bit) case and under severe restrictions including constant depth, constant width, single output neurons, and zero error bounds. These results exclude fixed-parameter tractability for standard architectural parameters like depth and width.

2 retrieved papers
Fixed-parameter tractability via input dimensionality combined with width and output/error parameters

The authors develop algorithms showing that quantized neural network training becomes fixed-parameter tractable when parameterized by the input dimensionality combined with network width and either the output dimensionality or the error bound. These are the first non-trivial tractable parameterizations for this problem.

10 retrieved papers
Can Refute
Strengthened tractability results using treewidth instead of width

The authors prove that their fixed-parameter tractability results can be strengthened by replacing the width parameter with treewidth, a more general graph-theoretic measure. This is achieved through a structural insight (Lemma 1) bounding the non-zero indegree of neurons in solutions, enabling dynamic programming over tree decompositions.

10 retrieved papers

Core Task Comparisons

Comparisons with papers in the same taxonomy category

Within the taxonomy built over the current TopK core-task papers, the original paper is assigned to a leaf with no direct siblings and no cousin branches under the same grandparent topic. In this retrieved landscape, it appears structurally isolated, which is one partial signal of novelty, but still constrained by search coverage and taxonomy granularity.

Contribution Analysis

Detailed comparisons for each claimed contribution

Contribution

Strong lower bounds for quantized ReLU neural network training

The authors prove that training quantized ReLU neural networks remains NP-hard even in the binary (2-bit) case and under severe restrictions including constant depth, constant width, single output neurons, and zero error bounds. These results exclude fixed-parameter tractability for standard architectural parameters like depth and width.

Contribution

Fixed-parameter tractability via input dimensionality combined with width and output/error parameters

The authors develop algorithms showing that quantized neural network training becomes fixed-parameter tractable when parameterized by the input dimensionality combined with network width and either the output dimensionality or the error bound. These are the first non-trivial tractable parameterizations for this problem.

Contribution

Strengthened tractability results using treewidth instead of width

The authors prove that their fixed-parameter tractability results can be strengthened by replacing the width parameter with treewidth, a more general graph-theoretic measure. This is achieved through a structural insight (Lemma 1) bounding the non-zero indegree of neurons in solutions, enabling dynamic programming over tree decompositions.

Table of Contents