# Lipschitz constant estimation of Neural Networks via sparse polynomial optimization

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

## Key facts

- Cited by 87 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2020.

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

- [Orthogonalizing Convolutional Layers with the Cayley Transform](https://mlsanity.com/paper/2104.07167/) (2021)
- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [Whoever Started the Interference Should End It: Guiding Data-Free Model Merging via Task Vectors](https://mlsanity.com/paper/2503.08099/) (2025)
- [Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective](https://mlsanity.com/paper/2210.01787/) (2022)
- [CViT: Continuous Vision Transformer for Operator Learning](https://mlsanity.com/paper/2405.13998/) (2024)
- [Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation](https://mlsanity.com/paper/2210.07394/) (2022)
- [How Smooth Is Attention?](https://mlsanity.com/paper/2312.14820/) (2023)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Stable Neural Stochastic Differential Equations in Analyzing Irregular Time Series Data](https://mlsanity.com/paper/2402.14989/) (2024)
- [Visual Adversarial Attack on Vision-Language Models for Autonomous Driving](https://mlsanity.com/paper/2411.18275/) (2024)
- [LipsFormer: Introducing Lipschitz Continuity to Vision Transformers](https://mlsanity.com/paper/2304.09856/) (2023)
- [LOT: Layer-wise Orthogonal Training on Improving ℓ2 Certified Robustness](https://mlsanity.com/paper/2210.11620/) (2022)
- [Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural networks](https://mlsanity.com/paper/2104.05097/) (2021)
- [Some Fundamental Aspects about Lipschitz Continuity of Neural Networks](https://mlsanity.com/paper/2302.10886/) (2023)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularization](https://mlsanity.com/paper/2310.00116/) (2023)
- [Towards Understanding the Data Dependency of Mixup-style Training](https://mlsanity.com/paper/2110.07647/) (2021)
- [Efficient Bound of Lipschitz Constant for Convolutional Layers by Gram Iteration](https://mlsanity.com/paper/2305.16173/) (2023)
- [Fighting Uncertainty with Gradients: Offline Reinforcement Learning via Diffusion Score Matching](https://mlsanity.com/paper/2306.14079/) (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)
- [Statistical Guarantees for Variational Autoencoders using PAC-Bayesian Theory](https://mlsanity.com/paper/2310.04935/) (2023)
- [Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networks](https://mlsanity.com/paper/2204.00846/) (2022)
- [Approximation of Lipschitz Functions using Deep Spline Neural Networks](https://mlsanity.com/paper/2204.06233/) (2022)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learning](https://mlsanity.com/paper/2112.00423/) (2021)
- [Lipschitz constant estimation for 1D convolutional neural networks](https://mlsanity.com/paper/2211.15253/) (2022)
- [Analytical bounds on the local Lipschitz constants of ReLU networks](https://mlsanity.com/paper/2104.14672/) (2021)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [Width is Less Important than Depth in ReLU Neural Networks](https://mlsanity.com/paper/2202.03841/) (2022)

## Abstract (arXiv)

We introduce LiPopt, a polynomial optimization framework for computing increasingly tighter upper bounds on the Lipschitz constant of neural networks. The underlying optimization problems boil down to either linear (LP) or semidefinite (SDP) programming. We show how to use the sparse connectivity of a network, to significantly reduce the complexity of computation. This is specially useful for convolutional as well as pruned neural networks. We conduct experiments on networks with random weights as well as networks trained on MNIST, showing that in the particular case of the ℓ_∞-Lipschitz constant, our approach yields superior estimates, compared to baselines available in the literature.