Provable defenses against adversarial examples via the convex outer adversarial polytope

Introduction

Recent work in deep learning has demonstrated the prevalence of adversarial examples (Szegedy et al., 2014; Goodfellow et al., 2015), data points fed to a machine learning algorithm which are visually indistinguishable from “normal” examples, but which are specifically tuned so as to fool or mislead the machine learning system. Recent history in adversarial classification has followed something of a virtual “arms race”: practitioners alternatively design new ways of hardening classifiers against existing attacks, and then a new class of attacks is developed that can penetrate this defense. Distillation (Papernot et al., 2016) was effective at preventing adversarial examples until it was not (Carlini & Wagner, 2017b). There was no need to worry about adversarial examples under “realistic” settings of rotation and scaling (Lu et al., 2017) until there was (Athalye & Sutskever, 2017). Nor does the fact that the adversary lacks full knowledge of the model appear to be a problem: “black-box” attacks are also extremely effective (Papernot et al., 2017). Even detecting the presence of adversarial examples is challenging (Metzen et al., 2017; Carlini & Wagner, 2017a), and attacks are not limited to synthetic examples, having been demonstrated repeatedly on real-world objects (Sharif et al., 2016; Kurakin et al., 2016). Somewhat memorably, many of the adversarial defense papers at the most recent ICLR conference were broken prior to the review period completing (Athalye et al., 2018).

Given the potentially high-stakes nature of many machine learning systems, we feel this situation is untenable: the “cost” of having a classifier be fooled just once is potentially extremely high, and so the attackers are the de-facto “winners” of this current game. Rather, one way to truly harden classifiers against adversarial attacks is to design classifiers that are guaranteed to be robust to adversarial perturbations, even if the attacker is given full knowledge of the classifier. Any weaker attempt of “security through obscurity” could ultimately prove unable to provide a robust classifier.

In this paper, we present a method for training provably robust deep ReLU classifiers, classifiers that are guaranteed to be robust against any norm-bounded adversarial perturbations on the training set. The approach also provides a provable method for detecting any previously unseen adversarial example, with zero false negatives (i.e., the system will flag any adversarial example in the test set, though it may also mistakenly flag some non-adversarial examples). The crux of our approach is to construct a convex outer bound on the so-called “adversarial polytope”, the set of all final-layer activations that can be achieved by applying a norm-bounded perturbation to the input; if we can guarantee that the class prediction of an example does not change within this outer bound, we have a proof that the example could not be adversarial (because the nature of an adversarial example is such that a small perturbation changed the class label). We show how we can efficiently compute and optimize over the “worst case loss” within this convex outer bound, even in the case of deep networks that include relatively large (for verified networks) convolutional layers, and thus learn classifiers that are provably robust to such perturbations. From a technical standpoint, the outer bounds we consider involve a large linear program, but we show how to bound these optimization problems using a formulation that computes a feasible dual solution to this linear program using just a single backward pass through the network (and avoiding any actual linear programming solvers).

Background and Related Work

In addition to general work in adversarial attacks and defenses, our work relates most closely to several ongoing thrusts in adversarial examples. First, there is a great deal of ongoing work using exact (combinatorial) solvers to verify properties of neural networks, including robustness to adversarial attacks. These typically employ either Satisfiability Modulo Theories (SMT) solvers (Huang et al., 2017; Katz et al., 2017; Ehlers, 2017; Carlini et al., 2017) or integer programming approaches (Lomuscio & Maganti, 2017; Tjeng & Tedrake, 2017; Cheng et al., 2017). Of particular note is the PLANET solver (Ehlers, 2017), which also uses linear ReLU relaxations, though it employs them just as a sub-step in a larger combinatorial solver. The obvious advantage of these approaches is that they are able to reason about the exact adversarial polytope, but because they are fundamentally combinatorial in nature, it seems prohibitively difficult to scale them even to medium-sized networks such as those we study here. In addition, unlike in the work we present here, the verification procedures are too computationally costly to be integrated easily to a robust training procedure.

By far the most similar paper to this work is the concurrent work of Raghunathan et al. (2018), who develop a semidefinite programming-based relaxation of the adversarial polytope (also bounded via the dual, which reduces to an eigenvalue problem), and employ this for training a robust classifier. However, their approach applies only to two-layer networks, and only to fully connected networks, whereas our method applies to deep networks with arbitrary linear operator layers such as convolution layers. Likely due to this fact, we are able to significantly outperform their results on medium-sized problems: for example, whereas they attain a guaranteed robustness bound of 35% error on MNIST, we achieve a robust bound of 5.8% error. However, we also note that when we do use the smaller networks they consider, the bounds are complementary (we achieve lower robust test error, but higher traditional test error); this suggests that finding ways to combine the two bounds will be useful as a future direction.

Training Provably Robust Classifiers

This section contains the main methodological contribution of our paper: a method for training deep ReLU networks that are provably robust to norm-bounded perturbations. Our derivation roughly follows three steps: first, we define the adversarial polytope for deep ReLU networks, and present our convex outer bound; second, we show how we can efficiently optimize over this bound by considering the dual problem of the associated linear program, and illustrate how to find solutions to this dual problem using a single modified backward pass in the original network; third, we show how to incrementally compute the necessary elementwise upper and lower activation bounds, using this dual approach. After presenting this algorithm, we then summarize how the method is applied to train provably robust classifiers, and how it can be used to detect potential adversarial attacks on previously unseen examples.

with $z_{1}\equiv x$ and $f_{\theta}(x)\equiv\hat{z}_{k}$ (the logits input to the classifier). We use $\theta=\{W_{i},b_{i}\}_{i=1,\dots,k}$ to denote the set of all parameters of the network, where $W_{i}$ represents a linear operator such as matrix multiply or convolution.

For multi-layer networks, $\mathcal{Z}_{\epsilon}(x)$ is a non-convex set (it can be represented exactly via an integer program as in (Lomuscio & Maganti, 2017) or via SMT constraints (Katz et al., 2017)), so cannot easily be optimized over.

The foundation of our approach will be to construct a convex outer bound on this adversarial polytope, as illustrated in Figure 1. If no point within this outer approximation exists that will change the class prediction of an example, then we are also guaranteed that no point within the true adversarial polytope can change its prediction either, i.e., the point is robust to adversarial attacks. Our eventual approach will be to train a network to optimize the worst case loss over this convex outer bound, effectively applying robust optimization techniques despite non-linearity of the classifier.

We can conduct similar analysis on test examples as well. If the network predicts some class $\hat{y}$ on an example $x$, then we can use the same procedure as above to test whether the network will output any different class for a norm-bounded perturbation. If not, then the example cannot be adversarial, because no input within the norm ball takes on a different class (although of course, the network could still be predicting the wrong class). Although this procedure may incorrectly “flag” some non-adversarial examples, it will have zero false negatives, e.g., there may be a normal example that can still be classified differently due to a norm-bounded perturbation, but all norm-bounded adversarial examples will be detected.

2 Efficient Optimization via the Dual Network

Because solving an LP with a number of variables equal to the number of activations in the deep network via standard approaches is not practically feasible, the key aspect of our approach lies in our method for very efficiently bounding these solutions. Specifically, we consider the dual problem of the LP above; recall that any feasible dual solution provides a guaranteed lower bound on the solution of the primal. Crucially, we show that the feasible set of the dual problem can itself be expressed as a deep network, and one that is very similar to the standard backprop network. This means that providing a provable lower bound on the primal LP (and hence also a provable bound on the adversarial error), can be done with only a single backward pass through a slightly modified network (assuming for the time being, that we still have known upper and lower bounds for each activation). This is expressed in the following theorem

and $g_{\theta}(c,\alpha)$ is a $k$ layer feedforward neural network given by the equations

where $\nu$ is shorthand for $(\nu_{i},\hat{\nu}_{i})$ for all $i$ (needed because the objective $J$ depends on all $\nu$ terms, not just the first), and where $\mathcal{I}_{i}^{-}$, $\mathcal{I}_{i}^{+}$, and $\mathcal{I}_{i}$ denote the sets of activations in layer $i$ where the lower and upper bounds are both negative, both positive, or span zero respectively.

The “dual network” from (7) in fact is almost identical to the backpropagation network, except that for nodes $j$ in $\mathcal{I}_{i}$ there is the additional free variable $\alpha_{i,j}$ that we can optimize over to improve the objective. In practice, rather than optimizing explicitly over $\alpha$, we choose the fixed, dual feasible solution

This makes the entire backward pass a linear function, and is additionally justified by considerations regarding the conjugate set of the ReLU relaxation (see Appendix A.3 for discussion). Because any solution $\alpha$ is still dual feasible, this still provides a lower bound on the primal objective, and one that is reasonably tight in practice.The tightness of the bound is examined in Appendix B. Thus, in the remainder of this work we simply refer to the dual objective as $J(x,g_{\theta}(c))$, implicitly using the above-defined $\alpha$ terms.

3 Computing Activation Bounds

where $D_{i}$ is a diagonal matrix with entries

We can compute $(\nu_{i},\hat{\nu}_{i})$ and the corresponding upper bound $J_{\epsilon}(x,\nu)$ (which is now a vector) in a layer-by-layer fashion, first generating bounds on $\hat{z}_{2}$, then using these to generate bounds on $\hat{z}_{3}$, etc.

The resulting algorithm, which uses these backward pass variables in matrix form to incrementally build the bounds, is described in Algorithm 1. From here on, the computation of $J$ will implicitly assume that we also compute the bounds. Because the full algorithm is somewhat involved, we highlight that there are two dominating costs to the full bound computation: 1) computing a forward pass through the network on an “identity matrix” (i.e., a basis vector $e_{i}$ for each dimension $i$ of the input); and 2) computing a forward pass starting at an intermediate layer, once for each activation in the set $\mathcal{I}_{i}$ (i.e., for each activation where the upper and lower bounds span zero). Direct computation of the bounds requires computing these forward passes explicitly, since they ultimately factor into the nonlinear terms in the $J$ objective, and this is admittedly the poorest-scaling aspect of our approach. A number of approaches to scale this to larger-sized inputs is possible, including bottleneck layers earlier in the network, e.g. PCA processing of the images, random projections, or other similar constructs; at the current point, however, this remains as future work. Even without improving scalability, the technique already can be applied to much larger networks than any alternative method to prove robustness in deep networks that we are aware of.

4 Efficient Robust Optimization

Using the lower bounds developed in the previous sections, we can develop an efficient optimization approach to training provably robust deep networks. Given a data set $(x_{i},y_{i})_{i=1,\dots,N}$, instead of minimizing the loss at these data points, we minimize (our bound on) the worst location (i.e. with the highest loss) in an $\epsilon$ ball around each $x_{i}$, i.e.,

This is a standard robust optimization objective, but prior to this work it was not known how to train these classifiers when $f$ is a deep nonlinear network.

We also require that a multi-class loss function have the following property (all of cross-entropy, hinge loss, and zero-one loss have this property):

Under this assumption, we can upper bound the robust optimization problem using our dual problem in Theorem 2, which we prove in Appendix A.4.

Let $L$ be a monotonic loss function that satisfies Property 1. For any data point $(x,y)$, and $\epsilon>0$, the worst case adversarial loss from (11) can be upper bounded by

where $J_{\epsilon}$ is vector valued and as defined in (6) for a given $\epsilon$, and $g_{\theta}$ is as defined in (7) for the given model parameters $\theta$.

We denote the upper bound from Theorem 2 as the robust loss. Replacing the summand of (11) with the robust loss results in the following minimization problem

All the network terms, including the upper and lower bound computation, are differentiable, so the whole optimization can be solved with any standard stochastic gradient variant and autodiff toolkit, and the result is a network that (if we achieve low loss) is guaranteed to be robust to adversarial examples.

5 Adversarial Guarantees

Although we previously described, informally, the guarantees provided by our bound, we now state them formally. The bound for the robust optimization procedure gives rise to several provable metrics measuring robustness and detection of adversarial attacks, which can be computed for any ReLU based neural network independently from how the network was trained; however, not surprisingly, the bounds are by far the tightest and the most useful in cases where the network was trained explicitly to minimize a robust loss.

The upper bound from Theorem 2 functions as a certificate that guarantees robustness around an example (if classified correctly), as described in Corollary 1. The proof is immediate, but included in Appendix A.5.

For a data point $x$, label $y^{\star}$ and $\epsilon>0$, if

We denote the fraction of examples that do not have this certificate as the robust error. Since adversaries can only hope to attack examples without this certificate, the robust error is a provable upper bound on the achievable error by any adversarial attack.

Detecting adversarial examples at test time

The certificate from Theorem 1 can also be modified trivially to detect adversarial examples at test time. Specifically, we replace the bound based upon the true class $y^{\star}$ to a bound based upon just the predicted class $\hat{y}=\max_{y}f_{\theta}(x)_{y}$. In this case we have the following simple corollary.

For a data point $x$, model prediction $\hat{y}=\max_{y}f_{\theta}(x)_{y}$ and $\epsilon>0$, if

then $x$ cannot be an adversarial example. Specifically, $x$ cannot be a perturbation of a “true” example $x^{\star}$ with $\|x-x^{\star}\|_{\infty}\leq\epsilon$, such that the model would correctly classify $x^{\star}$, but incorrectly classify $x$.

ϵitalic-ϵ\epsilon-distances to decision boundary

Experiments

Here we demonstrate the approach on small and medium-scale problems. Although the method does not yet scale to ImageNet-sized classifiers, we do demonstrate the approach on a simple convolutional network applied to several image classification problems, illustrating that the method can apply to approaches beyond very small fully-connected networks (which represent the state of the art for most existing work on neural network verification). Scaling challenges were discussed briefly above, and we highlight them more below. Code for these experiments is available at http://github.com/locuslab/convex_adversarial.

A summary of all the experiments is in Table 1. For all experiments, we report the clean test error, the error achieved by the fast gradient sign method (Goodfellow et al., 2015), the error achieved by the projected gradient descent approach (Madry et al., 2017), and the robust error bound. In all cases, the robust error bound for the robust model is significantly lower than the achievable error rates by PGD under standard training. All experiments were run on a single Titan X GPU. For more experimental details, see Appendix B.

We consider training a robust binary classifier on a 2D input space with randomly generated spread out data points. Specifically, we use a 2-100-100-100-100-2 fully connected network. Note that there is no notion of generalization here; we are just visualizing and evaluating the ability of the learning approach to fit a classification function robustly.

2 MNIST

We present results on a provably robust classifier on the MNIST data set. Specifically, we consider a ConvNet architecture that includes two convolutional layers, with 16 and 32 channels (each with a stride of two, to decrease the resolution by half without requiring max pooling layers), and two fully connected layers stepping down to 100 and then 10 (the output dimension) hidden units, with ReLUs following each layer except the last.

Figure 4 shows the training progress using our procedure with a robust softmax loss function and $\epsilon=0.1$. As described in Section 3.4, any norm-bounded adversarial technique will be unable to achieve loss or error higher than the robust bound. The final classifier after 100 epochs reaches a test error of 1.80% with a robust test error of 5.82%. For a traditionally-trained classifier (with 1.07% test error) the FGSM approach results in 50.01% error, while PGD results in 81.68% error. On the classifier trained with our method, however, FGSM and PGD only achieve errors of 3.93% and 4.11% respectively (both, naturally, below our bound of 5.82%). These results are summarized in Table 1.

Using Newton’s method with backtracking line search, for each example, we can compute in 5-6 Newton steps the maximum $\epsilon$ that is robust as described in (17) for both a standard classifier and the robust classifier. Figure 5 shows the maximum $\epsilon$ values calculated for each testing data point under standard training and robust training. Under standard training, the correctly classified examples have a lower bound of around $0.007$ away from the decision boundary. However, with robust training this value is pushed to 0.1, which is expected since that is the robustness level used to train the model. We also observe that the incorrectly classified examples all tend to be relatively closer to the decision boundary.

3 Other Experiments

We present the results of our robust classifier on the Fashion-MNIST dataset (Xiao et al., 2017), a harder dataset with the same size (in dimension and number of examples) as MNIST (for which input binarization is a reasonable defense). Using the same architecture as in MNIST, for $\epsilon=0.1$, we achieve a robust error of 34.53%, which is fairly close to the PGD error rate of 31.63% (Table 1). Further experimental details are in Appendix B.3.

HAR

We present results on a human activity recognition dataset (Anguita et al., 2013). Specifically, we consider a fully connected network with one layer of 500 hidden units and $\epsilon=0.05$, achieving 21.90% robust error.

SVHN

Finally, we present results on SVHN. The goal here is not to achieve state of the art performance on SVHN, but to create a deep convolutional classifier for real world images with provable guarantees. Using the same architecture as in MNIST, for $\epsilon=0.01$ we achieve a robust error bound of 42.09%, with PGD achieving 34.52% error. Further experimental details are in Appendix B.5.

4 Discussion

Scaling to ImageNet-sized classification problems remains a challenging task; the MNIST classifier takes about 5 hours to train for 100 epochs on a single Titan X GPU, which is between two and three orders of magnitude more costly than naive training. But because the approach is not combinatorially more expensive in its complexity, we believe it represents a much more feasible approach than those based upon integer programming or satisfiability, which seem highly unlikely to ever scale to such problems. Thus, we believe the current performance represents a substantial step forward in research on adversarial examples.

Conclusion

In this paper, we have presented a method based upon linear programming and duality theory for training classifiers that are provably robust to norm-bounded adversarial attacks. Crucially, instead of solving anything costly, we design an objective equivalent to a few passes through the original network (with larger batch size), that is a guaranteed bound on the robust error and loss of the classifier.

While we feel this is a substantial step forward in defending classifiers, two main directions for improvement exist, the first of which is scalability. Computing the bounds requires sending an identity matrix through the network, which amounts to a sample for every dimension of the input vector (and more at intermediate layers, for each activation with bounds that span zero). For domains like ImageNet, this is completely infeasible, and techniques such as using bottleneck layers, other dual bounds, and random projections are likely necessary. However, unlike many past approaches, this scaling is not fundamentally combinatorial, so has some chance of success even in large networks.

Finally, although our focus in this paper was on adversarial examples and robust classification, the general techniques described here (optimizing over relaxed convex networks, and using a non-convex network representation of the dual problem to derive guaranteed bounds), may find applicability well beyond adversarial examples in deep learning. Many problems that invert neural networks or optimize over latent spaces involve optimization problems that are a function of the neural network inputs or activations, and similar techniques may be brought to bear in these domains as well.

Acknowledgements

This work was supported by a DARPA Young Faculty Award, under grant number N66001-17-1-4036. We thank Frank R. Schmidt for providing helpful comments on an earlier draft of this work.

References

Appendix A Adversarial Polytope

Recall (4), which uses a convex outer bound of the adversarial polytope.

With the convex outer bound on the ReLU constraint and the adversarial perturbation on the input, this minimization problem is the following linear program

A.2 Proof of Theorem 1

In this section we derive the dual of the LP in (19), in order to prove Theorem 1, reproduced below:

and $g_{\theta}(c,\alpha)$ is a $k$ layer feedforward neural network given by the equations

where $\nu$ is shorthand for $(\nu_{i},\hat{\nu}_{i})$ for all $i$ (needed because the objective $J$ depends on all $\nu$ terms, not just the first), and where $\mathcal{I}_{i}^{-}$, $\mathcal{I}_{i}^{+}$, and $\mathcal{I}_{i}$ denote the sets of activations in layer $i$ where the lower and upper bounds are both negative, both positive, or span zero respectively.

In detail, we associate the following dual variables with each of the constraints

where we note that can easily eliminate the dual variables corresponding to the $z_{i,j}=0$ and $z_{i,j}=\hat{z}_{i,j}$ from the optimization problem, so we don’t define explicit dual variables for these; we also note that $\mu_{i,j}$, $\tau_{i,j}$, and $\lambda_{i,j}$ are only defined for $i,j$ such that $j\in\mathcal{I}_{i}$, but we keep the notation as above for simplicity. With these definitions, the dual problem becomes

The key insight we highlight here is that the dual problem can also be written in the form of a deep network, which provides a trivial way to find feasible solutions to the dual problem, which can then be optimized over. Specifically, consider the constraints

Note that the dual variable $\lambda$ corresponds to the upper bounds in the convex ReLU relaxation, while $\mu$ and $\tau$ correspond to the lower bounds $z\geq 0$ and $z\geq\hat{z}$ respectively; by the complementarity property, we know that at the optimal solution, these variables will be zero if the ReLU constraint is non-tight, or non-zero if the ReLU constraint is tight. Because we cannot have the upper and lower bounds be simultaneously tight (this would imply that the ReLU input $\hat{z}$ would exceed its upper or lower bound otherwise), we know that either $\lambda$ or $\mu+\tau$ must be zero. This means that at the optimal solution to the dual problem

i.e., the dual variables capture the positive and negative portions of $(W_{i}^{T}\nu_{i+1})_{j}$ respectively. Combining this with the constraint that

which we will abbreviate as $\nu=g_{\theta}(c,\alpha)$ to emphasize the fact that $-c$ acts as the “input” to the network and $\alpha$ are per-layer inputs we can also specify (for only those activations in $\mathcal{I}_{i}$), where $\nu$ in this case is shorthand for all the $\nu_{i}$ and $\hat{\nu}_{i}$ activations.

The final objective we are seeking to optimize can also be written

A.3 Justification for Choice in α𝛼\alpha

We can re-express this using conjugate functions defined as

Plugging this in, we can minimize over each $\hat{z}_{i},z_{i}$ pair independently

Substituting the conjugate functions into the Lagrangian, and letting $\hat{\nu}_{i}=W_{i}^{T}\nu_{i+1}$, we get

This is almost the form of the dual network. The last step is to plug in the indicator function for the outer bound of the ReLU activation (we denote the ReLU polytope) for $f_{i}$ and derive $f^{*}_{i}$.

ReLU polytope

If $u\leq 0$ then $\mathcal{S}\subset\{(\hat{z},z):z=0\}$. Then, $I^{*}_{\mathcal{S}}(\hat{y},y)\leq\max_{\hat{z}}\hat{y}\cdot\hat{z}=I(\hat{y}=0)$.

Let $\mathcal{S}$ be the set of the third case. Then:

Recall that in the LP form, the forward pass in this case was defined by

Combining this with the earlier two cases and plugging into (34) using $f^{*}_{i}=I^{*}_{\mathcal{S}}$ results in

where the dual network here matches the one from (7) exactly when $\alpha=\frac{u_{i,j}}{u_{i,j}-l_{i,j}}$.

A.4 Proof of Theorem 2

In this section, we prove Theorem 2, reproduced below:

Let $L$ be a monotonic loss function that satisfies Property 1. For any data point $(x,y)$, and $\epsilon>0$, the worst case adversarial loss from (11) can be upper bounded with

where $J_{\epsilon}$ is as defined in (6) for a given $x$ and $\epsilon$, and $g_{\theta}$ is as defined in (7) for the given model parameters $\theta$.

First, we rewrite the problem using the adversarial polytope $\mathcal{Z}_{\epsilon}(x)$.

Since $L(x,y)\leq L(x-a1,y)$ for all $a$, we have

where $C=(I-\mathbf{e}_{y}1^{T})$. Since $L$ is a monotone loss function, we can upper bound this further by using the element-wise maximum over $[C\hat{z}_{k}]_{i}$ for $i\neq y$, and elementwise-minimum for $i=y$ (note, however, that for $i=y$, $[C\hat{z}_{k}]_{i}=0$). Specifically, we bound it as

where, if $C_{i}$ is the $i$th row of $C$, $h(z_{k})$ is defined element-wise as

This is exactly the adversarial problem from (2) (in its maximization form instead of a minimization). Recall that $J$ from (6) is a lower bound on (2) (using $c=-C_{i}$).

Multiplying both sides by $-1$ gives us the following upper bound

Applying this upper bound to $h(z_{k})_{i}$, we conclude

Applying this to all elements of $h$ gives the final upper bound on the adversarial loss.

A.5 Proof of Corollary 1

In this section, we prove Corollary 1, reproduced below:

For a data point $x$ and $\epsilon>0$, if

Recall that $J$ from (6) is a lower bound on (2). Combining this fact with the certificate in (40), we get that for all $y\neq f(x)$,

Crucially, this means that for every point in the adversarial polytope and for any alternative label $y$, $(\hat{z}_{k})_{f(x)}\geq(\hat{z}_{k})_{y}$, so the classifier cannot change its output within the adversarial polytope and is robust around $x$. ∎

Appendix B Experimental Details

We use the Adam optimizer (Kingma & Ba, 2015) (over the entire batch of samples) with a learning rate of 0.001.

Comparison to Naive Layerwise Bounds

with the convex outer approximation mirroring it rather closely. In contrast, the layerwise bounds produce the bound:

Such bounds are essentially vacuous in our case, which makes sense intuitively. The naive bound has no way to exploit the “tightness” of activations that lie entirely in the positive space, and effectively replaces the convex ReLU approximation with a (larger) box covering the entire space. Thus, such bounds are not of particular use when considering robust classification.

It is of some interest to see what the true adversarial polytope for the examples in this data set looks like versus the convex approximation, evaluated at the solution of the robust optimization problem. Figure 7 shows one of these figures, highlighting the fact that for the final network weights and choice of epsilon, the outer bound is empirically quite tight in this case. In Appendix B.2 we calculate exactly the gap between the primal problem and the dual bound on the MNIST convolutional model. In Appendix B.4, we will see that when training on the HAR dataset, even for larger $\epsilon$, the bound is empirically tight.

B.2 MNIST

We use the Adam optimizer (Kingma & Ba, 2015) with a learning rate of 0.001 (the default option) with no additional hyperparameter selection. We use minibatches of size 50 and train for 100 epochs.

Depending on the random weight initialization of the network, the optimization process for training a robust MNIST classifier may get stuck and not converge. To improve convergence, it is helpful to start with a smaller value of $\epsilon$ and slowly increment it over epochs. For MNIST, all random seeds that we observed to not converge for $\epsilon=0.1$ were able to converge when started with $\epsilon=0.05$ and taking uniform steps to $\epsilon=0.1$ in the first half of all epochs (so in this case, 50 epochs).

Random filters from the two convolutional layers of the MNIST classifier after robust training are plotted in Figure 9. We see a similar story in both layers: they are highly sparse, and some filters have all zero weights.

We plot histograms to visualize the distributions of pre-activation bounds over examples in Figure 10. We see that in the first layer, examples have on average more than half of all their activations in the $\mathcal{I}^{-}_{1}$ set, with a relatively small number of activations in the $\mathcal{I}_{1}$ set. The second layer has significantly more values in the $\mathcal{I}^{+}_{2}$ set than in the $\mathcal{I}^{-}_{2}$ set, with a comparably small number of activations in the $\mathcal{I}_{2}$ set. The third layer has extremely few activations in the $\mathcal{I}_{3}$ set, with 90% all of the activations in the $\mathcal{I}^{-}_{3}$ set. Crucially, we see that in all three layers, the number of activations in the $\mathcal{I}_{i}$ set is small, which benefits the method in two ways: a) it makes the bound tighter (since the bound is tight for activations through the $\mathcal{I}^{+}_{i}$ and $\mathcal{I}^{-}_{i}$ sets) and b) it makes the bound more computationally efficient to compute (since the last term of (6) is only summed over activations in the $\mathcal{I}_{i}$ set).

We empirically evaluate the tightness of the bound by exactly computing the primal LP and comparing it to the lower bound computed from the dual problem via our method. We find that the bounds, when computed on the robustly trained classifier, are extremely tight, especially when compared to bounds computed for random networks and networks that have been trained under standard training, as can be seen in Figure 11.

B.3 Fashion-MNIST

We use exactly the same parameters as for MNIST: Adam optimizer with the default learning rate 0.001, minibatches of size 50, and trained for 100 epochs.

Figure 12 plots the error and loss curves (and their robust variants) of the model over epochs. We observe no overfitting, and suspect that the performance on this problem is limited by model capacity.

B.4 HAR

We use the Adam optimizer with a learning rate 0.0001, minibatches of size 50, and trained for 100 epochs.

Figure 13 plots the error and loss curves (and their robust variants) of the model over epochs. The bottleneck here is likely due to the simplicity of the problem and the difficulty level implied by the value of $\epsilon$, as we observed that scaling to more more layers in this setting did not help.

Earlier, we observed that on random networks, the bound gets progressively looser with increasing $\epsilon$ in Figure 6. In contrast, we find that even if we vary the value of $\epsilon$, after robust training on the HAR dataset with a single hidden layer, the bound still stays quite tight, as seen in Table 2. As expected, training a robust model with larger $\epsilon$ results in a less accurate model since the adversarial problem is more difficult (and potentially impossible to solve for some data points), however the key point is that the robust bounds are extremely close to the achievable error rate by FGSM, implying that in this case, the bound is tight.

B.5 SVHN

We use the Adam optimizer with the default learning rate 0.001, minibatches of size 20, and trained for 100 epochs. We used an $\epsilon$ schedule which took uniform steps from $\epsilon=0.001$ to $\epsilon=0.01$ over the first 50 epochs.

Note that the robust testing curve is the only curve calculated with $\epsilon=0.01$ throughout all 100 epochs. The robust training curve was computed with the scheduled value of $\epsilon$ at each epoch. We see that all metrics calculated with the scheduled $\epsilon$ value steadily increase after the first few epochs until the desired $\epsilon$ is reached. On the other hand, the robust testing metrics for $\epsilon=0.01$ steadily decrease until the desired $\epsilon$ is reached. Since the error rate here increases with $\epsilon$, it suggests that for the given model capacity, the robust training cannot achieve better performance on SVHN, and a larger model is needed.