Wasserstein distributional robustness of neural networks
Authors: Xingjian Bai
Guangyi He
Yifan Jiang
Jan Obloj
Venue: NeurIPS 2023 poster (2023)
Keywords: adversarial attack
adversarial robustness of DNN
adversarial training
Wasserstein distance
distributionally robust optimization
sensitivity analysis
asymptotic bounds

Abstract: Deep neural networks are known to be vulnerable to adversarial attacks (AA). For an image recognition task, this means that a small perturbation of the original can result in the image being misclassified. Design of such attacks as well as methods of adversarial training against them are subject of intense research. We re-cast the problem using techniques of Wasserstein distributionally robust optimization (DRO) and obtain novel contributions leveraging recent insights from DRO sensitivity analysis. We consider a set of distributional threat models. Unlike the traditional pointwise attacks, which assume a uniform bound on perturbation of each input data point, distributional threat models allow attackers to perturb inputs in a non-uniform way. We link these more general attacks with questions of out-of-sample performance and Knightian uncertainty. To evaluate the distributional robustness of neural networks, we propose a first-order AA algorithm and its multistep version. Our attack algorithms include Fast Gradient Sign Method (FGSM) and Projected Gradient Descent (PGD) as special cases. Furthermore, we provide a new asymptotic estimate of the adversarial accuracy against distributional threat models. The bound is fast to compute and first-order accurate, offering new insights even for the pointwise AA. It also naturally yields out-of-sample performance guarantees. We conduct numerical experiments on CIFAR-10, CIFAR-100, ImageNet datasets using DNNs on RobustBench to illustrate our theoretical results. Our code is available at https://github.com/JanObloj/W-DRO-Adversarial-Methods.

Wasserstein distributional robustness of neural networks
Xingjian Bai
Guangyi He Mathematical Institute University of Oxford, UK
Department of Computer Science University of Oxford, UK xingj ian. bai@sjo ox. ac. uk
com
Yifan Jiang
Jan Obtój* Mathematical Institute University of Oxford, UK j an. joloj@matha ox ac. uk
Mathematical Institute University of Oxford, UK yifan. angomaths. ox ac. uk
Abstract
Deep neural networks are known to be vulnerable to adversarial attacks (AA). For an image recognition task, this means that small perturbation of the original can result in the image being misclassified. Design of such attacks as well as methods adversarial training against them are subject of intense research. We re-cast the problem using techniques of Wasserstein distributionally robust optimization (DRO) and obtain novel contributions leveraging recent insights from DRO sensitiv- ity analysis. We consider a set of distributional threat models. Unlike the traditional pointwise attacks, which assume uniform bound on perturbation of each input data point, distributional threat models allow attackers to perturb inputs in non- uniform way. We link these more general attacks with questions out-of-sample performance and Knightian uncertainty. To evaluate the distributional robustness of neural networks, we propose a first-order AA algorithm and its multistep version. Our attack algorithms include Fast Gradient Sign Method (FGSM) and Projected Gradient Descent (PGD) as special cases. Furthermore, we provide a new asymp- totic estimate of the adversarial accuracy against distributional threat models. The bound is fast to compute and first-order accurate, offering new insights even for the pointwise AA. It also naturally yields out-of-sample performance guarantees. We conduct numerical experiments on CIFAR- 10, CIFAR-100 ImageNet datasets us- ing DNNs on RobustBench to illustrate our theoretical results. Our code is available at https:// / / thub. com/ JanObloj WR-DWWWD----- Adversarias ialllllllll Methods.
Introduction
Model uncertainty is ubiquitous phenomenon across different fields of science. In decision theory and economics, is often referred to as the Knightian uncertainty (Knight, 1921), or the unknown unknowns, distinguish it from the risk which stems from the randomness embedded by design in the scientific process, see Hansen and Marinacci (2016) for an overview. Transcribing to the context of data science, risk refers to the randomness embedded random initialization, drop-outs etc., and uncertainty encompasses the extent to which the dataset an adequate description of reality. Robustness, the ability to perform well under uncertainty. thus relates to several themes in ML including adversarial attacks, out-of-sample performance and
training by design, e.g., through
Corresponding author. www maths ox. ac. uk/ www.keoople/aa..obla.....
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

out-of-distriee -f--siiibbbittionn performance. In this work, we mainly focus on the former but offer unified perspective on robustness in all of its facets.
Vulnerability of DNNs to crafted adversarial attacks (AA), diagnosed in Biggio et al. (2013), Good- fellow al. (2015), relates to the ability of attacker to manipulate network's outputs by changing the input images only slightly - often in ways imperceptible to a human eye. As such, AA are of key importance for security-sensitive applications and an active field of research. Most works so far have focused on attacks under pointwise ly-bounded image distortions but a growing stream of research, pioneered by Staib and Jegelka (2017) and Sinha al. (2018), frames the problem using Wasserstein distributionally robust optimization (DRO). We offer novel contributions to this literature.
Our key contributions can be summarized as follows. 1) We propose a unified approach to adversarial attacks and training based on sensitivity analysis for Wasserstein DRO. We believe this approach, leveraging results from Bartl et al. (2021), is better suited for madient-based optimization methods than duality approach adopted in most of the works to date. We further link the adversarial accuracy
to the adversarial loss, and investigate the out-of-sample performance. 2) We derive a general adversarial attack method. As special case, this recovers the classical FGSM attack lending it a further theoretical underpinning. However, our method also allows one carry out attacks under a distributional threat model which, we believe, has not been done before. We also propose a rectified DLR loss suitable for the distributional attacks. 3) We develop asymptotically certified bounds on adversarial accuracy, applicable to a general threat, including the classical pointwise perturbations. The bounds are first-order accurate and much faster to compute than, e.g., the AutoAttack (Croce and Hein, 2020) benchmark. The performance of our methods is documented using CIFAR-10 (Krizhevsky, 2009), CIFAR- 100 (Krizhevsky, 2009), ImageNet (Deng et al., 2009) datasets and neural networks from RobustBench (Croce et al., 2021).
2 Related Work
Adversarial Attack (AA). Original research focused on the pointwise l,.-bounded image distortion. Numerous attack methods under this threat model have been proposed in the literature, including Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2015), Projected Gradient Descent (PGD) (Madry et al., 2018), CW attack (Carlini and Wagner, 2017). 7), etc. In these white-box attacks, the attacker has full knowledge of the neural network. There are also black-box attacks, such as Zeroth Order Optimization (ZOO) (Chen et al., 2017). Boundary Attack (Brendel et al., 2018), and Query-limiter Attack (Ilyas et al., 2018). AutoAttack (Croce and Hein, 2020), an ensemble of white-box and black- box attacks, provides useful benchmark for pointwise l 1,-robussness of neural networks. Notably Hua et al. (2022) considered AA with Ip distance replaced by a proxy for human eye evaluation.
Adversarial Defense. Early works on data augmentation (Goodfellow et al., 2015, Madry et al., 2018, Tramèr et al., 2018) make use of strong adversarial attacks to augment the training data with adversarial examples; more recent works (Gowal et al., 2021, Xing et al., 2022, Wang et al., 2023) focus on adding randomness to training data through generative models such GANs and diffusion models. Zhang et al. (2019) consider the trade-off between robustness and accuracy of neural network via TRADES, regularized loss. Analogous research includes MART (Wang et al., 2020) and SCORE (Pang et al., 2022). Other loss regularization methods such as adversarial distributional training (Dong et al., 2020) and adversarial weight perturbation (Wu et al., 2020) have been shown to smooth the loss landscape and improve the robustness. In addition, various training techniques can be overlaid to improve robustness, including droup-out layers, early stopping and parameter fine-tuning Sehwag et al. (2020). The closest to our setting are Sinha et al. (2018), García Trillos and Garefa Trillos (2022) which employ Wasserstein penalization and constraint respectively. However, so far, even the papers which used distributional threat models to motivate DRO-basec training methods actually used classical pointwise attacks evaluate robustness of their trained DNNs. This highlights the novelty of our distributional threat attack.
Robust Performance Bounds. Each AA method gives particular upper bound on the adversarial accuracy of the network. contrast, research on certified robusiness aims at classifying images which are robust to all possible attacks allowed in the threat model and thus providing an attack-agnostic lower bound on the classification accuracy. To verify robustness of images, deterministic methods using off- shel solvers (Tjeng et al., 2019), relaxed linear programming (Wong and Kolter, 2018,
2

---

Weng et al., 2018a) or semi cemi-definite programming (Raghunathan et al., 2018, Dathathri et al., 2020) have been applied. Hein and Andriushchenko (2017), Weng al. (2018b) derive Lipschitz-based metrics to characterize the maximum distortion an image can uphold; Cohen et al. (2019) constructs certifiable classifier by adding smooth noise to the original classifier; see Li et al. (2023) for review.
Distributionally Robust Optimization (DRO). Mathematically, it is formulated as a min-max problem
inf sup Ez]] 66 QE
(I)
where we minimize the worst-case loss over all possible distributions Q E P. In financial economics, such criteria appear in the context of multi-prior preferences, see (Gilboa and Schmeidler, 1989, Föllmer and Weber, 2015). We refer to (Rahimian and Mehrotra, 2019) for survey of the DRO.
We focus on the Wasserstein ambiguity set & B& (P), which is ball centered the reference distribution P with radius å under the Wasserstein distance. We refer to Gao and Kleywegt (2022) for a discussion of many advantages of this distance. In particular, measures close each other can have different supports which is key in capturing data perturbations, see Sinha et al. (201 8). Staib and Jegelka (2017) interpreted pointwise adversarial training as a special case of Wasserstein DRO (W-DRO), Volpi et al. (2018) utilized W-DRO to improve network performance on unseen data distributions. More recently, Bui al. (2022) unified various classical adversarial training methods, such as PGD-AT, TRADES, and MART, under the W-DRO framework.
W-DRO, while compelling theoretically, is often numerically intractable. In the literature, two lines of research have been proposed to tackle this problem. The duality approach rewrites (1), changing the sup univariate inf featuring transform of fa. We refer to Mohajerin Esfahani and Kuhn (2018)
for the data-driven case, Blanchet and Murthy (2019), Bartl et al. (2020), Gao and Kleywegt (2022) for general probability measures and Huang al. (2022) for a further application with coresets. The second approach, which we adopt here considers the first order approximation to the original DRO problem. This can be seen as computing the sensitivity of the value function with respect to the model uncertainty as derived in Bartl et al. (2021), see also Lam (2016), García Trillos and García Trillos (2022) for analogous results in different setups.
3 Preliminaries
Image Classification Task. An image is interpreted as a tuple (I, y) where the feature vector
E X' encodes the graphic information and y E y {L..... ..... . denotes the class, tag, of the image. W.l.o.g., we take X = [0. 1]".. A distribution of labelled images corresponds to a probability measure P on X x y. We are given the training set Dr, and the test set Dtc, subsets of X' Jr i.idd sampled from P. We denote P (resp. P) the empirical measure of points the training set (resp. test set), i.e., P |P.r| E( 0(w.))- A neural network is a map fo : X - Rm
where (x) a + b²). fo(x) f'o... f'
is a nonlinear activation function, and 0 {w<, b'; i 1) is the collection of parameters. We denote S the set of images equipped with their labels generated by fo. i.e.,
s (1r, v) X' y arg max fo(x:; (v) 1sism
The aim of image classification is to find network fo with high (clean) prediction accuracy A := P(S) = Ep[[s]. To this end, fe is trained solving² the stochastic optimization problem
inf EPLL((((z), 2)],
dee
where è denotes the of admissible parameters, and is a (piecewise) smooth loss function, e.g..
cross entropy loss CE: R. x y - IR given by
CE(,,V) - (log softmax(=))
In practice, is not accessible and we use P or 1 instead, c.g., in (2) we replace P with P and then compute the clean accuracy as P(S). In our experiments we make it clear which dataset used. By convention, cross entropy is function of two probability measures. In this case, we implicitly normalize the logit by applying softmax, and associate class y with the Dirac measure 8y.
3

---

Wasserstein Distances. Throughout, (p. g) is pair of conjugate indices, 1/p + 1/9 1. with 1 < p & 0b. We consider a norm on X' and denote 1. its dual, || (a. | < 1}.
Our main interest is in -11 the I,-norm for which -I I where (r, 8) are conjugate indices, & r & sc. We consider adversarial attacks which perturb the image feature but not its label Accordingly, we define pseudo distance* d on X x y as
(22, W2)) = | - x2ll + 00 (0ll(v)) (mz)"
We denote II(P, Q) the set of couplings between (æ, y) and (x', 3²) whose first margin is and second margin is Q, and Tµ P: == P T denotes the pushforward measure of P under map T.
The p- Wasserstein distance, 1 & p o0, between probability measures P and Q on X y is
Q) = inf E [d((z)) v1), (x2, v2)) T ((P,)))
(5)
The oc- Wasserstein distance Wo is given by
W (s Q)= esssse sup (1(1,, (12,
IT(P, Q))-
(6)
We denote the p- Wasserstein ball centered at P with radius by Bs(P). We mainly consider the cases where p, (2, oo). Intuitively, we can view p the index of image-wise flexibility and r as the index pixel-wise flexibility. Unless p = 1 is explicitly allowed, p > 1 in what follows.
Wasserstein Distributional Robustness: adversarial attacks and training
W-DRO Formulation. The Wasserstein DRO (W-DRO) formulation of DNN training task is given by:
inf sup Eo(L(Jo(x). 6E QEBa(P)
where (P) is the p-Wasserstein ball centered at P and 5 denotes the budget of the adversarial attack. In practice, P is not accessible and is replaced with P. When oo, the above adversarial loss coincides with the pointwise adversarial loss of Madry et al. (2018) given by
inf E[]sup(L(ffa(e))) 8) |a' æ| 8]].
050
Recently, Bui al. (2022) considered a more general criterion they called unified distributional robustness. It can be re-cast equivalently as an extended W-DRO formulation using couplings:
inf sup Ex[Jo(z, y, .')).
(8)
OE (P-)((P)))
where (P.)).) is the set of couplings between (a, v) and (a'. v/) whose first margin is P and the second margin within a Wasserstein 5-ball centered at P. This formulation was motivated by the observation that for p co, taking Jø(a (z, y, x', ./) ((fe(x).v) + BL(fe(z), fo(x))) it retrieves the TRADES loss of (Zhang et al., 2019) given by
inf Ep L(fe(z).v) + dE0
sup 2/1z-1/66
W-DRO Sensitivity. practice, training using (7), let alone (8), computationally infeasible, To back propagate 0 is essential to understand the inner maximization problem denoted by
V(6) = sup [olJo(z y)].
QEB,(P)
where write Jo( L(fe(z),)) One view the adversarial loss V(8) as certain regularization of the vanilla loss. Though we are not able to compute the exact value of V(5) for neural networks with sufficient expressivity, DRO sensitivity analysis results allow us to derive numerical approximation to (5) and further apply gradient-based optimization methods. This is the main novelty of our approach previous works considering W-DRO formulation mostly relied on duality results in the spirit of Blanchet and Murthy (2019) to rewrite (7).
'Our results can be adapted to regression tasks where the class label is continuous and sensitive to the perturbation. In such setting different d would be appropriate.

---

Assumption 4.1. We assume the map (z, v) - Jo y) is L-Lipschitz under d, i.e.,
[Jo( v1) - Ja(22, v2)l < Ld( (11, vi), (22, 12))).
The above assumption is weaker than the L-smoothness assumption encountered in the literature which requires Lipschitz continuity of gradients of Jo. see for example Sinha et al. (201 Assummptoon BJ and Volpi et al. (2018)[ Assumptions
2]. We also remark that our assumption holds for any continuously differentiable Jo as the feature space X' = [0. 1 is compact.
The following result follows readily from (Bartl et al., 2021, Theorem 2.2) and its proof.
Theorem 4.1. Under Assumption 4.1, the following first order approximations hold:
(i) V(6) V(0) + 8Y + o(5), where
r= = Ep Vol 1/4
(ii) V()) = Eos [,, y)l + o(0), where
Q8 [1. w) - (x 8h(V vV 12 P.
and h is uniquely determined by (h(r), = ||0]
The above holds for any probability measure, in particular with replaced consistently by an empirical measure P or P. In Figure I, we illustrate the performance of our first order approximation of the adversarial loss on CIFAR- 10 (Krizhevsky, 2009) under different threat models.
(W,., Timos Model
[W. Thmet Moree
V(R
V/00 -2
P05
1.2
-0.0
0.5
0.5
-0.0
0.7
Figure 1: Performance the first order approximation for the W-DRO value derived in Theorem 4.1. Left: NeteResNet-28-111 (Gowal et al., 2020) under CE loss (3) and (Wa,, lse) threat model with 1/255, ..., 10/255. Right: WideResNet-28-- 10 (Wang et al., 2023) under ReDLR loss (10) and (W2, 12) threat models with 5 = 1/16,... 10/16.
WD-Adversarial Accuracy. We consider an attacker with perfect knowledge of the network fo and the data distribution P. aiming to minimize the prediction accuracy of fo under an admissible attack. Complementing the W-DRO training formulation, Staib and Jegelka (2017), Sinha et al. (2018) proposed Wasserstein distributional threat models under which an attack is admissible if the resulting attacked distribution Q stays in the p- --Wasserstein ball B&( P), where 5 is the attack budget, i... the tolerance for distributional image distortion. We define the adversarial accuracy as:
Aş inf Q(S) inf Eql1s]. (P)
QEBs(P)
Note that As is decreasing in with A, A. the clean accuracy. For p 0c, the Wasserstein distance essentially degenerates to the uniform distance between images and hence the proposed threat model coincides with the popular pointwise threat model. For & p oo, the distributional threat model is strictly stronger than the pointwise one, as observed in Staib and Jegelka (2017, Prop. 3.... Intuitively, is because the attacker has a greater flexibility and can perturb images close to the decision boundary only slightly while spending more of the attack budget on images farther away from the boundary. The threat is also closely related out-of-din distriibuttiiiii generalization, see Shen et al. (2021) for survey.
5

---

WD-Adversarial Attack. We propose Wasserstein distributionally adversarial attack methods. As mentioned above, date, even the papers which used distributional threat models to motivate DRO-based training methods then used classical pointwise attacks to evaluate robustness of their trained DNNs. Our contribution novel and enabled by the explicit first-order expression for the distributional attack in Theorem 4. (ii), which is not accessible using duality methods.
We recall the Difference of Logits Ratio (DLR) loss of Croce and Hein (2020). (Zl,...y 7m) fa()) for the output of a neural network, and ((1) e ... > 2(m) are the order statistics of 2, then DLR loss given by
write 2
2y 2(2)
by =(1)
2(1) - 2(3)
DLR(2,9)
By 2(1)
else.
2(1) 2(3)
The combination of CE loss and DLR loss has been widely shown an effective empirical attack for pointwise threat models. However, under distributional threat models, intuitively, an effective attack should perturb more aggressively images classified far from the decision boundary and leave the misclassified images unchanged. Consequently, neither CE loss nor DLR loss are appropriate this intuition is confirmed in our numerical experiments, see Table for details. To rectify this, propose ReDLR (Rectified DLR) loss:
2y - (22
if By =(1):
ReDLR(z, v) -(DLR) =
2(1) 2(3
(10)
else.
Its key property is to leave unaffected those images that are already misclassified. Our experiments show it performs superior CE or DLR.
An attack performed using the test data set. For a given loss function, our proposed attack is:
projs (a' ah(V ah(Va.o(o' y)) T -V "oJo(a"' v))l
(11)
where is the step size and projs is a projection which ensures the empirical measure pi+1
[Deal (xzg)))D, (at+ u) stays inside the Wasserstein ball B5(P), In the case p == p 0D, verify h(x) = sgn(x) and write (11) as
x r+1 projs (a' + a J .y)))
This gives exactly Fast Gradient Sign Method (single step) and Projected Gradient Descent (multi- step) proposed in Goodfellow al. (2015), Madry al. (2018) and we adopt the same labels for our more general algorithms. A pseudocode for the above attack is summarized in Appendix C.
Finally, note that Theorem 4.1 offers computationally tractable approximations to the W-DRO adversarial training objectives (7) and (8). In Appendix D we propose two possible training methods but do not evaluate their performance and otherwise leave this topic future research.
5 Performance Bounds
Understanding how a DNN classifier will perform outside the training data set is of key importance. We leverage the DRO sensitivity results now to obtain lower bound Ag. We then use results convergence of empirical measures in Fournier and Guillin (2015) to translate our lower bound into guarantees out-of-sample performance.
Bounds on Adversarial Accuracy.
We propose the following metric of robustness:
Ag
R₂
[O. 17.
A
Previous works mostly focus on the maximum distortion a neural network can withhold to retain certain adversarial performance, see Hein and Andriushchenko (2017), Weng al. (2018b) for
"To stress the Wasserstein attack and the particular loss function may write, egg., W-PPGD-ReDLL

---

local robustness and Bastani et al. (2016) for global robustness. However, there is no immediate connection between such a maximum distortion and the adversarial accuracy, especially in face of distributionally adversarial attack. In contrast, since A Ao is known, computing RR is equivalent to computing As. We choose to focus on the relative loss of accuracy as it provides convenient normalization: 0 & RR & 1. Rs = corresponds to very robust architecture which performs as well under attacks as it does on clean test data, while Rs = corresponds to an architecture which loses all of its predictive power under adversarial attack. Together the couple (A, As) thus summarizes the performance of a given classifier. However, computing As is difficult and time- coneumnnnuming. Below, we develop a simple and efficient method to calculate theoretical guaranteed bounds on R and thus also on As-
Assumption 5.1. We assume that for any Qe Bs(P)
< Q(S) <1
iii (p(Q(-1S). P(JS))
(() o(6), where S (X' S and the conditional distribution is given by Q(E Q(E (0(EnS)/QU S)QQ(S).
The first condition stipulates -on-eegen:rac:: the classifier does not perform perfectly but retains some accuracy under attacks. The second condition says the classes are well-separated: for ó small enough admissible attack can rarely succeed.
We write the adversarial loss condition on the correctly classified images and misclassified images as
C(o) = sup Eo[Jo(z,))]S] and ( = sup EolJo(z, y)|s.. Qu (P))
Qe
We note that an upper bound on R. is given by any adversarial attack. In particular,
RS $ R5 == Qs(S)/A.
(12)
Theorem 5.1. Under Assumptions 4.1 and 1. we have an asymptotic lower bound as 5 - 0
Rs W(0) - (())
W(0) V(0) + o(8) R2' + o(8) RR, o(8).
(13)
where the first order approximations are given by
(00) - (o,, and R3 W(0) - V(0) 88 (0))) V(0)
R
(14)
VV0)-V(0)
The equality between the lower bound and the two first-order approximations R2J and R3 follows from Theorem 4. Consequently, R2 := min R,z} allows us estimate the model robustness without performing any sophisticated adversarial attack. Our experiments, detailed below, show the bound reliable for small and is orders of magnitude faster to compute than Rs even in the classical case of pointwise attacks. The proof is reported in Appendix A. Its key ingredient is the following tower-like property.
Proposition 5.2. Under Assumptions 4.1 and 5.1, we have
V()) sup Eg(C(H)1s + W + o(6). QEBx(P)
Bounds on Out-of-Sample Performance. Our results on distributionally adversarial robustness translate into bounds for performance of the trained DNN unseen data. We rely the results of Fournier and Guillin (2015) and refer to Lee and Raginsky (2018) for analogous applications to finite sample guarantees and to Gao (2022) for further results and discussion.
We fix 1 <<p p < n/2 and let N = [Derl. M = [Dee If sampling of data from P described on a probability space (2, F, P) then is a random measure on this space and, by ergodic theorem, P-a.s., it converges weakly to P N - In fact, W,,PP, P)) converges to zero IP-a.s. Crucially the rates of convergence were obtained Dereich et al. (2013), Fournier and Guillin (2015) and yield
(P, P)] & - and P(W,(P,,)) > E) K exp(-KKe="),
(15)
where is constant depending on p and n which can be computed explicitly, see for example Guo and Obłój (2019, Appendix). This, with triangle inequality and Theorem 5.1, gives
7

---

Corollary 5.3. Under Assumptions 4.1 and 5.1 on measure P, with probability at least 1 2K exp(-KE" 3) it holds that
P(S) > AR + o()).
Next results provide a finer statistical guarantee on the out-of-sample performance for robust (W-DRO) training. Its proof is reported in Appendix B.
Theorem 5.4. Under Assumption 4.1, with probability at least - K exp( Sep(-KNV KNe)) we have
1/8 + +(E) < V(6) + LE (Eq (o)o2x)))) QERS(P)
V(0) & V(8) +E
sup
where B3 (P) = arg max (P Eq [o, (2, y) and constant K only depends on and n.
Our lower bound estimate in Theorem 5.1 can be restated as
(6) (0)
A = Ā Åσ $
(0)) Č(() + o
We now use Theorem 5.4 bound AA(0), the shortfall of the adversarial accuracy under P. using quantities evaluated under P.
Corollary 5.5. Under Assumptions 4.1 and 5.1, with probability at least cxxp(-KN6") holds that
((6) (0) AAs(P) < ((0) - Ō()) + W(0) - Č(() + o(8).
2L8
We remark that the above results are easily extended to the out-of-sample performance on the test set, via the triangle inequality W (f, P) & W, (P. P) (P(P, P). By using complexity measures such as entropy integral (Lee and Raginsky, 2018), Rademacher complexity (Gao, 2022, Gao et al., 2022) further analysis can be undertaken for
inf sup EQLJa(x, v)] and PEO Q=Bs(P)
inf sup dE QEBs(P)
Eo(Jo(E,))]+
(16)
In particular, a dimension-free estimate of out-of-sample performance is obtained in (Gao, 2022) under Lipschitz framework with light-tail reference measures.
6 Numerical Experiments
Experimental Setting. We conduct experiments on high performance computing server equipped with 49 GPU nodes. The algorithms are implemented in Python. Experiments are conducted on CIFAR-10, 10, CIFAR-100, and ImageNet datasets. Numerical results are consistent across different datasets, and we present the results on CIFAR-10 in body paragraph only for the sake of brevity. Results on CIFAR- 100 and ImageNet are reported in Appendix F.
CIFAR-10 (Krizhevsky, 2009) comprises 60,000 color images across 10 mutually exclusive classes, with 6,000 images per class. Each image contains 32 x 32 pixels in color channels. We normalize the input feature as vector i [0, 3x33332, The dataset is further divided into training and test sets, containing 50,000 and 10,000 images respectively. We evaluate the robustness of neural networks on the test set only.
We consider four threat models (Wp, 4.) with p. (2, o0) with different range of attack budget depending on the relative strength of the attack. E.g., roughly speaking, if an -attack modifies one third of the pixels of an image with strength 4/255, then it corresponds to an lztattack with strength 1/2. When clear from the context, drop the 5 subscript.
We take top neural networks from RobustBench (Croce et al., 2021), lively maintained repository that records benchmark robust neural networks on CIFAR- against pointwise attacks. For pointwise threat models (Wo. 1,), RobustBench reports As obtained using AutoAttack (Croce and Hein, 2020) for L 8/255 and 12, 8 1/2, see Appendix H. However, due high computational

---

cost of AutoAttack, we apply PGD-50 based on CE and DLR losses as substitute to obtain the reference adversarial accuracy for attacks with relatively small budgets and 6 1/8, 1/4 for 12. For distributional threat models (W2, 1r). there is no existing benchmark attacking method. Therefore, W-PGD attack (11) based on ReDLR loss is implemented to obtain the reference adversarial accuracy Aş- All PGD attacks are run with 50 iteration steps and take between 1 and 12 hours to run on a single GPU environment. Bounds R!, R" compute ca. 50 times faster.
2/255, 4/255 for l
Table I: Comparison of adversarial accuracy of neural networks on RobustBench under different empirical attacks. Set attack budget 8 8/255 for le. threat models and 1/2 for threat models.
Wi
W2
Methods
AutoAttack
W-PGD-CE
W-PGD-DLR
W-PGD-ReDLR
I
57.66%
61.32% 74.62%
79.00%
45.46% 61.69% %
1
75.78%
78.69%
Distributionally Adversarial Attack. We report in Table 1 the average accuracy of top neural networks on RobustBench against pointwise and distributional attacks under different loss functions. The predicted drop in accuracy between pointwise, i.e., 3o-W-DRO attack and distributional 2- W-DRO attack is only realized using the ReDLR loss.
we compare the adversarial accuracy of robust networks on RobustBench against pointwise threat models and distributional threat models. We notice a significant drop of the adversarial accuracy even for those neural networks robust against pointwise threat models.
In Figure 2,
Lon
Adhressriial Aecuncy (9%,
Adformriial Jessuncy (M5,
w0p
305
Adiitittall
Advesazial Acouzay
Figure 2: Shortfall of WD-adversarial accuracy with different metrics lx (left) and lg (right).
Bounds on Adversarial Accuracy. We report in Table 2 the computation time of our proposed bounds R2 min R/J R33 in (14) and R2 in (12) with the computation time of R, obtained from AutoAttack. Computing our proposed bounds R!, R" is orders of magnitude faster than performing an attack to estimate R. This also holds for distributional threat attacks.
Table 2: Computation times of (Wa,, 1 8/255 attack for one mini-batch of size 100, in seconds. We compute R by AutoAttack and average the computation time over models on RobustBench grouped by their architecture.
PreActResNet-18
R8sNet-18
ResNet-50
WRN-28-10
WRN-34-10
WRN-70-16
R R' R
197
175
271
401
456
2369
0.52
0.49
0.17
0.55
0.53
1.46
To illustrate the applications of Theorem 5.1, we plot the bounds R! and Rd against R for neural networks on RobustBench. The results are plotted in Figure 3 and showcase the applicability of our bounds across different architectures." 6 Note that smaller values are suitable for the stronger Wy-distributional attack. For pointwise threat models (top row) compute the bounds using CE loss. For distributional threat models (bottom row), reference adversarial accuracy obtained from a
We use all 60 available networks RobustBench (model zoo) for loe and all 20 available networks for /z.

---

W-PGD- ReD-ReDLR attack and, accordingly, we use ReDLR loss to compute R" and R'. In this case, the width of the gap between our upper and lower bounds varies significantly for different DNNs. To improve the bounds, instead of R we could estimate (()) and use the lower bound in (13). This offers trade-off between computational time and accuracy which explored further in Appendix
Di Thrret Nodd 21230
Three with
Threst
(B6, Ae) Timan Morkl with d 1/510
(W, Ag) Thmaa Made with 1/200
(15,0) Theet Mocel 1/12
(1I, Thess Morie yous 1/16.
Figure 3: R2 & R' versus R. Top row: We -attack with bounds computed based on CE loss across neural networks on RobustBench. Bottom row: W2-attack for the same sets of neural networks with bounds computed using ReDLR loss.
7 Limitations and Future Work
Limitations. Our theoretical results are asymptotic and their validity is confined to the linear approximation regime. We believe that the empirical results we presented from all the leaderboard models on RobustBench across different attack types provide an overwhelming evidence that our results are valid and relevant for the range of attack budget ó considered in AA settings. However, as 5 increases we are likely to go outside of the linear approximation regime, see Figure 1. In Appendix we plot the results for pointwise attack with 5 8/255 where some of neural networks have lower bound R! greater than the reference R. We do not have theoretical results provide guarantees on the range of applicability but, in Appendix E, discuss possible rule of thumb solution.
Future Work. We believe our research opens up many avenues for future work. These include: developing stronger attacks under distributional threat models, testing the performance the two training algorithms derived here and investigating further sensitivity- the relation between the values and optimizers in (16), verifying empirical performance of our out-of- sample results, including Corollary 5.5, and extending these to out-of-distribution performance.
ones, as well as analyzing
Broader Impact. Our work contributes the understanding of robustness of DNN classifiers. We believe it can help users in designing and testing DNN architectures. It also offers a wider viewpoint on the question of robustness and naturally links the questions of adversarial attacks, out-of-sample performance, out-of di-dirtribution performance and Knightian uncertainty. We provide computationally efficient tools to evaluate robustness of DNNs. However, for small attacks and we acknowledge the risk that some users may try to apply the methods outside of their applicable regimes. Finally, in principle, our work could also enhance understanding of malicious agents aiming to identify and attack vulnerable DNN-based classifiers.
results asymptotic and hence valid
Acknowledgements
The authors are grateful to Johannes Wiesel for his most helpful comments and suggestions in the earlier stages of this project. JO gratefully acknowledges the support from St John's 's College, Oxford. YJ's research supported by the EPSRC Centre for Doctoral Training in Mathematics of Random Systems: Analysis, Modelling and Simulation (EP/S023925/1). XB and GH's work, part of their research internship with JO, was supported by the Mathematical Institute and, respectively, St John's College and St Anne's College, Oxford.
10

---

References
D. Bartl, S. Drapeau, and L. Tangpi. Computational aspects of robust optimized certainty equivalents and option pricing. Mathematical Finance, 30(1):287-309, 2020.
D. Bartl, S. Drapeau, J. Oblój, and J. Wiesel. Sensitivity analysis of Wasserstein distributionally robust optimization problems. Proc. Soc. A., 4772256))22221177 Dec. 2021.
O. Bastani, Y. loannou, L.. Lampropoulos, D. Vytiniotis, A. Nori, and A. Criminisi. Measuring neural net robustness with constraint. In Advances in Neural Information Processing Systems, volume 29,
Curran Associates, Inc., 2016.
B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šmdić, P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery in Databases, Lecture Notes in Computer Science, pages 387-402, Berlin, Heidelberg, 2013. Springer.
Blanchet and K. Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-600, May 2019.
W. Brendel, J. Rauber, and M. Bethge. Decision-based adversarial attacks: reliable attacks against black-box machine learning models. In International Conference on Learning Representations, 2018.
A. T. Bui, T. Le, Q. H. Tran, H. Zhao, and D. Phung. A unified Wasserstein distributional robustness framework for adversarial training. In International Conference on Learning Representations, Jan. 2022.
N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. 2017 IEEE Symposium on Security and Privacy (SP), pages 39-57. IEEE, May 2017.
P.YY Chen, H. Zhang, Y. Sharma, J. Yi, and C.-J. Hsieh. ZOO: zeroth order optimization based black-box attacks deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15-26. ACM, Nov. 2017.
J. Cohen, E. Rosenfeld, and Z. Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference Machine Learning, pages 1310-1320. PMLR, May 2019.
Croce and M. Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In Proceedings of the 37th International Conference on Machine Learning, pages 2206-2216. PMLR, Nov. 2020.
Croce, M. Andriushchenko, V. Sehwag, E. Debenedetti, N. Flammarion, M. Chiang, Mittal, and M. Hein. RobustBench: A standardized adversarial robustness benchmark, Oct. 2021.
S. Dathathri, K. Dvijotham, A. Kurakin, A. Raghunathan, Uesato, R. R. Bunel, S. Shankar, J. Steinhardt, I. Goodfellow, P. S. Liang, and P. Kohli. Enabling certification of verification- agnostic networks via memory-efficient semidefinite programming. In Advances in Neural Information Processing Systems, volume 33, pages 5318-5331. Curran Associates, Inc., 2020.
J. Deng, W. Dong, R. Socher, I.-J. Li, K. Li, and I.. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
S. Dereich, M. Scheutzow, and R. Schottstedt. Constructive quantization: approximation by empirical measures, In Annales de I'IHP Probabilités et statistiques, volume 49, pages 1183-1203, 2013.
Y. Dong, Z. Deng, T. Pang, J. Zhu, and H. Su. Adversarial distributional training for robust deep learning. In Advances Neural Information Processing Systems, volume 33, pages 8270-8283 Curran Associates, Inc., 2020.
H. Föllmer and Weber. The axiomatic approach to risk measures for capital determination. Annual Review of Financial Economics, 7(1):301-333 2015.
N. Fournier and A. Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3-4):707-738 2015.
R. Gao. Finite-sample guarantees for wasserstein distributionally robust optimization: breaking the curse of dimensionality. Operations Research, 2022.
R. Gao and Kleywegt. Distributionally robust stochastic optimization with Wasserstein distance. Mathematics of OR, Aug. 2022.

---

R. Gao, X. Chen, and A. Kleywegt. Wasserstein distributionally robust optimization and variation regularization. Operations Research, 2022.
C. A. García Trillos and N. García Trillos. On the regularized risk of distributionally robust learning over deep neural networks. Res Math Sci, 93))54, Aug. 2022.
I. Gilboa and D. Schmeidler. Maxmin expected utility with non non-unique prior. Journal of Mathematiccal Economics, 18(2):111153, 1989.
I. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
S. Gowal, C. Qin, J. Uesato, T. Mann, and P. Kohli. Uncovering the limits of adversarial training against norm-bounde adversarial examples. arXiv preprint DeXiv:2010.035000 2020.
S. Gowal, S.-A. Rebuffi, O. Wiles, F. Stimberg, D. A. Calian, and A. Mann. Improving robustness using generated data. In Advances in Neural Information Processing Systems, volume 34, pages 4218-4235 Curran Associates, Inc., 2021.
G. Guo and J. Oblój. Computational methods for martingale optimal transport problems. The Annals of Applied Probability, 29(6):3111 - -3347, 2019.
L. P. Hansen and M. Marinacci. Ambiguity aversion and model misspecification: an economic perspective. Statistical Science, 31(4)5511-515, 2016.
M. Hein and M. Andriushchenko. Formal guarantees the robustness of classifier against adversarial manipulation. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
X. Hua, H. Xu, J. Blanchet, and V. A. Nguyen. Human imperceptible attacks and applications to improve fairness. In 2022 Winter Simulation Conference (WSC), pages
2022.
R. Huang, J. Huang, W. Liu, and H. Ding. Coresets for Wasserstein distributionally robust optimiza- tion problems. In Advances in Neural Information Processing Systems, Oct. 2022.
A. Ilyas, L. Engstrom, A. Athalye, and J. Lin. Black-box adversarial attacks with limited queries and information. In Proceedings of the 35th International Conference on Machine Learning, pages 2137-2146. PMLR, July 2018.
H. Knight. Risk, Uncertainty and Profit. Boston, New York, Houghton Mifflin Company, 1921.
A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
H. Lam. Robust sensitivity analysis for stochastic systems. Mathematics of OR, 41(4):2248-13 1275,
Nov. 2016.
M. Larsson, J. Park, and Wiesel. On concentration of the empirical measure for general transport costs, 2023.
J. Lee and M. Raginsky. Minimax statistical learning with Wasserstein distances. Advances in Neural Information Processing Systems, 31, 2018.
L. Li, T. Xie, and B. Li. SoK: Certified robustness for deep neural networks. In 44th IEEE Symposium on Security and Privacy. IEEE, 2023.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
P. Mohajerin Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Math. Program., 171(1): 115-166, Sept. 2018.
J. L. M. Olea, C. Rush, A. Velez, and J. Wiesel. The out-of-sample prediction error of the square- root-lasso and related estimators, 2023.
T. Pang, M. Lin, X. Yang, Zhu, and S. Yan. Robustness and accuracy could be reconcilable by (proper) definition. In Proceedings of the 39th International Conference on Machine Learning. pages -72777 PMLR, June 2022.
A. Raghunathan, J. Steinhardt, and P. S. Liang. Semidefinite relaxations for certifying robustness to adversarial examples. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
H. Rahimian and S. Mchrotra. Distributionally robust optimization: A review, Aug, 2019.
12

---

V. Sehwag, S. Wang, P. Mittal, and S. Jana. HYDRA: pruning adversarially robust neural networks In Advances in Neural Information Processing Systems, volume 33, pages 19655-19666 Curran Associates, Inc., 2020.
Z. Shen, J. Liu, Y. He, X. Zhang, R. Xu, H. Yu, and P. Cui. Towards out-of-distribution generalization: survey, Aug. 2021.
A. Sinha, H. Namkoong, and J. Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
M. Staib and S. Jegelka. Distributionally robust deep learning as a generalization of adversarial training. In NIPS workshop on Machine Learning and Computer Security, volume 3, page 4, 2017.
V. Tjeng, K. Y. Xiao, and R. Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference Learning Representations, 2019.
F. Tramèr, A. Kurakin, N. Papernot, I. Goodfellow, D. Boneh, and P. McDaniel. Ensemble adversarial training: attacks and defenses. In International Conference on Learning Representations, 2018.
R. Volpi, H. Namkoong, O. Sener, C. Duchi, V. Murino, and S. Savarese. Generalizing to unseen domains via adversarial data augmentation. Advances in Neural Information Processing Systems, 31, 2018.
Y. Wang, D. Zou, J. Yi, J. Bailey, X. Ma, and Q. Gu. Improving adversarial robustmess requires revisiting misclassified examples. In International Conference on Learning Representations, 2020.
Z. Wang, T. Pang, C. Du, M. Lin, W. Liu, and S. Yan. Better diffusion models further improve adversarial training. In Proceedings of the 40th International Conference Machine Learning. 2023.
Weng, H. Zhang, Chen, Z. Song, C.-J. Hsieh, Daniel, D. Boning, and Dhillon. Towards fast computation of certified robustness for ReI.U networks. In Proceedings of the 35th International Conference on Machine Learning, pages 5276-5285. PMLR, July 2018a.
T. W. Weng, H. Zhang, P.-Y. Chen, Yi, D. Su. Gao, C.-J. Hsich, and L. Daniel. Evaluating the robustness of neural networks: an extreme value theory approach. In International Conference on Learning Representations. International Conference on Learning Representations, ICLR, 2018b.
E. Wong and Z. Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning, pages 5286-5295, PMLR, July 2018.
D. Wu, S.-T. Xia, and Y. Wang. Adversarial weight perturbation helps robust generalization. In Ad- vances in Neural Information Processing Systems, volume 33, pages 2958-2969 Curran Associates, Inc., 2020.
Y. Xing, Q. Song, and G. Cheng. Why do artificially generated data help adversarial robustness. In Advances in Neural Information Processing Systems, Oct. 2022.
H. Zhang, Y. Yu, Jiao, Xing, L. E. Ghaoui, and M. Jordan. Theoretically principled trade-off between robustness and accuracy. In Proceedings of the 36th International Conference on Machine Learning, pages 7472-7482. PMLR, May 2019.
13

---

A Bounds on Adversarial Accuracy
Recall that Proposition 5.2 states the following tower-like property
V(6) sup Eo(C(8)1s + W go] o(6), (PBa(P)
where
C(6) sup Qe
Eo[Jo(r,y]sS] and ( sup QER,(P)
Proof of Proposition 5.2. One direction follows directly from the usual tower property of conditional expectation:
V()) sup QEBx(P) Eo[J(r,))]== sup Eq Eg(Eo(((.V))(([]] QEBa(P) W(
< sup E ((0))))s++((65s)))) (P),(P)
For the other direction, note that
Q(E[S) Q(E S))Q(S) and = 5T/Q(S))
are well-defined for any Borel by Assumption 5.1. Take an arbitrary & > 0 and Qe, Qu B& (P) such that
Eq.l > C(ă) -a and Eq. > ( - E.
We further take Q. (P) such that
Eq.(C( s= QeBx(P)
sup
and write distribution @ given by
These give = Q
sup Eg(C(0)1 = 8 QEB,(P)
3a EE. (e,, [|[]] (J(c,,,))) 3
=Eg|Jo(2, v)1 3E.
Recall Assumption 5.1 (ii) gives for any QE E (s(P)
(((((())),P((1555) + W,(QQ(1)))))(()))))) 0()).
Now take ne (I(Q.(41)), such that E.,, [d, similarly Tar E (( Then by definition of Q, we have x = (.(S) + (S)) E II(Q., Q). Moreover, we derive W)(Q..Q)² & Ex[d(X,
+ (19)) and
(Btp://........00)))++0+00...... =(
which implies W, 2) o(8) by triangle inequality. Hence, by L-Lipschitzness of Jo and (Bartl et al., 2021, Appendix Corollary 7.5) we obtain
sup Eo(C()) + W < V(8+ o()) 38 V(8) o(6) + 3z. (EB.(P)
Finally, by taking
we deduce
(8)
sup Eg(C(()Ls+ ((0]ss=++ o()) (P))
which concludes the proof of Proposition 5.2.
14

---

Now, we present the proof of the lower bound estimate in Theorem 5.1,
As W (O) (0)
R.s
(()) - V(0)
Proof of Theorem 5.1. By adding and subtracting W Proposition 5.2 now gives
V())
sup Eg(C(6)4s + W (6) + o(6)
Qe (P())
sup Eq (W& ((6)) 0
QeB
(6)) (W - (()) 0()). Naturally, rewrite loss V(0) using the usual tower property
V(0) = AC (1 - A)) ((0) (0) - C(O))A.
Together these yield
V(6) - (0) = (1 (W W(0)) + As(C(o) - C(O)) + (W(0) C(O)) - As) + 0(6)
> (W) C(0))(A- As) o(8).
Plugging in C(0) = (V) - (1 - (---))W(0)) (0)]/A completes the proof.
B Bounds on Out-of-Sample Performance
The concentration inequality in Fournier and Guillin (2015) is pivotal to derive the out-of-sample performance bounds. It characterizes how likely empirical measure deviate from its generating distribution. We note that recently (Larsson et al., 2023, Olea et al., 2023) obtained concentration inequalities considering other transport costs, including sliced Wasserstein distances which are of particular interest for regression tasks. Recall we denote P as the empirical measure of training set Dr, with size N and P as the empirical measure of test set Dtc with size M. We use the same notations to denote quantities computed from P and P. respectively. We restate the concentration inequality
(F, P) E) & K <exp(-KNe"),
where is a constant only depending on n and p. For convenience, K might change from line to line in this section. Together with Theorem 1. we give an out-of-sample clean accuracy guarantee Corollary 5.3.
Proof of Corollary 5.3. By triangle inequality and concentration inequality, we have
FOW,(P, P) > 2s) & P(W,(P, P) > E) + (P, P) s) < 2K exp(-Ke" min(M, NJ). With Theorem 5.1, it implics that with probability at least - 2K exp(- min(M,NN) we have À Age 2 AR + o(e).
The following results provide a guarantee on the out-of-sample adversarial performance.
Proof of Theorem 5.4. Estimates in Fournier and Guillin (2015) imply that with probability least 1- K exp(-KNe N*",, we have BB(P) B8+s (P). Hence, we derive V(ō) V s). On the other hand, since Ja is L-Lipschitz, from (Bartl et al., 2021, Appendix Corollary 7.5) we obtain
1/9 + +(E),
((8+e) V(6)+ + sup QEB3(())
where BT(P) arg max maxxeBB(PP EolJo(a, v)]. Combining above results, we conclude that with probability at least 1 - K Kexp(- KN
1/4 + + ( Le.
V(6) < (()) + sup (E
[eelV
15

---

Proof Corollary 5.5. By Theorem 5.1, we have
V(0) ( ( ((O) o()).
AP)
We now bound the numerator and denominator separately. By taking ö in Theorem 5.4, we have with probability at least 1 K (00K--8))), ( < V Lö. Similarly, also show that V(0) V(0)- Ló. Hence, we have with probability at least K cop"))
V(6) - ((()) < V6)
(()) + 2L6.
For the denominator, notice that P(P B,(P)) > 1 - K exp( - KN exp()")). By Assumption 5,1 (ii), we have with probability at least (xp(-KKN6")
w,(P((1)) + wy, = o(6).
This implies
[C(0) ((0) - ((0) + (() = o(8).
Combining above results, we conclude that with probability at least 1 K exp( Sap(-KNN -KN8",
AAs(P) & v(6) (0)
2L8
+
W(0) - Č(() +
W(0) Ō(0)
C W-PGD Algorithm
We give the details of W-PGD algorithm implemented in this paper. Recall in Section 4, we propose
[+1 projs (a' ah(V y) VV 1)
(17)
where take | ||, and hence h is given by (h(x), || In particular, M(x) sgn(x)) for s = 1 and h(r) = x/||ø/|e for 2. The projection step projs is based on any off-the-shelf optimal transport solver 9 which pushes the adversarial images back into the Wasserstein ball along the geodesics. The solver 9 gives the optimal matching T' between the original test data Drr and the perturbed test data D/c- Formally, projs maps
L' d x 5d (T(x) x),
1/p
where d 1 Σ (E.,)DDD. TT(x) -x the Wasserstein distance between P and P., See Algorithm for pseudocodes. numerical experiments, due to the high computational cost of the OT solver, always couple each image with its own perturbation.
x|p}
16

---

Algorithm 1: W-PGD Attack
Input: Model parameter 0, attack strength 6, ratio r; iteration step 7, OT solver Y; Data: Test set De {(r,))((<, ~ Pj with size M;
def projs (D te: D/r)
T = J Dit);
// Generate transport map from OT solver
d = M (i (T(x) - =x|p] 1/p
// Calculate the Wasserstein distance
for (I, in Due do
x + dd 1 (T(x) z); x' - clamp(r1 rr, 1);
// Project back to the Wasserstein ball
return D/r- def att)ck(D(t):
- ró/l;
// Calculate stepsize
Dide - Diri
for 1 & i & do
T M (uwieeD V (o 1/a
// Calculate T
for (I, Didde do
(v, - (x + odl Jo v (1ll
Dudv projs Die, Dade); return Dade.
D Wasserstein Distributionally Adversarial Training
Theorem 4.1 offers natural computationally tractable approximations to the W-DRO training objective
inf sup Eq[Jo(x. v) #e QEBx(P)
and extension
sup E v. 0E (P.)
inf
First, consider regularized optimization problem:
inf Ep[[e(x, 8Y].
dee
The extra regularization term 8T allows us to approximate the W-DRO objective above. similar approach has been studied in García Trillos and García Trillos (2022) in the context of Neural ODEs, and Sinha et al. (2018) considered Wasserstein distance penalization and used duality.
Training is done by replacing with P. Note that f is a statistics over the whole data set. order to implement stochastic gradient descent method, an asynchronous update of the parameters is needed. We consider = -I and, by a direct calculation, obtain
V f1- 21-9E Ep V. a V VaJo(a, y), sgn( Vo.Jo v))) 2..
We calculate the term 9--9 from the whole training dataset using parameter 0 from previous epoch;
we estimate
E VeVVveedeee v), sgn(( Jo y)>> J0(( y)
on a mini- batch and update current parameter after each batch. At the end of an epoch, we update 0* to 0. See Algorithm 2 for pseudocodes.
Another classical approach consists in clean training the network but on the adversarial perturbed data. To this we employ the Wasserstein FGSM attack described in Section 4 and shift training data (x, y) by (x,, v) - (prois(r + Jo x))
w)ll 1)1l )..)
17

---

Similarly to the discussion above, an asynchronous update of parameters is applied, see Algorithm for details. Empirical evaluation of the performance of Algorithms 2 and 3 left for future research.
Algorithm Loss Regularization
Input: Initial parameter Oo. hyperparameter 8, learning rate n/: Data: Training Drr {(2,, (x,,)) P} with size N: 8* - to. 0 - -0;
repeat
T=
(+ (F.a)EDD VaJor (z, v)ll1
1/9
// Calculate T from 0*
repeat
Generate mini-batch B with size B):
// Calculate gradient (o
VeJo(z, Do] (i VoJo(z,
// Calculate gradient VoT
VoT = - B ( M vl
// Update 0 by stochastic gradient descent
0 - 0 VVJal( y) + dV,T);
until the end of epoch;
8* - 0:
until the end condition.
Algorithm 3: Adversarial Data Perturbation
Input:
Initial parameter 0o, hyperparameter 8, learning rate ry; Data: Training set Drr ((x, (x, v) P) with size N; 8* - to. - 0o:
repeat
(z, w>1l? 1/4
V T= ( E
// Calculate Y from 0*
repeat
Generate mini-batch B with size [B]
// Do W-FGSM attack on B
(z, v) (prois(æ + Sh(V VV. (2,) () v):
// Update 0 by stochastic gradient descent
0 - 0 71 [B] (nnen VoJo(z,y);
until the end of epoch;
0 0:
until the end condition.
E Robust Performance Bounds
As pointed out in Section 7, with attack budget 5 8/255 some neural networks have lower bounds R' surpassing the reference value R obtained from AutoAttack. It is because for most of neural networks = 8/255 outside the linear approximation region the adversarial loss V and we underestimate (8) by using first order approximations in Theorem 4.1. In Figure 4, we plot our proposed bounds R" and R! against R for (W 1xp)) threat model with 5 = 8/255.
In general, to compute more accurate lower bounds the adversarial accuracy, explained in Section 6, we can consider the first lower bound in (13). We thus introduce R² (n) given by
R'(n) ( (88,n)
W V(())
where V(6, n) is the approximated adversarial loss computed by a W-PDG-(n) attack. In Figures 5 and 6, we include plots for different bounds of R under W2 threat models which illustrate the changing performance
the lower bound Theorem as V(8) computed an increasing accuracy. We achieve this performing W-PDG-(n) attack, where 5, 50. An 50 attack takes
18

---

(Woo: 1o) Threat Model with ó = 8/255
R
0.8
R!
0.7
0.5
0.4
0.40
0.45
Figure 4: R'&R' versus R. Bounds are computed based on CE loss across neural networks on RobustBench under a (Wa threat model with budget 8/255. At this 5 linear approximation may be inefficient as seen from the blue dots crossing the diagonal.
10 times more computational time than the n attack and the latter is times more computational costly than the one-step bound R'. The plots thus illustrate trade-off between computational time and accuracy of the proposed lower bound. For clarity, we also point out that Figure has a different scaling from the other plots.
In practice, we would compare our one- ane-step-attack bound R' with the bound obtained by iterating the attack several steps: propose W-PGD(5) in our paper and report R If the difference between two small it indicates linear approximation is working very well. If the difference is significant, we would use (5) and maybe compare it against R' If we observe that V is convex as for the CE loss under (Was: (oo) attack the lower bound should decrease. In this case, the one-step bound may in fact not be lower bound for too large as shown in Figure 4. If we observe (ō) is concave as for the ReDLR loss and our W2 attacks the one-step lower bound might be too low and will increase with additional PGD steps. This is visible in Figures 5 and 6.
5 1/510
1/255
1.00
1.00
R
R"
0.98
0.95
0.96
(G)
R (5)
(50)
0.90
R' (50)
0.94
0.85
0.92
0.90
0.80
0.88
0.75
0.86
0.90
0.92
01.91
0.96
0.98
1.00
0,500
0.825
(1850
01875
10.000
0.925
0.950
0.975
1.000
Figure Comparison of lower bounds computed from different W-PDG-(1) attacks, where n = 5, 50. Bounds computed based CE loss across neural networks on RobustBench under (W2, threat models with budget 1/510, 1/255.
F Experiments Other Datasets
We illustrate our theoretical results CIFAR- 100 (Krizhevsky, 2009) and ImageNet (Deng et al., 2009) datasets. We analyze all the networks included on RobustBench leaderboards. Only lop norm on images is considered as RobustBench does not provide any models for l2 for these datasets. Similar CIFAR-10. CIFAR-100 is a low resolution dataset but with 100 classes. Fach class contains 500 training images and 100 testing images, and each image has 32 32 pixels in 3 color channels. For
19

---

1/32
1/16
1.00
R!
Sagh
0.98
(3)
0.95
(S)
(30)
(50)
0.96
y
0.90
0.94
0.85
0.92
0.90
0.90
0.92
0.91
0.96
0.96
1.00
0.80
0.85
0.90
0.95
1.00
Figure 6: Comparison of lower bounds computed from different W-PDG-(n) attacks, where 5, 50. Bounds are computed based on ReDLR loss across neural networks on RobustBench under (W2, 12) threat models with budget 1/32, 1/16.
ImageNet dataset, we use a subset of 5000 images selected by RobustBench. The size of image may vary among different preprocessing. A typical size is 224 x 224 pixels in color channels. Numerical results mirror those for CIFAR-10 10 the body paragraph.
Before the discussion on the numerical results, remark that the computation time of our proposed methods do not suffer from the curse of dimensionality. Despite the fact that complexity Wasserstein distance in higher dim can cause troubles, this does not happen for our methods due to our formulae for the first order sensitivity. This means that the approximation to the worst case Wasserstein adversarial attack is explicit and only requires to compute the gradient Ja y). In consequence, the size of the image only affects the first layer the DNN and the number of classes affects the last layer of the DNN. The computational time thus mostly determined by the (hidden) architecture of the DNN model we consider.
In Figure 7, we compare the adversarial accuracy under pointwise threat models and distributional threat models. For Wz threat model, we apply a combination PGD-50 attack based on CE, DLR losses to obtain the reference adversarial accuracy; for W2 threat model, we apply a 50-step W-PGD- ReDLR to obtain the reference WDD-avversaria accuracy. Similar to CIFAR- 10, we observe a drop of adversarial accuracy under distributional threat models CIFAR-100 and ImageNet.
In Figure we plot the bounds R' and R" against R on CIFAR-100 and ImageNet. We compute bounds under Wa: -attack based on CE loss across neural networks on RobustBench; Wyyattack for the same sets of neural networks with bounds computed using ReDLR loss, where R (5) denotes the lower bound (eq. (13)) computed from a 5-ete W-PGD attack. For pointwise threat models, our upper and lower bounds sandwich the true (AutoAttack) accuracy ratio very well at fraction of the computational cost. For distributional threat models, our bounds work but the tightness of the bound model-des -epee--de We display also the improved bound obtained with steps of W-PGD attack which leads to marked improvement in the lower bound's performance. This is akin to Figure 5 in Appendix E.
G Comparison to Existing Attack Methods
In this section, we compare our proposed W-PGD attack with existing attack methods. We reiterate that our method focuses on distributional threats under a given budget d. While the W-DRO formulation has been explored in numerous works, discussed, believe that none of them proposed an AA method specifically tailored for the distributional threat under a given attack budget.
We illustrate the main difference between our sensitivity approach and duality approach employed in Sinha et (2018), Volpi al. (2018), Hua al. (2022), etc. When using duality of W-DRO, the optimization involves a minimization over the Lagrangian multiplier X. However, in the aforemen- tioned works, fixed is used. While their choice of may be optimal for some budget 5, there no universal approach achieve an optimal attack for given budget 8. In contrast, our attack is an explicit first-order approximation designed to optimal for a given budget It only involves V te y) and its norms which are fast compute using standard methods.
20

---

CIFAR-100
ImtgeNet
80%
7036
8/25G
6/202
4/206
Adveriarial Anarney (M,, bg)
R/265
Adceratial Accurary (XA5,
000%
6/356
0092
6056
305
3076
32%
2005
3050
10%
030
105
30%
103
8055
09
30%
305
5050
0015
Adversciaa Accuracy I..)
Adversarial Accuracy (W....
Figure Shortfall of WD-adversarial accuracy on CIFAR-100 (left) and ImageNet (right).
(o) Thmme Nodkl
4750
Mtakd 1201
(Ware) The Mookk with 1255
Figure 8: R & R! versus R on CIFAR-100 (top) and ImageNet (bottom).
Despite no existing baseline for addressing distributional threat, is possible to reverse engineer comparison setup ex post. We employ CW attack which gives the minimum distortion needed to successfully attack an image. Due to the computational cost of CW attack, the experiment is conducted on the first 1000 correctly classified images from the ImageNet subset used by RobustBench. By calculating the square root of the mean square of the minimum distortion over this chosen dataset, we obtain a reference (2) budget 0.000711 to perform our distributional attacks. Employing our W-PGDD55))ReDDL
attack results in 934 images being successfully attacked out of the 1000. The CW attack, which by construction was successful on all 1000 images, took ca 4.5h run (on Tesla 1100-SMM-332GB-L. GPU) and the time needed to be scaled linearly with the number of images as the attack has to performed image by image. In contrast, our attack took ca 50min to run (on NVIDIA A 100-SXM4-40GGB GPU). In addition, we use mini-batches, which allows for computational speed improvements based on the available GPU memory.
H Additional Numerical Results
In Tables 3 and 4, report the clean accuracy and the adversarial accuracy under different threat models for all but neural networks available on RobustBench (model zoo). All networks are named after their labels ne-neworkk because they are not robust to any attacks. In addition, we also remove Kang2021Stabb which contains NeuralODE blocks and Ding2020MMA which has huge gap between adversarial accuracies obtained from PGD and AutoAttack.
RobustBench (model zoo). We remove Standard network and Standard
In Tables 5, 6, 7 and 8, include the complete list of R and its bounds used in Figure 3. We write AR" R" R and AR R² R.
21

---

Table 3: Complete list of adversarial accuracies under (W 1x) and (W2, 1x)
threat models.
8=1/8
8=1/4
8=1/8
Network
Clean
Wa
W2
Wa
W/2
Wa.
W2
Augussin2020AAdveersaiaalll
91.08
87.88
82.03
84.48
73.17
72.91
56.66
Augussin2020AAdvvrrsriilll ____iaal__31____ 10
92.23
89.20
83.70
85.80
74.06
76.25
56.33
Auguusin22220AAivrrsrria_LL____
93.96
91.63
84.86
88.32
75.04
78.79
59.73
Ding2020MMA
88.02
83.57
77.69
78.44
69.67
66.09
53.47
Engstrom22U19Robustees
90.83
86.81
81.99
82.37
73.77
69.24
57.77
Gowal22000Uncovering
90.89
87.62
83.19
84.26
75.83
74.50
60.94
Gowal2020Unccvvering
extra
94.73
92.64
88.08
89.52
79.74
80.53
60.18
Rade2021HHchpr_RR88_dde
90.57
88.03
83.57
84.58
77.26
76.15
62.74
Rchufi22021Fixing_22
91.79
89.26
86.09
86.43
81.06
78.80
67.18
Rcbufti2021Fixing_T0 _0_ixinnnn___6______1 1aa_________uxx__dpp_____6 ddpm
92.41
90.36
87.27
87.69
81.67
80.42
67.93
Rebufii001/Fixing_ 70 cltmittmi____ extra
95.74
93.78
89.73
91.18
81.59
82.32
63.43
Rebuffi2021Fixiing R18 cutmix ddpm
90.33
87.48
84.24
84.48
75.86
63.85
Rice20200verfiting
88.68
85.07
80.62
80.35
73.28
67.68
56.83
Rony2019Decoupiin
89.04
84.74
78.47
79.25
69.39
66.44
51.15
Schwag202IPrroxy
90.93
88.42
85.50
85.66
80.50
77.24
67.96
Schwag202IProxy
89.76
87.08
83.34
83.87
77.62
74.41
65.02
95.16
93.44
88.99
90.79
82.58
83.68
68.65
Wing2022RRcter__RRN700111
95.54
93.76
89.94
91.79
83.47
84.97
70.09
Wa2020AAvervarial
88.51
85.32
81.33
82.05
75.31
73.66
62.21
22

---

Table Complete list of adversarial accuracies under (Wo, (0) and (W2, (x) threat models.
6=2/255
6=4/255
8=8/255
Network
Clean
Wo:
W2
Wo
W2
Woc
W2
A RNI8
80.23
73.85
68.54
66.70
58.76
51.06
42.91
(heepalll202/Twwardd WRN34
85.32
79.87
73.41
73.18
64.60
58.04
48.12
Addepalli20022Efffcieent RN18
85.71
79.16
71.75
71.37
59.59
52.48
37.84
Addepaali20022Efficieent WRN
10
88.70
82.95
74.75
75.52
63.35
57.81
42.03
Audrusscchenko02000dddeaaaaaddd
79.85
72.30
66.16
64.45
55.83
43.93
37.86
Cammon2019Cilabeled
89.69
84.59
77.02
77.87
66.59
59.53
46.32
Chenz020AAvvessariall
86.04
79.68
67.45
71.61
51.23
51.56
29.66
Chen2020E:fhcient
85.34
78.48
70.91
70.64
59.24
51.12
39.32
Chen2021LTD B
85.21
79.78
72.74
72.97
61.86
56.94
41.48
Chen202ILTD WRN34_22
86.03
80.71
75.31
74.19
64.95
57.71
44.87
Cui2020Learnable: 2a_pilee_34_1___ 34_10
88.22
81.95
71.25
74.20
57.88
52.86
40.14
Cui2020Learmalle __3___33_00_0
88.70
82.20
72.16
74.46
S7.74
53.57
37.73
Dui202llPrrmmtteriiing
87.02
82.39
77.35
76.96
69.28
61.55
52.43
(bberncdetii222LLLihttXCCCCCC XCTT-L12
91.73
86.59
78.09
79.42
66.77
57.58
44.90
91.30
86.14
77.83
78.89
66.86
57.27
43.90
Dehenedeeti2022..hh..XC1
90.06
84.91
77.11
77.50
65.35
56.14
44.28
Fngetromm2019RRobunnnes
87.03
80.34
74.30
72.22
63.43
49.25
41.85
Gowaa22020U/nncoveringg _a______1111 extra
89.48
84.78
78.08
78.77
67.93
62.80
48.51
Gowal22200Uncoveringg 34
85.64
79.84
73.22
73.47
62.78
56.86
42.87
Gowal22220Unnoveriigg 70 16
85.29
79.81
72.89
73.47
62.25
57.20
43.29
Gowal2020Uinoovrring 70 extra
91.10
86.86
79.81
81.06
70.01
65,88
50.55
Govaa22011Improvingg_22 10_ddddm_100m
87.50
83.37
78.46
78.30
70.50
63.44
54.95
Gowal2021Imprrvingg_ _0cean_________ 11______________ (16__dmm__10000 100m
88.74
84.76
80.48
80.08
73.27
66.11
59.34
Govea22021Improvingg
87.35
82.08
76.83
76.22
68.16
58.63
51.17
Hendrrcks20119ssing
87.11
81.36
74.48
74.21
63.45
54.92
44.19
Huang2020Self
83.48
77.59
69.33
70.55
58.46
53.34
38.96
Exppo2021Exploring
90.56
85.77
77.78
79.50
67.52
61.56
47.30
Huang2021Exploriigg ema
91.23
86.84
79.28
80.79
69.02
62.54
48.46
Jhaang202RRevisttingWWeee
WRN-A4
91.59
87.35
79.76
81.69
69.62
65.79
50.22
Jia202LASSATT34 34_
84.98
79.26
73.00
72.44
62.88
56.26
43.92
Jia20221AS-AT_70016
85.66
80.29
73.90
73.52
63.76
57.61
44.19
Pang2020Roosting
85.14
79.34
71.93
72.60
61.17
53.74
39.40
Pang2022Robustness___
88.61
83.73
78.46
77.16
69.51
61.04
51.67
Pung2022Robustness. WRN70
89.01
84.77
79.57
78.58
70.61
63.35
52.93
Rade202 ddpm
88.16
83.26
77.54
76.83
67.49
60.97
47.37
Rade20211Helperr extra
91.47
86.72
80.47
80.29
69.48
62.83
47.57
Rade2202HHeipe_RR18__dde
86.86
81.12
75.67
74.39
64.92
57.09
43.99
Rade202/Hccler__I18 _
89.02
83.21
77.16
76.36
66.10
57.67
43.38
Rcbuth22021Fiiing_Uu
88,50
84.32
78.88
78.83
70.59
64.64
52.31
Rebufhh022|Fixing__P 2_________t_____________________ ddpm
87.33
82.36
76.33
76.08
66.35
60.75
46.73
Rebufi202//Fixing__1 70___0111 1166_ctmmx_ddee
88.54
84.31
78.64
78.79
68.95
64.25
49.75
Rebuffi2021Fixinn_P00 70_ 177001111001111
1116___mmx_eeree_11111ee _xtraa
92.23
88.02
81.21
82.76
70.39
66.58
47.97
Rebutth2021Fixiing 818 ddpm
83.53
77.99
71.46
71.68
61.83
56.66
44.26
Rice20200vveritting
85.34
79.60
74.06
72.82
64.81
53.42
43.66
Schwag2020HHyda
88.98
83.49
76.02
76.18
65.38
57.14
44.37
Schwag2021Proxx
86.68
81.72
76.91
76.39
68.84
60.27
53.29
1wwwagg021PPox_RI1
84.59
79.25
73.87
72.74
64.73
55.54
46.58
Schwag2021Pron
Prony220221 ResNss152
87.21
82.55
78.08
77.30
70.78
62.79
56.67
Siaawarin2020Improving
86.84
80.21
74.16
72.47
63.54
50.72
43.25
Sridhar202
89.46
84.34
77.42
78.03
66.42
59.66
46.45
86.53
81.45
73.95
75.63
64.18
60.41
45.77
Wang20201mproving
87.51
82.15
74.59
75.47
63.17
56.29
42.57
Wang2023Better__
92.44
88.40
81.51
83.10
71.42
67.31
52.03
2ang2023Berter_wwe W
93.26
89.72
82.88
84.90
73.95
70.69
55.17
Wong2020Fast
83.34
75.77
69.60
67.23
58.38
43.21
36.96
WiveaaAAvversarial
85.36
79.69
73.33
72.90
62.64
56.17
42.28
Auv220AAversariill
88.25
82.98
76.83
76.61
66.45
60.04
46.70
7hang2019Theoreee
84.92
78.96
71.68
71.15
60.30
53.08
40.05
Zhang2019 20u
87.20
79.42
72.40
70.29
60.61
44.83
36.65
Zhang2020AAtacck
84.52
78.48
71.10
71.32
59.45
53.51
40.76
89.36
84.01
81.57
77.10
73.45
59.64
53.50
23

---

Table 5: Complete list of and its bounds under (Wz. (2)
threat model based on CE loss.
8=1/8
6=1/4
Network
AR"
AR'
R
AR"
AR'
Augussin2002AAAvversaiaalll
0.9649
0.0026
-0.0153
0.9275
0.0083
-0.0324
Augussin2020AAdvvesariallll 34_10
0,9669
0.0035
-0.0097
0.9303
0.0115
-0.0201
Augussin2020AAAvvessaaialll
1atteeerrrrria_________ 34_10 extra
0.9752
0.0031
-0.0150
0.9400
0.0084
-0,0239
Ding2020MMA
0,9496
0.0016
-0.0176
0.8912
0.0081
-0.0334
Engstrom2211RRobssnnes
0,9557
0.0019
-0.0087
0,9069
0.0057
-00256
Govaa22020Uncoverrng
0,9640
0,0022
-0.0063
0.9271
0.0045
-00111
Gow.al2020Uncovvrrnngg. extra extra
0.9779
0.0013
-0.0121
0.9451
0.0050
00,2009
Rade202/1Hclpe__H _e__deedeee_RR_ddpppmpp
0.9720
0.0017
-0.0124
0.9339
0.0061
+0,0009
Rchufii202/Fixing. 1aaaaa_____1__11111
0.9724
0.0034
-0.0107
0.9416
0.0060
-0.0232
Rebutii202lFixing 70 cutumii ddpm
0.9778
0.0021
-0.0137
0.9489
0.0052
-002599
Rebuffi2021Fixiine 16 cutmix extra
0,9795
0.0018
-0.0091
0.9524
0.0040
-0.0184
Rebufii202lFixing R18 cutmix ddpm
0,9686
0.0032
-0.0150
0.9352
0.0061
+00339
Rice20200vcrfittnng
0,9593
0.0030
-0.0178
0.9061
0.0090
-0,0342
Rony2019Deccupling
0,9517
0.0015
-0.0144
0.8899
0.0077
-0.0316
Schwag2021Proxy
0.9724
0.0027
-0.0099
0.9420
0.0065
-0.0335
Sehwag2021 Proxy R18
0,9703
0.0028
-0.0133
0.9344
0.0057
-0.0271
Wang2023Better, WRN-28-10
0,9819
0.0013
-0.0098
0.9541
0.0047
-0.0147
Wang2023Better_ - WRN-70-16
0,9814
0.0015
-0.0069
0.9609
0,0029
-0.0163
Wu2020AAversariial
0.9640
0.0024
-0.0088
0.9270
0.0051
-0.0211
Table 6: Complete list R and its bounds under (2)
threat model based on ReDLR loss.
8=1/32
8=1/16
Network
AR"
AR'
R
AR"
AR!
Augussin2020AAdverssiialll
0.9844
0.0058
-0.0358
0.9723
0.0131
+0,5005
Augussin2020AAvverssrialll 34_10
0,9868
0.0026
-0.0518
0.9738
0.0094
-0.0743
Augustin2020AAvvessaiill 34_10 extra
0,9879
0.0049
-0.0452
0,9756
0.0105
-0.0652
Ding2020MMA
0.9788
0.0087
-0.0694
0.9644
0.0148
-0.1079
Engstrom2211Roobustess
0,9834
0.0036
-0.0798
0.9719
0.0085
-0.1250
Gowaa22020Unsovrring
0.9837
0.0048
-0.0581
0.9719
0.0110
-0.0918
Gowal2020Uncoovrring extra
0.9915
0.0026
-0.0574
0.9855
0.0039
-0.0998
Rade2021HHelperr R18 ddpm
0.9879
0.0055
-0.0530
0.9802
0.0075
-0.8871
Rebufi200lFiiiing 28 _8_10 _0__mtiiix____ ddpm
0,9902
0.0034
-0.0572
0.9826
0.0069
-0.0912
Rebufti2021Fixing _0____0______66 70_16_cctmixx_________eeeee__ wtl__cutmmx_pppeee _dpp
0.9920
0.0023
-0.0610
0.9852
0.0055
0.0966
Rebufti2021Fixingg 70_ www.mctttt..mmeeee extra
0.9922
0.0020
-0.0339
0.9851
0.0050
-00852
Rebutii001lFixing_ R18
cwt.mcutmi_i._eeeee ddpm
0,9894
0.0034
-0.0711
0.9791
0.0081
0.11004
Rice20200vcrfitting
0.9859
0.0046
-0.0825
0.9738
0.0104
-0.1663
0.9829
0.0045
-0.0855
0.9672
0.0116
-0.1267
Schwag2021Proxx
0.9918
0.0018
-0.0767
0.9824
0.0047
-0.1165
Schwag Proxy_
0.9890
0.0039
-0.0558
0.9789
0.0097
-0.0668
Wang2023Better WRN-28-10
0,9902
0.0023
-0.0492
0,9832
0.0054
-0.0775
Wang2023Better.
WRN-70-16
0,9919
0.0020
-0.0494
0.9850
0.0043
-0.0780
Wu2020AAvvessarial
0.9867
0.0037
-0.0704
0.9759
0.0092
-0.1114

---

Table 7: Complete list R and its bounds under (Wz, (x)
threat model based on CE loss.
6=2/255
6=4/255
Network
R
AR"
AR'
R
AR"
AR!
Towapl __NN8
0,9205
0.0172
-0,0234
0.8314
0.0403
-0.0390
Addepalii202//owwars: WRN34
0.9361
0.0144
-0,0266
0.8577
0.0374
-0.0399
Addepaali20022Efficiienn RN18
0.9236
0.0126
-0.0194
0.8327
0.0329
-0.0312
kideppalli2222Effiiienettt
0.9352
0.0097
-0.0167
0.8514
0.0275
-0.0218
Andiustcchenkk0000Oddekaaanngg
0.9054
0.0125
-0.0200
0.8071
0.0296
-0.0496
Carmon2019Unlabele
0,9431
0.0056
-0,0122
0.8682
0.0236
00.144
Chen2020AAdvessarial
0.9261
0.0074
-0.0319
0.8323
0.0206
0.0495
Chen2020Efticcient
0.9199
0.0111
-0.1007
0.8273
0.0293
0.0177
Chen20221LTDD_WRR34JJJJ
0,9363
0.0099
-00224
0.8564
0.0275
000347
Chen2021LTD 2
0,9382
0.0105
-0.2280
0.8624
0.0322
-00476
Cui2020L.camalle ____blll3__0000
0,9290
0.0070
-0.1188
0.8410
0.0196
-00324
Cui2020Learnable __rpbbleee4420_0
0.9267
0.0079
-0.0150
0.8395
0.0224
-.0296
Paiat2i/ar
0.9468
0.0069
-0.0173
0.8844
0.0139
-003622
Debenedett12022Lighh.XCCC7 XCTT-L12
0,9440
0.0041
-0.0154
0.8658
0.0162
-0.2333
Dabencdeeti20022iighhhXCTTIMMM
0,9435
0.0049
-001644
0.8641
0.0194
0.0233
Dabemederti2222iighttXXTTT--
0,9428
0.0048
-0.239
0.8605
0.0198
0.0357
Engstroon2011Roobuttnes
0,9231
0.0101
-0.2203
0.8298
0.0263
0.0406
Goval22220Uncoveeringg _8_______________ _x__exrra
0,9476
0.0072
+0.0149
0,8803
0.0221
-00214
0.9323
0.0081
-0.0156
0.8579
0.0206
-00331
Gowaa22000Unccvvrrigg. 70_16
0.9357
0.0055
+0.0144
0.8614
0.0155
-002799
Gowal22200Uncovering
extra
0.9535
0.0050
-0.0129
0.8898
0.0196
000137
Gowa|20211mmpoovngg 28 10 ddpm 100m
0.9528
0.0073
-0.1192
0.8949
0.0177
-.03477
Gowa|22221lmprovingg 70 16 ddpm 100m
0,9551
0.0061
-0.0147
0.9024
0.0169
-00265
Gowa/2021Imprrviigg Re___Rd8___dddddd_ed _ddpm_100mm 100m
0.9397
0.0065
-0.0166
0.8726
0.0117
-0.387
Hendnycks2019UUsing
0.9340
0.0057
-0.0250
0.8519
0.0215
0.0447
Huang2020Self
0.9294
0.0075
-0.0139
0.8451
0.0270
0.0201
Huang2021Explorrng
0.9471
0.0051
-0.0991
0.8779
0.0227
-0.0091
Huang20211Exploring ema
0,9519
0.0054
-0.0103
0.8856
0.0226
-0.1003
Huang2022Revisstingg WRN-A4
0.9537
0.0052
40.1101
0.8919
0.0167
-0.0227
Jia202LLAS-AT334
0.9327
0.0102
-0.0133
0.8524
0.0262
0.0277
Jia2022LAS-TT_7U0 70
0,9372
0.0070
-0.1788
0,8585
0.0229
0.0262
Pang2020Boosting
0,9319
0.0181
-0.0349
0.8526
0.0430
0.0611
Pung2002Robustness,, WRN28_10
0.9449
0.0095
-0.0199
0.8708
0.0229
-0.0225
mmn2022Rohusnes__RRN000
0.9524
0.0056
+0.2200
0.8828
0.0225
-0.0331
Rade2002HHelperdddmm
0.9444
0.0068
-0.0195
0.8715
0.0188
0.0317
Rade202111elper_een _xtra extra
0.9481
0.0057
-0.0158
0,8778
0.0186
0.0247
Rade202|1Helper R18 _dd__dmm___p__
0,9339
0.0098
-0.0203
0.8564
0.0220
000407
Rade202 R18 extra
0.9347
0.0095
+0.1183
0.8578
0.0220
000370
Rebuthi202//ixinn__0000 106 1e___106_______
1116-__utii___e .dpm
0.9528
0.0063
-0.0196
0.8907
0.0226
-00295
Rebufti2021lFxiigg222
0.9432
0.0088
-0.0193
0.8713
0.0262
0.0286
Rebuth2221lFixing 1arpiiiiin_______u__eeee
0,9522
0.0071
-0.0204
0,8899
0.0208
0.0311
Rebuffi2021Fixingg.. 70
_u_mii extra
0.9544
0.0051
-0.0169
0.8973
0.0191
-00282
Rebuffi2021FFxingg.P R1aiiinnn__R___111 ____pmmmmm
0.9337
0.0078
4..140
0.8584
0.0242
-0.2770
Rice20200verfitting
0.9327
0.0091
-0.0233
0.8532
0.0199
-0.0548
Schwag20200yydr
0.9383
0.0055
+0.1133
0.8561
0.0262
-0.126
Schwag202IProxy
0,9428
0.0073
-0.0150
0.8813
0.0166
0.0348
Schwag2021Proxy R18
0,9369
0.0091
-0.0099
0.8598
0.0240
0.0364
Schwag2021Proox
2ro.00221Pooy_eeNNss51222222 ResNest152
0.9466
0.0062
-0.0138
0.8864
0.0151
0.0308
Sttawarin2220mprrving
0.9237
0.0084
-0.0190
0.8345
0.0243
-0.428
Sridhar2021RRousst
0.9428
0.0063
-0.0122
0.8722
0.0221
00.177
Tiibhar2021Robus_344...
0,9413
0.0067
-0.0665
0.8740
0.0208
-0.089
Wang20201mmproving
0,9387
0.0119
40.2166
0.8624
0.0362
00.303
Wang2023Better, WRN-28-10
0.9563
0.0067
-0.0149
0.8990
0.0166
0.0248
0.9620
0.0049
-0.0149
0.9104
0.0165
-0.0339
Wong2020Fast
0,9093
0.0128
-0.0282
0.8068
0.0301
0.0608
Wu2020AAveessriia
0,9336
0.0068
-0.0161
0.8540
0.0225
-00267
Wu2020AAveesaaiial..
0,9403
0.0073
-0.0139
0.8681
0.0228
-0.030
Grang2019Theortticnn
0.9298
0.0061
-0.0190
0.8381
0.0238
-0.0289
7hang2019 You
0.9107
0.0073
+0.0166
0.8061
0.0203
-0.0506
2hang2020AAtteer
0.9285
0.0082
-0.0167
0.8438
0.0257
-0.0267
2000emeeyyyy
0.9402
0.0187
-0.0307
0.8629
0.0404
-0.0514
25

---

Table 8: Complete list of and its bounds under (W2, (o)
threat model based on ReDLR loss.
6=1/510
6=1/255
Network
AR"
AR'
R
AR"
AR!
Aidepalli2022Towarrrr __NN8
0,9762
0.0080
-0.1301
0.9533
0.0202
-0.1902
Addepalli2021Towarrds WRN34
0.9774
0.0102
-0.0849
0.9590
0.0197
-0.1257
Addepaali20022Efficiienn RN18
0.9740
0.0088
-0.1012
0.9534
0.0195
-0.1480
kidepaali22222Effiiienettt Batpi/icittt__N_______ 1_
0.9749
0.0124
-0.0645
0.9563
0.0231
-0.0942
Andrisscchenoo02200dddessnnnd
0,9679
0.0140
-0.0969
0.9438
0.0294
-0.1357
Carmon2019Unlabeled
0,9775
0.0079
-0.8033
0.9584
0.0178
0.1162
Chen2020AAdvessarial
0.9639
0.0182
-0.0351
0,9371
0.0351
0.0485
Chen2020Efticcient
0.9713
0.0147
-0.7742
0,9495
0.0281
001073
Chen20221LTDD_WRR34JJJJ
0,9758
0.0140
-00622
0.9578
0.0236
-00960
Chen2021LTD 2
0,9780
0.0078
10.1077
0.9635
0.0124
-0.1615
Cui2020L.ammalle ____blllc__000
0.9694
0.0121
-0.0663
0.9462
0.0228
-0.8388
Cui2020Learnalle 2artnablle_4__200 _34_20
0.9710
0.0132
-00722
0,9492
0.0231
-0.9882
Parat2i/ar
0.9814
0.0082
-0.8255
0.9654
0.0164
-012006
Debenedett12022Lighh.XCCC7 XCTT-L12
0,9760
0.0076
-0.730
0.9579
0.0181
-0.1063
Dabencdeeti20022igghhhXCTTIMMMM
0,9781
0.0127
0.0477
0.9574
0.0280
0.0682
Dabemseett2222LLghhXXX111111
0,9795
0.0078
000911
0.9620
0.0161
0..370
Engstroon2019Roobuttnes
0.9746
0.0086
-0.1117
0.9550
0.0174
0.1600
Goval22220Uncoverringg
Laapiiinn__________e_eee___ _x__exrra
0,9791
0.0075
00.813
0.9623
0.0153
0012113
0.9748
0.0110
000786
0.9546
0.0220
-0.1166
Gowaa22000Unccvvrrigg. 70_16
0.9722
0.0162
400583
0.9552
0.0232
-0.0906
Gowal22200Uncovering
extra
0.9801
0.0070
-00786
0.9639
0.0136
-0.1
Gowa|20211mmpoovngg 28 10 ddpm 100m
0.9814
0.0070
-008522
0.9690
0.0119
-0.2811
Gowa|22221lmprovingg 70 16 ddpm 100m
0.9838
0.0072
-00778
0.9726
0.0114
-0.1150
Gowa|20211mprrvving 1ae_e_R8_____ddddd_d_______ _ddpm_1000m 100m
0.9797
0.0069
00.044
0.9626
0.0160
-0.1200
Hendnycks2019UUsing
0.9778
0.0090
000963
0.9582
0.0183
00.1398
Huang2020Self
0.9714
0.0117
0007664
0,9478
0.0252
00.0882
Huang2021Explorrng
0.9770
0.0109
+00556
0.9593
0.0208
-0.8003
Huang20211Exploring ema
0.9792
0.0091
-0.6255
0.9623
0.0189
-0.0923
Huang2022Revisstingg
WRN-A4
0.9810
0.0088
40.521
0.9646
0.0181
-0.0766
Jia202LLAS-AT344
0,9762
0.0139
-0.0433
0.9575
0.0232
0.1118
Jia2022LAS-TT_7U0 A6
0.9751
0.0138
-0.0707
0,9583
0.0219
0.1091
Pang2020Boosting
0,9745
0.0093
-0,0444
0.9528
0.0195
0.0330
Pang2002Robustness,, WRN28_10
0.9823
0.0055
-0.1111
0.9707
0.0095
-0.1988
mmn2022Rohusnes__wRN000
0.9836
0.0078
+0.0882
0.9711
0.0139
-0.1378
Rade2002HHelperdddmm
0.9808
0.0068
-0.9336
0.9672
0.0124
-0.1430
Rade202111elper_een _ extra
0.9809
0.0066
-0.846
0.9674
0.0130
-0.1298
Rade202|1Helper R18 ddpm
0.9778
0.0056
-0.1266
0.9627
0.0098
-0.1904
Rade202 R18 extra
0.9784
0.0127
-0.7200
0.9587
0.0244
-0.1073
Rebuthi202//ixinn__0000 111_1100_______
htt________________ .dpm
0.9829
0.0046
-0.0777
0.9681
0.0130
06.1
Rebufti2021lFxiing222 2a__________txx_ddppppppp
0.9816
0.0050
-0. 1.10
0.9651
0.0115
0..1336
Rebuth2221lFixing 01e____0________666666____
0.9824
0.0072
-0.099
0.9680
0.0141
-0.1035
Rebuffi2021Fixingg. 70
_u_mii extra
0.9809
0.0056
-0.7118
0.9661
0.0126
-0.1058
Rebuffi2021FFxingg.P R18_inn_________1 ____pmmmm
0.9758
0.0104
+0.8555
0.9564
0.0194
-0.1276
Rice20200verfitting
0.9773
0.0082
-0.1061
0.9593
0.0159
-0.1547
Schwag20200yydr
0.9758
0.0096
+0.805
0.9577
0.0192
00.1201
Schwag202IProxy
0,9818
0.0073
-0.0831
0.9657
0.0162
00.1002
Schwag2021Proxy R18
0,9795
0.0071
-00964
0.9609
0.0154
00.1770
Schwag2022IProxy
Pro.o02211oooyeeNNsss1222222 ResNest152
0.9805
0.0144
-0.361
0,9667
0.0243
00.573
Sttawarin2220mprrving
0.9747
0.0088
10.1054
0.9511
0.0204
00.500
Sridhar2021RRousst
0,9766
0.0087
-0.0332
0.9594
0.0160
00.1400
Soobatr20
0,9749
0.0105
-0.6022
0.9537
0.0221
-0.0588
Wang20201mmprovingg
0,9738
0.0195
40.0144
0.9552
0.0341
-0.0185
Wang2023Better, WRN-28-10
0.9840
0.0054
000767
0,9692
0.0129
-0.1120
0.9835
0.0049
000747
0.9727
0.0074
-0.1121
Wong2020Fast
0,9674
0.0163
-0.9001
0.9448
0.0268
-0.1281
Wu2020AAveessriial
0,9776
0.0089
-0.837
0.9577
0.0221
-0.1215
Wu2020AAveesaaiial..
0,9778
0.0077
-0.0963
0,9588
0.0158
-0.1419
Grang2019Theortticnn
0.9774
0.0132
-0.0670
0.9565
0.0277
-0.1003
7hang2019 You
0.9720
0.0135
-0.1073
0.9502
0.0247
-0.1580
7hang2020
0.9724
0.0208
-0.0225
0.9504
0.0386
-0.0312
2000emmeyyyy
0.9875
0.0035
-0.1267
0.9777
0.0068
-0.1838
26


Reviews:
[{"review_id": "qv1iQRcWTT", "reviewer": "Reviewer_fHjF", "summary": "This paper links more general attacks with question of out-of-sample performance and Knightian uncertainty. To evaluate the distributional robustness of neural networks, this paper proposes a first-order AA algorithm and its multistep version. The proposed attack algorithms include Fast Gradient Sign Method (FGSM) and Projected Gradient Descent (PGD) as special cases. Furthermore, the authors provide a new asymptotic estimate of the adversarial accuracy against distributional threat models. The bound is fast to compute and first-order accurate, offering new insights even for the pointwise AA. It also naturally yields out-of-sample performance guarantees. This paper also conducts numerical experiments on the CIFAR-10 dataset to illustrate the theoretical results.", "questions": "The proposed results are valid for small attacks and it is still questionable for the proposed approach for the practical use. Additionally, it would be more general for the proposed method to further discuss on the generalization ability of the Wasserstein-robust models.", "limitations": "This paper uses Wasserstein distributionally robust optimization (DRO) and obtain novel contributions leveraging recent insights from DRO sensitivity analysis. Yet, it would be better to clarify with more sufficient evidences. The detailed comments can be seen in the weaknesses.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a unified approach to adversarial attacks and training based on sensitivity analysis for Wasserstein DRO. This approach leveraging results from Bartl et al. (2021) is better suited for gradient-based optimization methods than duality approach adopted in most of the works to date. This paper further links the adversarial accuracy to the adversarial loss, and investigate the out-of-sample performance.\n2. This paper derives a general adversarial attack method. As a special case, this recovers the classical FGSM attack lending it a further theoretical underpinning. However, the proposed method also allows to carry out attacks under a distributional threat model which has not been done before. This paper develops certified bounds on adversarial accuracy including the classical pointwise perturbations. The bounds are first-order accurate and much faster to compute than the AutoAttack benchmark.", "weaknesses": "1. The Wasserstein distance for the adversarial robustness was usually discussed in the theoretical analysis. This paper utilizes the first order approximation of the adversarial loss on the CIFAR-10 for the verification. This approach contributes on the efficiency of the Wasserstein distributional robustness for the practical use. Yet, it is still questionable on the robustness on the large-scale dataset. Due to the computational complexity of the data dimension for the Wasserstein distance, it would be interesting to see the performance and the efficiency of the proposed approach on the image data such as tiny-ImageNet with dimension 64 and ImageNet with dimension 224.\n2. The Wasserstein distance is about the overall loss rather than the single norm such as L_2 and L_\\infty. Thus, the Wasserstein robustness may contribute to other types of robustness such as common corruptions, natural adversarial examples and the perturbations beyond the adversarial robustness. It would be more sufficient to see the potential improvement of the proposed approach on more general perturbed images.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Re **Weakness 1** - We trust your first point was addressed by our new experiments showcasing the performance on CIFAR100 and ImageNet. In fact, while we agree that the complexity of Wasserstein distance in higher dim can cause troubles, this does not happen for our methods at all due to our formulae for the first order sensitivity. This means that the approximation to the worst case Wasserstein adversarial attack is explicit and only requires us to compute the gradient $\\nabla_x J$. In consequence, the size of the image only affects the first layer of the DNN and the number of classes affects the last layer of the DNN. The computational time is thus mostly determined by the (hidden) architecture of the DNN model we consider. We hope that the performance and feasibility of our methods on these much larger datasets might turn this weakness into a new strength in your eyes. \n\nRe **Weakness 2** - Thank you for highlighting the potential of Wasserstein robustness on general perturbed images. While we focused mainly on adversarial attacks, our intended scope is indeed larger, as highlighted by the general discussion on Knightian uncertainty and the specific section on out-of-sample performance. We believe that the capacity of our methods to consider general image perturbations by viewing them as elements of an $l_2$ or $l_\\infty$ ball is a strength of the DRO approach. Notwithstanding that, there are certain limitations we should highlight:\n* a) These perturbations might be relatively large implying radius of perturbation ball outside of the linear approximation regime to which our methods are adapted.\n* b) The relevance of our bounds for some perturbation contexts might be limited. For instance, while our analysis targets worst-case adversarial scenarios, common corruptions focus on random real-world perturbations not specifically crafted to deceive neural networks. These corruptions are inherently non-adversarial, model-agnostic, and predefined. Hence, we expect model performance against such corruptions to surpass our derived bounds, limiting their insights under these scenarios. \n\nBoth a) and b) could potentially be addressed by changing the underlying metric on images and using a bespoke one instead of $l_2$ or $l_\\infty$. \nWe note that paper [C] listed by Reviewer 5QWe used a bespoke metric designed to capture if two images were distinguishable to a human eye to better describe (classical) adversarial attacks. We believe this idea could be applied in other contexts as well. \nSpecifically, to capture common corruptions, we would need to implement a metric which would measure how close one image is to being a common corruption of the other (say as defined by ImageNet-C and 3DCC). If we used this metric in defining the Wasserstein distance, common corruptions of our test dataset would all lie in a small ball around it. We could then, in principle, establish (asymptotically) certified bounds for distributional common corruption attacks, following the methodology presented in our paper. However, designing such metrics meeting the prerequisites for subsequent derivations (e.g., for our methods it needs to come from a semi-norm and we need to be able to compute its dual) is not trivial and falls outside the scope of our current work. We thank you for your suggestion and see it as a promising direction for future works. \n\nRe **Question** - the question of validity of the asymptotic regime was raised by another reviewer as well and is discussed in our general response above. As for generalisation ability, our methods can naturally provide insights (and bounds) on performance on unseen data generated from the same (or Wasserstein-close) distribution as the training data. We highlight this in the section *Bounds on out-of-sample performance* and in *Corollary 5.3* in particular. These tools apply to any models. If we understand well the last part of this question, the reviewer believes it would be interesting to investigate specifically how well Wasserstein-DRO-*trained* models perform on this criterion, and indeed compare their performance with other robust models. We empathically agree. While clearly outside the scope of the current paper, we hope to investigate this subject in a subsequent work. Indeed, in Appendix D, we suggested a natural Wasserstein-DRO-training method resulting from our insights and these will be the natural starting point for such further research.\n\nRe **Limitations** - we of course agree and have now included the empirical study of performance of our methods on two higher-dimensional datasets. The results are fully in line with those obtained on CIFAR10 and testify, we believe, to general applicability of our results."}, {"review_id": "Ko4HoicbuV", "reviewer": "Reviewer_5QWe", "summary": "The paper proposes a new method combining Wasserstein distance, DRO, and adversarial attack. The novelty is that the method computes the adversarial attack bounded by the Wasserstein distance. The paper provides a bound on the performance of out-of-domain samples. It applies the new adversarial attack on CIFAR10 dataset. The numerical results show that the attack is effective on models that are robust to pointwise attacks, and computing attacks is much faster than other methods.", "questions": "1. For the computation time in Table 2, do the authors compare with PGD? PGD is a simple gradient-based method, so the computation time should be very small. Other methods, like FGSM, are also very fast. Also, for Table 2, do all the algorithms stop when they successfully attack all the images?\n2. In line 165, the authors mention another distributional attack, why this method is not compared to in the paper?\n3. In line 39, the paper mentions the approach \"is better suited for gradient-based optimization methods than duality approach adopted in most of the works to date\". Can you clarify on this point?", "limitations": "The authors discuss some of the limitations of the work, including only valid on small-scale attacks. More limitations could include the stability of the attack and how it compares to more state-of-the-art attack methods. The method also should be compared with more attack methods, like DRO-based attacks. From the current experiments, it is not very convincing that the method outperforms many other adversarial attack methods.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposes an interesting direction by combining DRO and adversarial attacks. It is clear in the writing and presenting methods.\n2. The paper gives some theoretical results on the proposed methods, like lower bound on $R_{\\delta}$. The paper also shows numerical results comparing the lower bound from different methods.\n3. The paper provides numerical results to show that the adversarial attack is effective at attacking and fast to compute.", "weaknesses": "1. The paper misses some references and does not compare the method with the existing DRO adversarial attack methods, like [A].\n[B, C] also have a similar approach by combining DRO with adversarial attacks. In the area of traditional attacks, the paper can compare with more methods, like CW attack in [D].\n\n[A] Sinha, A., Namkoong, H., Volpi, R. and Duchi, J., 2017. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv:1710.10571.\n[B] Volpi, R., Namkoong, H., Sener, O., Duchi, J.C., Murino, V. and Savarese, S., 2018. Generalizing to unseen domains via adversarial data augmentation. Advances in neural information processing systems, 31.\n[C] Hua, X., Xu, H., Blanchet, J. and Nguyen, V.A., 2022, December. Human imperceptible attacks and applications to improve fairness. In 2022 Winter Simulation Conference (WSC) (pp. 2641-2652). IEEE.\n[D] Carlini, N. and Wagner, D., 2017, May. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp) (pp. 39-57). Ieee.\n\n2. The paper only does experiments on CIFAR10 dataset. It would be helpful to see results on other datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions which raise important points. While you thought our writing and presentation were clear, your questions allowed us to understand where we could have explained the key insights and contributions better, for which we are particularly grateful. We stride in this rebuttal to answer all your questions as well as to provide these additional clarifications. \n\nRe **Weakness 1** - thank you for mentioning these reference. [A] was a major pioneering work on distributional robustness which we cite, see lines 36, 70, 89, 158 for details. arXiv hosts 5 versions of the work, all with the same title, the first 4 have three authors whilst the newest 2020 version has R. Volpi added as a co-author. We felt it was best to cite the 2018 ICLR version of this work but we are happy to adjust the citation if required. More importantly, a comparison with all of the suggested papers is not straightforward as our focus is different. We discuss this in the global rebuttal above and argue that using AutoAttack is a better benchmark. These comments apply to comparison with [D] which developed the CW attack (please note also that this work was cited in our paper at line 55). Nevertheless, a reverse-engineered comparison is presented in Rebuttal to Reviewer 1Lzk.\n\nBoth [B] and [C] utilize duality of DRO to conduct distributional adversarial attack with emphasis on the performance of neural networks on unseen distribution and  the human imperceptible attacks respectively. We are grateful for pointing these new references to us and we will  cite them as related works. However, neither of them show their attacks can attain or approximate the adversarial distribution within the given budget. In fact, their proposed algorithms amount to the DRO problem with a penalization term. Let us consider this in detail as it also answers **Question 3**. In [C], the W-DRO training is re-written using duality in equation (3). This requires a minimization over the Lagrangian $\\lambda$. However, in their attack method [C] fixes $\\lambda$ and simply uses a gradient descent on (4), see line 7 in their Algorithm 1. While their choice of $\\lambda=1$ may be optimal for *some* budget $\\delta$ there is no way to perform an optimal attack for a *given* budget $\\delta$. Similarly, [B] change the W-DRO problem to (4) and perform a SGD on the surrogate loss $\\phi_\\gamma$ in (5).\nWe believe, the same weakness applies to all methods using duality to re-write the W-DRO objective, e.g., Sinha et al. '18 (see ref at line 415), use duality in Prop. 5 but in Algorithm 1 a fixed $\\gamma$ is used. In contrast, our one-step attack is an explicit first-order approximation to the optimal attack for a *given* budget $\\delta$ and only involves $\\nabla_x J$ and its norms which are fast to compute using standard methods. Note that the first step of (11) does *not* require any projection. That is only needed for multiple step version of the attack but can be done efficiently, see Appendix C for details. \n\nWe hope our discussion clarifies the relation of our contribution to the SOTA in the field, and how our sensitivity approach leading to a first order approximation of the adversarial distribution is well-suited to gradient-based methods. We look forward to further discussion with you and hope to turn this weakness into a strength in your eyes. \n\nRe **Weakness 2** - we have now included the empirical study of performance of our methods on two other datasets: CIFAR100 and ImageNet, see the global rebuttal above. The results are fully in line with those obtained on CIFAR10 and testify, we believe, to general applicability of our methods.\n\nRe **Question 1** - In Table 2 we compare the computational time of the true robustness metric $\\mathcal R_{\\delta}$ \nestimated using AutoAttack with the the computational time of our bounds. AutoAttack will stop if an image has been successfully attacked.\nBoth bounds $\\mathcal R^{l}$ and $\\mathcal R^{u}$ have the same order of computation time as the FGSM attack since they are both gradient-based. As discussed above, we used AutoAttack as the benchmark as we are interested in estimating $\\mathcal R_{\\delta}$ as well as we can to illustrate the performance of our bounds. We did not compare with other attack methods here on their own. We can roughly view a PGD(50) attack as 50 times more expensive than the FGSM attack or than our bounds. \n\nRe **Question 2** - Staib and Jegelka '17 (:=[E]) is one of the earliest works considering adversarial attack under DRO framework. We believe, they introduced the *distributional* threat model and we cite them accordingly. However, they concentrate on adversarial training in the context of *pointwise* threat models, with limited consideration for distributional attacks. In fact, ReDLR loss and sensitivity of DRO are two key ingredients proposed in our manuscript which lead to effective distributional attacks. Indeed, we believe our paper is the first to design and perform AA to a given distributional budget. Our Table 1 offers an empirical validation of the claim in [E] about the relative strengths of the attacks. In addition, we believe our proposed W-PGD attacks can be potentially used for distributional adversarial training. This is mentioned in Appendix D but, but is an important project left for future research. Such a new training could be then meaningfully compared with the network trained in [E].\n\nRe **Question 3** - we addressed this above.\n\nRe **Limitations** - see above, the global rebuttal and our response to the last question of Reviewer 1Lzk. We stress that our aim is *not* to outperform an existing AA method and that a direct comparison is not meaningful as, to the best of our knowledge, no other attack method for a distributional threat with a given budget has been proposed in the literature. However, even for *pointwise* threat models, our contribution offers very efficient bounds on robustness and AutoAttack represent a SOTA benchmark."}, {"review_id": "qab0kIhRbo", "reviewer": "Reviewer_Q9Xf", "summary": "The paper focuses on the issue of distributional robustness in deep neural networks and introduces a novel approach to address it. The authors present a tractable distributional attack within a Wasserstein ball, which allows attackers to perturb inputs in a non-uniform manner. They propose a first-order approximation of the problem and introduce a new loss function called ReDLR. This framework encompasses the Fast Gradient Sign Method (FGSM) attack as a special case. The authors also provide tractable bounds for adversarial accuracy against distributional threat models, which offer insights even for pointwise attacks. To validate their approach, experiments are conducted on the CIFAR-10 dataset using state-of-the-art deep neural networks on RobustBench, demonstrating the effectiveness of the attack and the tightness of the bounds.", "questions": "The paper demonstrates strong mathematical foundations and is very well written with a very accurate state of the art. The contributions, particularly the formation of a tractable framework for Wasserstein Distributionally Robust Optimization (WDRO) with asymptotic guarantees, are significant.\n\nHowever, certain concerns arise:\n\n-The proposed attack and adversarial accuracy boundaries heavily rely on the validity of the first-order approximation. Therefore, one query would be how the first-order estimation scales with the dimension of the input space. Specifically, does this approach retain its efficacy when applied to larger vision problems, such as those found in ImageNet (224x224x3)?\n\n-The use of the term 'certified bound' seems somewhat misleading as it actually refers to an asymptotic result. The proposed bounds, as they currently stand, cannot provide certification for a given radius (even a small one) as depicted in appendix Figure E1. Furthermore, the lower bound appears to be loose in the experiments. The approach proposed in the appendix to tighten the bound sometimes leads to overestimation, rendering it unsuitable for certification without additional guarantees. Therefore, how could this issue be addressed for a more accurate and reliable certification?\n\n", "limitations": "The authors adequately addressed the limitations", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "\nThe strengths of the paper are:\n\n-The introduction of a tractable attack for Wasserstein Distributionally Robust Optimization (WDRO) stands as a significant contribution, as does the adversarial accuracy boundary. Both offer key advancements to the current understanding and applications of deep learning models under adversarial conditions.\n\n-The paper is underpinned by robust mathematical foundations, and its place in relation to the existing body of work in the field is clearly and precisely articulated, demonstrating a deep and accurate understanding of the state-of-the-art.\n", "weaknesses": "-The guarantees provided in the paper are asymptotic in nature and depend on the quality of the first-order approximation of the problem. This introduces some limitations and potential uncertainty in the practical applicability of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your praise of our contribution. In particular, your comments that our results offer \"key advancements to the current understanding and applications of deep learning models under adversarial conditions\" as well as demonstrating \"a deep and accurate understanding of the state-of-the-art\" were truly rewarding to read. We answer below your questions and look forward to any further discussion. \n\nRe **Weaknesses** - we agree, this is true for any methods relying on a first-order approximation. We acknowledged this further in the global response above. We believe the empirical results testify to practical relevance of our methods and we also suggest how combining our W-DRO attack with different number of steps could offer a practical way to assess the regime of applicability.\n\nRe **First Question** - we present now the empirical evidence on ImageNet. For *pointwise* threat our bounds are still very tight and perform similarly to the lower dimensional dataset CIFAR10. The computational times are likewise hundreds of times quicker than AutoAttack (note that AutoAttack is slower when the images are harder to attack and it has to deploy secondary attacks which likely explains why its on average slower for CIFAR-10 than for CIFAR-100). \nHowever, for the *distributional* threat the lower bound performs markably worse. We attribute this to more pronounced concavity of $V(\\delta)$. Here, we see that performing 5 steps W-PGD-ReDLR attack offers a significant improvement on the one-step lower bound.\n\nRe **Second Question** - Thank you for this interesting question. We agree that *asymptotically certified bounds* might be a more appropriate term. \nWe point out that in other contexts one also obtains certified bounds which might sometimes fail. For example, L. Li, T. Xie, and B. Li '23 (see line 326) or J. Cohen, E. Rosenfeld, and Z. Kolter '19 (line 340)  both derive *probabilistic certified robustness bounds* obtained from random smoothing. Those bounds only hold with a certain confidence. However the smoothing distribution is tuned, there exists a small probability that the derived certified bounds violate the truth. Even for small $\\delta$ our methods incur an $o(\\delta)$ error which could, in principle, lead to violations even if we have not seen these in our results on the three datasets. \n\nWhile most $\\delta=8/255$ attacks may be imperceptible to human eyes, for us it does not count as a small-$\\delta$ attack. In Figure 1, we plot the performance of the first order approximation for the W-DRO value. With delta=8/255, we see a roughly 20\\% relative error and this means that, in practice, our bounds need to be improved at this level. This can be done using a W-PGD(n)-CE attack to better approximate the W-DRO value function and derive a tighter bound. We discussed this approach in some detail already in the related point in our global rebuttal. The approach offers a tradeoff between computational intensity and quality of the lower bound and was illustrated in Figure E.2. In addition we also applied it now to CIFAR-10 at $\\delta=8/255$ to amend Figure E.1 and show the improved lower bounds using 5 iterations of PGD ($n=5$). We also carried out the approximation for $n=10$ and the change is negligible giving us confidence that using $\\mathcal R^l(5)$ is justified.\n\nWe acknowledge the approach outlined above is a practical answer offering a rule of thumb solution. A more comprehensive theoretical investigation would be challenging. One avenue would be to try to derive a second-order sensitivity for W-DRO problem and use it to bound the error of the first-order approximation. This would likely involve much stronger assumptions, in particular controlling the second derivatives, similarly to, e.g., Sinha et al. '18 (line 415) who assume the gradient of the loss function is $L$-Lipschitz. Another possibility would be to use duality approach combined with strong assumptions to control the convexity/concavity of the W-DRO function. Both directions appear to be in interesting but challenging and remain outside of the scope of the present study."}, {"review_id": "ZpfPlrNzew", "reviewer": "Reviewer_1Lzk", "summary": "This paper presents a novel adversarial attack methodology premised on Wasserstein distributionally robust optimization. This approach serves as a generalized technique that encompasses many established adversarial attack methods such as FGSM and TRADES. To ensure computational tractability, the authors introduce a first-order approximation of the attack loss. This approximation is particularly suited for gradient-based optimization methodologies, offering a much faster computational speed compared to SOTA techniques such as AutoAttack. Theoretical evidence is provided for certified bounds on adversarial accuracy and out-of-sample performance. Experiments on the CIFAR-10 dataset are conducted to demonstrate the effectiveness of the proposed method.", "questions": "- I personally found the intuition stated in line 171-173 is quite important to understand the method and should be further stressed, both in the introduction and the earlier subsections of the method. \n\n- S^c seems to first appeare in line 215, but no clear definition is provided. \n\n- How strong is Assumption 4.1? Though intuitively for classification problems it should be held, it would be great if the authors provide some experimental analysis (with several commonly used NNs), or pinpoint some references.", "limitations": "See Weakness and Questions.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ The proposed ReDLR loss (10) is both simple and effective. It is built on clear intuition, that the attack should perturb images classified far from the decision boundary more aggressively while leaving misclassified images unchanged. The theoretical analysis and guarantees provided further validate the proposed approach.\n\n+ The method is presented using robust proofs and in-depth analysis. I didn't notice any substantial unjustifiable assumptions or logical inaccuracies. The section on \"Bounds on Out-of-Sample Performance\" is particularly intriguing. Despite substantial parts of the proof being left in the appendix due to page limits, the analysis still provides invaluable insights for future research on empirical distributions of test sets and broader applications of Wasserstein balls.\n\n+ The empirical results demonstrate notable improvements over robust baseline methods like DLR. It is worth noting that while the proposed ReDLR method may appear very similar to DLR at first glance, the empirical results show significant improvements, attesting to the effectiveness of the theoretical analysis.\n\n+ The paper is well-structured and clearly written. Even the first part of the method section could serve as a comprehensive introduction to DLR-based methods, making it approachable and comprehensible even for novices in the field.", "weaknesses": "- One weakness of the paper is that the number of experiments provided is limited (only results on CIFAR-10 with a limited number of baselines compared). However, considering the major contribution of the paper is to provide a comprehensive theoretical analysis and the existing results already demonstrate the effectiveness of the method, I would say the weakness of experiments does not affect the overall quality of the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and praise. This is much appreciated. Thank you in particular, for emphasising our contributions in introducing the ReDLR loss function and results in the \"Bounds on Out-of-Sample Performance\" section which, while important, we were not able to stress appropriately ourselves. Your comment that \"the analysis still provides invaluable insights for future research\" was hugely rewarding to read. We answer below your questions and look forward to any further discussion.\n\nRe **Weaknesses** - thank you for your understanding. We were focused on delivering a theoretically complete paper with proper empirical illustration of the performance of our methods but we did not have time, nor space to be honest, to present a comprehensive analysis on multiple datasets. We have now addressed this and included, see our global rebuttal above, results for CIFAR-100 and ImageNet. Both showcase the effectiveness of our methods. \n\nYou mention also a limited number of baselines compared. This relates to comments made by other reviewers who asked us to benchmark our attack against other attacks. We argue above, in the global rebuttal, against a direct comparison with papers focusing on AA methods and for using the AutoAttack benchmark instead. Nevertheless, we can reverse engineer a comparison setup ex-post. We do this for the CW attack proposed in paper [D] (see report 5QWe) as this was also requested by Reviewer 5QWe. Specifically, Table V in paper [D] reports the average budget needed for a successful attack (for Inception v3 on a subset of ImageNet) under $l_2$ and $l_\\infty$ metrics. These averages can be thus seen as an upper bound on the $\\mathcal W_1$ distance. We re-did their computationsusing the first 1000 correctly classified images from the ImageNet subset used by RobustBench. We obtained an average budget of $0.00617$ which agrees with their reported average of $0.006$ in Table V in [D]. We then computed the average of the squares which provides an upper bound on the $\\mathcal W_2$ distance *squared*, and taking the square root gave us a budget of $0.00711$ to perform a distributional $(\\mathcal W_2,l_\\infty)$ attack. We used our proposed W-PGD(50)-ReDLR method. This resulted in 934 images being successfully attacked out of the 1000. The CW attack took ca 4.5h to run (on a Tesla V100-SXM2-32GB-LS GPU) and the time needed scaled *linearly* with the number of images as the attack has to be performed image by image (but with a very large variance of time per image). In contrast, our attack took ca 50min to run (on a NVIDIA A100-SXM4-40GB GPU). In addition, we use mini-batches so the computational speed can be improved in function of the GPU's available memory. \n\nRe **First Question** - thank you. We agree this needs to be stressed earlier on and more clearly. We will make this change.\n\nRe **Second Question** - thank you. We will introduce the notation for the complement of an event earlier on.\n\nRe **Third Question** - thank you for raising this. A discussion, even if brief, of this assumption should have been included. We provide details here and will add a short comment to the paper. We believe this is a reasonable assumption. First, it is an order of magnitude weaker than the $L$-smoothness assumption often made in the related literature see, e.g., Assumption B in Sinha et al. '18 (line 415) which requires the gradients $\\nabla_x J$, $\\nabla_\\theta J$ to be $L$-Lipschitz in both $x$ and in $\\theta$, see also Assumption 1 in Sridhar et al. '21 (arXiv:2106.02078) and the discussion therein, as well as references [24]-[27] therein, or Assumptions 1 and 2 in paper [B] listed by Reviewer 5QWe. In fact, in this Assumption 2 the authors in [B] required the $l_2$ operator norm of the Hessian of the loss function to be $L$-Lipschitz. Second, as $x\\in [0,1]^n$ which is a compact, we note that any continuously differentiable function will be automatically Lipschitz. \n\nWe note also that understanding the regularity of the gradient $\\nabla_x J$ not only helps with checking Assumption 4.1 holds but also with answering other questions. One such question, raised by Reviewer 5QWe, is stability of our attack. Our one-step attack is given via an explicit formula, which involves the gradient and the reciprocal of $\\Upsilon$, which in turn is an expected norm of the gradient over the test dataset. Stability of the attack will thus largely reduce to control on the smoothness of the gradient.  \n\nOf course, in practice, we not only want Assumption 4.1 to hold but we also want the constant $L$ to be reasonable and known. Or more broadly we want to have a concrete handle of the smoothness of the gradient. This is more challenging, especially if we deal with a large dimensional model trained using many additional tricks and procedures. Here to our help comes a body of literature exploring empirically the loss landscape for trained networks and the impact of various training features on this landscape. We mention Li et al. '17 (arXiv:1712.09913) or Chromanska et al. '15 (arXiv:1412.0233) among the seminal papers. Applying this techniques to assess specifically the validity of Assumption 4.1 on particular trained models remains outside the focus of our paper.  \n\n"}]

Author rebuttal:
We are deeply grateful to all the reviewers for their comments and questions. We were pleased to hear the reviewers felt our paper was well structured and clearly presented. It was rewarding to see all the reviewers list numerous strengths of our work and very interesting that their emphasis was different, testifying to the multi-faceted nature of our contribution. You felt we offered ''key advancements to the current understanding and applications of deep learning models under adversarial conditions'' and provided ''invaluable insights for future research''. This is exciting to hear. Equally, your questions were often eye-opening for us, thank you. We address some of them here and the rest in the individual replies. We look forward to discussing these with you.

**Performance of our methods on other datasets and in higher dimensions**. 
The reviewers requested to see the performance of our methods on a higher-dimensional dataset. In the attached PDF, we illustrate the performance on CIFAR-100 and ImageNet datasets. We analyse all the models included on RobustBench leaderboards. For ImageNet, we use the 5000 images selected by RobustBench. The plots and the table mirror those for CIFAR-10 in our submission. For pointwise threat models, our upper and lower bounds sandwich the true (AutoAttack) accuracy ratio very well at a fraction of the computational cost. For distributional threat models, our bounds work but the tightness of the bound is model-dependent. We display also the improved bound obtained with 5 steps of W-PGD attack which leads to a marked improvement in the lower bound's performance. This is akin to Figure E.2 in our supplementary material (aka Appendix). We only consider the $l_\infty$ norm on images as RobustBench does not provide any models for $l_2$ for these higher-dim datasets.

**Asymptotic character of our results and their validity regime**.
To draw a parallel with calculus: linear approximations to a function offer countless applications, indeed are the basis of any gradient descent method, but are typically only useful locally and have to be handled with care. Similarly, we believe that our methods bring new powerful insights to the W-DRO robustness of NN. This was recognised in many of the reviewers' comments. Equally, the methods have their limitations which we acknowledge. We believe that the empirical results we presented from all the leaderboard models on RobustBench across CIFAR-10, CIFAR-100 and ImageNet and across different attack types provide an overwhelming evidence that our results are valid and relevant for the range of attack budget $\delta$ considered in AA settings. However, we do not have theoretical results to provide guarantees on the range of applicability. 

In practice, we would compare our one-step-attack bound $\mathcal R^l$ with the bound obtained by iterating the attack several steps: we propose W-PGD(5) in our paper and report $\mathcal R^l(5)$. If the difference between the two is small it indicates linear approximation is working very well. If the difference is significant, we would use $\mathcal R^l(5)$ and maybe compare it against $\mathcal R^l(10)$. If we observe that $V(\delta)$ is convex - as for the CE loss under $(\mathcal W_\infty, l_\infty)$ attack - the lower bound should decrease. In this case, the one-step bound may in fact not be a lower bound for $\delta$ too large as shown in Figure E.1 in the Appendix. If we observe $V(\delta)$ is concave - as for the ReDLR loss and our $\mathcal W_2$ attacks - the one-step lower bound might be too low and will increase with additional PGD steps. This is visible in Figure E.2 and in the attached PDF for CIFAR-100 and ImageNet results, and for CIFAR-10 with $\delta=8/255$.

**Comparison with existing adversarial attack (AA) methods and the advantages of our approach**. The focus of our contribution is different to many previous works proposing an adversarial attack (AA) method. The latter often focuses on reporting the minimal budget needed for a successful attack - the methods are designed to continue attacking until successful and report the distortion level they required. In contrast, we are interested in fixing the attack budget upfront and computing (and doing so fast) how robust a given network is to attacks within that budget. This makes a comparison difficult as the purpose is different. Nevertheless, a reversed-engineered comparison is included in Rebuttal to Reviewer 1Lzk below.

This difficulty is solved by taking AutoAttack as a reference *pointwise* attack method as it works to a specified attack budget. 
Hence, we argue that for *pointwise* threat models it suffices to compare with AutoAttack and we use it for canonical deltas on RobustBench. AutoAttack is an ensemble of white-box and black-box attacks including Auto-PGD based on CE loss and DLR loss. In Corce 20 [Section 4.2], the authors claim that DLR loss is more stable than CW loss with less severe failure of attacks. We thus feel that using AutoAttack, if indirectly, includes a comparison to the CW attack which hopefully answers Reviewer 5QWe's point. 
We emphasize that the aim of our paper is to open the window of Wasserstein distributional attack and to provide computationally efficient generic way to compute bounds on robustness. Our focus is not to outperform specific existing adversarial attacks for *pointwise* threat models. 

W-DRO formulation has been explored in a number of works, as discussed. However, we believe, none of them proposed an AA method for the associated distributional threat and a *given* attack budget. Hence there is no direct competition for us to compare against. This highlights the strength of our approach using sensitivity analysis as contrasted with dual formulation exploited in the earlier works. We discuss this in more detail in our rebuttal to Reviewer 5QWe below. This point was also stressed by Reviewer 1LzK who also asked us to emphasise this more clearly, which we will do. 

Meta-review: The paper presents a new approach by integrating Distributionally Robust Optimization (DRO) with adversarial attacks, significantly enhancing the field's understanding of neural network robustness. By introducing a first-order Adversarial Attack (AA) algorithm, the authors not only encompass existing methods like FGSM and PGD but also offer new insights into distributional threat models. The paper's strength lies in its solid theoretical underpinning and the introduction of first-order accurate bounds on adversarial accuracy, validated by numerical experiments on the CIFAR-10 dataset. This work efficiently bridges the gap between adversarial attacks and out-of-sample performance, and is especially noteworthy for its fast computation relative to existing benchmarks. Given these merits, I recommend accept.
Decision: Accept (poster)