Global Adversarial Robustness Guarantees for Neural Networks
Authors: Luca Laurenti
Andrea Patane
Matthew Wicker
Luca Bortolussi
Luca Cardelli
Marta Kwiatkowska
Venue:  (2020)
Keywords: Adversarial Robustness
Statistical Guarantees
Deep Neural Networks
Bayesian Neural Networks

Abstract: We investigate global adversarial robustness guarantees for machine learning models.  Specifically, given a trained model we consider the problem of computing the probability that its prediction at any point sampled from the (unknown) input distribution is susceptible to adversarial attacks.  Assuming continuity of the model, we prove measurability for a selection of local robustness properties used in the literature. We then show how concentration inequalities can be employed to compute global robustness with estimation error upper-bounded by $\epsilon$, for any $\epsilon > 0$ selected a priori. We utilise the methods to provide statistically sound analysis of the robustness/accuracy trade-off for a variety of neural networks architectures and training methods on MNIST, Fashion-MNIST and CIFAR. We empirically observe that robustness and accuracy tend to be negatively correlated for networks trained via stochastic gradient descent and with iterative pruning techniques, while a positive trend is observed between them in Bayesian settings.

Under review as a conference paper at ICLR 2020
GLOBAL ADVERSARIAL ROBUSTNESS GUARANTEES FOR NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate global adversarial robustness guarantees for machine learning models. Specifically, given trained model we consider the problem of com- puting the probability that its prediction at any point sampled from the (unknown) input distribution is susceptible to adversarial attacks. Assuming continuity of the model, we prove measurability for selection of local robustness properties used in the literature. We then show how concentration inequalities can be employed to compute global robustness with estimation error upper-bounded by for any e > 0 selected a priori. We utilise the methods to provide statistically sound analysis of the robustness/accuraay trade-off for variety of neural networks ar- chitectures and training methods on MNIST, Pashion-MNISS and CIFAR. We empirically observe that robustness and accuracy tend to be negatively correlated for networks trained via stochastic gradient descent and with iterative pruning techniques, while a positive trend is observed between them in Bayesian settings.
INTRODUCTION
Adversarial attacks are potentially imperceptible input manipulations that when applied to a test point result in misclassification. Since even state-of-the--rt deep learning models have been shown susceptible to such attacks (Goodfellow et al. 2014). adversarial examples have raised serious con- cerns about the security and robustness of models learned from data (Biggio & Roli 2018). As standard accuracy measures fail to capture model behaviour in adversarial setting, the develop- ment of techniques capable of quantifying the robustness of machine learning models is an essential pre-condition for their application in safety-critical scenarios, where model failures have already led to fatal accidents (Yadron& & Tynan 2016). In such settings, we require models that are not only accurate, but also have guaranteed robust behaviour (Michelmore al. 2019). However, while tech- niques for the computation of local adversarial robustness guarantees (i.e., specific to a particular test point) have been developed for variety of machine learning models (Katz al. 2017 Biggio & Roli, 2018 Cardelli et al. 2019b), to the best of our knowledge relatively few studies of global robustness (Bastani et al.) [016;] Ruan al., 2019: Webb et al. 2018) have been considered, and none rigorously quantify the probability that a neural network is robust to adversarial perturbations.
Given a neural network (NN) f we investigate the global robustness properties of f. We start from a local notion of robustness specific to a point (e.g. robustness against bounded norm perturbations or adversarial attacks) and pose the problem of computing the probability that the prediction of f in a test point sampled from a (possibly unknown) data distribution P, is robust according to a given local property. Unfortunately, exact computation of such global robustness measures is intractable. Nevertheless, we show how statistically sound approximations with quantifiable and arbitrarily small error can be computed by making use concentration inequalities (Massart. 2007). Crucially, this allows to provide statistical guarantees over the estimation of the global robustness measures, while keeping computations to a minimum. In order to do so, we prove that the global adversarial robustness property defined here is measurable for range of commonly used notions of adversarial examples and NN architectures, and show how global robustness can be reformulated as sum of independent and identically distributed random variables. Hence, bounds such additive Chernoff or Hoeffding's 's inequality can be used to quantify the error with respect to an empirical estimator.
We utilise our techniques to statistically quantify the robustness of a variety of different neural network architectures and training methods, and experimentally study their robustness profile on

---

Under review as a conference paper at ICLR 2020
multiple datasets, including MNIST, Fashion-MNISS and CIFAR. In particular, we analyse the ef- fects of iterative magnitude pruning on network robustness. Interestingly, while weight pruning may increase test set accuracy (as observed by Frankle & Carbin (2018). we find that it does not have any positive effect on global robustness for the examples we analysed. We further empirically eval- uate the robustness accuracy trade-off (Tsipras et al. 2018) for a wide selection of different network architectures and hyper- parameters, which allows us to compare different training regimes. We find that accuracy and robustness tend to be at odds in networks trained via stochastic gradient descent, whereas there seems to exist a positive correlation between accuracy and robustness in Bayesian set- tings. More specifically, for the datasets analysed, we observe that optimising Bayesian network architecture for accuracy leads to networks that are more robust against adversarial examples.
In summary, this paper makes the following main contributions:
We consider probabilistic global adversarial robustness measures for neural networks and prove their measurability.
We show how concentration inequalities can be used to provide statistical guarantees on global robustness estimations with an a priori error bound.
We investigate the trade off between robustness and accuracy for variety of networks architectures and training methods. We provide empirical results that suggest that networks trained by Bayesian methods might be more robust than their deterministic counter-parts.
Related Works Various methods, both heuristic and based on formal verification, have been de- rived to evaluate the local adversarial robustness of neural networks (Goodfellow et al. 2014 Wicker et al. 2018 Tramer et al. 2017: Katz et al. 2017 Cardelli et al. 20019]] Carlini et al. 2017). In ad- dition to local robustness, which focuses on a specific test point, global measures of robustness have also been discussed in the literature (Bastani et al. 2216; Ruan et al. 2019: Webb et al.) (011)). Intu- itively, these generalise the notion of local robustness to a set of test points (or a data distribution), so as to marginalise out their influence. This yields global measure of robustness for the network that describes the probability wrt the input distribution that a certain local property is satisfied (Dreossi] itt al.) 2019). While these approaches consider similar global robustness measures to those discussed here, they lack a characterisation of error bounds. In contrast, our approach provides statistical error bounds on the estimation of global robustness, up to any priori specified tolerance O.
Formal bounds on global adversarial robustness are given by (Fawzi et al. 2018). However, im- plementation details are given only for linear and quadratic classifiers, since the computation of the bound relies on the distance from the decision boundary. Our approach instead generalises to any continuous model for which local robustness can be computed. A worst-case notion of global ro- bustness is discussed by Katz et al. (2017): Gooiinat et al. (2018), where a network is considered globally adversarially robust if there are no input points that are vulnerable adversarial attacks. However, this notion of global robustness tends to be too pessimistic and hard to compute in practice, since it is valid for all points in the input space (independently of their likelihood wrt the imput distri- bution). Instead, the global robustness measure considered here is probabilistic, in that it computes the probability that point drawn from the data distribution is vulnerable to adversarial attacks.
Similar techniques to those used in this paper are applied for the computation of PAC bounds for the evaluation of the generalisation error of learning models (McAllester) 1999] Vapnik 2013) and their robustness (Xu & Mannor 2012 Gourdeau et al. 2019). This differs from the problem studied here as PAC aims at bounding the generalisation capabilitice of family of learning models, whereas our method yields bounds on a specific trained model. Additionally, when computing global robustness, we focus on analyzing the probability that a perturbation applied to a test point causes a prediction change, independently of the point ground truth (i.e. independently of the generalisation error).
GLOBAL ADVERSARIAL ROBUSTNESS OF NEURAL NETWORKS
In this section we discuss notions of global robustness for neural networks. Namely, first introduce qualitative and quantitative variants of local robustness, and then define global robustness as their expected values wrt the (possibly unknown) input distribution. Throughout this paper, we consider a neural network f g.m + _R" with any activation function and arbitrarily many layers, such that, for a test point RT. f(x) = (f)( .... fn (x)) represents the vector of the confidence
2

---

Under review as a conference paper at ICLR 2020
values for each of the class labels. D { y)) E Ry {1,...n]} n)} is test dataset comprising [D] input points, which we assume to be iid sampled from a distribution P.
Measure of Global Robustness. Given a test point x sampled from P. we consider the indicator function g I + {0,1] 1}, which returns 1 if f is locally robust in æ; and is defined as follows.
Definition 1. (Local Robustness) Given E Th and ô > O, lei T (i Th T xlp S 8), where - lp is Lp norm, be a 8-ball around x. Call ((z) arg ma
f((x) the set of
classes for which the confidence of f in x is maximised. Then we say that f is locally robust in around T iff g(x) 1, where:
g {1 o
ifC()) is a singleton and 43 T C(²) ((x)
otherwise.
That is, f is locally robust in x if small perturbations in the input do not cause classification change. Note that we require the predicted class of x to be unambiguous, i.e. C(x) comprises only one class, and otherwise uniquely defined in this case). Local robustness is widely used to investigate the properties of neural networks and various algorithms have been derived for its computation and approximation (Dreossi) et al. 2019). Details on how we compute or approximate g(æ) are given in Section 3.1
view the point not locally robust (as the classification decision output is not
Building on local robustness, we are interested in computing the global robustness of f. which is defined below as the probability that a test point sampled from P is locally robust. Definition 2. (Global Robustness) The robustness of f is defined as:
R(g) P.elepll(22) plg(=)] f g(z)p(x)dz,
where p the density probability associated P.
is important to emphasise that R(g) a property of the neural network, as the effect of each single input point is marginalised out when taking the expectation. We remark that, since is indicator function, under the assumption that g is measurable (discussed in detail in Section 3), follows that R(g) is well defined probability measure.
Quantitative Measure of Global Robustness. As discussed in the previous section, we define indicator function. It is often useful to consider quantitative notion for the
local robustness g robustness of f. For example, given a b-ball around a test point x, we may want to know not just if f is locally robust in æ, but also the maximal variation in the classification confidence values of the various classes, which evaluate the network's 's robustness independently of the decision procedure used for the classification. Further, one could require the model confidence be robust up specific output threshold (Katz et al. (2077). Specifically, given f and test point æ E R" we consider a function g(x) that quantifies the robustness of f in x and defined as follows.
Definition 3. (Quantitative Local Robustness) Given x E Rm and 8 > O, let T = fo E RR' olp 8), where
is an Lip norm, be 8-ball around x. We define the quantitative local robustness of f in x around T as:
g(x) max h(f(x), f()),
BET
where h R" R + R is given function that measure differences between f predictions.
In Section 4 we provide experimental results using h defined the Lox norm between predictions, as well as by checking whether this norm is greater than given threshold y > 0 (which is akin to the definition introduced by Katz al. (2017)). Similarly R(g), the following definition generalises quantitative local robustness to a global property, by taking the expectation of g(r) with respect to the input data distribution.
Definition 4. (Quantitative Global Robustness) The quantitative robustness of f is defined as:
D(g) = Ee- [g(x)] []]]
[())p(x)dr,
(2)
where p is the density probability associated to P.
Exact computation of R(g) and D(g) is infeasible it requires the computation of an integral with respect to an unknown input distribution. Nevertheless, in what follows, we show that under mild assumptions it is possible estimate these quantities with a priori arbitrarily stringent guarantees.
3

---

Under review as a conference paper at ICLR 2020
3 STATISTICAL GUARANTEES ON ADVERSARIAL ROBUSTNESS
In this section we derive estimations of R(g) and (gg) with arbitrarily stringent a priori statistical guarantees. In particular, in Equation 3 we consider empirical estimators of these quantities and then in Theorem | 2 we show that the probability that the error between these quantities and the real measures is greater than a threshold can be upper bounded by employing concentration inequalities. In Section 3.1 we review how and are computed or approximated in practice, and finally describe the global robustness guarantees computation pipeline Section 3.2] Proofs for the Propositions and Theorems state in this Section are reported in the Appendix Section
We consider the following empirical estimators:
RmmP
(g.
Σ (2.))ES
g(z)
D DOM (g.
Σ
g(z) |S|
(a.y)ES
where S is set of size [S] of test points iid sampled from P. In order to derive a worst-case scenario bound on the distance between R(g) and Rgm S), first have show that g a measurable function] In fact, the measurability of guarantees that R(g) is well defined probability measure induced by P. the data distribution. Hence, concentration inequalities can be applied bound the error between R(g) and RemP(g S).
Proposition 1. Assume that, for i E {l.....n.. fú. the i-th component of the neural network f is a continuous function, then g(x), as defined Definition] 7 is measurable.
Proof of Proposition is based on noticing that the set {z E R" [g(x) > 0} can be rewritten as the union of pre-images of measurable sets for measurable function. Note that the overwhelming majority of the neural networks commonly used in practice are continuous. Hence, the assumption in Proposition
[ is almost always verified in practice. At this point, we can state the following theorem, which bounds the probability that the distance between R(g) and femp S) is greater than e, for any >>0
Theorem 1. Assume that g is measurable, then for any holds that that for any (possibly unknown) input data distribution P
Prob() () () e) S 2e 2c'
Theorem [ gives a bound that is problem and architecture independent, that is it holds for any data distribution and any architecture of the network f. As illustrated in [oction|4.]] the required number of samples for given error tolerance e, although exponential in is generally under control in practice. The proof of Theorem relies on reformulating Equation [ as probability measure and then the application of the Chernoff bound to a sum of independent Bernoulli random variables.
In the remaining part of this section, we show how to derive statistical guarantees on the error be- tween Dgg) and Demp (g, S). Again, we first show that under mild assumptions g(x:) is measurable. Then, we use this result to bound the error by using concentration inequalities.
Proposition 2. Consider g, as defined in Definition
3 Then, under the assumption that (1x1, ((((z)) f(22)) is continuous in both In and I2, we have that g measurable.
In the following theorem we show that result similar to that of Theorem I can obtained also for the more general case of quantitative global robustness.
Theorem 2. Assume that g is measurable and that, for any inpul point x, B(x)) E [A, B] C RR.. Then, for any (possibly unknown) input data distribution P, it holds that
262
Prob(IDemP(E)
D(g)
E)
2e
(R-
Note that in practice it often the case that the output of a neural network is bounded (notably for classification problems and regression problems over bounded input space). The proof of Theorem relies on the application of union bound and Hoeffding incquality (Vapnik 2013), and the resulting upper bound is again problem and architecture independent.
In this paper by measurable we mean Borel measurable.
4

---

Under review as a conference paper at ICLR 2020
3.1 COMPUTATION OF LOCAL ROBUSTNESS g(z) AND g(2)
The computation of global robustness depends on the ability to compute local robustness g(x) (or analogously g(x)) for every input point xr that is, to establish the presence absence of an adver- sarial attack in a neighbourhood of x. For deep neural networks this is known to be NP-complete (Katz al., 2017). For exact computation of g(z) we employ the verification method introduced by (Huang et al. 2017), which builds on input space discretisation and constraint solving to perform exhaustive search of the neighbourhood. Results for this are discussed in Section Unfortunately, the computational complexity for the exact computation of g(æ) quickly gets prohibitive for large networks. As in (Bastani et al. 2016), in these cases we proceed by approximating local robust- ness. The trade-off between scalability and approximation quality of adversarial attack method is empirically discussed in (Carlini et al. 2017). We remark that the statistical bounds we compute are fully transparent to the way in which g is computed approximated. More precisely, the meth- ods discussed in Section 3 provide sound, statistical bounds on the global robustness estimation, independently on the definition and computation of g(x)..
3.2 COMPUTATION OF GLOBAL ROBUSTNESS R(g) AND D(g)
We detail how global robustness with statistical guarantees can be computed. In Theorems D and 2 proved that statistical guarantees can be computed on standard estimators for R(g) and g)) In fact, given statistical tolerance e >> 0, this can be done by computing the smallest number of samples NV |S| that satisfies Equation 4 (respectively Equation 5 for the computation of (gg)).
Let S {x;; = l...., N) be N test points randomly taken from the test dataset DD we then com- pute the values of g(x;,) (respectively g(r::) using the methods discussed in the previous subsection. We finally use these values to evaluate Equation 3. This provides with an estimator Remy S)
(respectively Demp(g, 5)) that meets the required statistical guarantees by construction.
EXPERIMENTS AND APPLICATIONS
We apply the presented techniques obtain statistically sound estimation of the robustness profile for an array of NN architectures. In Section 4.1 we analyse the convergence rate of the bound on global robustness, using the exact local robustness method of Huang et al. (017).. In Section 4.2 we report empirical tobustness/accuracy trade-off for a variety of different networks trained on MNIST and CIFAR, using FGSM (Goodfellow al.. 2014) for approximate computation of local robustness. Section 4.3 analyses the effects of pruming on the network generalisation and global robustness on MNIST and MNSIS. Results for Bayesian networks are discussed in Section
Ras Conerrgetin
005
0:75
6:55
C(T) C(x)
ff
f(
Figure 1: Convergence of the global robustness estimation wrt error tolerance e (decreasing values along the x-axis). For each e we compute 50 empirical estimates (blue dots). As the error tolerance decreases the estimated quantities converge to a tight cluster. The red line interpolates the number of sampled images needed for the computation of each blue dot.
4.1 CONVERGENCE ANALYSIS OF BOUND
Figure I depicts the convergence rate of our robustness estimation method wrt the error tolerance Namely, we train a CNN on MNIST and estimate its global robustness up to a decreasing value of e.
"Code can be found at: link left blank during peer review.
5

---

Under review as a conference paper at ICLR 2020
For each value of c compute 50 different estimates of global robustness (blue dots in the figure), statistically guaranteed to be e-close to the actual robustness of the network. In order to do so, for every E compute the number of samples required to meet the guarantees (using Equations a and 5) and independently build 50 subset of the test dataset 'D. Hence, for each value of this give rise to 50 different estimation of global robustness. As decreases, the variance of the estimated values decreases as well, quickly converging at around 5% error. The red line in the plot shows the number of samples needed obtain the required guarantees. Notice that, though the number of samples is exponential wrt c, 5% tolerance is already obtained with just above 700 samples taken from the input distribution. This is orders of magnitudes smaller than test datasets used for training deep networks.
4.2 ROBUSTNESS OF DETERMINISTIC NEURAL NETWORKS
In this section, we empirically evaluate the trade-off between global robustness and accuracy for deterministic networks. Recent works have suggested that robustness and accuracy might be at odds, and observed that this was the case when training neural networks Tsippaa et al., 2018). While the trade-off between robustness and accuracy is generally different for each application, we contribute these analyses by quantifying (i.e. with guaranteed statistical error) the robustness/accuracy trade-off in fully connected networks (FCNs) and convolutional neu- ral networks (CNNs) trained on MNIST, Stochastic Gradient Descent (SGD).
selection of datasets
(Xiao et al.) 2017) and CIFAR-10 10 using
Figure depicts the empirical robustness/accuracy trade-off we observe, computed with statistical error 0.05. Overall, the observed trade-off is computed on approximately 3800 different neu- ral network models (each blue dot in the figure represents robustness and accuracy obtained with a particular neural network), namely 1000 fully-connected networks (FCNs) and 1000 convolutional neural networks (CNNs) for MNIST, 500 FCNs and 500 CNNs for Fashion MNIST, and 800 CNNs for CIFAR-10. The different networks were obtained by means of a grid search over the hyperparam- eters space, where we vary depths, widths, activation functions, learning rates and training epochs. In the case of CNNs we also vary the number of convolutional layers, number of filters in each convolutional layer, and the size of the kernel used (additional details about the hyperparameters used and values explored can be found in the Appendix Section BB. For CIFAR-10 10 approximately 200 models are taken from the DEMOGEN model dataset (Jiang et al. 2018). The global properties checked in these analyses are global robustness induced by: checking whether NNs prediction on
Loo 5-ball produces confidence variations above 0.50 (shown in Figures (a) and (c)); computing maximum softmax variation in Lx norm (shown in Figures (b), (d) and (c)); checking for changes in classification (shown in Figure (c)). These are further reported in each figure box. Notice that the 8 used for Fashion- MNIST and CIFAR- 10 is smaller than the one used for MNIST, as every network was found fully non-robust for larger values of ó. We find that for harder problems, the network per- formance is more varied which results in greater noise in the quantification of the trade-off (as seen in Figure 2}.
For each of the datasets analysed and for all tested measures of robustness, we find a negative correlation between accuracy and robustness. This supports the current hypothesis of the robust- ness/accuracy trade off, and demonstrates that optimizing hyperparameters for accuracy might have negative effect on the resulting network robustness. We perform empirical analysis to find the apper-parameter that have a most profound effect on the network robustness. These are shown in the boxplots in Figure 2 which are computed by averaging out the results across all the networks tested. We find that both increasing model capacity (purple boxplots) and increasing training du- ration (green boxplots) tend to have a negative effect on robustness. Interestingly, these suggest a relationship between adversarial vulnerability and overfitting. We remark, however, that, though they align with previous hypothesis and similar empirical results (Tsipras et al., 2018), these results are empirical, and inevitably based on observations from only finitely many networks.
4.3 EFFECT OF ITERATIVE MAGNITUDE PRUNING ON ROBUSTNESS
Iterative Magnitude Pruning (IMP) is a network compression technique which has shown, empir- ically, be effective at reducing the number of weight parameters in neural networks. Empirical analyses demonstrated that IMP can at times remove up to 99% of the weights, while keeping (and even improving on) the original network test accuracy (Frankle & Carbin 2018). As the existence of

---

Under review as a conference paper at ICLR 2020
of OF NEAT
Actuncyss hiburnen 18- 0.5
Semenry Quee 20-1
Dffed Truining on Rebwernas
(a)
b)
f(x))
<
(2) f(2) 0o
of Cagecryce KobUE
Efrect ring Roburases
(c)
(d)
Acoicyy
C(a)
C(a)
(x()
f(2)
Accensy Notarin 38
(e)
0.50
(1x) f(2)
Figure 2: Analysis of empirical accuracy/robustnes. off computed on 4000 deterministic FCNs and CNNs (each blue dot the center plots represents the accuracy/robustness result for each net- work). Each set of plots has been labeled with the functions used to compute robustness. First row: analyses on the MNIST dataset. Second row: analyses on the Fashion-MNIST dataset. Third row: analyses on the CIFAR-10 dataset. We observe negative trend between accuracy and robustness.
a non-trivial interplay between model capacity and adversarial robustness has been suggested in the literature (Goodfellow al. 2014), we here explore the effect of IMP global robustness the same architectures described in Section 4.2 MNIST and Fashion-MNIST. Results for this anal- ysis shown in Figure 3, where
show the effect of IMP when removing 50%, 75%, 90% and 99% of the weights (IMP results reported in green dots and normal training results reported using blue dots in (a) and (b)). We find for IMP similar trade-off to the one observed when pruning not applied, with a slight reduction in accuracy when severe pruning strength is applied (shown in (c)). As the boxplots show, we find that the amount of pruning has no statistically significant effect on any of the global robustness measures investigated here. These observations are inline with the impact of other notions of weight regularization observed in (Goodfellow et al. 2014), further highlighting a relationship between weight pruning and network regularisation.
4.4 ROBUSTNESS OF BAYESIAN NEURAL NETWORKS
In this section we explore the global robustness of networks trained in Bayesian settings, which in principle should not suffer from overfitting-like issues (Gal & Smith 2018). We perform approx- imate Bayesian training on MNIST and Fashion-MNIST using Hamiltonian Monte Carlo (HMC), which is the gold-standard for Bayesian inference (Neal et al.] 2011). Unfortunately, this does not allow us to scale to CIFAR-10. While this could be possible by using other Bayesian approx- imate training techniques, it would add a non-trivial interplay between the results observed and the quality of the approximation. We again explore the model architecture space using the same discussed in Section 4.1 (instead of varying learning rates and epochs, we vary the parameters of the numerical integrator for the Hamiltonian dynamics and the number of samples that we use in order to approximate the posterior distribution). As such, the explored architectures exactly the same those explored for deterministic NNs and the only difference lies hence in the training methods (that is, deterministic vs. Bayesian). Results for this analysis are given Fig- ure 4 with pink dots showing Bayesian results and blue dots the deterministic ones (as in Figure
hyper-parameter
7

---

Under review as a conference paper at ICLR 2020
Accunayy as QuirI Ritratnes
Oountiatt Soth
(8)
Amaway
MakERokkes
f(a) [(a)
< 0.50
ASQUTCCy
(c)
Ascrracy to. Riblsinne 3 a-0 040251
Effect ReGLeSoR FctLSTeES
(b)
Accurscy
(ax) ((z)
Sacured
(f [8)
Figure 3: Quantitative analysis of global adversarial robustness models trained with iterative magnitude pruning. (a): robustness results on MNIST: (b): robustness results on Fashion-MNIST; (c): quantitative robustness on MNIST (top) and Fashion-MNIST (bottom). We observe that prun- ing leads to comparable trade-off wrt when pruning is not applied. The boxplots show lack of correlation between the proportion of weights pruned and global robustness.
Ellect Copeciy oF TcBUSTROSS
1MC
(a)
(b)
681 AI LO AccunCy
2004
1339
200
Can 0.0 KM MA sas 08 1.0
f(z)
f
(f()) f(x)
Figure 4: Global robustness analysis of Bayesian NNs. (a): results on MNIST: (b): results on Fashion-MNIST. Each plot is labeled with the notion of robustness used. In the rightmost plot, SGD was measured with attacks an order magnitude weaker as the models were more vulnerable.
2}. Interestingly, we find that, not only do Bayesian networks not exhibit the negative correlation between robustness and accuracy, they in fact reverse this correlation. This shows that, for the ar- chitectures analysed here, and for MNIST and Fashion-MNIST, robustness and accuracy are not at odds. Actually, the results suggest that selecting a Bayesian network prrer-pprameters to optimise test accuracy leads more globally robust networks as well. We further inspect the effect of model capacity on the global adversarial robustness. Interestingly, we show that there is weak positive correlation between model capacity and robustness for both MNIST and Fashion-MNISTT which again reverses the trend observed for deterministic networks.
CONCLUSION
We considered probabilistic measure of global adversarial robustness of neural networks and gave methods for its estimation with a- a-priori statistical guarantees. The presented techniques were em- ployed to provide statistically sound estimates of the robustness profile of array of neural network architectures on MNIST, CIFAR-10 10 and Fashion-MNIST.. We further investigated how the robust- ness/accuracy trade-off is affected by different training approaches, including Bayesian and iterative pruning methods. The methods discussed here rely only on the continuity of neural network models, and thus generalise to any machine learning model characterised by continuous function, provided that the given notion of local robustness can be computed in practice.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Osbert Bastani, Yani Ioannou, Leonidas Lampropoulos, Dimitrios Vytiniotis, Aditya Nori, and An- tonio Criminisi. Measuring neural net robustness with constraints, In Advances in neural infor- mation processing systems, pp. 2613-2621, 2016.
Battista Biggio and Fabio Roli. Wild patterns: 'en years after the rise of adversarial machine learning. Puttern Recognition, 84:1173311, 2018.
Luca Cardelli, Marta Kwiatkowska, Luca Laurenti, Nicola Paoletti, Andrea Patane, and Matthew Wicker. Statistical guarantees for the robustness of bayesian neural networks. arXiv preprint 1rXiv:1903.01980, 2019a.
Luca Cardelli, Marta Kwiatkowska, Luca Laurenti, and Andrea Patane. Robustness guarantees for bayesian inference with gaussian processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7759-7768, 2019b.
Nicholas Carlini, Guy Katz, Clark Barrett, and David L Dill. Provably minimally-distorted adver- sarial examples. arXiv preprint 17Xiv:1709. 10207, 2017.
Tommaso Dreossi, Shromona Ghosh, Alberto Sangiovanni- Vinnnnii-iieeellli, and Sanjit Seshia. A formalization of robustness for deep neural networks. arXiv preprint wrXi::1903.10033, 2019.
Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Analysis of classifiers robustness adversarial perturbations. Machine Learning, 107(3)481-505, 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprini arXiv: 180300000333335, 2018.
Yarin Gal and Lewis Smith. Sufficient conditions for idealised models have no adversarial examples: theoretical and empirical study with bayesian neural networks. arXiv preprint 1rXiv:1806.00067.. 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy, Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6677. 2014.
Divya Gopinath, Guy Katz, Corina S Päsäreanu, and Clark Barrett. Deepsafe: A data-driven ap- proach for assessing robustness of neural networks. In International Symposium on Automated Technology for Verification and Analysis, pp. 3-19. Springer, 2018.
Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, and James Worrell. On the hardness of robust classification. arXiv preprint 1909:: 2019.
A Hitchhikers Guide. Infinite dimensional analysis. Springer, 2006.
Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu. Safety verification of deep neural networks. International Conference on Computer Aided Verification, pp. 3-29. Springer, 2017.
Yiding Jiang, Dilip Krishnan, Hosscin Mobahi, and Samy Bengio. Predicting the generalization gap in deep networks with margin distributions. arXiv preprint arXiv:1810.00113. 2018
Guy Katz, Clark Barrett, David I. Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pp. 97-117. Springer. 2017.
Pascal Massart. Concentration inequalities and model selection. 2007.
David A McAllester. Some pac-bayesian theorems. Machine Learning, 37(3):355-365 1999.
Rhiannon Michelmore, Matthew Wicker, Luca Laurenti, Luca Cardelli, Yarin Gal, and Marta Kwiatkowska. Uncertainty quantification with statistical guarantees in end-to-end autonomous driving control, 2019.
Radford M Neal et al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(1 1):2, 2011.

---

Under review as a conference paper at ICLR 2020
Wenjie Ruan, Min Wu, Youcheng Sun, Xiaowei Huang, Daniel Kroening, and Marta Kwiatkowska. Global robustness evaluation of deep neural networks with provable guarantees for the hamming distance. International Joint Conference Artificial Intelligence, 2019.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint 1rXXiv:705..777 2017.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint 18Xiv:800..1213: 2018.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Stefan Webb, Tom Rainforth, Yee Whye Tch, and M Pawan Kumar. Statistical verification of neural networks. arXiv preprint
2018
Matthew Wicker, Xiaowei Huang, and Marta Kwiatkowska. Feature-guided black-box safety testing of deep neural networks. In International Conference on Tools and Algorithmss for the Construc- fion and Analysis of Systems, pp. 408-426, Springer, 2018
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint arXiv:1708.07745 2017.
Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, (0(3):391-4233 2012.
Danny Yadron and Dan Tynan. Tesla driver dies in first fatal crash while using autopilot mode. the Guardian, 1, 2016.
A PROOFS
In this Section of the Appendix we provide proofs for the Propositions and Theorems stated in the main paper.
Proof of Theorem By Definition have
Prob( Rm (g. 5) - R(g) > >))=
Prob(1 g(r)
E Bl=x)]] > E)
ZES
Since g(x) is indicator function, and under the assumption that g is measurable, Ez (g)) defines the probability of a random variable taking values in 10. Hence, the difference between
g(z) El>r(g(2) and its empirical frequency E E(wiees [ST be upper bounded by employing additive
Chernoff bounds (Vapnik )2013). yielding Equation
Proof of Theorem 2
Prob( Remp
[g, S) R(g) > E)
Prob Hemp (g, 5) - R(g) V H 5) - R(g) -c)
= =Prob(R* Remp (g. S) R(g) v R(g) Remp S). e)
(By the union bound)
< PProb(Hemmpp S) R(g) E) + Prob(R(g) - pe (g, 8)
Each of these terms can now be bounded by using Hoeffding's 's inequalities /aannik 2013).
Proof of Proposition For I. and j E (1.....n.. define
rz(x)= min (Jz(y) max (()))).
y
(*)
10

---

Under review as a conference paper at ICLR 2020
Note that, by definition of r and of g, it holds that g(z) 1 and C(æ) {5} if and only if (x) > 0. Furthermore, r is measurable by the Measurable Maximum Theorem (Theorem 18.19 in (uude 2006))). It thus follows that the set
Xj = {x E IR
(ry(a) 0}
is measurable, being it a super-level set of a measurable function (hence, the counter-image via a measurable function of a Borel-measurabe set), and so its indicator function 1x, (z). Measura- bility of then follows from the fact that
n
g(x) Σ (x) j=1
Proof of Proposition 2
1 RD x R > a Carathèodory function, Hence, measurability of g follows from the Measur- able Maximum Theorem (Theorem 18.19 in (Guide (2006)))
B EXPERIMENTAL SETTINGS
In this Section of the appendix provide details the training of the NN models that discussed in Section of the main paper.
For all networks, learning rates, for CIFARIO, in order to speed up convergence we use the Adam optimizer. For HMC, approximate the posterior using built-in functions provided by Tensorflow and Edward.
standard stochatic gradient descent with the noted those for CIFARIO,
For lottery ticket, we implemented general iterative magnitude pruning method which works with models written in Keras. Source code for this method is supplied in the project repository.
Below, we list the hyperparameter grid searchs that was performed in order to generate the plots found in the paper.
B.1 MNIST- SGD FCNS
Parameter
Values
Depth
1, 64, 128, 256, 512
Width
Activation Function
ReLu, Tanh, Sigmoid 0.05, 0.01, 0.005, 0.001 5, 10, 15, 20, 25
Learning Rates
Epochs
B.2 MNIST SGD CNNS
Parameter
Values
FC Depth
1, 2
FC Width
128, 256
Activation Function
ReLu
Convolutional Filters
10, 20, 30
Convolutional Kernel Size
3. 5, 7
Convolutional Depth
1, 0.05, 0.01, 0.005, 0.001
Learning Rates
Epochs
3, 6, 9, 12, 15
11

---

Under review as a conference paper at ICLR 2020
B.3
FASHION MNIST SGD FCNS
Parameter
Values
Depth
2, 3, 256, 512, 1024
Width
Activation Function
ReLu, Tanh, Sigmoid
Learning Rates
0,01, 0.005, 0.001
Epochs
5, 10, 15, 20, 25
B.4 FASHION MNIST SSD CNNS
Parameter
Values
FC Depth
1, 2
FC Width
128, 256
Activation Function
ReLu
Convolutional Filters
5, 20, 30
Convolutional Kernel Size
3, 3,5,7
Convolutional Depth
1, 2, 4
Learning Rates
0.0001, 0.001, 0.005
Epochs
3, 6, 9, 12, 15
B.5 CIFAR-10 SGD CNNS
Please refer to the Google DEMOGEN paper in order to extract their parameters for the network- in-network models. Below, where list convolutional depth we reporting the number of VGG- style blocks (two consecutive convolutional layers followed by a max pooling layer).
Parameter
Values
FC Depth
1, 2,
FC Width
128, 256, 512
Activation Function
ReLu
Convolutional Filters
24, 48, 64
Convolutional Kernel Size
3,
Convolutional Depth
1, 0.0001, 0.0005, 0.001, 0.005
Learning Rates
Epochs
3, 6, 9, 12, 15
B.6 MNIST IMP FCNS
Parameter
Values
Depth
1, 2, 3 128, 256, 512, 1024 ReLu, Tanh, Sigmoid 0.5, 0.75, 0.9, 0.99 1, 5 0.001
Width
Activation Function
Prop. Weight Reduction
Iterations of Pruning
Learning Rates
Epochs
10, 15
12

---

Under review as a conference paper at ICLR 2020
B.7
FASHION MNIST IMP FCNS
Parameter
Values
Depth
1, 2, 3,
Width
256, 5T2 ReLu, Tanh, Sigmoid 0.5, 0.75, 0.9, 0.99
Activation Function
Prop. Weight Reduction
Iterations of Pruning
1, 5
Learning Rates
0.001
Epochs
10, 15
B.8 MNIST HMC FCNS
Parameter
Values
Depth
1, 128, 256, 512
Width
Activation Function
ReLu, Tanh, Sigmoid
Step Size
0.01, 0.005, 0.001, 0.0001 10, 15, 20 100, 200, 400, 600
Number of Steps
Samples from Posterior
B.9 FASHION MNIST - HMC FCNS
Parameter
Values
Depth
1, 3
Width
128, 256, 512
Activation Function
ReLu
Step Size
0.01, 0.005, 0.001, 0.0001
Number of Steps
10, 15, 20 100, 200, 400, 600
Samples from Posterior
13


Reviews:
[{"review_id": "rJxOXFAoFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper seeks to analyze the global robustness of neural networks, a concept defined in the paper. The authors show using concentration inequalities that the empirical local robustness approximates the global robustness. The authors investigate various other issues in the robustness literature, including the robustness/accuracy tradeoff, whether iterative pruning increases robustness, and the robustness of Bayesian networks.\n\nI would vote for rejecting this paper for two key reasons. First, the notion of global robustness is not well-motivated (why do we want to compute this metric? What does it tell us that local robustness does not?). Second, the paper tries to do too many different things, and as a result does not give enough attention to any particular topic.\n\nFirst, I believe it is up to the authors to motivate their study of global robustness further. While I acknowledge that a few prior works exists along these lines, I do not feel that this work provides much new insight into why global robustness is interesting to examine.\n\nThe authors go on to prove results showing that an empirical estimator of the local robustness will converge to the global robustness. The bounds require that the dataset size scales with eps^-2, where eps is the error. This is not terrible but also not great; for example, achieving 1% error requires a dataset size of 10^4 (realistically, even larger datasets would be required to achieve results with high probability).\n\nNext, I would suggest that the authors avoid using the word “guarantees” if they are estimating empirical local robustness in an approximate (rather than exact) manner. Guarantees implies strict results, but the authors use a weak attack (FGSM) to approximate empirical local robustness. The results from FGSM could be far from optimal; the authors could use a stronger attack (e.g. PGD) in addition to changing the wording, or they could find provable guarantees using alternate methods.\n\nLastly, the authors try to tackle 3 extra questions beyond global robustness toward the end of the paper, and the last two questions are not properly fleshed out.\n\nI like section 4.2, where the authors empirically show that networks that have better hyperparameters (for regular accuracy) tend to be less robust. This is a confirmation of a previously studied phenomena in the literature. Ideally, I would also appreciate it if the authors found the line of best fit to the dataset in addition to the plots provided. I would like a clarification on whether any of these networks were trained to be robust, although it appears that they were all trained normally. I would also like to see plot 2c (for the standard case of robustness of C(x_tilde) = C(x)), except for MNIST and CIFAR10 as well. I feel that the last-layer representation metric the authors analyze (f(x) is close to f(x_tilde)) could be misleading, as robustness on the last layer does not necessarily imply standard adversarial robustness.\n\nSection 4.3 explores iterative pruning, but that seems fairly unrelated to the rest of the paper. Finally, Section 4.4 tries to show the opposite trend for Bayesian Neural Networks, but unfortunately the results for such networks do not yet scale beyond MNIST.\n\nAdditional Feedback:\n\n- Why did you use R^emp and D^emp as opposed to just R^emp(g) and R^emp(g_bar)?\n- In Figure 1, what is the dataset size |S|?\n- In the last sentence of Section 4.3, I didn’t understand what you meant about the relationship between weight pruning and network regularization. Do you mean that weight regularization has no effect on robustness, just like iterative weight pruning?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SkxcESapFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper formally defines local and global adversarial robustness. Following that, the paper investigates how to estimate local and global adversarial robustness using an estimator based on evaluating these quantities on the empirical distribution. Using a Chernoff bound, the papers evaluate probabilistic bounds on the deviation of the estimated quantities from the true quantities.  Finally, simulations are provided to evaluate these bounds for examples.\n\nComments:\n\nThe authors' insistence on their contribution being proving measurability does not make sense -- of course everything is measurable! Furthermore, the formal definitions or local and global robustness are well-known, the bounds in Theorems 1 and 2 are not novel and highly unlikely to be tight. The redeeming aspect of the paper is the experiments, where the authors show that these bounds can actually be (approximately) calculated. However, I feel that merely experimental results with correct but not significant theoretical contributions does not meet the bar for acceptance. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Skl1SoDAFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the adversarial robustness of neural networks by giving theoretical guarantees, providing statistical estimators and running experiments. It is a lot of work and it is reasonably written. The problem is that a fair bit of it is quite basic: for example the measurability property is very much expected -- noone was doubting it, and the proof is more of a formality than a contribution. Similarly with the statistical sampling: the method seems to rely on i.i.d. sampling -- has this reviewer missed any important details? If not, then it's only the bounds that are a contribution, but the method is not. We would appreciate more specific description of the main contribution, without it we cannot recommend the acceptance of this paper.\n\nI am very grateful to the authors for their response. I feel now that a main weakness of this paper may be that it puts too many results in one place. I would strongly suggest re-writing it, possibly into separate papers, to make the things pointed out in the response more clear and self-standing.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a framework for estimating "global robustness" of a neural network, defined as the expected value of "local robustness" (robustness to small perturbations) over the data distribution. The authors prove the the local robustness metric is measurable and that under this condition, derive a statistically efficient estimator. The authors use gradient based attacks to approximate local robustness in practice and report extensive experimental results across several datasets.

While the paper does make some interesting contributions, the reviewers were concerned about the following issues:
1) The measurability result, while technically important, is not surprising and does not add much insight algorithmically or statistically into the problem at hand. Outside of this, the paper does not make any significant technical contributions.
2) The paper is poorly organized and does not clearly articulate the main contributions and significance of these relative to prior work.
3) The fact that the local robustness metric is approximated via gradient based attacks makes the final results void of any guarantees, since there are no guarantees that gradient based attacks compute the worst case adversarial perturbation. This calls into question the main contribution claim of the paper on computing global robustness guarantees.

While some of the technical aspects of the reveiwers' concerns were clarified during the discussion phase, this was not sufficient to address the fundamental issues raised above.

Hence, I recommend rejection.
Decision: Reject