mlsanityData to 7 Oct 2026

Demystifying Lipschitz verification: positive matrices, negative results

arXiv 2603.28113 ↗First posted 30 Mar 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 37 of its 48 references that are in the map. First posted on arXiv 30 Mar 2026.

Builds on

37 of 48 references.

References · 37

  1. 2013Intriguing properties of neural networkscited by 5,114
  2. 2018Spectral Normalization for Generative Adversarial Networkscited by 1,618
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  4. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  5. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 413
  6. 2018Regularisation of Neural Networks by Enforcing Lipschitz Continuitycited by 311
  7. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  8. 2018Certified Defenses against Adversarial Examplescited by 305
  9. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  10. 2019Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networkscited by 290
  11. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  12. 2017Parseval Networks: Improving Robustness to Adversarial Examplescited by 288
25 more
  1. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  2. 2017Spectral Norm Regularization for Improving the Generalizability of Deep Learningcited by 178
  3. 2021Equinox: neural networks in JAX via callable PyTrees and filtered transformationscited by 143
  4. 2015Path-SGD: Path-Normalized Optimization in Deep Neural Networkscited by 117
  5. 2021Globally-Robust Neural Networkscited by 106
  6. 2020Exactly Computing the Local Lipschitz Constant of ReLU Networkscited by 102
  7. 2020Lipschitz constant estimation of Neural Networks via sparse polynomial optimizationcited by 87
  8. 2023A Unified Algebraic Perspective on Lipschitz Neural Networkscited by 58
  9. 2023Direct Parameterization of Lipschitz-Bounded Deep Networkscited by 49
  10. 2021Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100cited by 47
  11. 2024Neural Network Verification with Branch-and-Bound for General Nonlinearitiescited by 47
  12. 2022Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagationcited by 45
  13. 2021Recurrent Equilibrium Networks: Flexible Dynamic Models with Guaranteed Stability and Robustnesscited by 43
  14. 2018RecurJac: An Efficient Recursive Algorithm for Bounding Jacobian Matrix of Neural Networks and Its Applicationscited by 27
  15. 2021LipBaB: Computing exact Lipschitz constant of ReLU networkscited by 16
  16. 2022Chordal Sparsity for Lipschitz Constant Estimation of Deep Neural Networkscited by 15
  17. 2024ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networkscited by 10
  18. 2025Position: Solve Layerwise Linear Models First to Understand Neural Dynamical Phenomena (Neural Collapse, Emergence, Lazy/Rich Regime, and Grokking)cited by 8
  19. 2015Data-Dependent Path Normalization in Neural Networkscited by 6
  20. 2023Learning Dissipative Neural Dynamical Systemscited by 5
  21. 2024(Almost) Smooth Sailing: Towards Numerical Stability of Neural Networks Through Differentiable Regularization of the Condition Numbercited by 5
  22. 2025Enhancing Certified Robustness via Block Reflector Orthogonal Layers and Logit Annealing Losscited by 5
  23. 2024Synthesizing Neural Network Controllers with Closed-Loop Dissipativity Guaranteescited by 4
  24. 2024MIQCQP reformulation of the ReLU neural networks Lipschitz constant estimation problemcited by 1
  25. 2025ECLipsE-Gen-Local: Efficient Compositional Local Lipschitz Estimates for Deep Neural Networkscited by 1

Built on by

Not cited yet.