🤖 machine learning

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

This paper resolves an open problem by proving that computing $L_p$ -Lipschitz constants for two-layer input-convex neural networks and maximizing $L_p$ -norms over zonotopes are W[1]-hard with respect to the dimension for all fixed rational $p \in (1, \infty)$ , thereby establishing the optimality of brute-force enumeration under the Exponential Time Hypothesis.

Original authors: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, Tharrshann Jayan Logarajah, Georg Loho, Mihir More, Moritz Stargalla

Published 2026-08-26

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Aritra Das, Vincent Froese, Moritz Grillo, Debayan Gupta, Christoph Hertrich, Tharrshann Jayan Logarajah, Georg Loho, Mihir More, Moritz Stargalla

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, neural networks are the engines that power everything from image recognition to language translation. These systems learn by adjusting millions of internal settings, but they are notoriously fragile. A tiny, almost invisible change to an input—like a few pixels altered in a photograph—can sometimes cause the network to make a wildly incorrect prediction. To understand how fragile or robust a network is, scientists measure its "Lipschitz constant." Think of this number as a sensitivity gauge: a low value means the network changes its output only slightly when the input changes slightly, while a high value indicates that small nudges can lead to massive, unpredictable swings. For years, researchers have known that calculating this exact sensitivity for complex networks is incredibly difficult, often requiring so much computing power that it becomes practically impossible as the networks grow larger.

A specific type of network called an input-convex neural network was recently proposed as a way to make these systems more stable and easier to analyze. In these networks, the rules are stricter: the connections between layers are forced to be non-negative, which guarantees that the network behaves in a mathematically predictable, convex way. This restriction seemed like a promising shortcut. For some types of sensitivity measurements, this restriction did indeed make the problem solvable in a reasonable amount of time. However, for a broad and important class of measurements involving standard distance calculations, it remained an open question whether this architectural restriction was enough to make the problem easy to solve, or if the difficulty would persist.

A team of researchers has now answered that question with a definitive negative. They proved that even with the strict rules of input-convex networks, calculating the sensitivity for these specific measurements remains computationally intractable as the size of the network increases. Their work shows that no clever algorithm can solve this problem efficiently; the only way to find the answer is to essentially check every possible configuration one by one, a method that becomes impossibly slow as the network grows. This finding closes a significant chapter in the study of neural network robustness, revealing that the promise of input-convex networks does not extend to making all sensitivity calculations easy.

The researchers approached this problem by translating the behavior of the neural network into a geometric shape known as a zonotope. You can imagine a zonotope as a multi-dimensional block formed by stacking many smaller line segments together. The question of how sensitive the network is becomes a question of finding the longest possible line that can be drawn from the center of this block to its edge, measured in a specific way. While finding the longest line is easy for some shapes and easy for some types of distance measurements, the researchers discovered that for the specific measurements relevant to these networks, the problem becomes exponentially harder as the number of dimensions increases.

To prove this, the team constructed a series of logical bridges connecting the problem of measuring network sensitivity to a famous, notoriously difficult puzzle in computer science called the Multicolored Clique problem. This puzzle asks whether one can pick a specific number of items from different groups such that every pair of picked items is connected. The researchers showed that if you could quickly find the longest line in their geometric shapes, you could also quickly solve this difficult puzzle. Since computer scientists widely believe that the puzzle cannot be solved quickly, this implies that finding the longest line in these shapes cannot be done quickly either. They demonstrated this connection using two different mathematical constructions, one of which relied on elementary techniques and the other on deeper geometric insights, both leading to the same conclusion.

The study further explored how this difficulty changes when the type of distance measurement is altered. While the problem was already known to be hard for some measurements, it was unclear if it remained hard for a wide range of other standard measurements used in mathematics and engineering. The team proved that the difficulty holds true for every fixed type of standard distance measurement in this range. They achieved this by showing that the geometric shapes used for one type of measurement could be transformed into shapes for another type without losing the essential difficulty of the problem. This means that the barrier to solving these problems is not a quirk of a single measurement method but a fundamental property of the geometry involved.

The implications of this work are significant for the future of artificial intelligence safety and design. It clarifies that simply making a neural network input-convex is not a silver bullet that makes all aspects of its behavior easy to verify. While these networks are useful for ensuring the output is convex, they do not automatically grant the ability to quickly calculate how sensitive they are to small errors or attacks. The researchers also noted that their findings suggest that the brute-force methods currently used by scientists—checking every possible scenario—are essentially the best we can hope for under current assumptions about computing limits. There is no hidden shortcut waiting to be discovered that would allow these calculations to be performed quickly on large networks.

In a unique addition to their paper, the authors also reflected on their own research process, acknowledging that they used artificial intelligence tools to help generate the initial ideas for their proofs. They described how the AI provided raw mathematical arguments that were technically correct but lacked clarity and intuitive understanding. The human researchers then spent considerable time refining these arguments, stripping away unnecessary complexity, and uncovering the geometric intuition that made the proof convincing and clear. They argued that while AI can be a powerful tool for generating ideas, the human role in shaping those ideas into understandable, conceptually sound mathematics remains irreplaceable. Their work stands as a testament to the idea that in the age of AI, the value of human insight lies not just in finding answers, but in explaining them in a way that reveals the underlying truth.

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

Problem Statement
The paper addresses the computational complexity of determining the $L_p$ -Lipschitz constant for two-layer Input Convex Neural Networks (ICNNs) with ReLU activations. An ICNN is a restricted architecture where output weights are nonnegative, ensuring the computed function is convex. While computing the exact $L_p$ -Lipschitz constant for general ReLU networks is known to be NP-hard and W[1]-hard with respect to the input dimension $d$ , the complexity for ICNNs remained open for $p \in (1, \infty)$ . Specifically, it was unknown whether the restriction to ICNNs renders the problem fixed-parameter tractable (FPT) or polynomial-time solvable for these norms, contrasting with the known polynomial-time solvability for $L_1$ and FPT status for $L_\infty$ .

Through a duality established in prior work, computing the $L_p$ -Lipschitz constant for a two-layer ReLU ICNN is equivalent to maximizing the $L_q$ -norm (where $1/p + 1/q = 1$ ) over a zonotope generated by the network's weights. Consequently, the paper focuses on the $L_p$ -norm maximization problem over zonotopes in $\mathbb{R}^d$ for $p \in (1, \infty) \cap \mathbb{Q}$ .

Methodology
The authors establish hardness results through a series of parameterized reductions from the Multicolored Clique problem, which is W[1]-hard with respect to the clique size $k$ . The methodology proceeds in three main stages:

Reduction for $L_2^2$ -Max on Zonotopes:
The authors provide two distinct reductions from Multicolored Clique to the problem of maximizing the squared $L_2$ -norm ( $L_2^2$ -Max) over a zonotope in dimension $d = O(k)$ .
- Explicit Reduction (2k+1 dimensions): This construction uses elementary techniques to define a generator matrix. It employs a "gadget" based on vectors on the $L_2$ -unit circle (derived from Lemma 4.1) to encode the selection of nodes. The reduction ensures that a high $L_2^2$ -norm is achieved if and only if the selected nodes form a clique. The dimension is kept linear in $k$ by carefully balancing "node" and "edge" generators.
- Non-Explicit Reduction (2k dimensions): This approach utilizes the support function of a centrally symmetric zonotope. It constructs a function $F = V + \eta E$ , where $V$ (the node term) penalizes deviations from valid node selections and $E$ (the edge term) rewards adjacent node pairs. The edge term is constructed non-explicitly by solving a linear program based on an interpolation result (Proposition 4.4), which allows prescribing values for the support function on specific directions. This reduction achieves a tighter dimension of $2k$ .
Transfer to $L_p^p$ -Max ( $p \in (1, \infty)$ ):
To extend the hardness from $L_2^2$ to arbitrary $L_p^p$ , the authors employ a geometric embedding technique. They embed the original zonotope $Z(A)$ into a higher-dimensional space via an affine map $\Phi_\varepsilon(x) = \mathbf{1} + \varepsilon Jx$ , where $Jx = (x, -x)$ . This places the zonotope in the affine tangent hyperplane of the $L_p$ -sphere at the all-ones vector. Using a Taylor approximation (Lemma 5.1), they show that for sufficiently small $\varepsilon$ , the $L_p^p$ -norm of the embedded points approximates a constant plus a term proportional to the original $L_2^2$ -norm. This preserves the gap between "yes" and "no" instances of the Multicolored Clique problem.
Transfer to $L_p$ -Max:
Since the threshold for $L_p$ -Max must be rational, the authors cannot simply take the $p$ -th root of the $L_p^p$ threshold (which may be irrational). Instead, they utilize the positive gap established in the $L_p^p$ reduction to compute a rational threshold $T$ lying strictly between the $p$ -th roots of the "no" and "yes" bounds (Lemma 5.3), thereby transferring the hardness to the $L_p$ -norm maximization problem.

Key Contributions and Results

W[1]-Hardness: The paper proves that for every fixed $p \in (1, \infty) \cap \mathbb{Q}$ , maximizing the $L_p$ -norm (and $L_p^p$ -norm) over a zonotope in $\mathbb{R}^d$ is W[1]-hard with respect to the dimension $d$ .
ETH Lower Bounds: Assuming the Exponential Time Hypothesis (ETH), the problem cannot be solved in time $\rho(d)N^{o(d)}$ for any computable function $\rho$ , where $N$ is the input bit-length. This implies that brute-force enumeration of zonotope vertices (which runs in $O(N^{d-1})$ ) is essentially optimal.
ICNN Implications: By duality, these results imply that computing the $L_p$ -Lipschitz constant for two-layer ReLU ICNNs is also W[1]-hard with respect to the input dimension and admits no sub-exponential time algorithm under ETH.
Resolution of Open Problems: The work resolves the open question posed at COLT 2025 regarding the parameterized complexity of ICNN Lipschitz constants and the norm maximization over zonotopes for $p \in (1, \infty)$ .

Significance and Claims
The paper claims that restricting a ReLU network to be input-convex does not make the problem of computing $L_p$ -Lipschitz constants tractable for $p \in (1, \infty)$ , in contrast to the $L_1$ and $L_\infty$ cases. The results demonstrate that the "curse of dimensionality" persists even for this restricted, convex architecture.

The authors explicitly frame their contribution not just as a hardness proof, but as a clarification of the underlying mathematical intuition. They note that while independent proofs of the W[1]-hardness for $L_2$ and $L_p$ were generated by AI pipelines and other groups, their paper prioritizes a clear exposition of the conceptual intuitions behind the reductions. They highlight the geometric insights of their non-explicit reduction (using support functions and interpolation) and the explicit gadget construction as valuable contributions in their own right. The paper also serves as a case study in the age of AI, advocating for a "human layer" that digests machine-generated proofs to extract conceptual clarity and ensure rigorous, understandable exposition.

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

More like this