論文の概要: Heterogeneous Federated Learning on a Graph
- arxiv url: http://arxiv.org/abs/2209.08737v1
- Date: Mon, 19 Sep 2022 03:18:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-20 17:16:00.010021
- Title: Heterogeneous Federated Learning on a Graph
- Title(参考訳): グラフ上のヘテロジニアスフェデレーション学習
- Authors: Huiyuan Wang and Xuyang Zhao and Wei Lin
- Abstract要約: ローカルデータを共有せずに複数の分散デバイスでアルゴリズムをトレーニングするフェデレーション学習は、機械学習の実践でますます人気を集めている。
本研究では,データ分散と通信の不均一性を伴うフェデレート学習繰り返しにおけるパラメータ推定と,ローカル機器の計算能力の制限について考察する。
我々のアルゴリズムは収束率$O(T-1log T)$で$G$のエッジに沿ってパラメータのみを送信する。
- 参考スコア(独自算出の注目度): 9.135254524746847
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Federated learning, where algorithms are trained across multiple
decentralized devices without sharing local data, is increasingly popular in
distributed machine learning practice. Typically, a graph structure $G$ exists
behind local devices for communication. In this work, we consider parameter
estimation in federated learning with data distribution and communication
heterogeneity, as well as limited computational capacity of local devices. We
encode the distribution heterogeneity by parametrizing distributions on local
devices with a set of distinct $p$-dimensional vectors. We then propose to
jointly estimate parameters of all devices under the $M$-estimation framework
with the fused Lasso regularization, encouraging an equal estimate of
parameters on connected devices in $G$. We provide a general result for our
estimator depending on $G$, which can be further calibrated to obtain
convergence rates for various specific problem setups. Surprisingly, our
estimator attains the optimal rate under certain graph fidelity condition on
$G$, as if we could aggregate all samples sharing the same distribution. If the
graph fidelity condition is not met, we propose an edge selection procedure via
multiple testing to ensure the optimality. To ease the burden of local
computation, a decentralized stochastic version of ADMM is provided, with
convergence rate $O(T^{-1}\log T)$ where $T$ denotes the number of iterations.
We highlight that, our algorithm transmits only parameters along edges of $G$
at each iteration, without requiring a central machine, which preserves
privacy. We further extend it to the case where devices are randomly
inaccessible during the training process, with a similar algorithmic
convergence guarantee. The computational and statistical efficiency of our
method is evidenced by simulation experiments and the 2020 US presidential
election data set.
- Abstract(参考訳): ローカルデータを共有せずに、複数の分散デバイスでアルゴリズムをトレーニングするフェデレーション学習は、分散機械学習プラクティスでますます人気を集めている。
通常、グラフ構造$G$は通信用のローカルデバイスの後ろに存在する。
本研究では,データ分散と通信の不均質性を伴うフェデレーション学習におけるパラメータ推定と,ローカルデバイスの計算能力の制限について検討する。
局所デバイス上の分布を異なる$p$次元ベクトルの集合でパラメータ化することにより分布の不均一性を符号化する。
次に,ラッソ正規化を融合した$m$-estimationフレームワークの下で,全デバイスのパラメータを共同で推定し,接続デバイス上でのパラメータを$g$で同等に見積もることを提案する。
我々は、様々な特定の問題設定に対する収束率を得るためにさらに校正できる$G$に依存する推定器の一般的な結果を提供する。
驚いたことに、我々の推定器は、同じ分布を共有する全てのサンプルを集約できるかのように、G$のグラフ忠実度条件の下で最適な速度を達成する。
グラフの忠実度条件が満たされない場合、最適性を確保するために複数のテストによるエッジ選択手順を提案する。
局所計算の負担を軽減するため、admmの分散確率バージョンが提供され、ここで$t$が反復数を表す収束レート$o(t^{-1}\log t)$が与えられる。
このアルゴリズムでは,プライバシを保存する中央マシンを必要とせず,各イテレーションでG$のエッジに沿ってのみパラメータを送信する。
さらに、トレーニングプロセス中にデバイスがランダムにアクセスできない場合にまで拡張し、同様のアルゴリズムによる収束を保証する。
本手法の計算と統計的効率はシミュレーション実験と2020年アメリカ合衆国大統領選挙のデータセットによって実証されている。
関連論文リスト
- A Unified Framework for Gradient-based Clustering of Distributed Data [51.904327888475606]
我々は,ユーザのネットワーク上で動作する分散クラスタリングアルゴリズムのファミリーを開発する。
DGC-$mathcalF_rho$は、K$-meansやHuber Losといった一般的なクラスタリング損失に特化している。
DGC-$mathcalF_rho$のコンセンサス固定点は、全データ上の勾配クラスタリングの固定点と等価であることを示す。
論文 参考訳(メタデータ) (2024-02-02T10:44:42Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean
Estimation [58.03500081540042]
プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。
すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
論文 参考訳(メタデータ) (2023-01-31T18:47:42Z) - Generalized Differentiable RANSAC [95.95627475224231]
$nabla$-RANSACは、ランダム化された堅牢な推定パイプライン全体を学ぶことができる、微分可能なRANSACである。
$nabla$-RANSACは、精度という点では最先端のシステムよりも優れているが、精度は低い。
論文 参考訳(メタデータ) (2022-12-26T15:13:13Z) - Federated Learning Using Variance Reduced Stochastic Gradient for
Probabilistically Activated Agents [0.0]
本稿では,各エージェントが各反復において任意の選択の確率を持つような最適解に対して,分散低減と高速収束率の両方を達成する2層構造を持つフェデレートラーニング(FL)のアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-25T22:04:49Z) - 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) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳(メタデータ) (2022-02-08T12:58:14Z) - High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees [20.701475313495884]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳(メタデータ) (2022-01-21T01:26:08Z) - FedLGA: Towards System-Heterogeneity of Federated Learning via Local
Gradient Approximation [21.63719641718363]
システム不均一なFL問題を定式化してFedLGAと呼ばれる新しいアルゴリズムを提案する。
複数のデータセットに対する総合的な実験の結果、FedLGAはシステム不均一性に対して現在のFLベンチマークよりも優れていた。
論文 参考訳(メタデータ) (2021-12-22T16:05:09Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳(メタデータ) (2020-10-02T10:41:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。