Metraipolis › archive › dc_7d80d89e97ca

Convex Networks Remain Hard to Certify: Dimension-Accuracy Barriers for Lipschitz Constants — arXiv:2608.16150

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.16150
License (as archived): CC0-1.0
Archived: 2026-10-19T00:29:37.406Z
SHA-256 of the archived text: e1cd96924ac76cf59ec38280664cd676c411da9b6610c9e9cda2b7b985769ae9
Stable URL of this page: https://metraipolis.com/documento/dc_7d80d89e97ca

How to cite

Convex Networks Remain Hard to Certify: Dimension-Accuracy Barriers for Lipschitz Constants — arXiv:2608.16150 — arXiv (en), https://arxiv.org/abs/2608.16150 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7d80d89e97ca (Metraipolis archive dc_7d80d89e97ca, sha256 e1cd96924ac76cf59ec38280664cd676c411da9b6610c9e9cda2b7b985769ae9)

BibTeX

@misc{dc7d80d89e97ca,
  title = {Convex Networks Remain Hard to Certify: Dimension-Accuracy Barriers for Lipschitz Constants — arXiv:2608.16150},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.16150},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7d80d89e97ca; sha256 e1cd96924ac76cf59ec38280664cd676c411da9b6610c9e9cda2b7b985769ae9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.16150. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-18 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.16150 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T23:35:48.556Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).