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.05819v1
Date: Sun, 11 Aug 2024 16:46:42 GMT
ステータス: 処理完了
システム内更新日: 2024-08-13 15:27:01.069786
Title: On the Convergence of a Federated Expectation-Maximization Algorithm
Title（参考訳）: フェデレーション予測最大化アルゴリズムの収束性について
Authors: Zhixu Tao, Rajita Chandak, Sanjeev Kulkarni,
Abstract要約: 本稿では,Federated Mixture of $K$ Linear Regressionsモデルに対する期待最大化(EM)アルゴリズムの収束率について検討する。驚くべきことに、結果はボトルネックではなく、データの異質性によってフェデレート学習アルゴリズムの収束が加速することを示している。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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. We fully 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 each of the regimes. Interestingly, we identify that when $m$ grows exponentially in $n$, the EM algorithm only requires a constant number of iterations to converge. We perform experiments on synthetic datasets to illustrate our results. Surprisingly, the results show that rather than being a bottleneck, data heterogeneity can accelerate the convergence of federated learning algorithms.
Abstract（参考訳）: データの不均一性は、フェデレート学習アルゴリズムの収束率を研究する上で、長年にわたってボトルネックとなっていた。データ不均一性の問題をより深く理解するために,Federated Mixture of $K$ Linear Regressionsモデルに対する期待最大化(EM)アルゴリズムの収束率について検討する。 EMアルゴリズムの収束率を,$m/n$,$m$をクライアント数,$n$をクライアント毎のデータポイント数というすべての条件下で完全に特徴づける。信号対雑音比(SNR)を$\Omega(\sqrt{K})$で表すと、十分に初期化されたEMアルゴリズムはそれぞれの政権の下で基底真理の極小最大距離内に収束する。興味深いことに、$m$が指数関数的に$n$に成長するとき、EMアルゴリズムは収束するために一定の回数の反復しか必要としない。結果を説明するために,合成データセットの実験を行った。驚くべきことに、データはボトルネックではなく、フェデレートされた学習アルゴリズムの収束を加速することができる。

関連論文リスト

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)
Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-16T04:26:50Z)

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

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