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

Aritra Das; Vincent Froese; Moritz Grillo; Debayan Gupta; Christoph Hertrich; Tharrshann Jayan Logarajah; Georg Loho; Mihir More

cs.CCAug 25, 2026

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

Authors: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, Tharrshann Jayan Logarajah, Georg Loho, Mihir More,

Organizations: Ashoka University, Truth Audit Labs · Technische Universität Berlin · Max Planck Institute for Mathematics in the Sciences · University of Technology Nuremberg ·

Abstract

Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult even for shallow ReLU networks. We study this problem for two-layer input-convex neural networks (ICNNs), a restricted architecture where nonnegative output weights enforce convexity. Computing the $L_p$ -Lipschitz constant for these networks is equivalent to maximizing the dual norm over a zonotope. While $L_1$ - and $L_\infty$ -norm maximization on zonotopes admit fixed-parameter and polynomial-time algorithms, respectively, the parameterized complexity of the remaining $L_p$ -norms was open. We prove that, for every fixed $p\in (1,\infty)\cap \mathbb{Q}$ , maximizing the $L_p$ -norm over a zonotope in $\mathbb{R}^d$ is W[1]-hard with respect to the dimension $d$ . Moreover, our hardness results imply that brute-force enumeration algorithms are essentially optimal for this problem under the Exponential Time Hypothesis. By duality, the same hardness results hold for computing the $L_p$ -Lipschitz constant of two-layer ReLU ICNNs. Our proof first establishes the result for the $L_2$ -norm and then transfers the construction to arbitrary fixed $p\in (1,\infty)\cap\mathbb{Q}$ using a suitable Taylor approximation. These results resolve the corresponding questions regarding the parameterized complexity status for zonotope norm maximization and two-layer ICNN Lipschitz constants. Our paper resolves an open problem posted at COLT'25. There are several independent concurrent papers resolving the same problem. Our paper prioritizes a clear exposition of the underlying mathematics and conceptual intuitions behind the proof. Additionally, we explicitly describe our research process including the use of LLMs.

Figures & tables

Figure 1: Illustration of the duality between zonotopes and bias-free two-layer ICNNs for

W=(w_{1},w_{2},w_{3})^{\top}

with

w_{1}=(0,1)^{\top}

w_{2}=(1,0)^{\top}

, and

w_{3}=(1,1)^{\top}

. The ICNN computes

f\colon\mathbb{R}^{2}\to\mathbb{R},\,x\mapsto\sum_{i=1}^{3}\max\{0,w_{i}^{\top}x\}

(left) and the corresponding zonotope is

Z(W^{\top})

(right). The gradient

\nabla f

on a linear region (bold vector) corresponds to exactly one of the six vertices of

Z(W^{\top})

Figure 2: Example for

S=\{(1,1)/\sqrt{2},(-1,0),(0,-1)\}

(left). The faces of dimension one of

\mathcal{H}

are

H_{i}=\mathbb{R}w_{i}

for

i\in[3]

with

w_{1}=(1,-1)

w_{2}=(0,1)

w_{3}=(1,0)

, and

C(S)=\cone\{\rho_{1},\rho_{2},\rho_{3}\}=\{(0,1,1),(1/\sqrt{2},0,1),(1/\sqrt{2},1,0)\}

with

\rho_{i}=\Phi_{S}(w_{i})

for

i\in[3]

(center). We have

\mathbf{1}\in\operatorname{int}C(S)

with

\mathbf{1}=(1-1/\sqrt{2})\rho_{1}+1/\sqrt{2}(\rho_{2}+\rho_{3})

, and the corresponding zonotope is generated by

g_{1}=(1-1/\sqrt{2})(1,-1)

g_{2}=(0,1/\sqrt{2})

, and

g_{3}=(1/\sqrt{2},0)

(right).

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 3: The vectors from Lemma B.1 for

m=5

. The point

w_{1}+w_{2}+w_{3}+w_{5}

(red) corresponds to the not decreasing binary vector

\sigma=(1,1,1,0,1)

and lies in a circle with radius

\sqrt{1-\delta_{m}}

(red).

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

Sep 26, 2025

Parameterized Hardness of Zonotope Containment and Neural Network Verification

Neural networks with ReLU activations are a widely used model in machine learning. It is thus important to have a profound understanding of the properties of the functions computed by such networks. Recently, there has been increasing interest in the (parameterized) computational complexity of determining these properties. In this work, we close several gaps and resolve an open problem posed by Froese et al. [COLT '25] regarding the parameterized complexity of various problems related to network verification. In particular, we prove that, for all

\ell\ge 2

, deciding positivity (and thus surjectivity) of a function

f:\mathbb{R}^d\to\mathbb{R}

computed by an

\ell

-layer ReLU network is W[

\ell-1

]-hard when parameterized by the input dimension

d

. The case

\ell=2

implies that zonotope non-containment (a problem that is of independent interest in computational geometry, control theory, and robotics) is W[1]-hard with respect to the ambient dimension

d

. Moreover, we show that approximating the maximum within any multiplicative factor and computing the

L_p

-Lipschitz constant for

p\in(0,\infty]

\ell

-layer networks is NP-hard and W[

\ell-1

]-hard with respect to

d

. For

\ell\ge 3

, approximating the

L_p

-Lipschitz constant is NP- and W[

\ell-2

]-hard. We further show that the above problems are NP- and W[

t

]-hard (for all

t\ge 1

) with respect to

\ell

for constant

d

. Notably, our hardness results imply that the naive enumeration-based methods for these fundamental problems running in

n^{(\ell-1) d}\cdot\operatorname{poly}(N)

time are all essentially optimal under the Exponential Time Hypothesis.

Vincent Froese, Moritz Grillo, Christoph Hertrich +1

Technische Universität Berlin · Max Planck Institute for Mathematics in the Sciences · University of Technology Nuremberg

Neural Network Verification Parameterized Complexity

Ask PDF

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

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.

Tom A. Splittgerber

University of Bremen

Lipschitz Neural Networks

Ask PDF

Jun 24, 2025

Optimal estimates for the $\ell^p$ -Lipschitz constants of deep random ReLU neural networks

This paper studies the

\ell^p

-Lipschitz constants of ReLU neural networks

Φ: \mathbb{R}^d \to \mathbb{R}

with random parameters for

p \in [1,\infty]

. The distribution of the weights follows a variant of the He initialization. In the case of zero-bias networks, we derive matching high-probability upper and lower bounds for wide networks that differ at most by an absolute constant. The bounds reveal two remarkable phenomena. First, the bounds grow root-logarithmically in terms of the depth of the net. Second, the behavior of the

\ell^p

-Lipschitz constants varies significantly between the regimes

p \in [1,2)

and

p \in [2,\infty]

. For

p \in [2,\infty]

, the

\ell^p

-Lipschitz constant behaves similarly to

\|g\|_{p'}

, where

g \in \mathbb{R}^d

is a standard Gaussian vector and

1/p + 1/p' = 1

. In contrast, for

p \in [1,2)

, the

\ell^p

-Lipschitz constant aligns more closely with

\|g\|_2

. For networks with possibly nonzero biases, we obtain the same lower bounds without assumptions on the bias distributions. For symmetric bias distributions with bounded densities, we also derive high-probability upper bounds for the

\ell^p

-Lipschitz constants. For fixed sub-exponential bias distributions, these upper bounds differ from the lower bounds by a factor that has square-root dependence on the depth and logarithmic dependence on the width.

Sjoerd Dirksen, Patrick Finke, Paul Geuchen +2

ReLU Neural Networks Lipschitz Neural Networks

Ask PDF

Abstract

Lipschitz Neural Networks

Explore similar work

Parameterized Hardness of Zonotope Containment and Neural Network Verification

ExLipBaB: Exact Lipschitz Constant Computation for Piecewise Linear Neural Networks

Optimal estimates for the ℓp\ell^pℓp-Lipschitz constants of deep random ReLU neural networks

Optimal estimates for the $\ell^p$ -Lipschitz constants of deep random ReLU neural networks