Provable robustness against all adversarial $l_p$-perturbations for $p\geq 1$
Authors: Francesco Croce
Matthias Hein
Venue:  (2020)
Keywords: adversarial robustness
provable guarantees

Abstract: 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$- \textit{and} $l_\infty$-perturbations and show how that leads to the first provably robust models wrt any $l_p$-norm for $p\geq 1$.

Published as a conference paper at ICLR 2020
PROVABLE ROBUSTNESS AGAINST ALL ADVERSARIAL 1p- I-PERTURBBATION FOR p 2 1
Francesco Croce
Matthias Hein
University of Tübingen, Germany
University of Tübingen, Germany
ABSTRACT
In recent years several adversarial attacks and defenses have been pro- posed. 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 guarantecs. While provably robust models for specific (y-perturbation models have been developed, we show that they do not come with any guarantee against other ly-perturbations. We propose new regularization scheme, MMR-Universal, for ReLU networks which enforces robustness wrt 41- and bo0 be-petuuraaiion and show how that leads to the first provably robust models wrt any 1p n--orrm for p 2 1.
INTRODUCTION
The vulnerability of neural networks against adversarial manipulations (Szegedy et al., 2014 Goodfellow et al. 2015) is a problem for their deployment in safety critical systems such as autonomous driving and medical applications. In fact, small perturbations of the input which appear irrelevant or are even imperceivable to humans change the decisions of neural networks. This questions their reliability and makes them a target of adversarial attacks.
To mitigate the non-robustness of neural networks many empirical defenses have been proposed, e.g. by Gu & Rigazio (2015): y Zheng et al. (0166) Papernot et al. (2016): Huang
(2018) but at the same time more sophisticated attacks have proven these defenses to be ineffective (Carlini Wagner 2017 Athalye et al. 2018 Mosbach et al. 2018), with the exception of the adversarial training of Madry et al. (2018). However, even these advaaverrarrllly trained models are not more robust than normal ones when attacked with perturbations of small ly-norms with p A do
et al. (2016); Bastani et al. (2016); ; Madry et al.
(Sharma & Chen 2019 Schott et al.) 2019: Croce et al. 2019b Kang et al. 2019). The situation becomes even more complicated if one extends the attack models beyond balbs to other sets of perturbations (Brown el. al.] 2017 Engstrom et. al. 2017 Hendrycks &
Dietterich 2019
Geirhos et al. 2019).
Another approach, which fixes the problem of overestimating the robustness of a model, is provable guarantees, which means that one certifies that the decision of the network does not change in a certain ly-ball around the target point. Along this line, current state-of-the- art methods compute either the norm of the minimal perturbation changing the decision at point (c.g. Katz et al. (2017); ; Tieng et al. (2019) or lower bounds on it (Hein &
Andriushchenko 2017 Raghunathan et 2018 Wong & Kolter 2018). Several new training
schemes like (Hein & Andriushchemke kol 2017 Raghunathan et al.] 2018 Wong & Kolter 2018
Mirman et al. 2018 Croce el al.] 2019a Xiao al. 2019; Gowal et al. 2018) aim at both
enhancing the robustness of networks and producing models more amenable to verification
techniques. However, all of them are only able to prove robustness against a single kind of perturbations, typically cither 1z- or -bunddd, and not wrt all the (p-norms simultancously.
as shown in Soction 5 Some are also designed to work for a specific p (Mirman et al. 2018
Gowal et al. 2018) and it is not clear if they can be extended to other norms.
The only two papers which have shown, with some limitations, non-trivial empirical robustness against multiple types of ad aevessaiial examples are Schott et al. (019 and Tramer & Boneh

---

Rdd and is an Published as a conference paper at ICLR 2020
2019 which resist to ly- resp, 41- 12- and lat-akkkcks. However, they come without provable guarantees and Sccoot et al. (2019) is restricted to MNIST.
In this paper we aim at robustness against all the by-bounded attacks for p 2 1. We study the non-trivial case where none of the 1,-balls is contained in another. If Ep is the radius of the 1p-ball for which we want to be provably robust, this requires: d eg Ep > fq for p < q and d being the input dimension. We show that, for normally trained models, for the 41- and -balllls we use in the experiments none of the adversarial examples constrained to be in the 41-ball (i.e. results of an /ı-attack) belongs to the bx-ball, and vice versa. This shows that certifying the union of such balls is significantly more complicated than getting robust in only one of them, as in the case of the union the attackers have much larger variety of manipulations available to fool the classifier.
We propose technique which allows to train piecewise affine models (like ReLU networks) which are simullaneously provably robust all the Ip-norms with p E [1) First, we show that having guarantees on the 11- and -o-diittncee to the decision boundary and region boundaries (the borders of the polytopes where the classifier affine) is sufficient to derive meaningful certificates on the robustness wrt all fo-norms for p E (1, c0). In particular, our guarantoes are independent of the dimension of the input space and thus go beyond a naive approach where one just exploits that all 4p-metrics can be upper- and lower-bounded wrt any other I,-metric. Then, we extend the regularizer introduced in Croce et al. (2019a) so that we can directly maximize these bounds training time. Finally, we show the ellectiveness of our technique with experiments on four datasets, where the networks trained with our method are the first ones having non-trivial provable robustness wrt 41,, (2- and lee-perturbations
2 LOCAL PROPERTIES AND ROBUSTNESS GUARANTEES OF RELU NETWORKS
It is well known that feedforward neural networks (fully connected, CNNN, residual networks, DenseNets etc.) with piecewise affine activation functions, e.g. ReLU, leaky ReLU, yield contimuous piecewise affine functions (see e.g. Arora et al. (2018) : Croce Hein (018)).
Croce et al. (0199a) exploit this property to derive bounds the robustness of such networks against adversarial manipulations. In the following we recall the guarantecs of [Croe et al.
(2019a) wrt a single ly-perturbation which we extend in this paper to simultaneous guarantees wrt all the b-peetuurations for in oo].
2.1 RELU NETWORKS AS PIECEWISE AFFINE FUNCTIONS
Let f: 12d RK be a classifier with d being the dimension of the input space and K the number of classes. The classifier decision at point is given by arg max f-(x). In this paper r=l....K we deal with ReLU networks, that is with ReLU activation function (in fact our approach can be easily extended to any piecewise affine activation function e.g. leaky ReLU or other forms of layers leading to a piccewise affine classifier in Croce al. (2019b)).
Definition 2.1 A function f: Rdd + R is called piccewise affine if there crists a finite set of polytopes (Qr M (referred as lincar regions of f) such that affine function when restricted to every Qr.
Denoting the activation function as a (a(1)= max(0, 1} if ReLU is used) and assuming L hidden layers, we have the usual recursive definition of as
90hh (x) w ((-1(()) + b0, with (() = x and f(x) = (((+))((((a))) + ((L+1) the output of f. Moreover, W()) E R - and 800 E R where ny is the number of units in the I-th layer (ng = d, nL+11 = K).
= o(g (x)), I=
For the convenience of the reader summarize from Croce & Hein 2018 the description of the polytope Q(x) containing I and affine form of the classifier f when restricted to Q(z).
We assume that does not lie the boundary between polytopes (this is almost always
2

---

Published as a conference paper at ICLR 2020
true faces shared between polytopes are of lower dimension). Let A E() E Ruxx for I 1,...,, L be diagonal matrices defined elementwise as
A (2)s [1
sign
(x)) (x))
= else.
= (z)s = {
j and f1) 0,
else.
This allows us to write (1) as composition of affine functions, that is
(w)(() (Wl-1)) (x) (wor, + +b6) ...) + but b(t11)) + b9, which simplify as (x) V0 aD) with V E Rrixd and al)) R given by
(x) ww (x)
(..((ww),
v w
[II- 1d (z) and ah 600 j=1
Σ
(II W W (x) (60.
m=1
forward pass through the network sufficient. to compute V0) and b09 for every 1. The polytope Q(x) is given as intersection of N NEEL ny half spaces defined by
Q(x) n n
n E Rd A (x) (v + +a( 0}.
i=1,...
Finally, the affine restriction of f to Q(x) is f(=)lq(+) f(lt IQ(=( (z) v((+1) + (1++1).
Let q be defined via p + + and the correct class of x. We introduce
d (x) (v)")) 2: +a (1)
fc(x) fz)x)
and (x) = v( V2 v11+1)
(1)
(1)
for every = I,..., L, L...., 1, I,..., K and s + which represent the N ly-distances of to the hyperplanes defining the polytope (xx) and the K - In-distances of x to the hyperplancs defining the decision boundarics in Q(z). Finally, we define
d (=)x)) = min min
(2)s(x) and d (x) = min dp. 1= I= L j=l...,m
(2)
sgfcc
as the minimumn values of these two sets of distances (note that d2(x) (x) < <f is misclassified).
2.2 ROBUSTNESS GUARANTEES INSIDE LINEAR RECIONS
The Ip-robustness (x) of a classifier f at a point x, belonging to class c, wrt the Ip-norm is defined as the optimal value of the following optimization problem
(=(x)= min
||
s.th. max f((x + 6) 2 fe(x + 6), x Isc
(3)
SER
where is S a set of constraints on the input, e.g. pixel values of images have to be in [0. 1]. The robbouussssss (x) is the smallest Iy-distance to x of a point which is classified differently from c. Thus, (x) = 0 for misclassified points. The following theorem from Croce et al. 2019a rephrased to fit the current notation, provides guarantees on rz(x).
Theorem 2.1 (Croce et al. (2019a) If df < dz(x), then r,(2) 2 dg(x)) (x), while if [d)()) < de (z), then rp(x) m (d)(), (z),
Although Theorem 2.1 holds for any 4p-norm with p 2 1, requires to compute dz(x) and (z) for every p individually. In this paper, exploiting this result and the geometrical arguments presented in Section 3 we show that it is possible to derive bounds the robustness (x) for any E o0) using only information on rı (x) and (z).
In the next section, we show that the straightforward usage of standard norms inequalities does not yield meaningful bounds on the ly-robustness inside the union of the 4 and lx- ball, since these bounds depend the dimension of the input space of the network.
3

---

Published as a conference paper at ICLR 2020
Figure 1: Visualization the lz-ball contained in the union resp. the convex hull of the
union of 1 and -alls in R First column: co-centric l--blll (blue) and ball (black). Second: in red the largest 1z-ball completely contained in the union of 41- and ball. in green the convex hull of the union of the 4- and la-la Fourth: the largest l2- ball (red) contained in the convex hull. The l2-ball contained in the convex hull is significantly larger than that contained in the union of 1 and -all.
Third:
MINIMAL 1N-NORM OF THE COMPLEMENT OF THE UNION OF 4 AND -BALL AND ITS CONVEX HULL
Let B1 = (o (- ||<||| I {)} and Bx = for E ER |>=lloo S co } be the 4-ball of radius > 0 and the -bal of radius eao > 0 respectively, both centered al the origin in RRd We also assume e1 (eoo, de so that Bi & Brx and B & B₁.
Suppose we can guarantee that the classifier does not change its label in U1 = B1 U Boo. Which guarantee does that imply for all intermediate lp-norms? This question can be simply answered by computing the minimal fy-norms over Rd U1,00, namely mingerd |I=l|p- By the standard norm inequalities it holds, for every Rd, that
|æ>l| 2 || and ||>|| 2 || d'>
and thus a naive application of these inequalities yields the bound
||<|| 2 max { { eld"
min U
(4)
However, this naive bound does not take into account that we know that ||>||| 2 e and ||~|| 2 6.0 Our first result yields the exact value taking advantage of this information.
Proposition 3.1 If d 2 2 and E (Eoo; d then
(a coc) $ (d- 1dp-1)p11)
min WER
ch
(5)
Thus a guarantee both for 4- and laalball yields a guarantee for all intermediate 1p-norms. However, for affine classifiers a guarantee for B₁ and Bx implies a guarantee wrt the convex hull C' of their union B1 U B This can be seen by the fact that an affine classifier generates two half-spaces, and the convex hull of set A is the intersection of all half-spaces containing A. Thus, inside C' the decision of the affine classifier cannot change if it is guaranteed not to change in B, and B as is completely contained in one of the half-spaces generated by the classifier (see Figure [ for illustrations of Bi, B their union and their convex hull). With the following theorem, we characterize, for any p 2 1, the minimal 1--norm over I&d \C.
Theorem 3.1 Let be the conner hall of B1 B If d 2 2 and e E (Eoo, deso), then
min ||=||, rER*
61
(6)
(4//rw a + a9)
where C1. 11.-10 - and 1 to
4

---

Published as a conference paper at ICLR 2020
|X||__ =1,
ratios, d=784
||X||__ d=3072
ratios, d=3072
[X]|
( C' ( (blue), U1,00 (red) and its naive lower bound (4) (green). We fix 6oc = and show the results varying 61 E (1, d), for d = 784 and d = 3072. We plot the value (or a lower bound in case of (4) of the minimal || depending on c,, given by the different approaches (first and third plots). The rod curves are almost completely hidden by the green ones, as they mostly overlap, but can be seen for small values of ||<r|] Moreover, we report (second and fourth plots) the ratios of the minimal ||ل|| for R conv( B1 U Boo) and Rd \\ (B1 Boo). The values provided by 6 are much larger than those of (5)
Figure 2: Comparison of the minimal (2-norm over R
Note that our expression in Theorem 3.1 is exact and not just lower bound. Moreover, the minimal distanee of Rd (C to the origin in Equation 6 is independent from the dimension d, in contrast to the expression for the minimal 1p-norm over R U1,50 in (5) and its naive lower bound in 4 which are both decrcasing for increasing d and p 1. In Figure 1 we compare visually the largest 1z-balls (in red) fitting inside cither U1 or the convex hull C in RR, showing that the one C is clearly larger. In Figure 2 we provide a quantitative comparison in high dimensions. We plot the minimal [g-norm over Rd \ C (6) (blue) and
over Rd \ U1,cc (5) (red) and its naive lower bound (4) (green). We fix || 6 = and vary 61 d,, with either d 784 (left) or d 3072 (right), i.c. the dimensions of the imput spaces of MNIST and CIFAR-10. One sees clearly that the blue line corresponding to (6) significantly higher than the other two. In the second and fourth plots of Figure we show, for each ε,, the ratio of the Iz-distances given by (6) and (5). The maximal ratio about 3.8 for d = 784 and 5.3 for with d (for more detailed analysis see A.3
3072, meaning that the advantage of increases
These two examples indicate that the la-balss contained in C' can be a few times larger than those in -1 Recall that we deal with piecewise affine networks. If we could enlarge the linear regions on which the classifier affine so that it contains the l and -bal of some desired radii, we would automatically get the ly-balls of radii given by Theorem 3.1 to fit in the linear regions. The next section formalizes the resulting robustness guarantees.
4 UNIVERSAL PROVABLE ROBUSTNESS WITH RESPECT TO ALL LN-NORMS
Combining the results of Theorems 2. and 3.1 in the next theorem we derive lower bounds the robustness of continuous piecewise alfine classifier J, e.g. ReLU network. at point x wrt any no-mr with p > 1 using only off (I), df(x), d (r) and d (x) (see (2
Theorem 4.1 Let de (x), d2(x)) be defined as in (2 and defone pt = min (d), (dP( (x) and Poo = m (x), dh (x)]}. If dd 2d2 2 and x is correctly classified, then
(x)x)= >
(D//p- a + 00)4/o'
for any p E oo), with a pn
e and 1 1=
Pro
Croce et al. (2019a) add a regularization term to the training objective in order to enlarge the values of d (x) and di (z) for a fixed p. with x being the training points (note that they optimize d3 (x) and not |d, (x=) to encourage correct classification).
Sorting increasing order dB p.l.j and dP.,, (sce (1), that is the Ip-distances the hyperplanes defining Q(x) and to decision hyperplanes, and denoting them as dB and dD respectively, p.s." p.x."
5

---

Published as a conference paper at ICLR 2020
the Marimum Margin Regularizer (MMR) of Croce al. 2019a is defined
kn Σ max (0,
(x) dB p.
d p.x. ) (x))
MM)-L2(0)=
(0,
(8)
KB
BB
kD
YD
It trics to push the ky closest hyperplanes defining ((x) farther than YB from and the ED closest decision hyperplanes farther than " from x both wrt the 1p-metric. In other words, MMR-1, aims at widening the linear regions around the training points so that they contain 4p-balls of radius either "/ or 7D centered in the training points. Using MMR-I, wrt fixed 1p-norm, possibly in combination with the adversarial training of Madry et al. (2018), leads to classifier which are empirically resistant wrt (p-adversarial attacks and are easily verifiable by state-of-the-art methods provide lower bounds on the true robustness.
For our goal of simultaneous (y-robustness guarantees for all p 2 1, we use the insights obtained from Thcorem 4.1 to propose a combination of MMR-11 and MMR-Ie; called MMR- Universal. It enhances implicitly robustness wrt every 1p-norm without actually computing and modifying separately all the distances d (z) and (z)x for the different values of
Definition 4.1 (MMR-Universal) Let x be a training point. We define the regularizer
kB
dB 1,
(x)
dB (x)
MMR- ((RVeerse))))())
1
max (0,
+ doo max (o, 00,
KB
712
Yo0
i=1
K-1 A max (0,1
d
(2))
dD
(x)
1
Aoo max (0,
00,01
K
n
700
(9)
where KB E (1....,N); N}, >,, 71 > 0.
We stress that, even if the formulation of MMR-Universal is based on MMR--p, is just thanks to the novel geometrical motivation provided by Theorem 3.1 and its interpretation in terms of robustness guarantees of Theorem 4.1 that we have a theoretical justification of
Moreover, are not aware of any other approach which can enforce simultaneously 1 and loo lue-guarattes, which is the key property of MMR-Universal.
The loss function which is minimized while training the classifier f is then, with {(x;, 16)) being the training set and CE the cross-entropy loss,
T
L (((a,) WTT = Σ CE((()). + MMR-Universal((z))
During the optimization our regularizer aims at pushing both the polytope boundaries and the decision hyperplanes farther than 71 in Iı-distance and farther than %oo in distannc from the training point x, in order to achieve robustness close or better than Y1 and Yoo respectively. According to Theorem 4.1 this enhances also the 1p-robustness for E (1, oo). Note that if the projection of æ on a decision hyperplane does not lie inside Q(x), de (x) is just an approximation of the signed distance to the true decision surface, in which case Croce lt al.] (2019a) argue that it is an approximation of the local Cross-Lipschits Lipschitz constant which is also associated to robustness (see Hein & Andriushchenko, (2017)). The regularization parameters Å and Ac are used to balance the weight of the 41- and T -tem in the regularizer, and also wrt the cross-entropy loss. Note that the terms MMR- MMR-Universee involving the quantities dD d (x) penalize misclassification,
they take negative values in this case.
Moreover, we take into account the ky closest hyperplanos and not just the closest one as done in Theorems 2. and 4.1 This has two reasons: first, in this way the regularizer enlarges the size of the linear regions around the training points more quickly and effectively, given the large number of hyperplanes defining each polytope. Second, pushing many hyperplanes influences also the neighboring linear regions of Qzz). This comes into play when, in order to get better bounds on the robustness at æ, one wants to explore also a portion the input space outside of the linear region Q(x), which is where Theorem 4.1 holds. As noted in
6

---

Published as a conference paper at ICLR 2020
Raghunathan et al. (2018): :: Croce et al. (2019a Xiao et al. 2019 established methods to compute lower bounds on the robustness are loose or completely fail when using normally trained models. In fact, their effectiveness is mostly related to how many ReLU units have stable sign when perturbing the input x within a given lp-ball. This is almost equivalent to having the hyperplanes far from in Ip-distance, which is what MMR- tries to accomplish. This explains why in Section [5] we can certify the models trained with MMRRUniversal with the methods of Wong & Kolter (2018) and Tjeng et al. (2019).
EXPERIMENTS
We compare the models obtained via MMR-Universal regularizer to state-of-the-art methods for provable robustness and adversarial training. As evaluation criterion we use the robusl. lest error; defined as the largest classification error when every image of the test set can be perturbed within a fixed set (e.g. an 1,-ball of radius ep) We focus on the by-balls with p o0). Since computing the robust test error in general an NP-hard problem, we evaluate lower and upper bounds on it. The lower bound is the fraction of points for which an attack can change the decision with perturbations in the (p-balls of radius (adversarial samples). that is with 1p-norm smaller than Cp. For this task we use the PGD-attack (Kurakin al. (017)); Madry et al. (2018); [Tammr Bonch (2019) and the FAB-attack (Croce & Hein (2019]) for 4, 12 and loc MIP (Tjeng et al. (2019) for loc. and the Linear Region Atlack CCroce el al. (2019b:) ) for l2 and apply all of them (see C.3 for details). The upper bound is the portion of test points for which cannot certify, using the methods of Tfjeng et al.] (2019) and WWog & Kolter (2018), that no 1y-perturbation smaller than Ep can change the correct class of the original input.
Smaller values of the upper bounds on the robust test error indicate models with better provable robustnoss. While lower bounds give empirical estimate of the true robustness, it has been shown that they can heavily underestimate the vulnerability of classifiers (e.g. by Athalye et al. (2018); Mosbach et al. (2018))
5.1 CHOICE OF
In choosing the values of En for p E 21 )o), we try to be consistent with previous literature (e.g. Wong & Kolter (2018) Croce et al. (2019a)) for the values of exo and ég. Equation 6 provides, given E and coo, value at which one expect l2-robustness (approxinately
). Then we fix 61 such that this approximation is slightly larger than the dcsired cg. We show in Table [ the values chosen for Cp. p {1, oo), and used to compute the Notice that for these values no la-ball is contained in the others.
robust test error in Table
Table 1: The values chosen for 6p on the different datasets and the expected Ig-robustness level (last column) given 61 and coo; computed according to (
dataset
61
62 by (
MNIST F-MNIST
1
0.1
0.3
0.3162
GTS
3
4/258
0.2
0,2170
CIFAR-10
2
2/255
0.1
0.1252
Moreover, we compute for the plain models the percentage of adversarial examples given by an lı-attack (we use the PGD-attack) with budget 61 which have also Iorm smaller than or equal to coo, and vice versa. These percentages being (provably) robust in the union of these L,- balls is much more difficult than in just one of them (see also C.1.
zero for all the datasets, meaning that
7

---

Published as a conference paper at ICLR 2020
Table 2: We report, for the different datasets and training schemes, the test error (TE) and lower (LB) and upper (UB) bounds on the robust test error (in percentage) wrt the union of 1p-norms for p E {1, 2, oo} denoted as + 11 + 6o0 (that the largest test error possible any perturbation in the union 4 + l2 + 1.0 is allowed). The training schemes compared are plain training, adversarial trainings of Madry
al. (2018); (Trmmrr & Boneh (2019) (AT), robust. training of Wong & Kolter (2018); Wong et al. (2018) (KW), MMI regu aagularization of Croce et al. (0119a), MMR combined with AT (MMR+AT) and our MMR- Univeraal regularization. The models of our MMR- Universal are the only ones which have non trivial
upper bounds on the robust test error for all datasets.
provable robustness against multiple perturbations
4 +
l2
+
loc
+
l2
+
loc
model
TE
LB
UB
TE
LB
UB
plain
0.85
88.5
100
9.32
100
100
AT
0.82
4.7
100
11.54
26.3
100
AT-12
0.87
25.9
100
8.10
98.8
100
(T-(,,,,,,s
0.80
1.9
100
F-MNIST
14.13
29.6
100
KW-1o0
MNIST
1.21
4.8
100
21.73
43.6
100
KW-12
1.11
10.3
100
13.08
66.7
86.8
MMR-
1.65
10.4
100
14.51
36.7
100
MMR-12
2.57
78.6
99.9
12.85
95.8
100
MMR++TT-1
1.19
4.1
100
14.52
31.8
100
MMR++AD
1.73
15.3
99.9
13.40
66.5
99.1
MMR- Universal
3.04
12.4
20.8
18.57
43.5
52.9
plain
6.77
71.5
100
23.29
88.6
100
AT
6.83
64.0
100
27.06
52.5
100
AT-12
8.76
59.0
100
25.84
62.1
100
AT-(11, 100)
8.80
45.2
100
CIFAR-10
35.41
57.1
100
KW-1
15.57
87.8
100
38.91
51.9
100
GTS
KW-12
14.35
57.6
100
40.24
54.0
100
MMR-130
13.32
71.3
99.6
34.61
58.7
100
MMR-12
14.21
62.6
80.9
40.93
72.9
98.0
14.89
82.8
100
35.38
50.8
100
MMR+AT-E
15.34
58.1
84.8
37.78
61.3
99.9
MMR-Universal
15.98
51.6
52.4
46.96
63.8
64.6
5.2 MAIN RESULTS
We train CNNs MNIST, Rashion-MNISS (Xiao et al. (0117) German Traffic Sign (GTS)
Stallkamp et al. (012 and CIFAR-10 (Krizhevsky et al. (2014) We consider several
training schemes: plain training, the PGD-based adversarial training (AT) of Madry et al.
2018) and its extension to multiple balls in Tramèr & Boneh (2019), the robust training
KW) of Wong & Kolter (2018); WWng et al. (2018), the MMNl--ggullrizedd training (MMR) of Croce et al. (2019a). either alone or with adversarial training (MMR+ATT and the training with our regularizer MMR-Uniiersal. We use AT, KW, MMR and MMR+AT wrt l2 and loo. as these are the norms for which such methods have been used in the original papers. More details about the architecture and models C
In Table 2 we report test crror (TE) computed on the whole test set and lower (LB) and upper (UB) bounds on the robust test error obtained considering the union of the three balbal,, indicated by 1 + 12 + l.x. (these statistics are the first. 1000 points of the test set). The lower bounds I, + l/ -BB are given by the fraction of test points for which one of the adversarial attacks wrt 4, and loo is successful. The upper bounds I + l2 + -UB are computed as the percentage of points for which at least one of the three la-balls not certified to be free of adversarial examples (lower is better). This last one is the metric of main interest, since we aim at universally provably robust models. In C.2 we report the lower and upper bounds for the individual norms for every model.
Code available at https:///ttthhaeee http:///gtthaaa.ooo//sa///mmmmmt

---

Published as a conference paper at ICLR 2020
MMR-Universal is the only method which can give non-trivial upper bounds on the robust test error for all datasets, while almost all other methods aiming at provable robustness have 4 + l2 -UB close to or at 100%. Notably, test error of MMRRUniverssl is lower than the lower bound of all other methods except (,, showing that MMRRUniversal provably outperforms existing methods which provide guarantees wrt individual lp-balls, either l2 or lso; when certifying the union 4 12+2++1e +oo The test error slightly increased wrt the other methods giving provable robustness, but the same holds true for combined adversarial training 12, loc) compared to standard adversarial training AT- We conclude that MMR- Universal the only method so far being able to provide non-trivial robust.ness guaranlees for nultiple 1y-balls in the case that none of them contains any other.
GTS the upper bound the robust
12,
CONCLUSION
With MMR-Universal we have proposed the first method providing provable robustness guarantees for all 1p-balls with p 2 Compared to existing works guaranleeing robustiess wrt either l2 lxo, providing guarantees wrt the union of different lp lp-balls turns out to be considerably harder. It is an interesting open question if the ideas developed in this paper can be integrated into other approaches towards provable robustness.
ACKNOWLEDGEMENTS
We would like to thank Maksym Andriushchenko for helping us to set up and adapt the original code for MMR. We acknowledge support from the German Federal Ministry of Education and Research (BMBF) through the Tübingen AI Center (FKZ: 01IS18039A). This work was also supported by the DFG Cluster of Excellence "Machine Learning New Perspectives for Science", EXC 2064/1, project number 390727645, and by DFG grant 389792660 as part of TRR 248.
REFERENCES
R. Arora, A. Basuy, P. Mianjyz, and A. Mukherjee. Understanding deep neural networks with rectified lincar unit. In ICLR, 2018.
A. Athalye, N. Carlini, and D. A. Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In JCML, 2018.
O. Bastani, Y. Ioannou, L. Lampropoulos, D. Vytiniotis, A. Nori, and A. Criminisi. Mcasuring neural net robustness with constraints. In NIPS, 2016.
T. B. Brown, D. Mané, A. Roy, M. Abadi, and J. Gilmer. Adversarial patch. In NIPS 2017 Workshop on Machine Learning and Computer Security, 2017.
N. Carlini and D. Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In ACM Workshop on Artificial Intelligence and Security, 2017.
F. Croce and M. Hein. A randomized gradicnt-froe attack on relu networks. In GCPR, 2018.
F. Croce and M. Hein. Minimally distorted adversarial examples with a fast adaptive boundary attack. preprint, arXiv:1907.0000 2019.
F. Croce, M. Andriushchenko, and M. Hein. Provable robustness of relu networks via maximization of linear regions. In AISTATS, 2019a.
F. Croce, J. Rauber, and M. Hein. Scaling up the randomized gradient-free adversarial attack reveals overestimation of robustness using established attacks. International Journal of Computer Vision, 1-19, 2019b.
L. Engstrom, B. Tran, D. Tsipras, L. Schmidt, and A. Madry. A rotation and translation suffice: Fooling CNNs with simple transformations. In NIPS 2017 Workshop on Machine Learning and Computer Security, 2017.

---

Published as a conference paper at ICLR 2020
R. Geirhos, P. Rubisch, C.Michaelis, M. Bethge, F. A. Wichmann, and W. Brendel. Imagenet- trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness. In ICLR, 2019.
I. J. Goodfellow, Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic, T. A. Mann, and P. Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. preprint, arXIv:1810.1271533, 2018.
S. Gu and L. Rigazio. Towards deep neural network architectures robust to adversarial examples. In ICLR Workshop, 2013.
M. Hein and M. Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In NIPS, 2017.
D. Hendrycks and T. Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In ICLR, 2019.
R. Huang, B. Xu, D. Schuurmans, and C. Szepesvari. Learning with a strong adversary. In ICLR, 2016.
D. Kang, Y. Sun, T. Brown, D. Hendrycks, and J. Steinhardt. Transfer of adversarial robustness between perturbation types. preprint, arXiv:1905.01084 2019.
G. Katz, C. Barrett, D. Dill, K. Julian, and M. Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In CAV, 2017.
D. P. Kingma and J. Ba. Adam: method for stochastic optimization. preprint, arXiv:1412.6950, 2014.
A. Krizhevsky, V. Nair, and G. Hinton. Cifar-10 (canadian institute for advanced research). 2014. URL http://www.. cs. toronto. www.otoooeooooooooooooo www.-krii/cifar..... html
A. Kurakin, T. J. Goodfellow, and S. Bengio. Adversarial examples in the physical world. In JCLR Workshop, 2017.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Valdu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
M. Mirman, T. Gehr, and M. Vechev. Differentiable abstract interpretation for provably robust. neural networks. In ICML, 2018.
M. Mosbach, M. Andrinshchenko, T. Trost, M. Hein, and Klakow. Logit pairing methods can fool gradicnt-basee attacks. In NeurIPS 2018 Workshop on Security in Machine Learning, 2018
N. Papernot, P. McDonald, X. Wu, S. Jha, and A. Swami. Distillation as a defense to adversarial perturbations against deep networks. In IEEE Symposium Security & Privacy, 2016.
A. Raghunathan, J. Steinhardt, and P. Liang. Certified defenses against adversarial examples. In ICLR, 2018.
L. Schott, J. Rauber, M. Bethge, and W. Brendel. Towards the first adversarially robust neural network model on MNIST. In ICLR, 2019.
Y. Sharma and Chen. Attacking the madry defense model with 4 based adversarial examples. Tn ICLR Workshop, 2019.
J. Stallkamp, M. Schlipsing, J. Salmen, and C. Igel. Man computer: Benchmarking machine learning algorithms for traffic sign recognition. Neural Networks, 32:323-34 -322, 2012.
10

---

Published as a conference paper at ICLR 2020
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In ICLR, pp. 2503-2511, 2014.
V. Tjeng, K. Xiao, and R. Tedrake. Evaluating robustness of neural networks with mixed integer programming. In ICLR, 2019.
F. Tramèr and D. Boneh. Adversarial training and robustness for multiple perturbations. In NeurIPS, 2019.
E. Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In JCML, 2018.
E. Wong, F. Schmidt, J. H. Metzen, and J. Z. Kolter. Scaling provable adversarial defenses. In NeurIPS, 2018.
H. Xiao, Rasul, and R. Vollgraf. Fashion-MNIST: novel image datasct for benchmarking machine learning algorithms. preprint, arXiv:1708.07747, 2017.
K. Y. Xiao, V. Tjeng, N. M. Shafiullah, and A. Madry. Training for faster adversarial robustness verification via inducing relu stability. In ICLR, 2019.
S. Zheng, Y. Song, T. Leung, and T. J. Goodfellow. Improving the robustness of deep neural networks via stability training. In CVPR, 2016.
11

---

Published as a conference paper at ICLR 2020
A MINIMAL 12-NORM OF THE COMPLEMENT OF THE UNION OF 4 AND 1B-LLLL AND ITS CONVEX HULL
A.1 PROOF OF PROPOSITION 3.1
Proof. We first nole that for 61 < e holds B₁ C Bs and the proof follows from the standard inequality Iæ||, 2 ||=||oo where equality is attained for Exos, where e, are standard basis vectors. Morcover, if 61 > dex it holds B B1 as max ||]|| dc and the result follows by ||=||, 2 || d 1= The equality is realized by the vector with all the entries equal to /-
For the second case we first note that using Hölder inequality (u, U) S Iull Illll where 1, it holds
k
S
ko.
Let x E R4. Without loss of generality after a potential permutation of the coordinates it holds |mal |00ll Then we get
E [x;|]
|
P = l +
Laaa 2
| +
(d 1)
We have
Σ |z,] p
co + (el c
min |
<al? +
(d 1)
(d - 1)p-1'
noting that Janal = || and Σ Finally, we note that the vector
El E0o.
d-1
Σ iml
6 6oc
Ei + Eoo
d -
realizes equality, Indeed, ||el| = (d - 1) ((--x)) y'
+ eb which finishes the proof.
(d-1)P
A.2 PROOF OF THEOREM 3.
Proof. We first note that the minimum of the norm over Rd \ C lies on the boundary of C (otherwise any point on the segment joining the origin and y and outside C would have 1p-norm smaller than y). Morcover, the faces of C are contained in hyperplancs constructed as the affine hull of subsct of points from the union of the vertices of B₁ and B The vertices of B, are Vi = {Eles, -ejes
I,....d) d), where ei is the i-th element of the standard basis of IRd, and that of B. are Vae, consisting of the vectors whose components are elements of fex. - }. Note that Vio 0. Any subset of d vertices from Vi Voe defines a hyperplane which contains a face of if does not contain any point of the interior of C.
Let S be a set of vertices defining hyperplane containing a face of C. We first derive conditions on the vertices contained in S. Let k = ei
E N and a = = - E [0, 1). fx
For
Note that le + 1 بن Then no more than k vertices of B₁ belong to S, that is to a face of C. In fact, if we consider k + 1 vertices of B1, namely wlog {ELE),..., el }, and consider their convex combination 2 é1 k+1 e then || 2 < Exo by the definition of k. Thus S cannot contain more than & vertices of Bi.
Second, assume Gej is in S. If any vertex of Boo with uy -coo is also in S fxe E (0, 1), we get then, with a' = att | (1 a')ullso max(lo'e (1 a' a')coo 1, (1 a')ccc)
12

---

Published as a conference paper at ICLR 2020
where a1)o c and
Ja'e1 ("= l + 6xc)
- 600 Eoc
Thus S would not span a face as a convex combination intersects the interior C. This implies that if (iez is in S then all the vertices of B in S need to have f/ <5o, otherwise S would not define a face of C. Analogously, if -Eje E S then any vertex v of Bo in S has V/ -oo- However, we note that out of symmetry reasons we can just consider faces of C' in the positive orthant and thus we consider in the following just sets S which contain vertices of "positive type" G16,
Let now be a set (not necessarily defining a face of C) containing h S k vertices of Bi and d - h vertices of B and P the matrix whose columns are these points. The matrix has the form
11
0
60o
600
0
1
600
600
P
0
0
6xc
A
0
where A E igd-h.dhh is a matrix whose entries are either 6go or -Eco- the matrix P does not have full rank then the origin belongs to any hyperplane containing S, which means it cannot be a face of C. This also implics A has full rank if S spans a face of C.
We denote by ा the hyperplane generated by the affine hull of (the columns of P) assuming that A has full rank. Every point b belonging to the hyperplane generated by S is such that there exists unique a E Rd which satisfies
E1
Exc
Eoc
1
0
Coc
1i,d P
1 b
Pla =
a =
b',
El
6oo
6oc
0
A
0
where ldi,d is the matrix of size d1 d2 whose entries are The matrix (P'.8) e Id+1Id-1 need not have full rank, so that
(P',,PP",,'" bD) = dim rankP' = rank(P',
and then the linear system P'a = // has unique solution.
We define the vector U e Rd as solution of pT o = 1a,1, which is unique as P has full rank.
From their definitions we have Pa = and 1 a = 1, so that
1 = 1 a (P" 0) = v" Pa v
and thus
(b. =
(10)
noticing that this also implics that any vector b E Rd such that (b, u) 1 belongs (suppose that 3q & with (g. = 1, then define as the solution of Pe = and then 1 = (q, = (Pc, v) = (c. pfu) (c, 1) which contradicts that $ π))
Applying Hölder incquality to 10 we get for any be n,
|bb|]
(11)
|
where 1 Morcover, p (1, there exists always point d" for which equality.
11 holds
13

---

Published as a conference paper at ICLR 2020
In the rest of the proof compute ||ell for any when S is face of C' and then 11 yields the desired minimal value of | over all lying in faces of C.
Let U2), 1s Rh, 02 It holds
Rd- and In denotes the identity matrix of R.A.
pTu= = Coold-ni
AT )
0
22 )
1
)
1d,1,
1d-h,,
which implics
01
1
_ and
A U/2 = 1d-h,
heo
1 dh = (1
Eoc
1
Moreover, we have
h
1 [lu22llss
|elll || 1l + |122l1
112ll1
|1ll. max
(12)
61
If S generates face, then by definition x does not intersect with the interior of C and thus it holds for all b E æ: [[6]] 2 é1 and |16]l Eoo. Suppose ||e|]
_. Then there exists
d" such equality in Hölder's equality is realized, that is 1 (b",u) < = | ll ||ell, and thus |bb"|| = < co; which contradicts ||b 6oc for all b E and thus must hold
||ll| S co. Similarly, one can derive ||u| S 1. Combining 12 with the just derivod inequalities we get upper bounds on the norms of U2,
1 h and |12 S -
(13)
Eoo E1
E1
Furthermore 02 is defined as the solution of
AT
1
h ) E
1/2 =
18-h.1
600
We note that all the entries of A each row of AT and v2 is a lower bound on the 4--ormm of U2. Since every entry of the r.h.s. of the linear system is A we get ||22|1 _ -__ h fxx
foo are either or -1, that the inner product between
Tx q. which combined with (13 leads to
||u2|l1 =
This implies that A" = |12ll In order to achieve equality (u, = ||]| it has to hold u, = (g) for every * 0. If at least two components of v were non-zero, the corresponding columns of AT would be identical, which contradicts the fact that AT has full rank. Thus 122 can only have one non-zero component which in absolute value is equal to 1 A Thus, after a potential reordering the components, v has the form e1
h
V
O,
60o
times
From the second condition in we have
< and + 2 a = Recalling
ki we have
hE ak 1, N.
This means that, in order for S to define a face C, we need h == k if > h (k 1, if a 0 (in this case choosing h = k or h k leads to the samn v, so in practice it is possible to use simply h for any a).
Once we have determined v, we can use again 10 and 11
to see that
| 2 |1ll,
61
(14)
kk + (22 2)))² (
(4/en - a + 3/
14

---

Published as a conference paper at ICLR 2020
Finally, for any there exists b* for which equality is achieved in (14) Suppose that this br does not lie in a face of C. Then one could just consider the line segment from the origin to b* and the point intersecting the boundary of C' would have smaller l n--orrm contradicting the just derived inequality. Thus the b" realizing equality in (14) lies in a face of C.
A.3 COMPARISON OF THE ROBUSTNESS GUARANTER FOR THE UNION OF B1 AND Boo IN 5 AND THE CONVEX HULL OF B1 AND Bo IN G
We compare the robustness guarantees obtained by considering the union of B1 and Bx (denoted by by in the following), see (5), and the convex hull of B1 and Bx (denoted by be in the following), see 6 In particular, want to determine the ratio 8 a E [1, for <=
which the gain in the robustness guarantee be for the convex hull is maximized compared to just considering the robustness guarantee by as a function of the dimension d of the input space. We restrict here the analysis to the case of p = 2, that is computing the radius of the largest lz-ball fitting inside 01,00 or its convex hull C. Let us denote
(el - Exc 1e1-6x))")
by
min 1 U
&
(d 1)p-T)
be min ZERRIC
| (4/ew + a2)
the two bounds from 5 and
6 respectively, which can be rewritlen
(6 - 1)P bc(d)
6
by (6) 60o
Exo
(d 1)p-1
(ō - a + ag)
where 5 18]. We note that
- 1 S 8 + a = [0] + (6 181) 8.
As the differences are very small, we use instoad the lower bound
(0) = 6 0z
(6)
We want to find the value 8 which maximizes
th (d) varying (a numerical evaluation is
by
presented in Figure 2 Notice first that 5* maximizes also
(5)) = (1 1 (6-1)² -1 (by (
(1
(d - 1)p-1 21 1
and can be found as the solution of a (O))
a
(6 - 1)P
l
1 +
05 (O))
06
(d - 1)p-I
(8 1)2
-1
[8 (8-1) 1)P
-2 p(6 1)p-1
1 +
1+
(d - 1)p-1 = 0,
(d - 1)p-1
(d - 1)p-1)
which is equivalent to
(d 1)p-1 + (6 1)p p8 1)0 0.
Restricting the analysis to p- 2 for simplicity, we get
d d-1 + (0 - 1)2 26(6 - 1) = 82 + d== 0 and one can check that 5* is indeed a maximizer. Moreover, at 8" we have a ratio between the two bounds
8' Vd.
bc
bg by
dà - 1)
(v 1)2
di
by
V2
1s-
We observe that the improvement of the robustness guarantee by considering the convex hull instead of the union is increasing with dimension and is v 3.8 for d = 784 and x 5.3 for = 3072. Thus in high dimensions there is a considerable gain by considering the convex hull.
15

---

Published as a conference paper at ICLR 2020
B UNIVERSAL PROVABLE ROBUSTNESS WITH RESPECT TO ALL b NO-MSS
B.1 PROOF OF THEOREM
Proof. From the definition of d (x) and dp (a: we know that none of the hyperplanes {m²}; (either boundaries of the polytope Q(x) or decision hyperplanes) identified by V and v(), I -=..... L + 1, is closer than min (z), (x))) in 1y-distance. Therefore the interior of the 41-ball of radius P1 (namely, B1 (zz P1)) and of the -b-ll of radius Poo (B (oo)) centered x does not intersect with any of those hyperplancs. This implics that { are
intersecting the closure of R conv(B1(2, P1) B (x, Px))). Then, from Theorem 3.1 we
get
(d) (x)]3
P (m/p= + ag)
Finally, exploiting Theorem 2.1 rp(x) 2 min d (s),1d (00((() (x)]} holds.
C EXPERIMENTS
C.1 CHOICE OF Ep
In Table B we compute the percentage of adversarial perturbations given by the PGD-attack wrt lp with budget Ep which have n--ormm smaller than Eq, for q * p (the values of ep and Eq used are those from Table [). We used the plain model of each dataset.
The most relevant statistics of Table 3 are about the relation between the li- and 1x- perturbations (first two rows). In fact, none the adversarial examples wrt 4 is contained in the -bll, and vice versa. This means that, although the volume of the 41-ball is much smaller, even because of the intersection with the box constraints [0, 1]d, than that the ball in high dimension, and most of it is actually contained in the 1 -all, the adversarial examples found by l-aattccks are anyway very different from those got by -as-att The choice of such ep is then meaningful, the adversarial perturbations we are trying to prevent wrt the various norms are non-overlapping and in practice exploit regions of the input space significantly diverse one from another.
Moreover, one can see that also the adversarial manipulations wrt 1 and l2 do not overlap. Regarding the case l2 and 1 for MNIST and F-MNIST it happens that the adversarial examples wrt l2 are contained in the -bl. However, one observes in Table 4 being able to certify the -ball not sufficient the models trained on these datasets to be provably robust wrt the lo -orm, that is KW- MMR- and MMR+AT-Iss. have upper bounds on the robust test error in the ba-ball larger than 99%, despite the values of the lower bounds small (which means that the attacks could not find adversarial perturbations for many points).
get non-trivial guarantees wrt l2. In fact, all
Such analysis confirms that empirical and provable robustness two distinct problems, and the interaction of different kinds of perturbations, ions, as we have, changes according to which of these two scenarios considers.
Table 3: Percentage of li-avversarial examples contained in the lo.-ball and vice versa.
MNIST
F-MNIST
GTS
CIFAR. 10
h-perturbations with horm S 6.o (%)
0.0
0.0
boo be-perturbations with 4--orm (%)
0.0
0.0
0.0
0.0
1 4-perturbations with 1g-norm $ fg (%)
4.5
7.4
0.0
0.0
b-perturbations with 4.-ormm
(%)
0.0
0.0
0.0
0.0
d--peruuraation with l.. & 6oo (%)
100.0
100.0
0.3
16.0
perturbations with 12-norm 62 (%)
0.0
0.0
0.0
0.0
16

---

Published as a conference paper at ICLR 2020
C.2 MAIN RESULTS
In Table we report, for each dataset, the test error and upper and lower bounds on the robust test error, together with the Cp used, for each norm individually. It is clear that training for provable 1n-robustness (expressed by the upper bounds) does not, in general, yield provable ly-robustness for & even in the case where the lower bounds are small for both p and q.
In order to compute the upper bounds on the robust test error in Tables 2 and 4 we use the method of Wong & Kolter (2018) for all the three 1p-norms and that of Tieng et al. (2019) only for the norm. This second one exploits a reformulation of the problem in 13 in terms of mixed integer programming (MTP), which able to exactly compute the solution of (3) for p E (1, 2, oo}. However, such technique is strongly limited by its high computational cost. The only reason why it is possible to use it in practice is the exploitation of some presolvers which are able to reduce the complexity of the MIP. Unfortunately, such presolvers are effective just wrt 100. On the other hand, the method of Wong & Kolter (2018) applies directly to every lp-norm. This explains why the bounds provided for loo are tighter than those for / and l2.
C.3 EXPERIMENTAL DETAILS
The convolutional architecture that we use is identical to Wong & Kolter (018)) which consists of two convolutional layers with 16 and 32 filters of size x 4 and stride 2, followed by a fully connected layer with 100 hidden units. The AT- AT-12, KW, MMR and MMR+AT training models are those presented in Croce et al. 2019a) and available at https We trained the (1-(11,22,6<) performing for each batch of the 128 images the PGD-attack wrt the three norms (40 steps for MNIST and F-MNIST, 10 steps for GTS and CIFAR-10) and then training on the point realizing the maximal loss (the cross-entropy function is used), for 100 epochs. For all experiments with MMR-Universee
//github. cow/max--ndeaeccccoc pttp://bbl-oouuuteeestteeeeeeeee massss-max-lae m
we use batch size 128 and we train the models for 100 epochs. Moreover, we use Adain optimizer of Kingma & Ba (014) with learning rate of 5 x 10-4 for MNIST and F-MNIST, 0.001 for the other datasets. We also reduce the learning rate by a factor of 10 for the last 10 epochs. On CIFAR-IU 10 dataset we apply random crops and random mirroring of the images as data augmentation. For training we use MMR-Universal as in (9) with ky lincarly (wrt the epoch) decrcasing from 20% to 5% of the total number of hidden units of the network architecture. We also use training schedule for Ap where we linearly increase it from >p/10 to Ap during the first 10 epochs. We employ both schemes since they increase the stability of training with MMR. In order to determine the best set of hyperparameters λ1. Aso, n, and %oo of MMR, we perform a grid search over them for every dataset. In particular, we empirically found that the optimal values of Yp are usually between 1 and 2 times the Ep used for the evaluation of the robust test error, while the values of Xp are more diverse across the different datasets. Specifically, for the models we reported in Table 4 the following values for the (A1, Aoe) have been used: (3.0, 12.0) for MNIST, (3.0, 40.0) for F-MNIST, (3.0, 12.0) for GTS and (1.0, 6.0) for CIFAR-10.
In Tables 2 and ! while the test error which is computed on the full test set, the statistics regarding upper and lower bounds on the robust test error are computed on the first 1000 points of the respective test. sets. For the lower bounds we use the FAB-attack with the original parameters, 100 iterations and 10 restarts. For PGD we use also 100 iterations and 10 restarts: the directions for the update step the sign of the gradient for loc. the normalized gradient for l/ and the normalized sparse gradient suggested by Tramer Boneh (201)) with sparsity level 1% for MNIST and F-MNIST, 10% for GTS and CIFAR-10. Finally we use the Liner Region Attack as in the original codc. For MIP (Tjeng et al. (2019) we use timcout of 120s, that means if guarantee is obtained by that time, the algorithm stops verifying that point.
17

---

Published as a conference paper at ICLR 2020
Table 4: We report, for the different datasets and training schemes, the test error (TE) and lower (LB) and upper (UB) bounds on the robust test error (in percentage) wrt the fy-norms at thresholds Ep, with 1,2, 30 (that the largest test error possible if any perturbation of no-ormm equal to Ep is allowed). Moreover
show the 4 + 4 + + that is the upper bound on the robust error when the allacker allowed to use the union of the three L-balls..
The training schemies compared are plain training, adversarial training of Madry et al.
(2018
Tramèr & Boneh (2199) (AT), robust training of Wong Kolter (2018) Wong et al. 10018
(KW), MMR regularization of Croce et al (2019a), MMR combined with AT (MMR++ AT)
and our LMMR-Universal regularization. One can clearly see that our MMR- Unin-ualiersal models
the only ones which have non trivial upper bounds the robust test error wrt all the
considered norms.
provable robustness against multiple perturbations
l
Lo0
1
+
l2
Loo
model
TE
LB
UB
UB
LB
UB
MNIST
62
0.3
6oc
0.1
plain
0.85
2.3
100
3.1
100
88.5
100
88.5
100
AT-L
0.82
1.8
100
1.7
100
4.7
100
4.7
100
AT-12
0.87
2.1
100
2.2
100
25.9
100
25.9
100
AT-(h, (1,,22,00))
0.80
2.1
100
1.7
100
4.9
100
4.9
100
KW-Loo
1.21
3.6
100
2.8
100
4.4
4.4
4.8
100
KW-12
1.11
2.4
100
2.3
6.6
10.3
10.3
10.3
100
MMR-lcc
1.65
10.0
100
5.2
100
6.0
6.0
10.4
100
MMR--2
2.57
4.5
62.3
6.7
14.3
78.6
99.9
78.6
99.9
MMR++AT-.
1.19
3.6
100
2.4
100
3.6
3.6
4.1
100
MM-++AT-1
1.73
3.6
99.9
3.7
12.1
15.3
76.8
15.3
99.9
MMR- Universal
3.04
6.4
20.8
6.2
10.4
12.4
12.4
12.4
20.8
F-MNIST
C2
0.3
0.1
plain
9.32
31.3
100
65.8
100
100
100
100
100
AT-
11.54
19.0
100
17.1
100
25.4
73.0
26.3
100
AT-12
8.10
15.9
100
20.6
100
98.8
100
98.8
100
AT (2-,41,22,o0)
14.13
22.2
100
20.3
100
28.3
98.6
29.6
100
KW
21.73
42.7
100
30.5
99.2
32.4
32.4
43.6
100
KW-12
13.08
15.8
19.8
15.9
19.9
66.7
86.8
66.7
86.8
MMR--ac
14.51
28.5
100
23.5
100
33.2
33.6
36.7
100
MMR--2
12.85
18.2
39.4
24.8
33.2
95.8
100
95.8
100
AT-+AAT->>
14.52
27.3
100
22.9
100
27.5
30.7
31.8
100
MM-+AT-12
13.40
17.2
55.4
20.2
37.8
66.5
99.1
66.5
99.1
MMR Universal
18.57
25.0
52.4
24.3
37.4
43.5
44.3
43.5
52.9
GTS
3
0.2
1/255
plain
6.77
60.5
100
38.4
99.3
71.1
98.4
71.5
100
AT-l
6.83
64.0
100
24.9
99.2
31.7
82.3
64.0
100
AT-I2
8.76
44.0
100
27.2
98.4
58.9
97.1
59.0
100
NT-(11,22,10)
8.80
41.8
100
24.0
93.7
41.2
79.4
45.2
100
KW-1o0
15.57
87.8
100
41.1
77.7
36.1
36.6
87.8
100
KW-12
14.35
46.5
100
30.8
35.3
57.0
63.0
57.6
100
MMR-
13.32
71.3
99.6
40.9
41.7
49.5
49.6
71.3
99.6
MMR-12
14.21
54.6
80.4
36.3
36.6
62.3
63.6
62.6
80.9
AT---
14.89
82.8
39.9
38.3
38.4
82.8
100
MMR+AT-1,
15.34
49.4
81.3
33.2
33.8
57.2
60.2
58.1
84.8
MMR-Universe
15.98
49.7
51.5
34.3
47.0
47.0
51.6
52.4
CIFAR-10
2
C2
0.1
6oo
3/255
plain
23.29
61.0
48.9
100
88.6
88.6
100
AT-I
27.06
39.6
100
33.3
99.2
52.5
88.5
52.5
100
AT-12
25.84
41.9
35.3
99.9
62.1
99.4
62.1
100
(1-1,,,,,,1
35.41
47.7
100
41.7
88.2
57.0
76.8
57.1
100
KW-1.
38.91
51.9
39.9
66.1
46.6
48.0
51.9
100
KW-12
40.24
47.3
100
44.6
49.3
53.6
54.7
54.0
100
MMR--ac
34.61
54.1
42.3
57.7
61.0
58.7
100
MMR-12
40.93
58.9
98.0
50.4
56.3
72.9
86.1
72.9
98.0
MMR++AT-4.
35.38
50.6
41.2
48.7
54.2
50.8
100
AMR+AAT-4,
37.78
50.4
99.9
46.1
54.2
61.3
74.1
61.3
99.9
MMR- Universal
46.96
56.4
63.4
51.9
63.8
63.8
63.8
64.6

---

Published as a conference paper at ICLR 2020
MNIST
F-MNIST
19st error
UB
UB
UB
Union-UB
epoch
epoch
GTS
CIFAR-10
100
100
38
6
epoch
epoch
Figure 3: We show, for each dataset, the evolution of the test error (red), upper bound (UB) on the robust test error wrt 4 (black), l2 (cyan) and lc (blue) during training. Moreover, report in green the upper bounds on the test error when the attacker is allowed to exploit the union of the three ba-ba... The statistics on the robustness are computed epoch and then every 10 epochs on 1000 points with the method of Wong & Kolter (2018). using the models trained with MMR-Universal.
10
C.4 EVOLUTION OF ROBUSTNESS DURING TRAINING
We show Figure 3 the clean test. error (red) and the upper bounds on the robust test error wrt 4 (black), l2 (cyan), loo (blue) and wrt the union of the three 4p-balls (green), evaluated at epoch 1, 2, 5, 10 and then every 10 epochs (for each model we train for 100 epochs) for the models trained with our regularizer the test crror is computed on the whole test set, while the upper bound on the robust test error is evaluated
AMMR-Universal. For each dataset used in Section
the first 1000 points of the test set using the method introduced in Wong & Kolter (2018) (the thresholds E,, É2, 6ao are those provided in Table 1 Note that the statistics
To are not evaluated additionally with the MIP formulation of Tieng al.) (2019) the results in the main paper which would improve the upper bounds wrt loo. For all the datasets the test error keeps decreasing across epochs. The values of all the upper bounds generally improve during training, showing the effectiveness of MMR-Uniiersal..
C.5 OTHER COMBINATIONS OF MMR AND AT
We here report the robustness obtained training with MMR-1,+AT-I, with & on MNIST. This means that MMR used wrt lp. while adversarial training wrt 4 In particular we test P.q E 00). In Table 5 we report the test error (TE), lower (LB) and upper bounds (UB) on the robust test error for such model, evaluated wrt 4, l2, Lo and 4 + l2 + lx as done in Section 5 It is clear that training with MMR wrt single norm does not suffice to get provable guarantees in all the other norms, despite the addition of adversarial training. In fact, for both the models analysed the UB equals 100% for at least one norm. Note that the statistics wrt Lo in the plots do not include the results of the MIP formulation of Tieng et. al. (2019).
19

---

Published as a conference paper at ICLR 2020
Table Robustness other combinations of MMR and AT.
l2
loc
I1 + 12 + loc
model
TE
LB
UB
LB
UB
LB
UB
LB
UB
MMR-1++AT-
0.99
2.5
15.7
2.6
25.4
9.4
100
9.4
100
MIMR-6&AAT-L
1.43
2.7
100
2.3
100
5.6
30.2
5.6
100
C.6
LARGER MODELS
We trained models with MMR-Universa. also on the 'Large" architecture from Wong et al. (2018), but we could not achieve significant improvement compared to the smaller networks reported the main paper. Note that the verification becomes the more expensive the larger the network is. Thus for the results in Table 0 we use only the method of [Wng & Kolter (2018) to compute the UB on the robust test error (we do not additionally use Tjeng et al. (2019) for the statistics relative to the -oc-ruuussssss which yields tighter upper bounds), which explains why the results are seemingly worse than those in Table 2
Table 6: MMR- Universl models trained on the 'Large" architecture from Wong et al. 2018 with the same Cp as in the experiments in Section For the robuustes in this case the method Tjeng et al. (019 is not used.
MMR- Universal models with larger architecture
l
loo
4 + l +
100
model
TE
LB
UB
LB
UB
MNIST
2.20
4.6
11.2
4.2
6.9
8.8
48.8*
8.8
48.8
F-MNIST
19.20
29.8
47.6
25.5
34.2
43.6
64.4*
43.7
64.5
GTS
17.40
45.8
54.8
32.1
36.9
47.5
58.3*
49.8
60.1
CIFAR-10
45.09
48.6
63.3
46.0
48.9
57.1
69.6*
57.1
69.9
20


Reviews:
[{"review_id": "ryegXTSpYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overview:\n\nThe paper is dedicated to developing a regularization scheme for the provably robust model. The author proposes the MMR-Universal regularizer for ReLU based networks. It enforces l1 and l infinity robustness and leads to be provably robust with any lp norm attack for p larger than and equal to one.\n\nStrength Bullets:\n\n1. Using convex hull to enforce robustness, it is very reasonable and straightforward which highly aligns our intuition.\n2. The author provides detailed and conniving derivations and proof. And the results in table 2 do achieve the state-of-the-art provable robustness.\n3. It is the first robust regularizer that is able to provide non-trivial robustness guarantees for multiple lp balls. The lp balls don't contain any other. It also is one of the most straightforward methods among all potential similar methods.\n\nWeakness Bullets:\n\n1. I am very curious about the landscape or decision boundary analysis and visualization. For the author's MMR-Universal regularization, it should give the model a very \"good\" decision boundary which has clear marginal between any two categories. In my opinion, it is necessary to evidence to convince more readers.\n2. Try a few more classical CNN architectures. \n\nRecommendation:\n\nDue to the logical derivations and supportive experiment results, this is a weak accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rkeaaOD7qS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe author proposed MMR regularization for the provable robustness of union of l-1 and l-infty balls, which is robust to any l-p norm for p>=1. \n\nStrengths:\n1. The paper is well organized. \n2. The theoretical part is completed and experiments are done on MNIST, Fashion-MNIST, GTS, CIFAR-10. \n3. The proposed method presents a significant improvement over SOTA. \n\nWeakness:\n1. The author should provide more empirical analysis on the MMR regularization, like how it changes during the training process. \n2. The captions of the table and figure are too small. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygCdma6FH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the paper's contributions:\n\nThis paper proves a result on the l_p robustness (p \\neq 1, \\infty) of a piecewise affine classifier in terms of its l_1 and l_\\infty robustness. This result is based on the insight that a guarantee for l_1 and l_\\infty robustness of a piecewise affine classifier also guarantees robustness within the convex hull of the union of the l_1 and l_\\infty balls. The paper then proposes a regularization scheme called MMR-Universal for a ReLU neural network that simultaneously trains for l_1 and l_\\infty robustness. This scheme is based on maximizing the linear regions of the network as in Croce et al., AISTATS 2019. Using the main result of the paper, it is implied that the proposed regularization scheme also enforces l_p robustness for any p \\geq 1.\n\nMain comments: (1) The paper provides an interesting result that guarantees l_p robustness for a piecewise affine classifier based on only l_1 and l_\\infty robustness. (2) The experiments show that the proposed regularization scheme is indeed effective in simultaneously guaranteeing robustness with respect to all l_p balls.\n\nDetailed comments:\n\n- The proposed regularization scheme does not come with any explicit robustness guarantee. Is it possible to show that a model that minimizes the regularized loss is guaranteed to be l_p robust for some radius? In Appendix C.3, it is mentioned that the best values for \\gamma_p were empirically found to be 1-2 times the desired \\epsilon_p robustness. Could this be formalized in theory?\n\n- From Figure 2, it seems that there is an optimal ratio of l_1 to l_\\infty robustness for which the l_2 guarantee is maximized. It would be interesting to see what this optimal ratio is for maximizing the l_p guarantee, as a function of dimension d and p.\n\n- In the experiments, the MMR-Universal scheme is compared with MMR+AT-l_2 and MMR+AT-l_\\infty. It would be interesting to compare it with MMR-l_1+AT-l_\\infty or with MMR-l_\\infty+AT-l_1.\n\n- In eq(1), is c intended to be the true label at x?\n\n- In Figure 2, the red curves are missing in the first and third plots.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends the degree to which ReLU networks can be provably resistant to a broader class of adversarial attacks using a MMR-Universal regularization scheme.  In particular, the first provably robust model in terms of lp norm perturbations is developed, where robustness holds with respect to *any* p greater than or equal to one (as opposed to prior work that may only apply to specific lp-norm perturbations).

While I support accepting this paper based on the strong reviews and significant technical contribution, one potential drawback is the lack of empirical tests with a broader cohort of representative CNN architectures (as pointed out by R1).  In this regard, the rebuttal promises that additional experiments with larger models will be added in the future to the final version, but obviously such results cannot be used to evaluate performance at this time.
Decision: Accept (Poster)