論文の概要: A Geometric Approach to $k$-means
- arxiv url: http://arxiv.org/abs/2201.04822v1
- Date: Thu, 13 Jan 2022 07:47:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-14 23:01:28.186567
- Title: A Geometric Approach to $k$-means
- Title（参考訳）: $k$-meansに対する幾何学的アプローチ
- Authors: Jiazhen Hong, Wei Qian, Yudong Chen, Yuqian Zhang
- Abstract要約: 本稿では、望ましくないローカルソリューションをエスケープするための一般的なアルゴリズムフレームワークを提案する。
本稿では,これらのステップの実装について議論し,提案手法が$k$-meansアルゴリズムの変種をどのように統合するかを明らかにする。
- 参考スコア（独自算出の注目度）: 17.933546927589685
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: $k$-means clustering is a fundamental problem in various disciplines. This
problem is nonconvex, and standard algorithms are only guaranteed to find a
local optimum. Leveraging the structure of local solutions characterized in
[1], we propose a general algorithmic framework for escaping undesirable local
solutions and recovering the global solution (or the ground truth). This
framework consists of alternating between the following two steps iteratively:
(i) detect mis-specified clusters in a local solution and (ii) improve the
current local solution by non-local operations. We discuss implementation of
these steps, and elucidate how the proposed framework unifies variants of
$k$-means algorithm in literature from a geometric perspective. In addition, we
introduce two natural extensions of the proposed framework, where the initial
number of clusters is misspecified. We provide theoretical justification for
our approach, which is corroborated with extensive experiments.
- Abstract（参考訳）: k$-meansクラスタリングは、さまざまな分野において根本的な問題である。
この問題は非凸であり、標準アルゴリズムは局所最適を見つけることが保証されている。
[1]に特徴付けられる局所解の構造を活用し,好ましくない局所解をエスケープし,大域的解(あるいは基底的真理)を回復するための一般的なアルゴリズムフレームワークを提案する。
この枠組みは次の2つのステップを反復的に交互に構成する。
(i)局所溶液中の誤特定クラスタを検出して
(ii)非局所操作による現在のローカルソリューションの改善。
本稿では,これらのステップの実装について論じ,幾何学的観点からの文献における$k$-meansアルゴリズムの変種をいかに統一するかを明らかにする。
さらに、提案フレームワークの2つの自然な拡張を導入し、初期クラスタ数を誤特定する。
我々は、我々のアプローチを理論的に正当化し、広範な実験と組み合わせる。
関連論文リスト
- SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization [35.92829763686735]
本稿では,複数のエージェントが協調して,近傍通信によるネスト最適化構造に関わる問題を解く分散二段階最適化について検討する。
SPARKLE(Single-loop Primal-dual AlgoRithm frameworK)を提案する。
本稿では,SPARKLEの統一収束解析を行い,既存の分散二段階アルゴリズムと比較して,最先端の収束率を持つ全変種に適用する。
論文 参考訳（メタデータ） (2024-11-21T14:23:06Z) - A One-shot Framework for Distributed Clustered Learning in Heterogeneous
Environments [54.172993875654015]
異種環境における分散学習のためのコミュニケーション効率化手法のファミリーを提案する。
ユーザによるローカル計算に基づくワンショットアプローチと、サーバにおけるクラスタリングベースのアグリゲーションステップは、強力な学習保証を提供する。
厳密な凸問題に対しては,ユーザ毎のデータ点数がしきい値を超える限り,提案手法はサンプルサイズの観点から順序最適平均二乗誤差率を達成する。
論文 参考訳（メタデータ） (2022-09-22T09:04:10Z) - Gradient Based Clustering [72.15857783681658]
本稿では,クラスタリングの品質を計測するコスト関数の勾配を用いて,距離に基づくクラスタリングの一般的な手法を提案する。
アプローチは反復的な2段階の手順(クラスタ割り当てとクラスタセンターのアップデートの代替)であり、幅広い機能に適用できる。
論文 参考訳（メタデータ） (2022-02-01T19:31:15Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Distributed and Stochastic Optimization Methods with Gradient
Compression and Local Steps [0.0]
本稿では,誤差補償と局所的な更新を伴う解析および分散手法に関する理論的枠組みを提案する。
線形収束型Error-pensated法と分散型Local-SGD法を含む20以上の新しい最適化手法を開発した。
論文 参考訳（メタデータ） (2021-12-20T16:12:54Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - From Local SGD to Local Fixed-Point Methods for Federated Learning [17.04886864943171]
分散環境で,演算子の平均点の固定点,あるいは近似を求めるという一般的な問題を考える。
このようなコンセンサスを達成するための2つの戦略について検討する。一方は局所的なステップの固定数に基づくもので、もう一方はランダム化された計算に基づくものである。
論文 参考訳（メタデータ） (2020-04-03T09:24:10Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳（メタデータ） (2020-03-31T16:54:22Z) - Structures of Spurious Local Minima in $k$-means [20.155509538529568]
我々は、$k$-means問題に対する急激な局所解の構造について検討する。
分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
論文 参考訳（メタデータ） (2020-02-16T22:15:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。