Research map / Adversarial robustness and security / Certified and empirical robustness

Halt Fast! Early Stopping for Certified Robustness

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

Read the paperCheck your idea against 108,967 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 meta-learned, anytime-valid E-process for randomized smoothing certification that predicts per-image Beta mixture priors from a Phase I glimpse, cutting samples substantially while allowing adaptive early exits.

Problem

Randomized smoothing certification needs tens of thousands of Monte Carlo samples per input and fixed sample sizes chosen a priori, since peeking invalidates Clopper-Pearson bounds.

Approach

Uses anytime-valid E-values with a mixture-of-truncated-Beta prior whose parameters are predicted per image by a lightweight meta-learner trained with a Kelly-style NLL objective on a Phase I glimpse, plus bankruptcy, UCB and plateau early exits and a 1% KT safety anchor.

Key results

• Meta-1-Margin-Hybrid achieves comparable certified accuracy to Cohen-10k on CIFAR-10 at sigma=0.25 (72.2-74.0% vs 78.8%) with about 660-680 average samples versus 10,000 (roughly 15x fewer).
• Relaxed Tiered Cascade on CIFAR-10 (sigma=1.0, triage) uses 710.5 average samples versus 1,733.2 for the KT prior, a 2.4x speedup.
• Early rejection-only mode gives up to 45x speedup for rejections with a small drop in certified radius (e.g., MNIST sigma=0.25 exit 200 vs 350 samples for KT).

Surprising findings

• The anytime-valid bounds lose certification performance relative to Cohen-10k, and the paper notes the tax of anytime validity is a marginal cost on radius tightness.
• Zero-shot transfer: a meta-learner trained only on CIFAR-10 shows correlated termination latencies on ImageNet.

Limitations

• Anytime-valid bounds are looser than fixed-horizon Clopper-Pearson at the same N, reducing certified radius.
• Results reported as 20x-45x speedups are relative to a 10k-sample baseline and in some settings the KT baseline is only modestly beaten (8-15% reduction).
• Experiments limited to l2 randomized smoothing on three datasets with ResNet backbones; hyperparameters (aggression factor, epsilon, bias) were tuned via sweeps on the same evaluation setup.

Experimental setup

Datasets: MNIST CIFAR-10 ImageNet

Benchmarks: MNIST CIFAR-10 ImageNet

Metrics: certified accuracy average sample count mean radius radius discrepancy vs Cohen-10k

Baselines: Cohen-10k Cohen-1k KT prior mixture-of-mixtures

Builds on: Randomized Smoothing (Cohen et al.) test martingales Krichevsky-Trofimov estimator Clopper-Pearson interval MACER

Closest papers by meaning

• Incremental Randomized Smoothing Certification (ICLR 2024 · similarity 0.89)
• Sparse Transfer Learning Accelerates and Enhances Certified Robustness: A Comprehensive Study (AAAI 2025 · similarity 0.88)
• Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing (NeurIPS 2024 · similarity 0.88)
• Probably Approximately Global Robustness Certification (ICML 2025 · similarity 0.88)
• Certified Adversarial Robustness via Randomized $\alpha$-Smoothing for Regression Models (NeurIPS 2024 · similarity 0.86)
• Certified but Private: Scalable Zero-Knowledge Proofs for the Formal Verification of Neural Networks (NeurIPS 2026 · similarity 0.86)