Measurable threat correspondences and robust risk

Let $(\mathcal{X},{\mathrm{\Sigma }}_X)$ and $(\mathcal{Y},{\mathrm{\Sigma }}_Y)$ be measurable spaces, let $\mathcal{A}$ be a measurable action space, and let $P$ be a probability measure on $(\mathcal{X}\times \mathcal{Y},{\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y)$. A threat correspondence is a map $\mathrm{\Delta }:\mathcal{X}\to \mathcal{P}(\mathcal{X})$ with $\mathrm{\Delta }(x)\mathrm{\ne }\mathrm{\varnothing }$ for every $x$. It is measurable when its graph $\{(x,x^{\mathrm{\prime }})\in {\mathcal{X}}^2:x^{\mathrm{\prime }}\in \mathrm{\Delta }(x)\}$ belongs to ${\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_X$. For a measurable predictor $f:\mathcal{X}\to \mathcal{A}$ and a nonnegative measurable loss $\mathrm{\ell }:\mathcal{A}\times \mathcal{Y}\to [0,+\mathrm{\infty }]$, the pointwise robust loss is $L_{\mathrm{\Delta },f}(x,y)={\sup }_{x^{\mathrm{\prime }}\in \mathrm{\Delta }(x)}\mathrm{\ell }(f(x^{\mathrm{\prime }}),y)\mathrm{.}$ Its robust risk is the outer expectation $R_{P,\mathrm{\Delta }}^{\mathrm{r}\mathrm{o}\mathrm{b}}(f)={\mathbb{E}}_P^{\ast }[L_{\mathrm{\Delta },f}(X,Y)]:=\inf \{{\mathbb{E}}_P[g(X,Y)]:g\ge L_{\mathrm{\Delta },f}\text{ and }g\text{ is nonnegative measurable}\}\mathrm{.}$ If $L_{\mathrm{\Delta },f}$ is measurable, this is its ordinary expectation. The supremum need not be attained. For a metric $\rho$ on $\mathcal{X}$ and a radius $ϵ\ge 0$, the closed-ball threat is ${\mathrm{\Delta }}_{ϵ}(x)=\{x^{\mathrm{\prime }}\in \mathcal{X}:\rho (x,x^{\mathrm{\prime }})\le ϵ\}$. On ${\mathbb{R}}^d$, $\mathrm{\parallel }u{\mathrm{\parallel }}_{\mathrm{\infty }}:={\max }_{1\le j\le d}\mathrm{\mid }{u}_j\mathrm{\mid }$ and the ${\mathrm{\ell }}_{\mathrm{\infty }}$ threat is ${\mathrm{\Delta }}_{ϵ}(x)=\{x+\delta :\mathrm{\parallel }\delta {\mathrm{\parallel }}_{\mathrm{\infty }}\le ϵ\}$. When $\mathcal{A}=\mathcal{Y}=\{-1,+1\}$ with their discrete sigma-algebras and $\mathrm{\ell }(a,y)={\mathbf{1}}_{\{a\mathrm{\ne }y\}}$, the robust zero-one loss of a measurable classifier $f:\mathcal{X}\to \{-1,+1\}$ is $\mathbf{1}\{\mathrm{\exists }{x}^{\mathrm{\prime }}\in {\mathrm{\Delta }}_{ϵ}(x):f(x^{\mathrm{\prime }})\mathrm{\ne }y\}$.

Measurable spaces and measurable sets: a measurable space is a set equipped with a sigma-algebra.

A measurable function between measurable spaces: measurability means every measurable target set has measurable preimage.

A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain: a function is single-valued on its domain.

The product sigma-algebra and its finite iterates: ${\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y$ is generated by measurable rectangles.

Probability measures and probability spaces: a probability measure has total mass one.

Expectation of a nonnegative or integrable random variable: expectation is the corresponding extended or finite Lebesgue integral.

Pydi, Chapter 2 §§2.2–2.3: expected-supremum risk and the measurability caveat.

Kolter–Madry, Chapter 1: input-dependent perturbation sets and expected worst-case loss.