Computing Trustworthy Robustness Certifications for Neural Network Safety.

A major hurdle in AI safety is the vulnerability of neural networks to adversarial examples—subtly altered inputs that cause misclassification. To counter this, researchers focus on robustness certifications, which define the maximum permissible distortion an input can withstand without changing the network's prediction. These certifications are typically represented as axis-aligned hyper-rectangles. While many existing methods aim to maximize the volume of these certifications, this approach is computationally intractable. This paper introduces a new metric called the apothem measure, demonstrating how to compute apothem-optimal certifications efficiently. This method requires a linear number of calls to a neural network verifier relative to the input domain's diameter, offering a significant improvement over volume-optimal algorithms. Furthermore, the research introduces "dual certifications," which are intervals encompassing all instances of a specific class, providing apothem-minimum upper bounds for robustness. The proposed ParallelepipedoNN system, evaluated on standard datasets like MNIST and Fashion MNIST, shows at least a twofold improvement in minimum edge length compared to prior work, enhancing the trustworthiness of safety guarantees.