Model Releases
Parameterized Complexity of L_p-Lipschitz Constants for Input Convex Neural Networks and L_p-Norm Maximization over Zonotopes
arXiv:2608.24865v1 Announce Type: cross Abstract: Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult ev
arXiv:2608.24865v1 Announce Type: cross 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. We prove that, for every fixed pin (1,infty)ap 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 pin (1,infty)apQ 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.
Related
- ICNN-enhanced 2SP: Leveraging input convex neural networks for solving two-stage stochastic programming
- Learning Sparse Compositional Functions with Norm-Constrained Neural Networks
- A lift for input-convex neural network training
Source: arXiv cs.LG | 2026-08-26