論文の概要: Constant-Depth and Subcubic-Size Threshold Circuits for Matrix
Multiplication
- arxiv url: http://arxiv.org/abs/2006.14652v1
- Date: Thu, 25 Jun 2020 18:28:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 04:06:05.026663
- Title: Constant-Depth and Subcubic-Size Threshold Circuits for Matrix
Multiplication
- Title（参考訳）: 行列乗算のための定数深さ及びサブキュービックサイズ閾値回路
- Authors: Ojas Parekh, Cynthia A. Phillips, Conrad D. James, James B. Aimone
- Abstract要約: 大規模ニューラルネットワークハードウェアの最近の進歩は、その実践的実装を短期的可能性にしている。
しきい値ゲート論理を統合する2つの$N$を$N$行列に乗算する理論的アプローチについて述べる。
デンス行列乗算は畳み込みニューラルネットワークトレーニングにおけるコア演算である。
- 参考スコア（独自算出の注目度）: 1.9518237361775532
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Boolean circuits of McCulloch-Pitts threshold gates are a classic model of
neural computation studied heavily in the late 20th century as a model of
general computation. Recent advances in large-scale neural computing hardware
has made their practical implementation a near-term possibility. We describe a
theoretical approach for multiplying two $N$ by $N$ matrices that integrates
threshold gate logic with conventional fast matrix multiplication algorithms,
that perform $O(N^\omega)$ arithmetic operations for a positive constant
$\omega < 3$. Our approach converts such a fast matrix multiplication algorithm
into a constant-depth threshold circuit with approximately $O(N^\omega)$ gates.
Prior to our work, it was not known whether the $\Theta(N^3)$-gate barrier for
matrix multiplication was surmountable by constant-depth threshold circuits.
Dense matrix multiplication is a core operation in convolutional neural
network training. Performing this work on a neural architecture instead of
off-loading it to a GPU may be an appealing option.
- Abstract（参考訳）: マカロック・ピットのしきい値ゲートのブール回路は、20世紀後半に一般的な計算のモデルとして大きく研究されたニューラルネットワークの古典的なモデルである。
大規模ニューラルコンピューティングハードウェアの最近の進歩は、その実用的実装を近い将来に可能にしている。
閾値ゲート論理を従来の高速行列乗算アルゴリズムと統合し、正の定数$\omega < 3$に対して$O(N^\omega)$算術演算を行う2つの$N$を$N$行列に乗算する理論的アプローチを述べる。
提案手法は,そのような高速行列乗算アルゴリズムを,約$O(N^\omega)$ゲートを持つ定数深度しきい値回路に変換する。
我々の研究に先立ち、行列乗算の$\Theta(N^3)$-gateバリアが定数深さしきい値回路で実装可能かどうかは分かっていなかった。
Dense matrix multiplicationは畳み込みニューラルネットワークトレーニングにおけるコア操作である。
この作業をGPUにオフロードするのではなく、ニューラルネットワークで実行するというのは、魅力的な選択肢かもしれません。
関連論文リスト
- Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers [16.046186753149]
最近のLarge Language Models(LLM)におけるトランスフォーマーの成功の鍵は自己認識メカニズムである
我々は、注目行列の畳み込み様構造を利用して、畳み込み行列を用いた注目の効率的な近似法を開発する。
トランスフォーマーモデルにおけるアテンション計算を加速するための新しいパラダイムが、より長いコンテキストへのアプリケーションを支援することを願っています。
論文 参考訳（メタデータ） (2024-05-08T17:11:38Z) - Quantum Time-Space Tradeoffs for Matrix Problems [0.5524804393257919]
量子コンピュータが行列を含む様々な問題を解くのに必要な時間と空間を考察する。
ほぼ全ての行列$A$に対して、少なくとも$T$の入力クエリと$S$のメモリを持つ量子回路は$T=Omega(n2/S)$を必要とすることを証明している。
我々の下界の多くは時間と空間の複雑さで決定論的アルゴリズムと一致するため、量子コンピュータは任意の空間境界を持つこれらの問題に対していかなる利点も提供できないことを示す。
論文 参考訳（メタデータ） (2024-01-10T18:38:43Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - Block-encoding dense and full-rank kernels using hierarchical matrices:
applications in quantum numerical linear algebra [6.338178373376447]
本稿では,量子コンピュータ上の階層行列構造のブロック符号化方式を提案する。
我々の手法は、次元$N$から$O(kappa operatornamepolylog(fracNvarepsilon))$の量子線型系を解くランタイムを改善することができる。
論文 参考訳（メタデータ） (2022-01-27T05:24:02Z) - Fast Differentiable Matrix Square Root [65.67315418971688]
微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。
前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。
もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
論文 参考訳（メタデータ） (2022-01-21T12:18:06Z) - Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and
Energy [0.0]
しきい値回路$C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $log (rk(M_C)) le ed。
離散化ReLE回路や復号化シグモノイド回路などの他のニューラルネットワークのモデルに対しては、同様の不等式が離散化回路の$C$についても成り立つことを証明している。
論文 参考訳（メタデータ） (2021-07-01T05:37:53Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
我々は,超効率的なサイストリックアレイベースの多用途ハードウェアアクセラレータである textitVersaGNN を提案する。
textitVersaGNNは平均3712$times$ speedup with 1301.25$times$ energy reduction on CPU、35.4$times$ speedup with 17.66$times$ energy reduction on GPUを達成している。
論文 参考訳（メタデータ） (2021-05-04T04:10:48Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - What if Neural Networks had SVDs? [66.91160214071088]
様々なニューラルネットワークでは、行列反転のような時間を要する行列演算を採用している。
本稿では,行列演算を高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-29T12:58:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。