論文の概要: Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps

• arxiv url: http://arxiv.org/abs/2407.02689v2
• Date: Sun, 11 Aug 2024 05:10:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-13 20:53:08.492793
• Title: Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps
• Title（参考訳）: 分散最適化の高速化: ローカルステップの2次元的パースペクティブ
• Authors: Junchi Yang, Murat Yildirim, Qiu Feng,
• Abstract要約: 分散機械学習では、異なるデータを持つ複数のエージェントにまたがる線形変数が大きな課題となる。 本稿では,原変数上のラグランジアン収束を実現するフレームワークは,エージェント間通信を必要としないことを示す。
• 参考スコア（独自算出の注目度）: 4.471962177124311
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In distributed machine learning, efficient training across multiple agents with different data distributions poses significant challenges. Even with a centralized coordinator, current algorithms that achieve optimal communication complexity typically require either large minibatches or compromise on gradient complexity. In this work, we tackle both centralized and decentralized settings across strongly convex, convex, and nonconvex objectives. We first demonstrate that a basic primal-dual method, (Accelerated) Gradient Ascent Multiple Stochastic Gradient Descent (GA-MSGD), applied to the Lagrangian of distributed optimization inherently incorporates local updates, because the inner loops of running Stochastic Gradient Descent on the primal variable require no inter-agent communication. Notably, for strongly convex objectives, (Accelerated) GA-MSGD achieves linear convergence in communication rounds despite the Lagrangian being only linear in the dual variables. This is due to a structural property where the dual variable is confined to the span of the coupling matrix, rendering the dual problem strongly concave. When integrated with the Catalyst framework, our approach achieves nearly optimal communication complexity across various settings without the need for minibatches.
• Abstract（参考訳）: 分散機械学習では、異なるデータ分散を持つ複数のエージェント間の効率的なトレーニングが大きな課題となる。 集中コーディネータでさえ、最適な通信複雑性を達成する現在のアルゴリズムは、通常、大きなミニバッチまたは勾配複雑性の妥協を必要とする。 本研究では,強い凸,凸,非凸の目的にまたがる集中的および分散的設定に取り組む。 まず、分散最適化のラグランジアンに応用された基本原始双対法((Accelerated) Gradient Ascent Multiple Stochastic Gradient Descent (GA-MSGD))が局所的な更新を本質的に含んでいることを実証した。 特に、(加速された) GA-MSGD は、ラグランジアンが双対変数でのみ線型であるにもかかわらず、通信ラウンドにおける線形収束を達成する。 これは双対変数がカップリング行列のスパンに制限される構造的性質のためであり、双対問題は強く凹む。 Catalystフレームワークと統合すると,ミニバッチを必要とせずに,様々な設定でほぼ最適な通信複雑性を実現することができる。

関連論文リスト

• A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization [16.020878731214083]
  本稿では,分散バイレベル最適化のための完全一階分散手法である$textC2$DFBを提案する。 $textC2$DFBは計算効率と通信効率の両方です。
  論文  参考訳（メタデータ） (2024-10-18T02:00:45Z)
• Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems [39.197569803430646]
  最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。 近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
  論文  参考訳（メタデータ） (2023-04-21T11:38:41Z)
• DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization [27.317118892531827]
  我々は、DIAMOND(運動量と勾配追跡を伴う分散単時間スケール近似)と呼ばれる新しい分散二段階最適化を開発する。 我々はDIAMONDが$mathcalO(epsilon-3/2)$をサンプルと通信の複雑さで楽しむことを示し、$epsilon$-stationaryソリューションを実現する。
  論文  参考訳（メタデータ） (2022-12-05T15:58:00Z)
• A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints [7.028225540638832]
  直交制約付き分散最適化のための新しいアルゴリズムを提案する。 VRSGTは、サンプリングと通信の複雑さを同時に低減する直交制約付き分散最適化のための最初のアルゴリズムである。 数値実験では、VRGTSは現実の自律的なサンプルにおいて有望な性能を持つ。
  論文  参考訳（メタデータ） (2022-08-29T14:46:44Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  ローカル手法は通信時間を短縮する有望なアプローチの1つである。 局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-12T15:12:17Z)
• Semi-supervised Domain Adaptive Structure Learning [72.01544419893628]
  半教師付きドメイン適応 (SSDA) は,1) アノテーションの低いデータに過度に適合する手法と,2) ドメイン間の分散シフトの両方を克服しなければならない課題である。 SSLとDAの協調を正規化するための適応型構造学習手法を提案する。
  論文  参考訳（メタデータ） (2021-12-12T06:11:16Z)
• Cogradient Descent for Dependable Learning [64.02052988844301]
  双線形最適化問題に対処するために,CoGDアルゴリズムに基づく信頼度の高い学習法を提案する。 CoGDは、ある変数がスパーシティ制約を持つ場合の双線形問題を解くために導入された。 また、特徴と重みの関連を分解するためにも使用できるため、畳み込みニューラルネットワーク(CNN)をより良く訓練するための我々の手法をさらに一般化することができる。
  論文  参考訳（メタデータ） (2021-06-20T04:28:20Z)
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax Problems [80.46370778277186]
  大規模凸凹型ミニマックス問題は、ゲーム理論、堅牢なトレーニング、生成的敵ネットワークのトレーニングなど、多くの応用で発生する。 通信効率のよい分散外グレードアルゴリズムであるLocalAdaSientを開発した。 サーバモデル。 等質な環境と異質な環境の両方において,その有効性を実証する。
  論文  参考訳（メタデータ） (2021-06-18T09:42:05Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates [70.9701218475002]
  分散通信方式の統一収束解析を導入する。 いくつかの応用に対して普遍収束率を導出する。 私たちの証明は弱い仮定に依存している。
  論文  参考訳（メタデータ） (2020-03-23T17:49:15Z)

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

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