# Computational Asymmetries in Robust Classification

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 46 references that are in the map.
- First posted on arXiv 25 Jun 2023.

## Builds on (most cited first, 30 of 36)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [DeepFool: a simple and accurate method to fool deep neural networks](https://mlsanity.com/paper/1511.04599/) (2015)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Distillation as a Defense to Adversarial Perturbations against Deep Neural Networks](https://mlsanity.com/paper/1511.04508/) (2015)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods](https://mlsanity.com/paper/1705.07263/) (2017)
- [MagNet: a Two-Pronged Defense against Adversarial Examples](https://mlsanity.com/paper/1705.09064/) (2017)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Detecting Adversarial Samples from Artifacts](https://mlsanity.com/paper/1703.00410/) (2017)
- [On the (Statistical) Detection of Adversarial Examples](https://mlsanity.com/paper/1702.06280/) (2017)
- [Making an Invisibility Cloak: Real World Adversarial Attacks on Object Detectors](https://mlsanity.com/paper/1910.14667/) (2019)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [The Odds are Odd: A Statistical Test for Detecting Adversarial Examples](https://mlsanity.com/paper/1902.04818/) (2019)
- [advertorch v0.1: An Adversarial Robustness Toolbox based on PyTorch](https://mlsanity.com/paper/1902.07623/) (2019)
- [Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability](https://mlsanity.com/paper/1809.03008/) (2018)
- [Evaluating the Adversarial Robustness of Adaptive Test-time Defenses](https://mlsanity.com/paper/2202.13711/) (2022)
- [Defensive Distillation is Not Robust to Adversarial Examples](https://mlsanity.com/paper/1607.04311/) (2016)
- [MagNet and "Efficient Defenses Against Adversarial Attacks" are Not Robust to Adversarial Examples](https://mlsanity.com/paper/1711.08478/) (2017)
- [Accurate, reliable and fast robustness evaluation](https://mlsanity.com/paper/1907.01003/) (2019)
- [Early Methods for Detecting Adversarial Images](https://mlsanity.com/paper/1608.00530/) (2016)
- [Adversarial Example Defenses: Ensembles of Weak Defenses are not Strong](https://mlsanity.com/paper/1706.04701/) (2017)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [On Robustness to Adversarial Examples and Polynomial Optimization](https://mlsanity.com/paper/1911.04681/) (2019)
- [Adversarially Robust Learning Could Leverage Computational Hardness](https://mlsanity.com/paper/1905.11564/) (2019)

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

- [MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs](https://mlsanity.com/paper/2412.10186/) (2024)
- [Trustworthy Data- and ML-Ops for Intelligent Transportation Systems and Logistics](https://mlsanity.com/paper/2610.01282/) (2026)

## Abstract (arXiv)

In the context of adversarial robustness, we make three strongly related contributions. First, we prove that while attacking ReLU classifiers is mathitNP-hard, ensuring their robustness at training time is Sigma2P-hard (even on a single example). This asymmetry provides a rationale for the fact that robust classifications approaches are frequently fooled in the literature. Second, we show that inference-time robustness certificates are not affected by this asymmetry, by introducing a proof-of-concept approach named Counter-Attack (CA). Indeed, CA displays a reversed asymmetry: running the defense is mathitNP-hard, while attacking it is Sigma2P-hard. Finally, motivated by our previous result, we argue that adversarial attacks can be used in the context of robustness certification, and provide an empirical evaluation of their effectiveness. As a byproduct of this process, we also release UG100, a benchmark dataset for adversarial attacks.