Provable Robustness by Geometric Regularization of ReLU Networks
Authors: Chester Holtz
Changhao Shi
Gal Mishne
Venue:  (2021)
Keywords: deep learning
adversarial attack
robust certification

Abstract: Recent work has demonstrated that neural networks are vulnerable to small, adversarial perturbations of their input. In this paper, we propose an efficient regularization scheme inspired by convex geometry and barrier methods to improve the robustness of feedforward ReLU networks. Since such networks are piecewise linear, they partition the input space into polyhedral regions (polytopes). Our regularizer is designed to minimize the distance between training samples and the \textit{analytical centers} of their respective polytopes so as to push points away from the boundaries. Our regularizer \textit{provably} improves a lower bound on the necessary adversarial perturbation required to switch an example's label. The addition of a second regularizer that encourages linear decision boundaries improves robustness while avoiding over-regularization of the classifier. We demonstrate the robustness of our approach with respect to $\ell_\infty$ and $\ell_2$ adversarial perturbations on multiple datasets. Our method is competitive with state-of-the-art algorithms for learning robust networks. Moreover, applying our algorithm in conjunction with adversarial training boosts the robustness of classifiers even further.


Under review as a conference paper at ICLR 2021
PROVABLE ROBUSTNESS BY GEOMETRIC REGULARIZATION OF RELU NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Recent work has demonstrated that neural networks are vulnerable small, ad- versarial perturbations of their input. In this paper, we propose an efficient regu- larization scheme inspired by convex geometry and barrier methods to improve the robustness of feedforward ReLU networks. Since such networks are piecewise linear, they partition the input space into polyhedral regions (polytopes). Our regularizer is designed to minimize the distance between training samples and the analytical centers of their respective polytopes so to push points away from the boundaries. Our regularizer provably optimizes a lower bound on the necessary adversarial perturbation required to switch an example's label. The addition of a second regularizer that encourages linear decision boundaries improves robustness while avoiding over-regularization of the classifier. We demonstrate the robustness of our approach with respect to fec and lg adversarial perturbations multiple datasets. Our method is competitive with state-of-the-art algorithms for learning robust networks while involving fewer hyperparameters. Moreover, applying our al- gorithm in conjunction with adversarial training boosts the robustness of classifiers even further.
INTRODUCTION
Neural networks have been very successful in tasks such as image classification and speech recogni- tion. However, recent work (Szegedy al. 20144 Goodfellow et al.) (015)) has demonstrated that neural networks classifiers can be arbitrarily fooled by small, adversarially-coose perturbations of their inputs. Notably, (Su et al. (017)) demonstrated that neural network classifiers which can correctly classify "clean" images may be vulnerable to targeted attacks, c.g., misclassify those same images when only a single pixel is changed.
Previous work demonstrating this fragility of neural network classifiers to adversarial noise has motivated the development of many heuristic defenses including adversarial training (Madry et al. 2018) well certifiably robust classifiers such randomized smoothing (Cohen et al. 2019 Salman et al. 2019) which characterize the robustness of classifier according to its smoothness.
The intrinsic relationship between smoothness, Lipschitz continuity-and their corresponding local variants-and robustness has motivated a variety of techniques to encourage uniform and local smoothness through the explicit regularization of approximations of the global and local Lipschitz constants (Zhang et al. 2018 WWnng et al. 2018a b). Recently,Lecuuer et al. (2019); Li al. (2018); Cohen et al. (2019); Salman et al. (2019) proposed and extended simple, scalable technique randomized smoothing to transform arbitrary functions (e.g. neural network classifiers) into certifially and robust classifiers on &g perturbations.
Alternatively, previous work has also addressed adversarial robustness in the context of piecewise- linear classifiers (e.g., feedforward neural networks with ReLU activations). WWng Kolter (2018); Jordan et al. (2019) propose to certify the robustness of network f at an example x by considering bound on the radius of the maximum fn-norm ball contained within a union of polytopes over which f predicts the same class. Related to our work, Croce et al.) Liu et al. (2020) propose maximum margin regularizers (MMR) which quantifies robustness of a network at a point according to the local region in which it lies and the distance the classification boundary. Recent work also includes recovery and analysis of the piecewise linear function learned by an ReLU neural network during a training process (Arora al. 2018 Montáfar et al. 2014 Croce & Hein 2019). Typically, work in this area

---

Under review as a conference paper at ICLR 2021
centers around studying the complexity, interpretation, and improvement of stability and robustness of neural networks. For example, Montúfar et al. (2014); Serra et al. (2017) studied piecewise linear Montúfaar
representations of neural networks and proposed the "activation profle' to characterize the linear regions.
In this work, we propose novel regularizer for feedforward piecewise-linens neural networks, including convolutional neural networks, to increase their robustness to adversarial perturbations. Our Geometric Regularization (GR) method is based the fact that ReLU networks define continuous piecewise affine functions and is inspired by classical techniques from convex geometry and linear programming. We provide a novel robustness certificate based on the local polytope geometry of a point and show that our regularizer provably maximizes this certificate. We evaluate the efficacy of our method on three datasets. Notably, our method works regardless of the perturbation model and relies on fewer hyperparameters compared with related approaches. We demonstrate that our regularization term leads classifiers that are empirically robust and are comparable to the state of the art algorithms with respect to clean and robust test accuracy under l and loo -norm adversarial perturbations.
2 PRELIMINARIES
In this section, we briefly present background terminology pertaining to polytopes and their charac- terizations, adversarially robust classification, and the polytope decomposition the domain induced by an ReLU network and its linearization over given polytope.
2.1 PIECEWISE-LINEAR NETWORKS
ReLU network is a neural network such that all nonlinear activations are ReLU functions, where we denote the ReLU activation by R - R, axx) max x). Informally, we define (xa)]. Let f: Rd + [0, 1 a feedforward ReLU network with L hidden layers; for example, f may map from d-dimensional image to k-dimensional vector corresponding to likelihoods for k classes. Let ny be the number of hidden units at layer I, the input layer is of size ng = d, and let W E R and b(4) E R denote the weight matrix and bias vector at layer I, respectively. Since f may be represented as the composition of J. + linear transformations and L continuous piecewise-affine functions, f must necessarily continuous and piecewise-affine (for brevity, we will say piecewise-linear).
a: Rd + Rd by (x) =
The half-space representation, or H-representation, convex polytopes is defined as follows:
Definition 2.1 (Convex polytope). convex polytope K. is the convex hull of finitely many points. Alternatively, a convex polytope may be expressed as an intersection of m half-spaces. The H- representation of a polytope is defined as the solution set to a system of linear inequalities Ar S
= fx : Vj E [m]] aj by}
Following definition 3.1 from Croce et al., a function is piecewise-linee linear there exists a finite set of convex polytopes /m (referred to linear regions of such that - Qr Rd and is affine when restricted to each Qr, i.e., can be expressed on Qr as f(x) = Vx +a
Given a feedforward ReLUU network ʃ and an input & E Rd intend to recover the polytope Q conditioned on I and the linear restriction of f on Q. Therefore, we need to find A and b such that Ar < 6, where and b define the intersection of k half-spaces, i.e. polytope, and V and corresponding to the linearization of within this polytope such that f(x) = Vr + when restricted to Q
We follow the formulation and notations of Croce et al. If E Id and (x) x we recursively define the pre- and post-activation output every layer:
(x) (() (() (x)) +
(x) o(f((()))
The resulting classifier is then: f((+1) ( b(L+1).
2

---

Under review as a conference paper at ICLR 2021
By rewriting affine function, write f()) formally composition of affine functions:
f ( 2 + +64))... ...) 6(h)
where we define (1, 10,5% -.00
E R conditioned on æ and defined elementwise as:
1 sign( (x)) =
if and f (x) >0
otherwise
otherwise
We now derive the polytope of f at and the linear restriction of polytope By expanding the composition, concisely write f() v( + a where
v w
() (z)
(1)
a b0)
w ((-mm)) (x))8b0))
k=1 m=1
and characterize the polytope Q where x lies as the intersection N Et= ny half-spaces:
Ti, = e R ( (x)()) 20.
2.2 POLYTOPE CENTERS
There are various definitions of the "center" of a polytope. Notably, the Chebyshev center of polytope the center of the largest inscribed hall of K., or equivalently, the interior point of I. that maximizes the minimum distance between itself and the boundary of K. More formally,
Definition 2.2 (Chebyshev center). Let K. be a convex polytope. The Chebyshev center of K. with respect an Ep distance the point E. which satisfies the following min-max problem:
arg min max | E|p
2 SEK
Previous work explored the Chebyshev center in the context of adversarial machine learning (Croce al.) Jordan et al. 2019). For example, Croce Hein (2019) propose include the minimum distance to the boundary in non-smooth regularization term in their Maximum Margin Regularizer (MMR) to encourage samples to lie close to the Chebyshev centers of their respective polytopes.
In contrast, we explore the application of an alternative polytope center: the analytic center. The analytic center of a convex polytope expressed via the H-repressetation Ax S b canonically de- fined as element of K. that maximizes the product of the distances to the hyperplanes characterized by the rows A and the elements of b.
Definition 2.3 (Analytic center). Let IC be a convex polytope expressed via the H-representation: Ax < b. The analytic center of IC is the point E Rd which satisfies the following objectives:
d
Tac arg max
I
(b.
Σ 1=1
aijoy)
) = arg min
Σ log(b; Σ
(2)
x
j=1
S.L. I I
s.t. x E EC,
where the second objective is canonically known the logarithmic barrier potential (Nesterov & Nemirovskij 1994).
naturally follows that when boundary-planee of the polytope are symmetric about the analytic center (e.g. for polytopes that satisfy central symmetry property). it exactly corresponds to the Chebyshev center. A polytope K. C IRd is centrally symmetric if K. AC; that is, x and only K.
if there is unique point such that the reflection of about y is in K:: 2y
The analytic center, namely a weighted analytic center, has been extensively used interior point (IP) methods for linear programming (Boyd & Vandenberghe 2004). In general, the measure of closeness

---

Under review as a conference paper at ICLR 2021
(a)
(b)
(c)
Figure 1: Lower bounds on the robustness of an input example r. (a) Case 1: the input (black) is closer to the boundary of the polytope (z)) (grey) than to the decision boundary (red). Our ACR term improves robustness in this case. (b) Case the input a closer to the decision boundary than to the boundary of (x)). Smoothing / addresses this case. (c) The analytic center of convex polytope. The inner ellipsoid corresponds to the Dikin ellipsoid at z The dashed lines show level curves of the logarithmic barrier function.
STE
(a)
(h)
(d)
Figure 2: Recovered linear regions and linearizations of trained feedforward, single hidden layer (128 neurons) ReLU network on the two-moons dataset. (a) Polytopes defined by a vanilla network fvamilla- (b:: Linearization of fvanilla restricted to the polytopes in da (c) Polytopes defined by a robust network frobust- (d): Linearization of frobust restricted to the polytopes in (c). Note the difference in the granularity of the partitions and the overall smoothness of the classifier. The flat transparent pink (b) and grey (d) planes correspond to the plane defined by y = 0. The intersection of the networks with these planes correspond to the decision boundaries.
to the analytic center is an important factor for the convergence of center-following algorithms. The properties of the log barrier potential that make it popular choice for interior point methods (including being twice continuously differentiable and convex) suggest we might use it as regularizer encourage robustness during learning.
Note, however, that the analytic center depends on how the set of particular inequalities is defined. The addition of redundant inequalities could feasibly push the analytic center arbitrarily close the boundary of the polytope. We discuss this further in Sec.
2.3 ROBUST CLASSIFICATION
Consider again the network f : Rd R² where the input might be a d-dimensional image and the output likelihood of that image belongs to of k classes. The associated classification is then c(x) = arg max;e[ fx(x). In adversarial machine learning, we are not just concerned that the classification be correct, but we also want to robust against adversarial examples, i.c. small perturbations the input which may change the output incorrect class.
Definition 2.4 (c-robust). is called c-robust with respect to norm at x. if the classification is consistent for small ball of radius around z::
c(x 8) c(x), V5
||
This c-robustness is intimately related to the uniform and local Lipschitz smoothness of f. Recall that function f has finite, global Lipschitz constant & > 0 with respect to norm
3k > 0 s.t. [f(x) f(x') k. || x' Vr, E X
4

---

Under review as a conference paper at ICLR 2021
An immediate consequence of Eq. 3 and Def. 2.3 is that if is uniformly L-Lipschitz, then f is e-robust at x with 27 (Pe - P)) where Pa is the likelihood of the most likely outcome, and P. is the likelihood of the second most likely outcome (Salman et al., 2019). The piecewise linearity of ReI.U networks facilitates the extension of this consequence to the locally Lipschitz regime such that for case 1 of Fig. L. corresponds to the norm of the affine map characterized by conditioned an input
Local smoothness is property exhibited by provably and empirically robust networks. In Fig 2 the adversarially trained neural network is smoother compared to the vanilla network (larger linear regions with linear functions that have smaller slope and smoother transitions- "comerr toints-betweer linear functions). In conjunction with smoothness, adversarial training also results coarser partitions, i.e. larger polytopes, in contrast to vanilla networks. is reasonable to assume that both of these properties are desirable in the context of robust classification.
In the case of piecewise linear networks, the lower-bound bound on the robustness of network a point given its associated polytope may be described with respect to two cases presented in Fig. ab)-(b. In case I, the point may be closer to the boundary of its polytope compared to the decision boundary, and vica-versa for case 2. It follows that for case 1, the distance to the polytope boundary is lower bound on the robustness the network at that point. Croce et al. propose to optimize this certificate exactly, and propose optimize relaxed version presented in the next section.
GEOMETRIC REGULARIZATION
3.1 ANALYTIC CENTER REGULARIZER (ACR)
We propose to adopt the logarithmic barrier potential regularizer encourage points be near their analytical centers. We define the analytic center regularization (ACR) as
m
n
JACR (I)
Σ (a;
UxyDy)
(4)
where V and are computed for network f given input via Eq. I and row-normalized. In related work, Croce et al.) [iu et al.] (2020) both propose variants to the vanilla MMR formulation which involve regularizing a summation over the distances to the k nearest boundary hyperplanes as opposed to only the distance to the nearest plane. This extension aims to ensure that the input is far from the boundary of the polytope. However, in addition to tuning this number, both methods employ a warm-up scheme to gradually increase the number of hyperplanes considered. In contrast, by regularizing the distance the analytic center, ACR natively inherits the desirable properties of MMR while taking into account all hyperplanes comprising the boundary and involving no additional hyperparameters.
We note that many assumptions made regarding the analytic center rely on the polytope P being minimally represented (e.g. the uniqueness of the analytic center). To elucidate this concept, define redundant hyperplanes:
Definition 3.1 (Redundant hyperplanes). Let P = Ax|Ar < b} be a polytope comprised of m constraints and E [m)) a is redundant constraint, redundant hyperplane, if it can be removed from the system without changing P, and irredundant otherwise. If all constraints in Az < b are irredundant, then the system is irredundant, and redundant otherwise.
In other words, the H-represeenattion of polytope is not unique. In fact, there are infinitely many H-representations of a polytope, but only one minimal representation. It is well-known that the inclusion of redundant hyperplanes may significantly affect the location of the analytic center.
Lemma 3.1 (Boyd & Vandenberghe 2004)). Let P = {a| Az S b) be an H-repreesetatton of polytope. The inclusion of redundant hyperplanes can make any interior point the analytic center.
To address this, we propose a masked variant of the ACR term which ensures that only boundary hyperplanes of P are included in the objective. However, recovering an irredundant H-representation nontrivial. We apply an approximate method which leverages the primal-dual equivalence between the half-space intersection problem and the convex hull problem. Details are provided in Appendix E
5

---

Under review as a conference paper at ICLR 2021
In practice, found that the application of ACR all constraints (i.e. without removing redundant constraints) performs as well or better than than the masked variant in addition to having lower computational overhead. We hypothesize that this is due to the composite nature of neural networks and the fact that the output of the network f is dependant on all hyperplanes- just irredundant hyperplanes- and that ignoring redundant hyperplanes during regularization may adversely affect learning. Additional justification for inclusion of the redundant constraints when evaluating GR can be found in Fig. [1] where we see that the network trained with GR exhibits more even and symmetric distribution of hyperplanes compared to other networks.
3.2 LINEAR DECISION BOUNDARY REGULARIZER (LDR)
Recent work (Moosavi-Deziooll et al. 2019 Qin al. 2019) has demonstrated that regularizing the curvature of the loss corresponds regularizing the curvature of the decision boundary, thus improving robustness. Specifically, Moosavi-Dezione MosatficllyyMoovvi----ooo.o
al. (2019); Qin et al. (2019) respectively provide a tight certificate that is linear in the maximum eigenvalue of the Hessian of the loss with respect to the input and an upper bound on the adversarial loss. However, the regularization schemes proposed suffer drawbacks. Namely, both methods require the careful setting of parameter which characterizes the local approximation of the Hessian and Qin et al. (2019) requires multiple iterations per training iteration. We exploit the intrinsic manifold structure of the data encourage the loss to behave linearly around data via the following regularization term:
(I
(5)
In general. we cannot compute this integral because M not known analytically, Belkin et al. (2006); Belkin & Niyogi (2008) propose the following discrete approximation that converges to the integral the sample limit:
V [.l(x;;) V=((=,)
(L)
Σ
NE
|10-- - xy
(JE(N
(F)
where N₂ is the minibatch size. Note that the contents of batches are randomized each epoch. The application of regularizers based on the graph Laplacian have also been explored in the past (Mishne cet al. 2019), including in the context of adversarial robustness (Jin & Rinard 2020). However, propose to apply manifold regularization to the gradient of the loss instead of the weights of classifier. In the case of piecewise linear networks, this regularizer may be interpreted as reducing the angle between adjacent linear restrictions of f. Such sharp angles are known to facilitate brittleness in the presence of adversarial noise (Roth al. 2019).
3.3 GEOMETRIC REGULARIZATION OF RELU NETWORKS
Following the definitions above, we propose the following objective for adversarially robust training
L(D) [D(((r) + AA (I.JJ.DR(()))
where ((x) is an arbitrary classification loss and AA and Å are hyper-parameter parameters to be optimized. We note that, given input x, a forward pass through f is sufficient compute both the linearization of If around x and the associated region (the polytope). Given these entries, optimizing the regularization term corresponds solving smooth, unconstrained convex problem which can be done very efficiently using gradient descent. Analogous to adversarial training, LDR requires computation of vz((x) performed via backpropagation. However, the gradients are computed only once per batch as opposed to iteratively as in adversarial training-basse based methods.
3.4 GEOMETRIC ROBUSTNESS GUARANTEES FOR RELU NETWORKS
We show that GR provably optimizes a lower bound on the radius of robustness. Given an input x and network f. let (x: be the distance from to the boundary of its polytope and let d (ær) be the distance from æ to the decision boundary defined by f. To recover robustness guarantees when d (2) < dz(z), and demonstrate that GR optimizes lower bound the robustness, rely the Dikin Ellipsoid (DE), defined by the Hessian of the logarithmic barrier function (Nesterov & Nemirovskij 1994).

---

Under review as a conference paper at ICLR 2021
Definition 3.2 (Dikin ellipsoid). The Dikin ellipsoid of radius of polytope Æ expressed by Ar I b
centered at å is defined as the set: (ā) = {a (z 2)" ( - -i) S r). where is the Hessian
a, by ==j
of the log-barrier function defined to be H = 5 with 8ij
0
otherwise
Notably, the Hessian of the logarithmic barrier function and the Dikin ellipsoid describe well the local geometry of IC in the following sense (we refer to Nesterov & Nemirovskii (1994) for details and proofs): (1) the Dikin ellipsoid is contained inside K:: (i()) S.C. for any x E K. (2) The Hessian of the oog-barrier changes slowly with respect to its local norm; while exploding to infinity at the boundary of K., In other words, the gradient of the logarithmic barrier function at points near the boundary of K. is dominated by component with direction perpendicular pointing towards the interior of K. (3) The volume of the Dikin ellipsoid is guaranteed to be at least m analytic center and its Dikin ellipse are given in Figure Ic
the boundary and
I (Kl( where is the number of hyperplanes comprising the boundary of K., An example of an
The properties of the Dikin ellipsoid imply that may be used to construct a certificate at a by taking the length of the shortest semi-axis of the ellipsoid. In particular, the length of the minor axis of the Dikin ellipsoid at æ may serve as a uniform lower-bound on the radius of robustness, and optimizing Eq. provably improves this radius. More concretely, we get the following robustness guarantees: Theorem (ACR Robustness guarantee for ReLU networks).
1. If dd(x) S dz()). then f is locally robust with radius L/VAmaz where Xmaz is the maximum eigenvalue of the Hessian matrix (and 1/v/omax is the length of the minor axis of the Dikin ellipsoid) of the log-barrier potential function functtin (maximized when JACR is minimized).
2. If dz(() 2 dd(x), let g (z). Then, for some constant c, the radius c= [191| where is the maximum eigenvalue of the Hessian of ((D))maximized JLDR minimized).
2ve
Ioll
Note that i-th axis of the ellipse described by the quadratic form xf Ax = corresponds to the i-th eigenvector of A with length VX.
As previously stated, we propose to use the length of the shortest minor sub-axis as certificate of robustness. We call this certificate the Dikin certificate. The proof that the Dikin certificate is a lower bound on the radius of robustness is given in the appendix, and relies on the following property and lemma which directly follow from the definitions of the Dikin ellipsoid and the analytic center.
Property 3.1. Let K. be a convex polytope. Let x be an interior point of K. and let Eg be the Dikin ellipse defined at x. Then En K.
Lemma 3.2. Let I. be a centrally symmetric convex polytope, and let H be the Hessian of the logarithmic barrier function defined on irreducible H-reprreennatton of K. Then, Foc Echeh and Amax (H (xac)) S Amax H (x)) Vx E K.
In other words, the point that satisfies the largest radius of robustness with respect the Dikin certificate is exactly the analytic center.
EXPERIMENTS
4.1 MAIN EXPERIMENTS
We provide variety of experiments to demonstrate the performance of GR. We evaluate GR on three datasets: MNIST (LeCun & Cortes) 2010), Fashion MNIST (Xiao et al. 2017]. and CIFAR-10 (Krizhevsky et a..). We consider robustness with respect to both &g and too distances. We use three criteria: upper and lower bounds on the robust test error for a given threshold and the mean lower bound on the pointwise radius of robustness. Lower bounds the robust test error for fg and l computed using the attack via Projected Gradient Descent (PGD) (Madry et al. 2018). Upper bounds and robust radii are computed using Wong & Kolter (2018).
We report our results in Table T We compare seven methods: plain training. adversarial training (AT) of (Madry et al. 2018), the robust loss of (Wong & Kolter 2018) (KW), the MMR and MMR +
7

---

Under review as a conference paper at ICLR 2021
Table 1: Results for 7 training schemes: plain, (adversarial training), KW, MMR and MMR+AT, GR, GR+AT, and 5 evaluation schemes for ReLU networks: clean test error (TE), lower (LB) and upper (UB) bounds on the robust test error via Wong & (201e) and average radius of robustness as estimated by Wong & Kolter (2018) (KW). The robustness radii are computed on the first 1000 points of the respective test sets. Models evaluated according to the available code.
CNN
FCI
perturbaion:
perturbuton::
bution:
perturbation:
TR
UB
TB
CTR
MINIST
plam
0.92
78.32
1001
0.0
0.35
3.1
100
0.04
16
98.32
100
0.0
1.73
9.7
06
0.217
plain
12.1
0.008
0.87
1.8
7.10
0.002
115
KW
121
3.03
4.4
0.096
1.11
2.2
6.0
0.32
2626
8.59
10.9
0.087
119
24
5.2
0.703
MMR
11.9
6.0
0.088
2.57
588
11.6
22.5
24.9
0.066
2.40
8.8
0.548
MMR AT
1224
5.6
3.6
0.091
2.12
4.6
9.7
0.38
2.04
14.0
14.1
0.082
1.37
388
6.4
0.592
GR
14
10.13
5.8
0.087
4.4
12
0.38
1.81
17.5
26.2
0.063
3.5
8.2
0.363
GR + AT
2.2
8.70
3.9
0.089
4.2
10.9
0.38
2.05
13.71
21.3
0.081
3.1
5.9
0.261
F-MNIST
0.3
6
0.3
plain
9.38
98.42
100
0.0
9.32
57.1
100
0.03
9:48
100
100
0.0
9.70
42.8
91.8
0.18
plan
13.62
29.8
73.0
0.0
8.10
31.3
95.5
0.008
9.15
19.9
01.4
0.11
KW
21.31
32.8
32.4
0.046
13.08
18.5
21.7
0.17
21.31
32.8
32.8
0.034
11:24
17.2
22.7
0.46
17.57
34.2
35.3
37.6
25.0
0.30
MMR AT
15.84
31.3
30.7
0.041
13:42
26.2
39.
0.21
15.84
31.3
34.8
0.027
12.12
19.7
23.4
0.66
GR
17:54
35.13
0,031
35.6
34.91
43.7
0.021
24.1
0.47
GR + AT
15.76
31.41
32.1
0.009
26.0
40.2
0.19
15.99
33.78
36.2
0.025
17.6
24.0
0.64
CIFARTO
2750
<-
plam
24.63
91.0
100
0.0
23.31
47.2
100
0.02
plain
27.04
52.5
0.001
25.82
35.8
100
RW
39.27
48.16
48.0
0.004
4024
439
49.0
0.10
MMR
34.59
57.17
4099
MMR
34.36
19.27
54.2
0.03
37.75
43.9
33.3
GR
38.91
57.79
63.9
0.002
$2.39
58.3
GR
37.36
41335
Table Comparisons to state-of-the-an first and second-order robust regularizers. TRADES Zhang al. 2019), Locally Linear Regularization (LLR) (Qin et al. 2019). TULIP (Gradient Regularization) (Finlay & Oberman 2019), and Curvature Regularization (CURE) (Moosavi-Dezioor
et al. 2019).
We evaluate each approach using the CNN architecture described in Table GableBlacc and utilize the PGD fxc
attach with e = 0.1 for MNIST and
2 for CIFARIO.
255
MNIST
CIFARIO
10
TE
LB
TE
LB
GR (this work)
2.14
10.13
38.91
57.79
LLR
1.13
10.43
25.83
58.14
TULIP
2.03
12.74
31.23
59.85
TRADES (3 = 1)
0.97
5.70
27.01
53.39
CURE
1.07
11.34
26.8
61.74
with adversarial training scheme (Croce et a..), and our approach (GR) with and without adversarial training. All schemes evaluated one hidden layer fully connected network with 1024 hidden units (FCI) and convolutional network (CNN) with 2 convolutional and 2 dense layers. Note that unlike other reported results which fine-tune their defense to each attack type, we demonstrate empirical robustness against multiple perturbation types by training one model per architecture and dataset and report its robustness against different attack types. Additional details are in the Appendix.
On MNIST, we outperform or match MMR's clean test eтror and lower-bound robust accuracy performance with respect to both E and L -nom perturbations. With respect to robust accuracy, we note that although the GR certificate is a lower bound on the MMR certificate, we closely match MMR's KW-based average certified radius. On F-MNIST and CIFARIO, 10, we again match MMR with respect to clean test error and empirical robust accuracy and certifiable radius. We emphasize that Croce et al. perform grid search on model parameters for each dataset and perturbation, while our single model trained per-dataset.
performance is based
We compare our approach to state-of tf-the-rr first and second-order regularizers in Table 2 Details of these algorithms are provided in the appendix. We note that TRADES and AT remain the state-of-the- art heuristic methods, while GR performs competitively with other provable methods that encourage local linearity of the loss. We note that these methods (i.e. LLR,, TULIP, and CURE) necessitate
8

---

Under review as a conference paper at ICLR 2021
Punter datapann
ACR
Cershee rnbustness radius
Gertiite robustress
radius
(a) GR
(b) MMR
(c) AT
(d) none
Figure Distributions of MMR and GR robustness certificates for regularized networks. For
networks trained with GR and AT, the GR certification matches closely with MMR.
(a) GR
(b) MMR
(c) AT
(d) none
Figure 4: Local loss surface near decision boundary of networks trained on the two-moons dataset.
iterating sampling around each training example compute their regularization terms and, and thus require additional overhead and setting hyperparameters governing their sampling procedures.
As mentioned before, the GR certificate is lower bound on the certificate proposed by Croce et al.) which is lower-bound on the radius of robustness. We present the empirical differences in point-wise certified radii Fig. For networks that are adversarially trained or regularized with GR, the distribution of point-wiss wise radii of robustness is close. In contrast, the distributions are significantly different for vanilla networks and networks trained with MMR. The implication is that for certain networks and inputs, the Dikin ellipsoid may not optimally characterize the polytopes, in particular, the H-representation polytope exhibits redundancy concentrated on one side, or if the polytope poorly conditioned in the sense that H is poorly conditioned (K is geometrically "clongated"),
4.2 ROBUSTNESS TO GRADIENT OBFUSCATION
Athalye et al. (2018) Qin et al. 2019) demonstrated that empirical robustness of neural networks may often due the effect of gradient obfuscation-is. -ic. the network learns fool first-order attacks by contorting the loss surface. Although this non- non-linearity of the loss surface may cause networks to appear exhibit robustness merely running PGD for more iterations reliably produces adversarial perturbations. In contrast, networks that exhibit robustness while being close locally linear exhibit "true" robustness to adversarial attacks. In Fig 4 we demonstrate that our regularizer produces models that exhibit such robustness to gradient obfuscation. We plot local regions of the loss surface near the decision boundary for various networks and show that training with GR leads to smooth loss in the region of samples near the decision boundary, replicating the effect of adversarial training, while the local loss surface exhibited by networks trained with MMR leads highly non-linear loss surfaces.
adversarial attacks, (Athalye al. (2018) further demonstrated that
CONCLUSION
We have introduced method based leveraging the geometry of piecewise- neural networks for training classifiers that are provably robust to norm-hounded adversarial attacks. Our approach is based the notion that piecewise-liness classifiers with large linear regions and smoother decision boundaries are robust. We demonstrate that our method learns robust networks that exhibit properties typical to robust networks and perform competitively with current state-of-the methods, including related, geometrically motivvted techniques. By exploiting the geometry of the network and data, our method relies on fewer hyperparameters compared related approaches. Furthermore, our method is scalable and leads to models which are simultaneously robust to multiple perturbation models.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu and Y. Li. Backward feature correction: How deep learning performs deep learning, ArXiv, 0os/2001.044133 2020.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations (ICLR), 2018.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. volume 80 of Proceedings of Machine Learning Rexearch, pp. 274-283, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018.
Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for laplacian manifold methods. Journal of Computer and System Sciences, 74(8): 1308, 2008
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. J. Mach. Learn. Res., 7, 2006.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Francesco Croce and Matthias Hein. A randomized gradient-free attack on ReLU networks. In Thomas Brox, Andrés Bruhn, and Mario Fritz (eds.), Pattern Recognition, pp. 215-227, Springer International Publishing, 2019.
Francesco Croce, Maksym Andriushchenko, and Matthias Hein. Provable robustness of relu networks via maximization of linear regions. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019.
Chris Finlay and Adam M. Oberman. Scaleable input gradient regularization gradiien for adversarial robust- ness. CoRR, abs/1905. 1468, 2019. URL
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamessing adversarial examples. In International Conference on Learning Representations, 2015.
Charles Jin and Martin Rinard. Manifold regularization for locally stable deep neural networks. 2020.
Matt Jordan, Justin Lewis, and Alexandros G Dimakis. Provable certificates for adversarial examples: Fitting ball in the union of polytopes. In Advances in Neural Information Processing Systems 32, pp. 14082-14092. 2019.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). URL. httpt:tttt/ttt / /www Cs twrottorroo....... www/ .o.oonto.dds/-kkii......
Far.htm
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yann
lecun wttp////////mnstttt/
M. Lecuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana. Certified robustness to adversarial examples with differential privacy. 2019 IEEE Symposium on Security and Privacy (SP), pp. 656-672, 2019.
Bai Li. Changyou Chen, Wenlin Wang, and Lawrence Carin. Second-order adversarial attack and certifiable robustness. CoRR, abs/1809.03 13, 2018.
Chen Liu, Mathieu Salzmann, and Sabine Süsstrunk. Training provably robust models by polyhedral envelope regularization, ArXiv, abs/1912.04792, 2020.
10

---

Under review as a conference paper at ICLR 2021
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018.
Gal Mishne, Uri Shaham, Alexander Cloninger, and Israel Cohen. Diffusion nets. Applied and Computational Harmonic Analysis, 47(2):259 285, 2019.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, NIPS' 14, 2014.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and P. Frossard. Robustness via curvature regularization, and vice versa. 2019 IEEE/CVF Conference on Computer Vision and Pattem Recognition (CVPR), pp. 9070-9078, 2019.
Yurii Nesterov and Arkadii Nemirovskii. Interior- Paitt Polynomial Algorithms in Convex Program- ming. Society for Industrial and Applied Mathematics, 1994.
Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Krishnamurthy Dvijotham, Alhussein Fawzi, Soham De, Robert Stanforth, and Pushmeet Kohli. Adversarial robustness through local linearization. In Advances in Neural Information Processing Systems 32, pp. 13847-13856. 2019.
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox: A python toolbox to benchmark the robustness of machine learning models. Reliable Machine Learning in the Wild, 34th International Conference Machine Learning, 2017.
Kevin Roth, Yannic Kilcher, and Thomas Hofmann. The odds are odd: A statistical test for detecting adversarial examples. CoRR, abs/1902.04818, 2019.
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya P. Razenshteyn, and Sébastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. CoRR, Abs/1906.045844 2019.
Hossein Sartipizadeh and Tyrone L. Vincent. Computing the approximate convex hull in high dimensions. CoRR, (bb//100.04422) 2016.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. CoRR, abs/1 11177221111111 14, 2017.
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. CoRR, abs/ 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv, abs/1312.6199, 2014.
Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S. Dhillon, and Luca Daniel. Towards fast computation of certified robustness for ReLU networks. In International Conference Machine Learning (ICML), 2018a.
Tsui- Wei Weng, Huan Zhang, Pin-Yo Yu Chen, Jinfeng Yi, Dong Su, Yupeng Gao, Cho-Jui Hsieh, and Luca Daniel. Evaluating the robustness of neural networks: An extreme value theory approach. In International Conference Learning Representations (ICLR), 2018b.
Eric Wong and Zico J. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. International Conference on Machine Learning (ICMI.), 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. CoRR, hbbs/1708.077// 2017.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. volume 97 of Proceedings of Machine Learning Research, pp. 7472-7482, Long Beach, California, USA, 09-15 Jun 2019.
Huan Zhang, Tsui- Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
11

---

Under review as a conference paper at ICLR 2021
A PRELIMINARIES
Let Ar < be an irreducible, affine matrix inequality characterizing a polytope in Ie where A E _m R= and b E R". We denote the feasible set characterizing the polytope by K:
K= { E |r b - 0}
Without loss of generality, let the rows of A be normalized under any lp norm. Then, the &p distance between any interior point x of K. to the i-th plane on the boundary of I. is nothing but (x) a. b;.
For completeness, we restate the curvature-bant based certificate of Moosavi Deziool et al. 2019) below. Theorem 2 (Moosavi-Dezfodde
al. (0119). Let f(x) denote the loss of neural network evaluated at I, and let r" be be the minimal perturbation necessary to fool the classifier. Let be the Hessian matrix of f(z), H 87g the second order Taylor expansion of x::
dx;ōu; E <RRddd Then, ||r*|| is the radius of robustness of J at x with respect to
1 " = min ||||| s.t. ((x) + Ve(x)"
Hr 2t
2
for threshold Let be such that == I - E(x) 2 O, and let V((x). Assume that = Amax and let u be the eigenvector corresponding to v. Then, we have
|gel|
(
1
2vc
-1 1) - ||r*|))
|
g ul
2vc
[g u)² -1
The above bounds can be further simplified to:
2v
||
5
19
||9|3
gz 1
B
PROOFS
B. THE DIKIN ELLIPSOID OF RADIUS IS CONTAINED WITHIN K. (oYYD & VANDENBERGHE 2004)
Let e denote the Dikin ellipse of radius at z E K. Note that since K,, (x) 2 Ovi. Let Ex. Additionally, let be the Hessian of the logarithmic barrier function at a feasible point a::
H(x) 5-A with Siz (x) i=j
otherwise*
The statement can be proven by showing that y E K. (i.e. y is feasible). Equivalently, we will show that d, (v) 2 0 Vi.
(y - T) (y x)
< by definition
(ai x)²
1
d2
(ai, 1 x)2
S Vi since all entries in the summation are nonnegative
(x)))
dz( d:(v)
<1 Ai
dxxx)
(v())
< Vi
dx)x)
Hence, for all i, 0 < ddlg)
(v) 0 Vi, and y K.
d,(x)
12

---

Under review as a conference paper at ICLR 2021
B.2
LEMMA 3.2
Recall the problem of recovering the Analytic center defined in Eq
77
aic arg max ZEK
arg max JEK
dx(x)
i=1
For brevity, let F
i== de (z).
Then the problem may be concisely written
arg max F(x) #EC
We will show that for any convex polytope I. satisfying central symmetry property (for example, zonotopes), that the maximizer of this problem is precisely a unique origin of the polytope. By definition, for centrally symmetric polytopes, for any constraint a constraint a. bb, and there exists unique interior point Te such that if K. its inversion with respect to d is also in K:: H E K. where T = 2x. I. We call this point 2e. the origin of K. A simple consequence of this definition that de lies at the midpoint of the line T.. follows that if x; the minimum-distan distance projection from æ onto boundary plane i, and if Fe lies on plane j. then d, dy.
there is a corresponding
The lemma is simple consequence this definition. For any perturbation applied to Ze. let e; > 0 be the variation in the Ep distance associated with the perturbation to boundary plane i. By the linearity of the boundary planes, the variation in the Ep distance suffered by the inverse boundary plane of boundary plane is -c.
m/2
F(x)
II (d((xe) (d) +G)
m/2
s II dx = F(xc)
so arg max, F(x) = xe, and Fac = Te- Accordingly, z, also corresponds to the Chebyshev center. Note that we can restate the definition of the Chebyshev center using the above notation:
Tcheb arg max min d4 (x)
(10)
x
Again, for any perturbation Ze, we have that min(min(dd(ra)) - e,, di(x))) + +i) = min(d((xe) - ei}
S min d, (xee)
so the solution Eq. 10 the origin of K., and Tag Teheb-
Finally, let H be the Hessian of the logarithmic barrier function at a feasible point x:
(d(x) i=
H(x) 5-2 A with 8ij-
otherwise*
Then, for any interior point it follows that
1
Amax (H (Nac)) max de (F
max
[d((z) Amax (H(x))
B.3 THEOREM
PROOF OF (1)
First, note that if (x)()) S dp(x), then the predicted class of x does not change for ball of radius d (I:) around 5., dp (x)). Let E,, be the Dikin ellipsoid at characterized by Hxx), the
13

---

Under review as a conference paper at ICLR 2021
Hessian of the logarithmic barrier potential evaluated at Let be the length of i-th shortest sub-axis of Eg. By definition,
1
VA;
where ); is the i-th largest eigenvalue of (x).
Since &g S Kz the polytope in which x lies, by Property 3.1, follows that
min r Vdmax
dg (3r)
where Amux is the largest eigenvalue of (xx) and 1. is lower bound on the minimal b--norm perturbation necessary to change the class.
Vana
PROOF OF (2)
Note that if dx(x)) < (x)x), then the Dikin certificate is not a sufficient lower- on the radius of robustness r", however, the bound of Theorem holds globally:
2v
||r
|gl||
where e is a loss-dependant constant, V((r), and v Amax-
C MAIN EXPERIMENTS
Table 3; Architectures for main experiments for number of classes nc.
FC1
CNN
FC(1024) ReLU
Conv(16, 4 x 4,
ReLU
FC(nc)
Conv(32, 4 x 4, 2)
ReLU
FC(100)
ReLU
FC(nc)
Table 4: Ablation experiments. We evaluate networks trained using both ACR and LDR terms, ACR only, and LDR only on loo perturbations. We see that the best performance achieved when both terms used.
MNIST
FMNIST
CIFARTO
TE
LB
TE
LB
TE
LB
Both
1.81
17.5
16.38
34.91
37.36
57.79
LDR
1.95
15.8
21.0
46.83
35.85
61.87
ACR
2.6
52.6
16.01
73.8
36.21
76.49
We abbreviate one hidden layer fully connected network with 1024 hidden units with FC1. The convolutional architecture that we use is identical to that of Wong & Kolter (2018); Croce et al. -consistnng of two convolutional layers with 16 and filters of size fully connected layer with 100 hidden units. For all experiments we use batch size 128 and we train the models for 100 epochs. Moreover, we use Adam optimizer (Kingma Ba 2015) with the default learning rate 0.001. On MNIST and F-MNIST
and stride 2, followed by
restrict the input to be in the range [0. 1]. On the CIFAR- 10 dataset, following Croce et al.] we apply random crops and random mirroring of the images data augmentation. We also apply warm-up training schedule for both regularization weights where we linearly increase them from X/10 to À during the first 10 epochs. For each dataset and architecture, perform grid search over the regularization weights. All the reported models and
14

---

Under review as a conference paper at ICLR 2021
the final set of hyperparameters will be made available acceptance. In order to make comparison to the robust training of Croce et al.) Wong Kolter (2018) we take their publicly available models.
We perform adversarial training using the PGD attack of Madry et al. (2018) with random selection of 50% clean and 50% adversarial examples in every batch. For the fo-mo we used the implemen- tation from Rauber et al. (2017) to perform PGD-based lg attacks. We the same fz-bound on the perturbation as the used in robust error. During training, we perform 40 iterations of the PGD attack for MNIST and F-MNIST, and for CIFAR-10. During evaluation, use 40 iterations for all datasets. Following Croce et al. the step size is selected as divided by the number of iterations and multiplied by 2.
C.I DETAILS STATE-OF-TIIE-ARI METHONS
We use publicly available implementation for all methods. We denote L(D) = Ep(((z) + R(x) to be the objective (e.g. as Eq. 7.) We briefly describe how each technique we compare to in Table formulates the R(x) term below:
Gradient Regularization (TULIP) (Finlay & Oberman 2019). The Gradient Regularization term of Finlay & Oberman 2019 is formulated norm on the gradient of the loss function with respect
to the input:
R(x) =((()]
Locally- Regularization (LLR) QQnn et al., 2019). Qin et al. (2019) propose to regularize the local linearity of the classifier:
R(x) = Ar(e, + ~I10TR v=((x)]
where 7(c, x) max.e g(f. 6, x) and gf.. 6, x) = |((r + 6) - E(x) [v)(
Locally-Lipschin Regularization (TRADES) (Zhang et al. 2019). Trades is the current empirical state the art and is motivated by the relationship between robustness and local Lipschitzness.
R R(x) = 3 max ((xxx')
((,,))
Curvature Regularization (CURE) Doosavi-Dezfoolii et al. 2019) Propose regularize the curvature of the loss with respect to the input:
R(x) (1)
Note that H is estimated through iterative approximation by computing finite differences.
D ADDITIONAL EXPERIMENTS
D.1 VISUALIZING THE EFFECTS OF REGULARIZATION
We explore the geometry of polytopes. In Fig. overlay histograms corresponding the radii of Dikin ellipsoids of samples pre- and post-robust training. It is clear that robust training increases the size of polytopes, agreeing with the intuition of the GR certificate.
In Fig. 6 we visualize the decision boundary for different values of AL. via Eq. 11 see that as this weight increased, the network imposes higher cost on the local loss curvature resulting in linearization of the decision boundary and lower overall confidence in predictions over the domain. However, something unusual happens when λ exceeds threshold: the network exhibits uncertainty uniformly over the domain, and both clean and adversarial test accuracy drop significantly.
As expected,
In Table 4 we highlight the importance of both parts of the regularization, i) penalization of the distance to boundary of the polytope ii) penalizing the curvature of decision boundaries across polytopes via ablative experiments. We train FCI MNIST using the each component of the regularization scheme. We clearly see that lower bounds on robustness computed using PGD is always significantly better when both terms used. In order to achieve the best empirical performance, it is necessary to both increase the distance of the points to the boundaries of the polytope and regularize the curvature of the decision boundary between polytopes.
15

---

Under review as a conference paper at ICLR 2021
70
Initialization Trained network
60
Number of datapoints
50
40
30
20
10
0.000
0.005
0.010
0.015
0.020
0.025
Certified robustness radius
Figure 5: GR over robust training. As expected, the volumes of polytopes (certification of robustness) increases over training.
A
(a) A1 = 0.0
(b) Ar. = 0.0001
(c) A. = 0.001
(d) A.. = 0.01
Figure 6: We plot decision boundaries via Eq. 11 for different values of AT. As expected, Xt. increases, the decision boundary exhibits less curvature.
16

---

Under review as a conference paper at ICLR 2021
(a) none
(b)
MMR
(d) GR
Figure 7: MNIST.
We plot visualization of neuron weights for networks trained with different regularizers on
2
D
(a) Input images
(b) Analytic centers for a vanilla network
(c) Analytic centers for an AT network
(d) Analytic centers for MMR network
(e) Analytic centers for GR network
Figure 8: We plot the analytic centers for trained networks. We see that the analytic centers for vanilla networks roughly correspond to noise. However, the analytic centers of polytopes induced by robust networks are clearly interpretable and similar to the inputs they are conditioned on.
D.2 ANALYSIS OF ELLIPSOIDS AND ANALYTIC CENTERS
The geometry of the partitioning and the associated polytopes induced by ReLU network is not obvious. Intuitively, we would like the partitions to be semantically reasonable, i.e. cleanly partition the domain into class-regions. However, this is not the examples. An immediate consequence of the GR certificate is that we expect "realistic" examples to lie far from the boundary of their respective polytopes. We encourage this via the JACR regularizer.
implied by the existence of adversarial
17

---

Under review as a conference paper at ICLR 2021
(a) GR
(b) MMR
(c) AT
(d) none
Figure 9: We evaluate the stochastic local Lipschitz constant (Eq. 12 networks trained in different ways on the Two Moons dataset uniformly over the grid. We see that GR exhibits local smoothness in regions around potentially adversarial examples, while preserving nonsmoothness elsewhere. In
contrast, the networks trained with MMR and adversarial training exhibit smoothness globally.
S
(a) GR
MMR
(c) AT
(d) none
Figure 10: We plot the decision boundaries for robust and non-robust networks on the Two Moons
dataset corresponding to Eq. IT the difference in likelihoods between the most likely class and the second most likely class. We that relative networks trained with other methods, networks trained with GR exhibits a larger gap i.e. more confidence for regions around the decision boundary (Pa Pg is large).
As a consequence, after training a robust network, we expect the true analytic centers of given polytope be semantically interpretable and close to "real" samples. We demonstrate that this the case in Figure First, note that the ACs of polytopes produced by a vanilla network are entirely noisy, We hypothesize (Fig. (5) that partitions converge early in training, and that the linear functions on each partition are the focus of the majority of training. As consequence, the content of polytopes for clear that the analytic centers of robust network polytopes non-robust networks are near-random.
are more interpretable (Fig.
D.3 VISUALIZING THE STRUCTURE OF ROBUST MODELS
We demonstrate several properties of networks trained with robust regularization terms. We train a single hidden layer feed forward ReLU network the Two Moons dataset. The decision boundaries are presented in Fig. I0 We estimate decision boundaries by plotting
r (x)
max L(v) max L(y) EEk
(11)
JER
where L(x) Eeenn and are the logits of f evaluated at æ. In other words, r(x) directly corresponds to the second term of the Lipschitz robustness bound of f at a. We first note Fig. that MMR and GR preserve the decision boundary learned by the vanilla network for the most
18

---

Under review as a conference paper at ICLR 2021
GR
(b) MMR
(c) AT
(d)
GR
MMR
(g) AT
(h) none
Figure 11: We evaluate the GR (top) and MMR (bottom) regularization terms uniformly over grid for networks trained different ways on the Two Moons dataset.
(a) GR
(b) MMR
(c) AT
(d) none
(e) GR
O MMR
(g) AT
(h) none
Figure 12: We evaluate the GR (top) and MMR (bottom) regularization terms uniformly over grid for networks trained in different ways on the Two Moons dataset. Although the numerical scale of the costs differ, it seems clear that GR exhibits the desirable property smoothness over the inputs.
19

---

Under review as a conference paper at ICLR 2021
part, however, the network trained via adversarial training has over-regularized, resulting in sub- optimal classifier. Interestingly, the regularizer we propose does exhibit a significant gap between the most likely and second most likely class likelihoods this is desirable property with respect to the GR robustness guarantee. We also notice that the network trained with GR exhibits less uniform smoothness compared to the other regularizers seen in Fig. ? MMR and adversarial training appear to over-regularize the network by imposing smoothness uniformly over the domain.
In Figures I1 and 12 we demonstrate that the network trained with GR exhibits spatial smoothness in contrast to the MMR term, i.e. neighboring points exhibit similar regularization loss. We hypothesize that this may partially provide evidence for (1) the empirical reduction in the number of linear partitions and increases their size (Fig. [5] such that more points are co-located within the interior of the same polytope and (2) smoother optimization.
In Fig. 9 we visualize the local smoothness of robust and non-robust networks. We uniformly sample points from the 2-d cube and approximate the stochastic local Lipschitz constant of f by computing the following term:
N f(x) (xx) = N
1
f(x 5,)
(12)
57
where 6; ~ M(o,e)- Note that for large values of L around point x, f exhibits local instability, and potentially brittleness with respect to adversarial perturbations of x. In conjunction with Fig T0 that GR along with AT and MMR exhibits behavioral properties that are typical of robust networks (e.g. local smoothness and confidence).
We also plot visualizations of layer-weights for fully connected network It is well-known that structured neuron weights lead to more robust networks (Allen-Zhu & Li 2020). However it has only been recently deeply explored in the context of adversarial machine learning (Allen-Zhi & Li| 2020). We demonstrate that networks trained with GR exhibit this property of encouraging neurons to learn structured features.
E EFFICIENT PRUNING OF REDUNDANT POLYTOPE REPRESENTATIONS
To remedy the issue of redundant representations of polytopes, we propose the following masked- version of ACR:
d
AC' (CBassac
= Σ log(a,
ByZz))
(13)
IR
j=1
where Ω is the index-set of irredundant hyperplanes. To compute Ω we leverage the primal-dual equivalence between allfe intersections and convex hulls and adopt the approximate convex-hull hull algorithm of Sartipizadeh & Vincent (2016) to prune redundant hyperplanes.
Given finite set of points S {=1-- .N } where each i; E Rd |Sartipizadeh & Vincent (016) propose to iteratively build an estimate an c-approximate convex hull (denoted by 8) selecting a point add & such that the maximum over all projections from S È to is minimized (i.e. is an extreme point of S), where the projection length from point to is computed by solving the following quadratic program:
[
d(v,E) min og
||
l|2
s.l. 2 0, 0g =
instead of exactly solving this problem. Sartipizadeh & Vincent (016) propose to select points that are c-close to the convex hull- - i.e. by requiring that max.es d(u E) c. In summary, at iteration t the algorithm selects 2, to add to E according to the following decision nule:
St = arg min ees max d(v, E wr)
WESiE
20

---

Under review as a conference paper at ICLR 2021
Note that not guaranteed uniqueness, in that there may be multiple & with the same number of elements, satisfying the distance requirements. However, as e increases, the size of a minimal representation, &, may decrease.
Notably, the above algorithm runs in time independent-of the dimension: O(K3/2 N2 log + for N points in dimension d, and where is the number of iterations. Additionally, it is provably correct, i.c. after the algorithm terminates the set & is guaranteed to be e-approximate convex hull of S where an e-aproxximate convex hull is defined to be:
Definition E.1 (c-approximate convex hull). An e-approximate convex hull of S is the convex hull of minimal subset & C S such that V2 E S, d(z,8) S e.
21


Reviews:
[{"review_id": "uHeTfzB52VD", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "As a reader and a reviewer, I am not unable to follow the main theoretical point in the paper. The proof of Theorem 1 is not properly explained with ambiguous reference to other articles. \n\nMore specifically, regarding the proof of Theorem 1 in Appendix A.2, the authors do not provide enough details nor explanation for the second part of the statement. Merely writing something like 'follow from papers xxx' without any details makes the proof unreadable.\n\nI think as a basic principle, the authors should consider readers' convenience and provide a self-contained proof and intuitive explanation of the claims. At least they should specify what results from outside are used in their theoretical analysis.\n\nThe careless treatment of theory makes the manuscript unreadable, and thus the present form is not qualify for an ICLR submission.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hsUFWTeEg5k", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The authors exploit the piecewise linear nature of ReLU neural networks to design a new regularizer that improves the robustness of the neural network. It can be viewed as a alternative to the regularizer proposed in Croce et al. (2018) -- the current regularizer uses the analytic center, whereas the previous work (named MMR) guarantees that are straightforward consequences of the geometric interpretation. The experimental setup is similar to the one in Croce et al. (2018), which compares the result of different adversarial defense methods on MNIST, F-MNIST, and CIFAR10 on small shallow networks. These computational results generally slightly outperform MMR on MNIST.\n\nThe paper is polished and well-written, and the use of the analytic center is reasonably motivated via the geometry of the neural network.\n\nHowever, the paper has a few major drawbacks that need to be addressed before acceptance.\n\n(1) Novelty: The paper can be seen as a twist on Croce et al., working off some of the same intuition and using very similar experiments. The theoretical results are a simple consequence of using the analytic center. Hence, this work can be viewed as incremental.\n\n(2) Experimental Results: Given that the set of regularization approaches has significantly grown since the prior paper was published, the authors should at least compare their methods with some of these. This is especially important given that the results are not much better than MMR (and worse in some cases).\n\n(3) Computational Considerations: The computation effort needed to incorporate this regularizer should be discussed explicitly so the reader can understand the trade-offs between incorporating this regularizer vs. other defense methods.\n\nSide note:\nThe authors should update the citation for Croce et al. to refer to the conference version of the paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "MIKpdxPvX1", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper present some regularization schemes for ReLU networks, based in geometrical properties (polytopes and analytical centers), aiming at robustifying networks against adversarial examples. The idea is to train the network such that the partition of the input space contains many less linear regions, and such that in each region, training points are gathered around the analytical center (and thus far from boundaries), making more difficult the attack task. \nDoing so the authors can  give certificates for robustness.  The proposed approach appears to be competitive in terms of bounds and do so with less hyper-parameters than other methods. \n\nThe idea of using regularization terms to make networks more robust makes sense, the particular proposed regularizers have some quite easy to catch motivation. \nThe presented results match state-of-the-art, however I have some (maybe naive) questions : \n-> why TE are missing sometimes? \n-> how can LB>UB (CNN l_inf) ? I would have say that max(LB)=min(UB)=true minimal distortion ? \nFig 3 is unreadable which is a pity since I think it could be some relevant information, its interpretation is quite brief too. \n\nOverall I think the presented work is interesting and quite well executed. Theoretical part seems ok, but I'm not familiar with some geometric notions so I might have missed things. \nI tend to accept the paper but I'm waiting for more explanations on the experimental results. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a novel regularization scheme for showing provable robustness guarantees for the class of ReLU networks.
The reviews of this paper were mixed but leaning more to reject. Even though geometric approaches to adversarial robustness are appealing there are too many issues left open (see below for detailed comments) so that the paper is not above the bar for ICLR.

Detailed comments:
 - incremental resp. small theoretical contribution: the bounds in Theorem 1 are worse than what has been derived in Croce et al (2019), which is admitted only in the Experiments section but this should directly be discussed after Theorem 1, or are based on other's work Moosavi-Dezfooli et al(2019)
 - the proofs are still not very clear even after the update e.g. it is not clear to me what is meant with the distance to the decision boundary d_D(x) as this quantity cannot be computed (this is the whole point here)
 - the experimental results are in most of the cases worse than prior work (KW and MMR). The authors argue that their results hold for both threat models but then the l_infty/l_2 robustness of the other models should have been provided to make the point.
Moreover, if multiple norm ball threat models is the point, then the authors should compare to the follow up work of Croce et al at ICLR 2020 which explicitly optimizes all l_p-balls. 
- the point with gradient obfuscation of MMR does not make sense to me as the gap between upper and lower bounds on the robust error is quite small for MMR in most cases. Gradient obfuscation would mean that the PGD attack fails and thus the lower bound would have to be close to zero. 
- Figure 1c) looks like the Figure from the book of Boyd and Vandenberghe - if this is the case then it has to be correctly referenced in the caption

Decision: Reject