Probably Approximately Global Robustness Certification
Peter Blohm, Patrick Indri, Thomas Gärtner, and 1 more author
In International Conference on Machine Learning (ICML), 2025
ICML 2025 Poster
We propose probabilistic guarantees for adversarial robustness of classification algorithms. Traditional formal verification is often intractable for modern models, while sampling-only approaches lack formal guarantees. Our method samples an epsilon-net and evaluates a local robustness oracle on the sample, yielding probably approximately global robustness guarantees. The required sample size is independent of input dimensionality, number of classes, and learning algorithm, which enables application to larger neural networks than typical formal global verification methods. Experiments show that the approach better characterizes robustness than prior sampling-based baselines and scales favorably compared with formal methods.