Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 33 of its 49 references that are in the map. First posted on arXiv 9 Oct 2024.
Builds on
33 of 49 references.
References · 33
- 2013Intriguing properties of neural networkscited by 5,155
- 2016Towards Evaluating the Robustness of Neural Networkscited by 2,998
- 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,340
- 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
- 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 567
- 2020On Adaptive Attacks to Adversarial Example Defensescited by 555
- 2018Certified Robustness to Adversarial Examples with Differential Privacycited by 468
- 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 445
- 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 328
- 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
- 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 255
- 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 187
21 more
- 2018Scaling provable adversarial defensescited by 143
- 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
- 2022(Certified!!) Adversarial Robustness for Free!cited by 132
- 2019A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networkscited by 125
- 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
- 2022General Cutting Planes for Bound-Propagation-Based Neural Network Verificationcited by 103
- 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
- 2021PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximationscited by 77
- 2022Certified Training: Small Boxes are All You Needcited by 52
- 2020The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verificationcited by 50
- 2024Neural Network Verification with Branch-and-Bound for General Nonlinearitiescited by 47
- 2021Fast Certified Robust Training with Short Warmupcited by 46
- 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
- 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
- 2023Understanding Certified Training with Interval Bound Propagationcited by 26
- 2023Expressive Losses for Verified Robustness via Convex Combinationscited by 23
- 2020Interval Universal Approximation for Neural Networkscited by 14
- 2024CTBENCH: A Library and Benchmark for Certified Trainingcited by 14
- 2019Universal Approximation with Certified Networkscited by 9
- 2023Expressivity of ReLU-Networks under Convex Relaxationscited by 8
- 2024Gaussian Loss Smoothing Enables Certified Training with Tight Convex Relaxationscited by 4
Built on by
Citing papers per year: 2025: 2.
2 papers.