  Randomized smoothing (RS) is a well known certified defense against
adversarial attacks, which creates a smoothed classifier by predicting the most
likely class under random noise perturbations of inputs during inference. While
initial work focused on robustness to $\ell_2$ norm perturbations using noise
sampled from a Gaussian distribution, subsequent works have shown that
different noise distributions can result in robustness to other $\ell_p$ norm
bounds as well. In general, a specific noise distribution is optimal for
defending against a given $\ell_p$ norm based attack. In this work, we aim to
improve the certified adversarial robustness against multiple perturbation
bounds simultaneously. Towards this, we firstly present a novel
\textit{certification scheme}, that effectively combines the certificates
obtained using different noise distributions to obtain optimal results against
multiple perturbation bounds. We further propose a novel \textit{training noise
distribution} along with a \textit{regularized training scheme} to improve the
certification within both $\ell_1$ and $\ell_2$ perturbation norms
simultaneously. Contrary to prior works, we compare the certified robustness of
different training algorithms across the same natural (clean) accuracy, rather
than across fixed noise levels used for training and certification. We also
empirically invalidate the argument that training and certifying the classifier
with the same amount of noise gives the best results. The proposed approach
achieves improvements on the ACR (Average Certified Radius) metric across both
$\ell_1$ and $\ell_2$ perturbation bounds.
