Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions

Abstract:Ganian et al. (ICLR 2026) proved that quantized neural network training is fixed-parameter tractable when parameterized jointly by architecture treewidth, input dimension $\alpha$, and output dimension $\omega$, and left open whether $\alpha+\omega$ alone yields fixed-parameter tractability. We prove that 2-QNNT is W[1]-hard parameterized by $\alpha+\omega$. The hardness already holds with zero error on $D_k=\{(\xi^{(r)},\xi^{(r)}):0\le r\le k\}$, where every input equals its target, $|D_k|=\alpha=\omega=k+1$, and the examples form a coordinatewise prefix chain. It also holds when every non-source bias is fixed to zero. Under the Exponential Time Hypothesis, no algorithm runs in $f(\alpha+\omega)|I|^{o(\alpha+\omega)}$ for any computable $f$. The reduction starts from DAG edge-disjoint paths, converts edge capacity to vertex capacity with a directed line graph, and normalizes the result into a valid layered architecture. The key structural step is a one-flip routing equivalence: on the prefix-chain inputs, nonnegative binary weights make every activation monotone, and each required output transition has a weight-one predecessor making the same transition. Iterating this relation backward extracts a path from the unique changing input, while different transitions yield vertex-disjoint paths. In particular, every neuron on these inputs has only $k+1$ possible activation profiles.

Machine Learning (cs.LG)

arXiv:2609.27932 [cs.LG]

(or arXiv:2609.27932v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.27932 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.