Adversarial robustness and robust risk — Examples

Assume AC. For an integer $d\ge 2$, set $\sigma =d^{1\mathrm{/}4}\mathrm{/}32$ and $ϵ=1\mathrm{/}4$. For the fixed-parameter Gaussian model with $\mathrm{\parallel }\theta {\mathrm{\parallel }}_2=\sqrt{d}$, the class-weighted sample-mean classifier has ${\mathrm{\ell }}_{\mathrm{\infty }}$ robust risk at most $1\mathrm{/}100$ with training-sample probability at least $1-2e^{-d\mathrm{/}(8({\sigma }^2+1))}$ whenever the integer sample size satisfies $n\ge 4\sqrt{d}$. In the separate Gaussian-prior experiment $\mathrm{\Theta }\sim N_d(0,I_d)$, every Borel learning rule $F:({\mathbb{R}}^d\times \{-1,+1\}{)}^n\times {\mathbb{R}}^d\to \{-1,+1\}$ has expected ${\mathrm{\ell }}_{\mathrm{\infty }}$ robust risk at least $(1-1\mathrm{/}d)\mathrm{/}2$ whenever $n\le \sqrt{d}\mathrm{/}(131072\log d)$. The first assertion concerns a fixed normalized parameter and an upper bound for one classifier; the second averages over a Gaussian prior and lower-bounds every such Borel learning rule. Expected robust risk in the prior experiment uses outer expectation over the parameter and training sample.

Schmidt et al., Corollary 22, Appendix A.1, PDF p. 26.

Schmidt et al., Corollary 23, Appendix A.2, PDF p. 30.

Robust sample upper bound in the Gaussian model: supplies the exact one-percent sufficient sample size.

Robust sample lower bound in the Gaussian model: supplies the learner-independent Gaussian-prior necessary sample size.

Let $d\ge 1$, $\theta \in \{-1,+1{\}}^d$, $0<\tau \le 1\mathrm{/}2$, $0\le ϵ<1$, and let $(X,Y)\sim P_{\theta ,\tau }$ be the binary-feature Bernoulli model. Let $T(x{)}_j=+1$ for $x_j\ge 0$ and $T(x{)}_j=-1$ for $x_j<0$. For every classifier $g:\{-1,+1{\}}^d\to \{-1,+1\}$, the classifier $g\circ T$ has exactly the same ${\mathrm{\ell }}_{\mathrm{\infty }}$ robust risk at radius $ϵ$ as $g$ has natural risk: $R_{P_{\theta ,\tau },{\mathrm{\Delta }}_{ϵ}}^{\mathrm{r}\mathrm{o}\mathrm{b}}(g\circ T)=\mathbb{P}(g(X)\mathrm{\ne }Y)\mathrm{.}$ For $w\in {\mathbb{R}}^d$, define $f_w(x)=+1$ when $⟨w,x⟩\ge 0$ and $f_w(x)=-1$ otherwise. In particular, if $0<\beta <1$ and $\tau \ge (\log (1\mathrm{/}\beta )\mathrm{/}(2d){)}^{1\mathrm{/}4}$, then the one-sample classifier $f_{Y_0{X}_0}\circ T$ has robust risk at most $\beta$ with training-sample probability at least $1-e^{-{\tau }^{2}d\mathrm{/}2}$.

Schmidt et al., Theorem 10 and Corollary 28, main text and Appendix B.1, PDF pp. 7, 31–32.

Kolter–Madry, Chapter 2, thresholding and linear models.

Binary-feature Bernoulli model: the support is exactly the sign hypercube with a binary label.

Architecture-dependent robustness in the Bernoulli model: supplies the one-sample high-probability error guarantee.

Assume AC and set $d={10}^{14}$, $\sigma =d^{1\mathrm{/}4}\mathrm{/}32$, $\beta =1\mathrm{/}100$, and $ϵ=1\mathrm{/}4$. In the fixed-parameter experiment with $\mathrm{\parallel }\theta {\mathrm{\parallel }}_2=\sqrt{d}$, one class-weighted training sample yields natural test error at most $1\mathrm{/}100$ with probability at least $1-2e^{-d\mathrm{/}(8({\sigma }^2+1))}$. In the distinct Gaussian-prior experiment $\mathrm{\Theta }\sim N_d(0,I_d)$, at the same $n=1$ and $ϵ$, every Borel learning rule $F:({\mathbb{R}}^d\times \{-1,+1\}{)}^n\times {\mathbb{R}}^d\to \{-1,+1\}$ has expected robust risk at least $(1-1\mathrm{/}d)\mathrm{/}2$. The first assertion fixes a normalized parameter; the second averages over the stated Gaussian prior. Expected robust risk in the prior experiment uses outer expectation over the parameter and training sample.

Schmidt et al., Corollary 19, Appendix A.1, PDF pp. 24–25.

Schmidt et al., Corollary 23, Appendix A.2, PDF p. 30.

One-sample natural error in the Gaussian model: supplies the fixed-parameter one-sample natural-error guarantee.

Robust sample lower bound in the Gaussian model: supplies the Gaussian-prior robust-risk lower bound.