Wasserstein distributional robustness of neural networks
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 multi-step 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 the CIFAR-10
dataset using DNNs on RobustBench to illustrate our theoretical results. Our
code is available at https://github.com/JanObloj/W-DRO-Adversarial-Methods.
Xingjian Bai, Guangyi He, Yifan Jiang, Jan Obloj
# Wasserstein distributional robustness of neural networks

###### 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 multi-step 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 the CIFAR-10 dataset using DNNs on RobustBench to illustrate our theoretical results. Our code is available at [https://github.com/JanObloj/W-DRO-Adversarial-Methods](https://github.com/JanObloj/W-DRO-Adversarial-Methods).

## 1 Introduction

Model uncertainty is an ubiquitous phenomenon across different fields of science. In decision theory and economics, it is often referred to as the _Knightian uncertainty_(Knight, 1921), or the _unknowns_, to 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 in a training by design, e.g., through random initialization, drop-outs etc., and uncertainty encompasses the extent to which the dataset is 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
out-of-distribution performance. In this work, we mainly focus on the former but offer a unified perspective on robustness in all of its facets.

Vulnerability of DNNs to crafted adversarial attacks (AA), diagnosed in Biggio et al. (2013), Goodfellow et al. (2015), relates to the ability of an 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_\(l_{p}\)-bounded image distortions but a growing stream of research, pioneered by Staib and Jegelka (2017) and Sinha et 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 gradient-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 a special case, this recovers the classical FGSM attack lending it a further theoretical underpinning. However, our method also allows to carry out attacks under a _distributional threat model_ which, we believe, has not been done before. **3)** We develop 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 dataset (Krizhevsky, 2009) and neural networks from RobustBench (Croce et al., 2021).

## 2 Related Work

Adversarial Attack (AA).Original research focused on the _pointwise_\(l_{p}\)-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), 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-limited Attack (Ilyas et al., 2018). AutoAttack (Croce and Hein, 2020), an ensemble of white-box and black-box attacks, provides a useful benchmark for _pointwise_\(l_{p}\)-robustness of neural networks.

Adversarial Defense.Early works on data augmentation (Goodfellow et al., 2015; Madry et al., 2018; Tramer 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 as GANs and diffusion models. Zhang et al. (2019) consider the trade-off between robustness and accuracy of a neural network via TRADES, a 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 group-out layers, early stopping and parameter fine-tuning Sehwag et al. (2020). The closest to our setting are Sinha et al. (2018), Garcia Trillos and Garcia Trillos (2022) which employ Wasserstein penalization and constraint respectively.

Robust Performance Bounds.Each AA method gives a particular upper bound on the adversarial accuracy of the network. In contrast, research on _certified robustness_ 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-the-shelf solvers (Tjeng et al., 2019), relaxed linear programming (Wong and Kolter, 2018; Weng et al., 2018) or semi-definite programming (Raghunathan et al., 2018; Dathathri et al., 2020) have been applied. Hein and Andriushchenko (2017), Weng et al. (2018) derive Lipschitz-based metrics to characterize the maximum distortion an image can uphold; Cohen et al. (2019) constructs a certifiable classifier by adding smooth noise to the original classifier; see Li et al. (2023) for a review.
Distributionally Robust Optimization (DRO).Mathematically, it is formulated as a min-max problem

\[\inf_{\theta\in\Theta}\sup_{Q\in\mathscr{P}}\mathbf{E}_{Q}[f_{\theta}(Z)], \tag{1}\]

where we minimize the worst-case loss over all possible distributions \(Q\in\mathscr{P}\). In financial economics, such criteria appear in the context of multi-prior preferences, see (Gilboa and Schmeidler, 1989; Follmer and Weber, 2015). We refer to (Rahimian and Mehrotra, 2019) for a survey of the DRO.

We focus on the Wasserstein ambiguity set \(\mathscr{P}=B_{\delta}(P)\), which is a ball centered at the reference distribution \(P\) with radius \(\delta\) under the Wasserstein distance. We refer to Gao and Kleywegt (2022) for a discussion of many advantages of this distance. In particular, measures close to each other can have different supports which is key in capturing data perturbations, see Sinha et al. (2018). Staib and Jegelka (2017) interpreted _pointwise_ adversarial training as a special case of Wasserstein DRO (W-DRO). More recently, Bui et 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) into a max-min problem where the inner minimization is a more tractable univariate problem. 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 et 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), Garcia Trillos and Garcia Trillos (2022) for analogous results in different setups.

## 3 Preliminaries

Image Classification Task.An image is interpreted as a tuple \((x,y)\) where the feature vector \(x\in\mathcal{X}\) encodes the graphic information and \(y\in\mathcal{Y}=\{1,\ldots,m\}\) denotes the class, or tag, of the image. W.l.o.g., we take \(\mathcal{X}=[0,1]\)2. A distribution of labelled images corresponds to a probability measure \(P\) on \(\mathcal{X}\times\mathcal{Y}\). We are given the training set \(\mathcal{D}_{tr}\) and the test set \(\mathcal{D}_{tt}\), subsets of \(\mathcal{X}\times\mathcal{Y}\), i.i.d. sampled from \(P\). We denote \(\widehat{P}\) (resp. \(\widetilde{P}\)) the empirical measure of points in the training set (resp. test set), i.e., \(\widehat{P}=\frac{1}{|\mathcal{D}_{tr}|}\sum_{(x,y)\in\mathcal{D}_{tr}} \delta_{(x,y)}\). A neural network is a map \(f_{\theta}:\mathcal{X}\rightarrow\mathbb{R}^{m}\)

Footnote 2: In practice, \(P\) is not accessible and we use \(\widehat{P}\) or \(\widetilde{P}\) instead, e.g., in (2) we replace \(P\) with \(\widehat{P}\) and then compute the clean accuracy as \(\widehat{P}(S)\). In our experiments we make it clear which dataset is used.

\[f_{\theta}(x)=f^{l}\circ\cdots\circ f^{1}(x),\qquad\text{where }f^{i}(x)= \sigma(w^{i}x+b^{i}),\]

\(\sigma\) is a nonlinear activation function, and \(\theta=\{w^{i},b^{i}:1\leq i\leq l\}\) is the collection of parameters. We denote \(S\) the set of images equipped with their labels generated by \(f_{\theta}\), i.e.,

\[S=\Big{\{}(x,y)\in\mathcal{X}\times\mathcal{Y}:\arg\max_{1\leq i\leq m}f_{ \theta}(x)_{i}=\{y\}\Big{\}}.\]

The aim of image classification is to find a network \(f_{\theta}\) with high (clean) prediction accuracy \(A:=P(S)=\mathbf{E}_{P}[\![1_{S}]\). To this end, \(f_{\theta}\) is trained solving3 the stochastic optimization problem

Footnote 3: By convention, cross entropy is a function of two probability measures. In this case, we implicitly normalize the logit \(z\) by applying \(\,\mathrm{softmax}\), and we associate a class \(y\) with the Dirac measure \(\delta_{y}\).

\[\inf_{\theta\in\Theta}\mathbf{E}_{P}[L(f_{\theta}(x),y)], \tag{2}\]

where \(\Theta\) denotes the set of admissible parameters, and \(L\) is a (piecewise) smooth loss function, e.g., cross entropy loss\({}^{3}\mathrm{CE}:\mathbb{R}^{m}\times\mathcal{Y}\rightarrow\mathbb{R}\) given by

\[\mathrm{CE}(z,y)=-(\log\circ\,\mathrm{softmax}(z))_{y}. \tag{3}\]

Wasserstein Distances.Throughout, \((p,q)\) is a pair of conjugate indices, \(1/p+1/q=1\), with \(1\leq p\leq\infty\). We consider a norm \(\|\cdot\|\) on \(\mathcal{X}\) and denote \(\|\cdot\|_{\bullet}\) its dual, \(\|\tilde{x}\|_{\bullet}=\sup\{\langle x,\tilde{x}\rangle:\|x\|\leq 1\}\). Our main interest is in \(\|\cdot\|=\|\cdot\|_{r}\) the \(l_{r}\)-norm for which \(\|\cdot\|_{\bullet}=\|\cdot\|_{s}\), where \((r,s)\) are conjugate
indices, \(1\leqslant r\leqslant\infty\). We consider adversarial attacks which perturb the image feature \(x\) but not its label \(y\). Accordingly, we define a pseudo distance4\(d\) on \(\mathcal{X}\times\mathcal{Y}\) as

Footnote 4: Our results can be adapted to regression tasks where the class label \(y\) is continuous and sensitive to the perturbation. In such a setting a different \(d\) would be appropriate.

\[d((x_{1},y_{1}),(x_{2},y_{2}))=\|x_{1}-x_{2}\|+\infty\mathbb{1}_{\{y_{1}\neq y _{2}\}}. \tag{4}\]

We denote \(\Pi(P,Q)\) the set of couplings between \((x,y)\) and \((x^{\prime},y^{\prime})\) whose first margin is \(P\) and second margin is \(Q\), and \(T_{\#}P:=P\circ T^{-1}\) denotes the pushforward measure of \(P\) under a map \(T\).

The \(p\)-Wasserstein distance, \(1\leqslant p<\infty\), between probability measures \(P\) and \(Q\) on \(\mathcal{X}\times\mathcal{Y}\) is

\[\mathcal{W}_{p}(P,Q):=\inf\left\{\mathbf{E}_{\pi}[d((x_{1},y_{1}),(x_{2},y_{2 }))^{p}]:\pi\in\Pi(P,Q)\right\}^{1/p}. \tag{5}\]

The \(\infty\)-Wasserstein distance \(\mathcal{W}_{\infty}\) is given by

\[\mathcal{W}_{\infty}(P,Q):=\inf\{\pi\text{--}\mathrm{ess}\;\sup d((x_{1},y_{1 }),(x_{2},y_{2})):\pi\in\Pi(P,Q)\}. \tag{6}\]

We denote the \(p\)-Wasserstein ball centered at \(P\) with radius \(\delta\) by \(B_{\delta}(P)\). We mainly consider the cases where \(p,r\in\{2,\infty\}\). Intuitively, we can view \(p\) as the index of image-wise flexibility and \(r\) as the index of pixel-wise flexibility. Unless \(p=1\) is explicitly allowed, \(p>1\) in what follows.

## 4 Wasserstein Distributional Robustness: adversarial attacks and training

W-DRO Formulation.The Wasserstein DRO (W-DRO) formulation of a DNN training task is given by:

\[\inf_{\theta\in\Theta}\sup_{Q\in B_{\delta}(P)}\mathbf{E}_{Q}[L(f_{\theta}(x),y)], \tag{7}\]

where \(B_{\delta}(P)\) is the \(p\)-Wasserstein ball centered at \(P\) and \(\delta\) denotes the budget of the adversarial attack. In practice, \(P\) is not accessible and is replaced with \(\widehat{P}\). When \(p=\infty\), the above adversarial loss coincides with the pointwise adversarial loss of Madry et al. (2018) given by

\[\inf_{\theta\in\Theta}\mathbf{E}_{P}[\sup\{L(f_{\theta}(x^{\prime}),y):\|x^{ \prime}-x\|\leqslant\delta\}].\]

Recently, Bui et 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_{\theta\in\Theta}\sup_{\pi\in\Pi_{\delta}(P,\cdot)}\mathbf{E}_{\pi}[J_{ \theta}(x,y,x^{\prime},y^{\prime})], \tag{8}\]

where \(\Pi_{\delta}(P,\cdot)\) is the set of couplings between \((x,y)\) and \((x^{\prime},y^{\prime})\) whose first margin is \(P\) and the second margin is within a Wasserstein \(\delta\)-ball centered at \(P\). This formulation was motivated by the observation that for \(p=\infty\), taking \(J_{\theta}(x,y,x^{\prime},y^{\prime})=L(f_{\theta}(x),y)+\beta L(f_{\theta}(x),f_{\theta}(x^{\prime}))\), it retrieves the TRADES loss of (Zhang et al., 2019) given by

\[\inf_{\theta\in\Theta}\mathbf{E}_{P}\Big{[}L(f_{\theta}(x),y)+\beta\sup_{x^{ \prime}:|x-x^{\prime}|\leqslant\delta}L(f_{\theta}(x),f_{\theta}(x^{\prime})) \Big{]}.\]

W-DRO Sensitivity.In practice, training using (7), let alone (8), is computationally infeasible. To back propagate \(\theta\) it is essential to understand the inner maximization problem denoted by

\[V(\delta)=\sup_{Q\in B_{\delta}(P)}\mathbf{E}_{Q}[J_{\theta}(x,y)],\]

where we write \(J_{\theta}(x,y)=L(f_{\theta}(x),y)\). One can view the adversarial loss \(V(\delta)\) as a certain regularization of the vanilla loss. Though we are not able to compute the exact value of \(V(\delta)\) for neural networks with sufficient expressivity, DRO sensitivity analysis results allow us to derive a numerical approximation to \(V(\delta)\) and further apply gradient-based optimization methods. This is the main novelty of our approach -- previous works considering a W-DRO formulation mostly relied on duality results in the spirit of Blanchet and Murthy (2019) to rewrite (7).

**Assumption 4.1**.: We assume the map \((x,y)\mapsto J_{\theta}(x,y)\) is \(L\)-Lipschitz under \(d\), i.e.,

\[|J_{\theta}(x_{1},y_{1})-J_{\theta}(x_{2},y_{2})|\leqslant Ld((x_{1},y_{1}),(x _{2},y_{2})).\]
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:_

1. \(V(\delta)=V(0)+\delta\Upsilon+o(\delta),\) _where_ \[\Upsilon=\Big{(}\mathbf{E}_{P}|\nabla_{x}J_{\theta}(x,y)\|_{\star}^{q}\Big{)}^ {1/q}.\]
2. \(V(\delta)=\mathbf{E}_{Q_{\delta}}[J_{\theta}(x,y)]+o(\delta),\) _where_ \[Q_{\delta}=\Big{[}(x,y)\mapsto\big{(}x+\delta h(\nabla_{x}J_{\theta}(x,y)) \|\Upsilon^{-1}\nabla_{x}J_{\theta}(x,y)\|_{\star}^{q-1},y)\Big{]}_{\#}P,\] _and_ \(h\) _is uniquely determined by_ \(\langle h(x),x\rangle=\|x\|_{\star}\)_._

The above holds for any probability measure, in particular with \(P\) replaced consistently by an empirical measure \(\widehat{P}\) or \(\widetilde{P}\). In Figure 1, we illustrate the performance of our first order approximation of the adversarial loss on CIFAR-10 (Krizhevsky, 2009) under different threat models.

WD-Adversarial Accuracy.We consider an attacker with perfect knowledge of the network \(f_{\theta}\) and the data distribution \(P\), aiming to minimize the prediction accuracy of \(f_{\theta}\) 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_{\delta}(P)\), where \(\delta\) is the attack budget, i.e., the tolerance for distributional image distortion. We define the adversarial accuracy as:

\[A_{\delta}:=\inf_{Q\in B_{\delta}(P)}Q(S)=\inf_{Q\in B_{\delta}(P)}\mathbf{E}_ {Q}[\![\![\,_{S}]\!]. \tag{9}\]

Note that \(A_{\delta}\) is decreasing in \(\delta\) with \(A_{0}=A\), the clean accuracy. For \(p=\infty\), 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 \(1\leqslant p<\infty\), the _distributional_ threat model is strictly stronger than the _pointwise_ one, as observed in Staib and Jegelka (2017, Prop. 3.1). Intuitively, it 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 to out-of-distribution generalization, see Shen et al. (2021) for a survey.

WD-Adversarial Attack.We propose _Wasserstein distributionally adversarial attack_ methods. We believe this is a novel contribution and, so far, 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 is possible thanks to the explicit first-order expression for the distributional attack in Theorem 4.1(ii).

We recall the Difference of Logits Ratio (DLR) loss of Croce and Hein (2020). If we write \(z=(z_{1},\ldots,z_{m})=f_{\theta}(x)\) for the output of a neural network, and \(z_{(1)}\geqslant\cdots\geqslant z_{(m)}\) are the order

Figure 1: Performance of the first order approximation for the W-DRO value derived in Theorem 4.1. Left: WideResNet-28-10 (Gowal et al., 2020) under CE loss (3) and \((\mathcal{W}_{\infty},l_{\infty})\) threat model with \(\delta=1/255,\ldots,10/255\). Right: WideResNet-28-10 (Wang et al., 2023) under ReDLR loss (10) and \((\mathcal{W}_{2},l_{2})\) threat models with \(\delta=1/16,\ldots,10/16\).
statistics of \(z\), then DLR loss is given by DLR loss is given by

\[\mathrm{DLR}(z,y)=\begin{cases}-\dfrac{z_{y}-z_{(2)}}{z_{(1)}-z_{(3)}},&\text{if }z_{y}=z_{(1)},\\ -\dfrac{z_{y}-z_{(1)}}{z_{(1)}-z_{(3)}},&\text{else}.\end{cases}\]

The combination of CE loss and DLR loss has been widely shown as 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 1 for details. To rectify this, we propose ReDLR (Rectified DLR) loss:

\[\mathrm{ReDLR}(z,y)=-(\mathrm{DLR})^{-}(z,y)=\begin{cases}-\dfrac{z_{y}-z_{(2 )}}{z_{(1)}-z_{(3)}},&\text{if }z_{y}=z_{(1)},\\ 0,&\text{else}.\end{cases} \tag{10}\]

Its key property is to leave unaffected those images that are already misclassified. Our experiments show it performs superior to CE or DLR.

An attack is performed using the test data set. For a given loss function, our proposed attack is:

\[x^{t+1}=\mathrm{proj}_{\delta}\big{(}x^{t}+\alpha h(\nabla_{x}J_{\theta}(x^{t },y))\big{|}\widetilde{\mathcal{T}}^{-1}\nabla_{x}J_{\theta}(x^{t},y)\big{|} \mathfrak{z}^{t-1}_{*}\big{)}, \tag{11}\]

where \(\alpha\) is the step size and \(\mathrm{proj}_{\delta}\) is a projection which ensures the empirical measure \(\widetilde{P}^{t+1}:=\frac{1}{|\widetilde{D}_{tt}|}\sum_{(x,y)\in\mathcal{D}_ {tt}}\delta_{(x^{t+1},y)}\) stays inside the Wasserstein ball \(B_{\delta}(\widetilde{P})\). In the case \(p=r=\infty\), one can verify \(h(x)=\mathrm{sgn}(x)\) and write (11) as

\[x^{t+1}=\mathrm{proj}_{\delta}\big{(}x^{t}+\alpha\ \mathrm{sgn}(\nabla_{x}J_{ \theta}(x^{t},y))\big{)}.\]

This gives exactly Fast Gradient Sign Method (single step) and Projected Gradient Descent (multi-step) proposed in Goodfellow et al. (2015), Madry et al. (2018) and we adopt the same labels for our more general algorithms.5 A pseudocode for the above attack is summarized in Appendix C.

Footnote 5: To stress the Wasserstein attack and the particular loss function we may write, e.g., _W-PGD-ReDLR_.

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 to future research.

## 5 Performance Bounds

Understanding how a DNN classifier will perform outside of the training data set is of key importance. We leverage the DRO sensitivity results now to obtain a lower bound on \(A_{\delta}\). We then use results on convergence of empirical measures in Fournier and Guillin (2015) to translate our lower bound into guarantees on out-of-sample performance.

Bounds on Adversarial Accuracy.We propose the following metric of robustness:

\[\mathcal{R}_{\delta}:=\frac{A_{\delta}}{A}\in[0,1].\]

Previous works mostly focus on the maximum distortion a neural network can withhold to retain certain adversarial performance, see Hein and Andriushchenko (2017), Weng et al. (2018) for 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 a distributionally adversarial attack. In contrast, since \(A=A_{0}\) is known, computing \(\mathcal{R}_{\delta}\) is equivalent to computing \(A_{\delta}\). We choose to focus on the relative loss of accuracy as it provides a convenient normalization: \(0\leqslant\mathcal{R}_{\delta}\leqslant 1\). \(\mathcal{R}_{\delta}=1\) corresponds to a very robust architecture which performs as well under attacks as it does on clean test data, while \(\mathcal{R}_{\delta}=0\) corresponds to an architecture which loses all of its predictive power under an adversarial attack. Together the couple \((A,A_{\delta})\) thus summarizes the performance of a given classifier. However, computing \(A_{\delta}\) is difficult and time-consuming. Below, we develop a simple and efficient method to calculate theoretical guaranteed bounds on \(\mathcal{R}\) and thus also on \(A_{\delta}\).
**Assumption 5.1**.: We assume that for any \(Q\in B_{\delta}(P)\)

1. \(0<Q(S)<1\).
2. \(\mathcal{W}_{p}(Q(\cdot|S),P(\cdot|S))+\mathcal{W}_{p}(Q(\cdot|S^{c}),P(\cdot|S^ {c}))=o(\delta),\) where the conditional distribution is given by \(Q(E|S)=Q(E\cap S)/Q(S)\).

The first condition stipulates non-degeneracy: the classifier does not perform perfectly but retains some accuracy under attacks. The second condition says the classes are well-separated: for \(\delta\) small enough an admissible attack can rarely succeed.

We write the adversarial loss condition on the correctly classified images and misclassified images as

\[C(\delta)=\sup_{Q\in B_{\delta}(P)}\mathbf{E}_{Q}[J_{\theta}(x,y)|S]\quad\text {and}\quad W(\delta)=\sup_{Q\in B_{\delta}(P)}\mathbf{E}_{Q}[J_{\theta}(x,y)|S^ {c}].\]

We note that an upper bound on \(\mathcal{R}_{\delta}\) is given by any adversarial attack. In particular,

\[\mathcal{R}_{\delta}\leqslant\mathcal{R}_{\delta}^{u}:=Q_{\delta}(S)/A. \tag{12}\]

**Theorem 5.1**.: _Under Assumptions 4.1 and 5.1, we have an asymptotic lower bound as \(\delta\to 0\)_

\[\mathcal{R}_{\delta}\geqslant\frac{W(0)-V(\delta)}{W(0)-V(0)}+o(\delta)= \widetilde{\mathcal{R}}_{\delta}^{l}+o(\delta)=\overline{\mathcal{R}}_{\delta }^{l}+o(\delta), \tag{13}\]

_where the first order approximations are given by_

\[\widetilde{\mathcal{R}}_{\delta}^{l}=\frac{W(0)-\mathbf{E}_{Q_{\delta}}[J_{ \theta}(x,y)]}{W(0)-V(0)}\quad\text{and}\quad\overline{\mathcal{R}}_{\delta}^ {l}=\frac{W(0)-V(0)-\delta\Upsilon}{W(0)-V(0)}. \tag{14}\]

The equality between the lower bound and the two first-order approximations \(\widetilde{\mathcal{R}}_{\delta}^{l}\) and \(\overline{\mathcal{R}}_{\delta}^{l}\) follows from Theorem 4.1. Consequently, \(\mathcal{R}_{\delta}^{l}:=\min\{\widetilde{\mathcal{R}}_{\delta}^{l}, \overline{\mathcal{R}}_{\delta}^{l}\}\) allows us to estimate the model robustness without performing any sophisticated adversarial attack. Our experiments, detailed below, show the bound is reliable for small \(\delta\) and is orders of magnitude faster to compute than \(\mathcal{R}_{\delta}\) 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(\delta)=\sup_{Q\in B_{\delta}(P)}\mathbf{E}_{Q}[C(\delta)\mathbbm{1}_{S}+W (\delta)\mathbbm{1}_{S^{c}}]+o(\delta).\]

Bounds on Out-of-Sample Performance.Our results on distributionally adversarial robustness translate into bounds for performance of the trained DNN on unseen data. We rely on 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<n/2\) and let \(N=|\mathcal{D}_{tr}|\), \(M=|\mathcal{D}_{tt}|\). If sampling of data from \(P\) is described on a probability space \((\Omega,\mathcal{F},\mathbb{P})\) then \(\widehat{P}\) is a random measure on this space and, by ergodic theorem, \(\mathbb{P}\)-a.s., it converges weakly to \(P\) as \(N\to\infty\). In fact, \(\mathcal{W}_{p}(\widehat{P},P)\) converges to zero \(\mathbb{P}\)-a.s. Crucially the rates of convergence were obtained in Dereich et al. (2013), Fournier and Guillin (2015) and yield

\[\mathbb{E}[\mathcal{W}_{p}(\widehat{P},P)]\leqslant KN^{-\frac{1}{n}}\quad \text{and}\quad\mathbb{P}(\mathcal{W}_{p}(\widehat{P},P)\geqslant\varepsilon) \leqslant K\exp(-KN\varepsilon^{n}), \tag{15}\]

where \(K\) is a constant depending on \(p\) and \(n\) which can be computed explicitly, see for example Guo and Obloj (2019, Appendix). This, with triangle inequality and Theorem 5.1, gives

**Corollary 5.3**.: _Under Assumptions 4.1 and 5.1 on measure \(\widehat{P}\), with probability at least \(1-2K\exp(-K\varepsilon^{n}\min\{M,N\})\) it holds that_

\[\vec{A}=\vec{P}(S)\geqslant\widehat{A}\widehat{\mathcal{R}}_{2\varepsilon}^{l} +o(\varepsilon).\]

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 \(1-K\exp(-KN\varepsilon^{n})\) we have_

\[V(\delta)\leqslant\widehat{V}(\delta)+\varepsilon\sup_{Q\in B_{\delta}^{*}( \widehat{P})}\Bigl{(}\mathbf{E}_{Q}\|\nabla_{x}J_{\theta}(x,y)\|_{s}^{q}\Bigr{)} ^{1/q}+o(\varepsilon)\leqslant\widehat{V}(\delta)+L\varepsilon\]

_where \(B_{\delta}^{\star}(\widehat{P})=\arg\max_{Q\in B_{\delta}(\widehat{P})} \mathbf{E}_{Q}[J_{\theta}(x,y)]\) and constant \(K\) only depends on \(p\) and \(n\)._

Our lower bound estimate in Theorem 5.1 can be restated as

\[\Delta\widehat{A}_{\delta}:=\widehat{A}-\widehat{A}_{\delta}\leqslant\frac{ \widehat{V}(\delta)-\widehat{V}(0)}{\widehat{W}(0)-\widehat{C}(0)}+o(\delta).\]

We now use Theorem 5.4 to bound \(\Delta A(\delta)\), the shortfall of the adversarial accuracy under \(P\), using quantities evaluated under \(\widehat{P}\).

**Corollary 5.5**.: _Under Assumptions 4.1 and 5.1, with probability at least \(1-K\exp(-KN\delta^{n})\) it holds that_

\[\Delta A_{\delta}(P)\leqslant\frac{\widehat{V}(\delta)-\widehat{V}(0)}{ \widehat{W}(0)-\widehat{C}(0)}+\frac{2L\delta}{\widehat{W}(0)-\widehat{C}(0)} +o(\delta).\]

We remark that the above results are easily extended to the out-of-sample performance on the test set, via the triangle inequality \(\mathcal{W}_{p}(\widehat{P},\widehat{P})\leqslant\mathcal{W}_{p}(\widehat{P},P)+\mathcal{W}_{p}(P,\widetilde{P})\). By using complexity measures such as entropy integral (Lee and Raginsky, 2018), Rademacher complexity (Gao, 2022, Gao et al., 2022) a further analysis can be undertaken for

\[\inf_{\theta\in\Theta}\sup_{Q\in B_{\delta}(P)}\mathbf{E}_{Q}[J_{\theta}(x,y)] \quad\text{and}\quad\inf_{\theta\in\Theta}\sup_{Q\in B_{\delta}(\widehat{P})} \mathbf{E}_{Q}[J_{\theta}(x,y)]. \tag{16}\]

In particular, a dimension-free estimate of out-of-sample performance is obtained in (Gao, 2022) under a Lipschitz framework with light-tail reference measures.

## 6 Numerical Experiments

Experimental Setting.We conduct experiments on a high performance computing server equipped with 49 GPU nodes. The algorithms are implemented in Python. All experiments are conducted on CIFAR-10 dataset (Krizhevsky, 2009), comprising 60,000 color images across 10 mutually exclusive classes, with 6,000 images per class. Each image contains \(32\times 32\) pixels in 3 color channels. We normalize the input feature as a vector \(x\in[0,1]^{3\times 32\times 32}\). 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 \((\mathcal{W}_{p},l_{r})\) with \(p,r\in\{2,\infty\}\) with different range of attack budget \(\delta\) depending on the relative strength of the attack. E.g., roughly speaking, if an \(l_{\infty}\)-attack modifies one third of the pixels of an image with strength 4/255, then it corresponds to an \(l_{2}\)-attack with strength 1/2. When clear from the context, we drop the \(\delta\) subscript.

We take top neural networks from RobustBench (Croce et al., 2021), a lively maintained repository that records benchmark robust neural networks on CIFAR-10 against _pointwise_ attacks. For _pointwise_ threat models \((\mathcal{W}_{\infty},l_{r})\), RobustBench reports \(A_{\delta}\) obtained using AutoAttack (Croce and Hein, 2020) for \(l_{\infty},\delta=8/255\) and \(l_{2},\delta=1/2\), see Appendix F. However, due to high computational cost of AutoAttack, we apply PGD-50 based on CE and DLR losses as a substitute to obtain the reference adversarial accuracy for attacks with relatively small budgets \(\delta=2/255,4/255\) for \(l_{\infty}\) and \(\delta=1/8,1/4\) for \(l_{2}\). For _distributional_ threat models \((\mathcal{W}_{2},l_{r})\), 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_{\delta}\). All PGD attacks are run with 50 iteration steps and take between 1 and 12 hours to run on a single GPU environment. Bounds \(\mathcal{R}^{l},\mathcal{R}^{u}\) compute ca. 50 times faster.

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 a pointwise, i.e., \(\infty\)-W-DRO attack and a distributional 2-W-DRO attack is only realized using the ReDLR loss.
In Figure 2, 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.

Bounds on Adversarial Accuracy.We report in Table 2 the computation time of our proposed bounds \(\mathcal{R}^{l}_{\delta}=\min\{\widetilde{\mathcal{R}}^{l}_{\delta},\overline{ \mathcal{R}}^{l}_{\delta}\}\) in (14) and \(\mathcal{R}^{u}_{\delta}\) in (12) with the computation time of \(\mathcal{R}_{\delta}\) obtained from AutoAttack. Computing our proposed bounds \(\mathcal{R}^{l},\mathcal{R}^{u}\) is orders of magnitude faster than performing an attack to estimate \(\mathcal{R}\). This also holds for _distributional_ threat attacks.

To illustrate the applications of Theorem 5.1, we plot the bounds \(\mathcal{R}^{l}\) and \(\mathcal{R}^{u}\) against \(\mathcal{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 as \(\delta\) increases we are likely to go outside of the linear approximation regime, see Figure 1. Indeed, in Appendix E we plot the results for pointwise attack with \(\delta=8/255\) where some of neural networks have a lower bound \(\mathcal{R}^{l}\) greater than the reference \(\mathcal{R}\). Note that smaller \(\delta\) values are suitable for the stronger \(\mathcal{W}_{2}\)-distributional attack. For _pointwise_ threat models (top row) we compute the bounds using CE loss. For _distributional_ threat models (bottom row), reference adversarial accuracy is obtained from a W-PGD-DLR attack and, accordingly, we use ReDLR loss to compute \(\mathcal{R}^{u}\) and \(\mathcal{R}^{l}\). 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 \(\mathcal{R}^{l}\), we could estimate \(V(\delta)\) and use the lower bound in (13). This offers a trade-off between computational time and accuracy which is explored further in Appendix E.

Footnote 6: We use all 60 available networks on RobustBench (model zoo) for \(l_{\infty}\) and all 20 available networks for \(l_{2}\).

## 7 Limitations and future work

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 of the two

\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & PreActResNet-18 & ResNet-18 & ResNet-50 & WRN-28-10 & WRN-34-10 & WRN-70-16 \\ \hline \hline \(\mathcal{R}\) & 197 & 175 & 271 & 401 & 456 & 2369 \\ \(\mathcal{R}^{l}\&\mathcal{R}^{u}\) & 0.52 & 0.49 & 0.17 & 0.55 & 0.53 & 1.46 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Computation times of \((\mathcal{W}_{\infty},l_{\infty}),\delta=8/255\) attack for one mini-batch of size \(100\), in seconds. We compute \(\mathcal{R}\) by AutoAttack and average the computation time over models on RobustBench grouped by their architecture.

\begin{table}
\begin{tabular}{c c c c c} \hline \hline  & \(\mathcal{W}_{\infty}\) & \multicolumn{3}{c}{\(\mathcal{W}_{2}\)} \\ \cline{2-5} Methods & AutoAttack & W-PGD-CE & W-PGD-DLR & W-PGD-ReDLR \\ \hline \(l_{\infty}\) & 57.66\% & 61.32\% & 79.00\% & **45.46\%** \\ \(l_{2}\) & 75.78\% & 74.62\% & 78.69\% & **61.69\%** \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of adversarial accuracy of neural networks on RobustBench under different empirical attacks. Set attack budget \(\delta=8/255\) for \(l_{\infty}\) threat models and \(\delta=1/2\) for \(l_{2}\) threat models.

Figure 2: Shortfall of WD-adversarial accuracy with different metrics \(l_{\infty}\) (left) and \(l_{2}\) (right).
training algorithms derived here and investigating further sensitivity-based ones, as well as analyzing 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.

Broader Impact.Our work contributes to 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-distribution performance and Knightian uncertainty. We provide computationally efficient tools to evaluate robustness of DNNs. However, our results are asymptotic and hence valid 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.

## 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 College, Oxford. YJ's research is 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.
