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

Probably Approximately Global Robustness Certification

ICML 2025 · Adversarial robustness and security › Certified and empirical robustness · approach: Neural network robustness verification · 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 probably approximately global (PAG) robustness certification: an epsilon-net sample of iid inputs mapped to (robustness, confidence) space gives high-probability bounds on the probability of non-robust high-confidence predictions, and is agnostic to the local robustness oracle.

Problem

Formal verification of classifier robustness is intractable for large networks, while sampling-based and adversarial methods give no formal guarantees on global behavior; a quantitative, probabilistic global robustness guarantee is needed.

Approach

Relax global rho-kappa-robustness into a probabilistic statement, sample an epsilon-net over the 2D quality space of (robustness, confidence) pairs using iid samples and a local robustness oracle, and derive a confidence-to-robustness lower-bound map M(kappa) whose guarantees hold with high probability; sample size is independent of input dimension, number of classes, and learner.

Key results

• Across 230 experiments on 40 networks, 211/230 trials had estimators consistent with the guarantees for all confidence values; 19 violations observed, with 5/180 remaining trials (about 0.028) failing to generalize, close to delta=0.01.
• For VGG11_BN on CIFAR-10 with PGD oracle (epsilon=1e-4, delta=p_min=0.01, sample size 989534), the approach scales to a 10M-parameter network with runtimes of about 38.8 min (standard) and 308 min (TRADES) per verification run.
• The bounds clearly separate formal robustness of standard versus TRADES-trained networks.

Measured effects reported in the paper

Surprising findings

• Apparent guarantee violations were concentrated in a single validation split for FeedForward on MNIST, attributed to distribution shift from the Gaussian-noise sampling approximation.

Limitations

• Requires iid samples from the data distribution; the experiments approximate it with Gaussian-noise-perturbed validation data, which can weaken guarantees.
• Guarantees only hold for confidence values up to kappa_max observed frequently enough in the sample; no guarantee for higher-confidence regions.
• Runtime is dominated by per-sample local robustness checks, so tight parameters are costly for large models.

Experimental setup

Datasets: MNIST CIFAR-10

Benchmarks: MNIST CIFAR-10

Metrics: estimated conditional violation probability p_kappa worst-case p_hat vs epsilon/p_min number of counterexamples n_c map size |M| runtime

Baselines: PGD auto_LiRPA Marabou

Builds on: epsilon-nets from iid samples (Haussler-Welzl / Hoeffding-style sample complexit PGD auto_LiRPA TRADES

Closest papers by meaning

• Adversarial Training and Provable Robustness: A Tale of Two Objectives (AAAI 2021 · similarity 0.92)
• PROVEN: Verifying Robustness of Neural Networks with a Probabilistic Approach (ICML 2019 · similarity 0.91)
• Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation (NeurIPS 2017 · similarity 0.91)
• Fast Adversarial Robustness Certification of Nearest Prototype Classifiers for Arbitrary Seminorms (NeurIPS 2020 · similarity 0.90)
• Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers (NeurIPS 2019 · similarity 0.90)
• Learning Better Certified Models from Empirically-Robust Teachers (NeurIPS 2026 · similarity 0.89)