Nearly Optimal Attention Coresets

2026-05-07 · Edo Liberty, Alexandr Andoni, Eldar Kleiner arxiv

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^ρ/ε})$.

📄 PDF Abstract BibTeX arXiv:2605.05602

Code (0)

등록된 구현이 없습니다.

Coresets for Multiple $\ell_p$ Regression

2024-06-04 · David P. Woodruff, Taisuke Yasuda

A coreset of a dataset with $n$ examples and $d$ features is a weighted subset of examples that is sufficient for solving downstream data analytic tasks. Nearly optimal constructions of coresets for least squares and $\e…

regression

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation

2024-07-03 · David P. Woodruff, Taisuke Yasuda

The $\ell_p$ subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane ($p = 1$), principal component analysis ($p = 2$), and center hyperplane problems ($p = \inf…

Coresets for Vertical Federated Learning: Regularized Linear Regression and $K$-Means Clustering

2022-10-26 · Lingxiao Huang, Zhize Li, Jialin Sun, Haoyu Zhao

Vertical federated learning (VFL), where data features are stored in multiple parties distributively, is an important area in machine learning. However, the communication complexity for VFL is typically very high. In thi…

Clustering Federated Learning regression Vertical Federated Learning

Composable Coresets for Determinant Maximization: Greedy is Almost Optimal

2023-09-26 · NeurIPS 2023 11

Given a set of $n$ vectors in $\mathbb{R}^d$, the goal of the \emph{determinant maximization} problem is to pick $k$ vectors with the maximum volume. Determinant maximization is the MAP-inference task for determinantal p…

2k Point Processes

Universal Weak Coreset

2023-05-26 · Ragesh Jaiswal, Amit Kumar

Coresets for $k$-means and $k$-median problems yield a small summary of the data, which preserve the clustering cost with respect to any set of $k$ centers. Recently coresets have also been constructed for constrained $k…

Clustering Constrained Clustering Data Compression