# Relaxing Local Robustness

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 34 references that are in the map.
- First posted on arXiv 11 Jun 2021.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Adversarial examples in the physical world](https://mlsanity.com/paper/1607.02533/) (2016)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [The Limitations of Deep Learning in Adversarial Settings](https://mlsanity.com/paper/1511.07528/) (2015)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Adversarial Patch](https://mlsanity.com/paper/1712.09665/) (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)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [Adversarial Training and Robustness for Multiple Perturbations](https://mlsanity.com/paper/1904.13000/) (2019)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Exploring the Landscape of Spatial Robustness](https://mlsanity.com/paper/1712.02779/) (2017)
- [Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability](https://mlsanity.com/paper/1809.03008/) (2018)
- [Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing](https://mlsanity.com/paper/1912.09899/) (2019)
- [Provable Robustness of ReLU networks via Maximization of Linear Regions](https://mlsanity.com/paper/1810.07481/) (2018)
- [Smooth Loss Functions for Deep Top-k Classification](https://mlsanity.com/paper/1802.07595/) (2018)
- [Provable robustness against all adversarial lp-perturbations for p≥ 1](https://mlsanity.com/paper/1905.11213/) (2019)
- [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)

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

- [Unlocking Deterministic Robustness Certification on ImageNet](https://mlsanity.com/paper/2301.12549/) (2023)
- [Improved techniques for deterministic l2 robustness](https://mlsanity.com/paper/2211.08453/) (2022)
- [Self-Correcting Neural Networks For Safe Classification](https://mlsanity.com/paper/2107.11445/) (2021)
- [Limitations of Piecewise Linearity for Efficient Robustness Certification](https://mlsanity.com/paper/2301.08842/) (2023)
- [Robust Ambiguity Detection (RAD) From Model- and Feature-Space Consistency](https://mlsanity.com/paper/2608.11541/) (2026)
- [Formal Reasoning About Confidence and Automated Verification of Neural Networks](https://mlsanity.com/paper/2511.07293/) (2025)

## Abstract (arXiv)

Certifiable local robustness, which rigorously precludes small-norm adversarial examples, has received significant attention as a means of addressing security concerns in deep learning. However, for some classification problems, local robustness is not a natural objective, even in the presence of adversaries; for example, if an image contains two classes of subjects, the correct label for the image may be considered arbitrary between the two, and thus enforcing strict separation between them is unnecessary. In this work, we introduce two relaxed safety properties for classifiers that address this observation: (1) relaxed top-k robustness, which serves as the analogue of top-k accuracy; and (2) affinity robustness, which specifies which sets of labels must be separated by a robustness margin, and which can be ε-close in ℓp space. We show how to construct models that can be efficiently certified against each relaxed robustness property, and trained with very little overhead relative to standard gradient descent. Finally, we demonstrate experimentally that these relaxed variants of robustness are well-suited to several significant classification problems, leading to lower rejection rates and higher certified accuracies than can be obtained when certifying "standard" local robustness.