Complexity of Deciding Injectivity and Surjectivity of ReLU Neural Networks
<|reference_start|>Complexity of Deciding Injectivity and Surjectivity of ReLU Neural Networks: Neural networks with ReLU activation play a key role in modern machine learning. In view of safety-critical applications, the verification of trained networks is of great importance and necessitates a thorough understanding of essential properties of the function computed by a ReLU network, including characteristics like injectivity and surjectivity. Recently, Puthawala et al. [JMLR 2022] came up with a characterization for injectivity of a ReLU layer, which implies an exponential time algorithm. However, the exact computational complexity of deciding injectivity remained open. We answer this question by proving coNP-completeness of deciding injectivity of a ReLU layer. On the positive side, as our main result, we present a parameterized algorithm which yields fixed-parameter tractability of the problem with respect to the input dimension. In addition, we also characterize surjectivity for two-layer ReLU networks with one-dimensional output. Remarkably, the decision problem turns out to be the complement of a basic network verification task. We prove NP-hardness for surjectivity, implying a stronger hardness result than previously known for the network verification problem. Finally, we reveal interesting connections to computational convexity by formulating the surjectivity problem as a zonotope containment problem<|reference_end|>
@article{froese2024complexity,
    title={Complexity of Deciding Injectivity and Surjectivity of ReLU Neural
  Networks},
    author={Vincent Froese, Moritz Grillo and Martin Skutella},
    journal={arXiv preprint arXiv:2405.19805},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.19805},
    primaryClass={cs.CC cs.DM cs.LG}
}