Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing

• URL: http://arxiv.org/abs/2404.09586v4
• Date: Sat, 15 Jun 2024 11:14:36 GMT
• Title: Mitigating the Curse of Dimensionality for Certified Robustness via Dual Randomized Smoothing
• Authors: Song Xia, Yi Yu, Xudong Jiang, Henghui Ding,
• Abstract summary: This paper explores the feasibility of providing $ell$ certified robustness for high-dimensional input through the utilization of dual smoothing. The proposed Dual Smoothing (DRS) down-samples the input image into two sub-images and smooths the two sub-images in lower dimensions. Extensive experiments demonstrate the generalizability and effectiveness of DRS, which exhibits a notable capability to integrate with established methodologies.
• Score: 48.219725131912355
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Effects of Exponential Gaussian Distribution on (Double Sampling) Randomized Smoothing [21.618349628349115]
  We study the effect of two families of distributions, named Exponential Standard Gaussian (ESG) and Exponential General Gaussian (EGG) distributions, on Randomized Smoothing and Double Randomized Smoothing (DSRS) Our experiments on real-world datasets confirm our theoretical analysis of the ESG, that they provide almost the same certification under different exponents $eta$ for both RS and DSRS. Compared to the primitive DSRS, the increase in certified accuracy provided by EGG is prominent, up to 6.4% on ImageNet.
  arXiv  Detail & Related papers  (2024-06-04T13:41:00Z)
• DiffIR: Efficient Diffusion Model for Image Restoration [108.82579440308267]
  Diffusion model (DM) has achieved SOTA performance by modeling the image synthesis process into a sequential application of a denoising network. Traditional DMs running massive iterations on a large model to estimate whole images or feature maps is inefficient for image restoration. We propose DiffIR, which consists of a compact IR prior extraction network (CPEN), dynamic IR transformer (DIRformer), and denoising network.
  arXiv  Detail & Related papers  (2023-03-16T16:47:14Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Double Sampling Randomized Smoothing [19.85592163703077]
  We propose a Double Sampling Randomized Smoothing framework. It exploits the sampled probability from an additional smoothing distribution to tighten the robustness certification of the previous smoothed classifier. We show that DSRS certifies larger robust radii than existing datasets consistently under different settings.
  arXiv  Detail & Related papers  (2022-06-16T04:34:28Z)
• Robust and Accurate -- Compositional Architectures for Randomized Smoothing [5.161531917413708]
  We propose a compositional architecture, ACES, which certifiably decides on a per-sample basis whether to use a smoothed model yielding predictions with guarantees or a more accurate standard model without guarantees. This, in contrast to prior approaches, enables both high standard accuracies and significant provable robustness.
  arXiv  Detail & Related papers  (2022-04-01T14:46:25Z)
• Certifiably Robust Interpretation via Renyi Differential Privacy [77.04377192920741]
  We study the problem of interpretation robustness from a new perspective of Renyi differential privacy (RDP) First, it can offer provable and certifiable top-$k$ robustness. Second, our proposed method offers $sim10%$ better experimental robustness than existing approaches. Third, our method can provide a smooth tradeoff between robustness and computational efficiency.
  arXiv  Detail & Related papers  (2021-07-04T06:58:01Z)
• Higher-Order Certification for Randomized Smoothing [78.00394805536317]
  We propose a framework to improve the certified safety region for smoothed classifiers. We provide a method to calculate the certified safety region using $0th$-order and $1st$-order information. We also provide a framework that generalizes the calculation for certification using higher-order information.
  arXiv  Detail & Related papers  (2020-10-13T19:35:48Z)
• Improve the Robustness and Accuracy of Deep Neural Network with $L_{2,\infty}$ Normalization [0.0]
  The robustness and accuracy of the deep neural network (DNN) was enhanced by introducing the $L_2,infty$ normalization. It is proved that the $L_2,infty$ normalization leads to large dihedral angles between two adjacent faces of the polyhedron graph of the DNN function.
  arXiv  Detail & Related papers  (2020-10-10T05:45:45Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.