研究/論文初出 8/26 02:47
入力凸ニューラルネットワークの$L_p$-Lipschitz定数とゾノトープ上の$L_p$-ノルム最大化のパラメータ化複雑性
Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes
https://export.arxiv.org/api/query2026/8/26
AI要約
入力凸ニューラルネットワーク（ICNN）における$L_p$-Lipschitz定数の計算複雑性を分析。2層ICNNにおける$L_p$-Lipschitz定数の計算は、ゾノトープ上の$L_p$-ノルム最大化問題に帰着することを明らかにし、その計算困難性を研究する。
AI要点
- 入力凸ニューラルネットワーク（ICNN）のLp-Lipschitz定数の計算問題が、ゾノトープ上のLp-ノルム最大化問題に還元された。
- 固定p∈(1,∞)∩ℚに対し、d次元ゾノトープ上のLp-ノルム最大化問題は、次元dに関してW[1]-hardであることが証明された。
- これは、指数時間仮説の下では、この問題に対する総当たり法がほぼ最適であることを意味する。
- この結果は、2層ReLU ICNNのLp-Lipschitz定数を計算する問題にも適用される。
- 本研究は、ゾノトープノルム最大化と2層ICNNのLipschitz定数に関するパラメーター化複雑性の未解決問題を解決した。
なぜ重要か
ICNNのLipschitz定数の計算複雑性に関する理論的な限界が示され、深層学習モデルの解析と設計における計算論的な課題を明らかにする。