論文の概要: LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations

• arxiv url: http://arxiv.org/abs/2505.18420v1
• Date: Fri, 23 May 2025 22:58:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:42.409433
• Title: LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations
• Title（参考訳）: LocalKMeans: 分散ローカルイテレーションによるRoydのアルゴリズムの収束
• Authors: Harsh Vardhan, Heng Zhu, Avishek Ghosh, Arya Mazumdar,
• Abstract要約: 我々は、ロイズアルゴリズム(Lloyd, 1956)として知られる古典的な$K$-means交互化アルゴリズムを解析する。 局所的なステップに対して支払われる価格は、より高い信号対雑音比であることが示される。
• 参考スコア（独自算出の注目度）: 24.939790719971136
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we analyze the classical $K$-means alternating-minimization algorithm, also known as Lloyd's algorithm (Lloyd, 1956), for a mixture of Gaussians in a data-distributed setting that incorporates local iteration steps. Assuming unlabeled data distributed across multiple machines, we propose an algorithm, LocalKMeans, that performs Lloyd's algorithm in parallel in the machines by running its iterations on local data, synchronizing only every $L$ of such local steps. We characterize the cost of these local iterations against the non-distributed setting, and show that the price paid for the local steps is a higher required signal-to-noise ratio. While local iterations were theoretically studied in the past for gradient-based learning methods, the analysis of unsupervised learning methods is more involved owing to the presence of latent variables, e.g. cluster identities, than that of an iterative gradient-based algorithm. To obtain our results, we adapt a virtual iterate method to work with a non-convex, non-smooth objective function, in conjunction with a tight statistical analysis of Lloyd steps.
• Abstract（参考訳）: 本稿では,従来の$K$-means交互最小化アルゴリズム,あるいはロイズアルゴリズム (Lloyd, 1956) を,局所的な反復ステップを組み込んだデータ分散環境で解析する。 複数のマシンにまたがるラベル付けされていないデータを仮定すると、ローカルデータ上で繰り返し実行し、そのようなローカルステップの1L$ごとにのみ同期するアルゴリズムであるLoydのアルゴリズムをマシン内で並列に実行するLocalKMeansを提案する。 我々は、これらの局所的なイテレーションのコストを非分散的な設定と比較し、局所的なステップに対して支払われるコストがより高い信号対雑音比であることを示す。 局所的な反復は、勾配に基づく学習法において理論的に研究されてきたが、非教師なし学習法の解析は、反復的勾配に基づくアルゴリズムよりも潜伏変数、例えばクラスタの同一性の存在により、より関与している。 この結果を得るために,非凸,非平滑な目的関数を扱う仮想イテレート法と,ロイドステップの厳密な統計解析を併用する。

関連論文リスト

• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• 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)
• Robust Methods for High-Dimensional Linear Learning [0.0]
  統計的に頑健で計算効率の良い線形学習法を高次元バッチ設定で提案する。 バニラスパース、グループスパース、低ランク行列回復など、いくつかのアプリケーションでフレームワークをインスタンス化する。 バニラ $s$-sparsity の場合、重いテールと $eta$-corruption の下で $slog (d)/n$ レートに達することができます。
  論文  参考訳（メタデータ） (2022-08-10T17:00:41Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• On Accelerating Distributed Convex Optimizations [0.0]
  本稿では,分散マルチエージェント凸最適化問題について検討する。 提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。 実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
  論文  参考訳（メタデータ） (2021-08-19T13:19:54Z)
• Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent [7.6860514640178]
  分散強化学習のための新しいゼロ階最適化アルゴリズムを提案する。 これにより、各エージェントはコンセンサスプロトコルを使わずに、コスト評価を独立してローカル勾配を推定できる。
  論文  参考訳（メタデータ） (2021-07-26T18:11:07Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• From Local SGD to Local Fixed-Point Methods for Federated Learning [17.04886864943171]
  分散環境で,演算子の平均点の固定点,あるいは近似を求めるという一般的な問題を考える。 このようなコンセンサスを達成するための2つの戦略について検討する。一方は局所的なステップの固定数に基づくもので、もう一方はランダム化された計算に基づくものである。
  論文  参考訳（メタデータ） (2020-04-03T09:24:10Z)

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

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