論文の概要: Why ReLU? A Bit-Model Dichotomy for Deep Network Training

• arxiv url: http://arxiv.org/abs/2602.19017v1
• Date: Sun, 22 Feb 2026 03:12:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-24 17:42:02.443977
• Title: Why ReLU? A Bit-Model Dichotomy for Deep Network Training
• Title（参考訳）: なぜReLUは深層ネットワークトレーニングのためのビットモデル二分法
• Authors: Ilan Doron-Arad, Elchanan Mossel,
• Abstract要約: 有限精度制約は単に実装の詳細ではなく、学習可能性の基本的な決定要因であることを示す。 本結果は,有限精度制約は単に実装の詳細ではなく,学習可能性の基本的な決定要因であることを示す。
• 参考スコア（独自算出の注目度）: 13.35672617666336
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Theoretical analyses of Empirical Risk Minimization (ERM) are standardly framed within the Real-RAM model of computation. In this setting, training even simple neural networks is known to be $\exists \mathbb{R}$-complete -- a complexity class believed to be harder than NP, that characterizes the difficulty of solving systems of polynomial inequalities over the real numbers. However, this algebraic framework diverges from the reality of digital computation with finite-precision hardware. In this work, we analyze the theoretical complexity of ERM under a realistic bit-level model ($\mathsf{ERM}_{\text{bit}}$), where network parameters and inputs are constrained to be rational numbers with polynomially bounded bit-lengths. Under this model, we reveal a sharp dichotomy in tractability governed by the network's activation function. We prove that for deep networks with {\em any} polynomial activations with rational coefficients and degree at least $2$, the bit-complexity of training is severe: deciding $\mathsf{ERM}_{\text{bit}}$ is $\#P$-Hard, hence believed to be strictly harder than NP-complete problems. Furthermore, we show that determining the sign of a single partial derivative of the empirical loss function is intractable (unlikely in BPP), and deciding a specific bit in the gradient is $\#P$-Hard. This provides a complexity-theoretic perspective for the phenomenon of exploding and vanishing gradients. In contrast, we show that for piecewise-linear activations such as ReLU, the precision requirements remain manageable: $\mathsf{ERM}_{\text{bit}}$ is contained within NP (specifically NP-complete), and standard backpropagation runs in polynomial time. Our results demonstrate that finite-precision constraints are not merely implementation details but fundamental determinants of learnability.
• Abstract（参考訳）: 経験的リスク最小化(ERM)の理論分析は、計算のReal-RAMモデルの中で標準化されている。 この設定では、単純なニューラルネットワークのトレーニングは$\exists \mathbb{R}$-complete(NPよりも難しいと信じられている複雑性クラス)として知られている。 しかし、この代数的フレームワークは、有限精度ハードウェアによるデジタル計算の現実から分岐している。 本研究では,実効的なビットレベルモデル(\mathsf{ERM}_{\text{bit}}$)の下でERMの理論的複雑性を分析する。 本モデルでは,ネットワークのアクティベーション機能によって制御されるトラクタビリティの急激な二分法を明らかにする。 有理係数と次数2$以上の多項式活性化を持つディープネットワークの場合、トレーニングのビット複雑度は厳しい:$\mathsf{ERM}_{\text{bit}}$は$\#P$-Hardであり、したがってNP完全問題よりも厳密である。 さらに、経験的損失関数の1つの部分微分の符号を決定することは、(BPPではそうではない)難解であり、勾配の特定のビットを決定することは、$\#P$-Hardであることを示す。 これは、爆発的な勾配と消滅する現象に対する複雑性理論的な視点を与える。 対照的に、ReLUのような片方向の線形アクティベーションに対しては、精度要件は引き続き管理可能である: $\mathsf{ERM}_{\text{bit}}$はNP(特にNP完全)に含まれ、標準バックプロパゲーションは多項式時間で実行される。 本結果は,有限精度制約は単に実装の詳細ではなく,学習可能性の基本的な決定要因であることを示す。

関連論文リスト

• Expressive Power of Deep Networks on Manifolds: Simultaneous Approximation [2.815765641180636]
  境界重みを持つ定数深度$mathrmReLUk-1$ネットワークは、ソボレフ空間内の任意の関数を近似することができることを示す。 また、必要なパラメータ数が対数係数に一致することを示すことで、我々の構成がほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2025-09-11T11:28:20Z)
• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  連続状態と行動空間を持つ非線形力学系の一般設定におけるオンライン強化学習のサンプル複雑性について検討した。 我々のアルゴリズムは、$mathcalO(N epsilon2 + Mathrmln(m(epsilon)/epsilon2)$のポリシーを後悔する。 力学がコンパクトで実数値のパラメータ集合によってパラメータ化される特別な場合、$mathcalO(sqrt)のポリシー後悔を証明する。
  論文  参考訳（メタデータ） (2025-01-27T10:01:28Z)
• Neural Networks and (Virtual) Extended Formulations [8.185918509343818]
  私たちは、$P$を最適化するニューラルネットワークのサイズに対して、より低い境界を証明します。 我々は、$mathrmxc(P)$が任意のモノトーンや入力ニューラルネットワークのサイズの低い境界であることを示し、$P$を超える線形最適化問題を解く。
  論文  参考訳（メタデータ） (2024-11-05T11:12:11Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• 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)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)

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

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