Existence and Minimax Theorems for Adversarial Surrogate Risks in Binary Classification

This paper studies binary classification on $\mathbb{R}^{d}$ with two classes encoded as $-1$ and $+1$. Data is distributed according to a distribution $\mathcal{D}$ on $\mathbb{R}^{d}\times\{-1,+1\}$. We denote the marginals according to the class label as ${\mathbb{P}}_{0}(S)=\mathcal{D}(S\times\{-1\})$ and ${\mathbb{P}}_{1}(S)=\mathcal{D}(S\times\{+1\})$. Throughout the paper, we assume ${\mathbb{P}}_{0}(\mathbb{R}^{d})$ and ${\mathbb{P}}_{1}(\mathbb{R}^{d})$ are finite but not necessarily that ${\mathbb{P}}_{0}(\mathbb{R}^{d})+{\mathbb{P}}_{1}(\mathbb{R}^{d})=1$.

To classify points in $\mathbb{R}^{d}$, algorithms typically learn a real-valued function $f$ and then classify points ${\mathbf{x}}$ according to the sign of $f$ (arbitrarily assigning the sign of 0 to be $-1$). The classification error, also known as the classification risk, of a function $f$ is

$$R(f)=\int{\mathbf{1}}_{f({\mathbf{x}})\leq 0}d{\mathbb{P}}_{1}+\int{\mathbf{1}}_{f({\mathbf{x}})>0}d{\mathbb{P}}_{0}.$$

(1)

Notice that finding minimizers to $R$ is straightforward: define the measure ${\mathbb{P}}={\mathbb{P}}_{0}+{\mathbb{P}}_{1}$ and let $\eta=d{\mathbb{P}}_{1}/d{\mathbb{P}}$. Then the risk $R$ can be re-written as

$$R(f)=\int\eta({\mathbf{x}}){\mathbf{1}}_{f({\mathbf{x}})\leq 0}+(1-\eta({\mathbf{x}})){\mathbf{1}}_{f({\mathbf{x}})>0}d{\mathbb{P}}.$$

Hence a minimizer of $R$ must minimize the function $C(\eta({\mathbf{x}}),\alpha)=\eta({\mathbf{x}}){\mathbf{1}}_{\alpha\leq 0}+(1-\eta({\mathbf{x}})){\mathbf{1}}_{\alpha>0}$ at each ${\mathbf{x}}$ ${\mathbb{P}}$-a.e. The optimal Bayes risk is then

$$\inf_{f}R(f)=\int C^{*}(\eta)d{\mathbb{P}}$$

where $C^{*}(\eta)=\inf_{\alpha}C(\eta,\alpha)=\min(\eta,1-\eta)$.

This paper analyzes the evasion attack, in which an adversary knows both the function $f$ and the true label of the data point, and can perturb each input before it is evaluated by the function $f$. To constrain the adversary, we assume that perturbations are bounded by $\epsilon$ in a norm $\|\cdot\|$. Thus a point ${\mathbf{x}}$ with label $+1$ is misclassified if there is a perturbation ${\mathbf{h}}$ with $\|{\mathbf{h}}\|\leq\epsilon$ for which $f({\mathbf{x}}+{\mathbf{h}})\leq 0$ and a point ${\mathbf{x}}$ with label $-1$ is misclassified if there is a perturbation ${\mathbf{h}}$ with $\|{\mathbf{h}}\|\leq\epsilon$ for which $f({\mathbf{x}}+{\mathbf{h}})>0$. Therefore, the adversarial classification risk is

$$R^{\epsilon}(f)=\int\sup_{\|{\mathbf{h}}\|\leq\epsilon}{\mathbf{1}}_{f({\mathbf{x}}+{\mathbf{h}})\leq 0}d{\mathbb{P}}_{1}+\int\sup_{\|{\mathbf{h}}\|\leq\epsilon}{\mathbf{1}}_{f({\mathbf{x}}+{\mathbf{h}})>0}d{\mathbb{P}}_{0}$$

(2)

which is the expected proportion of errors subject to the adversarial evasion attack. The expression $\sup_{\|{\mathbf{h}}\|\leq\epsilon}{\mathbf{1}}_{f({\mathbf{x}}+{\mathbf{h}})\leq 0}$ evaluates to 1 at a point ${\mathbf{x}}$ iff ${\mathbf{x}}$ can be moved into the set $[f\leq 0]$ by a perturbation of size at most $\epsilon$. Equivalently, this set is the Minkowski sum $\oplus$ of $[f\leq 0]$ and $\overline{B_{\epsilon}({\mathbf{0}})}$. For any set $A$, let $A^{\epsilon}$ denote

$$A^{\epsilon}=\{{\mathbf{x}}\colon\exists{\mathbf{h}}\text{ with }\|{\mathbf{h}}\|\leq\epsilon\text{ and }{\mathbf{x}}+{\mathbf{h}}\in A\}=A\oplus\overline{B_{\epsilon}({\mathbf{0}})}=\bigcup_{{\mathbf{a}}\in A}\overline{B_{\epsilon}({\mathbf{a}})}.$$

(3)

This operation ‘thickens’ the boundary of a set by $\epsilon$. With this notation, (2) can be expressed as $R^{\epsilon}(f)=\int{\mathbf{1}}_{\{f\leq 0\}^{\epsilon}}d{\mathbb{P}}_{1}+\int{\mathbf{1}}_{\{f>0\}^{\epsilon}}d{\mathbb{P}}_{0}$.

Unlike the classification risk $R$, finding minimizers to $R^{\epsilon}$ is nontrivial. One can re-write $R^{\epsilon}$ in terms of ${\mathbb{P}}$ and $\eta$ but the resulting integrand cannot be minimized in a pointwise fashion. Nevertheless, it can be shown that minimizers of $R^{\epsilon}$ exist (Awasthi et al., 2021b; Bungert et al., 2021; Pydi and Jog, 2021; Frank and Niles-Weed, 2023).

As minimizing the empirical version of risk in (1) is computationally intractable, typical machine learning algorithms minimize a proxy to the classification risk called a surrogate risk. In fact, Ben-David et al. (2003) show that minimizing the empirical classification risk is NP-hard in general. One popular surrogate is

$$R_{\phi}(f)=\int\phi(f)d{\mathbb{P}}_{1}+\int\phi(-f)d{\mathbb{P}}_{0}$$

(4)

where $\phi$ is a decreasing function.¹¹1Notice that due to the asymmetry of the sign function at 0 in (1), $R_{\phi}$ is not quite a generalization of $R$. To define a classifier, one then threshholds $f$ at zero. There are many reasonable choices for $\phi$—one typically chooses an upper bound on the zero-one loss which is easy to optimize. We make the following assumption on $\phi$:

A particularly important example, which plays a large role in our proofs, is the exponential loss $\psi(\alpha)=e^{-\alpha}$, which will be denoted by $\psi$ in the remainder of this paper. Assumption 1 includes many but not all all surrogate risks used in practice. Notably, some multiclass surrogate risks with two classes are of a somewhat different form, see for instance (Tewari and Bartlett, 2007) for more details.

In order to find minimizers of $R_{\phi}$, we rewrite the risk in terms of ${\mathbb{P}}$ and $\eta$ as

$$R_{\phi}(f)=\int\eta({\mathbf{x}})\phi(f({\mathbf{x}}))+(1-\eta({\mathbf{x}}))\phi(-f({\mathbf{x}}))d{\mathbb{P}}$$

(5)

Hence the minimizer of $R_{\phi}$ must minimize $C_{\phi}(\eta,\cdot)$ pointwise ${\mathbb{P}}$-a.e., where

$$C_{\phi}(\eta,\alpha)=\eta\phi(\alpha)+(1-\eta)\phi(-\alpha).$$

In other words, if one defines $C_{\phi}^{*}(\eta)=\inf_{\alpha}C_{\phi}(\eta,\alpha)$, then a function $f^{*}$ is optimal if and only if

$$\eta({\mathbf{x}})\phi(f^{*}({\mathbf{x}}))+(1-\eta({\mathbf{x}}))\phi(-f^{*}({\mathbf{x}}))=C_{\phi}^{*}(\eta({\mathbf{x}}))\quad{\mathbb{P}}\text{-a.e.}$$

(6)

Thus one can write the minimum value of $R_{\phi}$ as

$$\inf_{f}R_{\phi}(f)=\int C_{\phi}^{*}(\eta)d{\mathbb{P}}.$$

(7)

To guarantee the existence of a function satisfying (6), we must allow our functions to take values in the extended real numbers $\overline{\mathbb{R}}=\mathbb{R}\cup\{-\infty,+\infty\}$. Allowing the value $\alpha=+\infty$ is necessary, for instance, for the exponential loss $\psi(\alpha)=e^{-\alpha}$: when $\eta=1$, the minimum of $C_{\psi}(1,\alpha)=e^{-\alpha}$ is achieved at $\alpha=+\infty$. In fact, one can express a minimizer as a function of the conditional probability $\eta({\mathbf{x}})$ using (6). For a loss $\phi$, define $\alpha_{\phi}:[0,1]\to\overline{R}$ by

$$\alpha_{\phi}(\eta)=\inf\{\alpha:\alpha\text{ is a minimizer of }C_{\phi}(\eta,\cdot)\}.$$

(8)

Lemma 25 in Appendix C shows that the function $\alpha_{\phi}$ is montonic and $\alpha_{\phi}(\eta)$ is in fact a minimizer of $C_{\phi}(\eta,\cdot)$. Thus the function

$$f^{*}({\mathbf{x}})=\alpha_{\phi}(\eta({\mathbf{x}}))$$

(9)

is measurable and satisfies (6). Therefore, $f^{*}$ must be a minimizer of the risk $R_{\phi}$.

Similarly, rather directly minimizing the adversarial classification risk, practical algorithms minimize an adversarial surrogate. The adversarial counterpart to (4) is

$\displaystyle R_{\phi}^{\epsilon}(f)=\int\sup_{\|{\mathbf{h}}\|\leq\epsilon}\phi(f({\mathbf{x}}+{\mathbf{h}}))d{\mathbb{P}}_{1}+\int\sup_{\|{\mathbf{h}}\|\leq\epsilon}\phi(-f({\mathbf{x}}+{\mathbf{h}}))d{\mathbb{P}}_{0}.$

(10)

Due to the definitions of the adversarial risks (2) and (10), the operation of finding the supremum of a function over $\epsilon$-balls is central to our subsequent analysis. For a function $g$, we define

$$S_{\epsilon}(g)({\mathbf{x}})=\sup_{\|{\mathbf{h}}\|\leq\epsilon}g({\mathbf{x}}+{\mathbf{h}})$$

(11)

Using this notation, one can re-write the risk $R_{\phi}^{\epsilon}$ as

$\displaystyle R_{\phi}^{\epsilon}(f)=\int S_{\epsilon}(\phi\circ f)d{\mathbb{P}}_{1}+\int S_{\epsilon}(\phi\circ-f)d{\mathbb{P}}_{0}$

By analogy to (5), we equivalently write the risk $R_{\phi}^{\epsilon}$ in terms of ${\mathbb{P}}$ and $\eta$:

$$R_{\phi}^{\epsilon}(f)=\int\eta({\mathbf{x}})S_{\epsilon}(\phi\circ f)({\mathbf{x}})+(1-\eta({\mathbf{x}}))S_{\epsilon}(\phi\circ-f)({\mathbf{x}})d{\mathbb{P}}.$$

(12)

However, unlike (5), because the integrand of $R_{\phi}^{\epsilon}$ cannot be minimized in a pointwise manner, proving the existence of minimizers to $R_{\phi}^{\epsilon}$ is non-trivial. In fact, unlike the adversarial classification risk $R^{\epsilon}$, there is little theoretical understanding of properties of minimizing $R_{\phi}^{\epsilon}$.

In order to define the adversarial risks $R^{\epsilon}$ and $R_{\phi}^{\epsilon}$, one must show that $S_{\epsilon}({\mathbf{1}}_{A}),S_{\epsilon}(\phi\circ f)$ are measurable. To illustrate this concern, Pydi and Jog (2021) show that for every $\epsilon>0$ and $d>1$, there is a Borel set $C$ for which the function $S_{\epsilon}({\mathbf{1}}_{C})({\mathbf{x}})$ is not Borel measurable. However, if $g$ is Borel, then $S_{\epsilon}(g)$ is always measurable with respect to a larger $\sigma$-algebra called the universal $\sigma$-algebra ${\mathscr{U}}(\mathbb{R}^{d})$. Such a function is called universally measurable. We prove the following theorem and formally define the universal $\sigma$-algebra in Appendix A.

In fact, in Appendix A, we show that a function defined by a supremum over a compact set is universally measurable— a result of independent interest. The universal $\sigma$-algebra is smaller than the completion of ${\mathcal{B}}(\mathbb{R}^{d})$ with respect to any Borel measure. Thus, in the remainder of the paper, unless otherwise noted, all measures will be Borel measures and the expression $\int S_{\epsilon}(f)d{\mathbb{Q}}$ will be interpreted as the integral of $S_{\epsilon}(f)$ with respect to the completion of ${\mathbb{Q}}$.

In this section, we explain how the integral of a supremum $\int S_{\epsilon}(f)d{\mathbb{Q}}$ can be expressed in terms of a supremum of integrals. We start by defining the Wasserstein-$\infty$ metric.

In other words, ${\mathbb{P}}$, ${\mathbb{Q}}$ are within a Wasserstein-$\infty$ distance of $\epsilon$ if there is a coupling $\gamma$ for ${\mathbb{P}}$ and ${\mathbb{Q}}$ for which $\operatorname{supp}\gamma$ is contained in the set $\Delta_{\epsilon}=\{({\mathbf{x}},{\mathbf{x}}^{\prime})\colon\|{\mathbf{x}}-{\mathbf{x}}^{\prime}\|\leq\epsilon\}$.

The $\infty$-Wasserstein metric is closely related to the to the operation $S_{\epsilon}$. First, we show that $S_{\epsilon}$ can be expressed as a supremum of integrals over a Wasserstein-$\infty$ ball. For a measure ${\mathbb{Q}}$, we write

$${{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{Q}})=\{{\mathbb{Q}}^{\prime}\text{ Borel}:W_{\infty}({\mathbb{Q}},{\mathbb{Q}}^{\prime})\leq\epsilon\}.$$

Lemma 5.1 of Pydi and Jog (2021) proves an analogous statement for sets, namely that ${\mathbb{Q}}(A^{\epsilon})=\sup_{{\mathbb{Q}}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{Q}})}{\mathbb{Q}}(A)$, under suitable assumptions on ${\mathbb{Q}}$ and ${\mathbb{Q}}^{\prime}$.

Conversely, the $W_{\infty}$ distance between two probability measures can be expressed in terms of the integrals of $f$ and $S_{\epsilon}(f)$. Let $C_{b}(X)$ be the set of continuous bounded functions on the topological space $X$.

This observation will be central to proving a duality result. See Appendix B for proofs of Lemmas 3 and 4.

Our goal in this paper is to understand properties of the surrogate risk minimization problem $\inf_{f}R_{\phi}^{\epsilon}$. The starting point for our results is Lemma 3, which implies that $\inf_{f}R_{\phi}^{\epsilon}$ actually involves a $\inf$ followed by a $\sup$:

$$\inf_{f\text{ Borel}}R_{\phi}^{\epsilon}(f)=\inf_{f\text{ Borel}}\sup_{\begin{subarray}{c}{\mathbb{P}}_{0}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{0})\\ {\mathbb{P}}_{1}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{1})\end{subarray}}\int\phi\circ fd{\mathbb{P}}_{1}^{\prime}+\int\phi\circ-fd{\mathbb{P}}_{0}^{\prime}.$$

We therefore obtain a lower bound on $\inf_{f}R_{\phi}^{\epsilon}$ by swapping the $\sup$ and $\inf$ and recalling the definition of $C_{\phi}^{*}(\eta)=\inf_{\alpha}C_{\phi}(\eta,\alpha)$:

	$\displaystyle\inf_{f\text{ Borel}}R_{\phi}^{\epsilon}(f)$	$\displaystyle\geq\sup_{\begin{subarray}{c}{\mathbb{P}}_{0}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{0})\\ {\mathbb{P}}_{1}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{1})\end{subarray}}\inf_{f\text{ Borel}}\int\phi\circ fd{\mathbb{P}}_{1}^{\prime}+\int\phi\circ-fd{\mathbb{P}}_{0}^{\prime}$
		$\displaystyle=\sup_{\begin{subarray}{c}{\mathbb{P}}_{0}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{0})\\ {\mathbb{P}}_{1}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{1})\end{subarray}}\inf_{f\text{ Borel}}\int\frac{d{\mathbb{P}}_{1}^{\prime}}{d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime})}\phi(f)+\left(1-\frac{d{\mathbb{P}}_{1}^{\prime}}{d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime})}\right)\phi(-f)d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime})$
		$\displaystyle\geq\sup_{\begin{subarray}{c}{\mathbb{P}}_{0}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{0})\\ {\mathbb{P}}_{1}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{1})\end{subarray}}\int C_{\phi}^{*}\left(\frac{d{\mathbb{P}}_{1}^{\prime}}{d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime})}\right)d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime})$		(14)

If we define

$$\bar{R}_{\phi}({\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime})=\int C_{\phi}^{*}\left(\frac{d{\mathbb{P}}_{1}^{\prime}}{d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime})}\right)d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime}),$$

(15)

then we have shown

$$\inf_{f\text{ Borel}}R_{\phi}^{\epsilon}(f)\geq\sup_{\begin{subarray}{c}{\mathbb{P}}_{0}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{0})\\ {\mathbb{P}}_{1}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{1})\end{subarray}}\bar{R}_{\phi}({\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime}).$$

(16)

This statement is a form of weak duality.

When the surrogate adversarial risk is replaced by the standard adversarial classification risk, Pydi and Jog (2021) proved that the analogue of (16) is actually an equality, so that strong duality holds for the adversarial classification problem. Concretely, by analogy to (15), consider

$$\bar{R}({\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime})=\int C^{*}\left(\frac{d{\mathbb{P}}_{1}^{\prime}}{d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime})}\right)d({\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime}).$$

Let $\mu$ be the Lebesgue measure and let $\mathcal{L}_{\mu}(\mathbb{R}^{d})$ be the Lebesgue $\sigma$-algebra. Then define

$${\tilde{{\mathcal{B}}}^{\infty}_{\epsilon}}({\mathbb{Q}})=\{{\mathbb{Q}}^{\prime}\colon W_{\infty}({\mathbb{Q}},{\mathbb{Q}}^{\prime})\leq\epsilon,{\mathbb{Q}}^{\prime}\text{ a measure on $(\mathbb{R}^{d},\mathcal{L}_{\mu}(\mathbb{R}^{d}))$}\}.$$

(17)

Pydi and Jog (2021) show the following.

This is a foundational result in the theory of adversarial classification, but it leaves an open question crucial in applications: Does the strong duality relation extend to surrogate risks and to general measures? In this work, we answer this question in the affirmative.

We start by proving the following:

When $\epsilon=0$, we recover the fundamental characterization of the minimum risk for standard (non-adversarial) classification in (7). Theorem 6 can be rephrased as

$$\inf_{f\text{ Borel}}\sup_{\begin{subarray}{c}{\mathbb{P}}_{0}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{0})\\ {\mathbb{P}}_{1}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{1})\end{subarray}}\hat{R}_{\phi}(f,{\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime})=\sup_{\begin{subarray}{c}{\mathbb{P}}_{0}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{0})\\ {\mathbb{P}}_{1}^{\prime}\in{{\mathcal{B}}^{\infty}_{\epsilon}}({\mathbb{P}}_{1})\end{subarray}}\inf_{f\text{ Borel}}\hat{R}_{\phi}(f,{\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime})$$

(20)

where

$$\hat{R}_{\phi}(f,{\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime})=\int\phi(f)d{\mathbb{P}}_{1}^{\prime}+\int\phi(-f)d{\mathbb{P}}_{0}^{\prime}$$

As discussed in Pydi and Jog (2021), this result has an appealing game theoretic interpretation: adversarial learning with a surrogate risk can be though of as a zero-sum game between the learner who selects a function $f$ and the adversary who chooses perturbations through ${\mathbb{P}}_{0}^{\prime}$ and ${\mathbb{P}}_{1}^{\prime}$. Furthermore, the player to pick first does not have an advantage.

Additionally, (20) suggest that training adversarially robust classifiers could be accomplished by optimizing over primal functions $f$ and dual distributions ${\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime}$ simultaneously.

A consequence of Theorem 6 is the following complementary slackness conditions for optimizers $f^{*},{\mathbb{P}}_{0}^{*},{\mathbb{P}}_{1}^{*}$:

This theorem implies that every minimizer $f^{*}$ of $R_{\phi}^{\epsilon}$ and every maximizer $({\mathbb{P}}_{0}^{*},{\mathbb{P}}_{1}^{*})$ of $\bar{R}_{\phi}$ forms a primal-dual pair. The condition (21) states that every maximizer of $\bar{R}_{\phi}$ is an optimal adversarial attack on $f^{*}$ while the condition (22) states that every minimizer $f^{*}$ of $R_{\phi}^{\epsilon}$ also minimizes the conditional risk $C_{\phi}(\eta^{*},\cdot)$ under the distribution of optimal adversarial attacks. In other words, $f^{*}$ minimizes the standard surrogate risk with respect to the optimal adversarially perturbed distributions. Explicitly: (22) implies that every minimizer $f^{*}$ minimizes the loss $\hat{R}_{\phi}(f,{\mathbb{P}}_{0}^{*},{\mathbb{P}}_{1}^{*})=\int C(\eta^{*}({\mathbf{x}}),f({\mathbf{x}}))d{\mathbb{P}}^{*}$ in a pointwise manner ${\mathbb{P}}^{*}$-a.e. This fact is the relation (6) with respect to the measures ${\mathbb{P}}_{0}^{*},{\mathbb{P}}_{1}^{*}$ that maximize the dual $\bar{R}_{\phi}$.

This interpretation of Theorems 6 and 7 shed light on the phenomenon of transfer attacks. These theorems suggests that adversarial examples are a property of the data distribution rather than a specific model. Later results in the paper even show that there are maximizers of $\bar{R}_{\phi}$ that are independent of the choice of loss function $\phi$ (see Lemma 26). Theorem 7 specifically states that every maximizer of $\bar{R}_{\phi}$ is actually an optimal adversarial attack on every minimizer of $R_{\phi}^{\epsilon}$. Notably, this statement is indepent of the choice of minimizer of $R_{\phi}^{\epsilon}$. Because neural networks are highly expressive model classes, one would hope that some neural net could achieve adversarial error close to $\inf_{f}R^{\epsilon}_{\phi}(f)$. If $f^{*}$ is a minimizer of $R_{\phi}^{\epsilon}$ and $g$ is a neural net with $R^{\epsilon}_{\phi}(g)\approx R^{\epsilon}_{\phi}(f^{*})$, one would expect that an optimal adversarial attack against $f^{*}$ would be a successful attack on $g$ as well. Notice that in this discussion, the adversarial attack is independent of the neural net $g$. A method for calculating these optimal adversarial attacks is an open problem.

Finally, to demonstrate that Theorem 7 and the preceding discussion is non-vacuous, we prove the existence of primal and dual optimizers along with results that elaborate on their structure.

Theorem 3.5 of (Jylhä, 2014) implies that when the norm $\|\cdot\|$ is strictly convex and ${\mathbb{P}}_{0},{\mathbb{P}}_{1}$ are absolutely continuous with respect to Lebesgue measure, the optimal ${\mathbb{P}}_{0}^{*},{\mathbb{P}}_{1}^{*}$ of Theorem 8 are induced by a transport map. Corollary 3.11 of (Jylhä, 2014) further implies that these transport maps are continuous a.e. with respect to the Lebesgue measure $\mu$. As the $\ell_{\infty}$ metric is commonly used in practice, whether there exist maximizers of the dual of this type for non-strictly convex norms remains an attractive open problem.

In analogy with (6) and (9) one would hope that due to the complimentary slackness condition (22), one could define a minimizer in terms of the conditional $\eta^{*}({\mathbf{x}})$. Notice, however, that as this quantity is only defined ${\mathbb{P}}^{*}$-a.e., verifying the other complimentary slackness condition (21) would be a challenge. To circumvent this issue, we construct a function $\hat{\eta}:\mathbb{R}^{d}\to[0,1]$, defined on all of $\mathbb{R}^{d}$, to which we can apply (9). Concretely, we show that $\alpha_{\phi}(\hat{\eta}({\mathbf{x}}))$ is always a minimizer of $R_{\phi}^{\epsilon}$, with $\alpha_{\phi}$ as defined in (8).

In fact, we show that $\hat{\eta}$ is a version of the conditional derivative $d{\mathbb{P}}_{1}^{*}/d{\mathbb{P}}^{*}$, where ${\mathbb{P}}_{0}^{*},{\mathbb{P}}_{1}^{*}$ are the measures which maximize $\bar{R}_{\phi}$ independently of the choice of $\phi$ (see Lemma 24), as described in the discussion preceding Theorem 8. The fact that the function $\hat{\eta}$ is independent of the choice of loss $\phi$ suggests that the minimizer of $R_{\phi}^{\epsilon}$ encodes some fundamental quality of the distribution ${\mathbb{P}}_{0},{\mathbb{P}}_{1}$.

Simultaneous work (Li and Telgarsky, 2023) also proves the existence of a minimizer to the primal $R_{\phi}^{\epsilon}$ along with a statement on the structure of this minimizer. Their approach leverages prior results on the adversarial Bayes classifier to construct a minimizer to the adversarial surrogate risk.

The central proof strategy of this paper is to apply the Fenchel-Rockafellar duality theorem. This classical result relates the infimum of a convex functional with the supremum of a concave functional. One can argue that $\bar{R}_{\phi}$ is concave (Lemma 12 below); however, the primal $R_{\phi}^{\epsilon}$ is not convex for non-convex $\phi$. Thus the Fenchel-Rockafellar theorem is applied to a convex relaxation $\Theta$ of the primal $R_{\phi}^{\epsilon}$.

The remainder of the paper then argues that minimizing $\Theta$ is equivalent to minimizing $R_{\phi}^{\epsilon}$. Notice that the Fenchel-Rockafellar theorem actually implies the existence of dual maximizers. We show that that dual maximizers of $\bar{R}_{\psi}$ for $\psi(\alpha)=e^{-\alpha}$ satisfy certain nice properties that are independent of the loss $\psi$. These properties then allow us to construct the function $\hat{\eta}$ present in Theorem 9 in addition to minimizers of $\Theta$ from the dual maximizers of $\bar{R}_{\psi}$, for any loss $\phi$. The construction of these minimizers guarantee that they minimize $R_{\phi}^{\epsilon}$ in addition to $\Theta$.

Section 5 proves strong duality and complimentary slackness theorems for $\bar{R}_{\phi}$ and $\Theta$, the convex relaxation of $R_{\phi}^{\epsilon}$. Next, in Section 6, a version of the complimentary slackness result is used to prove the existence of minimizers to $\Theta$. Subsequently, Section 7 shows the equivalence between $\Theta$ and $R_{\phi}^{\epsilon}$.

Appendix A proves Theorem 1 and further discusses universal measurability. Next, Appendix B proves all the results about the $W_{\infty}$-norm used in this paper. Appendix C then defines the function $\alpha_{\phi}$ which is later used in the proof of several results. Appendices D,  E, F, and G.3 contain technical deferred proofs.

The fundamental duality relation of this paper follows from employing the Fenchel-Rockafellar theorem in conjunction with the Riesz representation theorem, stated below for reference. See e.g. (Villani, 2003) for more on this result.

Let $\mathcal{M}(X)$ be the set of finite signed Borel measures on a space $X$ and recall that $C_{b}(X)$ is the set of bounded continuous functions on the space $X$.

See Theorem 1.9 of (Villani, 2003) and result 7.17 of (Folland, 1999) for more details.

Notice that in the Fenchel-Rockafellar theorem, the left-hand side of (23) is convex while the right-hand side is concave. However, when $\phi$ is non-convex, $R_{\phi}^{\epsilon}$ is not convex. In order to apply the Fenchel-Rockafellar theorem, we will relax the primal $R_{\phi}^{\epsilon}$ will to a convex functional $\Theta$.

We define $\Theta$ as

$$\Theta(h_{0},h_{1})=\int S_{\epsilon}(h_{1})d{\mathbb{P}}_{1}+\int S_{\epsilon}(h_{0})d{\mathbb{P}}_{0}$$

(24)

which is convex in $h_{0},h_{1}$ due to the sub-additivity of the supremum operation. Notice that one obtains $\Theta$ from $R_{\phi}^{\epsilon}$ by replacing $\phi\circ f$ with $h_{1}$ and $\phi\circ-f$ with $h_{0}$.

The functional $\Xi$ will be chosen to restrict $h_{0},h_{1}$ in the hope that at the optimal value, $h_{1}=\phi(f)$ and $h_{0}=\phi(-f)$ for some $f$. Notice that if $h_{1}=\phi(f)$, $h_{0}=\phi(-f)$ then for all $\eta\in[0,1]$,

$$\eta h_{1}({\mathbf{x}})+(1-\eta)h_{0}=\eta\phi(f))+(1-\eta)\phi(-f)\geq C_{\phi}^{*}(\eta).$$

Thus we will optimize $\Theta$ over the set of functions $S_{\phi}$ defined by

$$S_{\phi}=\left\{\begin{aligned} &(h_{0},h_{1})\colon h_{0},h_{1}\colon K^{\epsilon}\to\overline{\mathbb{R}}\text{ Borel, }0\leq h_{0},h_{1}\text{ and for}\\ &\text{all ${\mathbf{x}}\in\mathbb{R}^{d}$, $\eta\in[0,1]$, }\eta h_{0}({\mathbf{x}})+(1-\eta)h_{1}({\mathbf{x}})\geq C_{\phi}^{*}(\eta)\end{aligned}\right\}$$

(25)

where $K=\operatorname{supp}({\mathbb{P}}_{0}\cup{\mathbb{P}}_{1})$. (Notice that the definition of $S_{\epsilon}(g)$ in (11) assumes that the domain of $g$ must include $\overline{B_{\epsilon}({\mathbf{x}})}$. Thus in order to define the integral $\int S_{\epsilon}(h)d{\mathbb{Q}}$, the domain of $h$ must include $(\operatorname{supp}{\mathbb{Q}})^{\epsilon}$.) Thus we define $\Xi$ as

$$\Xi(h_{0},h_{1})=\begin{cases}0&\text{if }(h_{0},h_{1})\in S_{\phi}\\ +\infty&\text{otherwise}\end{cases}$$

(26)

The following result expresses $\bar{R}_{\phi}$ as an infimum of linear functionals continuous with respect to the weak topology on probability measures. This lemma will assist in the computation of $\Xi^{*}$. In the remainder of this section, $\mathcal{M}_{+}(S)$ will denote the set of positive finite Borel measures on a set $S$.

We sketch the proof and formally fill in the details in Appendix D. Let ${\mathbb{P}}^{\prime}={\mathbb{P}}_{0}^{\prime}+{\mathbb{P}}_{1}^{\prime}$, $\eta^{\prime}=d{\mathbb{P}}_{1}^{\prime}/d{\mathbb{P}}^{\prime}$. Then

$$\int h_{1}d{\mathbb{P}}_{1}^{\prime}+\int h_{0}d{\mathbb{P}}_{0}^{\prime}=\int\eta^{\prime}h_{1}+(1-\eta^{\prime})h_{0}d{\mathbb{P}}^{\prime}$$

Clearly, the inequality $\geq$ holds because $\eta^{\prime}h_{1}+(1-\eta^{\prime})h_{0}\geq C_{\phi}^{*}(\eta^{\prime})$ for all $(h_{0},h_{1})\in S_{\phi}$. Equality is achieved at $h_{1}=\phi(\alpha_{\phi}(\eta^{\prime})),h_{0}=\phi(-\alpha_{\phi}(\eta^{\prime}))$, with $\alpha_{\phi}$ as in (8). However, these functions may not be continuous. In Appendix D, we show that $h_{0},h_{1}$ can be approximated arbitrarily well by elements of $S_{\phi}\cap E$.

Notice that if $h_{0}$, $h_{1}$ are continuous, then $S_{\epsilon}(h_{0})$, $S_{\epsilon}(h_{1})$ are also continuous and $\int S_{\epsilon}(h_{0})d{\mathbb{Q}}$, $\int S_{\epsilon}(h_{1})d{\mathbb{Q}}$ are well-defined for every Borel ${\mathbb{Q}}$. Hence we assume that ${\mathbb{P}}_{0}$, ${\mathbb{P}}_{1}$ are Borel measures rather than their completion.

Let $K=\operatorname{supp}({\mathbb{P}}_{0}+{\mathbb{P}}_{1})$. We will apply the Fenchel-Rockafellar Duality Theorem to the functionals given by (24) and (26) on the vector space $E=C_{b}(K^{\epsilon})\times C_{b}(K^{\epsilon})$ equipped with the sup norm. By the Riesz representation theorem, dual of the space $E$ is $E^{*}=\mathcal{M}(K^{\epsilon})\times\mathcal{M}(K^{\epsilon})$.

To start, we argue that the Fenchel-Rockafellar duality theorem applies to these functionals. First, notice that if $(h_{0},h_{1})\in E$, then both $h_{0},h_{1}$ are bounded so $\Theta(h_{0},h_{1})<\infty$. Furthermore, $\Theta$ is convex due to the subadditivity of supremum and $\Xi$ is convex because the constraint $h_{0}({\mathbf{x}})+(1-\eta)h_{1}({\mathbf{x}})\geq C_{\phi}^{*}(\eta)$ is linear in $h_{0}$ and $h_{1}$. Furthermore, $\Theta$ is continuous on $E$ because $\Theta$ is convex and bounded and $E$ is open, see Theorem 2.14 of (Barbu and Precupanu, 2012).

Because the constant function $(C_{\phi}^{*}(1/2),C_{\phi}^{*}(1/2))$ is in $S_{\phi}$, $\Xi$ is not identically $\infty$ and therefore the Fenchel-Rockafellar theorem applies.

Clearly $\inf_{E}\Theta(h_{0},h_{1})+\Xi(h_{0},h_{1})$ reduces to the left-hand side of (28).

We now compute the dual of $\Xi$. Lemma 12 implies that

	$\displaystyle-\Xi^{*}(-{\mathbb{P}}_{0}^{\prime},-{\mathbb{P}}_{1}^{\prime})=-\sup_{(h_{0},h_{1})\in S_{\phi}\cap E}-\int h_{0}d{\mathbb{P}}_{0}^{\prime}-\int h_{1}d{\mathbb{P}}_{1}^{\prime}$		(29)
	$\displaystyle=\begin{cases}\bar{R}_{\phi}({\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime})&\text{if }{\mathbb{P}}_{i}^{\prime}\geq 0\\ -\infty&\text{otherwise}\end{cases}$

This computation implies that the term $-\Xi^{*}(-{\mathbb{P}}_{0}^{\prime},-{\mathbb{P}}_{1}^{\prime})$ present in the Fenchel-Rockafellar Theorem is not $-\infty$ iff ${\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime}$ are positive measures. Next, notice that because $\Theta(h_{0},h_{1})<+\infty$ for all $(h_{0},h_{1})\in E$, $-\Theta^{*}({\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime})$ is never $+\infty$. Therefore, it suffices to compute $\Theta^{*}$ for positive measures ${\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime}$. Lemma 4 implies that for positive measures ${\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime}$,

	$\displaystyle\Theta^{*}({\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime})=\sup_{h_{0},h_{1}\in C_{0}(K^{\epsilon})}\int h_{1}d{\mathbb{P}}_{1}^{\prime}+\int h_{0}d{\mathbb{P}}_{0}^{\prime}-\left(\int S_{\epsilon}(h_{0})d{\mathbb{P}}_{0}+\int S_{\epsilon}(h_{1})d{\mathbb{P}}_{1}\right)$
	$\displaystyle=\sup_{h_{1}\in C_{0}(K^{\epsilon})}\left(\int h_{1}d{\mathbb{P}}_{1}^{\prime}-\int S_{\epsilon}(h_{1})d{\mathbb{P}}_{1}\right)+\sup_{h_{0}\in C_{0}(K^{\epsilon})}\left(\int h_{0}d{\mathbb{P}}_{0}^{\prime}-\int S_{\epsilon}(h_{0})d{\mathbb{P}}_{0}+\right)$
	$\displaystyle=\begin{cases}0&{\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime}\text{ positive measures, with }W_{\infty}({\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{0})\leq\epsilon\text{ and }W_{\infty}({\mathbb{P}}_{1}^{\prime},{\mathbb{P}}_{1})\leq\epsilon\\ +\infty&{\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{1}^{\prime}\text{ positive measures, with either }W_{\infty}({\mathbb{P}}_{0}^{\prime},{\mathbb{P}}_{0})>\epsilon\text{ or }W_{\infty}({\mathbb{P}}_{1}^{\prime},{\mathbb{P}}_{1})>\epsilon\end{cases}$