# Lipschitz regularity of deep neural networks: analysis and efficient estimation

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

## Key facts

- Cited by 415 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2018.

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

- [Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth](https://mlsanity.com/paper/2103.03404/) (2021)
- [Machine Unlearning of Features and Labels](https://mlsanity.com/paper/2108.11577/) (2021)
- [Vision GNN: An Image is Worth Graph of Nodes](https://mlsanity.com/paper/2206.00272/) (2022)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023)
- [Beyond Periodicity: Towards a Unifying Framework for Activations in Coordinate-MLPs](https://mlsanity.com/paper/2111.15135/) (2021)
- [Penalizing Gradient Norm for Efficiently Improving Generalization in Deep Learning](https://mlsanity.com/paper/2202.03599/) (2022)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Proximal Optimal Transport Modeling of Population Dynamics](https://mlsanity.com/paper/2106.06345/) (2021)
- [Learning Smooth Neural Functions via Lipschitz Regularization](https://mlsanity.com/paper/2202.08345/) (2022)
- [A Survey on Uncertainty Quantification Methods for Deep Learning](https://mlsanity.com/paper/2302.13425/) (2023)
- [Spectral Normalisation for Deep Reinforcement Learning: an Optimisation Perspective](https://mlsanity.com/paper/2105.05246/) (2021)
- [Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds](https://mlsanity.com/paper/2111.01395/) (2021)
- [Contrastive Adapters for Foundation Model Group Robustness](https://mlsanity.com/paper/2207.07180/) (2022)
- [A Dynamical System Perspective for Lipschitz Neural Networks](https://mlsanity.com/paper/2110.12690/) (2021)
- [A Policy-Guided Imitation Approach for Offline Reinforcement Learning](https://mlsanity.com/paper/2210.08323/) (2022)
- [Direct Parameterization of Lipschitz-Bounded Deep Networks](https://mlsanity.com/paper/2301.11526/) (2023)
- [CViT: Continuous Vision Transformer for Operator Learning](https://mlsanity.com/paper/2405.13998/) (2024)
- [Semi-Supervised Active Learning with Temporal Output Discrepancy](https://mlsanity.com/paper/2107.14153/) (2021)
- [Score-based Generative Modeling Secretly Minimizes the Wasserstein Distance](https://mlsanity.com/paper/2212.06359/) (2022)
- [Recurrent Equilibrium Networks: Flexible Dynamic Models with Guaranteed Stability and Robustness](https://mlsanity.com/paper/2104.05942/) (2021)
- [Generalization Bounds For Meta-Learning: An Information-Theoretic Analysis](https://mlsanity.com/paper/2109.14595/) (2021)
- [Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagation](https://mlsanity.com/paper/2210.07394/) (2022)
- [RPCANet: Deep Unfolding RPCA Based Infrared Small Target Detection](https://mlsanity.com/paper/2311.00917/) (2023)
- [How Smooth Is Attention?](https://mlsanity.com/paper/2312.14820/) (2023)
- [INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer](https://mlsanity.com/paper/2402.02317/) (2024)
- [Solving PDE-constrained Control Problems Using Operator Learning](https://mlsanity.com/paper/2111.04941/) (2021)
- [NECO: NEural Collapse Based Out-of-distribution detection](https://mlsanity.com/paper/2310.06823/) (2023)
- [Can Push-forward Generative Models Fit Multimodal Distributions?](https://mlsanity.com/paper/2206.14476/) (2022)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)

## Abstract (arXiv)

Deep neural networks are notorious for being sensitive to small well-chosen perturbations, and estimating the regularity of such architectures is of utmost importance for safe and robust practical applications. In this paper, we investigate one of the key characteristics to assess the regularity of such methods: the Lipschitz constant of deep learning architectures. First, we show that, even for two layer neural networks, the exact computation of this quantity is NP-hard and state-of-art methods may significantly overestimate it. Then, we both extend and improve previous estimation methods by providing AutoLip, the first generic algorithm for upper bounding the Lipschitz constant of any automatically differentiable function. We provide a power method algorithm working with automatic differentiation, allowing efficient computations even on large convolutions. Second, for sequential neural networks, we propose an improved algorithm named SeqLip that takes advantage of the linear computation graph to split the computation per pair of consecutive layers. Third we propose heuristics on SeqLip in order to tackle very large networks. Our experiments show that SeqLip can significantly improve on the existing upper bounds. Finally, we provide an implementation of AutoLip in the PyTorch environment that may be used to better estimate the robustness of a given neural network to small perturbations or regularize it using more precise Lipschitz estimations.