Computational Asymmetries in Robust Classification

Samuele Marro, Michele Lombardi
6/25/2023
cs.LGcs.CR

Official code: samuelemarro/counter-attack (6 stars, MIT, PyTorch, last commit 2024-02-09).

Abstract

In the context of adversarial robustness, we make three strongly related contributions. First, we prove that while attacking ReLU classifiers is $\mathit{NP}$-hard, ensuring their robustness at training time is $Σ^2_P$-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 $\mathit{NP}$-hard, while attacking it is $Σ_2^P$-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.

View on arXivView PDF

Code Implementations(1)

samuelemarro/counter-attackOfficial100%
PyTorchMIT

A Neural Network metadefense that uses adversarial attacks to detect non-robust inputs.

60Julia, PythonFeb 18, 20202 years agoMIT
adversarial-attackspytorch

Similar Papers

Is Certifying $\ell_p$ Robustness Still Worthwhile?

85% match2023

Theoretical Foundations of Adversarially Robust Learning

83% match2023

Certified Robust Neural Networks: Generalization and Corruption Resistance

83% match1 repo182023

It Is All About Data: A Survey on the Effects of Data on Adversarial Robustness

83% match2023

Seasoning Model Soups for Robustness to Adversarial and Natural Distribution Shifts

83% match2023

On the Duality Between Sharpness-Aware Minimization and Adversarial Training

83% match1 repo252026

Cite this paper

@article{marro2023computational,
  title  = {Computational Asymmetries in Robust Classification},
  author = {Samuele Marro and Michele Lombardi},
  year   = {2023},
  eprint = {2306.14326},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2306.14326v1},
  journal = {ICML 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2306.14326.svg)](https://codeofpaper.com/paper/2306.14326)

Discussion