論文の概要: Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise

• arxiv url: http://arxiv.org/abs/2607.25190v1
• Date: Tue, 28 Jul 2026 01:42:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-29 20:50:42.675441
• Title: Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise
• Title（参考訳）: ロイドの「K$-Means Clustering」アルゴリズムはフランク・ウルフ
• Abstract要約: ロイドのアルゴリズムとフランク・ウルフ(FW)アルゴリズムの新たな接続を確立する。 非漸近的な$mathcalO (1/t)$収束率をSSE目的の局所最小値に導出する。 空のクラスタを考慮し、同じ収束率を維持しながら半平滑な目的のためのFW変種を開発する。
• 参考スコア（独自算出の注目度）: 12.631946630806302
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lloyd's $K$-means algorithm, also known as naïve $K$-means, is a widely used ad hoc optimization heuristic, designed to minimize the sum of squared errors (SSE) across all $K$-partitions of a dataset via iterative cluster refinement. In this work, we establish a novel connection between Lloyd's algorithm and the Frank-Wolfe (FW) algorithm, a prominent first-order method for projection-free optimization. We demonstrate that Lloyd's algorithm is a special case of FW. Leveraging recent advances in FW methods for concave objectives, we derive a non-asymptotic $\mathcal{O}(1/t)$ convergence rate to a local minimum of the SSE objective. To account for empty clusters, an outcome possible under Lloyd's greedy assignment, we develop an FW variant for semismooth objectives while retaining the same convergence rate that is solely controlled by the initial SSE value. We illustrate our findings with a simulation study for spherical Gaussian mixtures and a real-world image segmentation dataset.
• Abstract（参考訳）: ロイドの$K$-meansアルゴリズム(英: Lloyd's $K$-means algorithm)は、反復クラスタリファインメントによるデータセットのすべての$K$-partitionに対する2乗誤差(SSE)の和を最小化するために設計された、広く使われているアドホック最適化ヒューリスティックである。 本研究では,ロイドのアルゴリズムとFW(Frank-Wolfe)アルゴリズムとの新たな接続を確立する。 ロイドのアルゴリズムはFWの特別な場合であることを示す。 コンケーブ目的に対するFW法の最近の進歩を活用して、SSE目的の局所最小値への非漸近$\mathcal{O}(1/t)$収束率を導出する。 空のクラスタを考慮し、ロイドの欲求代入の下で得られる結果について、初期SSE値にのみ制御される同じ収束率を維持しながら、半平滑な目的のためのFW変種を開発する。 本研究は,球状ガウス混合と実世界の画像セグメンテーションデータセットのシミュレーション研究により述べる。

関連論文リスト

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations [24.939790719971136]
  我々は、ロイズアルゴリズム(Lloyd, 1956)として知られる古典的な$K$-means交互化アルゴリズムを解析する。 局所的なステップに対して支払われる価格は、より高い信号対雑音比であることが示される。
  論文  参考訳（メタデータ） (2025-05-23T22:58:40Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• 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)
• Consistency of Lloyd's Algorithm Under Perturbations [11.56433365648479]
  ロイドのアルゴリズムは最も広く使われているクラスタリングアルゴリズムの1つである。 準ガウス混合のサンプルに対するロイドのアルゴリズムの誤クラスタリング速度は、$O(log(n))$ iterationsの後に指数関数的に有界であることを示す。
  論文  参考訳（メタデータ） (2023-09-01T16:45:52Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model [12.868722327487752]
  行列値の観測を行うために低ランク混合モデル(LrMM)を提案する。 ロイドのアルゴリズムと低ランク近似を統合して計算効率のよいクラスタリング法を設計する。 本手法は,実世界のデータセットにおける文献上の他者よりも優れる。
  論文  参考訳（メタデータ） (2022-07-11T03:16:10Z)
• Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap [24.073221004661427]
  部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。 広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
  論文  参考訳（メタデータ） (2022-05-26T17:47:35Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。 クエリを少なくすることで、問題の解決が容易になる。
  論文  参考訳（メタデータ） (2021-06-04T02:32:26Z)
• A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering [0.0]
  ローン申請や広告などの人間中心の意思決定システムへのデータクラスタリングの適用において、クラスタリングの結果は異なる人口集団の人々に対して差別される可能性がある。 そこで我々は,$k$-meansの更新とグループスワップ更新を併用した,新たな交代バランス型$k$-means (SAKM) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T01:47:15Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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