# Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 78 references that are in the map.
- First posted on arXiv 13 Oct 2022.

## Builds on (most cited first, 30 of 43)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Regularisation of Neural Networks by Enforcing Lipschitz Continuity](https://mlsanity.com/paper/1804.04368/) (2018)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks](https://mlsanity.com/paper/1802.04034/) (2018)
- [Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers](https://mlsanity.com/paper/2011.13824/) (2020)
- [Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation](https://mlsanity.com/paper/1705.08475/) (2017)
- [Formal Security Analysis of Neural Networks using Symbolic Intervals](https://mlsanity.com/paper/1804.10829/) (2018)
- [Efficient Formal Safety Analysis of Neural Networks](https://mlsanity.com/paper/1809.08098/) (2018)
- [Branch and Bound for Piecewise Linear Neural Network Verification](https://mlsanity.com/paper/1909.06588/) (2019)
- [A Dual Approach to Scalable Verification of Deep Networks](https://mlsanity.com/paper/1803.06567/) (2018)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [General Cutting Planes for Bound-Propagation-Based Neural Network Verification](https://mlsanity.com/paper/2208.05740/) (2022)
- [Exactly Computing the Local Lipschitz Constant of ReLU Networks](https://mlsanity.com/paper/2003.01219/) (2020)
- [Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks](https://mlsanity.com/paper/1911.00937/) (2019)
- [Lipschitz constant estimation of Neural Networks via sparse polynomial optimization](https://mlsanity.com/paper/2004.08688/) (2020)
- [Robustness Verification for Transformers](https://mlsanity.com/paper/2002.06622/) (2020)
- [Skew Orthogonal Convolutions](https://mlsanity.com/paper/2105.11417/) (2021)
- [Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds](https://mlsanity.com/paper/2111.01395/) (2021)
- [Certified Monotonic Neural Networks](https://mlsanity.com/paper/2011.10219/) (2020)

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

- [Neural Network Verification with Branch-and-Bound for General Nonlinearities](https://mlsanity.com/paper/2405.21063/) (2024)
- [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)
- [Performance Scaling via Optimal Transport: Enabling Data Selection from Partially Revealed Sources](https://mlsanity.com/paper/2307.02460/) (2023)
- [Verification of Neural Control Barrier Functions with Symbolic Derivative Bounds Propagation](https://mlsanity.com/paper/2410.16281/) (2024)
- [ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks](https://mlsanity.com/paper/2404.04375/) (2024)
- [Lipschitz constant estimation for general neural network architectures using control tools](https://mlsanity.com/paper/2405.01125/) (2024)
- [Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted Activations](https://mlsanity.com/paper/2401.14033/) (2024)
- [Stability and Generalization in Free Adversarial Training](https://mlsanity.com/paper/2404.08980/) (2024)
- [Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Loss](https://mlsanity.com/paper/2505.15174/) (2025)
- [Hybrid Zonotopes Exactly Represent ReLU Neural Networks](https://mlsanity.com/paper/2304.02755/) (2023)
- [Policy Verification in Stochastic Dynamical Systems Using Logarithmic Neural Certificates](https://mlsanity.com/paper/2406.00826/) (2024)
- [Provable Bounds on the Hessian of Neural Networks: Derivative-Preserving Reachability Analysis](https://mlsanity.com/paper/2406.04476/) (2024)
- [Upper and lower bounds for the Lipschitz constant of random neural networks](https://mlsanity.com/paper/2311.01356/) (2023)
- [A Variational Perspective on High-Resolution ODEs](https://mlsanity.com/paper/2311.02002/) (2023)
- [Learning conditional distributions on continuous spaces](https://mlsanity.com/paper/2406.09375/) (2024)
- [Estimating Neural Network Robustness via Lipschitz Constant and Architecture Sensitivity](https://mlsanity.com/paper/2410.23382/) (2024)
- [Distance-Aware Error for Spline Networks: A Bottom-Up Approach to Uncertainty](https://mlsanity.com/paper/2501.04757/) (2025)
- [Adaptive Branch-and-Bound Tree Exploration for Neural Network Verification](https://mlsanity.com/paper/2505.00963/) (2025)
- [TAROT: Towards Essentially Domain-Invariant Robustness with Theoretical Justification](https://mlsanity.com/paper/2505.06580/) (2025)
- [Local Stability and Region of Attraction Analysis for Neural Network Feedback Systems under Positivity Constraints](https://mlsanity.com/paper/2505.22889/) (2025)
- [Scalable Verification of Neural Control Barrier Functions Using Linear Bound Propagation](https://mlsanity.com/paper/2511.06341/) (2025)
- [A mathematical certification for positivity conditions in Neural Networks with applications to partial monotonicity and Trustworthy AI](https://mlsanity.com/paper/2406.08525/) (2024)
- [Provably Safeguarding a Classifier from OOD and Adversarial Samples: an Extreme Value Theory Approach](https://mlsanity.com/paper/2501.10202/) (2025)
- [ECLipsE-Gen-Local: Efficient Compositional Local Lipschitz Estimates for Deep Neural Networks](https://mlsanity.com/paper/2510.05261/) (2025)
- [ExLipBaB: Exact Lipschitz Constant Computation for Piecewise Linear Neural Networks](https://mlsanity.com/paper/2602.15499/) (2026)
- [Fitting Is Not Enough: Smoothness in Extremely Quantized LLMs](https://mlsanity.com/paper/2605.08894/) (2026)
- [Measuring Model Robustness via Fisher Information: Spectral Bounds, Theoretical Guarantees, and Practical Algorithms](https://mlsanity.com/paper/2606.04767/) (2026)
- [CQnet: convex-geometric interpretation and constraining neural-network trajectories](https://mlsanity.com/paper/2302.10895/) (2023)

## Abstract (arXiv)

Lipschitz constants are connected to many properties of neural networks, such as robustness, fairness, and generalization. Existing methods for computing Lipschitz constants either produce relatively loose upper bounds or are limited to small networks. In this paper, we develop an efficient framework for computing the ℓ_∞ local Lipschitz constant of a neural network by tightly upper bounding the norm of Clarke Jacobian via linear bound propagation. We formulate the computation of local Lipschitz constants with a linear bound propagation process on a high-order backward graph induced by the chain rule of Clarke Jacobian. To enable linear bound propagation, we derive tight linear relaxations for specific nonlinearities in Clarke Jacobian. This formulate unifies existing ad-hoc approaches such as RecurJac, which can be seen as a special case of ours with weaker relaxations. The bound propagation framework also allows us to easily borrow the popular Branch-and-Bound (BaB) approach from neural network verification to further tighten Lipschitz constants. Experiments show that on tiny models, our method produces comparable bounds compared to exact methods that cannot scale to slightly larger models; on larger models, our method efficiently produces tighter results than existing relaxed or naive methods, and our method scales to much larger practical models that previous works could not handle. We also demonstrate an application on provable monotonicity analysis. Code is available at https://github.com/shizhouxing/Local-Lipschitz-Constants.