論文の概要: Optimal Quantization for Matrix Multiplication

• arxiv url: http://arxiv.org/abs/2410.13780v1
• Date: Thu, 17 Oct 2024 17:19:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-18 13:22:22.113894
• Title: Optimal Quantization for Matrix Multiplication
• Title（参考訳）: 行列乗算のための最適量子化
• Authors: Or Ordentlich, Yury Polyanskiy,
• Abstract要約: 我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
• 参考スコア（独自算出の注目度）: 35.007966885532724
• License:
• Abstract: Recent work in machine learning community proposed multiple methods for performing lossy compression (quantization) of large matrices. This quantization is important for accelerating matrix multiplication (main component of large language models), which is often bottlenecked by the speed of loading these matrices from memory. Unlike classical vector quantization and rate-distortion theory, the goal of these new compression algorithms is to be able to approximate not the matrices themselves, but their matrix product. Specifically, given a pair of real matrices $A,B$ an encoder (compressor) is applied to each of them independently producing descriptions with $R$ bits per entry. These representations subsequently are used by the decoder to estimate matrix product $A^\top B$. In this work, we provide a non-asymptotic lower bound on the mean squared error of this approximation (as a function of rate $R$) for the case of matrices $A,B$ with iid Gaussian entries. Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error for any (non-random) pair of matrices $A$, $B$ in terms of only Frobenius norms $\|A\|_F, \|B\|_F$ and $\|A^\top B\|_F$. For iid Gaussian matrices our quantizer achieves the lower bound and is, thus, asymptotically optimal. A practical low-complexity version of our quantizer achieves performance quite close to optimal. In information-theoretic terms we derive rate-distortion function for matrix multiplication of iid Gaussian matrices.
• Abstract（参考訳）: 機械学習コミュニティにおける最近の研究は、大きな行列の損失圧縮(量子化)を実行する複数の方法を提案した。 この量子化は行列乗法(大規模言語モデルの主成分)の高速化に重要である。 古典的ベクトル量子化や速度歪み理論とは異なり、これらの新しい圧縮アルゴリズムの目標は行列自身ではなく行列積を近似できることである。 具体的には、1組の実行列が$A,B$のエンコーダ(圧縮機)を与えられたとき、それぞれがそれぞれ独立して1エントリあたり$R$ビットの記述を生成する。 これらの表現はデコーダによって行列積 $A^\top B$ を推定するために使われる。 本研究では、この近似の平均二乗誤差の漸近的でない下界を、イド・ガウス成分を持つ行列 $A,B$ に対して(レート $R$ の関数として)与える。 アルゴリズムにより、任意の(非ランダムな)行列対に対する近似誤差を明示的に保証したネスト格子に基づく普遍的量子化器を、フロベニウスノルム$\|A\|_F, \|B\|_F$, $\|A^\top B\|_F$のみの観点から構成する。 iidガウス行列に対して、我々の量子化器は下界を達成し、したがって漸近的に最適である。 我々の量子化器の実用的低複雑さバージョンは、非常に最適に近い性能を達成する。 情報理論の観点からは、イド・ガウス行列の行列乗法に対する速度歪み関数を導出する。

関連論文リスト

• Quantum Time-Space Tradeoffs for Matrix Problems [0.5524804393257919]
  量子コンピュータが行列を含む様々な問題を解くのに必要な時間と空間を考察する。 ほぼ全ての行列$A$に対して、少なくとも$T$の入力クエリと$S$のメモリを持つ量子回路は$T=Omega(n2/S)$を必要とすることを証明している。 我々の下界の多くは時間と空間の複雑さで決定論的アルゴリズムと一致するため、量子コンピュータは任意の空間境界を持つこれらの問題に対していかなる利点も提供できないことを示す。
  論文  参考訳（メタデータ） (2024-01-10T18:38:43Z)
• Multiresolution kernel matrix algebra [0.0]
  本研究では, あるS形式において, 最適スパース行列を生成するサンプルレットを用いて, カーネル行列の圧縮を示す。 カーネル行列の逆数(もし存在するなら)は S-形式でも圧縮可能である。 行列代数は擬微分計算によって数学的に正当化される。
  論文  参考訳（メタデータ） (2022-11-21T17:50:22Z)
• 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)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。 我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
  論文  参考訳（メタデータ） (2021-08-08T05:28:06Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T03:07:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。