Robustness between the worst and average case
Authors: Leslie Rice
Anna Bair
Huan Zhang
J Zico Kolter
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial robustness
data augmentation
Hamiltonian Monte Carlo
path sampling

Abstract: Several recent works in machine learning have focused on evaluating the test-time robustness of a classifier: how well the classifier performs not just on the target domain it was trained upon, but upon perturbed examples.  In these settings, the focus has largely been on two extremes of robustness: the robustness to perturbations drawn _at random_ from within some distribution (i.e., robustness to random perturbations), and the robustness to the _worst case_ perturbation in some set (i.e., adversarial robustness).  In this paper, we argue that a sliding scale between these two extremes provides a valuable additional metric by which to gauge robustness. Specifically, we illustrate that each of these two extremes is naturally characterized by a (functional) q-norm over perturbation space, with q=1 corresponding to robustness to random perturbations and q=\infty corresponding to adversarial perturbations.  We then present the main technical contribution of our paper: a method for efficiently estimating the value of these norms by interpreting them as the partition function of a particular distribution, then using path sampling with MCMC methods to estimate this partition function (either traditional Metropolis-Hastings for non-differentiable perturbations, or Hamiltonian Monte Carlo for differentiable perturbations).  We show that our approach provides substantially better estimates than simple random sampling of the actual “intermediate-q” robustness of both standard, data-augmented, and adversarially-trained classifiers, illustrating a clear tradeoff between classifiers that optimize different metrics. Code for reproducing experiments can be found at https://github.com/locuslab/intermediate_robustness.

Robustness between the worst and average case
Leslie Rice
Anna Bair
Department of Computer Science Careegie Mellon University Pittsburgh, laricelcs. cmu. edu
Department Machine Learning Carnegie Mellon University Pittsburgh, PA abair@cmu, edu
Huan Zhang
J. Zico Kolter
Department of Computer Science
Department of Computer Science Carnegie Mellon University & Bosch Center for Artificial Intelligence Pittsburg,, PA zkolterâcs. cmu. edu
Carnegie Mellon University Pittsburgh, PA huanthuan-zhang com
Abstract
Several recent works in machine learning have focused on evaluating the test-time robustness classifier: how well the classifier performs not just on the target do- main it was trained upon, but upon perturbed examples. In these settings, the focus has largely been on two extremes robustness: the robustness to perturbations drawn random from within some distribution (i.e., robustness random perturba- tions), and the robustness to the worst case perturbation in some set (i.e., adversarial robustness). In this paper, argue that sliding scale between these two extremes provides a valuable additional metric by which to gauge robustness. Specifically, illustrate that each of these extremes is naturally characterized by (fune- tional) q-norm over perturbation space, with = corresponding to robustness to corresponding adversarial perturbations. We
random perturbations and 9 then present the main technical contribution of our paper: method for efficiently estimating the value of these norms by interpreting them the partition function of a particular distribution, then using path sampling with MCMC methods to estimate this partition function (either traditional Hattopolls-Hastinge for non non-differentiable perturbations, or Hamiltonian Monte Carlo for differentiable perturbations). We show that our approach provides substantially better estimates than simple random sampling of the actual "intermediate-g" robustness of standard, data- augmented, classifiers, illustrating a clear tradeoff between classifiers that optimize different metrics. Code for reproducing experiments can be found at rtbusssteeseeess.s..
and adversarially-trann
https: tig...........
Introduction
There has been an increasing focus in recent years in evaluating the robustness of machine learning classifiers, broadly interpreted as evaluating their performance not just on test set, but also evaluating bounds
the performance relative to some additional (possibly domain domain-specific) uncertainty the problems. Although there are many formal definitions of robustness, most work in this area has focused particular settings. In the "classical" sense of robustness, the classifier terms its worst-case loss under some perturbation set applied to the inputs, i.e., we
consider evaluating
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

could evaluate (via finite sample approximation)
E B max E(h(x + 5). 6EA(Z)
(I)
where DD denotes a distribution over z; y pairs, h denotes the hypothesis function, denotes a loss, and (xx) denotes some (input-dependent) uncertainty region. This formulation, for instance, underlies adversarial examples and also motivates the classical adversarial training approaches. However, substantial work has also been done in evaluating the setting of robustness to random perturbations, i.., evaluating a classifier via the loss
EnyDD (Es-P())((((( + +6), yi]]
where now P(z) denotes some (again, input-dependent) distribution over possible perturbations. This formulation underlies common data augmentation strategies in deep learning, as well as most formulations of "natural" robustness [Hendrycks and Dietterich 2018 (even if not always written in this formal manner).
Until now, these two types of robustness have typically been seen largely separate notions. We believe there is inherent value in generalizing these two notions to place them in a unified framework. The main criticism of worst-case robustness is that it focuses "too much" the worst case, while the criticism of average-case is that it is "not robust enough". It seems very likely that what people actually want in terms of robustness is precisely something in the middle, between these two extremes.
In this paper, we advocate for a more fine-grained spectrum of robustness definitions, which naturally interpolates between both these two extremes. In particular, we argue that robustness to random perturbations and worst-case robustness can be naturally interpreted as (functional) f, norms [l of the loss function evaluated over the perturbation distribution (which can be uniform distribution in the case of traditional adversarial loss). In particular, the random setting corresponds to the choice of q 1 and the adversarial setting corresponds to the choice of q co. We believe that it is also valuable and informative to consider the performance of classifiers in a wide range in between these two extremes, i.e., the performance of "intermediate-q" robustness. However, evaluating this intermediate-g robustness is non-trivial, owing to the fact that it requires computing a high dimensional integral over the perturbation space. Thus, main technical contribution of this paper is the proposal of a simple approach to evaluating the relevant robustness norms, using a combination of path sampling and Markov chain Monte Carlo (MCMC) approaches (specifically the Hamiltonian Monte Carlo method for cases where loss is a differentiable function of the perturbation space). Despite their seeming complexity, in this particular case the eventual estimators take the very simple form of geometric mcan computed over samples from an annealed distribution over the perturbation region.
We evaluate our approach on networks trained via standard training, data augmentation, and adversar- ial training. In all the cases our proposed approach shows clear trade-off between different levels of robustness that would missed by solely considering just the random or adversarial perturbation setting. Furthermore, we show that our HMC-based path sampling estimator for intermediate-q robustness vastly superior to naive estimates produced e.g. by Monte Carlo sampling. We also briefly highlight the possibility of actually training networks using these estimators create classifiers more robust to these intermediate notions of robustness. Code for reproducing experiments can be found at wttppp/.ww......aaaaaaeaaeeeeeee
2 Background and related work
Robustness in deep learning Adversarial robustness is the "classicial" view of robustness that traces its roots back to robust optimization, a field in optimization theory that allows for the study of worst-case uncertainty [Ben-Tal et al. 2009 Szegedy et al.) 2013 noted the marked presence of adversarial examples in deep classifiers, which the addition of imperceptible amounts of noise leads
to gross misclassification of input images by deep networks. Goodfellow et al. (2014) then introduced
the Fast Gradient Sign Method (FGSM), which uses a single gradient step to generate adversarial
We should emphasize that this use of E, norms is entirely orthogonal to the use of é, balls as perturbation regions, commonly done in adversarial robustness. The l,, norms here can be applied to any perturbation region. will highlight.

---

examples and was used to perturb training examples as the original form of adversarial training. Subsequently, the Basic Iterative Method was introduced by Kurakin et al. [2016], and rendered
FGSM adversarial training ineffective through attacks using multiple, smaller FGSM steps (although
the robustness of FGSM adversarial training was later improved (Wong et al. 2020 Andriushchenko
and Flammarion 2020)). The work of Madry et al. 2017] further improved upon this iterative attack, and incorporated the resulting Projected Gradient Descent (PGD) adversary into adversarial training. Today, PGD remains the most empirically effective adversary for adversarial training and attacks. While traditional adversarial training focuses on perturbations within some by-norm ball, it has also been expanded to more realistic threat models, from spatial transformations [Engstrom et al. 2019 Xiao et al. 2018 to weather corruptions and lighting changes [Wong and Kolter 2020
However, when considering robustness to more "realistic" (yet synthetic) perturbations, the focus is often shifted from robustness to the worst-case perturbation within some set to robustness to random perturbations [Geirhos et al., 2018 Hendryyks and Dietterich, 2018, [Hendrycks et al.) 2019h Yin et al., 2019]. was been further studied whether such synthetic corruptions can universalyy l improve robustness to real-world distribution shifts, such geographic location, or camera hardware [Hendrycks et al., 2020]. Other naturally occurring distribution shifts of interest include consistency shifts (Shankar et a 2019] and dataset shifts [Storkeyy] 2009 Taori et al., 2020). For example, the impact of dataset shift has been emphasized on the ImageNet dataset, where the performance of models trained on ImageNet was shown to be drastically worse on reproduction of the validation set [Recht et al. [019]. While some work such as Meunier et al. (2021] could be interpreted as an interpolation between random and adversarial noise, generally the field faces divide between studies on adversarial robustness and robustness to random data perturbations.
MCMC methods for partition function estimation Because our definition of intermediate-g robustness involves computation of high dimensional integral over a perturbation distribution, our work can also be related to methods for estimating an intractable partition function of a probability distribution. The problem of computing normalizing constants ties to the problem of computing differences in free energy in physics. Several Monte Carlo sampling-based
approaches exist for approximately estimating normalizing constants. Importance sampling is one approach at estimating ratios of normalizing constants that relies samples from one of the distributions. Bridge sampling [Bennett, [176,] Meng and Wong 1996]. on the other hand, uses a single "bridge" distribution to interpolate between the two distributions and reduce the Monte Carlo errors associated with importance sampling. Annealed importance sampling [Jrzynski 1997 Neal 2001] bridges the gap between the two distributions by chaining together intermediate distributions, and linked importance
sampling [Neal] 2005) then combined bridge sampling with annealed importance sampling to bridge these intermediate distributions. Path sampling [Gelman and Meng 1998), which originated under the name of thermodynamic integration in physics [Ogata] 1989] aims at reducing Monte Carlo errors by introducing flexible paths.
Our proposed approach also leverages Hamiltonian Monte Carlo methods to improve the sample efficiency of our eventual estimator [Duane et al. 1987 Betancourt] Neal Neal et al. [21T]. Hamil-
tonian Monte Carlo (HMC) is useful due to its avoidance of random walks, and is compatible with sampling in constrained space through use of reflection [Afshar et al. 2015).
3 A simple generalization of robustness
To begin, we first make the simple observation that there is natural interpolation between the notions of adversarial robustness and robustness to random perturbations. Specifically, we note that both these notions can be expressed as function by norms over the perturbation space. Specifically, we define the following functional norm
Definition 1. For a continuous function f R - R and density p T TR+, ((x)dr 1, let [|ll be the q-norm of the function under this density
(fFla)Putovae" 1/0
[Ill = EEeo [1
(3)
Then as the proposition shows, random perturbation loss and adversarial perturbation loss simply correspond to two extremes of this functional norm over the perturbation 6, as formalized by the following proposition.
3

---

Proposition 1. Let 6 be a random variable with density μt and consider the expectation
Eg [1((h(z + 6), 8),
(4)
Then (for smooth loss {) this corresponds the expected loss random samples from μ when q = 1, and to the expected adversarial loss over the domain of μ when q = oc.
This proposition follows immediately from the fact that losses are non-negative, and the fact that the 2. norm is given by the pointwise maximum of the function, assuming a smooth loss & (i.e. not zero-one loss). Note that "traditional" adversarial loss actually arises more specifically when q - 00 and μ a uniform distribution over some norm ball (unrelated to the norm q). When we have < q < oo, we enable a full spectrum of robustness measurements, which we refer to as intermediate-g robustness, that evaluates the performance of classifiers in wide range in between these two extreme cases. Furthermore, we argue that there are naturally appealing properties of these intermediate-q robustness measures: whereas adversarial robustness may overestimate the risk of what effectively amount to "measure zero" regions of the perturbation space, random robustness may likewise fail to take into account smaller but non-negli regions that do contain areas of high loss.
As an example, when considering 6 as a Gaussian distribution, adversarial loss (q = 00) is not mean- ingful because the worst case perturbation can be arbitrarily far away from x. Meanwhile, random data augmentation with Gaussian noise (q = 1) is often insufficient for evaluating robustness because random Gaussian samples are rarely good adversarial examples. Our intermediate-g robustness allows us to consider a middle ground where the model is robust under a certain degree of adversarial noise (stronger than randomly sampled Gaussian noise) while the evaluation is not hindered by very rare events (c.g., an extremely low probability Gaussian sample far away from 2).
4 Estimating intermediate-q robustness via MCMC methods
Of course, simply writing the loss in this manner is not particularly useful on its own. In most cases, the integral in Equation 3 cannot be computed exactly, and so we must resort to numerical approximation methods. Specifically, in order to estimate the q- q-norm robustness for arbitrary nonlinear model h, loss l, and (known) density (u, we consider the problem of computing the integral
(J e(h(x + 5), m(())d
(1/4)
Z =
(5)
One could naively estimate this integral by using Monte Carlo sampling, and sample 5(1) ,..., ((m) randomly from density μe, and approximate the objective as the following,
Momtte Carlo = = Σ
E(h(x + +50 )00)) (1/g)
1=1
However, because the integral in 5 will be dominated by values with large {(h(x + 8), y). simply using Monte Carlo sampling will be insufficient approximate this integral well for larger values of 4. as random sampling will place too much weight on regions of low loss.
Instead, in this work we argue that it is beneficial to interpret the task at hand one of evaluating the partition function of a particular unnormalized probability density. Specifically, we define an (unnormalized) density over the perturbation ó
p = ((h(z + 6), v)))(()))))
Then clearly, just from construction, we see that the task of evaluating the (1 root of) partition function (the normalizing constant) of this distribution is exactly the same as that of computing the integral of interest.
The advantage of this perspective on the integral of interest, however, is that we can use a wealth of techniques developed for partition function estimation in order to better estimate this particular integral. Specifically, we argue to use the path sampling [Gelman and Meng 1998] approach, a Markov chain Monte Carlo based method, to approximate the desired partition function. In fact, we show that for the precise form of the integral question, the eventual estimator produced by this method takes on a very simple form: it consists of a geometric mean over samples generated from certain annealed distribution. This makes the estimator particularly simple to implement and even in some cases to train networks based upon, via standard automatic differentiation toolkits.

---

4.1 Evaluating the particular function of the loss-based distribution
We state our main result on the path sampling formulation of the integral of interest via the following theorem.
Theorem 1. Consider the task of approximately computing the following integral:
(1/9)
z: ((th(2+)))
Let ((()),()) ... {lm) be m. scalars corresponding to linearly interpolated values from O to q. For
i = 1,.... m, sample 5(0) from the following unnormalized density
8 p(o)((0), where, p(ö)t) & E(h(x 8), y) u(6).
Then the following estimator, given by the geometric mean of the resulting samples
Zpatt = (II ((h(z [I(h((=+(()) +(()). 1/mm
(8)
i=1
is consistent estimator of our integral Z. Practically, the m samples can be drawn using MCMC.
Proof. For notational completeness, we define the density
p(8)() =(1) =(1) ((01))
(9)
where
((8(() E(h(x ()))))(())
(10)
and where z()) denotes the partition function of this distribution
(1)) ((81))85
(11)
Taking the log of both sides of and differentiating with respect to t, we get:
dt log( (t)) = dt log p(o)t)d8
J 4 ((11))
J ((8(t)dd
/ p(0)t) d 4((l))
(12)
d6
z(t)
p(0lt)
Ea-p(81t)
log ((1)))
dt
Es-((811)
log (((h(( + 6), 8))
where we use the fact that
log p(8(t) Log (((h(x + 8))
(13)
Then we can integrate
12 from 0 to to get
[2(g) 12(0)
1/'' Es-p(si)) log(e(h(z 5), 8)) dt
log
(14)
Given in our case =0) = and incorporating the exponent (1 (1/g), we have
(10) 1 Es-p(ai)) log(E(h(x + 6), w/1 dt
log
(15)
Then the right hand side of Equation 15 can be interpreted as the expectation log(E(h(z: + 8), over the joint distribution of (6, (). where / is a random variable with a uniform distribution in [0,
log
100)
Ec-U10,9 Es log(E(h(> + o).
(16)
5

---

Algorithm Evaluating the intermediate-q robustness of neural network function h using path sampling estimation with m MCMC samples with z, y D for some norm q.
Initialize 8(0) randomly for i = 1. 172 do
Let (()) ;= q m 1-1
Sample 8(()) ~ p(8)(()) using MCMC from initial state 6
end for
[II.T E(h(x + (.(0) v)) 1/m
return
Finally, sampling (810, ((1) for i I,, ....., mn from this joint distribution p(6, 1) (which we can do by linearly interpolating (10 between and of and then sampling 566) from (()), we have the fact that
m VIA
((h((( (((()+8(1))))) 1/m
2path :- exp
(og(((((=+0))).))))
II
(17)
is a consistent estimator of the desired integral.
The key point of this result is that allows us approximate the desired integral just through the ability to sample from the distribution p(o]t). While this is still challenging task, sampling from unnormalized probability distributions is well-studied problem, and we can apply MCMC sampling methods to this task. Further, while the sampling of (8(+) (19) can be done in different ways, we choose linearly anneal ((0) from 0 q. and then draw g(t) p(oltt using some MCMC sampler. This has the nice feature that it starts with sampling from an "easy" distribution (when / = 0, the distribution over ó is simply given by μ), and gradually anneals more peaked distribution as increases. The resulting algorithm for evaluating a network using this geometric mean estimator is shown in Algorithm !
4.2 Sampling from the (unnormalized) loss distribution via HMC
In order to generate the samples for the path sampling estimation (7) from the desired distribution p(6, t), we use Markov chain Monte Carlo (MCMC) methods to sample ó from the unnormalized distribution p(ō't) t). When the loss is a differentiable function of the perturbation distribution, we can take advantage of gradient-based methods to reduce random walk behavior in MCMC sampling and achieve more efficient sampling. Hamiltonian Monte Carlo (HMC) is one such gradient- based MCMC method that simulates Hamiltonian dynamics to improve sample efficiency in high-dimensional spaces. HMC is based on the Hamiltonian function H (q, p) = (() + K (p). where is a d-dimensional position vector, p is d-dimensional momentum vector, (q)) is the potential energy, and K Kp) is the kinetic energy. To translate this to our setting, U6) = log(E(x + 6), y) (()) is just the negative log probability density of the distribution we want to sample from, and K ((p) = ||pll2/(2a3)
the
negative log probability density of the zero-mean Gaussian distribution with variance a². Then the Hamiltonian function H is equal the following:
|Pp|2 o²
H - loo((E(h + 0), + log ((0) +
(18)
In order to make use of Hamiltonian dynamics in practice, Hamiltonian's 's equations must be dis- cretized. The Leapfrog method is one such discretization of Hamiltonian dynamics, using small stepsize a to discretize time and numerically integrating the system of differential equations as follows:
= p ot logg(((((( ()) 6),u))2
= 5 + ap/o²
(19)
p = p + at (og(e(((xx+++ 0), n))/2
The leapfrog method reversible by simply negating p (although this need not be done in practice, since K(p) K(-p)). The HMC algorithm begins by first sampling a momentum vector

---

NO, o²), independent of the current state of 6. Then, the Leapfrog method in 19 is repeated for steps to propose new Markov state (6', p²). This proposed state is then accepted with probability min[1, (1, (P(-))) where AH = H - H)), If the state (6', p/) is not accepted, the next state then set to p).
Given that in general, our perturbation distribution will likely be constrained in some manner, we need modify the HMC algorithm so that our proposals remain within the boundaries of the perturbation distribution. Consider the case where our perturbation distribution is the loo norm ball with radius e, so that each element of 8 is constrained be within -c and c. In order to enforce these constraints while preserving the dynamics, we incorporate what is known as reflection in HMC. In this case, after setting ò = 6 + cp/o². we check if any 8 > or 6 < for corresponding momentum term, Pi, and if 62 > E, we set 6; = 2c - 8/. whereas if 8f < -c, we set 8 = -2 8. We repeat this reflection step until 8, satisfies our constraints. One can think of this behavior as effectively simulating reflecting off a physical boundary.
1, ..... n. If so, we negate the
We note that we can still easily use the path sampling estimator for non-differentiable perturbations by replacing the Hamilton Monte Carlo sampler with any other non-gradient based MCMC sampler, such as a random walk Metropolis. This is roughly similar random sampling, but with a more subtle weighting on terms that involve higher loss.
4.3 Estimating the partition function during training
We further consider the possibility of training networks using the estimators we have discussed to achieve better intermediate robustness. However, this becomes less computationally feasible due to the number of samples required to get a good estimate of the objective, due to the m x L iterations of the path sampling estimator with Hamiltonian Monte Carlo, where I. the number of Leapfrog steps. Additionally, the step size a and variance o² in HMC require careful tuning. However, for larger values of q. the path sampling estimator essential to getting accurate estimates of the training objective, random sampling will be much less likely to come across regions of the perturbation distribution with high loss. Path sampling draws samples from the unnormalized loss distribution using MCMC, and so with increased g. there will be higher weighting on samples that induce higher loss. The Hamiltonian Monte Carlo method has the additional benefit of following the gradient (along with some noise). and for larger q, even with small number of iterations, path sampling have advantages over Monte Carlo sampling during training.
5 Experimental evaluation
In this section, we evaluate the intermediate-g robustness of models trained using standard training, data augmentation, and adversarial training. comparing estimates of the functional q-norm of the loss function over the perturbation distribution computed via naive, Monte Carlo sampling (6) and path sampling 8 with Hamiltonian Monte Carlo (for differentiable perturbations) and random walk Metropolis Hastings (for non- con-differentiable perturbations). We additionally show preliminary results of training according to the intermediate-g robustness objective approximated by these estimators. All of our experiments are either run on the MNIST dataset [LeCun et al.) 1998 the CIFAR-10 10 dataset [Krizhevsky et al. 2009]. We consider robustness over two types of perturbations, namely the fo norm bounded input perturbation and spatial transformations. Additional results can be found in Appendix A. and A.2 and experimental details can be found in Appendix A.3
5.1 Robustness over the -norm ball
In order to easily translate the notion of intermediate-q robustness to that of adversarial robustness, we consider perturbations uniformly distributed within an f- ball with radius e. Our evaluations of intermediate-q robustness on MNIST and CIFAR-10 in Table [ both show that estimates of the functional q-norm of the loss function evaluated over this perturbation distribution naturally interpolate between loss over random samples (MC q 1) and adversarial loss (PGD). For larger values of g, specifically y = 102 and q = 10a, the path sampling with HMC (PS+HMC) estimator consistently produces more accurate (i.e. higher) estimates of the desired integral than the Monte Carlo (MC) estimator. We show that this result holds for all of the models we evaluated, each of which were trained according to a different training objective, and across both datasets. The ad advantage of
7

---

Table 1: Evaluations comparing the Monte Carlo estimates (2mc) and path sampling with HMC estimates (ZPs-HMc) of the functional g-norm of the loss over the loo ball with radius e = 0.3 on MNIST and e = 0.03 on CIFAR-10. As increases, HPS computes better estimates interpolating between random and adversarial robustness. On MNIST, ZMc is computed with m = 2000, ZPS+HMC with m = 100, L 20, and Adv. loss corresponds to PGD with 100 iterations. On CIFAR-10, 10, ZMC is computed with 50 iterations at 10 restarts.
500, ZPs+HM with = 50, L 10, and Adv. loss corresponds to PGD with
Dataset Train method
2MC
ZPstHMC q
Adv. loss
q 1
g
10
9
10
9
10
9
9
10 9 = 10
MNIST
Standard
0.043
0.140
0.251
0.268
0.043
0.160
1.420
4.456
11.649
MNIST
MC q 1 PGD-50
0.032
0.084
0.143
0.154
0.032
0.088
0.692
2.133
7.363
MNIST
0.039
0.051
0.076
0.081
0.039
0.048
0.101
0.187
0.270
CIFAR-10
Standard
0.453
0.787
1.153
1.216
0.453
0.841
2.718
4.991
18.142
CIFAR-I0
MC q 1
0.405
0.532
0.717
0.756
0.405
0.546
1.490
3.140
14.240
CIFAR-10
10
0.733
0.734
0.743
0.761
0.733
0.734
0.743
0.796
1.411
Table 2:
Evaluation of models trained according to estimates of the functional g-norm of the loss over the foo ball with radius = 0.3 on MNIST. As we increase q during evaluation, models trained using the path sampling estimator with HMC tend have lower intermediate-g robust loss than models trained using the Monte Carlo estimator for the same Note that as we have shown in Table [ 2Mc is not reliable for large ZPS+HM should be used for comparisons. ZMC is computed with 2000, ZPs-HMC with 100, L 20, and Adv. loss corresponds to PGD with 100 iterations.
Train method
2MC
7eS+HIC
Adv. loss
=
q = 10
= 102
9 == 10
g Q=1
g = 10
9 = 10
q= 10
MC 10
0.026
0.058
0.098
0.105
0.026
0.058
0.412
1.336
3.722
MC ? = 10a
0.025
0.055
0.093
0.099
0.025
0.055
0.388
1.261
3.492
MC = 10
0.025
0.055
0.093
0.100
0.025
0.055
0.390
1.268
3.488
PS+HMC & 10
0.031
0.075
0.126
0.135
0.031
0.075
0.467
1.307
5.012
PS+IIMC q = 10a
0.028
0.060
0.099
0.107
0.028
0.058
0.304
0.816
2.613
PS+IMM = 10a
0.024
0.047
0.077
0.083
0.024
0.045
0.239
0.684
1.646
the PS+HMC estimator over the MC estimator is further illustrated in Figure I where we show the convergence of their corresponding estimates of the functional g-norm of the loss over this same perturbation distribution given increasing number of samples. Specifically, we compare the estimates of the intermediate-g robust loss computed by each estimator given the same number of iterations (which corresponds to for the MC estimator, and x L for the PS+HMC estimator). While for q = 1 the estimates converge to the same value given a similar number of iterations, for q = 100, the estimates quickly diverge, with path sampling producing a much higher (i.e. better) estimate.
In addition to evaluating intermediate-g robustness using both estimators, we additionally show the potential benefits of training using these estimators in Table On MNIST, we compare the results of training using the MC objective vs. the PS+HMC objective. We note that when q = 1, the MC estimate corresponds to just applying random perturbations per example and taking the average loss, similar to data augmentation methods. For the MC estimate computed during training, we use vn 50 samples, whereas for the PS+HMC estimate we use m 25 samples with L, = 2 leapfrog steps in order to compare an equivalent number of iterations. We find that most models trained according to the PS+HMC objective outperform those trained using the MC objective for the same value of q, i.c. have a lower intermediate-g robust loss. This suggests that even with a reasonably small number of samples, path sampling can still result in a better estimate of the objective.
We additionally attempt training on CIFAR- 10 using these estimators, however the computational complexity given the number of samples required to get a reasonable estimate makes training more challenging for larger datasets. Despite this, we see promise for training deep networks to robustness levels somewhere between robustness over random perturbations and robustness over worst-case perturbations. Full tables of results for MNIST and CIFAR-10 can be found in Tables 4 and respectively in Appendix A.I
8

---

Path sampling HMC
Monte Carlo
Path sampling HMC
Monte Carlo
3.0
0.4
2,5
Estimate
0.3
Estimate
2.0
0.2
0.1
0.5
0.0
0.0
1000
2000
3000
4000
5000
0
1000
2000
3000
4000
5000
Iterations
Iterations
(a)
(b)
Figure Comparison of the convergence of HMC-based path sampling and naive Monte Carlo estimates for (a) 1, and (b) q = 100 with increasing iterations on standard trained model on CIFAR-10 10 using a single batch. Iterations corresponds m for the Monte Carlo estimator, and to x L for the path sampling + HMC estimator using L 10 leapfrog steps. For smaller q = 1 (a). random sampling works reasonably well, whereas for = 100 (b), using path sampling with HMC is essential to get good estimates.
5.2 Robustness over (non-difffrrentiabl) spatial transformations
In order to show that the path sampling estimator can naturally be extended to non-differentiable perturbations, we consider a perturbation set consisting of parameterizations of spatial transformations on 10.. The parameters of the spatial transformations include horizontal flips, rotations between 10 to 10 degrees, scaling factors between 0.9 to 1.1, and cropping between to 4 pixels horizontally and vertically. Because the applied spatial perturbations are non- conn-ifferentiable in place of Hamiltonian Monte Carlo we use Gaussian random walk Metropolis Hastings sample from the unnormalized loss distribution. Specifically, We use the following proposal distributions: 1) perform a horizontal flip with probability 0.5; 2) scale the image by resizing by factor of N' 0.5): 3) rotate d degrees with d ~ (0, 5): 4) crop x y in the horizontal or vertical direction, each drawn ii.d. ~ N (0, 2) and then rounded to the nearest integer value. Additionally, at each value of the annealed we perform 20 burn-in steps and only keep the last value for estimation purposes.
We compare the estimates of the functional g-norm of the loss over this perturbation distribution generated by the Monte Carlo estimator and by the path sampling estimator using Gaussian random- walk Metropolis sampling on standard trained model and data augmentation (MC q = 1) trained model. The results in Table 3 that with larger q, the path sampling estimator produces better (higher) estimates than random sampling. For q = 10 the path sampling estimation approaches the adversarial loss over the transformation space, suggesting that this estimator, even without the advantage of Hamiltonian Monte Carlo, can effectively capture the entire spectrum of robustness. Estimates EMC and Eps were computed with m = 500. Due to the computational complexity, we only evaluate on the first 1000 CIFAR- 10 test examples. The adversarial loss was approximated by averaging the maximum loss value encountered for each example during the Metropolis Hastings sampling process. Results were averaged over three repeated runs with different random seeds.
6 Conclusion
In this paper, we proposed definition of intermediate-g robustness that smooths the gap between robustness random perturbations and adversarial robustness by generalizing these notions of robustness as functional fg norms of the loss function over the perturbation distribution. In order to evaluate intermediate-q robustness in practice, we introduced an approach for approximating the high dimensional integral over the perturbation distribution that uses path sampling, an effective estimator based on MCMC sampling. We showed that across different datasets, models trained on different training objectives, and different perturbation distributions (both differentiable and non- con-differenttiale

---

Table 3: Evaluations comparing the Monte Carlo estimates (2mc) and path sampling estimates (2ps) of the functional q-norm of the loss over non-differentiable spatial transformations on CIFAR-10. The intermediate-q losses naturally interpolate between loss over random perturbations, and worst-case loss over the space of spatial perturbations. Despite the necessity of using Gaussian random walk Metropolis Hastings in place of gradient-bassee based Hamiltonian Monte Carlo. the path sampling estimator still results in higher estimates of the desired integral than the Monte Carlo estimator for larger values of q.
Train method
ZMc
Zps
Adv. loss
q
0
10
9 = 10a
10
9
10
9 =
102
q= 10
Standard
0.450
2.268
3.687
3.865
0.444
2.450
4.636
4.889
5.625
MC 1
0.191
0.800
1.246
1.300
0.186
0.879
1.615
1.711
2.021
cases), our path sampling approach produces much better estimates the integral than simple Monte Carlo sampling. Additionally, illustrated the benefit of using the gradient-basee Hamiltonian Monte Carlo method as the MCMC sampler when the loss is differentiable with respect to the perturbatioon distribution. Lastly, we highlighted the possibility of training using these estimators, and showed that models trained on MNIST using these estimators do exhibit improved intermediate-g robustness, with path sampling again outperforming random sampling. However, the best way of estimating the integral during training of deep networks remains an open question, due to the computational complexity of accumulating enough MCMC samples at each epoch to get reasonable estimation.
Leslie Rice, Anna Bair and Huan Zhang are supported by a grant from the Bosch Center for Artificial Intelligence.
Acknowledgements
References
Hadi Mohasel Afshar, Justin Domke, et al. Reflection, refraction, and hamiltonian monte carlo. In NIPS, pages 3007-3015, 2015.
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training, arXiv preprint arXiv:2007.02617 2020.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton University Press, 2009.
Charles H Bennett. Efficient estimation of free energy differences from monte carlo data. Journal of Computational Physics, 22(2):245-268, 1976.
Michael Betancourt. A conceptual introduction to hamiltonian monte carlo. arXiv preprint
arXiv:1701.024533 2017.
Simon Duane, Anthony D Kennedy, Brian J Pendleton, and Duncan Roweth. Hybrid monte carlo. Physics letters B, 195(2):216-22,, 1987.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. Exploring the landscape of spatial robustness. In International Conference on Machine Learning, pages 1802-18111 1. PMLR, 2019.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A Wichmann, and Wieland Brendel. Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness. arXiv preprint arXiv: 18/ 1. 12231, 2018.
Andrew Gelman and Xiao-Li Meng. Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statistical science, pages 163-185, 1998.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv: 2014.
10

---

Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2018.
Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song. Using self-supervised learning can improve model robustness and uncertainty. arXiv preprint arXiv: 12340, 2019a.
Dan Hendrycks, Norman Mu, Ekin D Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshmi- narayanan. Augmix: A simple data processing method to improve robustness and uncertainty. 2019b.
arXiv preprint
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al. The many faces of robustness: A critical analysis of out-of-distribttion generalization. arXiv preprint arXiv:2006.16241, 2020.
Christopher Jarzynski. Nonequilibrium equality for free energy differences. Physical Review Letters, 78(14):2690, 1997.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alexey Kurakin, Ian Goodfellow, Samy Bengio, et al. Adversarial examples in the physical world, 2016.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. tradient-basee learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-322) 1998.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 170.006083 2017.
Xiao-Li Meng and Wing Hung Wong. Simulating ratios of normalizing constants via a simple identity: a theoretical exploration. Staristica Sinica, pages 831-860, 1996.
Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, and Yann Chevaleyre. Mixed nash equilibria in the adversarial examples game. arXiv preprint arXiv:2102.06600) 2021.
Radford M Neal. Annealed importance sampling. Statistics and computing, 1(2):125-133) 2001.
Radford M Neal. Estimating ratios of normalizing constants using linked importance sampling. arXiv preprint math/051 2005.
Radford M Neal al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(11):2, 2011.
Yosihiko Ogata. A monte carlo method for high dimensional integration. Numerische Mathematik, 55(2):137-157, 1989.
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning, pages 5389-5400. PMLR, 2019.
Vaishaal Shankar, Achal Dave, Rebecca Roelofs, Deva Ramanan, Benjamin Recht, and Ludwig Schmidt. Do image classifiers generalize across time? arXiv preprint 1rX.v:1906.0211 2019.
Amos J Storkey. When training and test sets different: characterising learning transfer. In In Dataset Shifi in Machine Learning, pages 3-28. MIT Press, 2009.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts in image classification. Advances in Neural Information Processing Systems, 33, 2020.
Eric Wong and J Zico Kolter. Learning perturbation sets for robust machine learning. arXiv preprint 000,0000000 2020.

---

Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint 0rX14:2001.3399, 2020.
Chaowei Xiao, Jun-Yan Zhu, Bo Li, Warren He, Mingyan Liu, and Dawn Song. Spatially transformed adversarial examples. arXiv preprini 1oXXvv8801.02611 2018.
Dong Yin, Raphael Gontijo Lopes, Jonathon Shlens, Ekin D Cubuk, and Justin Gilmer. A fourier perspective on model robustness in computer vision. arXiv preprint arXiv: 1906609908, 2019.
12


Reviews:
[{"review_id": "PSftnqVTRa_", "reviewer": "Reviewer_K1Rk", "summary": "This paper proposes to tackle robustness both to adversarial noise and to random noise. The authors motivates the use of the Lp norm of the loss for a given noise distribution as an interpolant between robustness to adversarial attacks and random noise. The approach is well sounded.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is easy to read to follow. I enjoyed the HMC sampling part that I did not know before. The experiments are nice and justifies the efficiency of the HMC sampling.\n\n\nRemarks:\n- The recovered loss as $p\\to\\infty$ is not exactly the adversarial loss. The authors must be careful because it tends towards the essential supremum for the measure $\\mu$ and not the maximum on the support of $\\mu$. I can discuss with the authors if they are not familiar with it.\n- The paper lacks a bit of rigor. \"For $f$ a function\" for instance is not well defined. Which space do they consider in the whole paper? Which problem they consider? What assumptions on the loss? etc. I really suggest the authors to work again on that point\n- The algorithm proposed by the authors to compute the integral seems dereasonably complicated at first sight in comparison with the naive sampling: $\\delta_1,\\cdot \\delta_n$ from $\\mu$ and return $\\left(\\frac1n\\sum l(h(x+\\delta_i),y)^p\\right)^{1/p}$. Although it is justified experimentally, If the estimator proposed by the authors has a smaller variance, the authors should prove it. The authors should also plot the time of computation, because one gradient computation is very costful.\n\nOther interpolations/related work:\n\nIn the paper [1], the authors proposed an entropic regularization of the adversarial problem. One can remark this regularization can be interpreted as an interpolation between a random noise and adversarial noise too.\n\n\nRating:\n\nFor now, I rate the paper as weak reject. I really suggest the authors to work on the rigor of their paper. Please define all the objects, etc. It can only make a better paper. Moreover, I suggest the authors to give a provable justification for the use of the HMC method.\n\n\n[1]Mixed Nash Equilibria in the Adversarial Examples Game. Laurent Meunier, Meyer Scetbon, Rafael Pinot, Jamal Atif, Yann Chevaleyre. ICML2021", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Understanding adversarial problems is a important topic, since it is a threat for ML systems in productions. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "DKn4rHdfgbm", "reviewer": "Reviewer_Ausy", "summary": "This paper proposes a definition of adversarial robustness that generalization current definitions of robustness, i.e. the loss incurred by a hypothesis when the input is contaminated by samples drawn from a perturbation set. The definition is based on a an Lp functional over the perturbation space, and interestingly it comprises the uniformly at random and adversarial cases when p=1 and p=\\inty, respectively. Subsequently, in order to approximate this quantity, the authors propose a MCMC sampling approach of the partition function of an alternative density. The authors demonstrate the proposed definition numerically for MNIST and CIFAR datasets, showing that their approach performs better than a naive MC sampling. Additionally, they show that if models are trained by minimizing this new notion of p-robustness, even while approximate, they result in better robustness across this spectrum.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is very well written and interesting. Their definition is valuable and insightful, as it generalizes current notions of robustness and reconciles two ideas that are often treated differently: adversarial perturbations and random perturbations from some distribution (as in distribution shifts). The proposed estimator is intuitive, and the numerical results confirm their effectiveness. \n\nMy only major comment regards their reflection approach to their HMC sampling process to remain within the perturbation constraint set, which they authors explain for the case of L_\\infty perturbations. Can the authors clarify if this is also applicable to general Lp balls? More generally, must this constraint set be convex for this to work? This question is motivated by the case of more general perturbations, such as those in color, contrasts, etc.\n\nMinor comments:\n- d\\delta missing in Eq 11\n- d\\theta missing in Eq 14 and 15\n- It was not immediately clear to me what the first column (\"Method\") in Table 1 and 2 referred to. Maybe the authors can clarify in the text, or table caption, that this refers to the way the models are trained.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "AS5FmPwONxv", "reviewer": "Reviewer_J5Fx", "summary": "The paper presents a unified characterization of classifier robustness, which covers both the worst-case adversarial robustness and robustness to random perturbations. The authors mainly focus on the problem of estimating the “intermediate-p robustness” for general p. By leveraging the techniques for partition function estimation, they propose a MCMC method for estimating the intermediate-p robustness. Theoretical justifications of the consistency of the proposed estimator are provided, and empirical evaluations on MNIST and CIFAR-10 are given.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The unified view of classifier robustness is new and interesting to me. However, I have a hard time understanding when the intermediate-p robustness (1<p<+infinity) is useful, which is the focus of the paper. Although the paper presents a very brief argument in lines 126-129 regarding this, without specific examples or further evidence, I cannot see the significance of the considered problem. This is my major concern of the paper. If the authors can convince me the user cases of intermediate-p robustness, I would be willing to raise my score. \n\nOther minor comments are listed below:\n1.\tHow to interpret the results of Table 1 and Table 2? What loss function is used?\n\n2.\tHow many MCMC samples are needed for producing a good estimate? In other words, what is the sample efficiency of the proposed estimator? It would be nice if the authors can show the convergence curves.\n\n3.\tFor worst-case adversarial robustness, a more common evaluation metric is robust accuracy (choose 0-1 loss as the loss function in Equation 1). It would be better to provide the robust accuracy for each classifier considered.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations of their work, but do not discuss the societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new notion of robustness that interpolates between random perturbations and adversarial perturbations. The authors also present a MCMC based approach to evaluate the proposed robustness notion. All the reviewers agreed that this is an interesting and insightful notion of robustness and the results presented are above the bar for NeurIPS. There were concerns raised about the significance of the proposed definition, but the author response in this direction has been satisfactory. The authors should take into account the reviewers' comments before preparing the final version.
Decision: Accept (Poster)