← All papers
First page of Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification

Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification

Yuhao Mao, Yani Zhang, Martin Vechev

cs.LG Oct 9, 2024 · v5 cs.AI
All theoretical results and proofs on multi-neuron convex relaxations are formalized in Lean using the Paper Formalizer tool, with a public repository.
Neural network certification methods heavily rely on convex relaxations to provide robustness guarantees. However, these relaxations are often imprecise: even the most accurate single-neuron relaxation is incomplete for general ReLU networks, a limitation known as the *single-neuron convex barrier*. While multi-neuron relaxations have been heuristically applied to address this issue, two central questions arise: (i) whether they overcome the convex barrier, and if not, (ii) whether they offer theoretical capabilities beyond those of single-neuron relaxations. In this work, we present the first rigorous analysis of the expressiveness of multi-neuron relaxations. Perhaps surprisingly, we show that they are inherently incomplete, even when allocated sufficient resources to capture finitely many neurons and layers optimally. This result extends the single-neuron barrier to a *universal convex barrier* for neural network certification. On the positive side, we show that completeness can be achieved by either (i) augmenting the network with a polynomial number of carefully designed ReLU neurons or (ii) partitioning the input domain into convex sub-polytopes, thereby distinguishing multi-neuron relaxations from single-neuron ones which are unable to realize the former and have worse partition complexity for the latter. Our findings establish a foundation for multi-neuron relaxations and point to new directions for certified robustness, including training methods tailored to multi-neuron relaxations and verification methods with multi-neuron relaxations as the main subroutine.

Neural network certification relies on convex relaxations, and single-neuron relaxations are known to be incomplete for ReLU networks (the single-neuron convex barrier). It was open whether multi-neuron relaxations overcome this barrier, or whether they offer any provable advantage over single-neuron ones.

The authors analyze layerwise and cross-layer multi-neuron relaxations P_r. Incompleteness is shown by constructing networks whose intermediate image has a strictly larger convex hull. A pumping-style argument inserts dummy identity layers to defeat cross-layer relaxations. Positive results come from equivalence-preserving network transformations (clipping subnetworks) and convex polytope input partitions. All results are formalized in Lean via Paper Formalizer.

No multi-neuron relaxation with finite resources is complete, and its bounding error can be arbitrarily large; this extends the single-neuron barrier to a universal convex barrier. Completeness can be recovered by adding a polynomial number of ReLU neurons or by partitioning the input domain. Single-neuron relaxations cannot realize the first remedy and need more partitions for the second.