Metraipolis › archive › dc_e77e3129fa56

The Complexity of ReLU Network Synthesis from a Parameter Multiset — arXiv:2611.04074

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.04074
License (as archived)
CC0-1.0
Archived
2026-11-04T12:41:24.933Z
SHA-256 of the archived text
ac00c7eba0933d8508bf1423a8c721631bd74a47133918e567023f48014faa49
Stable URL of this page
https://metraipolis.com/documento/dc_e77e3129fa56

How to cite

The Complexity of ReLU Network Synthesis from a Parameter Multiset — arXiv:2611.04074 — arXiv (en), https://arxiv.org/abs/2611.04074 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e77e3129fa56 (Metraipolis archive dc_e77e3129fa56, sha256 ac00c7eba0933d8508bf1423a8c721631bd74a47133918e567023f48014faa49)
BibTeX
@misc{dce77e3129fa56,
  title = {The Complexity of ReLU Network Synthesis from a Parameter Multiset — arXiv:2611.04074},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04074},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e77e3129fa56; sha256 ac00c7eba0933d8508bf1423a8c721631bd74a47133918e567023f48014faa49},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04074. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.04074 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T12:29:47.376Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).