证明了神经网络的Lp Lipschitz常数计算在高维下极难，且暴力枚举已是最好方法。
Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes
- 通过将问题转化为对称多面体上的Lp范数最大化，建立数学模型。
- 证明对任意有理数p∈(1,∞)，该问题在维度d上W[1]-难。
- 结果表明在高维下无法避免指数时间开销，适合理论研究者参考。
Lipschitz常数是衡量神经网络对输入扰动敏感性的标准方式，但即使对浅层ReLU网络也难以计算。本文研究两层输入凸神经网络（ICNNs）的Lp-Lipschitz常数计算问题，其等价于在对称多面体（zonotope）上最大化对偶范数。已知L₁和L∞范数在多面体上可分别用固定参数算法和多项式时间算法求解，但其余Lp范数的参数化复杂度仍未知。本文证明：对任意固定的有理数p∈(1,∞)，在ℝᵈ中最大化Lp范数是关于维度d的W[1]-难问题。进一步，该结果表明在指数时间假设下，暴力枚举算法已本质上最优。由对偶性，相同结论适用于两层ReLU ICNN的Lp-Lipschitz常数计算。证明首先针对L₂建立，再通过合适的泰勒逼近推广至任意固定有理数p∈(1,∞)。本工作解决了COLT'25提出的开放问题，与多个独立并发工作共同解决此难题。本文强调数学推导与概念直觉的清晰呈现，并明确描述研究过程，包括使用LLMs辅助探索。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。