# Limitations of Piecewise Linearity for Efficient Robustness Certification

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 35 references that are in the map.
- First posted on arXiv 21 Jan 2023.

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

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Randomized Smoothing of All Shapes and Sizes](https://mlsanity.com/paper/2002.08118/) (2020)
- [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)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Orthogonalizing Convolutional Layers with the Cayley Transform](https://mlsanity.com/paper/2104.07167/) (2021)
- [Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks](https://mlsanity.com/paper/1911.00937/) (2019)
- [Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability](https://mlsanity.com/paper/1809.03008/) (2018)
- [Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds](https://mlsanity.com/paper/2111.01395/) (2021)
- [Provable Robustness of ReLU networks via Maximization of Linear Regions](https://mlsanity.com/paper/1810.07481/) (2018)
- [Limitations of the Lipschitz constant as a defense against adversarial examples](https://mlsanity.com/paper/1807.09705/) (2018)
- [Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100](https://mlsanity.com/paper/2108.04062/) (2021)
- [Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes](https://mlsanity.com/paper/1903.08778/) (2019)
- [Fast Geometric Projections for Local Robustness Certification](https://mlsanity.com/paper/2002.04742/) (2020)
- [Relaxing Local Robustness](https://mlsanity.com/paper/2106.06624/) (2021)

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

- [Unlocking Deterministic Robustness Certification on ImageNet](https://mlsanity.com/paper/2301.12549/) (2023)
- [A Recipe for Improved Certifiable Robustness](https://mlsanity.com/paper/2310.02513/) (2023)
- [Is Certifying ℓp Robustness Still Worthwhile?](https://mlsanity.com/paper/2310.09361/) (2023)
- [1-Lipschitz Neural Networks are more expressive with N-Activations](https://mlsanity.com/paper/2311.06103/) (2023)

## Abstract (arXiv)

Certified defenses against small-norm adversarial examples have received growing attention in recent years; though certified accuracies of state-of-the-art methods remain far below their non-robust counterparts, despite the fact that benchmark datasets have been shown to be well-separated at far larger radii than the literature generally attempts to certify. In this work, we offer insights that identify potential factors in this performance gap. Specifically, our analysis reveals that piecewise linearity imposes fundamental limitations on the tightness of leading certification techniques. These limitations are felt in practical terms as a greater need for capacity in models hoped to be certified efficiently. Moreover, this is in addition to the capacity necessary to learn a robust boundary, studied in prior work. However, we argue that addressing the limitations of piecewise linearity through scaling up model capacity may give rise to potential difficulties -- particularly regarding robust generalization -- therefore, we conclude by suggesting that developing smooth activation functions may be the way forward for advancing the performance of certified neural networks.