  Convex relaxations have emerged as a promising approach for verifying
desirable properties of neural networks like robustness to adversarial
perturbations. Widely used Linear Programming (LP) relaxations only work well
when networks are trained to facilitate verification. This precludes
applications that involve verification-agnostic networks, i.e., networks not
specially trained for verification. On the other hand, semidefinite programming
(SDP) relaxations have successfully be applied to verification-agnostic
networks, but do not currently scale beyond small networks due to poor time and
space asymptotics. In this work, we propose a first-order dual SDP algorithm
that (1) requires memory only linear in the total number of network
activations, (2) only requires a fixed number of forward/backward passes
through the network per iteration. By exploiting iterative eigenvector methods,
we express all solver operations in terms of forward and backward passes
through the network, enabling efficient use of hardware like GPUs/TPUs. For two
verification-agnostic networks on MNIST and CIFAR-10, we significantly improve
L-inf verified robust accuracy from 1% to 88% and 6% to 40% respectively. We
also demonstrate tight verification of a quadratic stability specification for
the decoder of a variational autoencoder.
