論文の概要: Stochastic Gradient Methods with Compressed Communication for
Decentralized Saddle Point Problems
- arxiv url: http://arxiv.org/abs/2205.14452v1
- Date: Sat, 28 May 2022 15:17:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 18:41:08.051564
- Title: Stochastic Gradient Methods with Compressed Communication for
Decentralized Saddle Point Problems
- Title（参考訳）: 分散saddle point問題に対する圧縮通信を用いた確率的勾配法
- Authors: Chhavi Sharma, Vishnu Narayanan, P. Balamurugan
- Abstract要約: 分散環境でのサドルポイント問題のクラスを(中央サーバなしで)解くための2つのアルゴリズムを提案する。
まず、圧縮(C-DPSVRG)による分散近位変動低減勾配を示す。
次に,有限和設定のための圧縮(C-DPSVRG)を用いた分散型近距離低減勾配を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose two stochastic gradient algorithms to solve a class of
saddle-point problems in a decentralized setting (without a central server).
The proposed algorithms are the first to achieve sub-linear/linear computation
and communication complexities using respectively stochastic
gradient/stochastic variance reduced gradient oracles with compressed
information exchange to solve non-smooth strongly-convex strongly-concave
saddle-point problems in decentralized setting. Our first algorithm is a
Restart-based Decentralized Proximal Stochastic Gradient method with
Compression (C-RDPSG) for general stochastic settings. We provide rigorous
theoretical guarantees of C-RDPSG with gradient computation complexity and
communication complexity of order $\mathcal{O}( (1+\delta)^4
\frac{1}{L^2}{\kappa_f^2}\kappa_g^2 \frac{1}{\epsilon} )$, to achieve an
$\epsilon$-accurate saddle-point solution, where $\delta$ denotes the
compression factor, $\kappa_f$ and $\kappa_g$ denote respectively the condition
numbers of objective function and communication graph, and $L$ denotes the
smoothness parameter of the smooth part of the objective function. Next, we
present a Decentralized Proximal Stochastic Variance Reduced Gradient algorithm
with Compression (C-DPSVRG) for finite sum setting which exhibits gradient
computation complexity and communication complexity of order
$\mathcal{O}((1+\delta)\kappa_f^2 \kappa_g \log(\frac{1}{\epsilon}))$.
Extensive numerical experiments show competitive performance of the proposed
algorithms and provide support to the theoretical results obtained.
- Abstract（参考訳）: 本稿では,分散化環境でのサドル点問題のクラスを(中央サーバなしで)解くための2つの確率勾配アルゴリズムを提案する。
提案アルゴリズムは, 圧縮情報交換を用いた確率勾配/確率分散縮小勾配オークルを用いて, 線形・線形・通信の計算・通信複雑性を初めて達成し, 分散環境での非平滑な強凸サドル点問題の解法である。
最初のアルゴリズムは、一般的な確率的設定のための圧縮(C-RDPSG)を用いたRestartベースの分散確率勾配法である。
We provide rigorous theoretical guarantees of C-RDPSG with gradient computation complexity and communication complexity of order $\mathcal{O}( (1+\delta)^4 \frac{1}{L^2}{\kappa_f^2}\kappa_g^2 \frac{1}{\epsilon} )$, to achieve an $\epsilon$-accurate saddle-point solution, where $\delta$ denotes the compression factor, $\kappa_f$ and $\kappa_g$ denote respectively the condition numbers of objective function and communication graph, and $L$ denotes the smoothness parameter of the smooth part of the objective function.
次に、次数$\mathcal{O}((1+\delta)\kappa_f^2 \kappa_g \log(\frac{1}{\epsilon})$の勾配計算複雑性と通信複雑性を示す有限和設定に対して、圧縮(C-DPSVRG)を用いた分散確率確率分散勾配アルゴリズムを提案する。
大規模な数値実験により,提案アルゴリズムの競合性能が示され,理論結果への支持が得られた。
関連論文リスト
- Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
本稿では,通信制限条件下で分散最適化問題を解くことを検討する。
CEDASと呼ばれる圧縮精密拡散法について述べる。
特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
論文 参考訳（メタデータ） (2023-01-14T09:49:15Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
Decentralized Recursive Dec. Method (DREAM)
具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。
我々の数値実験は,従来の手法の優越性を検証した。
論文 参考訳（メタデータ） (2022-12-05T16:09:39Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample
Complexity [25.775517797956237]
本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。
我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2022-02-01T07:27:34Z) - Escaping Saddle Points with Compressed SGD [8.014396597444296]
勾配降下(SGD)は大規模分散機械学習の最適化手法である。
勾配圧縮によるSGD拡張は$varepsilon$1次定常点に収束することを示す。
勾配がリプシッツでないとき、RandomK圧縮機を持つSGDは、SGDと同じ数の反復数を持つ$varepsilon$-SOSPに収束する。
論文 参考訳（メタデータ） (2021-05-21T01:56:43Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Fast decentralized non-convex finite-sum optimization with recursive
variance reduction [19.540926205375857]
本稿では,SARAH型分散低減技術を用いたGT-SARAHと呼ばれる一階勾配法について述べる。
特に、$n = O(Nfrac12(lambda)3)$のようなビッグデータでは、ネットワークの複雑さとは無関係に、この複雑さは$O(Nfrac12Lepsilon-2)$に減少する。
さらに、局所的なミニバッチサイズの適切な選択は、勾配複雑性と通信複雑性のトレードオフをバランスさせる。
論文 参考訳（メタデータ） (2020-08-17T15:51:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。