論文の概要: A Witnessing Duality for ReLU Network Depth

• arxiv url: http://arxiv.org/abs/2610.38281v2
• Date: Mon, 02 Nov 2026 14:08:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-04 02:41:45.001972
• Title: A Witnessing Duality for ReLU Network Depth
• Title（参考訳）: ReLUネットワーク深さのウィットネス化
• Abstract要約: ReLUネットワークのディープ・ローバウンドは、入力で十分浅いネットワークが全て失敗すると断言する。 本研究では,最大入力数$nの正確な計算を行うために,隠蔽層数によって深さを計測する。 独立に固定された素数$qと深さ有界な$Kに対して、少なくとも$K$の隠蔽層を持つ有理ネットワークに対して一様の$mathsfTC0Refuterを与える。
• 参考スコア（独自算出の注目度）: 3.114745697185681
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A depth lower bound for ReLU networks asserts that every sufficiently shallow network fails on some input. What does a proof of such a bound compute? We study this question for exact computation of the maximum of $n$ real inputs, with depth measured by the number of hidden layers. For every separately fixed prime $q$ and depth bound $K$, we give a uniform $\mathsf{TC}^0$ refuter for rational networks with at most $K$ hidden layers and more than $q^K$ inputs, provided that the reduced denominators of their nonbias weights are not divisible by $q$. Biases may be arbitrary rationals. The refuter finds a rational input on which the network fails, and its correctness is provable in $\mathbf{VTC}^0$, the bounded-arithmetic theory of uniform constant-depth threshold computation. The underlying numerical depth lower bound follows from Averkov, Hojny and Merkert (ICLR 2025), extending Haase, Hertrich and Loho (ICLR 2023); our contribution is an internal proof that makes its geometric argument into a feasible refuter. On the construction side, $\mathbf{VTC}^0$ verifies locally checkable certificates for the balanced integer-weight maximum network of depth $\lceil\log_2 n\rceil$. At $q=2$, the construction and refuter meet: for each fixed $K$, the theory verifies that integer-nonbias-weight networks with arbitrary rational biases can compute the maximum with at most $K$ hidden layers exactly when $n\le 2^K$. We also give certified rational constructions of polynomial encoding length and depth $O(\log n/\log\log n)$. These results instantiate a witnessing duality: bounded proofs of certified existence and of refutation correspond, respectively, to threshold-computable constructors and refuters whose guarantees the theory proves.
• Abstract（参考訳）: ReLUネットワークのディープ・ローバウンドは、十分に浅いネットワークは入力でフェールすると断言する。 そのような有界な計算の証明は何か? そこで本研究では,隠蔽層数を用いて,最大$n$実数入力の正確な計算について検討する。 独立に固定されたすべての素数$q$と深度$K$に対して、最大で$K$の層と$q^K$以上の入力を持つ有理ネットワークに対して、均一な$\mathsf{TC}^0$のRefuterを与える。 バイアスは任意の有理数である。 共振器は、ネットワークが失敗する有理的な入力を見つけ、その正確性は、一様定数深度しきい値計算の有界パラメータ理論である $\mathbf{VTC}^0$ で証明可能である。 基礎となる数値深度下界は、Averkov, Hojny and Merkert (ICLR 2025) から続き、Haase, Hertrich and Loho (ICLR 2023) を拡張する。 構築側では、$\mathbf{VTC}^0$は深さ$\lceil\log_2 n\rceil$のバランスの取れた整数重み付き最大ネットワークのローカルチェック可能な証明書を検証する。 この理論は、各固定された$K$に対して、任意の有理バイアスを持つ整数非バイアス重み付きネットワークが、$n\le 2^K$のとき、少なくとも$K$の隠蔽層で最大値を計算することができることを証明している。 また、多項式符号化長と深さ$O(\log n/\log n)$の証明された有理構成を与える。 これらの結果は、証明された存在の有界証明と、その理論を保証するしきい値計算可能なコンストラクタとRefuterに対応している。

関連論文リスト

• Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon [0.0]
  我々は,帯域幅フィードバックを用いて,実現可能な多クラスPAC学習について検討する。 我々は、新しいアンカー次元$mathrmaBDSlemathrmBDS$に関する下界理論を修復する。
  論文  参考訳（メタデータ） (2026-08-31T05:23:35Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory [3.0120086446979877]
  本稿では,ReLUニューラルネットワークを用いた実入力に対して$d$以上の最大関数の正確な計算問題を考察する。 十分に狭いネットワークでは、最大値の非線形性を捕捉できないことを示す。 このことは、その単純性にもかかわらず、最大函数は固有の複雑さを持っていることを示唆している。
  論文  参考訳（メタデータ） (2026-01-04T07:40:42Z)
• Better Neural Network Expressivity: Subdividing the Simplex [6.311952568615851]
  我々は、$lceillog_3(n-1)rceil+1$ hidden layerは、$mathbbRn$上の全てのCPWL関数を計算するのに十分であることを示す。 この証明の重要なステップは、2つの隠れた層を持つReLUニューラルネットワークが5つの入力の最大関数を正確に表現できることである。
  論文  参考訳（メタデータ） (2025-05-20T13:23:57Z)
• Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete [4.170994234169557]
  InpiricalRiskmization(英語版)として知られる、与えられたデータポイントのセットに可能な限り適合する2層完全連結ニューラルネットワークの重みとバイアスを求める問題を考察する。 任意のデータポイントが有理である場合でも、いくつかのインスタンスを最適に訓練できるウェイトとして、任意の大きな次数の代数数が必要であることを証明します。 この結果、Basu, Mianjy, Mukherjee [ICLR 2018]のような検索アルゴリズムは、$mathsfNP=existsでない限り、複数の出力次元を持つネットワークでは不可能である。
  論文  参考訳（メタデータ） (2022-04-04T10:28:11Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
  本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。 我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
  論文  参考訳（メタデータ） (2021-01-18T15:40:27Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)

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

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