Certifying Incremental Quadratic Constraints for Neural Networks via
  Convex Optimization
  Abstracting neural networks with constraints they impose on their inputs and
outputs can be very useful in the analysis of neural network classifiers and to
derive optimization-based algorithms for certification of stability and
robustness of feedback systems involving neural networks. In this paper, we
propose a convex program, in the form of a Linear Matrix Inequality (LMI), to
certify incremental quadratic constraints on the map of neural networks over a
region of interest. These certificates can capture several useful properties
such as (local) Lipschitz continuity, one-sided Lipschitz continuity,
invertibility, and contraction. We illustrate the utility of our approach in
two different settings. First, we develop a semidefinite program to compute
guaranteed and sharp upper bounds on the local Lipschitz constant of neural
networks and illustrate the results on random networks as well as networks
trained on MNIST. Second, we consider a linear time-invariant system in
feedback with an approximate model predictive controller parameterized by a
neural network. We then turn the stability analysis into a semidefinite
feasibility program and estimate an ellipsoidal invariant set for the
closed-loop system.
