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

arXiv:2609.27932v1 Announce Type: new 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)}):0le rle 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.

Source: arXiv cs.LG | 2026-09-24