論文の概要: Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems

• arxiv url: http://arxiv.org/abs/2307.07113v1
• Date: Fri, 14 Jul 2023 01:32:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-17 15:13:29.973585
• Title: Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems
• Title（参考訳）: 分散還元法による分散確率的二重正規化非凸強凸ミニマックス問題の解法
• Authors: Gabriel Mancino-Ball and Yangyang Xu
• Abstract要約: 我々は、ピアツーピア通信により、$m$のコンピューティングエージェントのネットワークが協調すると考えている。 我々のアルゴリズムフレームワークは、二変数のコンセンサス制約を取り除くために、アグラジアン乗算器を導入している。 我々の知る限りでは、これはNCSCミニマックス問題に対する収束保証を、原始変数と双対変数の両方に適用する一般の非正規化器で提供する最初の研究である。
• 参考スコア（独自算出の注目度）: 7.5573375809946395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the decentralized, stochastic nonconvex strongly-concave (NCSC) minimax problem with nonsmooth regularization terms on both primal and dual variables, wherein a network of $m$ computing agents collaborate via peer-to-peer communications. We consider when the coupling function is in expectation or finite-sum form and the double regularizers are convex functions, applied separately to the primal and dual variables. Our algorithmic framework introduces a Lagrangian multiplier to eliminate the consensus constraint on the dual variable. Coupling this with variance-reduction (VR) techniques, our proposed method, entitled VRLM, by a single neighbor communication per iteration, is able to achieve an $\mathcal{O}(\kappa^3\varepsilon^{-3})$ sample complexity under the general stochastic setting, with either a big-batch or small-batch VR option, where $\kappa$ is the condition number of the problem and $\varepsilon$ is the desired solution accuracy. With a big-batch VR, we can additionally achieve $\mathcal{O}(\kappa^2\varepsilon^{-2})$ communication complexity. Under the special finite-sum setting, our method with a big-batch VR can achieve an $\mathcal{O}(n + \sqrt{n} \kappa^2\varepsilon^{-2})$ sample complexity and $\mathcal{O}(\kappa^2\varepsilon^{-2})$ communication complexity, where $n$ is the number of components in the finite sum. All complexity results match the best-known results achieved by a few existing methods for solving special cases of the problem we consider. To the best of our knowledge, this is the first work which provides convergence guarantees for NCSC minimax problems with general convex nonsmooth regularizers applied to both the primal and dual variables in the decentralized stochastic setting. Numerical experiments are conducted on two machine learning problems. Our code is downloadable from https://github.com/RPI-OPT/VRLM.
• Abstract（参考訳）: 本稿では,プライマリ変数と双対変数の両方に対して非滑らかな正規化項を持つ分散型,確率的非凸型(NCSC)のミニマックス問題について考察する。 カップリング関数が期待値または有限和形式であり、二重正則化子が凸関数であるとき、原始変数と双対変数に別々に適用される。 アルゴリズムフレームワークでは,双対変数のコンセンサス制約を解消するためにラグランジアン乗算器を導入する。 これを分散還元(VR)技術と組み合わせることで、提案手法は1回に1回の隣接通信により、一般的な確率的条件の下で、$\mathcal{O}(\kappa^3\varepsilon^{-3})$サンプル複雑性を達成でき、大バッチまたは小バッチのVRオプションで、$\kappa$は問題の条件番号であり、$\varepsilon$は所望の解精度である。 ビッグバッチVRでは、$\mathcal{O}(\kappa^2\varepsilon^{-2})$通信複雑性も達成できます。 特別な有限サム設定の下では、大バッチVRを用いた我々の方法は、$\mathcal{O}(n + \sqrt{n} \kappa^2\varepsilon^{-2})$サンプル複雑性と$\mathcal{O}(\kappa^2\varepsilon^{-2})$通信複雑性を達成できる。 すべての複雑さの結果は、我々が考慮している問題の特別なケースを解決するためのいくつかの既存の方法によって達成された最もよく知られた結果と一致する。 我々の知る限り、これは、分散確率環境における原始変数と双対変数の両方に適用される一般凸非平滑正規化器によるNCSCミニマックス問題に対する収束保証を提供する最初の研究である。 2つの機械学習問題に対して数値実験を行った。 私たちのコードはhttps://github.com/RPI-OPT/VRLMからダウンロードできます。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
  ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。 本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。 我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
  論文  参考訳（メタデータ） (2023-10-05T15:48:41Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• PRECISION: Decentralized Constrained Min-Max Learning with Low Communication and Sample Complexities [25.153506493249854]
  min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。 また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-05T00:26:10Z)
• An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization [25.21457349137344]
  私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization [69.49313819343992]
  広範に使われているEXTRA法とDIG法を拡張し,VR-EXTRA法とVR-DIGing法という2つの手法を提案する。 提案されたVR-EXTRAは、$O(kappa_s+n)logfrac1epsilon)$グラデーション評価と$O(kappa_b+kappa_c)logfrac1epsilon)$通信ラウンドを必要とする。 提案されているVR-DIGingは、O(kappa_b+kappa)の通信コストが少し高い
  論文  参考訳（メタデータ） (2020-09-09T15:48:44Z)

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

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