Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification

Abstract

We study certifying ReLU neural networks against adversarial input perturbations by partitioning the input uncertainty set and solving relaxations on each part. We show how intelligently designed branching can eliminate relaxation error for linear programs and reduce worst-case error for semidefinite programs. Experiments on MNIST, CIFAR-10, and Wisconsin breast-cancer classifiers demonstrate substantially higher certification rates.