# ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 35 references that are in the map.
- First posted on arXiv 5 Apr 2024.

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

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks](https://mlsanity.com/paper/1802.04034/) (2018)
- [Exactly Computing the Local Lipschitz Constant of ReLU Networks](https://mlsanity.com/paper/2003.01219/) (2020)
- [Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming](https://mlsanity.com/paper/1903.01287/) (2019)
- [Training robust neural networks using Lipschitz bounds](https://mlsanity.com/paper/2005.02929/) (2020)
- [Lipschitz constant estimation of Neural Networks via sparse polynomial optimization](https://mlsanity.com/paper/2004.08688/) (2020)
- [A Unified Algebraic Perspective on Lipschitz Neural Networks](https://mlsanity.com/paper/2303.03169/) (2023)
- [Lipschitz Certificates for Layered Network Structures Driven by Averaged Activation Operators](https://mlsanity.com/paper/1903.01014/) (2019)
- [Direct Parameterization of Lipschitz-Bounded Deep Networks](https://mlsanity.com/paper/2301.11526/) (2023)
- [Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation](https://mlsanity.com/paper/2210.07394/) (2022)
- [Stability Analysis using Quadratic Constraints for Systems with Neural Network Controllers](https://mlsanity.com/paper/2006.07579/) (2020)
- [Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization](https://mlsanity.com/paper/2310.00116/) (2023)
- [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)
- [Improved robustness to adversarial examples using Lipschitz regularization of the loss](https://mlsanity.com/paper/1810.00953/) (2018)
- [Lipschitz constant estimation for 1D convolutional neural networks](https://mlsanity.com/paper/2211.15253/) (2022)
- [Robust Machine Learning Modeling for Predictive Control Using Lipschitz-Constrained Neural Networks](https://mlsanity.com/paper/2308.13721/) (2023)
- [Sequential Synthesis of Distributed Controllers for Cascade Interconnected Systems](https://mlsanity.com/paper/1902.07114/) (2019)
- [Gradient-based Algorithms for Convex Discrete Optimization via Simulation](https://mlsanity.com/paper/2010.16250/) (2020)
- [Learning Dissipative Neural Dynamical Systems](https://mlsanity.com/paper/2309.16032/) (2023)
- [Distributed Synthesis of Local Controllers for Networked Systems with Arbitrary Interconnection Topologies](https://mlsanity.com/paper/1902.10506/) (2019)
- [Scalable Lipschitz Estimation for CNNs](https://mlsanity.com/paper/2403.18613/) (2024)

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

- [Stochastic Sample Approximations of (Local) Moduli of Continuity](https://mlsanity.com/paper/2509.15368/) (2025)
- [ECLipsE-Gen-Local: Efficient Compositional Local Lipschitz Estimates for Deep Neural Networks](https://mlsanity.com/paper/2510.05261/) (2025)
- [Assumed Density Filtering and Smoothing with Neural Network Surrogate Models](https://mlsanity.com/paper/2511.09016/) (2025)
- [L-Lipschitz Gershgorin ResNet Network](https://mlsanity.com/paper/2502.21279/) (2025)
- [LDLT L-Lipschitz Network: Generalized Deep End-To-End Lipschitz Network Construction](https://mlsanity.com/paper/2512.05915/) (2025)
- [The Price of Robustness: Stable Classifiers Need Overparameterization](https://mlsanity.com/paper/2603.02806/) (2026)
- [Demystifying Lipschitz verification: positive matrices, negative results](https://mlsanity.com/paper/2603.28113/) (2026)
- [Beyond Lipschitz: Data-Driven Robustness via Discrete Modulus of Continuity](https://mlsanity.com/paper/2605.28729/) (2026)
- [Scalable Incremental Robustness Analysis of Neural Network Feedback Systems](https://mlsanity.com/paper/2609.22576/) (2026)
- [AC Power Flow Contingency Analysis Using a Single Deep Neural Network](https://mlsanity.com/paper/2609.30859/) (2026)

## Abstract (arXiv)

The Lipschitz constant plays a crucial role in certifying the robustness of neural networks to input perturbations. Since calculating the exact Lipschitz constant is NP-hard, efforts have been made to obtain tight upper bounds on the Lipschitz constant. Typically, this involves solving a large matrix verification problem, the computational cost of which grows significantly for both deeper and wider networks. In this paper, we provide a compositional approach to estimate Lipschitz constants for deep feed-forward neural networks. We first obtain an exact decomposition of the large matrix verification problem into smaller sub-problems. Then, leveraging the underlying cascade structure of the network, we develop two algorithms. The first algorithm explores the geometric features of the problem and enables us to provide Lipschitz estimates that are comparable to existing methods by solving small semidefinite programs (SDPs) that are only as large as the size of each layer. The second algorithm relaxes these sub-problems and provides a closed-form solution to each sub-problem for extremely fast estimation, altogether eliminating the need to solve SDPs. The two algorithms represent different levels of trade-offs between efficiency and accuracy. Finally, we demonstrate that our approach provides a steep reduction in computation time (as much as several thousand times faster, depending on the algorithm for deeper networks) while yielding Lipschitz bounds that are very close to or even better than those achieved by state-of-the-art approaches in a broad range of experiments. In summary, our approach considerably advances the scalability and efficiency of certifying neural network robustness, making it particularly attractive for online learning tasks.