Exactly Computing the Local Lipschitz Constant of ReLU Networks

By Matt Jordan, A. Dimakis. 2020

147 citations recorded by the source corpus.

The Lipschitz constant of a neural network is a useful metric for provable robustness and generalization. We present a novel analytic result which relates gradient norms to Lipschitz constants for nondifferentiable functions. Next we prove hardness and inapproximability results for computing the local Lipschitz constant of ReLU neural networks. We develop a mixed-integer programming formulation to exactly compute the local Lipschitz constant for scalar and vector-valued networks. Finally, we apply our technique on networks trained on synthetic datasets and MNIST, drawing observations about the tightness of competing Lipschitz estimators and the effects of regularized training on Lipschitz constants.

Subfields: Artificial Intelligence, Computational Mechanics, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Alec Jacobson
2. Or Litany
3. Hsueh-Ti Derek Liu
4. Sanja Fidler
5. Francis Williams
6. Raquel Urtasun
7. Mohit Bansal
8. Jianfeng Gao

In Computational Mechanics

1. Sanja Fidler
2. Alec Jacobson
3. Or Litany
4. Francis Williams

In Electrical and Electronic Engineering

1. Or Litany
2. Sanja Fidler

Citations in the corpus

• Learning Smooth Neural Functions via Lipschitz Regularization (2022, methodology): “Several papers complement this subject by proposing more accurate methods to estimate the true Lipschitz constant, such as [Jordan and Dimakis 2020; Virmaux and Scaman 2018; Weng et al. 2018].”