Convex Networks Remain Hard to Certify: Dimension-Accuracy Barriers for Lipschitz Constants
2026-08-17 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study a special type of neural network that is convex in its inputs, which makes finding minimum values easier. However, they show that calculating how quickly the network's output can change globally (the Lipschitz constant) is actually very hard, even with few input dimensions. They prove that no efficient algorithms exist for exact or close approximations unless major complexity theory breakthroughs happen. This work answers an open theoretical question and reveals limits on how well one can estimate sensitivity for these networks based on input size and accuracy.
Input-convex neural networksReLU networkLipschitz constantNP-completenessW[1]-hardnessExponential Time HypothesisZonotopesParameterization by dimensionApproximation algorithmsConvex optimization
Authors
Pahan Dewasurendra, Subhashini Jayawardhana
Abstract
Input-convex neural networks permit globally tractable minimization over their inputs, so one might expect their global regularity to be tractable in low input dimension. We prove exact and accuracy-sensitive barriers to this expectation. Given a bias-free one-hidden-layer ReLU network $f(x)=\sum_{r=1}^n \mathrm{ReLU}(a_r^\top x)$ with unit positive output weights, deciding whether its global Euclidean Lipschitz constant is at least a rational threshold is NP-complete and W[1]-hard when parameterized by the input dimension $d$. The same holds on the unit ball and with integral first-layer weights having at most nine nonzeros. More sharply, no deterministic multiplicative approximation scheme runs in $g(d)\mathrm{poly}(\mathcal B,1/\varepsilon)$ time unless FPT equals W[1]. Under the Exponential Time Hypothesis, no such algorithm runs in $g(d)(\mathcal B+1/\varepsilon)^{o(d/\log d)}$ time. Thus accuracy cannot have a polynomial dependence separated from dimension. The exact result resolves the Euclidean case of an open problem posed at COLT 2025 and left open by the ICLR 2026 parameterized hardness theory for general two-layer networks. The approximation barrier is specific to generator-presented zonotopes, complementing known $(1/\varepsilon)^{O(d)}$-time schemes and an analogous barrier for halfspace-presented polytopes. Our lifted-selector reduction has an inverse-polynomial radial gap, proved through a quantitative theorem for rational cyclic zonogons. Equivalently, the results apply to Euclidean zonotope radius and positive-semidefinite binary quadratic maximization parameterized by rank. Convexity makes minimization easy, but it does not make global sensitivity fixed-parameter tractable or permit a dimension-separated fully polynomial accuracy guarantee.