Research map / Adversarial robustness and security / Certified and empirical robustness
Should We Pay This Much for Robustness? Efficient Proxy Certificates with Marginal Guarantees
Sayed Soroush Haj Zargarbashi, Mohammad Sadegh Akhondzadeh, Aleksandar Bojchevski
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a framework that delegates robustness certification from an expensive sound certificate (e.g., randomized smoothing) to a cheap proxy function, with statistical control of the proxy's deviation from the original certificate.
Problem
Strong model-agnostic robustness certificates such as randomized smoothing require many (e.g., ~2000) forward passes per input, making them too expensive for deployment.
Approach
Delegate certification to a cheap proxy function while statistically controlling its deviation from the original sound certificate, yielding proxy certificates with marginal guarantees.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace randomized smoothing certification with ProxC standalone proxy | ResNet-50 randomized smoothing · ImageNet r=0.14 | certification forwards per image: 1950 -> 1 (1950x speedup) | Improved |
| use ProxC standalone instead of randomized smoothing | ResNet-50 randomized smoothing · ImageNet r=0.14 | certified accuracy (%): 56.08 -> 48.53 | Hurt |
| use ProxC as fallback invoking RS only when proxy rejects | ResNet-50 randomized smoothing · ImageNet r=0.14 | certified ratio (%): 70.06 -> 72.35 with 2.50x certification speedup | Improved |
| increase calibration Monte Carlo budget in ProxC-H (ablation) | ProxC-H on ViT + denoising · ImageNet r=0.50 | certified ratio (%): 39.2 -> 49.8 (K=1k -> 20k) | Improved |
| increase calibration Monte Carlo budget in ProxC-H (ablation) | ProxC-H on ViT + denoising · ImageNet r=0.75 | certified ratio (%): 21.5 -> 38.9 (K=5k -> 20k) | Improved |
| apply ProxC at larger radius | ProxC standalone on ViT · ImageNet | certified ratio gap to randomized smoothing: r=0.25: 78.96 vs 58.56; r=0.50: 68.44 vs 37.54 | Hurt |
| apply ProxC on text with edit-distance smoothing | RoBERTa-base AG-News · AG-News insertions | certified ratio (%): r=0: 98.5 -> 100.0; r=3: 61.8 -> 23.9 | Mixed |
Limitations
- Full text unavailable; limitations not determined from abstract
Experimental setup
Baselines: randomized smoothing
Builds on: randomized smoothing
Closest papers by meaning
- Robust Conformal Prediction with a Single Binary Certificate (ICLR 2025 · similarity 0.87)
- One Sample is Enough to Make Conformal Prediction Robust (NeurIPS 2025 · similarity 0.87)
- Incremental Randomized Smoothing Certification (ICLR 2024 · similarity 0.86)
- Provably Cost-Sensitive Adversarial Defense via Randomized Smoothing (ICML 2025 · similarity 0.86)
- Halt Fast! Early Stopping for Certified Robustness (NeurIPS 2026 · similarity 0.85)
- Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
