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

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. Computing the $L_p$-Lipschitz constant for two-layer input-convex neural networks (ICNNs) is equivalent to maximizing the dual norm over a zonotope. While $L_1$- and $L_{\infty }$-norm maximization on zonotopes are fixed-parameter tractable and polynomial-time solvable, 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 a two-layer ReLU ICNN. Our paper resolves an open problem posted at COLT '25 (Froese et al. 2025). There are several independent concurrent papers resolving the same problem. Our paper prioritizes a clear exposition of the underlying geometric ideas and conceptual intuitions behind the proof. Additionally, we explicitly describe our research process including the use of LLMs.