Computational Asymmetries in Robust Classification
This work addresses computational hardness in adversarial robustness for machine learning security, providing theoretical insights and a new benchmark, but it is incremental in building on existing robustness research.
The paper proves that attacking ReLU classifiers is NP-hard, but ensuring their robustness during training is even harder (Σ²_P-hard), explaining why robust classifiers are often fooled. It also introduces Counter-Attack, a defense with reversed hardness, and uses attacks for robustness certification, releasing the UG100 benchmark dataset.
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.