arXiv:2609.27932 · v2
Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions
摘要
When the weights and biases of a neural network range over a fixed finite alphabet, training the network to fit a data set exactly becomes a finite combinatorial problem, and parameterized complexity asks which structural quantities of an instance make this problem tractable. Ganian, Sommer, and Sorge (ICLR 2026) showed that training quantized networks is fixed-parameter tractable when parameterized jointly by the input dimension $α$, the output dimension $ω$, and the treewidth of the architecture, and they asked whether $α+ω$ alone suffices. We show that it does not: training binary quantized networks is W[1]-hard parameterized by $α+ω$, so it admits no algorithm with running time $f(α+ω)\cdot|I|^{O(1)}$ for any computable $f$ unless FPT = W[1]. Hardness holds already for exact fitting of $k+1$ examples whose inputs equal their targets and form a coordinatewise prefix chain, and also when all biases are fixed to zero. The proof rests on a one-flip routing equivalence. On such data, nonnegative binary weights force every neuron to switch on at most once, and a network fits the data exactly if and only if the architecture contains vertex-disjoint paths that link each changing input to the corresponding output. Every neuron therefore has one of only $k+1$ activation profiles, yet deciding whether these profiles can be realized simultaneously is as hard as disjoint-path routing. Small input and output dimensions thus limit what each neuron can do locally, but not how the architecture forces neurons to share resources globally.
作者备注：17 pages, 1 figure, 2 tables. v2: rewritten with complete proofs; ETH-conditional running-time bounds removed after the refutation of ETH; the main W[1]-hardness result is unchanged