論文の概要: A Simple and Efficient Stochastic Algorithm for Decentralized
Nonconvex-Strongly-Concave Minimax Optimization
- arxiv url: http://arxiv.org/abs/2212.02387v2
- Date: Wed, 10 May 2023 04:54:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-11 17:09:12.531253
- Title: A Simple and Efficient Stochastic Algorithm for Decentralized
Nonconvex-Strongly-Concave Minimax Optimization
- Title(参考訳): 非凸強凸ミニマックス最適化のための単純かつ効率的な確率的アルゴリズム
- Authors: Lesi Chen, Haishan Ye, Luo Luo
- Abstract要約: Decentralized Recursive-gradient desc Ascent Method (textttDREAM) と呼ばれるシンプルで効率的なアルゴリズムを提案する。
オンライン設定には$mathcalObig(kappa2 sqrtN epsilon-2big)$ SFO呼び出しとオンライン設定と同じ通信複雑性が必要である。
オフライン設定には$mathcalObig(kappa2 sqrtN epsilon-2big)が必要である。
- 参考スコア(独自算出の注目度): 21.343547105464957
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the stochastic optimization for decentralized
nonconvex-strongly-concave minimax problem. We propose a simple and efficient
algorithm, called Decentralized Recursive-gradient descEnt Ascent Method
(\texttt{DREAM}), which achieves the best-known theoretical guarantee for
finding the $\epsilon$-stationary point of the primal function. For the online
setting, the proposed method requires $\mathcal{O}(\kappa^3\epsilon^{-3})$
stochastic first-order oracle (SFO) calls and
$\mathcal{O}\big(\kappa^2\epsilon^{-2}/\sqrt{1-\lambda_2(W)}\,\big)$
communication rounds to find an $\epsilon$-stationary point, where $\kappa$ is
the condition number and $\lambda_2(W)$ is the second-largest eigenvalue of the
gossip matrix~$W$. For the offline setting with totally $N$ component
functions, the proposed method requires $\mathcal{O}\big(\kappa^2 \sqrt{N}
\epsilon^{-2}\big)$ SFO calls and the same communication complexity as the
online setting.
- Abstract(参考訳): 本稿では,非凸強凸ミニマックス問題に対する確率的最適化について検討する。
そこで本研究では,初等関数の$\epsilon$-stationary pointを求めるための最もよく知られた理論的保証を実現する,分散再帰的漸進降降降法(\textt{dream})と呼ばれる,単純かつ効率的なアルゴリズムを提案する。
オンラインの設定には、$\mathcal{o}(\kappa^3\epsilon^{-3})$ 確率的一階 oracle (sfo) コールと$\mathcal{o}\big(\kappa^2\epsilon^{-2}/\sqrt{1-\lambda_2(w)}\,\big)$ の通信ラウンドが必要であり、$\kappa$ は条件番号、$\lambda_2(w)$ は gosip行列の2番目に大きい固有値である。
完全に$N$のコンポーネント関数を持つオフライン設定では、提案手法は$\mathcal{O}\big(\kappa^2 \sqrt{N} \epsilon^{-2}\big)$ SFO呼び出しとオンライン設定と同じ通信複雑性を必要とする。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [58.372148767703955]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳(メタデータ) (2024-02-14T13:44:16Z) - 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) - Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳(メタデータ) (2023-08-15T02:37:11Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳(メタデータ) (2023-06-30T20:36:44Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - 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) - Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文 参考訳(メタデータ) (2022-02-01T16:06:20Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳(メタデータ) (2021-02-15T07:10:33Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳(メタデータ) (2020-06-24T04:41:43Z) - Stochastic Recursive Gradient Descent Ascent for Stochastic
Nonconvex-Strongly-Concave Minimax Problems [36.645753881826955]
本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。
この方法はこの問題でよく知られている。
論文 参考訳(メタデータ) (2020-01-11T09:05:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。