論文の概要: Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective

• arxiv url: http://arxiv.org/abs/2111.03741v1
• Date: Fri, 5 Nov 2021 22:16:11 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-09 14:53:37.594271
• Title: Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Title（参考訳）: フェデレーション平均化のためのシャープ境界(ローカルSGD)と連続的展望
• Authors: Margalit Glasgow, Honglin Yuan, Tengyu Ma
• Abstract要約: Federated AveragingFedAvg(ローカルSGD)は、Federated Learning(FL)で最も人気のあるアルゴリズムの1つである。 微分方程式(SDE)の観点から、この量を解析する方法を示す。
• 参考スコア（独自算出の注目度）: 49.17352150219212
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Federated Averaging (FedAvg), also known as Local SGD, is one of the most popular algorithms in Federated Learning (FL). Despite its simplicity and popularity, the convergence rate of FedAvg has thus far been undetermined. Even under the simplest assumptions (convex, smooth, homogeneous, and bounded covariance), the best-known upper and lower bounds do not match, and it is not clear whether the existing analysis captures the capacity of the algorithm. In this work, we first resolve this question by providing a lower bound for FedAvg that matches the existing upper bound, which shows the existing FedAvg upper bound analysis is not improvable. Additionally, we establish a lower bound in a heterogeneous setting that nearly matches the existing upper bound. While our lower bounds show the limitations of FedAvg, under an additional assumption of third-order smoothness, we prove more optimistic state-of-the-art convergence results in both convex and non-convex settings. Our analysis stems from a notion we call iterate bias, which is defined by the deviation of the expectation of the SGD trajectory from the noiseless gradient descent trajectory with the same initialization. We prove novel sharp bounds on this quantity, and show intuitively how to analyze this quantity from a Stochastic Differential Equation (SDE) perspective.
• Abstract（参考訳）: フェデレート平均化(Federated Averaging、FedAvg、ローカルSGD)は、フェデレート学習(Federated Learning、FL)において最も人気のあるアルゴリズムの一つである。 その単純さと人気にもかかわらず、FedAvgの収束率は決定されていない。 最も単純な仮定(凸、滑らか、均一、有界共分散)の下でも、最もよく知られた上界と下界は一致せず、既存の解析がアルゴリズムの容量を捉えるかどうかは不明である。 本稿では,既存のFedAvg上界解析が即効的でないことを示す,既存の上限値と一致したFedAvgの下界を提供することで,この問題を最初に解決する。 さらに,既存の上界とほぼ一致する不均質な設定において下界を確立する。 下限はFedAvgの限界を示すが、3階の滑らかさを仮定すると、凸面と非凸面の両方でより楽観的な収束結果が証明される。 我々の分析は反復バイアス (iterate bias) と呼ばれる概念に起因しており、これは同じ初期化を持つ無騒音勾配降下軌道からsgd軌道の期待値の偏差によって定義される。 この量に対する新しい鋭い境界を証明し、確率微分方程式(sde)の観点から直感的にその量を分析する方法を示す。

関連論文リスト

• A Unified Analysis for Finite Weight Averaging [50.75116992029417]
  Gradient Descent(SGD)の平均イテレーションは、SWA(Weight Averaging)、EMA(Exponential moving Average)、LAWA(Latest Weight Averaging)といったディープラーニングモデルのトレーニングにおいて、経験的な成功を収めている。 本稿では、LAWAを有限重み平均化(FWA)として一般化し、最適化と一般化の観点からSGDと比較して、それらの利点を説明する。
  論文  参考訳（メタデータ） (2024-11-20T10:08:22Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• A Convergence Theory for Federated Average: Beyond Smoothness [28.074273047592065]
  フェデレートラーニングにより、大量のエッジコンピューティングデバイスが、データ共有を併用せずにモデルを学習できるようになる。 この設定における主要なアルゴリズムとして、ローカルデバイス上でGradient Descent(SGD)を並列に実行するFederated Average FedAvgが広く使用されている。 本稿では,フェデレートラーニングに関する理論的収束研究について述べる。
  論文  参考訳（メタデータ） (2022-11-03T04:50:49Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization [1.6973426830397942]
  平滑な非有限和最適化における高階法の下限を証明する。 pth-order regularized method は有限和の目的から利益を得ることができないことを示す。 新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
  論文  参考訳（メタデータ） (2021-03-08T23:33:58Z)
• Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance [0.0]
  本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。 この回避は、非自明な常微分方程式のノイズ離散化として研究される。
  論文  参考訳（メタデータ） (2020-12-07T19:14:49Z)
• Convergence of Gradient Algorithms for Nonconvex $C^{1+\alpha}$ Cost Functions [2.538209532048867]
  勾配が収束する副生成物を示し、収束率に明示的な上限を与える。 これにより、ドオブマルティンの超ガレ収束定理によるほぼ確実な収束を証明できる。
  論文  参考訳（メタデータ） (2020-12-01T16:48:59Z)
• 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)

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

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