TL;DR
Researchers from the University of Tübingen have developed MMR-Universal, the first regularization scheme that provides provable robustness guarantees against all $l_p$-norm adversarial attacks (for $p \geq 1$) simultaneously. By strategically maximizing the distance to decision boundaries in both $l_1$ and $l_\infty$ norms, the model creates a "safety zone" that mathematically covers every other $l_p$ norm, effectively ending the game of whack-a-mole where defending against one type of attack leaves a model vulnerable to others.
What Problem Does This Paper Address?
Deep learning models are notoriously fragile. A tiny, imperceivable change to an image (an adversarial perturbation) can flip a "stop sign" classification to "speed limit 80." Most defenses focus on a specific "threat model," usually defined by an $l_p$-norm (like $l_2$ for Euclidean distance or $l_\infty$ for maximum pixel change).
The core problem is robustness transferability. A model provably robust against $l_\infty$ attacks often has zero protection against $l_1$ attacks, and vice versa. In the real world, an attacker won't tell you which norm they are using. Previous attempts to defend against multiple norms were mostly empirical (heuristic-based) and lacked "certificates"—mathematical proofs that no perturbation within a certain radius can change the model's output.
Methods
The authors leverage the fact that ReLU networks are piecewise affine functions. This means the input space is partitioned into a massive collection of polytopes (linear regions); inside each region, the network behaves like a simple linear classifier.
The core technical contribution is a geometric insight:
- The Convex Hull Trick: The authors prove that if a classifier is robust within the convex hull of an $l_1$-ball and an $l_\infty$-ball, it is automatically robust for all intermediate $l_p$-norms ($p \in (1, \infty)$).
- Dimension Independence: Crucially, they derive a lower bound for $l_p$-robustness that does not depend on the input dimension $d$. This is a major improvement over "naive" bounds that degrade as image resolution increases.
- MMR-Universal Regularizer: They propose a training loss that penalizes the model if the training points are too close to the "boundaries" of their linear regions or the decision boundary, measured in both $l_1$ and $l_\infty$ distances. By pushing these boundaries away during training, they "carve out" a provably safe space for all $p \geq 1$.
Key Insights and Ideas
- The "Union" is Harder than the Parts: The authors show that for standard models, an $l_1$ attack almost never lands inside an $l_\infty$ ball of reasonable radius. This means the set of "dangerous" directions is much larger when considering multiple norms, making simultaneous defense significantly more difficult.
- $l_1$ and $l_\infty$ are the "Anchors": Because $l_1$ and $l_\infty$ are the extreme cases of $l_p$ norms, securing them (and the space between them) effectively blankets the entire spectrum of $p \geq 1$.
- Provable vs. Empirical: While adversarial training provides good empirical defense, it often fails to provide a certificate. MMR-Universal is designed specifically to make the model "verifiable" by existing tools like the Wong & Kolter provable framework.
Key Results
The method was evaluated on four standard computer vision benchmarks: MNIST, Fashion-MNIST, GTS (German Traffic Sign), and CIFAR-10. The authors compared MMR-Universal against state-of-the-art defenses.
- First of its kind: MMR-Universal was the only method to provide non-trivial "Upper Bounds" (the maximum possible error under attack) for the union of $l_1, l_2,$ and $l_\infty$ perturbations across all datasets.
- GTS Performance: On the German Traffic Sign dataset, while other "robust" models had a provable error of 100% (meaning they couldn't guarantee anything against a union of attacks), MMR-Universal achieved a provable robust error of 52.4%.
- Efficiency: By only needing to track $l_1$ and $l_\infty$ during training, the method avoids the computational nightmare of trying to optimize for every possible $p$ individually.
Limitations and Future Work
- Clean Accuracy Trade-off: Like almost all robustness methods, there is a "robustness tax." Models trained with MMR-Universal have slightly higher error on clean, un-attacked images compared to standard models.
- Scalability of Verification: While the training is efficient, proving the robustness (verification) still relies on external tools (like MIP solvers) which can be computationally expensive for very large, deep networks.
- Beyond $p < 1$: The current theory applies to $p \geq 1$. Extending these provable guarantees to $l_0$ (sparsity) or $p < 1$ remains an open challenge.
Summary updated