How Much Do $\ell_1$ Attacks Need Concentrated Perturbations?

Melika Shirian, Kianoosh Vadaei, Arshia Hemmat

A global $\ell_1$ budget limits how much an adversary may change an image, not how that change is distributed. We ask how much of an $\ell_1$ attack's observed success remains when large coordinate changes are restricted. We add a per-coordinate cap to the budget, enforce the joint constraint by exact in-loop projection, and sweep the cap for APGD-$\ell_1$, SLIDE, and FMN-$\ell_1$ without altering their objectives. Across 18 standard-model settings, caps of at most $32/255$ retain a median $97\%$ of attack success relative to each method's native uncapped baseline, while median peak magnitude falls by $80\%$ and median effective support nearly triples. At matched realized $\ell_1$, capped perturbations remain structurally distinct; separate ImageNet comparisons also show lower LPIPS and DISTS at selected caps. Direct in-loop constrained optimization preserves up to $88$ percentage points more attack success than post-hoc clipping, highlighting the importance of constraint enforcement. Suitable caps nevertheless vary across attacks and models, and adversarially trained classifiers exhibit more heterogeneous concentration sensitivity. These results establish perturbation…