論文の概要: A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory

• arxiv url: http://arxiv.org/abs/2601.01417v1
• Date: Sun, 04 Jan 2026 07:40:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:22.337667
• Title: A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory
• Title（参考訳）: 極グラフ理論によるReLUネットワークにおける最大計算の深さ階層化
• Authors: Itay Safran,
• Abstract要約: 本稿では,ReLUニューラルネットワークを用いた実入力に対して$d$以上の最大関数の正確な計算問題を考察する。 十分に狭いネットワークでは、最大値の非線形性を捕捉できないことを示す。 このことは、その単純性にもかかわらず、最大函数は固有の複雑さを持っていることを示唆している。
• 参考スコア（独自算出の注目度）: 3.0120086446979877
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of exact computation of the maximum function over $d$ real inputs using ReLU neural networks. We prove a depth hierarchy, wherein width $Ω\big(d^{1+\frac{1}{2^{k-2}-1}}\big)$ is necessary to represent the maximum for any depth $3\le k\le \log_2(\log_2(d))$. This is the first unconditional super-linear lower bound for this fundamental operator at depths $k\ge3$, and it holds even if the depth scales with $d$. Our proof technique is based on a combinatorial argument and associates the non-differentiable ridges of the maximum with cliques in a graph induced by the first hidden layer of the computing network, utilizing Turán's theorem from extremal graph theory to show that a sufficiently narrow network cannot capture the non-linearities of the maximum. This suggests that despite its simple nature, the maximum function possesses an inherent complexity that stems from the geometric structure of its non-differentiable hyperplanes, and provides a novel approach for proving lower bounds for deep neural networks.
• Abstract（参考訳）: 本稿では,ReLUニューラルネットワークを用いた実入力に対して$d$以上の最大関数の正確な計算問題を考察する。 深さ階層を証明し、幅$Ω\big(d^{1+\frac{1}{2^{k-2}-1}}\big)$は深さ$3\le k\le \log_2(\log_2(d))$の最大値を表すために必要である。 これは、この基本作用素の深さ$k\ge3$における最初の非条件超線型下界であり、深さが$d$でスケールしても成り立つ。 我々の証明手法は組合せ論に基づいており、計算ネットワークの第1の隠れ層によって誘導されるグラフにおいて、最大の微分不可能な隆起を、極小グラフ理論からチューランの定理を利用して、最大の非線形性を十分に狭いネットワークで捉えることができないことを示す。 これは、その単純な性質にもかかわらず、最大関数は、その非微分不可能な超平面の幾何学構造に由来する固有の複雑さを持ち、ディープニューラルネットワークの下位境界を証明する新しいアプローチを提供することを示唆している。

関連論文リスト

• Minimum Width of Deep Narrow Networks for Universal Approximation [9.00733527455972]
  完全連結ニューラルネットワークに必要な最小幅の下限と上限について検討する。 より直感的な例を構築して、不等式 $w_minge d_y+mathbf1_d_xd_yleq2d_x$ の新たな証明を示す。
  論文  参考訳（メタデータ） (2025-11-10T08:29:14Z)
• Depth-Bounds for Neural Networks via the Braid Arrangement [7.856998585396422]
  我々は、$d$数値の最大値を表すのに必要な$Omega(loglog d)$ hidden layerの非定数な下界を証明する。 ランク3の最大化層とランク2の最大化層が続くと、最大7個の数を表すのに十分であることを示す。
  論文  参考訳（メタデータ） (2025-02-13T13:37:52Z)
• Bayesian Inference with Deep Weakly Nonlinear Networks [57.95116787699412]
  我々は,完全連結ニューラルネットワークによるベイズ推定が解けることを示す物理レベルの厳密さを示す。 我々はモデルエビデンスを計算し、任意の温度で1/N$で任意の順序に後続する手法を提供する。
  論文  参考訳（メタデータ） (2024-05-26T17:08:04Z)
• How Many Neurons Does it Take to Approximate the Maximum? [10.995895410470279]
  我々は、$d$入力以上の最大関数を近似するために必要なニューラルネットワークのサイズについて検討する。 様々な深さにまたがる近似に必要な幅について, 新たな下限と上限を提供する。
  論文  参考訳（メタデータ） (2023-07-18T12:47:35Z)
• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  まず、3層ニューラルネットワークがコンパクトな集合上のインジケータ関数を近似するように設計可能であることを示す。 その後、これは単純複体へと拡張され、その位相構造に基づいて幅の上界が導かれる。 トポロジカルアプローチを用いて3層ReLUネットワークの普遍近似特性を証明した。
  論文  参考訳（メタデータ） (2023-05-25T14:17:15Z)
• Understanding Deep Neural Function Approximation in Reinforcement Learning via $\epsilon$-Greedy Exploration [53.90873926758026]
  本稿では、強化学習(RL)における深部神経機能近似の理論的研究について述べる。 我々は、Besov(およびBarron)関数空間によって与えられるディープ(および2層)ニューラルネットワークによる$epsilon$-greedy探索により、バリューベースのアルゴリズムに焦点を当てる。 我々の解析は、ある平均測度$mu$の上の$L2(mathrmdmu)$-integrable空間における時間差誤差を再構成し、非イド設定の下で一般化問題に変換する。
  論文  参考訳（メタデータ） (2022-09-15T15:42:47Z)
• Size and Depth Separation in Approximating Natural Functions with Neural Networks [52.73592689730044]
  本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。 我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。 また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
  論文  参考訳（メタデータ） (2021-01-30T21:30:11Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。 我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
  論文  参考訳（メタデータ） (2021-01-18T15:40:27Z)

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

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