The Complexity of ReLU Network Synthesis from a Parameter Multiset

Abstract:We ask how hard it is to build a neural network when its parameter values are given in advance. An instance supplies a multiset of rational numbers, a target behavior, and a bound on the number of neurons, output included. The question is whether one can choose the graph of a ReLU network within the bound, and place the numbers on its edges and biases so that it meets the target. This separates the numbers from the architecture; permutation training instead fixes the hidden units and only rearranges the output weights. Matching two labeled examples exactly is already $\mathsf{NP}$-complete; we ask what changes when the target must hold on every input or on average. Agreeing with a Boolean circuit on every Boolean input is $\Sigma_2^{\mathsf P}$-complete, already for four neurons. Agreeing with a given ReLU network on every real input lies in $\mathsf{DP}$ for every fixed neuron bound and is $\mathsf{DP}$-complete for three neurons. Approximating a ReLU network on the unit cube within absolute error one everywhere is $\Sigma_2^{\mathsf P}$-complete, even with no hidden neurons and all numbers equal and positive. Deciding whether some network has expected squared loss at most a threshold is $\mathsf{NP}^{\mathsf{PP}}$-complete for uniform Boolean inputs. For uniform inputs on the unit cube and for standard Gaussian inputs with a positive threshold, the same holds for two neurons when a positive risk gap, given in binary and possibly exponentially small, separates yes from no instances. Without a gap, the cube version is complete for guessing a polynomial-length string, then comparing a sum of exponentially many rationals with a threshold, all computable in polynomial time from the input and the guess. Since the graph is chosen too, the reductions must rule out every other network built from the same numbers.

Computational Complexity (cs.CC); Machine Learning (cs.LG)

arXiv:2611.04074 [cs.CC]

(or arXiv:2611.04074v1 [cs.CC] for this version)

https://doi.org/10.48550/arXiv.2611.04074 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.