cs.LGOct 9, 2024

Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification

Authors: Yuhao Mao, Yani Zhang, Martin Vechev

Organizations: †Department of Computer Science ETH Zürich, Switzerland · ‡Department of Information Technology and Electrical Engineering ETH Zürich, Switzerland

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: Triangle relaxation of a ReLU with input x∈[−1,1]x\in[-1,1] .
Figure 2: Blue area shows how the input box transforms under W1W_{1} and ReLU; shaded area is the feasible set computed by P1{\mathcal{P}}_{1} .
Figure 3: A network encoding f=max⁡(x1,x2)f=\max(x_{1},x_{2}) .
Figure 4: A partition of the input set where every part remains as a convex polytope through the layers.
Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Visualization of the single-neuron and multi-neuron relaxations for a network encoding f(x)=0f(x)=0 .
Figure 6: One coordinate of the clipping subnetwork realizing ci(y)=mi+ρ(yi−mi)−ρ(yi−ni){\bm{c}}_{i}({\bm{y}})={\bm{m}}_{i}+\rho({\bm{y}}_{i}-{\bm{m}}_{i})-\rho({\bm{y}}_{i}-{\bm{n}}_{i}) .
More in this topic

Neural Network Verification

Neural network verification develops methods to prove whether networks satisfy properties such as robustness, safety, and bounded output behavior.

See all 131 papers

Explore similar work

CardsList

  1. The Cost of Relaxation: Evaluating the Error in Convex Neural Network Verification

    Apr 20, 2026Merkouris Papamichail, Konstantinos Varsos, Giorgos Flouris +1Neural Network VerificationCertified Robustness

    Foundation for Research and Technology – Hellas, Heraklion, Greece · University of Crete, Heraklion, Greece · Catalan Institution for Research and Advanced Studies, Barcelona, Spain +1

  2. Neural Network Verification using Partial Multi-Neuron Relaxation

    May 28, 2026Ido Shmuel, Guy KatzNeural Network Verification

    The Hebrew University of Jerusalem, Jerusalem, Israel

  3. Certified Robustness via Sparse Second-Order Cone Relaxations

    Oct 12, 2026Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma +3Convex RelaxationSecond-Order Cone Programming

    Toronto Metropolitan University · University of Minnesota Twin Cities · Johns Hopkins University +2