  In this paper, we study certifying the robustness of ReLU neural networks
against adversarial input perturbations. To diminish the relaxation error
suffered by the popular linear programming (LP) and semidefinite programming
(SDP) certification methods, we take a branch-and-bound approach to propose
partitioning the input uncertainty set and solving the relaxations on each part
separately. We show that this approach reduces relaxation error, and that the
error is eliminated entirely upon performing an LP relaxation with a partition
intelligently designed to exploit the nature of the ReLU activations. To scale
this approach to large networks, we consider using a coarser partition whereby
the number of parts in the partition is reduced. We prove that computing such a
coarse partition that directly minimizes the LP relaxation error is NP-hard. By
instead minimizing the worst-case LP relaxation error, we develop a closed-form
branching scheme. We extend the analysis to the SDP, where the feasible set
geometry is exploited to design a branching scheme that minimizes the
worst-case SDP relaxation error. Experiments on MNIST, CIFAR-10, and Wisconsin
breast cancer diagnosis classifiers demonstrate significant increases in the
percentages of test samples certified. By independently increasing the input
size and the number of layers, we empirically illustrate under which regimes
the branched LP and branched SDP are best applied.
