The Complexity of ReLU Network Synthesis from a Parameter Multiset
Organizations: GREAT BAY UNIVERSITY, CHINA
Abstract
We ask how hard it is to build a ReLU network when its parameter values are given in advance. An instance supplies an appropriate encoding of a target behavior, a multiset of rational numbers, 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. Matching two labeled examples exactly is already -complete, so 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 -complete, already for four neurons. Agreeing with a given ReLU network on every real input lies in for every fixed neuron bound and is -complete for three neurons. Approximating a ReLU network on the unit cube within absolute error one everywhere is -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 -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.
Figures & tables
| Specification | Guarantee |
|---|---|
| Two explicit samples | -complete with positive integer inventory and cap one ( Theorem 3.3 ). |
| Boolean-circuit equality | -complete with cap four, even for monotone threshold targets ( Theorem 4.12 ). |
| Full-space ReLU equality | In for every fixed cap; cap three is -complete; cap two is -complete under at-most-once use ( Theorems 5.4 , 5.9 and 5.3 ). |
| Exact Boolean squared risk | -complete: integer inventory, cap two for at-most-once use, cap for exactly-once use ( Theorem 7.1 ). |
| Uniform approximation on a box | -complete with cap one and identical positive inventory values ( Theorem 6.2 ). |
| Exact continuous uniform squared risk | Complete for the discrete existential closure of exact rational weighted counting; integer-inventory cap-two hardness under both inventory rules ( Theorem 8.8 ). |
ReLU Neural Networks
Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.
See all 136 papers