ICNN Lipschitz Constant Computation Proven W[1]-Hard

Why This Article is Gaining Attention Now

Lipschitz constant is a representative method for quantifying the robustness of neural networks. This value, which considers how much the output can change when the input has small perturbations, is repeatedly used in adversarial robustness verification, generalization theory, and verifiable AI research. However, computing Lipschitz constant exactly even for shallow ReLU networks has long been known to be difficult.

This paper rigorously identifies this computational complexity using computational complexity theory. In particular, targeting the restricted structure of input-convex neural networks (ICNN), it shows that the L_p-Norm Lipschitz constant computation problem is W[1]-hard. Here, W[1]-hard means that, under the exponential time hypothesis (ETH), brute-force enumeration is essentially the minimum possible. Since this is an exact complexity bound rather than an empirical fact, it carries significant weight.

Background: ICNN and Zonotope Maximization

ICNN is a model that uses ReLU as the hidden-layer activation function while restricting output weights to nonnegative values. This single restriction makes the network output convex with respect to the input, and this structure has been widely used in applications such as meaning preservation in pursuit-evasion games, plan recognition, and uncertainty quantification.

According to the document, the problem of computing the L_p-Lipschitz constant for 2-layer ReLU ICNNs exactly corresponds to the problem of maximizing the L_p-norm over zonotopes. A zonotope is a type of centrally symmetric polytope, understood as a set formed by composing a linear transformation of the norm with an affine shift. Because of this correspondence, the two problems share the same computational difficulty.

Core Result: Intermediate p Is Hard

Maximization for L_1 and L_∞ had known fixed-parameter tractable algorithms and polynomial-time algorithms, respectively. The problem lies with intermediate p; the paper proves that for every fixed rational number p ∈ (1, ∞), L_p-norm maximization over zonotopes is W[1]-hard with respect to dimension d.

The proof strategy is clear. After first proving for L_2, they transfer the structure to other fixed p values using appropriate Taylor approximations. This stepwise approach is the technical key to extending the hardness obtained at p=2 to arbitrary 1<p<∞. Consequently, the computation of the L_p-Lipschitz constant for 2-layer ReLU ICNNs is also classified at the same difficulty.

Why It Matters

This result theoretically clarifies that Lipschitz constant tracking, which is actively used in robustness verification, can be structurally difficult. In particular, if exact computation is difficult even for intermediate p under restricted structures like ICNNs, then exact computation paths other than logical approximations or upper-bound estimation methods are practically limited.

It is also interesting that the proof process mentioned the use of LLMs. The fact that the researcher publicly disclosed using language models in the research process itself serves as a case that shows both the limitations and possibilities of AI-assisted research.

Implications and Limitations

While this paper clarifies the difficulty of exact computation for a specific architecture, specifically 2-layer ReLU ICNNs, extending to deeper networks or general non-partitioned architectures remains for future work. Moreover, the result concerns exact computation and does not preclude approximation bounds or Lipschitz upper-bound estimates. Nevertheless, this research serves as a direct benchmark for verification-oriented model research and complexity-based algorithm design.

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