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

技術要約：入力凸ニューラルネットワークにおける $L_p$-リプシッツ定数のパラメータ化複雑性とゾノトープ上の $L_p$ ノルム最大化

問題提起
本論文は、ReLU活性化関数を持つ2層の入力凸ニューラルネットワーク（ICNN）における $L_p$-リプシッツ定数を決定することの計算複雑性を取り扱う。ICNNは、出力重みが非負であることを保証する制限されたアーキテクチャであり、これにより計算される関数が凸関数となる。一般的なReLUネットワークの正確な $L_p$-リプシッツ定数を計算することは、入力次元 $d$ に関してNP困難かつW[1]-困難であることが知られているが、ICNNへの制限が $p \in (1, \infty)$ において、問題を固定パラメータ実行可能（FPT）にするか、あるいは多項式時間で解けるかについては未解決であった。これは、$L_1$ では多項式時間で解け、$L_\infty$ ではFPTであるという既知の事実とは対照的である。

先行研究で確立された双対性を通じて、2層ReLU ICNNの $L_p$-リプシッツ定数を計算することは、ネットワークの重みによって生成されるゾノトープ上での $L_q$-ノルム（ここで $1/p + 1/q = 1$）を最大化することと等価である。したがって、本論文は、$\mathbb{R}^d$ におけるゾノトープ上の $L_p$-ノルム最大化問題に焦点を当てている。

手法
著者らは、**マルチカラー・クリーク（Multicolored Clique）**問題からのパラメータ化簡約を通じて、困難性の結果を確立している。マルチカラー・クリーク問題は、クリークサイズ $k$ に関してW[1]-困難である。その手法は、主に以下の3つの段階で構成される：

1. ゾノトープ上の $L_2^2$-Maxへの簡約：
   著者らは、次元 $d = O(k)$ のゾノトープ上での平方 $L_2$-ノルム（$L_2^2$-Max）の最大化問題への、マルチカラー・クリークからの2つの異なる簡約を示す。

   • 明示的な簡約（2k+1次元）： この構成は、生成行列を定義するために初等的な手法を用いている。ノードの選択をエンコードするために、$L_2$-単位円上のベクトルに基づく「ガジェット」（補題4.1より導出）を採用している。この簡約は、選択されたノードがクリークを形成する場合にのみ高い $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$ へ困難性を拡張するために、著者らは幾何学的埋め込み手法を用いる。元のゾノトープ $Z(A)$ を、アフィン写像 $\Phi_\varepsilon(x) = \mathbf{1} + \varepsilon Jx$ （ここで $Jx = (x, -x)$）を介して高次元空間へ埋め込む。これにより、ゾノトープを全成分1のベクトルにおける $L_p$-球のアフィン接超平面内に配置する。テイラー近似（補題5.1）を用いることで、十分に小さい $\varepsilon$ に対して、$L_p^p$-ノルムが元の $L_2^2$-ノルムに比例する項と定数の和で近似されることを示す。これにより、マルチカラー・クリーク問題の「Yes」インスタンスと「No」インスタンスの間のギャップが保持される。

3. $L_p$-Maxへの転送：
   $L_p$-Maxの閾値は有理数でなければならないため、単に $L_p^p$ の閾値の $p$ 乗根を取ることはできない（それは無理数である可能性がある）。代わりに、著者らは $L_p^p$ の簡約で確立された正のギャップを利用して、「No」の境界と「Yes」の境界の $p$ 乗根の間に位置する有理的な閾値 $T$ を計算し（補題5.3）、それによって $L_p$-ノルム最大化問題への困難性を転送する。

主な貢献と結果

• W[1]-困難性： 論文は、すべての固定された $p \in (1, \infty) \cap \mathbb{Q}$ について、$\mathbb{R}^d$ におけるゾノトープ上の $L_p$-ノルム（および $L_p^p$-ノルム）の最大化は、次元 $d$ に関してW[1]-困難であることを証明している。
• ETH下界： 指数時間仮説（ETH）を仮定すると、この問題は、入力ビット長を $N$ としたとき、いかなる計算可能な関数 $\rho$ に対しても $\rho(d)N^{o(d)}$ の時間では解けない。これは、ゾノトープの頂点の総当たり列挙（$O(N^{d-1})$ で実行可能）が実質的に最適であることを意味する。
• ICNNへの影響： 双対性により、これらの結果は、2層ReLU ICNNの $L_p$-リプシッツ定数を計算することが、入力次元に関してW[1]-困難であり、ETHの下で劣指数時間アルゴリズムを持たないことを示唆している。
• 未解決問題の解決： 本研究は、ICNTのリプシッツ定数および $p \in (1, \infty)$ におけるゾノトープ上のノルム最大化のパラメータ化複雑性に関して、COLT 2025で提起された疑問を解決するものである。

意義と主張
本論文は、ReLUネットワークを入力凸に制限することは、$L_1$ および $L_\infty$ の場合とは異なり、$p \in (1, \infty)$ における $L_p$-リプシッツ定数の計算を扱いやすくするものではないと主張している。これらの結果は、この制限された凸アーキテクチャにおいても「次元の呪い」が存続することを証明している。

著者らは、自らの貢献を単なる困難性の証明ではなく、基礎となる数学的直観の明確化として位置づけている。彼らは、$L_2$ および $L_p$ のW[1]-困難性の独立した証明がAIパイプラインや他のグループによって生成されたことを認めつつ、本論文は簡約の背後にある概念的な直観の明快な解説を優先していると述べている。彼らは、支持関数と補間を用いた非明示的な簡約の幾何学的洞察や、明示的なガジェット構成が、それ自体として価値のある貢献であることを強調している。また、本論文はAI時代のケーススタディでもあり、機械生成された証明を消化して概念的な明晰さを抽出し、厳密で理解可能な解説を保証するための「人間のレイヤー」の重要性を提唱している。