CS Paper Radar

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

cs.CC cs.DMcs.LGcs.NE ·submitted 2026-08-25 17:47 UTC · v2
theory

Abstract

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.

Comment
26 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

On the (non-)closedness of the set of ReLU networks

cs.LG math.CAmath.FAmath.NA+1 ·2026-11-06 ·Eloi Martinet, Leon Bungert
theory similarity 0.70
Abstract · 27 pages, 6 figures

We prove that the set $\mathcal{N}_N$ of ReLU networks with one hidden layer and at most $N\in\mathbb N$ neurons is weakly closed in $W^{1,p}(Ω)$, for a bounded connected open set $Ω\subset\mathbb R^d$. Consequently, every coercive, weakly lower semicontinuous energy on this space attains its minimum over $\mathcal{N}_N$. This covers the Deep Ritz method with convex integrands, Sobolev training and Lipschitz learning. Moreover, as the weight decay parameter tends to zero, minimizers of the regularized problem converge, up to subsequences, to minimizers with minimal parameter norm. We also prove that the set of ReLU networks with two hidden layers of bounded widths is not closed in $W^{1,p}(Ω)$ or in $C(\overlineΩ)$. This disproves a conjecture of Petersen, Raslan and Voigtlaender.

0.16

Error bounds in Sobolev norms for approximations with norm constrained ReLU neural networks

cs.LG stat.ML ·2026-09-17 ·Xianjun Li, Yunfei Yang
similarity 0.69
Abstract

Recent studies have shown that smooth functions can be well approximated by ReLU neural networks with path norm constraint on the weights. We extend these results from uniform approximation to approximation in Sobolev norm. Specifically, we analyze how well Sobolev functions in $W^{n,p}$ can be approximated by neural networks with width $W$, depth $L$ and path norm bounded by $K$, when the approximation error is measured in the $W^{1,p}$-norm. For shallow networks with depth $L=1$, we derive the approximation error bound $\mathcal{O}(\max\{W^{-(n-1)/d}, K^{-(n-1)/(s-n)}\})$, when the smoothness index satisfies $n<s=(d+3)/2$ and the input is $d$-dimensional. For deep networks, we remove the restriction on the smoothness by showing that the approximation bound $\mathcal{O}(K^{-(n-1)/(d+d/p+1)})$ holds if the width $W$ and depth $L$ are sufficiently large.

0.07

Structure-Preserving Neural Approximation of Convex, Semiconvex, and Quasiconvex Functions

cs.LG math.OC ·2026-11-18 ·Yeachan Park, Yeoneung Kim
similarity 0.69
Abstract

Input convex neural networks provide a natural way to enforce convexity globally through architectural constraints. We study how this structure-preserving approximation framework extends to semiconvex, quasiconvex, and convex transformable functions. For $C^{1,1}$ convex functions on compact convex domains, we establish the sharp $W^{1,p}$ minimax rate $m^{-1/d}$ under max-affine approximation with $m$ affine pieces, and show that every max-affine function admits an exact bounded-width ICNN representation with complexity linear in $m$. The same $W^{1,p}$ approximation rate extends to semiconvex functions through quadratic lifting and to convex transformable functions through monotone composition. For general Lipschitz quasiconvex functions, we develop a quantitative finite-probe approximation theory based on monotone responses to affine projections and obtain a structure-preserving IqCNN with an $L^\infty$ approximation guarantee. We further show that these approximation results extend to ReLU-transferable smooth activations, including Softplus and ELU. Numerical experiments on PDE-based approximation problems compare the proposed architectures with parameter-matched MLPs and validation-tuned shape penalties, demonstrating global structural validity without penalty tuning while maintaining competitive approximation accuracy. Overall, the results identify recoverable convex latent structure as the key mechanism enabling gradient-level structure-preserving approximation beyond convexity.

0.29

NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks

cs.LG ·2026-10-08 ·Sangrock Lee
top venuetheory similarity 0.66
Abstract

A fundamental question in neural network architecture optimization is whether the minimum hidden-neuron count required to approximate a target function within a prescribed tolerance can be computed efficiently. This paper resolves this question for two-hidden-layer ReLU networks under an $L^p(\mathbb{R}^d,\mathbb{R}^m)$ approximation constraint. For every fixed $d \ge 1$, $m \ge 1$, and $1 \le p < \infty$, we prove that computing the optimum exactly is NP-hard. The result holds even when the target is represented by a rational ReLU network whose realization is nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. The polynomial-time reduction from 3-SAT produces an architecture gap in which unsatisfiable formulas yield an optimum of zero, whereas satisfiable formulas yield an optimum of at least $d+2$. The proof constructs compactly supported polyhedral frustum functions realized by two-hidden-layer ReLU networks and establishes the $L^p$-density of finite linear combinations of box-frustum functions. The results offer theoretical justification for employing heuristic approximation methods in the design of ReLU neural networks, illustrating that attaining a minimal configuration within polynomial time is computationally unachievable.

0.63

$\ell_p$-Norm Maximization over Zonotopes Is W[1]-Hard

cs.CC cs.CG ·2026-08-16 ·Yang Cao, Haoran Qi, Hanzhi Wang
theory similarity 0.65
Abstract

We study $\ell_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mathrm{poly}(L)$ time, but fixed-parameter tractability in the ambient dimension $d$ was open [FGHS25]. We prove W[1]-hardness and, under the Exponential Time Hypothesis (ETH), exclude $ρ_p(d)L^{o(d)}$ time, even for $5$-sparse generators, by encoding binary CSP constraints with normalized positive cap generators. We also give a deterministic $(1-\varepsilon)$-approximation with $\varepsilon^{-(d-1)/2}$ dependence and, among algorithms with fixed-degree polynomial dependence on $L$, rule out $(1/\varepsilon)^{o(d)}$ dependence under ETH. Support-function duality transfers the results to positive-output two-layer ReLU networks.

0.42

Optimal Deep Nonparametric Regression with Uniformly Bounded Lipschitz Constants

cs.LG stat.MLmath.ST ·2026-11-18 ·Jiaxin Shi, Ziyuan Chen, Jian Huang, Hansheng Wang
similarity 0.65
Abstract

Stability under input perturbations is necessary for deep neural network estimators in many applications involving noisy covariates or estimated features. Weight norm constraints are widely used to control sensitivity to input perturbations by bounding the Lipschitz constant of neural networks. However, existing approximation results under fixed bounds on standard norm products are insufficient to establish optimal statistical rates. In this paper, we establish a sharp approximation theory for deep ReLU networks under a split spectral norm product constraint. This theoretical result shows that sufficiently smooth Hölder functions can be uniformly approximated to arbitrary accuracy as the network depth increases, with the norm-product bound held fixed. We then propose a penalized least squares estimator for deep nonparametric regression. The resulting estimator has a uniformly bounded Lipschitz constant while still achieving the optimal nonparametric rate up to a logarithmic factor. As applications, we establish optimal prediction rates for two-stage learning and provide robustness guarantees under adversarial input perturbations. Numerical studies show that the penalized estimator has well-controlled sensitivity to input perturbations and prediction accuracy comparable to that of classical deep network methods.

0.09

Input convex neural networks as surrogates in mathematical optimisation

cs.LG math.OC ·2026-08-10 ·Yu Liu, Jan Kronqvist, Fabricio Oliveira
similarity 0.64
Abstract

Embedding trained neural networks as surrogates within optimisation problems is an established practice in operations research. The prevailing approach uses feedforward neural networks (FNNs) with ReLU activations, whose piecewise-linear structure admits an exact but computationally intensive mixed-integer programming (MIP) reformulation as the networks grow. We advocate input convex neural networks (ICNNs) as structurally superior surrogates when the underlying response is approximately convex or concave. The convex architecture offers two computational advantages. First, the ICNN-MIP formulation tends to yield a tighter linear programming (LP) relaxation than its FNN-MIP counterpart, with no integrality gap in favourable instances. Second, ICNNs uniquely admit an LP-based reformulation via epigraph representations of ReLU activations, though this embedding is not always exact. When it is not, we exploit the properties of ICNNs to construct the strongest continuous relaxation over box domains, namely, the convex hull of the ICNN's graph, bounded below by the epigraph and above by the concave envelope; this construction is tractable under input convexity but hard for general ReLU networks. On this basis, we develop a branch-and-bound algorithm that builds this relaxation at each node, branches directly on input variables rather than intermediate variables as in MIP reformulations, and terminates at the root node whenever the epigraph embedding is valid. Case studies on humanitarian food aid, oil well routing, and wine blending show that ICNN surrogates match FNN accuracy and deliver gains in solve time and scalability, supporting ICNN as the default surrogate when the underlying function is convex, concave, or well-approximated as such.

0.40

Boundary Geometry Determines Optimal Shallow ReLU Approximation under Weighted Coefficient Constraints

cs.LG stat.MLmath.FAmath.MG ·2026-10-27 ·Jia-Qi Yang, Lei Shi
similarity 0.63
Abstract · 92 pages, 2 figures, 2 tables

We study how boundary geometry affects $L^q$ approximation by shallow ReLU neural networks on convex bodies $K\subset\mathbb R^d$. The target classes are unit balls of weighted variation spaces that can enlarge classical spaces by incorporating domain geometry into constraints on output coefficients. We establish upper and lower bounds for arbitrary convex bodies and determine the optimal polynomial approximation exponents for all planar convex bodies and their products with polytopes, including cubes and circular cylinders. For $C^2$ convex bodies, we determine the optimal exponents in a dimension-dependent range of $q$ extending beyond $2$. When all principal curvatures are positive, the result extends to every finite $q\ge2$. For these classes, the dependence of the optimal exponent on the domain is captured by a single geometric growth exponent associated with small boundary caps. We also identify sharp weight thresholds for retaining the classical approximation exponent and improve previous weights on Euclidean balls while preserving the classical $L^2$ approximation rate. When the target is given as a finite ReLU network, the upper bounds can be realized by a compressed network using only the original neurons, without increasing the weighted coefficient sum. These results show that boundary geometry can change the optimal exponent even when dimension, error norm, and weighting rule are fixed.

0.26