Adversarial Risk Under Input Perturbation Sets

Pointwise Perturbations and Worst-Case Loss

A classifier can perform well on the observed inputs yet fail after a small change to each input. Adversarial risk formalizes this concern by asking, for every observed input, how large the loss could become among the inputs allowed by a specified perturbation set. The set is local to that input: it describes which alternatives the adversary may choose for that particular case.

This is a different question from asking how well a classifier performs in a new population. A changed population may place different probability on inputs, while pointwise adversarial risk keeps the original population’s probability weighting and takes a worst case within each input’s allowed set.

Definition: Let $(X,Y)$ have a source population distribution, let $h$ be a classifier, and let $\ell(h(x),y)$ be its loss. A pointwise threat set $\Delta(x)$ is a nonempty set of inputs that an adversary is allowed to substitute for $x$. The adversarial risk is $$ R_{\mathrm{adv}}(h)=E\left[\sup_{z\in\Delta(X)}\ell(h(z),Y)\right]. $$ The population expectation is with respect to the original joint distribution of $(X,Y)$. We assume the supremum in this expression is measurable and integrable; for zero-one loss, integrability is automatic once measurability holds.

A common choice is a norm ball, $\Delta(x)=\{x+\delta:\|\delta\|\leq\varepsilon\}$, where $\varepsilon$ is a radius chosen to represent the allowed perturbation size. The geometry of the chosen set matters: a ball in one norm permits different directions and magnitudes from a ball in another norm. The threat set is part of the definition of the risk, not a detail that can be omitted when reporting it.

Worked Example: A One-Dimensional Threshold

Let the score be $f(x)=x$, let the label be $Y=+1$, and use margin-based zero-one loss $\ell(x,+1)=\mathbf{1}\{f(x)\leq 0\}$, so a zero score counts as an error. The classifier is evaluated at $x=0.15$ with threat set $\Delta(x)=[x-0.2,x+0.2]$.

Here $\Delta(0.15)=[-0.05,0.35]$. The unperturbed score is $0.15>0$, so the ordinary loss is zero. But the allowed input $z=-0.05$ has score at most zero and incurs loss one. Therefore the supremum loss over the threat set is one, and the pointwise adversarial loss is one.

If instead $x=0.30$ with the same radius, the threat set is $[0.10,0.50]$. Every allowed input has positive score, so the supremum loss is zero. The two cases differ because one threat set reaches the decision boundary and the other does not.

Zero-One Loss and Reachable Errors

For classification, a particularly direct interpretation comes from zero-one loss. For a label $y$, let $\ell(h(z),y)=\mathbf{1}\{h(z)\ne y\}$. The supremum over a threat set is one exactly when at least one allowed input is misclassified. Thus adversarial risk is a probability of reachable error, rather than an average over a randomly selected perturbation.

Result: Suppose $h$ is measurable, $\Delta(x)$ is nonempty, and the event that some $z\in\Delta(X)$ satisfies $h(z)\ne Y$ is measurable. Under zero-one loss, $$ R_{\mathrm{adv}}(h)=P\left(\text{there exists }z\in\Delta(X)\text{ such that }h(z)\ne Y\right). $$

Proof. Fix a realized pair $(X,Y)=(x,y)$. Every loss $\mathbf{1}\{h(z)\ne y\}$ is either zero or one. If every $z\in\Delta(x)$ is classified correctly, their supremum is zero. If at least one $z\in\Delta(x)$ is classified incorrectly, one of these losses equals one, so the supremum is one. Consequently, pointwise, $$ \sup_{z\in\Delta(X)}\mathbf{1}\{h(z)\ne Y\} = \mathbf{1}\{\text{there exists }z\in\Delta(X):h(z)\ne Y\}. $$ Taking expectations of both sides gives the stated probability identity. $\square$

This result also explains why averaging the loss over a randomly sampled perturbation is not the same operation. A random perturbation can miss an allowed failure; the supremum records a failure whenever any allowed input causes one. A related basic property follows directly: if $\Delta_1(x)\subseteq\Delta_2(x)$ for every $x$, then the supremum over $\Delta_1(x)$ cannot exceed the supremum over $\Delta_2(x)$. Hence enlarging a threat set cannot reduce adversarial risk.

How Norm Geometry Changes Linear Classification Risk

For linear scores, the worst-case effect of a norm-ball perturbation can be calculated exactly. Consider binary labels $y\in\{-1,+1\}$, score $f(x)=w^\top x+b$, and margin-based zero-one loss $\mathbf{1}\{y f(x)\leq0\}$. This convention treats a zero signed margin as an error. Let the threat set be $\{x+\delta:\|\delta\|\leq\varepsilon\}$. The dual norm of $\|\cdot\|$ is $$ \|w\|_*=\sup_{\|u\|\leq1}|w^\top u|. $$

Theorem: For the linear score and loss just defined, with $\varepsilon\geq0$, $$ \sup_{\|\delta\|\leq\varepsilon} \mathbf{1}\{y f(x+\delta)\leq0\} = \mathbf{1}\{y(w^\top x+b)\leq\varepsilon\|w\|_*\}. $$ Thus a point is robustly classified correctly exactly when its signed margin exceeds $\varepsilon\|w\|_*$.

Proof. The signed score after perturbation is $$ y f(x+\delta)=y(w^\top x+b)+y w^\top\delta. $$ The smallest possible value of $y w^\top\delta$ over $\|\delta\|\leq\varepsilon$ is $-\varepsilon\|w\|_*$. The dual-norm inequality gives the lower bound because $|w^\top\delta|\leq\|w\|_*\|\delta\|\leq\varepsilon\|w\|_*$. This bound is attained: in finite-dimensional space, the continuous linear functional $u\mapsto y w^\top u$ attains its minimum on the compact unit ball, and the minimum is $-\|w\|_*$; scaling a minimizer by $\varepsilon$ gives the claimed value (with the result immediate if $w=0$ or $\varepsilon=0$). Therefore the minimum signed score is $y(w^\top x+b)-\varepsilon\|w\|_*$. The worst-case loss is one exactly when this minimum is at most zero, which is equivalent to $y(w^\top x+b)\leq\varepsilon\|w\|_*$. $\square$

The norm in input space therefore determines which dual norm measures the classifier’s vulnerability. For an $L_\infty$ threat set, the dual norm is $L_1$; for an $L_2$ threat set, it is $L_2$; and for an $L_1$ threat set, it is $L_\infty$. The resulting threshold is a geometric statement: the allowed perturbations can reduce the signed margin by at most $\varepsilon\|w\|_*$.

Worked Example: Comparing Two Threat-Set Geometries

Take $w=(1,2)$, $b=0$, label $y=+1$, input $x=(1,0)$, and radius $\varepsilon=0.4$. The original signed margin is $w^\top x=1$.

For an $L_\infty$ threat set, $\|w\|_*=\|w\|_1=|1|+|2|=3$. The greatest possible margin reduction is $0.4(3)=1.2$, so the worst signed margin is $1-1.2=-0.2$. The point is adversarially misclassified. Indeed, $\delta=(-0.4,-0.4)$ is allowed and gives score $1-0.4-0.8=-0.2$.

For an $L_2$ threat set, $\|w\|_*=\|w\|_2=\sqrt{1^2+2^2}=\sqrt{5}$. The greatest reduction is $0.4\sqrt{5}$, approximately $0.894$, leaving worst signed margin $1-0.4\sqrt{5}$, approximately $0.106>0$. The point is robustly classified correctly. The minimizing perturbation is $\delta=-0.4w/\|w\|_2$, which has $L_2$ norm $0.4$ and attains that margin.

The input and radius are identical in the two calculations. The difference in worst-case loss comes solely from the geometry of the allowed perturbation set.

Adversarial Risk Is Not Population Distribution Shift

A target population distribution $Q$ defines a risk such as $E_Q[\ell(h(X),Y)]$. This expectation changes the distribution over which cases are averaged. Adversarial risk instead starts with the source distribution of $(X,Y)$, retains its weighting of cases, and takes the largest allowed loss separately for each case. It is not enough to say that both are “worst-case” risks: the objects being varied are different.

Worked Example: Local Vulnerability Versus a Changed Population

Suppose the source population puts probability one on $(X,Y)=(0,+1)$, and the classifier predicts $+1$ at $x=0$ but $-1$ at $x=1$. Under the singleton threat set $\Delta(0)=\{0\}$, the adversarial risk is zero: the only allowed input is classified correctly.

Now consider a target population that puts probability one on $(X,Y)=(1,+1)$. Its ordinary target risk is one, because every target case is misclassified. This high target risk is caused by the target population’s mass being on a different input, not by a failure reachable from the source input under the stated threat set.

If the source threat set were changed to $\Delta(0)=\{0,1\}$, the source adversarial risk would instead be one, because the allowed input $1$ is misclassified. This change in adversarial risk comes from enlarging the pointwise set, not from changing the source population distribution.

The distinction matters when interpreting a robustness claim. A small adversarial risk is always relative to a stated loss, classifier, source population, and threat-set geometry. It does not by itself establish low risk under every changed population. Conversely, a large target risk does not show that target errors are reachable by the particular perturbations allowed in an adversarial-risk calculation.

Common Pitfall

Wrong reasoning: “The adversary may choose a different input, so adversarial risk is just ordinary risk under some shifted distribution.” This overlooks the order of operations. In adversarial risk, the supremum is taken within each source case before averaging over source cases; a target-distribution risk averages losses under the target distribution. They need not have the same weighting or the same allowed changes.

Correction: Write down the source distribution and the pointwise set $\Delta(x)$ explicitly. Then calculate the maximum loss over that set for each source case and average those maxima. If the question instead specifies a changed population, calculate risk under that population. Do not substitute one formulation for the other without an argument establishing that the two particular quantities coincide.

A second practical caution is that “small perturbation” has no unique mathematical meaning until its set is specified. Changing a norm, a radius, or the coordinates that may change can change the worst-case loss, as the linear example demonstrates. Robustness statements should therefore report the threat set, not just a perturbation size.

Check Your Understanding

Use the definitions and calculations above to answer these questions.

In zero-one classification, what event does the pointwise supremum loss indicate?
For a linear score, what dual norm determines the largest possible reduction in signed margin under an $L_\infty$ threat set?
Why can the target risk be large even when adversarial risk under a particular source threat set is zero?
If every pointwise threat set is enlarged, can adversarial risk decrease? Explain using the supremum definition.
For the linear example with $w=(1,2)$, $y=+1$, and margin $1$, calculate the $L_2$ worst-case margin at radius $0.2$. Is the point robustly classified correctly?