Summary
This paper studies the computational complexity of Lipschitz constants for two-layer input-convex neural networks (ICNNs), a restricted architecture where nonnegative output weights enforce convexity. Computing the Lp-Lipschitz constant of such networks is equivalent to maximizing the dual norm over a zonotope. While L1- and L∞-norm maximization on zonotopes admit fixed-parameter and polynomial-time algorithms respectively, the parameterized complexity of the remaining Lp-norms was open. The authors prove that for every fixed rational p in (1, ∞), maximizing the Lp-norm over a zonotope in R^d is W[1]-hard with respect to the dimension d. Under the exponential time hypothesis, this implies that brute-force enumeration algorithms are essentially optimal for this problem. By duality, the same hardness results apply to computing Lp-Lipschitz constants of two-layer ReLU ICNNs. The work is by Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich and others, available as arXiv:2608.24865.
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. This paper investigates the problem for two-layer input-convex neural networks (ICNNs), a restricted architecture in which nonnegative output weights enforce convexity.
Key points
- Equivalence: Computing the \(L_p\)-Lipschitz constant of a two-layer ICNN is equivalent to maximizing the dual norm over a zonotope.
- Known tractable cases: \(L_1\)-norm maximization on zonotopes admits a fixed-parameter algorithm, and \(L_\infty\)-norm maximization is solvable in polynomial time.
- Main result: 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\).
- Optimality: Under the Exponential Time Hypothesis (ETH), the hardness result implies that brute-force enumeration algorithms for this problem are essentially optimal.
- Implication for neural networks: By duality, the same hardness results transfer to computing the \(L_p\)-Lipschitz constants of two-layer ReLU ICNNs.
Reference
- arXiv: 2608.24865
- Authors: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, et al.
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/178634087