論文の概要: A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization

• arxiv url: http://arxiv.org/abs/2006.07013v1
• Date: Fri, 12 Jun 2020 08:58:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 03:34:54.133651
• Title: A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization
• Title（参考訳）: 非凸フェデレーション最適化のための確率勾配法の統一解析
• Authors: Zhize Li, Peter Richt\'arik
• Abstract要約: 非非状態におけるSGD不変量を満たすすべての方法について単一の解析を行う。 また、PL条件下での非非状態におけるより高速な線形収束を得るための統一解析も提供する。
• 参考スコア（独自算出の注目度）: 16.714109768541785
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the performance of a large family of SGD variants in the smooth nonconvex regime. To this end, we propose a generic and flexible assumption capable of accurate modeling of the second moment of the stochastic gradient. Our assumption is satisfied by a large number of specific variants of SGD in the literature, including SGD with arbitrary sampling, SGD with compressed gradients, and a wide variety of variance-reduced SGD methods such as SVRG and SAGA. We provide a single convergence analysis for all methods that satisfy the proposed unified assumption, thereby offering a unified understanding of SGD variants in the nonconvex regime instead of relying on dedicated analyses of each variant. Moreover, our unified analysis is accurate enough to recover or improve upon the best-known convergence results of several classical methods, and also gives new convergence results for many new methods which arise as special cases. In the more general distributed/federated nonconvex optimization setup, we propose two new general algorithmic frameworks differing in whether direct gradient compression (DC) or compression of gradient differences (DIANA) is used. We show that all methods captured by these two frameworks also satisfy our unified assumption. Thus, our unified convergence analysis also captures a large variety of distributed methods utilizing compressed communication. Finally, we also provide a unified analysis for obtaining faster linear convergence rates in this nonconvex regime under the PL condition.
• Abstract（参考訳）: 本稿では,スムーズな非凸状態におけるSGD変種群の性能について検討する。 そこで本研究では,確率勾配の第2モーメントを正確にモデル化できる汎用的で柔軟な仮定を提案する。 我々の仮定は、任意のサンプリングのSGD、圧縮勾配のSGD、SVRGやSAGAのような様々な分散還元SGD法など、文学におけるSGDの多くの特定の変種によって満たされる。 提案する統一仮定を満たした全手法に対して単一収束解析を行い,各変数の専用解析に頼らずに非凸系におけるsgd変種を統一的に理解する。 さらに, 統一解析は, いくつかの古典的手法の最もよく知られた収束結果の復元や改善に十分正確であり, 特殊事例として生じる多くの新しい手法に対して新たな収束結果を与える。 より一般的な分散/フェデレート非凸最適化設定では,直接勾配圧縮 (dc) と勾配差圧縮 (diana) のいずれを使用するかで異なる2つの汎用アルゴリズムフレームワークを提案する。 これら2つのフレームワークによってキャプチャされたすべてのメソッドもまた、我々の統一された仮定を満たすことを示す。 そこで,本研究では,圧縮通信を利用した分散手法の多種多様な解析を行った。 最後に、PL条件下でのこの非凸状態におけるより高速な線形収束率を得るための統一解析も提供する。

関連論文リスト

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• A Unified Convergence Theorem for Stochastic Optimization Methods [4.94128206910124]
  一連の統一最適化手法に対する収束結果の導出に使用される基本的な統一収束定理を提供する。 直接応用として、一般的な設定下での収束結果をほぼ確実に回復する。
  論文  参考訳（メタデータ） (2022-06-08T14:01:42Z)
• Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods [73.35353358543507]
  SGDA(Gradient Descent-Ascent)は、min-max最適化と変分不等式問題(VIP)を解くための最も顕著なアルゴリズムの1つである。 本稿では,多種多様な降下指数法を網羅した統合収束解析を提案する。 本研究では,新しい分散化手法 (L-SVRGDA) や,新しい分散圧縮方式 (QSGDA, DIANA-SGDA, VR-DIANA-SGDA) ,座標ランダム化方式 (SEGA-SGDA) など,SGDAの新しい変種を開発した。
  論文  参考訳（メタデータ） (2022-02-15T09:17:39Z)
• Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations [83.3201889218775]
  広く使われている1次サドル点最適化法は、帰納的導出時に同一の連続時間常微分方程式(ODE)を導出する。 しかし、これらの方法の収束特性は、単純な双線型ゲームでさえ質的に異なる。 いくつかのサドル点最適化法のための微分方程式モデルの設計に流体力学の研究フレームワークを採用する。
  論文  参考訳（メタデータ） (2021-12-27T18:31:34Z)
• Stochastic Extragradient: General Analysis and Improved Rates [23.29653334470774]
  Extragradient (SEG) 法は、min-max最適化と変分不等式問題を解くための最も一般的なアルゴリズムの1つである。 我々は,SEGのいくつかの変種を統一的に解析できる新しい理論フレームワークを開発した。 新たなSEG変種に対する我々のレートは、現在の最先端収束保証よりも優れており、制約の少ない仮定に依存している。
  論文  参考訳（メタデータ） (2021-11-16T16:49:31Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)
• 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)
• Linearly Converging Error Compensated SGD [11.436753102510647]
  本稿では、任意の圧縮と遅延更新を伴う分散SGDの変種を統一的に解析する。 我々のフレームワークは、量子化されたSGD、ErrorCompensated SGD、SGDの様々な変種をカバーするのに十分である。 我々は、分散還元や任意のサンプリングと誤りフィードバックと量子化を組み合わせたSGDの新しい変種を開発する。
  論文  参考訳（メタデータ） (2020-10-23T10:46:31Z)
• Sampling and Update Frequencies in Proximal Variance-Reduced Stochastic Gradient Methods [0.0]
  本稿では, 一般近似分散還元勾配法を提案し, 強い凸性仮定の下で解析する。 このアルゴリズムの特別な例は、SAGA、L-SVRGとその近位変種である。
  論文  参考訳（メタデータ） (2020-02-13T14:56:05Z)

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

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