Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications

Robustness certification aims to determine the maximum distortion an input can undergo without changing a neural network's classification. While many existing methods attempt to maximize the volume of these certification regions, such computations are often intractable. This paper investigates whether alternative geometric measures can provide more reliable and efficient safety guarantees for neural networks.

The authors introduce the 'apothem' measure—defined as the minimum slack between an input and the faces of its surrounding hyper-rectangle—as a more tractable alternative to volume. They develop the ParallelepipedoNN system, which utilizes a 'small-step' operator to iteratively refine robustness intervals by querying a neural network verifier (oracle). The system also implements 'dual certifications' to provide upper bounds on robustness, allowing researchers to determine if a network's failure to meet a safety threshold is due to the network itself or the limitations of the certification method.

The study proves that while volume-optimal certification is impossible to achieve in polynomial time via oracle-based algorithms, apothem-optimal certifications can be computed in a linear number of oracle calls relative to the input domain's diameter. Empirical evaluation on MNIST and Fashion MNIST datasets demonstrates that the ParallelepipedoNN system achieves at least a two-fold improvement in minimum edge length compared to existing methods, providing a more precise and computationally feasible approach to verifying neural network stability.

This research addresses a critical bottleneck in AI safety: the trade-off between the accuracy of safety guarantees and the computational cost of calculating them. By shifting the focus from volume to the apothem, the authors provide a practical framework that allows developers to distinguish between a truly non-robust network and an overly conservative certification, ultimately leading to more trustworthy AI systems.