論文の概要: Switch and Conquer: Efficient Algorithms By Switching Stochastic
Gradient Oracles For Decentralized Saddle Point Problems
- arxiv url: http://arxiv.org/abs/2309.00997v2
- Date: Wed, 13 Sep 2023 16:07:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-14 17:13:47.420467
- Title: Switch and Conquer: Efficient Algorithms By Switching Stochastic
Gradient Oracles For Decentralized Saddle Point Problems
- Title（参考訳）: Switch and Conquer: 分散サドルポイント問題に対する確率的勾配Oracleの切り替えによる効率的なアルゴリズム
- Authors: Chhavi Sharma, Vishnu Narayanan and P. Balamurugan
- Abstract要約: そこで本研究では, 一次変数と双対変数の更新を可能にする非接触な原始的ハイブリッド勾配(非接触PDHG)法を開発した。
GSGとSVRGの最適収束位相を利用することで、C-DPSSGが低-ナトリウム精度の解を得るのに適していることを示す。
- 参考スコア（独自算出の注目度）: 1.2277343096128712
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a class of non-smooth strongly convex-strongly concave saddle
point problems in a decentralized setting without a central server. To solve a
consensus formulation of problems in this class, we develop an inexact primal
dual hybrid gradient (inexact PDHG) procedure that allows generic gradient
computation oracles to update the primal and dual variables. We first
investigate the performance of inexact PDHG with stochastic variance reduction
gradient (SVRG) oracle. Our numerical study uncovers a significant phenomenon
of initial conservative progress of iterates of IPDHG with SVRG oracle. To
tackle this, we develop a simple and effective switching idea, where a
generalized stochastic gradient (GSG) computation oracle is employed to hasten
the iterates' progress to a saddle point solution during the initial phase of
updates, followed by a switch to the SVRG oracle at an appropriate juncture.
The proposed algorithm is named Decentralized Proximal Switching Stochastic
Gradient method with Compression (C-DPSSG), and is proven to converge to an
$\epsilon$-accurate saddle point solution with linear rate. Apart from
delivering highly accurate solutions, our study reveals that utilizing the best
convergence phases of GSG and SVRG oracles makes C-DPSSG well suited for
obtaining solutions of low/medium accuracy faster, useful for certain
applications. Numerical experiments on two benchmark machine learning
applications show C-DPSSG's competitive performance which validate our
theoretical findings. The codes used in the experiments can be found
\href{https://github.com/chhavisharma123/C-DPSSG-CDC2023}{here}.
- Abstract（参考訳）: 中央サーバを使わずに分散した環境では,非スムースな強凸型サドルポイント問題を考える。
このクラスにおける問題のコンセンサスを定式化するために、一般の勾配計算オラクルが原始変数と双対変数を更新できる不正確な原始双対勾配(非コンパクトPDHG)法を開発した。
まず, 確率的分散減少勾配 (SVRG) を持つ不正確なPDHGの性能について検討した。
svrg oracle による ipdhg のイテレートの初期保存的進展の有意な現象を明らかにする。
これに対処するため、我々は、更新の初期段階においてイテレートの進捗をサドルポイントソリューションに早めるために、オラクルが適切な結束でsvrg oracleに切り替えるために、一般化された確率勾配(gsg)計算を用いる、シンプルで効果的なスイッチングアイデアを開発した。
提案アルゴリズムは,C-DPSSG(Decentralized Proximal Switching Stochastic Gradient Method with Compression)と名付けられ,線形レートで$\epsilon$-accurate saddle point Solutionに収束することが証明された。
高精度なソリューションの提供とは別に,GSG と SVRG のオーラクルの最適収束位相を利用することで,C-DPSSG が低・ナトリウム精度の解を得るのに適しており,特定の用途に有用であることを示す。
2つのベンチマーク機械学習アプリケーションの数値実験により、C-DPSSGの競合性能が示され、理論的結果が検証された。
実験で使用されたコードは \href{https://github.com/chhavisharma123/C-DPSSG-CDC2023}{here} で見ることができる。
関連論文リスト
- ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。
本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。
本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
論文 参考訳（メタデータ） (2023-12-04T19:00:07Z) - DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over
Graphs [54.08445874064361]
本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。
Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。
提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
論文 参考訳（メタデータ） (2022-08-29T18:01:42Z) - On the Convergence to a Global Solution of Shuffling-Type Gradient
Algorithms [18.663264755108703]
勾配降下アルゴリズム (SGD) は、多くの機械学習タスクにおいて選択の方法である。
本稿では,SGDが凸設定として望まれる計算一般複雑性を達成したことを示す。
論文 参考訳（メタデータ） (2022-06-13T01:25:59Z) - Decentralized Stochastic Proximal Gradient Descent with Variance
Reduction over Time-varying Networks [30.231314171218994]
分散学習において、ノードのネットワークは、通常、その局所的な目的の有限サムである全体的な目的関数を最小化するために協力する。
そこで本研究では,分散縮小手法を利用して分散学習を高速化する新しいアルゴリズムDPSVRGを提案する。
論文 参考訳（メタデータ） (2021-12-20T08:23:36Z) - COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic
Convex Optimization [4.970364068620608]
我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。
問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。
また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
論文 参考訳（メタデータ） (2021-09-07T17:21:09Z) - 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) - Escaping Saddle Points with Stochastically Controlled Stochastic
Gradient Methods [12.173568611144626]
騒音やステップによって1次サドル勾配降下法(SCSG)が摂動可能であることを示す。
この問題を解決するために、別のステップが提案される。
提案手法は,サドル点に対するCNC-SCSGD法をさらに取り入れることを目的としている。
論文 参考訳（メタデータ） (2021-03-07T18:09:43Z) - A Retrospective Approximation Approach for Smooth Stochastic
Optimization [0.2867517731896504]
グラディエント(グラディエント、英: Gradient、SG)とは、最適化(SO)問題をスムーズ(ノンフィクション)な目標値で解くための補足的反復手法である。
論文 参考訳（メタデータ） (2021-03-07T16:29:36Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Detached Error Feedback for Distributed SGD with Random Sparsification [98.98236187442258]
コミュニケーションのボトルネックは、大規模なディープラーニングにおいて重要な問題である。
非効率な分散問題に対する誤りフィードバックよりも優れた収束性を示す分散誤差フィードバック(DEF)アルゴリズムを提案する。
また、DEFよりも優れた境界を示すDEFの一般化を加速するDEFAを提案する。
論文 参考訳（メタデータ） (2020-04-11T03:50:59Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。