Compositional Estimation of Lipschitz Constants for Deep Neural Networks
Yuezhu Xu S. Sivaranjani
The Lipschitz constant plays a crucial role in certifying the robustness of
neural networks to input perturbations and adversarial attacks, as well as the
stability and safety of systems with neural network controllers. Therefore,
estimation of tight bounds on the Lipschitz constant of neural networks is a
well-studied topic. However, typical approaches involve solving a large matrix
verification problem, the computational cost of which grows significantly for
deeper networks. In this letter, we provide a compositional approach to
estimate Lipschitz constants for deep feedforward neural networks by obtaining
an exact decomposition of the large matrix verification problem into smaller
sub-problems. We further obtain a closed-form solution that applies to most
common neural network activation functions, which will enable rapid robustness
and stability certificates for neural networks deployed in online control
settings. Finally, we demonstrate through numerical experiments that our
approach provides a steep reduction in computation time while yielding
Lipschitz bounds that are very close to those achieved by state-of-the-art
approaches.