AI Paper Atlas

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

NeurIPS 2026 · Adversarial robustness and security › Certified and empirical robustness · approach: Randomized smoothing certification · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
replace randomized smoothing certification with ProxC standalone proxyResNet-50 randomized smoothing · ImageNet r=0.14certification forwards per image: 1950 -> 1 (1950x speedup)Improved
use ProxC standalone instead of randomized smoothingResNet-50 randomized smoothing · ImageNet r=0.14certified accuracy (%): 56.08 -> 48.53Hurt
use ProxC as fallback invoking RS only when proxy rejectsResNet-50 randomized smoothing · ImageNet r=0.14certified ratio (%): 70.06 -> 72.35 with 2.50x certification speedupImproved
increase calibration Monte Carlo budget in ProxC-H (ablation)ProxC-H on ViT + denoising · ImageNet r=0.50certified 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.75certified ratio (%): 21.5 -> 38.9 (K=5k -> 20k)Improved
apply ProxC at larger radiusProxC standalone on ViT · ImageNetcertified ratio gap to randomized smoothing: r=0.25: 78.96 vs 58.56; r=0.50: 68.44 vs 37.54Hurt
apply ProxC on text with edit-distance smoothingRoBERTa-base AG-News · AG-News insertionscertified ratio (%): r=0: 98.5 -> 100.0; r=3: 61.8 -> 23.9Mixed

Limitations

Experimental setup

Baselines: randomized smoothing

Builds on: randomized smoothing

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy