ExLipBaB: Exact Lipschitz Constant Computation for Piecewise Linear Neural Networks

Tom A. Splittgerber

cs.LGFeb 17, 2026

ExLipBaB: Exact Lipschitz Constant Computation for Piecewise Linear Neural Networks

Authors: Tom A. Splittgerber

Organizations: University of Bremen

Abstract

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 $p$ -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.

Figures & tables

	ReLU, 0.11 [0.04]		GroupSort, 0.11 [0.05]
	$L(f)$ [std]	time (s)	$L(f)$ [std]	time (s)
Layerwise	3.12 [0.50]	0.00	1.62 [0.32]	0.00
ExLipBaB	1.15 [0.20]	0.03	1.01 [0.24]	0.03
LipSDP	1.62 [0.32]	3.63	1.30 [0.30]	0.00

Table 1: Test performance and global Lipschitz constant of 2 networks on synthetic data from the absolute value function over 20 runs. Shown are test RMSE mean [standard deviation] of the networks as well as mean Lipschitz estimate [std] for several methods.

Abalone, Shape $[9,16,16,1]$
$\mathbb{R}^{d_{0}}$	ReLU		MaxMin
$\mathbb{R}^{d_{0}}$	estimate	time (s)	estimate	time (s)
Layerwise	14.27	0.000	10.41	0.000
LipSDP	11.22	30.72	8.827	0.016
SymProp	15.22	0.017	8.918	0.015
ExLipBaB	11.21	20.83	4.487	357.8

Table 2: Lipschitz constant estimation of NN trained on the abalone data w.r.t.

||.||_{2}

Wine, Network shape $[11,12,12,1]$
$\mathbb{R}^{d_{0}}$	ReLU		MaxMin
$\mathbb{R}^{d_{0}}$	estimate	time (s)	estimate	time (s)
Layerwise	5.86	0.000	3.78	0.000
LipSDP (*)	1.84	26.65	2.87	0.014
LipSDP (**)	1.30	4.257	-	-
SymProp	4.78	0.015	11.09	0.013

Table 3: Lipschitz constant estimation of NN trained on the wine quality data w.r.t.

||.||_{2}

. LipSDP (network) (**) converged to an implausible value; (*) lists the neuron variant also for ReLU.

Figure 1: Number of subproblems for ExLipBaB on the NN trained on wine data with and without initial lower bound.

Wine, Network shape $[11,24,24,1]$
$\mathbb{R}^{d_{0}}$	ReLU		MaxMin
$\mathbb{R}^{d_{0}}$	estimate	time (s)	estimate	time (s)
Layerwise	5.86	0.000	6.10	0.002
LipSDP	1.19	4.630	4.70	0.012
SymProp	4.78	0.016	25.3	0.040
ExLipBaB	2.62	(*)	4.23	377.3

Table 4: Lipschitz constant estimation of NN trained on Bike sharing data w.r.t.

||.||_{2}

. (*) The ExLipBaB algorithm did not converge after 12 hours.

Bike sharing, Network shape [13, 20, 16, 8, 3]
$\mathbb{R}^{d_{0}}$	ReLU		MaxMin
$\mathbb{R}^{d_{0}}$	estimate	time (s)	estimate	time (s)
Layerwise	30848	0.000	13145	0.000
LipSDP	5895(*)	5.041	9946	0.018
SymProp	20846	0.043	58484	0.038
ExLipBaB	10802	39283	-	(**)

Table 5: Lipschitz constant estimation of NN trained on Bike sharing data w.r.t.

||.||_{2}

. (* The LiSDP algorithm in the forms neuron and layer did not converge; the network variant gave a bound below the true Lipschitz constant computed by ExLipBaB. (**) The algorithm hadn’t converged after 24 hours.)

Lipschitz Neural Networks

Lipschitz neural networks control how much outputs can change when inputs are perturbed, supporting robustness, stability, and convergence guarantees.

See all 24 papers

Demystifying Lipschitz verification: positive matrices, negative results
Mar 30, 2026Simon Kuang, Yuezhu Xu, S. Sivaranjani +1Neural Network Verification Lipschitz Neural Networks
Department of Mechanical and Aerospace Engineering University of California, Davis · Edwardson School of Industrial Engineering Purdue University
Parameterized Complexity of $L_p$ -Lipschitz Constants for Input Convex Neural Networks and $L_p$ -Norm Maximization over Zonotopes
Aug 25, 2026Aritra Das, Vincent Froese, Moritz Grillo +6Lipschitz Neural Networks Parameterized Complexity
Ashoka University, Truth Audit Labs · Technische Universität Berlin · Max Planck Institute for Mathematics in the Sciences +3
Lipschitz Thinking: Ten Years of Certifiable-by-Design Robust Neural Networks
Oct 5, 2026Fabio Brau, Giorgio Piras, Maura Pintor +1Neural Network Robustness Certified Robustness
Department of Electrical and Electronic Engineering, University of Cagliari, Cagliari, Italy

Mar 30, 2026J/K move · Enter open · S save

Demystifying Lipschitz verification: positive matrices, negative results

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

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

Neural Network Verification Lipschitz Neural Networks Semidefinite Programming

Open paper AskPDF 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.

Abstract

Lipschitz Neural Networks

Explore similar work

Demystifying Lipschitz verification: positive matrices, negative results

Parameterized Complexity of LpL_pLp​-Lipschitz Constants for Input Convex Neural Networks and LpL_pLp​-Norm Maximization over Zonotopes

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

Parameterized Complexity of $L_p$ -Lipschitz Constants for Input Convex Neural Networks and $L_p$ -Norm Maximization over Zonotopes