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. 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 infinity-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, infinity) Q, maximizing the L p-norm over a zonotope in 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, infinity) 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.