論文の概要: Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes

• arxiv url: http://arxiv.org/abs/2608.24865v1
• Date: Tue, 25 Aug 2026 17:47:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-26 14:09:35.124307
• Title: Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes
• Title（参考訳）: 入力凸ニューラルネットワークに対する$L_p$-Lipschitz定数のパラメータ化複雑性とゾノトープ上の$L_p$-Norm最大化
• Abstract要約: リプシッツはニューラルネットワークを入力するためのネットワークの感度に標準的手法を定めている。 この問題に対してブルートフォースが本質的に最適であることを示す。
• 参考スコア（独自算出の注目度）: 10.97628500062133
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: リプシッツ定数は、ニューラルネットワークの小さな入力摂動に対する感度を定量化する標準的な方法である。 非負の出力重みが凸性を強制する制約アーキテクチャである2層入力凸ニューラルネットワーク(ICNN)について,この問題を考察する。 これらのネットワークに対する$L_p$-Lipschitz定数の計算は、ゾノトープ上の双対ノルムを最大化するのと同値である。 L_1$-と$L_\infty$-normの最大化は、それぞれ固定パラメータと多項式時間アルゴリズムを許容するが、残りの$L_p$-normsのパラメータ化複雑性は開放された。 固定されたすべての$p\in (1,\infty)\cap \mathbb{Q}$に対して、$\mathbb{R}^d$ のゾノトープ上の$L_p$-ノルムを最大化することは、次元 $d$ に関して W[1]-ハードであることを証明する。 さらに, この結果から, 指数時間仮説の下では, ブルートフォース列挙アルゴリズムが本質的に最適であることが示唆された。 双対性により、2層 ReLU ICNN の$L_p$-Lipschitz 定数を計算する上で同じ硬度結果が成立する。 我々の証明はまず$L_2$-normの結果を確立し、適切なテイラー近似を用いて任意の固定された$p\in (1,\infty)\cap\mathbb{Q}$に変換する。 これらの結果は、2層ICNNリプシッツ定数とゾノトープノルム最大化のパラメータ化複雑性状態に関する対応する疑問を解決した。 本稿は COLT'25 に掲載したオープンな問題を解消する。 同じ問題を解く独立した論文がいくつかある。 本論文は、基礎となる数学と、証明の背後にある概念的直観の明確な説明を優先する。 また,LLMの使用を含む研究プロセスについても明確に述べる。

関連論文リスト

• A law of robustness for two-layer neural networks with arbitrary weights [0.0]
  Bubeck、Li、Nagarajは、一般的なデータでは、ノイズラベルに適合する$m$のニューロンを持つ任意の2層ニューラルネットワークは、リプシッツ定数を持つ必要があると推測した。 予想法則を1つの対数係数まで証明し、特にReLUネットワークにおいて連続的な片方向線形活性化を行う。
  論文  参考訳（メタデータ） (2026-07-08T17:44:15Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
  量子ビット効率の最適化を幾何学的問題として再検討する。 局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
  論文  参考訳（メタデータ） (2025-11-11T15:38:57Z)
• Parameterized Hardness of Zonotope Containment and Neural Network Verification [9.076330553662876]
  2層ReLUネットワークで計算された関数 $fcolonmathbbRdtomathbbR$ の正則性は、$d$ でパラメータ化されると W[1]-ハードであることが証明される。 また、2層ReLUネットワークにおける任意の乗算係数内の最大値の近似、2層ネットワークにおける$pin(0,infty)$に対する$L_p$-Lipschitz定数の計算、3層ネットワークにおける$L_p$-Lipschitz定数の近似はNPであることを示す。
  論文  参考訳（メタデータ） (2025-09-26T18:59:59Z)
• Learning Networks from Wide-Sense Stationary Stochastic Processes [7.59499154221528]
  ここでの重要な推論問題は、ノード出力(ポテンシャル)からエッジ接続を学習することである。 我々はWhittleの最大可能性推定器(MLE)を用いて時間相関サンプルから$Last$のサポートを学習する。 MLE問題は厳密な凸であり、ユニークな解であることを示す。
  論文  参考訳（メタデータ） (2024-12-04T23:14:00Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。