cs.LGMar 30, 2026

Demystifying Lipschitz verification: positive matrices, negative results

Authors: Simon Kuang, Yuezhu Xu, S. Sivaranjani, Xinfan Lin

Organizations: Department of Mechanical and Aerospace Engineering University of California, Davis · Edwardson School of Industrial Engineering Purdue University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

The global Lipschitz constant of a neural network is related to robustness and generalization, yet unlike in many classical models, it is not plainly legible from the parameters. This has motivated sophisticated verification algorithms, especially semidefinite programming (SDP) based on incremental quadratic constraints on the activation functions, to improve on the fast but often loose product of layerwise Lipschitz constants (the trivial bound). We ask why Lipschitz verification is a problem in the first place. Our answer is that the difficulty is structural: estimating a network's Lipschitz constant requires knowing which hidden states are reachable, and reachability is NP-hard. If P!=NP, then reachability is a barrier to any polynomial-time algorithm. Through explicit constructions, we show that this blindness can force SDP-based bounds to inherit the same qualitative failures as the trivial bound, including but not limited to polynomial per-layer conservatism. We show that the difficulties of NP-hard questions are not isolated to worst-case computational reductions, but actually afflict every instance of the verification problem. Thus SDP is not sufficient for Lipschitz verification. We also argue that it is not necessary: several apparent failures of the trivial bound arise from removable parameterization pathologies, and can be mitigated by optimizing or regularizing the trivial bound itself. We demonstrate this claim via a "spherical cow" linear model and numerical proofs of concept. While the main contribution is theoretical and negative, we finally motivate a novel form of trigonometric layers that do not need biases for universal approximation. Combined with trivial bound regularization, they make the trivial bound provably and practically tight.

Figures & tables

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

λ\lambdaTrain LossTest LossTrain Acc.Test Acc.
001.0×10−41.0\times 10^{-4}0.46610.46611.0001.0000.9330.933
10−210^{-2}0.05420.05420.09320.09320.9830.9830.9670.967
Appendix
Table D.1 : Iris experiment: final predictive performance after 20,000 steps.
λ\lambdaKK (upper)K/(2κ(W))K/(\sqrt{2}\kappa(W))L^\widehat{L}K/L^K/\widehat{L}
00179.21179.2125.0425.04105.74105.741.691.69
10−210^{-2}5.845.840.820.825.845.841.001.00
Appendix
Table D.2 : Iris experiment: 2-norm Lipschitz upper bound KK versus lower bounds. Here K/(2κ(W))K/(\sqrt{2}\kappa(W)) is the guaranteed lower bound from Theorem 3.1 , while L^\widehat{L} is an empirical lower bound from local optimization of the Lipschitz ratio over input pairs.
Figure D.1 : Iris experiment: training curves for λ=0\lambda=0 (left) and λ=10−2\lambda=10^{-2} (right). Shaded area indicates the gap between theoretical upper and lower bounds on the Lipschitz constant.
Figure D.2 : Iris experiment: decision boundaries in 2D principal component planes for λ=0\lambda=0 . (Training data)
Figure D.3 : Iris experiment: decision boundaries in 2D principal component planes for λ=10−2\lambda=10^{-2} . (Training data)
 lower bound L^\widehat{L}ECLipsEtrivialtrivial/ L^\widehat{L}ECLipsE/ L^\widehat{L}
no penalty19.596755.7630060.891534.34344.82
penalty λ=10−6\lambda=10^{-6}14.74130.19218.5814.838.83
Appendix
Table F.1 : Lipschitz upper and lower bounds on a 3-layer ReLU MNIST network initialized with an adversarial dead neuron.
configλ\lambdatrain losstest losstrain acc.test acc.
ReLU000.01360.06960.99530.9754
ReLU10−210^{-2}0.03020.05960.99190.9809
Cos/Sin10−210^{-2}0.01800.05170.99590.9826
Appendix
Table G.1 : MNIST three-way comparison: final predictive performance after 20 epochs.
configλ\lambdaKKKK timeL^\widehat{L}L^\widehat{L} timeK/L^K/\widehat{L}
ReLU00605.1710.03s48.0142.88s12.60
ReLU10−210^{-2}3.3140.02s2.6141.96s1.27
Cos/Sin10−210^{-2}3.7410.02s3.0828.16s1.21
Appendix
Table G.2 : MNIST three-way comparison: trivial Lipschitz upper bound KK , empirical lower bound L^\widehat{L} , computation times, and upper-to-lower ratio.
More in this topic

Neural Network Verification

Neural network verification develops methods to prove whether networks satisfy properties such as robustness, safety, and bounded output behavior.

See all 121 papers

Explore similar work

CardsList
Feb 17, 2026

ExLipBaB: Exact Lipschitz Constant Computation for Piecewise Linear Neural Networks

It has been shown that a neural network's Lipschitz constant can be leveraged to derive robustness guarantees, to improve generalizability via regularization or even to construct invertible networks. Therefore, a number of methods varying in the tightness of their bounds and their computational cost have been developed to approximate the Lipschitz constant for different classes of networks. However, comparatively little research exists on methods for exact computation, which has been shown to be NP-hard. Nonetheless, there are applications where one might readily accept the computational cost of an exact method. These applications could include the benchmarking of new methods or the computation of robustness guarantees for small models on sensitive data. Unfortunately, existing exact algorithms restrict themselves to only ReLU-activated networks, which are known to come with severe downsides in the context of Lipschitz-constrained networks. We therefore propose a generalization of the LipBaB algorithm to compute exact Lipschitz constants for arbitrary piecewise linear neural networks and pp-norms. With our method, networks may contain traditional activations like ReLU or LeakyReLU, activations like GroupSort or the related MinMax and FullSort, which have been of increasing interest in the context of Lipschitz constrained networks, or even other piecewise linear functions like MaxPool.

Tom A. Splittgerber

University of Bremen

Lipschitz Neural Networks
AskPDF
May 11, 2026

Hierarchical End-to-End Taylor Bounds for Complete Neural Network Verification

Reachability analysis of neural networks, which seeks to compute or bound the set of outputs attainable over a given input domain, is central to certifying safety and robustness in learning-enabled physical systems. Since exact reachable set computation is generally intractable, existing methods typically rely on tractable overapproximations. Examining the state of the art for smooth, twice-differentiable networks, we observe that existing approaches exploit at most second-order information and do not systematically leverage higher-order information. In this work, we introduce HiTaB, a novel verification framework that exploits second-order smoothness through both the Hessian, ∇2f\nabla^2 f, and its Lipschitz constant, L∇2fL_{\nabla^2 f}. We further develop a unified hierarchy of zeroth-, first-, and second-order bounds, together with precise conditions under which higher-order approximations yield provable improvements. Our main technical contribution is a compositional procedure for efficiently bounding L∇2fL_{\nabla^2 f} in deep neural networks via layerwise propagation of curvature bounds. We extend the framework to both ℓ2\ell_2- and ℓ∞\ell_\infty-constrained input sets and show how it can be integrated into branch-and-bound verification pipelines. To our knowledge, this is the first practical reachability analysis framework for smooth neural networks that systematically exploits Lipschitz continuity of curvature, leading to tighter and more informative safety certificates.

Taha Entesari, Mahyar Fazlyab

Johns Hopkins University

Neural Network VerificationNeural Network RobustnessCertified Robustness
AskPDF
Oct 5, 2026

Lipschitz Thinking: Ten Years of Certifiable-by-Design Robust Neural Networks

The Lipschitz property of a deep neural network provides a direct measure of its sensitivity to input perturbations and, when explicitly controlled, offers a principled way to limit the propagation of errors and improve robustness. Over the past decade, Lipschitz-bounded layers have been incorporated into increasingly expressive and high-performing deep models, narrowing the gap between empirical robustness and formal, by-design guarantees of stability. This article introduces the fundamental concepts underlying Lipschitz-bounded neural networks, explaining the principles behind Lipschitz-constrained layers, the mechanisms used to enforce their bounds, and how they yield robustness certificates at the cost of a single forward pass. The tutorial concludes by discussing emerging and open directions, highlighting Lipschitz control as a general framework for offering guaranteed, by-design stability.

Fabio Brau, Giorgio Piras, Maura Pintor +1

Department of Electrical and Electronic Engineering, University of Cagliari, Cagliari, Italy

Neural Network RobustnessCertified RobustnessLipschitz Neural NetworksNeural Network Stability
AskPDF