論文の概要: Fast Matrix Square Roots with Applications to Gaussian Processes and
Bayesian Optimization
- arxiv url: http://arxiv.org/abs/2006.11267v2
- Date: Mon, 30 Nov 2020 21:52:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 04:07:35.273559
- Title: Fast Matrix Square Roots with Applications to Gaussian Processes and
Bayesian Optimization
- Title（参考訳）: 高速行列平方根とガウス過程とベイズ最適化への応用
- Authors: Geoff Pleiss, Martin Jankowiak, David Eriksson, Anil Damle, Jacob R.
Gardner
- Abstract要約: 行列平方根とその逆は機械学習で頻繁に現れる。
我々は,$mathbf K1/2 mathbf b$,$mathbf K-1/2 mathbf b$とその導関数を行列ベクトル乗算(MVM)により計算するための高効率二次時間アルゴリズムを導入する。
提案手法は,Krylov部分空間法と有理近似,典型的には4ドル10分の精度で100ドル未満のMVMを推定する。
- 参考スコア（独自算出の注目度）: 24.085358075449406
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Matrix square roots and their inverses arise frequently in machine learning,
e.g., when sampling from high-dimensional Gaussians $\mathcal{N}(\mathbf 0,
\mathbf K)$ or whitening a vector $\mathbf b$ against covariance matrix
$\mathbf K$. While existing methods typically require $O(N^3)$ computation, we
introduce a highly-efficient quadratic-time algorithm for computing $\mathbf
K^{1/2} \mathbf b$, $\mathbf K^{-1/2} \mathbf b$, and their derivatives through
matrix-vector multiplication (MVMs). Our method combines Krylov subspace
methods with a rational approximation and typically achieves $4$ decimal places
of accuracy with fewer than $100$ MVMs. Moreover, the backward pass requires
little additional computation. We demonstrate our method's applicability on
matrices as large as $50,\!000 \times 50,\!000$ - well beyond traditional
methods - with little approximation error. Applying this increased scalability
to variational Gaussian processes, Bayesian optimization, and Gibbs sampling
results in more powerful models with higher accuracy.
- Abstract（参考訳）: 行列の平方根とその逆元は機械学習において頻繁に発生する(例えば、高次元ガウス群から$\mathcal{n}(\mathbf 0, \mathbf k)$ または共分散行列 $\mathbf k$ に対してベクトル $\mathbf b$ をホワイトニングする場合など)。
既存の方法は一般に$O(N^3)$計算を必要とするが、$\mathbf K^{1/2} \mathbf b$, $\mathbf K^{-1/2} \mathbf b$とその微分は行列ベクトル乗算(MVM)によって計算される。
本手法は, krylov 部分空間法と有理近似を組み合わせることで, 100 ドルの mvm 未満の精度で 4 桁の十進位置を実現する。
さらに、後方通過は、計算をほとんど必要としない。
50,\! 行列に対する本手法の適用性を示す。
000 \times 50,\!
000$ – 従来の方法をはるかに超える – 近似誤差はほとんどありません。
この拡張性を変分ガウス過程、ベイズ最適化、ギブスサンプリングに適用すると、より高精度なモデルが得られる。
関連論文リスト
- Optimal Quantization for Matrix Multiplication [35.007966885532724]
我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
論文 参考訳（メタデータ） (2024-10-17T17:19:48Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - 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) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Matrix Compression via Randomized Low Rank and Low Precision
Factorization [47.902465710511485]
現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。
この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。
LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
論文 参考訳（メタデータ） (2023-10-17T06:56:57Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Multiplicative updates for symmetric-cone factorizations [0.0]
コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。
SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
論文 参考訳（メタデータ） (2021-08-02T09:23:39Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Interpolating Log-Determinant and Trace of the Powers of Matrix
$\mathbf{A} + t \mathbf{B}$ [1.5002438468152661]
関数 $t mapto log det left( mathbfA + t mathbfB right)$ and $t mapto nametraceleft (mathbfA + t mathbfB)p right)$ ここで行列 $mathbfA$ と $mathbfB$ はエルミート的で正(半)で、$p$ と $t$ は実変数である。
論文 参考訳（メタデータ） (2020-09-15T23:11:17Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳（メタデータ） (2020-08-01T19:23:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。