  Randomized smoothing is a recently proposed defense against adversarial
attacks that has achieved SOTA provable robustness against $\ell_2$
perturbations. A number of publications have extended the guarantees to other
metrics, such as $\ell_1$ or $\ell_\infty$, by using different smoothing
measures. Although the current framework has been shown to yield near-optimal
$\ell_p$ radii, the total safety region certified by the current framework can
be arbitrarily small compared to the optimal. In this work, we propose a
framework to improve the certified safety region for these smoothed classifiers
without changing the underlying smoothing scheme. The theoretical contributions
are as follows: 1) We generalize the certification for randomized smoothing by
reformulating certified radius calculation as a nested optimization problem
over a class of functions. 2) We provide a method to calculate the certified
safety region using $0^{th}$-order and $1^{st}$-order information for
Gaussian-smoothed classifiers. We also provide a framework that generalizes the
calculation for certification using higher-order information. 3) We design
efficient, high-confidence estimators for the relevant statistics of the
first-order information. Combining the theoretical contribution 2) and 3)
allows us to certify safety region that are significantly larger than the ones
provided by the current methods. On CIFAR10 and Imagenet datasets, the new
regions certified by our approach achieve significant improvements on general
$\ell_1$ certified radii and on the $\ell_2$ certified radii for color-space
attacks ($\ell_2$ restricted to 1 channel) while also achieving smaller
improvements on the general $\ell_2$ certified radii. Our framework can also
provide a way to circumvent the current impossibility results on achieving
higher magnitude of certified radii without requiring the use of data-dependent
smoothing techniques.
