Certifying Incremental Quadratic Constraints for Neural Networks via Convex Optimization

Abstract

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.

arXiv commentAccepted for L4DC 2021

References in corpus (13)

• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Efficient Neural Network Robustness Certification with General Activation Functions
• Robust Large Margin Deep Neural Networks
• Semidefinite relaxations for certifying robustness to adversarial examples
• Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach
• Towards Fast Computation of Certified Robustness for ReLU Networks
• Robustness of classifiers: from adversarial to random noise
• Lipschitz constant estimation of Neural Networks via sparse polynomial optimization
• Exactly Computing the Local Lipschitz Constant of ReLU Networks
• Stability-certified reinforcement learning: A control-theoretic perspective
• Stability Analysis using Quadratic Constraints for Systems with Neural Network Controllers
• Reach-SDP: Reachability Analysis of Closed-Loop Systems with Neural Network Controllers via Semidefinite Programming
• Analytical bounds on the local Lipschitz constants of affine-ReLU functions