Abstract
We show that when taking into account also the image domain $[0,1]^d$, established $l_1$-projected gradient descent (PGD) attacks are suboptimal as they do not consider that the effective threat model is the intersection of the $l_1$-ball and $[0,1]^d$. We study the expected sparsity of the steepest descent step for this effective threat model and show that the exact projection onto this set is computationally feasible and yields better performance. Moreover, we propose an adaptive form of PGD which is highly effective even with a small budget of iterations. Our resulting $l_1$-APGD is a strong white-box attack showing that prior works overestimated their $l_1$-robustness. Using $l_1$-APGD for adversarial training we get a robust classifier with SOTA $l_1$-robustness. Finally, we combine $l_1$-APGD and an adaptation of the Square Attack to $l_1$ into $l_1$-AutoAttack, an ensemble of attacks which reliably assesses adversarial robustness for the threat model of $l_1$-ball intersected with $[0,1]^d$.
Introduction
Adversarial machine learning usually focuses on $l_\infty$ (small changes to all pixels) or $l_2$ (small Euclidean distance) perturbations. $l_1$-perturbations are unique because they are sparse: they allow for large changes to a very small number of pixels. However, a major flaw exists in current $l_1$ Projected Gradient Descent (PGD) attacks. In image classification, an adversarial example must satisfy two constraints simultaneously: it must be within an $l_1$-distance $\epsilon$ of the original image, and every pixel value must remain within the valid range $[0, 1]^d$ (the "box" constraint).
The Geometry of Sparse Attacks
Previous attacks often treated these constraints separately—typically projecting onto the $l_1$-ball and then simply "clipping" the values to $[0, 1]$. This paper proves that this approximation is suboptimal; it "hides" parts of the valid search space, making the attacks weaker. Clipping an $l_1$-projected image to the box actually reduces the $l_1$ distance to the original image, meaning the attacker isn't using their full budget $\epsilon$.
Methodology: $l_1$-APGD
The authors introduce several mathematical and algorithmic innovations to "mind the box":
- Exact Projection onto the Intersection: They derive an $O(d \log d)$ algorithm to project a point exactly onto the intersection of the $l_1$-ball and the $[0, 1]^d$ box. This is computationally as efficient as standard projection but yields much stronger attacks.
- Box-Aware Steepest Descent: They prove that with box constraints, the "steepest" direction involves a specific number of coordinates ($k$) depending on proximity to boundaries, rather than just a single coordinate.
- Adaptive PGD ($l_1$-APGD): This version is parameter-free, automatically adjusting step size and update sparsity. It employs a "multi-$\epsilon$" strategy, starting with a larger budget to find high-loss regions before narrowing down to the target $\epsilon$.
Experimental Results
Evaluating on benchmarks like CIFAR-10 and ImageNet, $l_1$-APGD consistently outperforms previous standards like SLIDE or EAD. The exact projection is shown to be critical for maximizing loss and minimizing robust accuracy.
By using $l_1$-APGD inside the adversarial training loop, the authors produced a model with 60.3% robust accuracy at $\epsilon=12$ on CIFAR-10, a massive improvement over previous models that typically hovered below 10% or required much more complex setups.
Conclusion
By correctly accounting for the intersection of the $l_1$-ball and the image box, $l_1$-APGD provides a more accurate assessment of model robustness. The proposed $l_1$-AutoAttack ensemble serves as a new "gold standard" for evaluating sparse adversarial robustness, showing that many prior works significantly overestimated their models' resilience.
Summary updated