Research map / Adversarial robustness and security / Certified and empirical robustness
Provable Robustness against a Union of L_0 Adversarial Attacks
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 feature partition aggregation (FPA), a vertically partitioned ensemble of submodels trained on disjoint feature sets that certifies deterministic feature robustness against the union of sparse evasion, backdoor, and poisoning attacks.
Problem
Sparse (L0) adversarial attacks that perturb an unknown subset of features; existing L0 certified defenses (randomized ablation) cover only evasion attacks, not training-time poisoning or backdoors, and are slow to certify.
Approach
Train an ensemble of submodels on disjoint feature subsets so any perturbed feature (train or test) affects at most one submodel; certify robustness via vote gaps under plurality voting or run-off elections, yielding deterministic guarantees over the union of evasion, poisoning, and backdoor attacks.
Key results
- FPA median certified robustness of 13 pixels over 10 for CIFAR10 and 12 over 10 for MNIST, versus randomized ablation's 10 pixels (CIFAR10).
- FPA is up to 3,134x faster to certify than randomized ablation (Weather), e.g., 743x on CIFAR10.
- On Weather at median robustness 1, FPA classification accuracy was 85.3% vs 75.2% for randomized ablation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace randomized ablation with FPA | CIFAR10 · CIFAR10 | median certified robustness (pixels): 10 -> 13 | Helped |
| Replace randomized ablation with FPA | MNIST · MNIST | median certified robustness (pixels): 10 -> 12 | Helped |
| Replace randomized ablation with FPA | Weather · Weather | median certified robustness (features): 1 -> 4 | Helped |
| Replace randomized ablation with FPA | Ames · Ames | median certified robustness (features): 1 -> 3 | Helped |
| Use FPA instead of RA at median robustness of 10 pixels | CIFAR10 · CIFAR10 | classification accuracy: 64.7% -> 75.0% | Helped |
| Increase FPA median robustness from 10 to 13 pixels | CIFAR10 · CIFAR10 | classification accuracy: 75.0% -> 62.4% | Hurt |
| Use FPA instead of RA at median robustness of 10 pixels | MNIST · MNIST | classification accuracy: 93.1% -> 96.1% | Helped |
| Increase FPA median robustness from 10 to 12 pixels | MNIST · MNIST | classification accuracy: 93.1% -> 87.2% | Hurt |
| Use FPA instead of RA at median robustness of 1 feature | Weather · Weather | classification accuracy: 75.2% -> 85.3% | Helped |
| Increase FPA median robustness from 1 to 4 features | Weather · Weather | classification accuracy: 75.2% -> 76.1% | Helped |
| Replace randomized ablation with FPA | all evaluated datasets · CIFAR10, MNIST, Weather, Ames | mean certification time: 743x; 235x; 3,134x; 1,082x | Helped |
| Use deterministic strided partitioning instead of random partitioning | FPA on CIFAR10 and MNIST · CIFAR10 and MNIST | certified accuracy: 15.6 percentage points for CIFAR10 and 11.9pp for MNIST | Helped |
Surprising findings
- Deterministic strided feature partitioning outperforms random partitioning substantially on vision data (up to 15.6pp certified accuracy on CIFAR10).
Limitations
- Under vertical partitioning with feature-disjoint submodels, partitioning loses feature-interaction information, which can reduce accuracy.
- Overlapping feature sets make optimal robustness NP-hard, so the method relies on disjoint partitions.
- Training multiple submodels is slower than a single RA model on CIFAR10 and MNIST on a single system.
Experimental setup
Datasets: CIFAR10 MNIST Weather Ames
Benchmarks: CIFAR10 MNIST Weather Ames
Metrics: median certified robustness classification accuracy mean certification time certified patch accuracy
Baselines: Randomized Ablation (Levine & Feizi 2020) Randomized Ablation (Jia et al. 2022) (De)randomized smoothing Patch IBP BagCert
Builds on: Deep Partition Aggregation Randomized Ablation Almost-tight L0 certification LightGBM
Closest papers by meaning
- Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation (AAAI 2020 · similarity 0.88)
- Certified Adversarial Robustness Under the Bounded Support Set (ICML 2022 · similarity 0.87)
- Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks (ICML 2020 · similarity 0.87)
- RobustBench: a standardized adversarial robustness benchmark (NeurIPS 2021 · similarity 0.87)
- Towards Million-Scale Adversarial Robustness Evaluation With Stronger Individual Attacks (CVPR 2025 · similarity 0.85)
- Consistent Adversarially Robust Linear Classification: Non-Parametric Setting (ICML 2024 · similarity 0.85)
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.