論文の概要: Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs

• arxiv url: http://arxiv.org/abs/2601.17136v1
• Date: Fri, 23 Jan 2026 19:25:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-27 15:23:07.302203
• Title: Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs
• Title（参考訳）: GPU上の線形代数カーネルK平均の通信回避
• Authors: Julian Bellavita, Matthew Rubino, Nakul Iyer, Andrew Chang, Aditya Devarakonda, Flavio Vella, Giulia Guidi,
• Abstract要約: 我々は大規模なKernel K-meansクラスタリングのための分散メモリ並列アルゴリズムスイートを提案する。 我々の手法は、ケルネル K-平均の計算コストが最も高い成分を通信効率の良い分散線形代数プリミティブにマッピングする。 我々の1.5Dアルゴリズムは、常に最高性能を達成し、K-meansは従来よりも1～2桁大きなデータにスケールできる。
• 参考スコア（独自算出の注目度）: 1.0017970035130424
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Clustering is an important tool in data analysis, with K-means being popular for its simplicity and versatility. However, it cannot handle non-linearly separable clusters. Kernel K-means addresses this limitation but requires a large kernel matrix, making it computationally and memory intensive. Prior work has accelerated Kernel K-means by formulating it using sparse linear algebra primitives and implementing it on a single GPU. However, that approach cannot run on datasets with more than approximately 80,000 samples due to limited GPU memory. In this work, we address this issue by presenting a suite of distributed-memory parallel algorithms for large-scale Kernel K-means clustering on multi-GPU systems. Our approach maps the most computationally expensive components of Kernel K-means onto communication-efficient distributed linear algebra primitives uniquely tailored for Kernel K-means, enabling highly scalable implementations that efficiently cluster million-scale datasets. Central to our work is the design of partitioning schemes that enable communication-efficient composition of the linear algebra primitives that appear in Kernel K-means. Our 1.5D algorithm consistently achieves the highest performance, enabling Kernel K-means to scale to data one to two orders of magnitude larger than previously practical. On 256 GPUs, it achieves a geometric mean weak scaling efficiency of $79.7\%$ and a geometric mean strong scaling speedup of $4.2\times$. Compared to our 1D algorithm, the 1.5D approach achieves up to a $3.6\times$ speedup on 256 GPUs and reduces clustering time from over an hour to under two seconds relative to a single-GPU sliding window implementation. Our results show that distributed algorithms designed with application-specific linear algebraic formulations can achieve substantial performance improvement.
• Abstract（参考訳）: クラスタリングはデータ分析において重要なツールであり、K平均はその単純さと汎用性で人気がある。 しかし、非線形分離可能なクラスタは扱えない。 Kernel K-meansはこの制限に対処するが、大きなカーネルマトリックスを必要とするため、計算とメモリ集約が可能である。 それまでの作業は、疎線型代数プリミティブを用いて定式化し、1つのGPU上で実装することで、カーネルK平均を加速した。 しかし、このアプローチはGPUメモリが限られているため、約8万以上のサンプルを持つデータセットでは実行できない。 本稿では,マルチGPUシステム上で大規模K-meansクラスタリングを行う分散並列並列アルゴリズムのスイートを提案することで,この問題に対処する。 提案手法は,K-meansの計算コストの高いコンポーネントをKernel K-means用に一意に調整された通信効率のよい分散線形代数プリミティブにマッピングし,数百万スケールのデータセットを効率的にクラスタリングする高度にスケーラブルな実装を実現する。 我々の研究の中心は、ケルネル K-平均に現れる線型代数原始体の通信効率の良い合成を可能にする分割スキームの設計である。 我々の1.5Dアルゴリズムは、常に最高性能を達成し、K-meansは従来よりも1～2桁大きなデータにスケールできる。 256 GPUでは、幾何平均スケーリング効率が79.7 %$で、幾何学平均スケーリングスピードが4.2 times$である。 1Dアルゴリズムと比較して、1.5Dアプローチは256GPU上で最大3.6\times$のスピードアップを実現し、単一GPUスライディングウインドウの実装と比較して1時間以上から2秒未満のクラスタリング時間を削減する。 アプリケーション固有の線形代数的定式化を用いて設計した分散アルゴリズムは,大幅な性能向上を実現することができることを示す。

関連論文リスト

• Large-Scale Gaussian Processes via Alternating Projection [23.79090469387859]
  本稿では,カーネル行列のサブブロックのみにアクセスする反復的手法を提案する。 我々のアルゴリズムは、交互プロジェクションに基づくもので、GPを非常に大きなデータセットにスケールするという現実的な課題の多くを解決し、各イテレーション時間と空間の複雑さを$mathcalO(n)で解決している。
  論文  参考訳（メタデータ） (2023-10-26T04:20:36Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  平均推定なしで直接データのクラスタを検出する新しいクラスタリングアルゴリズムを提案する。 具体的には,バタワースフィルタを用いてデータ点間の距離行列を構成する。 異なる視点に埋め込まれた相補的な情報をうまく活用するために、テンソルのSchatten p-norm正規化を利用する。
  論文  参考訳（メタデータ） (2023-05-12T03:01:41Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Adaptive Explicit Kernel Minkowski Weighted K-means [1.3535770763481905]
  カーネル K-平均は、K-平均をカーネル空間に拡張し、非線形構造を捉えることができ、任意の形状のクラスターを識別することができる。 本稿では, 線形および非線形アプローチの利点を, 駆動された対応する有限次元特徴写像を用いて組み合わせる手法を提案する。
  論文  参考訳（メタデータ） (2020-12-04T19:14:09Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
  単純なマルチカーネルk-means(SimpleMKKM)と呼ばれる,単純で効果的なマルチカーネルクラスタリングアルゴリズムを提案する。 我々の基準は、カーネル係数とクラスタリング分割行列における難解な最小化最大化問題によって与えられる。 クラスタリング一般化誤差の観点から,SimpleMKKMの性能を理論的に解析する。
  論文  参考訳（メタデータ） (2020-05-11T10:06:40Z)
• Fast Kernel k-means Clustering Using Incomplete Cholesky Factorization [11.631064399465089]
  カーネルベースのクラスタリングアルゴリズムは、データセット内の非線形構造を特定し、キャプチャすることができる。 線形クラスタリングよりも優れたパフォーマンスを実現することができる。 カーネルマトリックス全体の計算と保存は非常に大きなメモリを占有しているため、カーネルベースのクラスタリングが大規模なデータセットを扱うことは困難である。
  論文  参考訳（メタデータ） (2020-02-07T15:32:14Z)

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

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