Lipschitz constant estimation of Neural Networks via sparse polynomial optimization

We introduce LiPopt, a polynomial optimization framework for computing\nincreasingly tighter upper bounds on the Lipschitz constant of neural networks.\nThe underlying optimization problems boil down to either linear (LP) or\nsemidefinite (SDP) programming. We show how to use the sparse connectivity of a\nnetwork, to significantly reduce the complexity of computation. This is\nspecially useful for convolutional as well as pruned neural networks. We\nconduct experiments on networks with random weights as well as networks trained\non MNIST, showing that in the particular case of the $\\ell_\\infty$-Lipschitz\nconstant, our approach yields superior estimates, compared to baselines\navailable in the literature.\n