# Tightened Convex Relaxations for Neural Network Robustness Certification

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2020.

## Built on by (most cited first, 14 of 14)

- [How to Certify Machine Learning Based Safety-critical Systems? A Systematic Literature Review](https://mlsanity.com/paper/2107.12045/) (2021)
- [Improving the Accuracy-Robustness Trade-Off of Classifiers via Adaptive Smoothing](https://mlsanity.com/paper/2301.12554/) (2023)
- [Efficient Global Optimization of Two-Layer ReLU Networks: Quadratic-Time Algorithms and Adversarial Training](https://mlsanity.com/paper/2201.01965/) (2022)
- [Neural Network Verification in Control](https://mlsanity.com/paper/2110.01388/) (2021)
- [Projected Randomized Smoothing for Certified Adversarial Robustness](https://mlsanity.com/paper/2309.13794/) (2023)
- [Asymmetric Certified Robustness via Feature-Convex Neural Networks](https://mlsanity.com/paper/2302.01961/) (2023)
- [Practical Convex Formulation of Robust One-hidden-layer Neural Network Training](https://mlsanity.com/paper/2105.12237/) (2021)
- [Provable Bounds on the Hessian of Neural Networks: Derivative-Preserving Reachability Analysis](https://mlsanity.com/paper/2406.04476/) (2024)
- [Fast and Reliable N-k Contingency Screening with Input-Convex Neural Networks](https://mlsanity.com/paper/2410.00796/) (2024)
- [Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification](https://mlsanity.com/paper/2101.09306/) (2021)
- [Neural Network Verification as Piecewise Linear Optimization: Formulations for the Composition of Staircase Functions](https://mlsanity.com/paper/2211.14706/) (2022)
- [Tight Certified Robustness via Min-Max Representations of ReLU Neural Networks](https://mlsanity.com/paper/2310.04916/) (2023)
- [Mixing Classifiers to Alleviate the Accuracy-Robustness Trade-Off](https://mlsanity.com/paper/2311.15165/) (2023)
- [An Overview and Prospective Outlook on Robust Training and Certification of Machine Learning Models](https://mlsanity.com/paper/2208.07464/) (2022)

## Abstract (arXiv)

In this paper, we consider the problem of certifying the robustness of neural networks to perturbed and adversarial input data. Such certification is imperative for the application of neural networks in safety-critical decision-making and control systems. Certification techniques using convex optimization have been proposed, but they often suffer from relaxation errors that void the certificate. Our work exploits the structure of ReLU networks to improve relaxation errors through a novel partition-based certification procedure. The proposed method is proven to tighten existing linear programming relaxations, and asymptotically achieves zero relaxation error as the partition is made finer. We develop a finite partition that attains zero relaxation error and use the result to derive a tractable partitioning scheme that minimizes the worst-case relaxation error. Experiments using real data show that the partitioning procedure is able to issue robustness certificates in cases where prior methods fail. Consequently, partition-based certification procedures are found to provide an intuitive, effective, and theoretically justified method for tightening existing convex relaxation techniques.