We introduce LiPopt, a polynomial optimization framework for computing increasingly tighter upper bound on the Lipschitz constant of neural networks. The underlying optimization problems boil down to either linear (LP) or semidefinite (SDP) programming. We show how to use the sparse connectivity of a network, to significantly reduce the complexity of computation. This is specially useful for convolutional as well as pruned neural networks. We conduct experiments on networks with random weights as well as networks trained on MNIST, showing that in the particular case of the $\ell_\infty$-Lipschitz constant, our approach yields superior estimates as compared to other baselines available in the literature.
 We consider a neural network f d defined by the recursion: for an integer d larger than 1, matrices of appropriate dimensions and an activation function σ, understood to be applied element-wise. We refer to d as the depth, and we focus on the case where f d has a single real value as output. In this work, we address the problem of estimating the Lipschitz constant of the network f d . A function f is Lipschitz continuous with respect to a norm · if there exists a constant L such that for all x, y we have |f (x) − f (y)| ≤ L x − y . The minimum over all such values satisfying this condition is called the Lipschitz constant of f and is denoted by L(f ). The Lipschitz constant of a neural network is of major importance in many successful applications of deep learning. In the context of supervised learning, Bartlett et al. (2017) show how it directly correlates with the generalization ability of neural network classifiers, suggesting it as model complexity measure. It also provides a measure of robustness against adversarial perturbations (Szegedy et al., 2014) and can be used to improve such metric (Cisse et al., 2017) . Moreover, an upper bound on L(f d ) provides a certificate of robust classification around data points (Weng et al., 2018) . Another example is the discriminator network of the Wasserstein GAN , whose Lipschitz constant is constrained to be at most 1. To handle this constraint, researchers have proposed different methods like heuristic penalties (Gulrajani et al., 2017) , upper bounds (Miyato et al., 2018) , choice of activation function (Anil et al., 2019) , among many others. This line of work has shown that accurate estimation of such constant is key to generating high quality images. Lower bounds or heuristic estimates of L(f d ) can be used to provide a general sense of how robust a network is, but fail to provide true certificates of robustness to input perturbations. Such certificates require true upper bounds, and are paramount when deploying safety-critical deep reinforcement learning applications (Berkenkamp et al., 2017; Jin & Lavaei, 2018) . The trivial upper bound given by the product of layer-wise Lipschitz constants is easy to compute but rather loose and overly pessimistic, providing poor insight into the true robustness of a network (Huster et al., 2018) . Indeed, there is a growing need for methods that provide tighter upper bounds on L(f d ), even at the expense of increased complexity. For example Raghunathan et al. (2018a) ; Jin & Lavaei (2018) ; Fazlyab et al. (2019) derive upper bounds based on semidefinite programming (SDP). While expensive to compute, these type of certificates are in practice surprisingly tight. Our work belongs in this vein of research, and aims to overcome some limitations in the current state-of-the-art.
LP-based upper bounds on the Lipschitz constant of Neural Networks The authors study the problem of estimating the Lipschitz constant of a deep neural network with ELO activation function, formulating it as a polynomial optimisation problem.