論文の概要: Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and
Energy
- arxiv url: http://arxiv.org/abs/2107.00223v2
- Date: Wed, 28 Jun 2023 03:49:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-29 18:59:40.655486
- Title: Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and
Energy
- Title（参考訳）: サブ線形深さとエネルギーのしきい値回路の指数下限
- Authors: Kei Uchizawa and Haruki Abe
- Abstract要約: しきい値回路$C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $log (rk(M_C)) le ed。
離散化ReLE回路や復号化シグモノイド回路などの他のニューラルネットワークのモデルに対しては、同様の不等式が離散化回路の$C$についても成り立つことを証明している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we investigate computational power of threshold circuits and
other theoretical models of neural networks in terms of the following four
complexity measures: size (the number of gates), depth, weight and energy. Here
the energy complexity of a circuit measures sparsity of their computation, and
is defined as the maximum number of gates outputting non-zero values taken over
all the input assignments. As our main result, we prove that any threshold
circuit $C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $\log
(rk(M_C)) \le ed (\log s + \log w + \log n)$, where $rk(M_C)$ is the rank of
the communication matrix $M_C$ of a $2n$-variable Boolean function that $C$
computes. Thus, such a threshold circuit $C$ is able to compute only a Boolean
function of which communication matrix has rank bounded by a product of
logarithmic factors of $s,w$ and linear factors of $d,e$. This implies an
exponential lower bound on the size of even sublinear-depth threshold circuit
if energy and weight are sufficiently small. For other models of neural
networks such as a discretized ReLE circuits and decretized sigmoid circuits,
we prove that a similar inequality also holds for a discretized circuit $C$:
$rk(M_C) = O(ed(\log s + \log w + \log n)^3)$.
- Abstract（参考訳）: 本稿では,しきい値回路の計算能力とニューラルネットワークの他の理論モデルについて,サイズ(ゲート数)、深さ、重み、エネルギーの4つの複雑性尺度を用いて検討する。
ここで、回路のエネルギー複雑性は計算の空間性を測定し、全ての入力代入に対して非ゼロの値を出力する最大ゲート数として定義される。
主な結果として、任意のしきい値回路$C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $\log (rk(M_C)) \le ed (\log s + \log w + \log n)$, where $rk(M_C)$は通信行列$M_C$の2n$変数ブール関数の階数であることを示す。
したがって、そのようなしきい値回路$C$は、通信行列が階数を持つブール関数のみを$s,w$の対数係数の積と$d,e$の線型因子の積で計算することができる。
これは、エネルギーと重量が十分に小さい場合、偶数直線深度閾値回路のサイズに対する指数的な下界を意味する。
離散レイル回路や離散化sgmoid回路のような他のニューラルネットワークモデルに対しては、同様の不等式が離散化回路に対しても成り立つことが証明される: $rk(m_c) = o(ed(\log s + \log w + \log n)^3)$。
関連論文リスト
- Low-degree approximation of QAC$^0$ circuits [0.0]
パリティ関数はQAC$0$で計算できないことを示す。
また、$n$ビットのパリティをおよそ計算する深さ$d$のQAC回路には、$2widetildeOmega(n1/d)$が必要であることも示している。
論文 参考訳（メタデータ） (2024-11-01T19:04:13Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - On the Computational Power of QAC0 with Barely Superlinear Ancillae [10.737102385599169]
深さ$$d$$mathrmQAC0$回路は、近似次数$ta(n)$の関数を計算するために$n1+3-d$アンシラを必要とする。
これは超線形サイズの$mathrmQAC0$上の最初の超線形下界である。
論文 参考訳（メタデータ） (2024-10-09T02:55:57Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。
このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
論文 参考訳（メタデータ） (2021-10-07T05:25:23Z) - Bounds on the QAC$^0$ Complexity of Approximating Parity [0.0]
その結果,QAC回路はサイズに関係なくパリティを近似できることがわかった。
QAC回路は1/2 + exp(-o(n/d))$ perroximation of parityを達成するために少なくとも$Omega(n/d)$ multi-qubit gateを必要とする。
論文 参考訳（メタデータ） (2020-08-17T16:51:04Z) - Constant-Depth and Subcubic-Size Threshold Circuits for Matrix
Multiplication [1.9518237361775532]
大規模ニューラルネットワークハードウェアの最近の進歩は、その実践的実装を短期的可能性にしている。
しきい値ゲート論理を統合する2つの$N$を$N$行列に乗算する理論的アプローチについて述べる。
デンス行列乗算は畳み込みニューラルネットワークトレーニングにおけるコア演算である。
論文 参考訳（メタデータ） (2020-06-25T18:28:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。