論文の概要: An Efficient Stochastic Algorithm for Decentralized
Nonconvex-Strongly-Concave Minimax Optimization
- arxiv url: http://arxiv.org/abs/2212.02387v3
- Date: Sat, 12 Aug 2023 09:29:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-15 22:45:55.779931
- Title: An Efficient Stochastic Algorithm for Decentralized
Nonconvex-Strongly-Concave Minimax Optimization
- Title(参考訳): 分散非凸強凸ミニマックス最適化のための効率的な確率的アルゴリズム
- Authors: Lesi Chen, Haishan Ye, Luo Luo
- Abstract要約: 本稿では,マルチエージェントネットワーク上での分散非強度コンケーブ(NC-SC)ミニマックス問題の最適化を実現する。
本稿では,DREAM(Decentralized Recursive-gradient descEnt Ascent Method)と呼ばれる効率的なアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 28.10283834703862
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the stochastic optimization for decentralized
nonconvex-strongly-concave (NC-SC) minimax problems over a multi-agent network.
We propose an efficient algorithm, called the Decentralized Recursive-gradient
descEnt Ascent Method (DREAM), which achieves the best-known theoretical
guarantee for finding the $\epsilon$-stationary point of the primal function.
The proposed method requires $\mathcal{O}(\min (\kappa^3\epsilon^{-3},\sqrt{N}
\kappa^2 \epsilon^{-2} ))$ stochastic first-order oracle (SFO) calls and
$\tilde{\mathcal{O}}(\kappa^2 \epsilon^{-2})$ communication rounds to find an
$\epsilon$-stationary point, where $\kappa$ is the condition number. DREAM
achieves the best-known complexity for both the online and offline setups.
- Abstract(参考訳): 本稿では,マルチエージェントネットワーク上の分散非凸強対流(NC-SC)ミニマックス問題に対する確率的最適化について検討する。
そこで本研究では,初等関数の$\epsilon$-stationary pointを求めるための最もよく知られている理論的保証を実現するために,分散再帰的漸進降昇降法(dream)を提案する。
提案手法では,$\mathcal{o}(\min (\kappa^3\epsilon^{-3},\sqrt{n} \kappa^2 \epsilon^{-2} )$確率的一階oracle (sfo) コールと$\tilde{\mathcal{o}} (\kappa^2 \epsilon^{-2})$ の通信ラウンドが必要となる。
DREAMは、オンラインとオフラインの両方でよく知られた複雑さを実現する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。