Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing
It addresses the problem of certified robustness for high-dimensional inputs in machine learning security, offering a novel method that is incremental but integrates well with existing techniques.
This paper tackles the curse of dimensionality in Randomized Smoothing for certified robustness in image classifiers by proposing Dual Randomized Smoothing, which down-samples images into sub-images and smooths them in lower dimensions, achieving a superior upper bound on the robustness radius that decreases at a rate of (1/√m + 1/√n) instead of 1/√d, with experiments showing substantial improvements in accuracy and robustness on CIFAR-10 and ImageNet.
Randomized Smoothing (RS) has been proven a promising method for endowing an arbitrary image classifier with certified robustness. However, the substantial uncertainty inherent in the high-dimensional isotropic Gaussian noise imposes the curse of dimensionality on RS. Specifically, the upper bound of ${\ell_2}$ certified robustness radius provided by RS exhibits a diminishing trend with the expansion of the input dimension $d$, proportionally decreasing at a rate of $1/\sqrt{d}$. This paper explores the feasibility of providing ${\ell_2}$ certified robustness for high-dimensional input through the utilization of dual smoothing in the lower-dimensional space. The proposed Dual Randomized Smoothing (DRS) down-samples the input image into two sub-images and smooths the two sub-images in lower dimensions. Theoretically, we prove that DRS guarantees a tight ${\ell_2}$ certified robustness radius for the original input and reveal that DRS attains a superior upper bound on the ${\ell_2}$ robustness radius, which decreases proportionally at a rate of $(1/\sqrt m + 1/\sqrt n )$ with $m+n=d$. Extensive experiments demonstrate the generalizability and effectiveness of DRS, which exhibits a notable capability to integrate with established methodologies, yielding substantial improvements in both accuracy and ${\ell_2}$ certified robustness baselines of RS on the CIFAR-10 and ImageNet datasets. Code is available at https://github.com/xiasong0501/DRS.