Research map / Adversarial robustness and security / Black-box and transfer attacks
Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes sparse-PGD (sPGD), a PGD-like white-box l0 attack, combines it with Sparse-RS into sparse-AutoAttack for evaluation, and uses sPGD in adversarial training (sAT/sTRADES) to obtain robust models against l0-bounded perturbations.
Problem
Generating strong l0-bounded (sparse) adversarial perturbations is hard due to non-convex budgets, existing sparse attacks are either inefficient or do not control the l0 norm, and adversarial training against sparse perturbations is too costly.
Approach
Decompose the sparse perturbation into a magnitude tensor and a binary mask, optimize the mask through a continuous surrogate with top-k projection, use an unprojected gradient for the magnitude, and random reinitialization of the mask; the attack's efficiency then enables sparse adversarial training.
Key results
- sTRADES-trained PRN-18 on CIFAR-10 (k=20) reaches 61.7% robust accuracy under sAA, versus 24.1% for PGD0-T and 34.0%-level baselines in the ablation setting.
- sPGD outperforms Sparse-RS by a large margin under small iteration budgets (<1000), while Sparse-RS performs better only with abundant queries on l_inf and l0 models.
- sAA achieves the lowest robust accuracy among all evaluated attacks in Tables 1 and 2; sAT on ImageNet-100 (k=200) reaches 61.2% under sAA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train with sPGD adversarial training rather than PGD0-T | CIFAR-10 models, evaluated by sAA · CIFAR-10 test, k=20 | robust accuracy: 4.5 -> 61.7 | Helped |
| Train with sPGD adversarial training rather than PGD0-A | ImageNet-100 models, evaluated by sAA · ImageNet-100, k=200 | robust accuracy: 1.8 -> 61.2 | Helped |
| Train with sPGD adversarial training rather than PGD0-A | GTSRB models, evaluated by sAA · GTSRB, k=600 | robust accuracy: 0.0 -> 85.4 | Helped |
| Use sPGD instead of Sparse-RS with limited iterations | models evaluated against sparse perturbations · CIFAR-10 and ImageNet-100 | attack strength | Helped |
| Use sPGD rather than Sparse-RS to generate transferable perturbations | VGG11 and ResNet18 · CIFAR-10, k=20 | attack success rate: 28.4 vs 43.9; 37.4 vs 48.0 | Helped |
| Decompose the perturbation as δ=p⊙m (ablation) | sPGDproj · CIFAR-10, k=20 | robust accuracy: 49.4 -> 58.0 | Hurt |
| Use a continuous alternative f̃m for the mask (ablation) | sPGDproj · CIFAR-10, k=20 | robust accuracy: 58.0 -> 33.9 | Helped |
| Add random reinitialization (ablation) | sPGDproj · CIFAR-10, k=20 | robust accuracy: 33.9 -> 18.1 | Helped |
| Always use sparse projected gradients during training instead of randomly selecting backward functions (ablation) | sTRADES PRN-18 · CIFAR-10 test, k=20 | robust accuracy: 61.7 -> 41.5 | Hurt |
| Always use unprojected gradients during training instead of randomly selecting backward functions (ablation) | sTRADES PRN-18 · CIFAR-10 test, k=20 | robust accuracy: 61.7 -> 39.4 | Hurt |
| Alternate backward functions every 5 epochs instead of randomly selecting them (ablation) | sTRADES PRN-18 · CIFAR-10 test, k=20 | robust accuracy: 61.7 -> 51.5 | Hurt |
| Increase the training sparsity budget from 1× to 6× the test budget (ablation) | sTRADES PRN-18 · CIFAR-10 test, k=20 | robust accuracy: 34.0 -> 61.7 | Helped |
Surprising findings
- Adversarial training against l1-bounded perturbations gives the most robust models among non-l0 training methods, attributed to l1 being the tightest convex relaxation of l0.
- Sparse-RS outperforms sPGD on l_inf and l0 models given sufficient iterations, indicating gradient masking across sparse attacks.
Limitations
- Adversarial training with 20-iteration sPGD still has high computational overhead, hard to scale to very large datasets.
- sPGD-based adversarial training variants beyond sAT and sTRADES are left as future work; sAT training is relatively unstable.
- Pixel-level sparsity definition (a pixel is perturbed if any channel is) limits the scope of the threat model.
Experimental setup
Datasets: CIFAR-10 CIFAR-100 ImageNet-100 GTSRB
Benchmarks: CIFAR-10 ImageNet-100 GTSRB CIFAR-100
Metrics: robust accuracy attack success rate runtime
Baselines: PGD0 SparseFool SAIF CornerSearch Sparse-RS l1-APGD Fast-EG-l1 GD PORT DKL DM HAT
Builds on: PGD AutoAttack SAIF Sparse-RS TRADES
Closest papers by meaning
- Understanding and Improving Fast Adversarial Training against $l_0$ Bounded Perturbations (NeurIPS 2025 · similarity 0.91)
- Sparse-RS: A Versatile Framework for Query-Efficient Sparse Black-Box Adversarial Attacks (AAAI 2022 · similarity 0.90)
- Mind the Box: $l_1$-APGD for Sparse Adversarial Attacks on Image Classifiers (ICML 2021 · similarity 0.90)
- Towards Stable and Efficient Adversarial Training against $l_1$ Bounded Adversarial Attacks (ICML 2023 · similarity 0.89)
- $\sigma$-zero: Gradient-based Optimization of $\ell_0$-norm Adversarial Examples (ICLR 2025 · similarity 0.89)
- BRUSLEATTACK: A QUERY-EFFICIENT SCORE- BASED BLACK-BOX SPARSE ADVERSARIAL ATTACK (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.