論文の概要: 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を提案する。 我々は、これらの局所的なイテレーションのコストを非分散的な設定と比較し、局所的なステップに対して支払われるコストがより高い信号対雑音比であることを示す。 局所的な反復は、勾配に基づく学習法において理論的に研究されてきたが、非教師なし学習法の解析は、反復的勾配に基づくアルゴリズムよりも潜伏変数、例えばクラスタの同一性の存在により、より関与している。 この結果を得るために,非凸,非平滑な目的関数を扱う仮想イテレート法と,ロイドステップの厳密な統計解析を併用する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• 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)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)

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

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