Research map / Label-efficient and robust learning / Recognition and long-tail
Compositional Targeted Multi-Label Universal 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 CMLU, a compositional method that learns |C| label-wise universal perturbations whose affine convex cones can be combined to build targeted universal attacks on any label subset in constant time.
Problem
Targeted universal adversarial perturbations for multi-label recognition require 2^|C| perturbation vectors, giving exponential training time and space cost.
Approach
Assume each target-set perturbation is a sum of mutually orthogonal label-wise universal perturbations; optimize these label-wise vectors so that their affine convex cones support attacks on any label combination, reducing complexity to linear in the number of classes.
Key results
- CMLUβ achieves fooling rates close to the exponential-cost Oracle on NUS-WIDE and MS-COCO while having linear complexity (e.g., 97.6% vs 98.9% FR at target size 1 on NUS-WIDE with ASL).
- On OpenImages with ASL at target size 20, CMLUβ reaches 95.2% FR versus Oracle 96.8%, while Or-S and Or-C drop to 0%.
- CMLUβ's perturbations transfer between ASL and ML-Decoder with fooling rates often comparable to or better than the Oracle's.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use CMLUβ rather than the exponential-complexity Oracle | targeted universal perturbations · OpenImages, target sizes 1–20 | FR: 97.6 vs 97.3; 96.8 vs 95.2 | No clear effect |
| use CMLUβ rather than the exponential-complexity Oracle | targeted universal perturbations · OpenImages, target size 20 | NTR: 1.47 vs 1.67 | Hurt |
| increase perturbation budget ϵ from 0.01 to 0.07 (ablation) | Oracle · NUS-WIDE, target size 1 | FR: 63.5 -> 99.7 | Helped |
| increase perturbation budget ϵ from 0.01 to 0.07 (ablation) | CMLUβ · NUS-WIDE, target size 1 | FR: 38.5 -> 99.3 | Helped |
| increase κ from 15 to 30 (ablation) | Oracle · NUS-WIDE, target size 1 | NTR: 6.50 -> 4.40 | Helped |
| increase κ from 15 to 30 (ablation) | CMLUβ · NUS-WIDE, target size 1 | NTR: 8.32 -> 6.58 | Helped |
| increase κ from 15 to 30 (ablation) | Oracle · NUS-WIDE, target size 1 | FR: 99.1 -> 93.1 | Hurt |
| increase κ from 15 to 30 (ablation) | CMLUβ · NUS-WIDE, target size 1 | FR: 98.5 -> 85.5 | Hurt |
| compose label-wise perturbations with CMLUβ instead of naive Oracle Sum | multi-label universal attacks · OpenImages, larger target sets | FR: 0.0 vs 95.2 | Helped |
| compose label-wise perturbations with CMLUβ instead of Oracle Combination | multi-label universal attacks · OpenImages, target size 20 | FR: 0.0 vs 95.2 | Helped |
| use CMLUβ instead of CMLUα | compositional universal attacks · OpenImages, target size 20 | FR: 32.3 vs 95.2 | Helped |
| increase target set size | Or-S and Or-C · OpenImages | FR: 97.6 -> 0.0; 97.6 -> 0.0 | Hurt |
Surprising findings
- Naively summing or combining single-label universal perturbations (Or-S, Or-C) collapses to near-zero fooling rates at large target sizes, indicating no common intersection of adversarial regions.
- NAG achieves high fooling rates on OpenImages but flips many non-target labels, indicating it attacks groups of labels rather than class-specific directions.
Limitations
- Oracle baseline is exponential and was only feasible on subsets of 25, 40, and 100 classes.
- Evaluated only on a subset of target-set combinations due to computational cost.
- Independence and orthogonality assumptions on label-wise perturbations are approximations.
Experimental setup
Datasets: NUS-WIDE MS-COCO OpenImages
Benchmarks: NUS-WIDE MS-COCO OpenImages
Metrics: fooling success rate (FR) non-target flip rate (NTR) SSIM
Baselines: Oracle Oracle Sum (Or-S) Oracle Combination (Or-C) SGA NAG
Builds on: Universal adversarial perturbations (Moosavi-Dezfooli et al.) SGA NAG Asymmetric Loss
Closest papers by meaning
- Imprecise Label Learning: A Unified Framework for Learning with Various Imprecise Label Configurations (NeurIPS 2024 · similarity 0.85)
- Tight and Fast Bounds for Multi-Label Learning (ICML 2025 · similarity 0.84)
- Controller-Guided Partial Label Consistency Regularization with Unlabeled Data (AAAI 2024 · similarity 0.84)
- Generalization Analysis for Multi-Label Learning (ICML 2024 · similarity 0.84)
- Rethinking Self-Distillation: Label Averaging and Enhanced Soft Label Refinement with Partial Labels (ICLR 2025 · similarity 0.84)
- ULAREF: A Unified Label Refinement Framework for Learning with Inaccurate Supervision (ICML 2024 · similarity 0.84)
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.