Another adversarial machine learning paper “Certified Adversarial Robustness via Randomized Smoothing” builds a theory based on the notion of the half space. The paper introduced a technique referred to as randomized smoothing that transforms any classifier into a new one that admits a provable $\ell_2$ robustness certificate. Its core relies on the Gaussian shift bound (a form of the Neyman–Pearson lemma for mean‑shifted Gaussians).
Gaussian Shift Bound
Let
\[ X \sim \mathcal{N}(\mu,\sigma^2 I),\quad Y \sim \mathcal{N}(\mu + \delta,\sigma^2 I). \]
Fix a measurable set $S \subset \mathbb{R}^d$ with
\[ P_X(S) = \Pr[X \in S] = q. \]
We seek
\[ \inf_{S: P_X(S)=q} P_Y(S) \quad\text{and}\quad \sup_{S: P_X(S)=q} P_Y(S). \]
Neyman–Pearson setup
We set up a hypothesis test between
\[ H_0: Z \sim p_0 = \mathcal{N}(\mu,\sigma^2 I), \quad H_1: Z \sim p_1 = \mathcal{N}(\mu + \delta,\sigma^2 I). \]
The likelihood ratio is
\[ \Lambda(z) = \frac{p_1(z)}{p_0(z)} = \exp\Bigl(\frac{\delta^\top (z-\mu)}{\sigma^2} - \frac{|\delta|^2}{2\sigma^2}\Bigr), \]
which is monotone in $\delta^\top z$. By Neyman–Pearson, the extremal sets are of the form ${\Lambda(z)\le\tau}$ or ${\Lambda(z)\ge\tau}$, i.e.\ half‑spaces orthogonal to $\delta$.
Reduction to 1‑D
Project onto $u = \delta / |\delta|_2$, let $T = u^\top Z$. Then under $H_0$, $T\sim \mathcal{N}(u^\top\mu,\sigma^2)$; under $H_1$, $T\sim \mathcal{N}(u^\top\mu + |\delta|_2,\sigma^2)$. All orthogonal directions integrate out identically.
Minimum case (infimum)
Choose $S_{\min} = {T \le t^\star}$ so that $P_{H_0}(T \le t^\star)=q$. Then
\[ t^\star = u^\top\mu + \sigma\,\Phi^{-1}(q), \]
and
\[ \inf_{S: P_X(S)=q} P_Y(S) = P_{H_1}(T \le t^\star) = \Phi\Bigl(\Phi^{-1}(q) - \frac{|\delta|_2}{\sigma}\Bigr). \]
Maximum case (supremum)
Choose $S_{\max} = {T \ge t_{\max}}$ so that $P_{H_0}(T \ge t_{\max})=q$. Then $t_{\max} = u^\top\mu + \sigma\,\Phi^{-1}(1-q)$, and
\[ \sup_{S: P_X(S)=q} P_Y(S) = P_{H_1}(T \ge t_{\max}) = \Phi\Bigl(\Phi^{-1}(q) + \frac{|\delta|_2}{\sigma}\Bigr). \]
Deriving Cohen et al.’s Theorem
Define a base classifier $f$ and its smoothed version
\[ g(x) = \arg\max_c \Pr_{\varepsilon\sim \mathcal{N}(0,\sigma^2 I)}[f(x+\varepsilon)=c]. \]
Let
\[ p_A = \Pr[f(x+\varepsilon)=c_A], \quad p_B = \max_{B\neq A} \Pr[f(x+\varepsilon)=c_B], \]
and consider any perturbation $\delta$ with $|\delta|_2 = r$. Applying the above bounds to the regions $E_A = {z: f(z)=c_A}$ and $E_B$ yields:
\[ \Pr[f(x+\delta+\varepsilon)=c_A] \;\ge\; \Phi\Bigl(\Phi^{-1}(p_A) - \tfrac{r}{\sigma}\Bigr), \quad \Pr[f(x+\delta+\varepsilon)=c_B] \;\le\; \Phi\Bigl(\Phi^{-1}(p_B) + \tfrac{r}{\sigma}\Bigr). \]
Requiring the lower bound for $c_A$ to exceed the upper bound for all other classes gives
\[ \Phi\Bigl(\Phi^{-1}(p_A) - \tfrac{r}{\sigma}\Bigr) > \Phi\Bigl(\Phi^{-1}(p_B) + \tfrac{r}{\sigma}\Bigr) \quad\Longrightarrow\quad r < \frac{\sigma}{2}\bigl(\Phi^{-1}(p_A) - \Phi^{-1}(p_B)\bigr). \]
This is exactly the certified radius in Cohen et al.’s main theorem.
Conclusion
We have seen how the Gaussian shift bound—driven by the Neyman–Pearson lemma and reduction to one dimension—directly yields the dimension‑agnostic $\ell_2$ certificate of randomized smoothing. This elegant result underpins many extensions to anisotropic noise, other norms, and detection strategies.