Title: GLOBAL ADVERSARIAL ROBUSTNESS GUARANTEES FOR 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 , for any > 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.

1. INTRODUCTION:

Adversarial attacks are potentially imperceptible input manipulations that when applied to a test point result in misclassification. Since even state-of-the-art deep learning models have been shown susceptible to such attacks (Goodfellow et al., 2014) , adversarial examples have raised serious concerns about the security and robustness of models learned from data (Biggio & Roli, 2018) . As standard accuracy measures fail to capture model behaviour in an adversarial setting, the development 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 et al., 2019) . However, while techniques for the computation of local adversarial robustness guarantees (i.e., specific to a particular test point) have been developed for a variety of machine learning models (Katz et al., 2017; Biggio & Roli, 2018; Cardelli et al., 2019b) , to the best of our knowledge relatively few studies of global robustness (Bastani et al., 2016; Ruan et 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 x, 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 of concentration inequalities (Massart, 2007) . Crucially, this allows us 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 a range of commonly used notions of adversarial examples and NN architectures, and show how global robustness can be reformulated as a sum of independent and identically distributed random variables. Hence, bounds such as additive Chernoff or Hoeffding'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 multiple datasets, including MNIST, Fashion-MNIST and CIFAR. In particular, we analyse the effects 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 evaluate 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 settings. More specifically, for the datasets analysed, we observe that optimising a 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 a 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 derived to evaluate the local adversarial robustness of neural networks (Goodfellow et al., 2014; Wicker et al., 2018; Tramèr et al., 2017; Katz et al., 2017; Cardelli et al., 2019a; Carlini et al., 2017) . In addition to local robustness, which focuses on a specific test point, global measures of robustness have also been discussed in the literature (Bastani et al., 2016; Ruan et al., 2019; Webb et al., 2018) . Intuitively, 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 a global measure of robustness for the network that describes the probability wrt the input distribution that a certain local property is satisfied (Dreossi et 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 a priori specified tolerance > 0.

Formal bounds on global adversarial robustness are given by (Fawzi et al., 2018) . However, implementation 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 robustness is discussed by Katz et al. (2017) ; Gopinath et al. (2018) , where a network is considered globally adversarially robust if there are no input points that are vulnerable to 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 input distribution). Instead, the global robustness measure considered here is probabilistic, in that it computes the probability that a 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 capabilities of a 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).

2. GLOBAL ADVERSARIAL ROBUSTNESS OF NEURAL NETWORKS:

In this section we discuss two notions of global robustness for neural networks. Namely, we 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 : R m → R n , with any activation function and arbitrarily many layers, such that, for a test point x ∈ R m , f (x) = (f 1 (x), ..., f n (x)) represents the vector of the confidence values for each of the n class labels. D = {(x, y)|x ∈ R m , y ∈ {1, ..., n}} is a test dataset comprising |D| input points, which we assume to be iid sampled from a distribution P .

A Measure of Global Robustness. Given a test point x sampled from P , we consider the indicator function g : R m → {0, 1}, which returns 1 if f is locally robust in x, and is defined as follows.

Definition 1. (Local Robustness) Given x ∈ R m and δ > 0, let T x = {x ∈ R m | |x -x| p ≤ δ},

where | • | p is an L p norm, be a δ-ball around x. Call C(x) = arg max i∈{1,...,n} f i (x) the set of classes for which the confidence of f in x is maximised. Then we say that f is locally robust in x around T x iff g(x) = 1, where:

g(x) = 1 if C(x) is a singleton and ∀x ∈ T x C(x) = C(x) 0 otherwise.

That is, f is locally robust in x if small perturbations in the input do not cause a classification change.

Note that we require the predicted class of x to be unambiguous, i.e. C(x) comprises only one class, and otherwise we view the point as not locally robust (as the classification decision output is not 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(x) are given in Section 3.1.

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:

EQUATION

where p is the density probability associated to P.

It is important to emphasise that R(g) is 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 g is an indicator function, under the assumption that g is measurable (discussed in detail in Section 3), it follows that R(g) is a well defined probability measure.

A Quantitative Measure of Global Robustness. As discussed in the previous section, we define local robustness g as an indicator function. It is often useful to consider a quantitative notion for the robustness of f . For example, given a δ-ball around a test point x, we may want to know not just if f is locally robust in x, but also the maximal variation in the classification confidence values of the various classes, which evaluate the network's robustness independently of the decision procedure used for the classification. Further, one could require the model confidence to be robust up to a specific output threshold (Katz et al., 2017) . Specifically, given f and a test point x ∈ R m , we consider a function ḡ(x) that quantifies the robustness of f in x and is defined as follows.

Definition 3. (Quantitative Local Robustness) Given x ∈ R m and δ > 0, let T x = {x ∈ R m | |x - x| p ≤ δ}, where | • | p is an L p norm, be a δ-ball around x.

We define the quantitative local robustness of f in x around T x as:

ḡ(x) = max x∈T x h(f (x), f (x))

, where h : R n × R n → R is a given function that measure differences between f predictions.

In Section 4 we provide experimental results using h defined as the L ∞ norm between predictions, as well as by checking whether this norm is greater than a given threshold γ > 0 (which is akin to the definition introduced by Katz et al. (2017) ). Similarly to R(g), the following definition generalises quantitative local robustness to a global property, by taking the expectation of ḡ(x) with respect to the input data distribution. Definition 4. (Quantitative Global Robustness) The quantitative robustness of f is defined as:

EQUATION

)

where p is the density probability associated to P.

Exact computation of R(g) and D(ḡ) is infeasible as 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 to estimate these quantities with a priori arbitrarily stringent guarantees.

3. STATISTICAL GUARANTEES ON ADVERSARIAL ROBUSTNESS:

In this section we derive estimations of R(g) and D(ḡ) with arbitrarily stringent a priori statistical guarantees. In particular, in Equation 3 we consider empirical estimators of these quantities and then in Theorem 1 and 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 g and ḡ are computed or approximated in practice, and finally describe the global robustness guarantees computation pipeline in Section 3.2. Proofs for the Propositions and Theorems state in this Section are reported in the Appendix Section A.

We consider the following empirical estimators:

R emp (g, S) = (x,y)∈S g(x) |S| D emp (ḡ, S) = (x,y)∈S ḡ(x) |S| (3)

where S is a 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 R emp (g, S), we first have to show that g is a measurable function1 . In fact, the measurability of g guarantees that R(g) is a well defined probability measure induced by P , the data distribution. Hence, concentration inequalities can be applied to bound the error between R(g) and R emp (g, S). Proposition 1. Assume that, for i ∈ {1, ..., n}, f i , the i-th component of the neural network f is a continuous function, then g(x), as defined in Definition 1, is measurable.

Proof of Proposition is based on noticing that the set {x ∈ R m | g(x) > 0} can be rewritten as the union of pre-images of measurable sets for a measurable function. Note that the overwhelming majority of the neural networks commonly used in practice are continuous. Hence, the assumption in Proposition 1 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 R emp (g, S) is greater than , for any > 0.

Theorem 1. Assume that g is measurable, then for any > 0 it holds that that for any (possibly unknown) input data distribution

EQUATION

)

Theorem 1 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 Section 4.1, the required number of samples for a given error tolerance , although exponential in , is generally under control in practice. The proof of Theorem 1 relies on reformulating Equation 1 as a 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 between D(ḡ) and D emp (ḡ, S). Again, we first show that under mild assumptions ḡ(x) is measurable.

Then, we use this result to bound the error by using concentration inequalities. Proposition 2. Consider ḡ, as defined in Definition 3. Then, under the assumption that l(x 1 , x 2 ) = h(f (x 1 ), f (x 2 )) is continuous in both x 1 and x 2 , we have that ḡ measurable.

In the following theorem we show that a result similar to that of Theorem 1 can be obtained also for the more general case of quantitative global robustness. Theorem 2. Assume that ḡ is measurable and that, for any input point x, ḡ(x)

∈ [A, B] ⊂ R n .

Then, for any (possibly unknown) input data distribution P , it holds that

EQUATION

)

Note that in practice it is often the case that the output of a neural network is bounded (notably for classification problems and regression problems over a bounded input space). The proof of Theorem 2 relies on the application of union bound and Hoeffding inequality (Vapnik, 2013) , and the resulting upper bound is again problem and architecture independent.

3.1 COMPUTATION OF LOCAL ROBUSTNESS g(x) AND ḡ(x)

The computation of global robustness depends on the ability to compute local robustness g(x) (or analogously ḡ(x)) for every input point x, that is, to establish the presence or absence of an adversarial attack in a neighbourhood of x. For deep neural networks this is known to be NP-complete (Katz et al., 2017) . For exact computation of g(x) 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 4.1. Unfortunately, the computational complexity for the exact computation of g(x) quickly gets prohibitive for large networks. As in (Bastani et al., 2016) , in these cases we proceed by approximating local robustness. The trade-off between scalability and approximation quality of an 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 or approximated. More precisely, the methods 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(ḡ):

We detail how global robustness with statistical guarantees can be computed. In Theorems 1 and 2 we proved that statistical guarantees can be computed on standard estimators for R(g) and D(ḡ).

In fact, given a statistical tolerance > 0, this can be done by computing the smallest number of samples N = |S| that satisfies Equation 4 (respectively Equation 5for the computation of D(ḡ)).

Let S = {x i , i = 1, . . . , N } be N test points randomly taken from the test dataset D, we then compute the values of g(x i ) (respectively ḡ(x i )) using the methods discussed in the previous subsection. We finally use these values to evaluate Equation 3. This provides us with an estimator R emp (g, S)

(respectively D emp (ḡ, S)) that meets the required statistical guarantees by construction.

4. EXPERIMENTS AND APPLICATIONS:

We apply the presented techniques to 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. (2017) . In Section 4.2 we report empirical robustness/accuracy trade-off for a variety of different networks trained on MNIST and CIFAR, using FGSM (Goodfellow et al., 2014) for approximate computation of local robustness. Section 4.3 analyses the effects of pruning on the network generalisation and global robustness on MNIST and Fashion-MNIST. Results for Bayesian networks are discussed in Section 4.42 .

Figure 1 : Convergence of the global robustness estimation wrt error tolerance (decreasing values along the x-axis). For each 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 1 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 .

For each value of we compute 50 different estimates of global robustness (blue dots in the figure), statistically guaranteed to be -close to the actual robustness of the network. In order to do so, for every we compute the number of samples required to meet the guarantees (using Equations 4 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 to obtain the required guarantees. Notice that, though the number of samples is exponential wrt , 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 on a selection of datasets (Tsipras et al., 2018) . While the trade-off between robustness and accuracy is generally different for each application, we contribute to these analyses by quantifying (i.e. with guaranteed statistical error) the robustness/accuracy trade-off in fully connected networks (FCNs) and convolutional neural networks (CNNs) trained on MNIST, Fashion-MNIST (Xiao et al., 2017) and CIFAR-10 using Stochastic Gradient Descent (SGD).

Figure 2 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 neural 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 hyperparameters 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 B). For CIFAR-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 L ∞ δ-ball produces confidence variations above 0.50 (shown in Figures . These are further reported in each figure box. Notice that the δ 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 performance 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 robustness/accuracy trade off, and demonstrates that optimizing hyperparameters for accuracy might have a negative effect on the resulting network robustness. We perform empirical analysis to find the hyper-parameters 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 duration (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, empirically, to 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 analyses on the CIFAR-10 dataset. We observe a negative trend between accuracy and robustness.

a non-trivial interplay between model capacity and adversarial robustness has been suggested in the literature (Goodfellow et al., 2014) , we here explore the effect of IMP on global robustness on the same architectures described in Section 4.2 for MNIST and Fashion-MNIST. Results for this analysis are shown in Figure 3 , where we 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 a similar trade-off to the one observed when pruning is 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 approximate 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 approximate 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 hyper-parameters 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 are exactly the same as 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 was measured with attacks an order of 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 architectures analysed here, and for MNIST and Fashion-MNIST, robustness and accuracy are not at odds. Actually, the results suggest that selecting a Bayesian network hyper-parameters to optimise test accuracy leads to 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 a weak positive correlation between model capacity and robustness for both MNIST and Fashion-MNIST, which again reverses the trend observed for deterministic networks.

5. CONCLUSION:

We considered a probabilistic measure of global adversarial robustness of neural networks and gave methods for its estimation with a-priori statistical guarantees. The presented techniques were employed to provide statistically sound estimates of the robustness profile of an array of neural network architectures on MNIST, CIFAR-10 and Fashion-MNIST. We further investigated how the robustness/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 a continuous function, provided that the given notion of local robustness can be computed in practice.

A PROOFS:

In this Section of the Appendix we provide proofs for the Propositions and Theorems stated in the main paper.

Proof of Theorem 1 By Definition we have

P rob(|R emp (g, S) -R(g)| > ) = P rob(| x∈S g(x) |S| -E x∼P [g(x)]| > )

Since g(x) is an indicator function, and under the assumption that g is measurable, E x∼P [g(x)] defines the probability of a random variable taking values in {0, 1}. Hence, the difference between E x∼P [g(x)] and its empirical frequency (x,y)∈S

g(x):

|S| can be upper bounded by employing additive Chernoff bounds (Vapnik (2013) ), yielding Equation 4.

Proof of Theorem 2 P rob(|R emp (g, S) -R(g)| > ) =P rob(R emp (g, S) -R(g) > ∨ R emp (g, S) -R(g) < -) =P rob(R emp (g, S) -R(g) > ∨ R(g) -R emp (g, S) > )

(By the union bound) ≤P rob(R emp (g, S) -R(g) > ) + P rob(R(g) -R emp (g, S) > ) Each of these terms can now be bounded by using Hoeffding's inequalities (Vapnik, 2013) .

Proof of Proposition 1 For x ∈ R m and j ∈ {1, ..., n}, define r j (x) = min y∈T x f j (y) -max 

:

In this paper by measurable we mean Borel measurable.

Code can be found at: link left blank during peer review.

Figures and Tables:

Figure2depicts 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 neural 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 hyperparameters 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 B). For CIFAR-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 L ∞ δ-ball produces confidence variations above 0.50 (shown inFigures (a)  and (c)); computing maximum softmax variation in L ∞ norm (shown in Figures (b), (d) and (e)); checking for changes in classification (shown in Figure (c)). These are further reported in each figure box. Notice that the δ 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 performance is more varied which results in greater noise in the quantification of the trade-off (as seen in Figure2).

Figure 2: Analysis of empirical accuracy/robustness trade-off computed on 4000 deterministic FCNs and CNNs (each blue dot in the center plots represents the accuracy/robustness result for each network). 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 a negative trend between accuracy and robustness.

Figure 4, with pink dots showing Bayesian results and blue dots the deterministic ones (as in Figure

Figure 3: Quantitative analysis of global adversarial robustness on 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 pruning leads to comparable trade-off wrt when pruning is not applied. The boxplots show a lack of correlation between the proportion of weights pruned and global robustness.

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 of magnitude weaker as the models were more vulnerable.

Please refer to the Google DEMOGEN paper in order to extract their parameters for the networkin-network models. Below, where we list convolutional depth we are reporting the number of VGGstyle blocks (two consecutive convolutional layers followed by a max pooling layer).

Table content: <table><tr><td colspan="2">B.3 FASHION MNIST -SGD -FCNS B.7 FASHION MNIST -IMP -FCNS</td><td/></tr><tr><td/><td>Parameter Parameter</td><td/><td>Values Values</td></tr><tr><td/><td>Depth Depth</td><td/><td>2, 3, 4 1, 2, 3, 4</td></tr><tr><td/><td>Width Width</td><td/><td>256, 512, 1024 256, 512</td></tr><tr><td colspan="4">Activation Function ReLu, Tanh, Sigmoid Activation Function ReLu, Tanh, Sigmoid</td></tr><tr><td colspan="2">Learning Rates Prop. Weight Reduction</td><td/><td>0.01, 0.005, 0.001 0.5, 0.75, 0.9, 0.99</td></tr><tr><td colspan="2">Epochs Iterations of Pruning</td><td/><td>5, 10, 15, 20, 25 1, 2, 5</td></tr><tr><td colspan="2">Learning Rates</td><td/><td>0.001</td></tr><tr><td colspan="2">B.4 FASHION MNIST -SGD -CNNS Epochs</td><td/><td>5, 10, 15</td></tr><tr><td>B.8 MNIST -HMC -FCNS</td><td>Parameter</td><td/><td>Values</td></tr><tr><td/><td>FC Depth</td><td/><td>1, 2</td></tr><tr><td colspan="2">FC Width Parameter</td><td/><td>128, 256 Values</td></tr><tr><td colspan="2">Activation Function Depth</td><td/><td>ReLu 1, 2, 3</td></tr><tr><td colspan="2">Convolutional Filters Width</td><td/><td>5, 20, 30 128, 256, 512</td></tr><tr><td colspan="3">Convolutional Kernel Size Activation Function</td><td>3, 5, 7 ReLu, Tanh, Sigmoid</td></tr><tr><td colspan="2">Convolutional Depth Step Size</td><td colspan="2">1, 2, 3, 4 0.01, 0.005, 0.001, 0.0001</td></tr><tr><td colspan="2">Learning Rates Number of Steps</td><td/><td>0.0001, 0.001, 0.005 10, 15, 20</td></tr><tr><td colspan="2">Epochs Samples from Posterior</td><td/><td>3, 6, 9, 12, 15 100, 200, 400, 600</td></tr><tr><td colspan="2">B.5 CIFAR-10 -SGD -CNNS B.9 FASHION MNIST -HMC -FCNS</td><td/></tr><tr><td colspan="2">Parameter</td><td/><td>Values</td></tr><tr><td/><td>Depth</td><td/><td>1, 2, 3</td></tr><tr><td/><td>Width</td><td/><td>128, 256, 512</td></tr><tr><td colspan="2">Parameter Activation Function Step Size</td><td colspan="2">ReLu Values 0.01, 0.005, 0.001, 0.0001</td></tr><tr><td colspan="2">FC Depth Number of Steps</td><td/><td>1, 2, 3 10, 15, 20</td></tr><tr><td colspan="2">FC Width Samples from Posterior</td><td/><td>128, 256, 512 100, 200, 400, 600</td></tr><tr><td colspan="2">Activation Function</td><td/><td>ReLu</td></tr><tr><td colspan="2">Convolutional Filters</td><td/><td>24, 48, 64</td></tr><tr><td colspan="2">Convolutional Kernel Size</td><td/><td>3, 5, 7</td></tr><tr><td colspan="2">Convolutional Depth</td><td/><td>1, 2, 3</td></tr><tr><td colspan="2">Learning Rates</td><td colspan="2">0.0001, 0.0005, 0.001, 0.005</td></tr><tr><td colspan="2">Epochs</td><td/><td>3, 6, 9, 12, 15</td></tr><tr><td>B.6 MNIST -IMP -FCNS</td><td/><td/></tr><tr><td/><td>Parameter</td><td/><td>Values</td></tr><tr><td/><td>Depth</td><td/><td>1, 2, 3</td></tr><tr><td/><td>Width</td><td/><td>128, 256, 512, 1024</td></tr><tr><td colspan="2">Activation Function</td><td/><td>ReLu, Tanh, Sigmoid</td></tr><tr><td colspan="2">Prop. Weight Reduction</td><td/><td>0.5, 0.75, 0.9, 0.99</td></tr><tr><td colspan="2">Iterations of Pruning</td><td/><td>1, 2, 5</td></tr><tr><td colspan="2">Learning Rates</td><td/><td>0.001</td></tr><tr><td/><td>Epochs</td><td/><td>5, 10, 15</td></tr></table>

Peer review (iclr2020):
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. I 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. First, 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. The 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). Next, 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. Lastly, 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. I 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. Section 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. Additional Feedback: - Why did you use R^emp and D^emp as opposed to just R^emp(g) and R^emp(g_bar)? - In Figure 1, what is the dataset size |S|? - 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?