Semialgebraic Optimization for Lipschitz Constants of ReLU Networks
This work addresses the problem of efficiently computing Lipschitz constants for deep neural networks, which is crucial for applications like robustness certification and Wasserstein GANs, representing an incremental improvement over existing methods.
The authors tackled the problem of estimating Lipschitz constants for ReLU neural networks, which is important for robustness certification and GANs, by introducing a semidefinite programming hierarchy that combines polynomial lifting with a weak generalization of Putinar's positivity certificate. They demonstrated empirically that their method provides a trade-off with state-of-the-art linear programming approaches, achieving better bounds in some cases with less time.
The Lipschitz constant of a network plays an important role in many applications of deep learning, such as robustness certification and Wasserstein Generative Adversarial Network. We introduce a semidefinite programming hierarchy to estimate the global and local Lipschitz constant of a multiple layer deep neural network. The novelty is to combine a polynomial lifting for ReLU functions derivatives with a weak generalization of Putinar's positivity certificate. This idea could also apply to other, nearly sparse, polynomial optimization problems in machine learning. We empirically demonstrate that our method provides a trade-off with respect to state of the art linear programming approach, and in some cases we obtain better bounds in less time.