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

Lipschitz constants are critical for quantifying the sensitivity of neural networks to input perturbations, which directly impacts their robustness and generalization. While computing these constants is generally NP-hard, researchers have investigated whether restricted architectures, such as Input-Convex Neural Networks (ICNNs), allow for more efficient computation. This paper addresses the open problem of the parameterized complexity of computing the Lp-Lipschitz constant for two-layer ReLU ICNNs when the input dimension is treated as a parameter.

The authors establish a mathematical equivalence between computing the Lp-Lipschitz constant of a two-layer ReLU ICNN and maximizing the dual norm over a zonotope. They then focus on the parameterized complexity of this norm-maximization problem. Using reductions from the Multicolored Clique problem, the authors prove W[1]-hardness with respect to the input dimension d. They provide two distinct reductions: one explicit reduction using elementary geometric gadgets in 2k+1 dimensions, and a second, non-explicit reduction in 2k dimensions that utilizes the support functions of centrally symmetric zonotopes.

The study proves that for any fixed rational p in (1, infinity), maximizing the Lp-norm over a zonotope is W[1]-hard. Consequently, computing the Lp-Lipschitz constant for two-layer ReLU ICNNs is also W[1]-hard. Under the Exponential Time Hypothesis (ETH), these problems cannot be solved in time faster than the brute-force enumeration of the zonotope's vertices or the network's linear regions. This demonstrates that the architectural restriction to ICNNs does not yield the same computational tractability for Lp-norms (where p is not 1 or infinity) as it does for other cases.

This work resolves a significant open problem in the field of neural network verification and computational geometry. By proving that ICNNs do not simplify the complexity of Lipschitz constant computation for most Lp-norms, the paper provides a definitive negative result that guides future research toward identifying other tractable sub-cases or alternative architectural constraints. Additionally, the authors provide a transparent account of their research process, including the use of LLMs, contributing to the broader discussion on the role of AI in theoretical mathematics.