Randomized smoothing at high confidence: the Gaussian is optimal for every noise law

Randomized smoothing certifies a classifier by averaging a base classifier over a noise law $q$ on $\mathbb{R}^d$. We consider certificates that hold for every base classifier and require only that the top class has probability at least $1-\alpha$ under the noise. We prove that if $\mathbb{E}\|\eta\|_2^2\le d\sigma^2$ for $\eta\sim q$, then for $0<\alpha<1/4$ and $d\ge 1012\,\alpha^{-2}\log(16/\alpha)$ no such certificate exceeds $8\sigma\sqrt{\log(16/\alpha)}\,d^{1/p-1/2}$ in the $\ell_p$ norm, $2\le p\le\infty$. The Gaussian $N(0,\sigma^2 I)$ certifies $\sigma\Phi^{-1}(1-\alpha)\,d^{1/p-1/2}$, so it is optimal up to an absolute constant factor at every confidence level. Earlier bounds for general noise laws allow the certified radius at fixed noise level to grow like $\alpha^{-1/2}$ as $\alpha\to0$; the correct rate is $(\log 1/\alpha)^{1/2}$. The proof uses only the second moment of $q$: no product structure, symmetry, density or log-concavity.