Semialgebraic Optimization for Lipschitz Constants of ReLU Networks
arXiv:2002.03657
Abstract
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.
arXiv commentNeurIPS 2020
References in corpus (9)
- Spectral Normalization for Generative Adversarial Networks
- Provable defenses against adversarial examples via the convex outer adversarial polytope
- Certified Defenses against Adversarial Examples
- Evaluating Robustness of Neural Networks with Mixed Integer Programming
- Semidefinite relaxations for certifying robustness to adversarial examples
- Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach
- Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks
- Lipschitz constant estimation of Neural Networks via sparse polynomial optimization
- Provably Correct Automatic Subdifferentiation for Qualified Programs