論文の概要: NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks
- arxiv url: http://arxiv.org/abs/2610.11313v1
- Date: Thu, 08 Oct 2026 06:19:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-10 02:36:53.829437
- Title: NP-Hardness of Minimizing Neurons in Two-Hidden-Layer ReLU Neural Networks
- Title（参考訳）: 2Hdden-Layer ReLU ニューラルネットワークにおける最小化ニューロンのNP-Hardness
- Abstract要約: ニューラルネットワークアーキテクチャの最適化における基本的な問題は、ターゲット関数を近似するために必要な最小の隠れカウントを効率的に計算できるかどうかである。
本稿では、この問題を$Lp(mathbbRd,mathbbRm)$近似制約の下で2層ReLUネットワークに対して解決する。
すべての固定された$d ge 1$, $m ge 1$, $1 le p in$に対して、最適計算がNPハードであることを証明する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A fundamental question in neural network architecture optimization is whether the minimum hidden-neuron count required to approximate a target function within a prescribed tolerance can be computed efficiently. This paper resolves this question for two-hidden-layer ReLU networks under an $L^p(\mathbb{R}^d,\mathbb{R}^m)$ approximation constraint. For every fixed $d \ge 1$, $m \ge 1$, and $1 \le p < \infty$, we prove that computing the optimum exactly is NP-hard. The result holds even when the target is represented by a rational ReLU network whose realization is nonzero, componentwise nonnegative, compactly supported, globally Lipschitz, and continuous piecewise affine. The polynomial-time reduction from 3-SAT produces an architecture gap in which unsatisfiable formulas yield an optimum of zero, whereas satisfiable formulas yield an optimum of at least $d+2$. The proof constructs compactly supported polyhedral frustum functions realized by two-hidden-layer ReLU networks and establishes the $L^p$-density of finite linear combinations of box-frustum functions. The results offer theoretical justification for employing heuristic approximation methods in the design of ReLU neural networks, illustrating that attaining a minimal configuration within polynomial time is computationally unachievable.
- Abstract（参考訳）: ニューラルネットワークアーキテクチャ最適化における基本的な問題は、所定の許容範囲内でターゲット関数を近似するのに必要となる最小の隠れニューロンカウントを効率的に計算できるかどうかである。
本稿では、この問題を$L^p(\mathbb{R}^d,\mathbb{R}^m)$近似制約の下で2層ReLUネットワークに対して解決する。
すべての固定された$d \ge 1$, $m \ge 1$, $1 \le p < \infty$に対して、最適化を正確に計算することはNPハードであることを証明する。
その結果は、対象が非零、成分的に非負、コンパクトに支持された、グローバルなリプシッツ、連続的な断片的アフィンである有理ReLUネットワークで表されるときでも成り立つ。
3-SAT からの多項式時間短縮は、満足できない公式が 0 の最適値を得るのに対して、満足できる公式が少なくとも$d+2$の最適値を得るアーキテクチャギャップを生み出す。
この証明は、2層ReLUネットワークによって実現されたコンパクトに支持された多面体フラストム関数を構築し、ボックス・フラストム関数の有限線型結合の$L^p$-densityを確立する。
この結果は、ReLUニューラルネットワークの設計にヒューリスティック近似法を用いる理論的正当性を提供し、多項式時間内に最小構成に達することは、計算不可能であることを示した。
関連論文リスト
- Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks [0.6153038651687485]
実場のo-極小展開において、決定集合が定義可能な集合によって与えられる二項分類問題について検討する。
定義可能な集合の細胞分解を動機として、定義可能な決定領域の古典的プロキシとしてトレーサブル集合を導入し、ReLUニューラルネットワークによる近似を解析する。
論文 参考訳（メタデータ） (2026-06-29T20:44:20Z) - A Quantifier-Reversal Approximation Paradigm for Recurrent Neural Networks [1.096028999747108]
本稿では,量子化器の順序を逆転する近似パラダイムを基本的に導入する。
各ターゲット関数$f$に対して、固定トポロジと固定重みを持つ単一リカレントニューラルネットワーク(RNN)を構築する。
我々のRNN構造は、基盤となる深いフィードフォワードReLUネットワーク近似理論をエミュレートする。
論文 参考訳（メタデータ） (2025-11-19T10:43:48Z) - 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) - Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。
O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
論文 参考訳（メタデータ） (2025-06-03T06:31:59Z) - New advances in universal approximation with neural networks of minimal width [4.424170214926035]
リークReLUアクティベーションを持つオートエンコーダは$Lp$関数の普遍近似器であることを示す。
我々は,滑らかな可逆ニューラルネットワークが$Lp(mathbbRd,mathbbRd)$をコンパクト化できることを示す。
論文 参考訳（メタデータ） (2024-11-13T16:17:16Z) - 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) - Robust Training and Verification of Implicit Neural Networks: A
Non-Euclidean Contractive Approach [64.23331120621118]
本稿では,暗黙的ニューラルネットワークのトレーニングとロバスト性検証のための理論的および計算的枠組みを提案する。
組込みネットワークを導入し、組込みネットワークを用いて、元のネットワークの到達可能な集合の超近似として$ell_infty$-normボックスを提供することを示す。
MNISTデータセット上で暗黙的なニューラルネットワークをトレーニングするためにアルゴリズムを適用し、我々のモデルの堅牢性と、文献における既存のアプローチを通じてトレーニングされたモデルを比較する。
論文 参考訳（メタデータ） (2022-08-08T03:13:24Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。