Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.06495 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915607419551744 |
|---|---|
| author | Blohm, Peter Indri, Patrick Gärtner, Thomas Malhotra, Sagar |
| author_facet | Blohm, Peter Indri, Patrick Gärtner, Thomas Malhotra, Sagar |
| contents | We propose and investigate probabilistic guarantees for the adversarial robustness of classification algorithms. While traditional formal verification approaches for robustness are intractable and sampling-based approaches do not provide formal guarantees, our approach is able to efficiently certify a probabilistic relaxation of robustness. The key idea is to sample an $ε$-net and invoke a local robustness oracle on the sample. Remarkably, the size of the sample needed to achieve probably approximately global robustness guarantees is independent of the input dimensionality, the number of classes, and the learning algorithm itself. Our approach can, therefore, be applied even to large neural networks that are beyond the scope of traditional formal verification. Experiments empirically confirm that it characterizes robustness better than state-of-the-art sampling-based approaches and scales better than formal methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06495 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Probably Approximately Global Robustness Certification Blohm, Peter Indri, Patrick Gärtner, Thomas Malhotra, Sagar Machine Learning We propose and investigate probabilistic guarantees for the adversarial robustness of classification algorithms. While traditional formal verification approaches for robustness are intractable and sampling-based approaches do not provide formal guarantees, our approach is able to efficiently certify a probabilistic relaxation of robustness. The key idea is to sample an $ε$-net and invoke a local robustness oracle on the sample. Remarkably, the size of the sample needed to achieve probably approximately global robustness guarantees is independent of the input dimensionality, the number of classes, and the learning algorithm itself. Our approach can, therefore, be applied even to large neural networks that are beyond the scope of traditional formal verification. Experiments empirically confirm that it characterizes robustness better than state-of-the-art sampling-based approaches and scales better than formal methods. |
| title | Probably Approximately Global Robustness Certification |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2511.06495 |