論文の概要: A Batched Hartigan's $k$-Means Clustering

• arxiv url: http://arxiv.org/abs/2611.01207v1
• Date: Sat, 31 Oct 2026 18:59:34 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:48:43.039518
• Title: A Batched Hartigan's $k$-Means Clustering
• Title（参考訳）: バッチされたHartiganの$k$-Meansクラスタリング
• Abstract要約: 三角不等式を利用してベクトル化計算が可能なバッチハートガン法を考案する。 これにより、ハーディガンの手法はロイドの実行速度と初めて競合する。
• 参考スコア（独自算出の注目度）: 36.6519146337756
• License:
• Abstract: Hartigan's $k$-means algorithm has theoretical advantages over the standard Lloyd's variant, which has become synonymous with "$k$-means". Yet, Hartigan's algorithm is far slower in practice due to its inherently sequential calculations. We devise a Batched Hartigan's method that enables vectorized calculation by exploiting the triangle inequality to expose a set of parallel-safe updates and a smaller set of sequential updates. This makes Hartigan's method competitive with Lloyd's in execution speed for the first time.
• Abstract（参考訳）: ハルティガンの$k$-meansアルゴリズムは、標準ロイドの変種よりも理論的に有利であり、「$k$-means」と同義語となった。 しかし、ハルティガンのアルゴリズムは本質的にシーケンシャルな計算のため、実際ははるかに遅くなっている。 我々は、三角形の不等式を利用してベクトル化された計算を可能にするバッチハートガン法を考案し、並列セーフな更新セットとより小さなシーケンシャルな更新セットを公開する。 これにより、ハーディガンの手法はロイドの実行速度と初めて競合する。

関連論文リスト

• Minimax Last-Iterate Convergence in Matrix Games with Observed Actions [14.692647465985916]
  各ラウンドで高い確率で$widetildemathcalO(sqrtd/t)$の双対性ギャップを達成するアルゴリズムを開発する。 レートは標準帯域幅の下限と一致し、アクションの数とラウンド数の両方において最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2026-09-28T08:59:34Z)
• Mean-based algorithms: A lower bound and regret [0.0]
  平均に基づくアルゴリズムは、平均的な報酬が低いアクションに低い確率を割り当てる。 時間的地平線が不明で,帯域幅フィードバックのみが利用可能である場合,平均に基づくアルゴリズムについて検討する。 実験によると、平均ベースのアルゴリズムはわずかに遅いが、他の帯域幅フィードバックアルゴリズムと競合する可能性がある。
  論文  参考訳（メタデータ） (2026-06-03T14:23:41Z)
• An effective variant of the Hartigan $k$-means algorithm [0.013714053458441644]
  k-平均問題はおそらく古典的なクラスタリング問題であり、ロイドのアルゴリズム(1957年)と同義である。 ハーディガンのアルゴリズム(1975年)がほぼ全てのケースでより良い結果を与えることが明らかになっている。
  論文  参考訳（メタデータ） (2026-04-23T15:57:05Z)
• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback [46.50566806285207]
  ゼロサム行列ゲームにおいて繰り返しプレイやバンディットフィードバックで学習する問題について検討する。 プレイヤー間の通信なしに、最終項目のナッシュ均衡への収束を保証するアンカップリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-04-17T14:17:09Z)
• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation [3.6042575355093907]
  我々は,新しい変数を導入することにより,二乗証明の総和の程度を大幅に減少させる汎用フレームワークを開発した。 クラスタリングとロバストモーメント推定という2つの重要な推定問題に対して,2乗和に基づくアルゴリズムを高速化する。
  論文  参考訳（メタデータ） (2021-01-05T13:49:59Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)

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

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