論文の概要: Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions

• arxiv url: http://arxiv.org/abs/2609.06327v2
• Date: Sun, 13 Sep 2026 14:47:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:04.409015
• Title: Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions
• Title（参考訳）: ソフトマックス注意のための問合せ型コアセット:改善された境界と効率的な構成
• Abstract要約: ソフトマックスアテンションのためのクエリ公開コアセット(英: query-oblivious coreset for a softmax-attention)は、ボール内の全てのクエリに対して、注意出力が$varepsilon$以内のキー値ペアのサブセットである。 カーネルインスタンスはボズザイ・ヴォス連鎖を適用でき、Chevetの不等式はキーを値次元から分割し、サイズ$O(e(sqrtd_vKleinsqrtd_klog(1+))$をランダム時間で与える。 クウェン全首の国勢調査
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A query-oblivious coreset for a softmax-attention head is a subset of the key-value pairs whose attention output is within $\varepsilon$ of the full one for every query in a ball. Liberty, Andoni and Kleiner proved that unweighted coresets of size $O(\sqrt d e^{ρ+\frac12\logρ+o(\log\logρ)}/\varepsilon)$ exist, $ρ$ the query radius times the centred key radius, against a lower bound $Ω(\sqrt d e^ρ/\varepsilon)$, and conjectured that closing the gap needs new techniques. It does not: a spherical lift of both balls into one exponential-kernel instance lets the Bozzai-Rothvoss chaining bound apply, and Chevet's inequality splits key from value dimension, giving coresets of size $O(e^ρ(\sqrt{d_v}+\sqrt{d_k\log(1+ρ)})/\varepsilon)$ in randomised polynomial time, the first constructive whole-ball guarantee within $\sqrt{\log(1+ρ)}$ of the lower bound. A sampling cap $O(e^{2ρ}/\varepsilon^{2})$ completes the envelope; in fixed dimension Tai's diameter-free bound removes the logarithm, settling the Gaussian-restriction case of a Bozzai-Rothvoss question for the kernels. We give theLiberty-Andoni-Kleiner lower boud transfer the one-waycommunication bounds of Chen et r is the price of one signing forall queries. A census of every head of Qwen2.5-7B-Instruct and Llama-3-8B-Instruct finds $ρ$ at least 23.877, so everyactor $e^ρ/\varepsilon$prescribes a coreset larger than the cache: the algorithmic contribution is asymptotic on these models.
• Abstract（参考訳）: ソフトマックスアテンションヘッドの問合せ用コアセット(英: query-oblivious coreset for a softmax-attention head)は、ボール内の全てのクエリに対して、注意出力が$\varepsilon$以内のキー値ペアのサブセットである。 Liberty, Andoni and Kleiner は、サイズ$O(\sqrt d e^{ρ+\frac12\logρ+o(\log\logρ)}/\varepsilon)$の存在を証明した。 二つの球を1つの指数関数-カーネルインスタンスに球体を持ち上げると、ボズザイ・ロスボス連鎖が適用され、チェヴェットの不等式は値次元から鍵を分割し、値のコアセットが$O(e^ρ(\sqrt{d_v}+\sqrt{d_k\log(1+ρ)})/\varepsilon)$をランダム化多項式時間で与え、$\sqrt{\log(1+ρ)}$の最初の構成的全球保証は$\sqrt{\log(1+ρ)}$である。 サンプリングキャップ$O(e^{2ρ}/\varepsilon^{2})$はエンベロープを完成させ、固定次元のタイの直径自由境界は対数を取り除き、ボズザイ・ロスボス問題(英語版)のガウス制限ケースを固定する。 我々は、Chen et r の片方向通信境界は、署名された全てのクエリの価格である、Liberty-Andoni-Kleiner ローボー転送を与える。 Qwen2.5-7B-インストラクトとLlama-3-8B-インストラクトの全ヘッドの国勢調査では、$ρ$少なくとも23.877なので、 everyactor $e^ρ/\varepsilon$prescribes a coreset than the cache: the algorithmic contribute is asymptotic on these model。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy [0.0]
  グラフニューラルネットワークがスパースグラフにどの程度の深さを持つ必要があるかを研究する。 深さの値は、Kesten-Stigum比$=2$である。 任意の深さの局所分類器は、孤立根によって設定された普遍床 $e-(-)$ を破ることはない。
  論文  参考訳（メタデータ） (2026-07-18T07:11:45Z)
• Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model [37.35522173770848]
  対称ポリトープ$P=mathbfxinmathbbRd:|mathbfAmathbfx|_inftyle1$, $mathbfAinmathbbRntimes d$のジョン・エリプシドは、長いレバレッジスコアアルゴリズムによって計算される。
  論文  参考訳（メタデータ） (2026-06-18T11:00:03Z)
• New Bounds for Kernel Sums via Fast Spherical Embeddings [12.14121214083427]
  新たに$tilde O(d+varepsilon2+1/varepsilon3)$を証明した。 証明の中心には、Bartal, Recht and Schulman (2011) によって導入された意味での新しい高速球面埋め込み定理があり、埋め込みデータ直径を制限している。
  論文  参考訳（メタデータ） (2026-05-02T05:42:50Z)
• Tight Bounds for Learning Polyhedra with a Margin [0.2836066255205732]
  PAC学習交差点に$k$ハーフスペースと$$$マージンのアルゴリズムを誤差内に与える。 我々のアルゴリズムは、ほとんどの点がポリヘドロンの境界から少なくとも$$の距離を持つとしか約束されていないとき、より一般的な設定にまで拡張する。
  論文  参考訳（メタデータ） (2026-04-16T04:43:12Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• On the Intrinsic Dimensions of Data in Kernel Learning [1.675218291152252]
  ラプラスカーネルのようなカーネルの場合、実効次元$d_K$はミンコフスキー次元$d_$よりもかなり小さく、正則領域で証明可能であることを示す。 以上の結果から,Laplaceカーネルのようなカーネルの場合,実効次元$d_K$は,通常のドメインに有するMinkowski次元$d_$よりも著しく小さいことが分かる。
  論文  参考訳（メタデータ） (2026-01-22T17:32:24Z)
• Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers [9.19267739465056]
  サイズ $tildeO(varepsilon-2 cdot minvarepsilon-2, d)$ if $n geq 4m$。 d = 1$ の特別な場合、最適コアセットサイズは $tildeTheta(varepsilon-1/2 + fracmn varepsilon-1)$ となる。 我々の結果は、ロバスト$(k,z)$-clusteringにまで拡張されます。
  論文  参考訳（メタデータ） (2025-10-28T16:49:03Z)
• Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation [47.790126028106734]
  NPハードネスに対処するための一般的なアプローチは、強力なコアセットを計算することである。 我々は$ell_p$サブスペース近似を$tilde O(kepsilon-4/p)$ for $p2$と$tilde O(kp/2epsilon-p)$ for $p>2$に対して強コアセットを構築するアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-03T16:49:28Z)
• Stronger Coreset Bounds for Kernel Density Estimators via Chaining [0.5454560484178483]
  本稿では,カーネル関数のコアセットの複雑性を改善するために,差分法と連鎖法を適用した。 我々の結果は、ガウスカーネルとラプラシアカーネルのコアセットとして$Obig(fracsqrtdvarepsilonsqrtloglog frac1varepsilonbig)をランダムに生成する時間アルゴリズムを与える。 また、最もよく知られた$Obig(fracsqrtdvarepsilonsqrtlog (2max1,
  論文  参考訳（メタデータ） (2023-10-12T17:44:59Z)
• Non-asymptotic spectral bounds on the $\varepsilon$-entropy of kernel classes [4.178980693837599]
  この話題は、カーネルベースの手法の現代的な統計理論において重要な方向である。 我々は、我々の境界の多くの結果について議論し、それらが一般のカーネルのバウンドよりもかなり厳密であることを示す。
  論文  参考訳（メタデータ） (2022-04-09T16:45:22Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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