Black-Box Certification with Randomized Smoothing: A Functional
  Optimization Based Framework
  Randomized classifiers have been shown to provide a promising approach for
achieving certified robustness against adversarial attacks in deep learning.
However, most existing methods only leverage Gaussian smoothing noise and only
work for $\ell_2$ perturbation. We propose a general framework of adversarial
certification with non-Gaussian noise and for more general types of attacks,
from a unified functional optimization perspective. Our new framework allows us
to identify a key trade-off between accuracy and robustness via designing
smoothing distributions, helping to design new families of non-Gaussian
smoothing distributions that work more efficiently for different $\ell_p$
settings, including $\ell_1$, $\ell_2$ and $\ell_\infty$ attacks. Our proposed
methods achieve better certification results than previous works and provide a
new perspective on randomized smoothing certification.
