# Exactly Computing the Local Lipschitz Constant of ReLU Networks

arXiv: https://arxiv.org/abs/2003.01219 · HTML: https://mlsanity.com/paper/2003.01219/

## Key facts

- Cited by 102 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Mar 2020.

## Built on by (most cited first, 30 of 102)

- [Learning Smooth Neural Functions via Lipschitz Regularization](https://mlsanity.com/paper/2202.08345/) (2022)
- [Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds](https://mlsanity.com/paper/2111.01395/) (2021)
- [Contrastive Adapters for Foundation Model Group Robustness](https://mlsanity.com/paper/2207.07180/) (2022)
- [Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation](https://mlsanity.com/paper/2210.07394/) (2022)
- [On Vanishing Gradients, Over-Smoothing, and Over-Squashing in GNNs: Bridging Recurrent and Graph Learning](https://mlsanity.com/paper/2502.10818/) (2025)
- [On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning](https://mlsanity.com/paper/2210.06443/) (2022)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Some Fundamental Aspects about Lipschitz Continuity of Neural Networks](https://mlsanity.com/paper/2302.10886/) (2023)
- [Measuring Generalization with Optimal Transport](https://mlsanity.com/paper/2106.03314/) (2021)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Parameterizing Activation Functions for Adversarial Robustness](https://mlsanity.com/paper/2110.05626/) (2021)
- [Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization](https://mlsanity.com/paper/2310.00116/) (2023)
- [Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram Iteration](https://mlsanity.com/paper/2305.16173/) (2023)
- [Improving the Accuracy-Robustness Trade-Off of Classifiers via Adaptive Smoothing](https://mlsanity.com/paper/2301.12554/) (2023)
- [LipBaB: Computing exact Lipschitz constant of ReLU networks](https://mlsanity.com/paper/2105.05495/) (2021)
- [A Quantitative Geometric Approach to Neural-Network Smoothness](https://mlsanity.com/paper/2203.01212/) (2022)
- [Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks](https://mlsanity.com/paper/2204.00846/) (2022)
- [Model Error Propagation via Learned Contraction Metrics for Safe Feedback Motion Planning of Unknown Systems](https://mlsanity.com/paper/2104.08695/) (2021)
- [Reliably-stabilizing piecewise-affine neural network controllers](https://mlsanity.com/paper/2111.07183/) (2021)
- [Instance-Dependent Generalization Bounds via Optimal Transport](https://mlsanity.com/paper/2211.01258/) (2022)
- [Gradient-Regularized Out-of-Distribution Detection](https://mlsanity.com/paper/2404.12368/) (2024)
- [Analytical bounds on the local Lipschitz constants of ReLU networks](https://mlsanity.com/paper/2104.14672/) (2021)
- [On the Impact of Hard Adversarial Instances on Overfitting in Adversarial Training](https://mlsanity.com/paper/2112.07324/) (2021)
- [Spelunking the Deep: Guaranteed Queries on General Neural Implicit Surfaces via Range Analysis](https://mlsanity.com/paper/2202.02444/) (2022)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [Stability Verification of Neural Network Controllers using Mixed-Integer Programming](https://mlsanity.com/paper/2206.13374/) (2022)
- [Learning-based Design of Luenberger Observers for Autonomous Nonlinear Systems](https://mlsanity.com/paper/2210.01476/) (2022)
- [Statistical Safety and Robustness Guarantees for Feedback Motion Planning of Unknown Underactuated Stochastic Systems](https://mlsanity.com/paper/2212.06874/) (2022)
- [On the Lipschitz Constant of Deep Networks and Double Descent](https://mlsanity.com/paper/2301.12309/) (2023)

## Abstract (arXiv)

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.