# On the tightness of linear relaxation based robustness certification methods

arXiv: https://arxiv.org/abs/2210.00178 · HTML: https://mlsanity.com/paper/2210.00178/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 21 references that are in the map.
- First posted on arXiv 1 Oct 2022.

## Builds on (most cited first, 18 of 18)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Achieving Verified Robustness to Symbol Substitutions via Interval Bound Propagation](https://mlsanity.com/paper/1909.01492/) (2019)
- [CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networks](https://mlsanity.com/paper/1811.12395/) (2018)
- [The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification](https://mlsanity.com/paper/2006.14076/) (2020)
- [Towards Proving the Adversarial Robustness of Deep Neural Networks](https://mlsanity.com/paper/1709.02802/) (2017)
- [Evaluating Robustness of Neural Networks with Mixed Integer Programming](https://mlsanity.com/paper/1711.07356/) (2017)
- [On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples](https://mlsanity.com/paper/2006.06759/) (2020)

## Abstract (arXiv)

There has been a rapid development and interest in adversarial training and defenses in the machine learning community in the recent years. One line of research focuses on improving the performance and efficiency of adversarial robustness certificates for neural networks citegowal:19, wongzico:18, raghunathan:18, WengTowardsFC:18, wong:scalable:18, singh:convexbarrier:19, Huangetal:19, single-neuron-relax:20, Zhang2020TowardsSA. While each providing a certification to lower (or upper) bound the true distortion under adversarial attacks via relaxation, less studied was the tightness of relaxation. In this paper, we analyze a family of linear outer approximation based certificate methods via a meta algorithm, IBP-Lin. The aforementioned works often lack quantitative analysis to answer questions such as how does the performance of the certificate method depend on the network configuration and the choice of approximation parameters. Under our framework, we make a first attempt at answering these questions, which reveals that the tightness of linear approximation based certification can depend heavily on the configuration of the trained networks.