論文の概要: 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)$。
関連論文リスト
- Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
制御された演算は量子アルゴリズムの基本的な構成要素である。
n$-control-NOT ゲートを任意の単一量子ビットと CNOT ゲートに分解することは重要な作業である。
論文 参考訳(メタデータ) (2023-12-20T17:23:11Z) - On the Pauli Spectrum of QAC0 [2.5602836891933074]
我々は、$mathsfQAC0$のパウリスペクトルが低度濃度を満たすと推測する。
我々はこの予想を、少なくとも$nO(1/d)$補助量子ビットを持つ深さ-d$,-size $mathsfQAC0$回路のクラスで証明する。
我々は新しい回路の低境界と学習結果を応用として得る。
論文 参考訳(メタデータ) (2023-11-16T07:25:06Z) - Classical simulation of peaked shallow quantum circuits [2.6089354079273512]
準ポリノミカルランタイム$nO(logn)$のアルゴリズムについて述べる。
我々のアルゴリズムは、浅い回路の出力確率を、与えられた逆多項式加法誤差の範囲内で推定することができる。
論文 参考訳(メタデータ) (2023-09-15T14:01:13Z) - 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) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳(メタデータ) (2022-04-22T12:37:56Z) - 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) - Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation [99.59319332864129]
最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
論文 参考訳(メタデータ) (2020-11-23T17:25:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。