Source-linked AI summary
Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes
Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, Tharrshann Jayan Logarajah, Georg Loho, Mihir More, Moritz Stargalla
TL;DR
The paper studies whether intermediate Lp-Lipschitz constants become tractable for two-layer input-convex ReLU networks, using their equivalence to dual-norm maximization over zonotopes. It proves dimension-parameterized hardness for every fixed rational p∈(1,∞), with matching ETH-based enumeration lower bounds.
Problem
The parameterized complexity of Lp-norm maximization over zonotopes and Lp-Lipschitz computation for two-layer ReLU ICNNs was open for p∈(1,∞).
Method
The paper first proves hardness for L2-Max on Zonotopes, then transfers the construction to fixed rational p∈(1,∞) and uses zonotope–ICNN duality.
Results
For every fixed rational p∈(1,∞), both zonotope p-Max and two-layer ICNN Lp-Lipschitz Constant are W[1]-hard in dimension d and lack ρ(d)N^o(d)-time algorithms under ETH.
Takeaways & Limitations
Restricting ReLU networks to be input-convex does not make these intermediate-norm problems tractable, unlike the L1- and L∞-norm cases.
Takeaways & Limitations
The parameterized-complexity status remains incomplete because membership in W[1] is still open.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks whether restricting ReLU networks to input-convex architectures makes intermediate-norm Lipschitz computation tractable, and answers negatively through parameterized hardness results for zonotope maximization.
- Exact Lp-Lipschitz computation is NP-hard for two-layer ReLU networks, motivating parameterized analysis by input dimension.
- ICNNs enforce convexity through nonnegative weights beyond the first layer and can simplify some computational problems.
- Lp-norm maximization over zonotopes is fixed-parameter tractable for p=1 and polynomial-time solvable for p=∞, leaving p∈(1,∞) unresolved.
- The results imply that brute-force enumeration of zonotope vertices or neural-network linear regions is essentially optimal under ETH.
- The paper reduces Multicolored Clique to L2-Max on Zonotopes with dimension linear in the clique size, using two conceptually different constructions.
- For every fixed rational p∈(1,∞), p-Max on Zonotopes is W[1]-hard in dimension d and lacks a ρ(d)N^o(d)-time algorithm under ETH.
- By zonotope–ICNN equivalence, the same hardness and ETH lower bounds apply to two-layer ICNN Lp-Lipschitz constants.
2 Preliminaries
The preliminaries define the norm, network, geometric, and parameterized-complexity objects used to formulate Lipschitz-constant and zonotope-maximization problems.
- A positively homogeneous function satisfies f(λx)=λf(x) for λ≥0, while a decreasing vector has nonincreasing coordinates.
- A two-layer ReLU network combines affine inputs through ReLU activations, and nonnegative output weights make the network an ICNN computing a convex function.
- A zonotope is generated from vectors by taking all sums with coefficients in [0,1], with the generator matrix collecting those vectors as columns.
- FPT parameterized by k means running time f(k)·|x|^O(1), whereas W[1]-hardness is evidence against such algorithms.
- The two decision problems ask whether an ICNN Lipschitz constant or a zonotope’s maximum Lp-norm reaches a rational threshold L.
- Enumerating all zonotope vertices places Lp-Max in XP with respect to dimension when norm-threshold testing is polynomial-time.
3 Lp-Lipschitz-constant for Input-convex ReLU Networks
The paper identifies a geometric duality between bias-free two-layer ReLU ICNNs and zonotopes: network linear-region gradients correspond to zonotope vertices, so Lipschitz computation becomes dual-norm maximization.
- Conjugate exponents satisfy 1/p+1/q=1, and an ICNN’s Lp-Lipschitz constant is determined by the q-norms of its linear-region gradients.
- Thus, computing the ICNN Lp-Lipschitz constant is equivalent to maximizing the Lq-norm over the associated zonotope.
- Bias-free ReLU ICNNs correspond bijectively to polytopes through support functions, with addition represented by Minkowski sums.
- For a bias-free two-layer ICNN, the associated polytope is the zonotope Z(W^T).
- Vertices of Z(W^T) correspond to hyperplane-arrangement regions, and each vertex equals the sum of the active generators determining that region’s gradient.
4 Two Hardness Reductions for L2 2-Max on Zonotopes
The section presents two parameterized reductions from Multicolored Clique to L2-norm maximization over zonotopes, using dimensions 2k+1 and 2k. Both encode node choices geometrically and separate clique instances from non-cliques by a threshold gap.
- 4.1 Explicit Reduction with 2k + 1 Dimensions: The gadget makes nonzero decreasing binary vectors lie on the L2-unit circle, while other binary vectors lie strictly inside it.This encodes the choice of one object, later one node, through the unique decreasing pattern.
- 4.1 Explicit Reduction with 2k + 1 Dimensions: Clique-consistent node selections maximize the edge contribution, whereas nonmatching edges incur a quantitative loss.For matching edges the relevant bound is 2Λ; for nonmatching edges it is at most Λ(2 − δ/2).
- 4.1 Explicit Reduction with 2k + 1 Dimensions: The explicit reduction creates a threshold gap: yes-instances exceed L, while no-instances remain below L − m^2.The construction has polynomial encoding size and dimension d = 2k + 1, yielding W[1]-hardness and the ETH lower bound.
- 4.2 Non-Explicit Reduction with 2k Dimensions: The second reduction uses a node term and an edge term in a 2k-dimensional space, with the node term enforcing discrete choices and the edge term rewarding adjacency.The generators for the edge term are obtained non-explicitly through a polynomial-size linear program.
- 4.2 Non-Explicit Reduction with 2k Dimensions: The combined support function distinguishes k-colored cliques from non-cliques, and maximizing it on the unit sphere equals maximizing the L2-norm over the constructed zonotope.The edge term has value Ecl for clique selections and at most Ecl − δ* otherwise; the final construction is a polynomial-time parameterized reduction.
5 Hardness for Lp-norms with p ∈(1, ∞)
The paper transfers the L2 hardness construction for zonotope norm maximization to every fixed rational p in (1,∞), using a local embedding and Taylor approximation. The resulting reductions preserve a positive gap and establish W[1]-hardness with ETH-based running-time lower bounds, with corresponding consequences for ICNN Lipschitz constants.
- Transfer construction: The transfer embeds x as (1_d + εx, 1_d − εx), placing a scaled antisymmetric copy of the original zonotope in the tangent space at the all-ones vector.The resulting prism is [0,b] + εJZ(A), and its translated face dominates the Lp objective for sufficiently small ε.
- Transfer construction: Taylor approximation makes the transformed Lp objective reproduce the original L2 objective up to a controllable error term.The leading variation is second order, proportional to ∥x∥2^2, while the remainder is bounded by Cpε^4∥x∥4.
- Gap preservation: Proposition 5.2 constructs, in polynomial time, a rational higher-dimensional zonotope whose Lp maximization instance preserves the original positive gap.For fixed p, the generators and thresholds have polynomial encoding size, and the construction doubles the dimension while adding one generator.
- Gap preservation: A rational threshold between the p-th roots of the yes- and no-instance bounds can be computed by polynomial-time binary search.Lemma 5.3 produces T with B^1/p < T ≤ A^1/p and polynomial encoding size.
- Hardness consequences: For every fixed rational p in (1,∞), Lp-Max on Zonotopes is W[1]-hard by dimension and lacks time ρ(d)N^o(d) under ETH.The reduction has dimension D = 4k + 2 ∈ O(k), with polynomial encoding size.
- Hardness consequences: By duality, the same W[1]-hardness and ETH lower bound apply to the Lp-Lipschitz constant of two-layer ICNNs.The relevant norm exponent is the conjugate exponent in the zonotope formulation.
6 Conclusion
The paper establishes parameterized hardness for zonotope norm maximization and, by duality, for two-layer ReLU ICNN Lipschitz constants. It also identifies remaining tractability and classification questions.
- Conclusion: For every fixed rational p in (1,∞), exact Lp-norm maximization over generator-represented zonotopes in R^d is W[1]-hard with respect to d.Under ETH, no algorithm runs in time ρ(d)N^o(d) for any computable function ρ.
- Conclusion: The same parameterized hardness and ETH lower bounds apply to computing Lp-Lipschitz constants for two-layer ReLU ICNNs.The transfer follows from the duality between zonotopes and these networks.
- Conclusion: The ETH lower bounds make brute-force enumeration of zonotope vertices or neural-network linear regions essentially optimal.
- Open questions: The conclusion calls for identifying special cases, architectural restrictions, or combined parameters that restore tractability.
- Open questions: Whether these problems belong to W[1] remains open, so their parameterized complexity status is not completely settled.
7 Research Process with AI
The paper describes concurrent LLM-assisted discovery of the reductions and emphasizes human work in repairing proofs, recovering prior ideas, and producing understandable mathematics. It distinguishes correctness from mathematical clarity and intuition.
- Research process with AI: Different groups independently found reductions for the same open problem using LLMs around the same time.The authors state that initial reduction versions were independently found in May 2026 by different subsets of authors.
- Research process with AI: The authors argue that prompting an LLM with an open-problem list may require little subject-specific expertise for some reduction problems.They characterize these problems as involving a few tricks that may already be scattered across the literature.
- Research process with AI: Human review strengthened the reductions but found gaps, flaws, excessive technicality, and pseudo-intuitive language in the LLM-generated proofs.
- Research process with AI: Working through the LLM output helped the authors recover prior literature, understand the geometric intuition, and identify conceptual insights such as Lemma 4.3.
- Research process with AI: The paper presents digested mathematics rather than only machine-generated proofs, emphasizing that understandable proofs and proof ingredients are important contributions.