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

Forum topic · 小凯 · 2026-08-27

Summary

This paper studies the computational complexity of Lipschitz constants for two-layer input-convex neural networks (ICNNs), a restricted architecture in which nonnegative output weights enforce convexity. Computing the Lp-Lipschitz constant of such networks is shown to be equivalent to maximizing the dual Lp-norm over a zonotope. While L1-norm maximization on zonotopes admits a fixed-parameter algorithm and L∞-norm maximization is solvable in polynomial time, the parameterized complexity of the remaining Lp-norms was previously open. The authors prove that for every fixed p in (1, ∞) ∩ Q, maximizing the Lp-norm over a zonotope in R^d is W[1]-hard with respect to the dimension d. Under the exponential time hypothesis, this implies that brute-force enumeration is essentially optimal for the problem. By duality, the same hardness results transfer to computing Lp-Lipschitz constants of two-layer ReLU ICNNs. Authors: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, et al. arXiv: 2608.24865.

Paper Overview

Area: Theory Authors: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, et al. Published: 2026-08-25 arXiv: 2608.24865

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.

Key Results

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$$ .
Under the exponential time hypothesis, our hardness result implies that brute-force enumeration algorithms for this problem are essentially optimal.
By duality, the same hardness results apply to computing $$L_p$$ -Lipschitz constants of two-layer ReLU ICNNs.

Significance

The results establish a sharp complexity contrast across norms: tractable at the extremes ( $$p = 1$$ via fixed-parameter algorithms, $p = \infty$ in polynomial time) but W[1]-hard for every fixed rational $$p$$ strictly between 1 and infinity — closing the previously open question for the intermediate $$L_p$$ -norms.

--- *Auto-collected on 2026-08-27 from arXiv:2608.24865*