ML Security PapersLaplace-Bridged Randomized Smoothing for Fast Certified Robustness
Miao Lin 1, MD Saifur Rahman Mazumder 2, Feng Yu 2, Daniel Takabi 1, Rui Ning 1
Published on arXiv
2604.24993
Input Manipulation Attack
OWASP ML Top 10 — ML01
Key Finding
Achieves up to 494× certification speedup on edge devices while attaining stronger certified robustness than standard randomized smoothing, eliminating the need for noise-augmented training
Laplace-Bridged Smoothing (LBS)
Novel technique introduced
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.
Key Contributions
- Analytic reformulation of randomized smoothing that replaces Monte Carlo sampling with efficient low-dimensional probability space computations
- Achieves stronger certified robustness than standard RS without requiring noise-augmented training
- Reduces per-sample certification cost by nearly 10× on CIFAR-10/ImageNet and up to 494× on edge devices (Jetson Orin Nano, Raspberry Pi 4)
🛡️ Threat Analysis
Proposes a certified defense against adversarial examples (input manipulation attacks) using randomized smoothing with formal ℓ2 robustness guarantees.