# Local Lipschitz Constant Computation of ReLU-FNNs: Upper Bound Computation with Exactness Verification

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 27 references that are in the map.
- First posted on arXiv 17 Oct 2023.

## Builds on (most cited first, 11 of 11)

- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming](https://mlsanity.com/paper/1903.01287/) (2019)
- [Robust Physical-World Attacks on Deep Learning Models](https://mlsanity.com/paper/1707.08945/) (2017)
- [Stability Analysis using Quadratic Constraints for Systems with Neural Network Controllers](https://mlsanity.com/paper/2006.07579/) (2020)
- [On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples](https://mlsanity.com/paper/2006.06759/) (2020)
- [l2 Induced Norm Analysis of Discrete-Time LTI Systems for Nonnegative Input Signals and Its Application to Stability Analysis of Recurrent Neural Networks](https://mlsanity.com/paper/2011.12726/) (2020)
- [Dissipativity and Integral Quadratic Constraints, Tailored computational robustness tests for complex interconnections](https://mlsanity.com/paper/2105.07401/) (2021)
- [Stability Analysis of Recurrent Neural Networks by IQC with Copositive Mutipliers](https://mlsanity.com/paper/2202.04592/) (2022)
- [Dissipativity, Convexity and Tight O'Shea-Zames-Falb Multipliers for Safety Guarantees](https://mlsanity.com/paper/2207.01363/) (2022)

## Built on by (most cited first, 2 of 2)

- [KKL Observer Synthesis for Nonlinear Systems via Physics-Informed Learning](https://mlsanity.com/paper/2501.11655/) (2025)
- [Upper and lower bounds for the Lipschitz constant of random neural networks](https://mlsanity.com/paper/2311.01356/) (2023)

## Abstract (arXiv)

This paper is concerned with the computation of the local Lipschitz constant of feedforward neural networks (FNNs) with activation functions being rectified linear units (ReLUs). The local Lipschitz constant of an FNN for a target input is a reasonable measure for its quantitative evaluation of the reliability. By following a standard procedure using multipliers that capture the behavior of ReLUs,we first reduce the upper bound computation problem of the local Lipschitz constant into a semidefinite programming problem (SDP). Here we newly introduce copositive multipliers to capture the ReLU behavior accurately. Then, by considering the dual of the SDP for the upper bound computation, we second derive a viable test to conclude the exactness of the computed upper bound. However, these SDPs are intractable for practical FNNs with hundreds of ReLUs. To address this issue, we further propose a method to construct a reduced order model whose input-output property is identical to the original FNN over a neighborhood of the target input. We finally illustrate the effectiveness of the model reduction and exactness verification methods with numerical examples of practical FNNs.