Laplace-Bridged Randomized Smoothing for Fast Certified Robustness

• URL: http://arxiv.org/abs/2604.24993v1
• Date: Mon, 27 Apr 2026 20:57:22 GMT
• Title: Laplace-Bridged Randomized Smoothing for Fast Certified Robustness
• Abstract summary: Laplace-Bridged Smoothing (LBS) is an analytic reformulation of Randomized Smoothing (RS)<n>On NVIDIA Jetson Orin Nano and Raspberry Pi 4, LBS achieves speedups of up to $494times$, enabling practical certified deployment on real-world edge devices.
• Score: 6.735531892653216
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Randomized Smoothing (RS) offers formal $\ell_2$ guarantees for arbitrary base classifiers but faces two key practical bottlenecks: (i) it often relies on noise-augmented training to achieve nontrivial certificates, which increases training cost, can reduce clean accuracy, and weakens RS as a genuinely post-hoc defense; and (ii) certification is computationally expensive, typically requiring tens of thousands of noisy forward passes per input, which hinders deployment, especially on resource-constrained edge devices. To address both limitations, we propose Laplace-Bridged Smoothing (LBS), an analytic reformulation of RS that replaces high-dimensional input-space Monte Carlo (MC) sampling with efficient computations in a low-dimensional probability space. LBS preserves formal robustness guarantees without requiring noise-augmented training while substantially reducing certification burden. On CIFAR-10 and ImageNet, LBS attains stronger certified robustness than RS and reduces per-sample certification cost by nearly an order of magnitude. Notably, on NVIDIA Jetson Orin Nano and Raspberry Pi 4, LBS achieves speedups of up to $494\times$, enabling practical certified deployment on real-world edge devices. Finally, we provide theoretical justification for the analytic formulation and certificate validity of LBS.

Related papers

• Halt Fast! Early Stopping for Certified Robustness [22.167611337327028]
  Randomized Smoothing (RS) provides rigorous guarantees for neural networks without architectural constraints.<n>Standard RS requires tens of thousands of model evaluations per input and forces practitioners to commit to fixed sample sizes a priori.<n>We present a novel meta-learning framework for anytime-valid certified robustness that adaptively deploys computational resources.
  arXiv  Detail & Related papers  (2026-06-26T03:41:58Z)
• Clipping Bottleneck: Stabilizing RLVR via Stochastic Recovery of Near-Boundary Signals [83.0127582612634]
  Near-boundary Rescue (NSR) is a minimal, plug-and-play modification that retains out-of-bound tokens to recover lost signals.<n>NSR substantially improves training stability and delivers consistent gains over strong baselines such as DAPO and GSPO.
  arXiv  Detail & Related papers  (2026-05-21T16:45:31Z)
• Efficient and Stable Reinforcement Learning for Diffusion Language Models [59.75789436018925]
  Reinforcement Learning (RL) is crucial for unlocking the complex reasoning capabilities of Diffusion-based Large Language Models (dLLMs)<n>Applying to dLLMs faces unique challenges in efficiency and stability.<n>We propose Spatio-Temporal Pruning (STP), a framework designed to simultaneously improve the efficiency and stability of RL for dLLMs.
  arXiv  Detail & Related papers  (2026-02-09T17:04:23Z)
• Cascading Robustness Verification: Toward Efficient Model-Agnostic Certification [1.6105236927161437]
  Incomplete verifiers scale efficiently and reduce the cost of robustness verification.<n>CRV is a model-agnostic verifier, meaning that its robustness guarantees are independent of the model's training process.<n>We show that CRV achieves equal or higher verified accuracy compared to powerful but computationally expensive incomplete verifiers.
  arXiv  Detail & Related papers  (2026-02-04T05:54:08Z)
• Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification [83.25968588249776]
  We present a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets.<n>With negligible computational overhead, $textttPT-LiRPA$ exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output.
  arXiv  Detail & Related papers  (2025-07-07T18:45:53Z)
• Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing [12.513566361816684]
  Implicit models such as Deep Equilibrium Models (DEQs) have emerged as promising alternative approaches for building deep neural networks. Existing certified defenses for DEQs employing deterministic certification methods can not certify on large-scale datasets. We provide the first randomized smoothing certified defense for DEQs to solve these limitations.
  arXiv  Detail & Related papers  (2024-11-01T06:14:11Z)
• Incremental Randomized Smoothing Certification [5.971462597321995]
  We show how to reuse the certification guarantees for the original smoothed model to certify an approximated model with very few samples. We experimentally demonstrate the effectiveness of our approach, showing up to 3x certification speedup over the certification that applies randomized smoothing of the approximate model from scratch.
  arXiv  Detail & Related papers  (2023-05-31T03:11:15Z)
• Smooth-Reduce: Leveraging Patches for Improved Certified Robustness [100.28947222215463]
  We propose a training-free, modified smoothing approach, Smooth-Reduce. Our algorithm classifies overlapping patches extracted from an input image, and aggregates the predicted logits to certify a larger radius around the input. We provide theoretical guarantees for such certificates, and empirically show significant improvements over other randomized smoothing methods.
  arXiv  Detail & Related papers  (2022-05-12T15:26:20Z)
• Input-Specific Robustness Certification for Randomized Smoothing [76.76115360719837]
  We propose Input-Specific Sampling (ISS) acceleration to achieve the cost-effectiveness for robustness certification. ISS can speed up the certification by more than three times at a limited cost of 0.05 certified radius.
  arXiv  Detail & Related papers  (2021-12-21T12:16:03Z)
• Certified Defense via Latent Space Randomized Smoothing with Orthogonal Encoders [13.723000245697866]
  We investigate the possibility of performing randomized smoothing and establishing the robust certification in the latent space of a network. We use modules, whose Lipschitz property is known for free by design, to propagate the certified radius estimated in the latent space back to the input space. Experiments on CIFAR10 and ImageNet show that our method achieves competitive robustness certified but with a significant improvement of efficiency during the test phase.
  arXiv  Detail & Related papers  (2021-08-01T16:48:43Z)
• Fast Certified Robust Training via Better Initialization and Shorter Warmup [95.81628508228623]
  We propose a new IBP and principled regularizers during the warmup stage to stabilize certified bounds. We find that batch normalization (BN) is a crucial architectural element to build best-performing networks for certified training.
  arXiv  Detail & Related papers  (2021-03-31T17:58:58Z)

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.