論文の概要: Nearly Optimal Attention Coresets
- arxiv url: http://arxiv.org/abs/2605.05602v1
- Date: Thu, 07 May 2026 02:37:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-08 22:27:11.491122
- Title: Nearly Optimal Attention Coresets
- Title（参考訳）: ほぼ最適注意コアセット
- Authors: Edo Liberty, Alexandr Andoni, Eldar Kleiner,
- Abstract要約: 単位ノルムキーと値の任意のセットに対して$(K,V)$ in $mathbbRd$に対して、大まかに$O(sqrtd e+o()/varepsilon)$ である部分集合 $(K',V')$ が存在して [ left| operatornameAttn(q,K,V)- operatornameAttn(q,K',V') right| となることを示す。
- 参考スコア（独自算出の注目度）: 44.07231236667843
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of estimating the Attention mechanism in small space, and prove the existence of coresets for it of nearly optimal size. Specifically, we show that for any set of unit-norm keys and values $(K,V)$ in $\mathbb{R}^d$, there exists a subset $(K',V')$ of size at most $O({\sqrt{d} e^{ρ+o(ρ)}/\varepsilon})$ such that \[ \left\| \operatorname{Attn}(q,K,V)- \operatorname{Attn}(q,K',V') \right\| \le \varepsilon \] simultaneously for all queries whose norm is bounded by $ρ$. This outperforms the best known results for this problem. We also offer an improved lower bound showing that $\varepsilon$-coresets must have size $Ω({\sqrt{d} e^ρ/ε})$.
- Abstract（参考訳）: 我々は,小空間における注意機構を推定する問題を考察し,ほぼ最適な大きさのコアセットの存在を証明した。
具体的には、任意の単位ノルムキーと値の集合に対して、$(K,V)$ in $\mathbb{R}^d$ に対して、大まかに$O({\sqrt{d} e^{ρ+o(ρ)}/\varepsilon})$ である部分集合 $(K',V')$ が存在し、ノルムが $ρ$ で有界なすべてのクエリに対して \[ \left\| \operatorname{Attn}(q,K,V)- \operatorname{Attn}(q,K',V') \right\| \le \varepsilon \] が同時に存在することを示す。
この問題は最もよく知られた結果を上回っている。
また、$\varepsilon$-coresets は $Ω({\sqrt{d} e^ρ/ε})$ でなければならないことを示す。
関連論文リスト
- Deterministic Coreset for Lp Subspace [10.070877057133004]
本稿では,決定論的$ell_p$サブスペース埋め込みを保証する$varepsilon$-coresetを構築するための最初の反復アルゴリズムを紹介する。
各イテレーションにおいて、アルゴリズムは、保守されたセットの損失が元のデータセットの損失によって上と下の境界であることを保証する。
我々のコアセットは $ell_p$ 回帰問題を決定論的に解くのにも使える。
論文 参考訳（メタデータ） (2026-01-01T14:31:16Z) - Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
複素ヒルベルト空間上で作用するエルミート作用素 $A$ を 2n$ とする。
A$ がパウリ拡大において小さな次数を持つとき、あるいは言い換えれば、$A$ は局所 $n$-量子ハミルトニアンである。
A$ が $d$-local, textiti.e., $deg(A)le d$ であるときは常に、次の離散化型不等式を持つことを示す。
論文 参考訳（メタデータ） (2025-09-15T14:26:11Z) - Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
制約付き部分空間近似のための一般的なフレームワークを導入する。
分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
論文 参考訳（メタデータ） (2025-04-29T15:56:48Z) - A Tight VC-Dimension Analysis of Clustering Coresets with Applications [19.213536807823836]
ここでは,距離の最小化を行う中心に点を割り当てることが目的とする,$k$-clustering問題に対するコアセットを検討する。
点集合 $P$ が与えられたとき、コアセット $Omega$ はすべての候補解に対して$P$ のコストを近似する小さな重み付き部分集合である。
以下の指標に対して、改良された$k$-medianコアセット境界を得る。
論文 参考訳（メタデータ） (2025-01-11T17:00:57Z) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳（メタデータ） (2024-02-23T12:22:03Z) - Improved Coresets for Euclidean $k$-Means [24.850829728643923]
1組の$d$次元の$n$ポイントが与えられたとき、ユークリッド$k$平均問題(ユークリッド$k$中間問題を参照)は、$k$センターを見つけることからなる。
本稿では,$tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon)を改善する。
論文 参考訳（メタデータ） (2022-11-15T14:47:24Z) - Towards Optimal Lower Bounds for k-median and k-means Coresets [25.713987341159918]
計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。
我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
論文 参考訳（メタデータ） (2022-02-25T16:13:28Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。