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

• URL: http://arxiv.org/abs/2608.24865v1
• Date: Tue, 25 Aug 2026 17:47:37 GMT
• Title: Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes
• Abstract summary: Lipschitz constants standard way to the sensitivity of networks to input neurals.<n>We prove that brute-force is essentially optimal for this problem.
• Score: 10.97628500062133
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• A law of robustness for two-layer neural networks with arbitrary weights [0.0]
  Bubeck, Li and Nagaraj conjectured that, for generic data, any two-layer neural network with $m$ neurons that fits noisy labels must have Lipschitz constant.<n>We prove the conjectured law, up to one logarithmic factor, for every continuous piecewise-linear activation in particular for ReLU networks.
  arXiv  Detail & Related papers  (2026-07-08T17:44:15Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  We recast qubit-efficient optimization as a geometry problem.<n>Local-consistency problem coincides exactly with the Sherali-Adams level-2 polytope $mathrmSA(2)$.
  arXiv  Detail & Related papers  (2025-11-11T15:38:57Z)
• Parameterized Hardness of Zonotope Containment and Neural Network Verification [9.076330553662876]
  We prove that deciding positivity of a function $fcolonmathbbRdtomathbbR$ computed by a 2-layer ReLU network is W[1]-hard when parameterized by $d$.<n>We also show that approximating the maximum within any multiplicative factor in 2-layer ReLU networks, computing the $L_p$-Lipschitz constant for $pin(0,infty)$ in 2-layer networks, and approximating the $L_p$-Lipschitz constant in 3-layer networks are NP
  arXiv  Detail & Related papers  (2025-09-26T18:59:59Z)
• Learning Networks from Wide-Sense Stationary Stochastic Processes [7.59499154221528]
  A key inference problem here is to learn edge connectivity from node outputs (potentials)<n>We use a Whittle's maximum likelihood estimator (MLE) to learn the support of $Last$ from temporally correlated samples.<n>We show that the MLE problem is strictly convex, admitting a unique solution.
  arXiv  Detail & Related papers  (2024-12-04T23:14:00Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.