論文の概要: Parameterized Hardness of Zonotope Containment and Neural Network Verification
- arxiv url: http://arxiv.org/abs/2509.22849v1
- Date: Fri, 26 Sep 2025 18:59:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-30 22:32:18.908157
- Title: Parameterized Hardness of Zonotope Containment and Neural Network Verification
- Title（参考訳）: ゾノトープ含有量のパラメータ化硬さとニューラルネットワークによる検証
- Authors: Vincent Froese, Moritz Grillo, Christoph Hertrich, Moritz Stargalla,
- Abstract要約: 2層ReLUネットワークで計算された関数 $fcolonmathbbRdtomathbbR$ の正則性は、$d$ でパラメータ化されると W[1]-ハードであることが証明される。
また、2層ReLUネットワークにおける任意の乗算係数内の最大値の近似、2層ネットワークにおける$pin(0,infty)$に対する$L_p$-Lipschitz定数の計算、3層ネットワークにおける$L_p$-Lipschitz定数の近似はNPであることを示す。
- 参考スコア（独自算出の注目度）: 9.076330553662876
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Neural networks with ReLU activations are a widely used model in machine learning. It is thus important to have a profound understanding of the properties of the functions computed by such networks. Recently, there has been increasing interest in the (parameterized) computational complexity of determining these properties. In this work, we close several gaps and resolve an open problem posted by Froese et al. [COLT '25] regarding the parameterized complexity of various problems related to network verification. In particular, we prove that deciding positivity (and thus surjectivity) of a function $f\colon\mathbb{R}^d\to\mathbb{R}$ computed by a 2-layer ReLU network is W[1]-hard when parameterized by $d$. This result also implies that zonotope (non-)containment is W[1]-hard with respect to $d$, a problem that is of independent interest in computational geometry, control theory, and robotics. Moreover, we show that approximating the maximum within any multiplicative factor in 2-layer ReLU networks, computing the $L_p$-Lipschitz constant for $p\in(0,\infty]$ in 2-layer networks, and approximating the $L_p$-Lipschitz constant in 3-layer networks are NP-hard and W[1]-hard with respect to $d$. Notably, our hardness results are the strongest known so far and imply that the naive enumeration-based methods for solving these fundamental problems are all essentially optimal under the Exponential Time Hypothesis.
- Abstract（参考訳）: ReLUアクティベーションを備えたニューラルネットワークは、機械学習において広く使われているモデルである。
したがって、そのようなネットワークによって計算される関数の性質を深く理解することが重要である。
近年、これらの性質を決定するための(パラメータ化された)計算複雑性への関心が高まっている。
本研究では,ネットワーク検証に関連する諸問題のパラメータ化複雑性について,Froese et al [COLT '25] が投稿したオープンな問題を,いくつかのギャップを埋め,解決する。
特に、2層ReLUネットワークで計算された函数 $f\colon\mathbb{R}^d\to\mathbb{R}$ の正則性(したがって全射性)は、$d$ でパラメータ化されると W[1]-ハードであることが証明される。
この結果は、計算幾何学、制御理論、ロボット工学に独立した関心を持つ問題である$d$に関して、ゾノトペ(非)はW[1]ハードであることを意味する。
さらに,2層ReLUネットワークにおける乗算係数の最大値の近似,2層ネットワークにおける$L_p$-Lipschitz定数の計算,および3層ネットワークにおける$L_p$-Lipschitz定数の近似は,$d$に対してNP-hardおよびW[1]-hardであることを示す。
特に、我々の硬度結果はこれまでに知られている中で最強であり、これらの基本的な問題を解決するための単純列挙に基づく方法が、指数時間仮説の下で本質的に最適であることを示唆している。
関連論文リスト
- Complexity of Injectivity and Verification of ReLU Neural Networks [5.482420806459269]
ReLUネットワークによって計算される関数のインジェクティビティは、関数の可逆性が要求されるたびに重要な役割を果たす。
インジェクティビティを決定する正確な計算複雑性のcoNP完全性を証明する。
また,特定の入力が特定の出力しか得られないことを検証するネットワーク検証問題についても検討する。
論文 参考訳（メタデータ） (2024-05-30T08:14:34Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-18T04:41:07Z) - The Onset of Variance-Limited Behavior for Networks in the Lazy and Rich
Regimes [75.59720049837459]
無限幅挙動からこの分散制限状態への遷移をサンプルサイズ$P$とネットワーク幅$N$の関数として検討する。
有限サイズ効果は、ReLUネットワークによる回帰のために、$P* sim sqrtN$の順序で非常に小さなデータセットに関係があることが分かる。
論文 参考訳（メタデータ） (2022-12-23T04:48:04Z) - Neural Network Approximation of Continuous Functions in High Dimensions
with Applications to Inverse Problems [6.84380898679299]
現在の理論では、ネットワークは問題の次元で指数関数的にスケールすべきだと予測されている。
ニューラルネットワークがH"より古い(あるいは一様)連続関数を近似するのに要する複雑性を境界付ける一般的な方法を提案する。
論文 参考訳（メタデータ） (2022-08-28T22:44:07Z) - Correlation Functions in Random Fully Connected Neural Networks at
Finite Width [17.51364577113718]
この記事では、ガウスのランダムな重みとバイアスと$L$の隠蔽層を持つ完全に接続されたニューラルネットワークについて考察する。
有界非線形性に対しては、ネットワーク出力とその導関数の共役相関関数に対して1/n$の急激な再帰推定を与える。
いずれの場合も、深さと幅の比$L/n$は、個々のニューロンのゆらぎのスケールとニューロン間相関の大きさの両方を制御し、有効なネットワーク深さの役割を担っている。
論文 参考訳（メタデータ） (2022-04-03T11:57:18Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - Theory of Deep Convolutional Neural Networks III: Approximating Radial
Functions [7.943024117353317]
我々は、2つの畳み込み層、ダウン演算子、完全に接続された層からなるディープニューラルネットワークのファミリーを考える。
ネットワーク構造は、畳み込み層の数と完全に連結された層の幅を決定する2つの構造パラメータに依存する。
論文 参考訳（メタデータ） (2021-07-02T08:22:12Z) - Deep neural network approximation of analytic functions [91.3755431537592]
ニューラルネットワークの空間に エントロピーバウンド 片方向の線形活性化関数を持つ
我々は、ペナル化深部ニューラルネットワーク推定器の予測誤差に対するオラクルの不等式を導出する。
論文 参考訳（メタデータ） (2021-04-05T18:02:04Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。