論文の概要: 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は、オンラインとオフラインの両方でよく知られた複雑さを実現する。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - 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) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51: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) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to
Minimax Optimization [133.53164856723782]
そこで我々は,関数値のみが得られるブラックボックス最小最適化のための新しいアクセラレーションゼロ階運動量 (AccZOM) 法を提案する。
一方,ブラックボックス最小値最適化のためのアクセラレーションゼロ階運動量降下法(Acc-MDA)を提案する。
特に、Acc-MDAは、$tildeO(kappa_y2.5epsilon-3)$の低い勾配の複雑さを、バッチサイズ$O(kappa_y4)$で得ることができる。
論文 参考訳（メタデータ） (2020-08-18T22:19:29Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。