# Provable Robustness of ReLU networks via Maximization of Linear Regions

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2018.

## Built on by (most cited first, 30 of 51)

- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [On the Adversarial Robustness of Vision Transformers](https://mlsanity.com/paper/2103.15670/) (2021)
- [Skew Orthogonal Convolutions](https://mlsanity.com/paper/2105.11417/) (2021)
- [Relating Adversarially Robust Generalization to Flat Minima](https://mlsanity.com/paper/2104.04448/) (2021)
- [Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective](https://mlsanity.com/paper/2210.01787/) (2022)
- [SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2111.09277/) (2021)
- [Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100](https://mlsanity.com/paper/2108.04062/) (2021)
- [How to Certify Machine Learning Based Safety-critical Systems? A Systematic Literature Review](https://mlsanity.com/paper/2107.12045/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Consistent Counterfactuals for Deep Models](https://mlsanity.com/paper/2110.03109/) (2021)
- [Exploring and Exploiting Decision Boundary Dynamics for Adversarial Robustness](https://mlsanity.com/paper/2302.03015/) (2023)
- [Boosting the Certified Robustness of L-infinity Distance Nets](https://mlsanity.com/paper/2110.06850/) (2021)
- [Robust Models Are More Interpretable Because Attributions Look Normal](https://mlsanity.com/paper/2103.11257/) (2021)
- [Adversarial Robustness via Fisher-Rao Regularization](https://mlsanity.com/paper/2106.06685/) (2021)
- [How and When Adversarial Robustness Transfers in Knowledge Distillation?](https://mlsanity.com/paper/2110.12072/) (2021)
- [Towards Evaluating the Robustness of Deep Diagnostic Models by Adversarial Attack](https://mlsanity.com/paper/2103.03438/) (2021)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verification](https://mlsanity.com/paper/2111.08922/) (2021)
- [Unlocking Deterministic Robustness Certification on ImageNet](https://mlsanity.com/paper/2301.12549/) (2023)
- [Adversarial Attacks on Traffic Sign Recognition: A Survey](https://mlsanity.com/paper/2307.08278/) (2023)
- [FairProof : Confidential and Certifiable Fairness for Neural Networks](https://mlsanity.com/paper/2402.12572/) (2024)
- [Deep Contract Design via Discontinuous Networks](https://mlsanity.com/paper/2307.02318/) (2023)
- [Connections between Numerical Algorithms for PDEs and Neural Networks](https://mlsanity.com/paper/2107.14742/) (2021)
- [Improved techniques for deterministic l2 robustness](https://mlsanity.com/paper/2211.08453/) (2022)
- [Towards Robust Dataset Learning](https://mlsanity.com/paper/2211.10752/) (2022)
- [Confidence-aware Training of Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2212.09000/) (2022)
- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (2024)
- [On the Local Complexity of Linear Regions in Deep ReLU Networks](https://mlsanity.com/paper/2412.18283/) (2024)
- [Recent Advances in Large Margin Learning](https://mlsanity.com/paper/2103.13598/) (2021)
- [Understanding and Accelerating Neural Architecture Search with Training-Free and Theory-Grounded Metrics](https://mlsanity.com/paper/2108.11939/) (2021)

## Abstract (arXiv)

It has been shown that neural network classifiers are not robust. This raises concerns about their usage in safety-critical systems. We propose in this paper a regularization scheme for ReLU networks which provably improves the robustness of the classifier by maximizing the linear regions of the classifier as well as the distance to the decision boundary. Our techniques allow even to find the minimal adversarial perturbation for a fraction of test points for large networks. In the experiments we show that our approach improves upon adversarial training both in terms of lower and upper bounds on the robustness and is comparable or better than the state-of-the-art in terms of test error and robustness.