論文の概要: CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence
- arxiv url: http://arxiv.org/abs/2301.05872v3
- Date: Sun, 29 Sep 2024 03:04:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-01 21:57:55.951558
- Title: CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence
- Title(参考訳): CEDAS: 収束性を改善した圧縮分散確率勾配法
- Authors: Kun Huang, Shi Pu,
- Abstract要約: 本稿では,通信制限条件下で分散最適化問題を解くことを検討する。
CEDASと呼ばれる圧縮精密拡散法について述べる。
特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
- 参考スコア(独自算出の注目度): 9.11726703830074
- License:
- Abstract: In this paper, we consider solving the distributed optimization problem over a multi-agent network under the communication restricted setting. We study a compressed decentralized stochastic gradient method, termed ``compressed exact diffusion with adaptive stepsizes (CEDAS)", and show the method asymptotically achieves comparable convergence rate as centralized { stochastic gradient descent (SGD)} for both smooth strongly convex objective functions and smooth nonconvex objective functions under unbiased compression operators. In particular, to our knowledge, CEDAS enjoys so far the shortest transient time (with respect to the graph specifics) for achieving the convergence rate of centralized SGD, which behaves as $\mathcal{O}(n{C^3}/(1-\lambda_2)^{2})$ under smooth strongly convex objective functions, and $\mathcal{O}(n^3{C^6}/(1-\lambda_2)^4)$ under smooth nonconvex objective functions, where $(1-\lambda_2)$ denotes the spectral gap of the mixing matrix, and $C>0$ is the compression-related parameter. In particular, CEDAS exhibits the shortest transient times when $C < \mathcal{O}(1/(1 - \lambda_2)^2)$, which is common in practice. Numerical experiments further demonstrate the effectiveness of the proposed algorithm.
- Abstract(参考訳): 本稿では,通信制限条件下でのマルチエージェントネットワーク上での分散最適化問題について考察する。
本研究では,非バイアス圧縮演算子の下での滑らかな強凸対象関数と滑らかな非凸対象関数の両方に対して,非圧縮的収束率を集中的 {確率勾配勾配勾配 (SGD) として漸近的に達成する圧縮分散確率勾配法について検討する。
特に、我々の知る限り、CEDAS は(グラフ特異性に関して)最も短い過渡時間(英語版)で、中央集権 SGD の収束率(英語版)($\mathcal{O}(n{C^3}/(1-\lambda_2)^{2})$ 滑らかな強凸対象関数、$\mathcal{O}(n^3{C^6}/(1-\lambda_2)^4)$ 滑らかな非凸対象関数、$(1-\lambda_2)$ 混合行列のスペクトルギャップを表す。
特に、CEDASは、実際に一般的な$C < \mathcal{O}(1/(1 - \lambda_2)^2)$が最短の過渡時間を示す。
数値実験により,提案アルゴリズムの有効性がさらに示された。
関連論文リスト
- Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
パラメータ・サーバ・フレームワークにおける圧縮勾配通信を用いた分散勾配降下(SGD)のための新しいアルゴリズムを提案する。
平坦な1ビット勾配勾配勾配法(FO-SGD)は2つの単純なアルゴリズムの考え方に依存している。
論文 参考訳(メタデータ) (2024-05-17T21:17:27Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳(メタデータ) (2023-11-07T17:39:17Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳(メタデータ) (2023-05-30T17:47:27Z) - Zero-Order One-Point Estimate with Distributed Stochastic
Gradient-Tracking Technique [23.63073074337495]
本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。
分散勾配追跡法を,勾配推定のない帯域設定に拡張する。
近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
論文 参考訳(メタデータ) (2022-10-11T17:04:45Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳(メタデータ) (2022-09-12T06:53:24Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文 参考訳(メタデータ) (2022-03-29T17:59:10Z) - Improving the Transient Times for Distributed Stochastic Gradient
Methods [5.215491794707911]
拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。
EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。
我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
論文 参考訳(メタデータ) (2021-05-11T08:09:31Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳(メタデータ) (2021-02-19T12:22:56Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳(メタデータ) (2020-05-15T21:14:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。