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

技术摘要：输入凸神经网络的 $L_p$-利普希茨常数的参数化复杂度以及分量型（Zonotope）上的 $L_p$ 范数最大化问题

问题陈述
本文研究了确定具有 ReLU 激活函数的两层输入凸神经网络（ICNN）的 $L_p$-利普希茨常数的计算复杂度。ICNN 是一种受限的架构，其输出权重为非负，从而确保了计算出的函数是凸的。虽然对于一般 ReLU 网络，计算精确的 $L_p$-利普希茨常数已知是 NP-hard 且相对于输入维度 $d$ 是 W[1]-hard 的，但对于 $p \in (1, \infty)$，ICNN 的复杂度情况仍处于开放状态。具体而言，此前尚不清楚将问题限制在 ICNN 是否会使该问题变为固定参数可处理（FPT）或多项式时间可解，这与已知的 $L_1$ 情况（多项式时间可解）和 $L_\infty$ 情况（FPT）形成了对比。

通过先前研究建立的对偶性，计算两层 ReLU ICNN 的 $L_p$-利普希茨常数等价于在由网络权重生成的分量型（zonotope）上最大化 $L_q$ 范数（其中 $1/p + 1/q = 1$）。因此，本文的研究重点是 $\mathbb{R}^d$ 中分量型上的 $L_p$-范数最大化问题，其中 $p \in (1, \infty) \cap \mathbb{Q}$。

方法论
作者通过一系列从 多色团（Multicolored Clique） 问题（该问题相对于团的大小 $k$ 是 W[1]-hard 的）进行的参数化归约来建立硬度结果。该方法分为三个主要阶段：

1. 分量型上的 $L_2^2$-Max 归约：
   作者提供了两种从多色团到在维度 $d = O(k)$ 下的分量型最大化平方 $L_2$-范数（$L_2^2$-Max）问题的不同归约方式。

   • 显式归约（2k+1 维）： 该构造使用初等技术来定义生成矩阵。它采用了一个基于 $L_2$ 单位圆向量（源自引理 4.1）的“小部件”（gadget）来编码节点的选择。该归约确保当且仅当所选节点构成一个团时，才能实现较高的 $L_2^2$-范数。通过仔细平衡“节点”和“边”生成器，保持了维度与 $k$ 成线性关系。
   • 非显式归约（2k 维）： 该方法利用中心对称分量型的支撑函数。它构造了一个函数 $F = V + \eta E$，其中 $V$（节点项）惩罚偏离有效节点选择的行为，而 $E$（边项）奖励相邻的节点对。边项是通过求解一个基于插值结果（命题 4.4）的线性规划来非显式构造的，这允许在特定方向上规定支撑函数的值。该归约实现了更紧凑的 $2k$ 维度。

2. 向 $L_p^p$-Max ($p \in (1, \infty)$) 的转移：
   为了将 $L_2^2$ 的硬度扩展到任意 $L_p^p$，作者采用了几何嵌入技术。他们通过仿射映射 $\Phi_\varepsilon(x) = \mathbf{1} + \varepsilon Jx$（其中 $Jx = (x, -x)$）将原始分量型 $Z(A)$ 嵌入到一个更高维的空间中。这使得该分量型位于 $L_p$ 球面上全 1 向量处的仿射切超平面内。利用泰勒近似（引理 5.1），他们证明了对于足够小的 $\varepsilon$，嵌入点的 $L_p^p$-范数近似于一个常数加上一个与原 $L_2^2$-范数成正比的项。这保留了多色团问题中“是”与“否”实例之间的间隙。

3. 向 $L_p$-Max 的转移：
   由于 $L_p$-Max 的阈值必须是有理数，作者不能简单地对 $L_p^p$ 的阈值取 $p$ 次方根（因为结果可能是无理数）。相反，他们利用在 $L_p^p$ 归约中建立的正向间隙，计算出一个位于“否”和“是”界限的 $p$ 次方根之间的有理阈值 $T$（引理 5.3），从而将硬度转移到 $L_p$-范数最大化问题。

核心贡献与结果

• W[1]-Hardness： 本文证明了对于每个固定的 $p \in (1, \infty) \cap \mathbb{Q}$，在 $\mathbb{R}^d$ 中最大化分量型上的 $L_p$-范数（及 $L_p^p$-范数）相对于维度 $d$ 是 W[1]-hard 的。
• ETH 下界： 在指数时间假设（ETH）成立的前提下，该问题无法在时间 $\rho(d)N^{o(d)}$ 内解决，其中 $\rho$ 是任何可计算函数，$N$ 是输入比特长度。这意味着对分量型顶点进行暴力枚举（运行时间为 $O(N^{d-1})$）本质上是接近最优的。
• ICNN 含义： 通过对偶性，这些结果意味着计算两层 ReLU ICNN 的 $L_p$-利普希茨常数对于输入维度也是 W[1]-hard 的，并且在 ETH 下不存在亚指数时间算法。
• 解决开放问题： 本工作解决了 COLT 2025 提出的关于 $p \in (1, \infty)$ 时 ICNN 利普希茨常数的参数化复杂度和分量型上范数最大化问题的开放问题。

意义与主张
本文声称，将 ReLU 网络限制为输入凸（input-convex）并不能使计算 $p \in (1, \infty)$ 时 $L_p$-利普希츠常数的问题变得易于处理，这与 $L_1$ 和 $L_\infty$ 的情况不同。结果表明，即使在这种受限的凸架构下，“维度诅咒”依然存在。

作者明确指出，他们的贡献不仅是一个硬度证明，更是一种对底层数学直觉的澄清。他们指出，虽然关于 $L_2$ 和 $L_p$ 的 W[1]-hard 性的独立证明是由 AI 流水线和其他团队生成的，但他们的论文优先考虑了对归约背后概念直觉的清晰阐述。他们强调了其非显式归约（使用支撑函数和插值）的几何洞察力以及显式小部件构造的几何价值。本文也作为一个人工智能时代的案例研究，倡导通过“人类层”来消化机器生成的证明，以提取概念清晰度并确保严谨、易懂的阐述。