Source-linked AI summary
Provable robustness against all adversarial $l_p$-perturbations for $p\geq 1$
Francesco Croce, Matthias Hein
TL;DR
Existing provable robustness methods typically guarantee robustness for a specific perturbation norm, leaving other l_q perturbations uncertified. The paper proposes MMR-Universal, which uses l1 and l∞ robustness for ReLU networks; experiments report non-trivial provable guarantees across l1, l2, and l∞ perturbations. Its stated scope is piecewise affine models, including ReLU networks.
Problem
Existing provably robust models for specific l_p perturbations do not guarantee robustness against other l_q perturbations.
Source: §1 · p. 1Method
Results
MMR-Universal is the only evaluated method with non-trivial upper bounds on robust test error for all datasets, and on GTS its upper bound is below the lower bound of all methods except AT-(l1, l2, l∞).
Source: §5.2 · p. 9Takeaways & Limitations
The method provides the first reported provable robustness guarantees for all l_p balls with p ≥ 1.
Source: §6 · p. 9The approach is developed for piecewise affine classifiers, including ReLU networks and extensions such as leaky ReLU.
Source: §2.1 · p. 2
Abstract
from arXiv · showhide
In recent years several adversarial attacks and defenses have been proposed. Often seemingly robust models turn out to be non-robust when more sophisticated attacks are used. One way out of this dilemma are provable robustness guarantees. While provably robust models for specific $l_p$-perturbation models have been developed, we show that they do not come with any guarantee against other $l_q$-perturbations. We propose a new regularization scheme, MMR-Universal, for ReLU networks which enforces robustness wrt $l_1$- and $l_\infty$-perturbations and show how that leads to the first provably robust models wrt any $l_p$-norm for $p\geq 1$.
1 Introduction
Empirical defenses can fail under stronger attacks, and provable methods generally certify only a particular perturbation norm. The paper targets simultaneous robustness across all l_p norms for p ≥ 1 using guarantees for l1 and l∞ perturbations.
1 Introduction
- Prior empirical defenses have often been defeated by more sophisticated attacks, while l∞ adversarial training does not ensure greater robustness to small l_p attacks for p ≠ ∞.The cited exception to attacks defeating empirical defenses is adversarial training by Madry et al. (2018).Source: §1 · p. 1
- Existing provably robust training methods generally certify one perturbation type, often l2 or l∞, rather than all l_p norms simultaneously.Some are designed for a specific p, and their extension to other norms is unclear.Source: §1 · p. 1
- Robustness against all l_p-bounded attacks is non-trivial when none of the l_p-balls is contained in another.For the studied l1 and l∞ balls, normally trained models produce attacks in either ball that do not belong to the other.Source: §1 · p. 2
- MMR-Universal trains piecewise affine models using l1 and l∞ distance guarantees to derive dimension-independent certificates for intermediate l_p norms.The method extends the Croce et al. (2019a) regularizer to maximize the relevant bounds during training.Source: §1 · p. 2
- Experiments on four datasets report the first non-trivial provable robustness for l1, l2, and l∞ perturbations from networks trained with the proposed method.The reported guarantees extend to all l_p norms for p ∈ [1, ∞].Source: §1 · p. 2
2 Local properties and robustness guarantees of ReLU networks
The section represents ReLU networks as affine within local polytopes, then uses distances to region and decision boundaries to bound robustness. Its key extension derives intermediate-norm bounds from l1 and l∞ information.
2.1 ReLU networks as piecewise affine functions
- A ReLU network is affine on each polytope in a finite partition of the input space, and a forward pass determines the local affine form.The paper says the approach can extend to other piecewise affine activations, such as leaky ReLU.Source: §2.1 · pp. 2–3
2.2 Robustness guarantees inside linear regions
- The robustness radius is the smallest l_p distance to an input classified differently, with zero robustness assigned to misclassified points.The optimization also imposes input constraints such as image pixel values lying in [0, 1].Source: §2.2 · p. 3
- Bounds for any intermediate l_p robustness can be derived using only l1 and l∞ distances to region and decision boundaries.The standard l_p norm inequalities alone give bounds that depend on input dimension.Source: §2.2 · p. 3
- Figure 1 shows a larger l2-ball inside the convex hull of the l1 and l∞ balls than inside their union.Its columns compare the two original balls, the largest l2-ball in their union, their convex hull, and the largest l2-ball in that hull.Source: Figure 1 · p. 4
3 Minimal lp-norm of the complement of the union of l1- and l∞-ball and its convex hull
The section derives exact intermediate-norm distances outside the union of an l1- and an l∞-ball and its convex hull. For affine classifiers, guarantees on both balls extend to their convex hull, whose distance bound is dimension-independent.
3 Minimal lp-norm of the complement of the union of l1- and l∞-ball and its convex hull
- The exact distance outside the union uses the known lower bounds on both the l1- and l∞-norms, which the naive norm-inequality bound ignores.The section first frames the intermediate-p guarantee as the minimum lp-norm outside the union.Source: §3 · p. 4
- For affine classifiers, a guarantee on both balls extends to their convex hull, and the theorem characterizes the minimum lp-norm outside that hull.The section considers ε1 between ε∞ and dε∞, so neither ball contains the other.Source: §3 · p. 4
- The convex-hull minimum l2-distance is up to 3.8 times the union distance for d=784 and 5.3 times for d=3072.Figure 2 compares these distances with ε∞=1 as ε1 varies; the convex-hull expression is exact and dimension-independent.Source: §3 · p. 5, Figure 2 · p. 5
- The larger lp-balls inside the convex hull motivate enlarging the affine regions around training points so those balls fit within them.The next section formalizes the resulting robustness guarantees.Source: §3 · p. 5
4 Universal provable robustness with respect to all lp-norms
The section combines l1- and l∞-margin regularization to obtain robustness bounds for all lp norms from endpoint-distance information. MMR-Universal pushes nearby region and decision boundaries away from training points, with the stated goal of improving intermediate-norm robustness as well.
4 Universal provable robustness with respect to all lp-norms
- Bounds for any lp norm use the distances at the training point for the different p values, combining the piecewise-affine robustness results with the geometric result.The method applies to continuous piecewise-affine classifiers such as ReLU networks.Source: §4 · pp. 5–6
- MMR-Universal combines MMR-l1 and MMR-l∞ to enhance robustness for every lp norm without separately computing and modifying all corresponding distances.The authors state that the joint l1- and l∞-guarantees are the key property of the regularizer and give it a theoretical justification.Source: §4 · p. 6
- The regularizer pushes polytope and decision hyperplanes beyond γ1 in l1 and γ∞ in l∞ from each training point, which Theorem 4.1 links to intermediate-norm robustness.λ1 and λ∞ balance the two norm terms and their weights relative to cross-entropy; decision-distance terms also penalize misclassification.Source: §4 · p. 6
- Using several closest hyperplanes enlarges training-point regions more quickly and can also influence neighboring regions when robustness bounds explore beyond the current region.The regularizer uses the kB closest hyperplanes rather than only the closest one.Source: §4 · p. 6
- MMR-Universal seeks to move the hyperplanes whose proximity is associated with unstable ReLU signs, which the authors connect to certifying these models with existing methods.The passage names the Wong & Kolter (2018) and Tjeng et al. (2019) certification methods.Source: §4 · p. 7
5 Experiments
The experiments compare MMR-Universal with provable-robustness and adversarial-training methods using robust test-error bounds on unions of norm balls. The chosen perturbation balls are non-nested, and MMR-Universal is the only method with non-trivial upper bounds across all datasets.
5.1 Choice of ϵp
- For the chosen thresholds, no lp-ball contains another, and zero cross-norm attack examples on every dataset show that robustness to the union is harder than robustness to one ball.The reported percentages are zero for l1 attacks whose l∞ norm is within budget, and vice versa.Source: §5.1 · p. 7
5.2 Main results
- Table 2 reports non-trivial union-robustness upper bounds for MMR-Universal on every dataset, unlike almost all other provable-robustness methods.On GTS, its upper bound is below the lower bound of every method except AT-(l1, l2, l∞).Source: Table 2 · p. 8, §5.2 · p. 9
- CNNs are trained on MNIST, Fashion-MNIST, German Traffic Sign, and CIFAR-10, with union-robustness statistics computed on the first 1000 test points.Test error is computed on each dataset's whole test set.Source: §5.2 · p. 8
5 Experiments
- The evaluation compares plain, adversarial, robust, MMR, combined MMR-plus-adversarial, and MMR-Universal training using union-of-balls robust test-error bounds.The lower bound counts successful attacks; the upper bound counts points for which at least one ball is not certified free of adversarial examples.Source: §5 · p. 7, §5.2 · p. 8
6 Conclusion
MMR-Universal is presented as the first method with provable guarantees for every lp-ball with p ≥ 1. The accompanying proofs develop geometric conditions for comparing l1 and l∞ balls and their convex hull.
6 Conclusion
- MMR-Universal provides the first provable robustness guarantees for all lp-balls with p ≥ 1.The conclusion notes that guarantees for a union of lp-balls are considerably harder than guarantees for either l2 or l∞ alone.Source: §6 · p. 9
A.1 Proof of Proposition 3.1
- When ϵ1 < ϵ∞, B1 is contained in B∞; when ϵ1 > dϵ∞, B∞ is contained in B1.These containment cases follow from norm inequalities.Source: §A.1 · p. 12
A.2 Proof of Theorem 3.1
- Faces of the convex hull C lie in hyperplanes spanned by subsets of d vertices from the union of the B1 and B∞ vertices.A candidate hyperplane contains a face only if it does not intersect the interior of C.Source: §A.2 · p. 12
A.3 Comparison of the robustness guarantee for the union of B1 and B∞in (5) and the convex hull of B1 and B∞in (6)
The analysis compares l2 robustness bounds from the union of B1 and B∞ with bounds from their convex hull. The convex hull's gain increases with input dimension.
A.3 Comparison of the robustness guarantee for the union of B1 and B∞in (5) and the convex hull of B1 and B∞in (6)
- The comparison maximizes the ratio of the convex-hull and union bounds over δ = ϵ1/ϵ∞ in [1, d], for p = 2.It evaluates the largest l2-ball fitting inside either the union or its convex hull.Source: §A.3 · p. 15
- The convex-hull robustness guarantee improves over the union by approximately 3.8 at d = 784 and 5.3 at d = 3072.The authors characterize this as a considerable gain in high dimensions.Source: §A.3 · p. 15
B.1 Proof of Theorem 4.1
The proof transfers distances from the input to relevant hyperplanes into a robustness bound using the convex hull of l1 and l∞ balls.
B.1 Proof of Theorem 4.1
- If no identified decision or region-boundary hyperplane is closer than the minimum l1 and l∞ boundary distance, the centered balls avoid those hyperplanes and Theorem 3.1 supplies the resulting bound.The proof applies this to the convex hull of the two balls.Source: §B.1 · p. 16
C.1 Choice of ϵp
The selected l1 and l∞ attacks produce non-overlapping adversarial examples, and l1 and l2 attacks also do not overlap. Cross-norm containment varies by norm and dataset, so robustness or attack behavior for one norm does not settle the others.
C.1 Choice of ϵp
- 0% of l1 adversarial examples lie in the l∞-ball, and 0% of l∞ adversarial examples lie in the l1-ball.The table reports the percentage of examples contained in the other norm’s ball.Source: §C.1 · p. 16, Table 3 · p. 16
- l1- and l2-adversarial examples also do not overlap, while l2 examples lie inside the l∞-ball for MNIST and F-MNIST.For those datasets, l∞ certification alone still does not provide non-trivial l2 guarantees.Source: §C.1 · p. 16
- The authors conclude that empirical and provable robustness interact differently across perturbation types.Their analysis treats attack-example overlap and certified robustness as distinct scenarios.Source: §C.1 · p. 16
C.2 Main results
Training for provable robustness against one lp-norm does not generally provide provable robustness against another. The reported l∞ bounds are tighter because the MIP approach is practical only for l∞, while the method applied across all three norms yields looser bounds for l1 and l2.
C.2 Main results
- Training for provable lp-robustness does not generally yield provable lq-robustness for q ≠ p, even when lower bounds are small for both norms.The section reports this pattern across datasets and training schemes.Source: §C.2 · p. 17
- The l∞ upper bounds are tighter because presolvers make the computationally expensive MIP method practical for l∞, while Wong and Kolter’s method applies to every lp-norm.Tjeng et al.’s MIP approach is used only for l∞ in these comparisons.Source: §C.2 · p. 17
C.3 Experimental details
The experiments compare training schemes across datasets using clean test error and certified robust-error bounds, with robustness statistics computed on a 1,000-example subset. MMR-Universal is the only compared approach reported to have non-trivial upper bounds across all considered norms.
C.3 Experimental details
- The convolutional network has two convolutional layers with 16 and 32 filters, followed by a fully connected layer with 100 hidden units.MMR-Universal models use batch size 128 and train for 100 epochs; CIFAR-10 also uses random crops and mirroring.Source: §C.3 · p. 17
- In Tables 2 and 4, test error is computed on the full test set, whereas statistics for upper and lower bounds on robust test error use the first 1,000 test points.Source: §C.3 · p. 17
- MMR-Universal is the only compared approach with non-trivial upper bounds on robust test error for all considered norms.Table 4 reports test error and lower and upper robust-error bounds for individual norms and their union.Source: §C.3 · p. 18, Table 4 · p. 18
- Figure 3 tracks clean test error and individual- and union-ball upper bounds during MMR-Universal training, sampling epochs 1, 2, 5, 10, then every 10 epochs.Robustness statistics use 1,000 points and Wong and Kolter’s method.Source: Figure 3 · p. 19
C.4 Evolution of robustness during training
Across datasets, MMR-Universal’s test error decreases and its robust-error upper bounds generally improve during training. The supplementary experiments report that combining single-norm MMR with adversarial training still leaves a norm without a non-trivial guarantee, while larger networks did not significantly improve on smaller ones.
C.4 Evolution of robustness during training
- For all datasets, test error decreases across epochs, and robust-error upper bounds generally improve during MMR-Universal training.The plotted bounds omit the tighter l∞ results that the MIP formulation would provide.Source: §C.4 · p. 19
C.5 Other combinations of MMR and AT
- For both tested MNIST combinations of single-norm MMR and adversarial training, at least one norm has a 100% robust-error upper bound.The combinations use MMR for one norm and adversarial training for the other.Source: §C.5 · p. 19
C.6 Larger models
- MMR-Universal on the larger architecture did not achieve significant improvement over the smaller networks reported in the main paper.Verification becomes more expensive as network size increases.Source: §C.6 · p. 20
- The larger-model results use only Wong and Kolter’s bounds, without the tighter l∞ bounds from Tjeng et al.’s method.The authors say this explains why the results appear worse than those in Table 2.Source: §C.6 · p. 20