論文の概要: Faster Approx. Top-K: Harnessing the Full Power of Two Stages
- arxiv url: http://arxiv.org/abs/2506.04165v1
- Date: Wed, 04 Jun 2025 17:04:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-05 21:20:14.481795
- Title: Faster Approx. Top-K: Harnessing the Full Power of Two Stages
- Title（参考訳）: より高速な近似トップK:2段階のフルパワーのハーネス
- Authors: Yashas Samaga, Varun Yerram, Spandana Raj Babbula, Prateek Jain, Praneeth Netrapalli,
- Abstract要約: 我々は、配列から最大値のK$要素を特定することを目的としたTop-$K$選択問題を考える。
我々は、Cloud TPUv5e上にアルゴリズムを実装し、元のアルゴリズムよりも桁違いのスピードアップを実現した。
- 参考スコア（独自算出の注目度）: 27.818549607776752
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the Top-$K$ selection problem, which aims to identify the largest-$K$ elements from an array. Top-$K$ selection arises in many machine learning algorithms and often becomes a bottleneck on accelerators, which are optimized for dense matrix multiplications. To address this problem, \citet{chern2022tpuknnknearestneighbor} proposed a fast two-stage \textit{approximate} Top-$K$ algorithm: (i) partition the input array and select the top-$1$ element from each partition, (ii) sort this \textit{smaller subset} and return the top $K$ elements. In this paper, we consider a generalized version of this algorithm, where the first stage selects top-$K'$ elements, for some $1 \leq K' \leq K$, from each partition. Our contributions are as follows: (i) we derive an expression for the expected recall of this generalized algorithm and show that choosing $K' > 1$ with fewer partitions in the first stage reduces the input size to the second stage more effectively while maintaining the same expected recall as the original algorithm, (ii) we derive a bound on the expected recall for the original algorithm in \citet{chern2022tpuknnknearestneighbor} that is provably tighter by a factor of $2$ than the one in that paper, and (iii) we implement our algorithm on Cloud TPUv5e and achieve around an order of magnitude speedups over the original algorithm without sacrificing recall on real-world tasks.
- Abstract（参考訳）: 我々は、配列から最大値のK$要素を特定することを目的としたTop-$K$選択問題を考える。
上位$K選択は、多くの機械学習アルゴリズムで発生し、高密度行列乗算に最適化されたアクセラレーターのボトルネックになることが多い。
この問題に対処するため、 \citet{chern2022tpuknnknearestneighbor} は高速な2段階の \textit{approximate} Top-$K$アルゴリズムを提案した。
i) 入力配列を分割し、各パーティションから上位1$要素を選択する。
(ii) この \textit{smaller subset} をソートし、上位の$K$要素を返す。
本稿では,このアルゴリズムの一般化バージョンについて考察する。このアルゴリズムでは,各パーティションから,各パーティションから上位$K'$要素を約1ドルで選択する。
私たちの貢献は以下の通りです。
(i) この一般化されたアルゴリズムの期待されるリコールの式を導出し、第1段階でのパーティションが少ない$K' > 1$を選択すると、元のアルゴリズムと同じリコールを維持しつつ、入力サイズを第2ステージに効果的に削減できることを示す。
(ii) 元のアルゴリズムのリコールの期待値に上限を導出します。これは、その論文の2ドル以上の係数で、確実に厳密である。
3)本アルゴリズムをCloud TPUv5e上に実装し,実世界のタスクのリコールを犠牲にすることなく,元のアルゴリズムよりも約1桁の高速化を実現する。
関連論文リスト
- Log-Time K-Means Clustering for 1D Data: Novel Approaches with Proof and Implementation [0.0]
この論文は、1D$k$-meansクラスタリングの理論と実践を橋渡しし、効率的で健全なアルゴリズムを提供する。
ベンチマークでは、大規模なデータセットのScikit-learnと比較して、4500倍のスピードアップが示されている。
論文 参考訳（メタデータ） (2024-12-19T09:03:39Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - A Faster $k$-means++ Algorithm [11.428775569173638]
ほぼ最適な実行時間で$k$-means++問題を解決するアルゴリズムを提案する。
我々は、$widetildeO(nd + nk2)$時間しかかからない新しいアルゴリズムtextscFastKmeans++を提案する。
論文 参考訳（メタデータ） (2022-11-28T08:17:12Z) - An Improved Algorithm For Online Min-Sum Set Cover [0.45687771576879593]
我々は、アルゴリズムが注文された$n$要素のリストを保持するオンライン嗜好集約のモデルについて研究する。
競合比(ALG-to-OPTコスト比)が$O(r2)$である計算効率の良いランダム化アルゴリズムを構築する。
O(r3/2 cdot sqrtn)$-competitive and $Omega(r)$ is a lower bound on the performance of any deterministic online algorithm。
論文 参考訳（メタデータ） (2022-09-11T14:03:51Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - A new heuristic algorithm for fast k-segmentation [0.0]
文献には$k$-segmentationの厳密で近似的な方法が存在する。
本稿では,既存の手法を改善するために,新しいアルゴリズムを提案する。
計算コストのごく一部で正確な手法と競合するアキュラシーを提供することを実証的に見出した。
論文 参考訳（メタデータ） (2020-09-02T04:50:17Z) - Submodular Maximization in Clean Linear Time [42.51873363778082]
我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。
解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
論文 参考訳（メタデータ） (2020-06-16T17:06:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。