Fugu-MT 論文翻訳(概要): A Witnessing Duality for ReLU Network Depth

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

arxiv url: http://arxiv.org/abs/2610.38281v1
Date: Wed, 28 Oct 2026 05:04:04 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-31 05:25:12.373633
Title: A Witnessing Duality for ReLU Network Depth
Title（参考訳）: ReLUネットワーク深さのウィットネス化
Abstract要約: ReLU計算ネットワークのディープローバウンド(deep lower bound)は、ある入力に対してより浅いネットワークアースを割り当てる。この既知の境界は$mathVTC0$であり、一様定数深度しきい値の有界パラメータ理論である。最大で$K$の隠蔽層を持つネットワーク、非バイアス重みが$q$、任意の有理バイアス、および$n>qK$の入力を避けると、リフュータはネットワークが乱す長さの合理的な入力を返す。
参考スコア（独自算出の注目度）: 3.114745697185681
License: http://creativecommons.org/licenses/by/4.0/
Abstract: A depth lower bound for ReLU networks asserts that every shallower network errs on some input; we ask when a weak theory can prove such a bound so that an error can be computed. For the exact computation of $\max(x_1,\ldots,x_n)$, recent work shows two hidden layers suffice with unrestricted rational weights. By contrast, Haase, Hertrich and Loho (ICLR 2023) proved that integer weights require depth logarithmic in $n$, and Averkov, Hojny and Merkert (ICLR 2025) extended the bound to nonbias weights whose denominators are powers of a fixed integer not divisible by a prime $q$. With integer weights the bound is sharp: the classical balanced construction has depth $\lceil\log_2 n\rceil$. For each fixed $q$ and depth cap $K$, we prove this known bound in $\mathbf{VTC}^0$, the bounded-arithmetic theory of uniform constant-depth threshold computation, together with a refuter that is itself such a computation and whose correctness the theory proves. Given a network with at most $K$ hidden layers, nonbias weights whose reduced denominators avoid $q$, arbitrary rational biases and $n>q^K$ inputs, the refuter returns a rational input of polynomial length on which the network errs. The proof makes the obstruction finite: an iterated intersection product of piecewise-linear functions is divisible by $q$ for the network but not for the maximum, so one of finitely many test points exposes the error. By witnessing, provable refutation corresponds to a provably correct refuter, and provable existence of a certified network to a provably correct constructor. On the construction side, we introduce certificates that label each maximum gadget by the inputs it aggregates; with them the theory verifies the balanced construction, which meets the refuter at the sharp threshold $n\le2^K$, and a rational family of polynomial description length and depth $O(\log n/\log\log n)$ built from known depth-two blocks.
Abstract（参考訳）: ReLUネットワークのディープローバウンドは、ある入力に対してより浅いネットワークの全てのアーラを主張する; 弱い理論がそのようなバウンドを証明し、エラーを計算できるかどうかを問う。最近の研究は、$\max(x_1,\ldots,x_n)$の正確な計算について、2つの隠れた層が制限されない有理重みで十分であることを示している。対照的に、Haase, Hertrich and Loho (ICLR 2023) は整数重みが$n$の深さ対数を必要とすることを証明し、Averkov, Hojny and Merkert (ICLR 2025) は、分母が素数$q$で割り切れない固定整数のパワーである非バイアス重みに境界を拡張した。古典的平衡構造は深さ$\lceil\log_2 n\rceil$を持つ。固定された$q$ とdeep cap $K$ に対して、この既知の境界が$\mathbf{VTC}^0$ であることを証明する。最大で$K$の隠蔽層を持つネットワーク、非バイアス重みが$q$、任意の有理バイアス、および$n>q^K$の入力を回避している場合、リフュータはネットワークがアースする多項式長の有理入力を返す。この証明は障害を有限にしている: 分割線型関数の反復交叉積は、ネットワークに対して$q$で割り切れるが、最大のためにはならないので、有限個のテストポイントのうちの1つがエラーを露呈する。確認することにより、証明可能な消火は証明可能な正しい消火器に対応し、証明可能な正しいコンストラクタへの認証ネットワークの存在を証明可能なものにする。構築側では,各最大ガジェットを集約した入力によってラベル付けする証明書を導入し,その理論により, 高いしきい値$n\le2^K$, 多項式記述長と深さ$O(\log n/\log \log n)$の合理的なファミリを, 既知の深さ2ブロックから構築した平衡構造を検証した。

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

関連論文リスト