Exactly Computing the Local Lipschitz Constant of ReLU Networks

Abstract

The local Lipschitz constant of a neural network is a useful metric with applications in robustness, generalization, and fairness evaluation. We provide novel analytic results relating the local Lipschitz constant of nonsmooth vector-valued functions to a maximization over the norm of the generalized Jacobian. We present a sufficient condition for which backpropagation always returns an element of the generalized Jacobian, and reframe the problem over this broad class of functions. We show strong inapproximability results for estimating Lipschitz constants of ReLU networks, and then formulate an algorithm to compute these quantities exactly. We leverage this algorithm to evaluate the tightness of competing Lipschitz estimators and the effects of regularized training on the Lipschitz constant.

arXiv commentAccepted into NeurIPS 2020. Code: https://github.com/revbucket/lipMIP

References in corpus (14)

• Intriguing properties of neural networks
• An approach to reachability analysis for feed-forward ReLU neural networks
• Semidefinite relaxations for certifying robustness to adversarial examples
• Spectrally-normalized margin bounds for neural networks
• Parseval Networks: Improving Robustness to Adversarial Examples
• Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach
• Towards Fast Computation of Certified Robustness for ReLU Networks
• On the regularization of Wasserstein GANs
• Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability
• Deep ReLU Networks Have Surprisingly Few Activation Patterns
• Output Range Analysis for Deep Neural Networks
• Training individually fair ML models with Sensitive Subspace Robustness
• Fairness Through Awareness
• Provably Correct Automatic Subdifferentiation for Qualified Programs

Cited by in corpus (6)

• Training robust neural networks using Lipschitz bounds
• NASGEM: Neural Architecture Search via Graph Embedding Method
• Certifying Incremental Quadratic Constraints for Neural Networks via Convex Optimization
• Learning Safe Neural Network Controllers with Barrier Certificates
• Analytical bounds on the local Lipschitz constants of affine-ReLU functions
• Statistically Optimal Generative Modeling with Maximum Deviation from the Empirical Distribution