TL;DR
Researchers have discovered that standard $l_1$ adversarial attacks are suboptimal because they fail to correctly account for the "box constraints" of image data (pixels must be between 0 and 1). By introducing $l_1$-APGD—which uses exact projections and adaptive sparsity—the authors provide a more reliable way to evaluate robustness and achieve state-of-the-art results in training $l_1$-robust classifiers.
What Problem Does This Paper Address?
In the world of adversarial machine learning, most research focuses on $l_\infty$ (changing all pixels slightly) or $l_2$ (changing pixels based on Euclidean distance) perturbations. The $l_1$ norm is unique because it encourages sparsity: an attacker tries to change as few pixels as possible to fool a classifier.
However, the authors identify a major flaw in how $l_1$ attacks were previously implemented. In image classification, any adversarial image must still be a valid image—meaning every pixel value must stay within the box $[0, 1]$. Standard Projected Gradient Descent (PGD) attacks usually project the perturbation onto an $l_1$-ball and then "clip" the values to fit the $[0, 1]$ range.
The authors argue that this two-step "project then clip" approach is a poor approximation. The true threat model is the intersection of the $l_1$-ball and the $[0, 1]$ box. By ignoring the geometry of this intersection, previous attacks were "hiding" parts of the search space, leading researchers to overestimate how robust their models actually were.
Methods
The paper introduces several technical innovations to fix these issues:
- Exact Projection onto the Intersection: They prove that projecting a point onto the intersection of an $l_1$-ball and the $[0, 1]^d$ box can be done efficiently in $O(d \log d)$ time. This ensures the attack always stays within the mathematically correct "threat model."
- Adaptive Sparsity and Step Size ($l_1$-APGD): Building on the "Auto-PGD" framework, they created a version that requires no manual tuning of step sizes. Crucially, it uses adaptive sparsity: it starts with dense updates to explore the space and progressively becomes sparser to fine-tune the attack.
- Multi-$\epsilon$ Scheduling: To avoid getting stuck in local minima, the attack starts by searching in larger $l_1$-balls (e.g., $3\epsilon$ and $2\epsilon$) before narrowing down to the target radius $\epsilon$.
- $l_1$-AutoAttack: They assembled an ensemble of four diverse attacks—including a newly adapted black-box $l_1$-Square Attack—to provide a standardized, "plug-and-play" benchmark for $l_1$ robustness.
Key Insights and Ideas
- The "Box" is a Feature, Not a Bug: Properly incorporating the $[0, 1]$ constraints doesn't just make the math cleaner; it makes the attack significantly more potent. The authors show that the "correct" steepest descent direction for the intersection is actually less sparse than for the $l_1$-ball alone, justifying why multi-pixel updates are more effective.
- Fixing Catastrophic Overfitting: A common problem in adversarial training is "catastrophic overfitting," where a model becomes robust to a specific weak attack but remains vulnerable to others. The authors found that training with $l_1$-APGD prevents this, likely because the adaptive sparsity forces the model to defend against a much wider variety of perturbations.
- Black-Box Superiority: Their adapted $l_1$-Square Attack outperformed existing black-box methods (like Pointwise Attack) by a large margin, proving that even without gradient information, the "box constraint" geometry is vital.
Key Results
- Exposing Vulnerabilities: $l_1$-APGD consistently found lower robust accuracies than previous SOTA attacks (like SLIDE or EAD). For many models, the "robust" accuracy dropped by 5-10% when tested with the new method.
- New SOTA for Robustness: By using $l_1$-APGD during adversarial training, the authors produced a model with 60.3% robust accuracy (at $\epsilon=12$ on CIFAR-10). This is a massive jump over the previous best of approximately 54-55%.
- Efficiency: Despite the added mathematical complexity, $l_1$-APGD is computationally comparable to standard PGD, making it practical for large-scale training.
Limitations and Future Work
The authors admit they don't have a complete theoretical explanation for why standard $l_1$-PGD fails so badly during adversarial training while their version succeeds, though they suspect it relates to the diversity of the generated adversarial examples.
Future work could involve exploring how these "box-aware" attacks behave on even higher-dimensional data or different types of constraints (e.g., $l_0$ or $l_\infty$ combined with other domain-specific requirements). There is also an open question about whether similar geometric insights could improve attacks in non-image domains, like natural language or tabular data.
Summary updated