論文の概要: Matrix Product Sketching via Coordinated Sampling

• arxiv url: http://arxiv.org/abs/2501.17836v1
• Date: Wed, 29 Jan 2025 18:35:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-30 15:52:51.410337
• Title: Matrix Product Sketching via Coordinated Sampling
• Title（参考訳）: 配向サンプリングによるマトリックス製品スケッチ
• Authors: Majid Daliri, Juliana Freire, Danrong Li, Christopher Musco,
• Abstract要約: 我々は、小さな空間スケッチに基づいて行列積 $mathbfATmathbfB$ を近似するというよく研究された問題を再考する。 我々は, $mathbfA$ と $mathbfB$ がスパースであることを証明する。
• 参考スコア（独自算出の注目度）: 15.820518033589705
• License:
• Abstract: We revisit the well-studied problem of approximating a matrix product, $\mathbf{A}^T\mathbf{B}$, based on small space sketches $\mathcal{S}(\mathbf{A})$ and $\mathcal{S}(\mathbf{B})$ of $\mathbf{A} \in \R^{n \times d}$ and $\mathbf{B}\in \R^{n \times m}$. We are interested in the setting where the sketches must be computed independently of each other, except for the use of a shared random seed. We prove that, when $\mathbf{A}$ and $\mathbf{B}$ are sparse, methods based on \emph{coordinated random sampling} can outperform classical linear sketching approaches, like Johnson-Lindenstrauss Projection or CountSketch. For example, to obtain Frobenius norm error $\epsilon\|\mathbf{A}\|_F\|\mathbf{B}\|_F$, coordinated sampling requires sketches of size $O(s/\epsilon^2)$ when $\mathbf{A}$ and $\mathbf{B}$ have at most $s \leq d,m$ non-zeros per row. In contrast, linear sketching leads to sketches of size $O(d/\epsilon^2)$ and $O(m/\epsilon^2)$ for $\mathbf{A}$ and $\mathbf{B}$. We empirically evaluate our approach on two applications: 1) distributed linear regression in databases, a problem motivated by tasks like dataset discovery and augmentation, and 2) approximating attention matrices in transformer-based language models. In both cases, our sampling algorithms yield an order of magnitude improvement over linear sketching.
• Abstract（参考訳）: 行列積を近似するよく研究された問題である $\mathbf{A}^T\mathbf{B}$ を、小さな空間スケッチである $\mathcal{S}(\mathbf{A})$ と $\mathcal{S}(\mathbf{B})$ と $\mathbf{A} \in \R^{n \times d}$ と $\mathbf{B}\in \R^{n \times m}$ に基づいて再検討する。 私たちは、共有ランダムシードの使用を除いて、スケッチを互いに独立して計算しなければならない設定に興味を持っています。 我々は、$\mathbf{A}$ と $\mathbf{B}$ がスパースであるとき、 \emph{coordinated random sample} に基づくメソッドは、Johnson-Lindenstrauss Projection や CountSketch のような古典的な線形スケッチ手法より優れていることを証明している。 例えば、フロベニウスのノルム誤差 $\epsilon\|\mathbf{A}\|_F\|\mathbf{B}\|_F$ を得るには、調整されたサンプリングには、$O(s/\epsilon^2)$ と $\mathbf{A}$ と $\mathbf{B}$ のスケッチが必要である。 対照的に、線形スケッチは$O(d/\epsilon^2)$と$O(m/\epsilon^2)$ for $\mathbf{A}$と$\mathbf{B}$のスケッチにつながる。 私たちは2つのアプリケーションに対するアプローチを実証的に評価します。 1)データベースにおける分散線形回帰、データセット発見や拡張といったタスクによって動機付けられた問題、 2) 変圧器を用いた言語モデルにおける注意行列の近似 どちらの場合も、サンプリングアルゴリズムは線形スケッチよりも桁違いに改善される。

関連論文リスト

• Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
  本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。 ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-11T03:43:52Z)
• In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting [21.002519159190538]
  我々は分散アルゴリズムを解析し、$N$クライアント上で低ランク行列の分解を計算する。 グローバルな$mathbfV$ in $mathbbRd times r$をすべてのクライアントに共通とし、ローカルな$mathbfUi$ in $mathbbRn_itimes r$を得る。
  論文  参考訳（メタデータ） (2024-09-13T12:28:42Z)
• 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)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。 mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
  論文  参考訳（メタデータ） (2023-10-02T16:44:47Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)

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

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