- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper investigates the computational complexity of computing exact -Lipschitz constants for two-layer ReLU input-convex neural networks (ICNNs), focusing on whether these problems become tractable when parameterized by the input dimension . The authors establish an equivalence between computing the Lipschitz constant of an ICNN and maximizing the corresponding dual norm over a zonotope.
The main contribution is proving that, for every fixed rational , exact -norm maximization over zonotopes and exact -Lipschitz constant computation for two-layer ReLU ICNNs are W[1]-hard with respect to . Under the Exponential Time Hypothesis (ETH), they further establish that no exact algorithm can achieve a running time of , implying that existing enumeration-based algorithms are essentially optimal in their asymptotic dependence on dimension. The proof uses a reduction from Multicolored Clique to -norm maximization over zonotopes, followed by a construction extending the hardness result to general rational . These findings address an open problem from COLT 2025, although the authors acknowledge concurrent independent results.
The validation is entirely theoretical, relying on formal complexity reductions, geometric constructions, and mathematical proofs. The paper provides two alternative hardness reductions but does not include numerical experiments, computational benchmarks, or empirical evaluations on neural networks. Consequently, its contribution is primarily to establishing worst-case computational hardness rather than developing or validating a practical Lipschitz estimation algorithm.
Critical strengths
The paper resolves an open problem from COLT 2025 by establishing W[1]-hardness for computing exact -Lipschitz constants of two-layer ReLU ICNNs for every fixed rational . Furthermore, the ETH-based lower bound rules out algorithms with running time , providing a strong characterization of the computational difficulty. This counts towards contribution because it establishes that input convexity alone does not guarantee tractability and clarifies the fundamental limitations of exact Lipschitz computation.
Critical weaknesses
Although the paper addresses an important open problem from COLT 2025, its main theoretical results substantially overlap with several concurrent works acknowledged in Section 1.2. In particular, Cao et al. (2026) establish W[1]-hardness for general rational , along with related ETH-based lower bounds and approximation results. While this paper provides a different geometric construction and improves the reduction dimension to for the case, it is unclear whether these differences lead to fundamentally stronger theoretical conclusions or broader implications. The main contribution therefore appears to be an alternative proof of results that have already been independently established. This limits the incremental novelty of the work and is my primary concern regarding acceptance.
Questions for authors
- Novelty relative to concurrent work
The paper acknowledges several concurrent works that establish similar W[1]-hardness results for -norm maximization over zonotopes. Could the authors clarify the main theoretical advantages of their approach beyond the improved reduction dimension and geometric interpretation? In particular, does the proposed geometric construction enable any stronger complexity results or extensions that are not readily obtainable from existing reductions? Clarifying these distinctions would help assess the novelty and significance of the contribution relative to concurrent work.
- Implications for approximate and practical Lipschitz certification
The paper establishes hardness for exact global -Lipschitz constant computation, while practical neural-network certification often relies on approximate bounds or domain-restricted Lipschitz estimates. Could the authors clarify whether their hardness constructions imply any meaningful limitations for approximate Lipschitz certification, such as computing bounds within a prescribed relative error, or for Lipschitz estimation over bounded input domains? Understanding which aspects of practical certification are affected by these hardness results would help assess the broader significance and applicability of the theoretical findings.
2 comments
Thank you for the response and the clarifications. Following the ICLR policy, I no longer weigh the concurrent results discussed in Section 1.2 against the submission, as they appeared only recently and are not peer-reviewed. The paper resolves the open problem posed at COLT 2025, and the novelty of the contribution stands. I have raised my score to 3.
Thank you for your careful reading and evaluation of our paper, and for your feedback. We believe we have addressed all raised questions in the responses below, and we are happy to answer any further questions.
Please see our general response for a discussion regarding our views on the novelty of our paper in light of the concurrent works. Additionally, we believe that the implicit technique (in particular, Proposition 4.2) that we used in the reduction of Section 4 is of interest on its own and could be applicable to other geometric problems involving zonotopes.
Since the function used in our construction is positively homogeneous, the hardness results transfer also to computing Lipschitz constants over bounded input domains (as long as the domain contains an open set around the origin). For example, hardness holds for computing the Lipschitz constant on λ⋅Bp (for any λ>0) for any scaled version of the Lp-unit ball Bp={x∈Rd:∥x∥p≤1}. We have included this in Section 5 of the paper (line 488-490).
As indicated in our response to Reviewer ArH7, our explicit reduction in the appendix implies that computing the Lp-Lipschitz constant within a relative error of ε=1/poly(n) is W[1]-hard for all fixed p∈(1,∞)∩Q. Regarding constant-factor approximation, the (1−ε)-approximation FPT algorithm of Shenmaier 2018 shows that approximation is tractable for small input dimensions. We now also discuss practical implications of our results in Section 6.