Tight Certified Robustness via Min-Max Representations of ReLU Neural
  Networks
Brendon G. Anderson Samuel Pfrommer Somayeh Sojoudi
The reliable deployment of neural networks in control systems requires
rigorous robustness guarantees. In this paper, we obtain tight robustness
certificates over convex attack sets for min-max representations of ReLU neural
networks by developing a convex reformulation of the nonconvex certification
problem. This is done by "lifting" the problem to an infinite-dimensional
optimization over probability measures, leveraging recent results in
distributionally robust optimization to solve for an optimal discrete
distribution, and proving that solutions of the original nonconvex problem are
generated by the discrete distribution under mild boundedness, nonredundancy,
and Slater conditions. As a consequence, optimal (worst-case) attacks against
the model may be solved for exactly. This contrasts prior state-of-the-art that
either requires expensive branch-and-bound schemes or loose relaxation
techniques. Experiments on robust control and MNIST image classification
examples highlight the benefits of our approach.