論文の概要: A Simple and Efficient Stochastic Algorithm for Decentralized
Nonconvex-Strongly-Concave Minimax Optimization
- arxiv url: http://arxiv.org/abs/2212.02387v1
- Date: Mon, 5 Dec 2022 16:09:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 19:20:15.828910
- Title: A Simple and Efficient Stochastic Algorithm for Decentralized
Nonconvex-Strongly-Concave Minimax Optimization
- Title（参考訳）: 非凸強凸ミニマックス最適化のための単純かつ効率的な確率的アルゴリズム
- Authors: Lesi Chen, Haishan Ye, Luo Luo
- Abstract要約: 本稿では,分散化された非コンケーブ最小値問題に対する依存性最適化について検討する。
これは$mathcalO(kappa3epsilon-3)$ one-order oracle (FO) call and $mathcalObig(kappa2epsilon-2/sqrt1-lambda_W),big)$ communication rounds to find a $epsilon$。
- 参考スコア（独自算出の注目度）: 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
(DREAM), which 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$. To the best our knowledge, DREAM is the first algorithm
whose SFO and communication complexities simultaneously achieve the optimal
dependency on $\epsilon$ and $\lambda_2(W)$ for this problem.
- Abstract（参考訳）: 本稿では,非凸強凸ミニマックス問題に対する確率的最適化について検討する。
我々は,分散再帰的勾配降下上昇法 (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)$は$w$ がゴシップ行列の2番目に大きい固有値である。
我々の知る限り、DREAMは、この問題に対して$\epsilon$と$\lambda_2(W)$の最適依存性を同時に達成する最初のアルゴリズムである。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。