Search papers, labs, and topics across Lattice.
This paper investigates the parameterized complexity of computing $L_p$-Lipschitz constants for two-layer input-convex neural networks (ICNNs), establishing that maximizing the $L_p$-norm over zonotopes is W[1]-hard for every fixed rational $p$ in the interval (1,∞). The findings highlight that while certain norms can be computed efficiently, the remaining $L_p$-norms present significant computational challenges, implying that brute-force methods are essentially optimal under the Exponential Time Hypothesis. By proving these results, the authors resolve an open problem in the field and provide a clear mathematical exposition alongside insights into their research methodology, including the use of LLMs.
Maximizing $L_p$-norms over zonotopes is W[1]-hard for all fixed rational $p \in (1, \infty)$, revealing deep computational challenges in neural network sensitivity analysis.
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.
