論文の概要: A New Theoretical Perspective on Data Heterogeneity in Federated Optimization
- arxiv url: http://arxiv.org/abs/2407.15567v1
- Date: Mon, 22 Jul 2024 11:52:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-23 15:11:26.810184
- Title: A New Theoretical Perspective on Data Heterogeneity in Federated Optimization
- Title(参考訳): フェデレート最適化におけるデータ不均一性に関する新しい理論的展望
- Authors: Jiayi Wang, Shiqiang Wang, Rong-Rong Chen, Mingyue Ji,
- Abstract要約: 連邦学習(FL)において、データ不均一性は、既存の理論解析が収束率について悲観的である主な理由である。
特に多くのFLアルゴリズムでは、局所的な更新数が大きくなると収束率が劇的に増加する。
本稿では,理論的理解と実践的パフォーマンスのギャップを,新たな視点からの理論的分析を提供することによって埋めることを目的とする。
- 参考スコア(独自算出の注目度): 39.75009345804017
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In federated learning (FL), data heterogeneity is the main reason that existing theoretical analyses are pessimistic about the convergence rate. In particular, for many FL algorithms, the convergence rate grows dramatically when the number of local updates becomes large, especially when the product of the gradient divergence and local Lipschitz constant is large. However, empirical studies can show that more local updates can improve the convergence rate even when these two parameters are large, which is inconsistent with the theoretical findings. This paper aims to bridge this gap between theoretical understanding and practical performance by providing a theoretical analysis from a new perspective on data heterogeneity. In particular, we propose a new and weaker assumption compared to the local Lipschitz gradient assumption, named the heterogeneity-driven pseudo-Lipschitz assumption. We show that this and the gradient divergence assumptions can jointly characterize the effect of data heterogeneity. By deriving a convergence upper bound for FedAvg and its extensions, we show that, compared to the existing works, local Lipschitz constant is replaced by the much smaller heterogeneity-driven pseudo-Lipschitz constant and the corresponding convergence upper bound can be significantly reduced for the same number of local updates, although its order stays the same. In addition, when the local objective function is quadratic, more insights on the impact of data heterogeneity can be obtained using the heterogeneity-driven pseudo-Lipschitz constant. For example, we can identify a region where FedAvg can outperform mini-batch SGD even when the gradient divergence can be arbitrarily large. Our findings are validated using experiments.
- Abstract(参考訳): 連邦学習(FL)において、データ不均一性は、既存の理論解析が収束率について悲観的である主な理由である。
特に多くのFLアルゴリズムでは、局所的な更新数が大きくなると収束率が劇的に増加し、特に勾配の発散と局所リプシッツ定数の積が大きくなる。
しかし、実験的な研究により、これらの2つのパラメータが大きい場合でも、より局所的な更新が収束率を向上させることが示され、これは理論的な結果とは矛盾する。
本稿では,データ不均一性の新しい視点から理論的解析を行うことにより,理論的理解と実践的パフォーマンスのギャップを埋めることを目的とする。
特に、局所リプシッツ勾配仮定と比較して新しい弱い仮定を提案し、不均一性駆動擬似リプシッツ仮定と名付けた。
これと勾配の発散仮定は、データの不均一性の影響を共同で特徴づけることができることを示す。
FedAvg とその拡張の収束上界を導出することにより、既存の研究と比較すると、局所リプシッツ定数はより小さい不均一性駆動擬リプシッツ定数に置き換えられ、対応する収束上界は、同じ局所更新数に対して著しく減少するが、その順序は同じであることを示す。
さらに、局所目的関数が二次関数である場合には、不均一性駆動擬リプシッツ定数を用いて、データの不均一性の影響に関するより多くの洞察を得ることができる。
例えば、勾配の偏差が任意に大きい場合でも、FedAvgがミニバッチSGDより優れている領域を特定できる。
実験により得られた知見を検証した。
関連論文リスト
- Generalization error of min-norm interpolators in transfer learning [2.7309692684728617]
最小ノルム補間器は、現代の機械学習アルゴリズムの暗黙の正規化限界として自然に現れる。
多くのアプリケーションでは、トレーニング中に限られた量のテストデータが利用できるが、この設定におけるmin-normの特性は十分に理解されていない。
我々はこれらの特徴を達成するために、新しい異方性局所法を確立した。
論文 参考訳(メタデータ) (2024-06-20T02:23:28Z) - Nonparametric logistic regression with deep learning [1.2509746979383698]
非パラメトリックロジスティック回帰では、クルバック・リーバーの発散は容易に発散できる。
余剰リスクを解析する代わりに、最大可能性推定器の一貫性を示すのに十分である。
重要な応用として、深層ニューラルネットワークによるNPMLEの収束率を導出する。
論文 参考訳(メタデータ) (2024-01-23T04:31:49Z) - Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
既存の一般化境界は、現代のニューラルネットワークの一般化を促進する重要な要因を説明することができない。
データ空間における学習予測関数の局所リプシッツ正則性に依存するインスタンス依存の一般化境界を導出する。
ニューラルネットワークに対する一般化境界を実験的に解析し、有界値が有意義であることを示し、トレーニング中の一般的な正規化方法の効果を捉える。
論文 参考訳(メタデータ) (2022-11-02T16:39:42Z) - On the Unreasonable Effectiveness of Federated Averaging with
Heterogeneous Data [39.600069116159695]
既存の理論では、フェデレーション学習におけるフェデレーション平均化(FedAvg)アルゴリズムの性能は、データの不均一性が低下すると予想している。
本稿では,従来の理論的予測と矛盾するFedAvgの有効性について述べる。
論文 参考訳(メタデータ) (2022-06-09T18:25:25Z) - Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
正規化フローの微分同相性に基づいて、閉領域上の累積分布関数(CDF)を推定する。
一般的なフローアーキテクチャとUCIデータセットに関する実験は,従来の推定器と比較して,サンプル効率が著しく向上したことを示している。
論文 参考訳(メタデータ) (2022-02-23T06:11:49Z) - Localisation in quasiperiodic chains: a theory based on convergence of
local propagators [68.8204255655161]
局所プロパゲータの収束に基づく準周期鎖に最も近いホッピングを持つ局所化の理論を提示する。
これらの連続分数の収束、局所化、あるいはその欠如を分析することは可能であり、それによって臨界点とモビリティエッジが帰結する。
結果は、振る舞いの範囲をカバーする3つの準周期モデルの理論を分析することで実証される。
論文 参考訳(メタデータ) (2021-02-18T16:19:52Z) - Binary Classification of Gaussian Mixtures: Abundance of Support
Vectors, Benign Overfitting and Regularization [39.35822033674126]
生成ガウス混合モデルに基づく二項線形分類について検討する。
後者の分類誤差に関する新しい非漸近境界を導出する。
この結果は, 確率が一定である雑音モデルに拡張される。
論文 参考訳(メタデータ) (2020-11-18T07:59:55Z) - Reducing the Variance of Variational Estimates of Mutual Information by
Limiting the Critic's Hypothesis Space to RKHS [0.0]
相互情報(英: Mutual Information、MI)は、2つの確率変数間の依存性に関する情報理論の尺度である。
近年の手法では、未知密度比を近似するニューラルネットワークとしてパラメトリック確率分布や批判が実現されている。
我々は、高分散特性は、批評家の仮説空間の制御不能な複雑さに起因すると論じる。
論文 参考訳(メタデータ) (2020-11-17T14:32:48Z) - On Localized Discrepancy for Domain Adaptation [146.4580736832752]
本稿では,局所化後の仮説空間上で定義される局所的不一致について検討する。
2つの領域を交換すると、それらの値が異なるため、非対称な移動困難が明らかになる。
論文 参考訳(メタデータ) (2020-08-14T08:30:02Z) - Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。
平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。
任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
論文 参考訳(メタデータ) (2020-06-16T20:53:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。