Fugu-MT 論文翻訳(概要): On the Convergence of a Federated Expectation-Maximization Algorithm

論文の概要: On the Convergence of a Federated Expectation-Maximization Algorithm

arxiv url: http://arxiv.org/abs/2408.05819v2
Date: Mon, 17 Mar 2025 19:15:58 GMT
ステータス: 翻訳完了
システム内更新日: 2025-03-19 14:13:22.201703
Title: On the Convergence of a Federated Expectation-Maximization Algorithm
Title（参考訳）: フェデレーション予測最大化アルゴリズムの収束性について
Authors: Zhixu Tao, Rajita Chandak, Sanjeev Kulkarni,
Abstract要約: FMLR(Federated Mixture of $K$ Linear Regressions Model)の予測最大化(EM)アルゴリズムの収束率について検討する。我々は、$Omega(sqrtK)$の信号対雑音比(SNR)を用いて、よく知られたEMアルゴリズムが、すべての規則の下で基底真理のミニマックス距離内に収束することを示す。興味深いことに、クライアントの数がクライアント毎のデータポイント数に対して合理的に増加すると、EMアルゴリズムは収束するために一定回数の反復しか必要としない。
参考スコア（独自算出の注目度）: 0.0
License:
Abstract: Data heterogeneity has been a long-standing bottleneck in studying the convergence rates of Federated Learning algorithms. In order to better understand the issue of data heterogeneity, we study the convergence rate of the Expectation-Maximization (EM) algorithm for the Federated Mixture of $K$ Linear Regressions model (FMLR). We completely characterize the convergence rate of the EM algorithm under all regimes of $m/n$ where $m$ is the number of clients and $n$ is the number of data points per client. We show that with a signal-to-noise-ratio (SNR) of order $\Omega(\sqrt{K})$, the well-initialized EM algorithm converges within the minimax distance of the ground truth under all regimes. Interestingly, we identify that when the number of clients grows reasonably with respect to the number of data points per client, the EM algorithm only requires a constant number of iterations to converge. We perform experiments on synthetic data to illustrate our results. In line with our theoretical findings, the simulations show that rather than being a bottleneck, data heterogeneity can accelerate the convergence of iterative federated algorithms.
Abstract（参考訳）: データの不均一性は、フェデレート学習アルゴリズムの収束率を研究する上で、長年にわたってボトルネックとなっていた。データ不均一性の問題をよりよく理解するために,Federated Mixture of $K$ Linear Regressions Model (FMLR) に対する期待最大化(EM)アルゴリズムの収束率について検討した。我々は、$m/n$、$m$はクライアント数、$n$はクライアント当たりのデータポイント数という全ての規則の下で、EMアルゴリズムの収束率を完全に特徴付けている。信号対雑音比(SNR)を$\Omega(\sqrt{K})$で表すと、十分に初期化されたEMアルゴリズムはすべての規則の下で基底真理の極大距離内に収束する。興味深いことに、クライアントの数がクライアント毎のデータポイント数に対して合理的に増加すると、EMアルゴリズムは収束するために一定回数の反復しか必要としない。結果を説明するために,合成データの実験を行った。理論的な結果から,データの不均一性はボトルネックではなく,反復的フェデレーションアルゴリズムの収束を加速させることが示唆された。

関連論文リスト

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)
A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文参考訳（メタデータ） (2024-09-07T06:37:23Z)
Achieving Linear Speedup in Non-IID Federated Bilevel Learning [16.56643290676128]
我々はFedMBOという新しいフェデレーションバイレベルアルゴリズムを提案する。 We show that FedMBO achieve a convergence rate of $mathcalObig(frac1sqrtnK+frac1K+fracsqrtnK3/2big)$ on non-i.d.datasets。これは、i.d.d.federated bilevel optimizationに対する最初の理論的線形スピードアップ結果である。
論文参考訳（メタデータ） (2023-02-10T18:28:00Z)
Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文参考訳（メタデータ） (2022-10-21T15:56:13Z)
Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文参考訳（メタデータ） (2022-10-14T01:42:05Z)
Differentially Private Federated Learning via Inexact ADMM with Multiple Local Updates [0.0]
我々は,複数の局所的な更新を施した乗算器アルゴリズムのDP不正確な交互方向法を開発した。当社のアルゴリズムでは,各イテレーション毎に$barepsilon$-DPを提供しており,$barepsilon$はユーザが管理するプライバシ予算である。提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも31%削減すると同時に,データプライバシのレベルが同じであることを実証する。
論文参考訳（メタデータ） (2022-02-18T19:58:47Z)
A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
論文参考訳（メタデータ） (2021-10-27T08:01:17Z)
PROMPT: Parallel Iterative Algorithm for $\ell_{p}$ norm linear regression via Majorization Minimization with an application to semi-supervised graph learning [0.0]
スパースリカバリ,データクラスタリング,半教師付き学習など,いくつかの応用がある。我々は、MajolizaTion Minimization (PROMPT)による$ell_P$ノルム回帰のための並列反復AlgOrithMを提案する。
論文参考訳（メタデータ） (2021-10-23T10:19:11Z)
Differentially Private Federated Learning via Inexact ADMM [0.0]
差分プライバシー(DP)技術は、データプライバシを推論攻撃から保護するために、フェデレーション付き学習モデルに適用することができる。我々は,信頼領域のサブプロブレム列を解く乗算器アルゴリズムのDP不正確な交互方向法を開発した。提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも22%削減すると同時に,データプライバシのレベルも同等に向上する。
論文参考訳（メタデータ） (2021-06-11T02:28:07Z)
Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文参考訳（メタデータ） (2020-11-19T10:00:54Z)
Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。提案アルゴリズムの有効性と有効性を示す実験を行った。
論文参考訳（メタデータ） (2020-11-04T16:49:29Z)

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

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