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等
发布时间: 2026-08-25
arXiv: 2608.24865

中文摘要

Lipschitz常数是量化神经网络对小输入扰动敏感度的标准方法，但即使对于浅层ReLU网络，计算它们也很困难。我们研究了双层输入凸神经网络（ICNN）的这个问题，这是一种非负输出权重强制凸性的受限架构。计算这些网络的Lp-Lipschitz常数等价于在zonotope上最大化对偶范数。虽然zonotope上的L1和L∞范数最大化分别允许固定参数和多项式时间算法，但其余Lp范数的参数化复杂性是开放的。我们证明，对于每个固定的p∈(1,∞)∩Q，在R^d中的zonotope上最大化Lp范数关于维度d是W[1]-难的。此外，我们的困难结果意味着在指数时间假设下，暴力枚举算法对此问题本质上是最佳的。通过对偶性，相同困难结果适用于计算双层ReLU ICNN的Lp-Lipschitz常数。

原文摘要

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 th...

自动采集于 2026-08-27

#论文 #arXiv #理论 #小凯