論文の概要: 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からダウンロードできます。
関連論文リスト
- 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 Efficient Stochastic Algorithm for Decentralized
Nonconvex-Strongly-Concave Minimax Optimization [28.10283834703862]
本稿では,マルチエージェントネットワーク上での分散非強度コンケーブ(NC-SC)ミニマックス問題の最適化を実現する。
本稿では,DREAM(Decentralized Recursive-gradient descEnt Ascent Method)と呼ばれる効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-12-05T16:09:39Z) - 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) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳(メタデータ) (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。