# Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 2 Apr 2022.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [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)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (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)
- [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)
- [Lipschitz Certificates for Layered Network Structures Driven by Averaged Activation Operators](https://mlsanity.com/paper/1903.01014/) (2019)
- [Stability-certified reinforcement learning: A control-theoretic perspective](https://mlsanity.com/paper/1810.11505/) (2018)
- [Learning Robust Output Control Barrier Functions from Safe Expert Demonstrations](https://mlsanity.com/paper/2111.09971/) (2021)
- [A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics](https://mlsanity.com/paper/1908.05209/) (2019)
- [Analytical bounds on the local Lipschitz constants of ReLU networks](https://mlsanity.com/paper/2104.14672/) (2021)
- [Safe Approximate Dynamic Programming Via Kernelized Lipschitz Estimation](https://mlsanity.com/paper/1907.02151/) (2019)
- [Chordal Decomposition for Spectral Coarsening](https://mlsanity.com/paper/2009.02294/) (2020)

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

- [Direct Parameterization of Lipschitz-Bounded Deep Networks](https://mlsanity.com/paper/2301.11526/) (2023)
- [Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization](https://mlsanity.com/paper/2310.00116/) (2023)
- [Lipschitz constant estimation for 1D convolutional neural networks](https://mlsanity.com/paper/2211.15253/) (2022)
- [ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networks](https://mlsanity.com/paper/2404.04375/) (2024)
- [Probabilistic Stability Guarantees for Feature Attributions](https://mlsanity.com/paper/2504.13787/) (2025)
- [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)
- [Convolutional Neural Networks as 2-D systems](https://mlsanity.com/paper/2303.03042/) (2023)
- [Chordal Sparsity for SDP-based Neural Network Verification](https://mlsanity.com/paper/2206.03482/) (2022)
- [Improved Scalable Lipschitz Bounds for Deep Neural Networks](https://mlsanity.com/paper/2503.14297/) (2025)
- [Efficient Symbolic Reasoning for Neural-Network Verification](https://mlsanity.com/paper/2303.13588/) (2023)
- [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)
- [Demystifying Lipschitz verification: positive matrices, negative results](https://mlsanity.com/paper/2603.28113/) (2026)
- [Scalable Incremental Robustness Analysis of Neural Network Feedback Systems](https://mlsanity.com/paper/2609.22576/) (2026)

## Abstract (arXiv)

Lipschitz constants of neural networks allow for guarantees of robustness in image classification, safety in controller design, and generalizability beyond the training data. As calculating Lipschitz constants is NP-hard, techniques for estimating Lipschitz constants must navigate the trade-off between scalability and accuracy. In this work, we significantly push the scalability frontier of a semidefinite programming technique known as LipSDP while achieving zero accuracy loss. We first show that LipSDP has chordal sparsity, which allows us to derive a chordally sparse formulation that we call Chordal-LipSDP. The key benefit is that the main computational bottleneck of LipSDP, a large semidefinite constraint, is now decomposed into an equivalent collection of smaller ones: allowing Chordal-LipSDP to outperform LipSDP particularly as the network depth grows. Moreover, our formulation uses a tunable sparsity parameter that enables one to gain tighter estimates without incurring a significant computational cost. We illustrate the scalability of our approach through extensive numerical experiments.