論文の概要: Stochastic Recursive Gradient Descent Ascent for Stochastic
Nonconvex-Strongly-Concave Minimax Problems
- arxiv url: http://arxiv.org/abs/2001.03724v2
- Date: Fri, 23 Oct 2020 09:37:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-12 09:25:36.395835
- Title: Stochastic Recursive Gradient Descent Ascent for Stochastic
Nonconvex-Strongly-Concave Minimax Problems
- Title（参考訳）: 確率的非凸強凸ミニマックス問題に対する確率的再帰的勾配降下上昇
- Authors: Luo Luo, Haishan Ye, Zhichao Huang, Tong Zhang
- Abstract要約: 本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。
この方法はこの問題でよく知られている。
- 参考スコア（独自算出の注目度）: 36.645753881826955
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We consider nonconvex-concave minimax optimization problems of the form
$\min_{\bf x}\max_{\bf y\in{\mathcal Y}} f({\bf x},{\bf y})$, where $f$ is
strongly-concave in $\bf y$ but possibly nonconvex in $\bf x$ and ${\mathcal
Y}$ is a convex and compact set. We focus on the stochastic setting, where we
can only access an unbiased stochastic gradient estimate of $f$ at each
iteration. This formulation includes many machine learning applications as
special cases such as robust optimization and adversary training. We are
interested in finding an ${\mathcal O}(\varepsilon)$-stationary point of the
function $\Phi(\cdot)=\max_{\bf y\in{\mathcal Y}} f(\cdot, {\bf y})$. The most
popular algorithm to solve this problem is stochastic gradient decent ascent,
which requires $\mathcal O(\kappa^3\varepsilon^{-4})$ stochastic gradient
evaluations, where $\kappa$ is the condition number. In this paper, we propose
a novel method called Stochastic Recursive gradiEnt Descent Ascent (SREDA),
which estimates gradients more efficiently using variance reduction. This
method achieves the best known stochastic gradient complexity of ${\mathcal
O}(\kappa^3\varepsilon^{-3})$, and its dependency on $\varepsilon$ is optimal
for this problem.
- Abstract（参考訳）: ここで、$f$ は $\bf y$ の強凸であるが、$\bf x$ と ${\mathcal Y}$ の非凸であれば $\bf x$ と ${\mathcal Y}$ は凸コンパクト集合である。
私たちは確率的設定に注目し、各イテレーションでバイアスのない確率的勾配の見積もりにのみアクセスできる。
この定式化には、堅牢な最適化や逆トレーニングといった特別なケースとして、多くの機械学習アプリケーションが含まれている。
我々は、函数 $\Phi(\cdot)=\max_{\bf y\in{\mathcal Y}} f(\cdot, {\bf y})$ の ${\mathcal O}(\varepsilon)$-定常点を見つけることに興味がある。
この問題を解くための最も一般的なアルゴリズムは確率勾配の上昇であり、$\mathcal O(\kappa^3\varepsilon^{-4})$ 確率勾配の評価が必要であり、$\kappa$は条件数である。
本稿では,分散還元法を用いてより効率的に勾配を推定する,確率的再帰的勾配降下上昇法(sreda)という新しい手法を提案する。
この方法は${\mathcal O}(\kappa^3\varepsilon^{-3})$の確率勾配複雑性を最もよく知られており、$\varepsilon$への依存はこの問題に最適である。
関連論文リスト
- Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳（メタデータ） (2023-08-15T02:37:11Z) - Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization [20.54801745090522]
我々は、mathbbRd f(x) 三角形q mathbbE_xi [Fxi]$inf(x)$ Lipschitz における $min_x という形式の問題を考察する。
最近提案された勾配なし法は、少なくとも$mathcalO(L4 d3/2 epsilon-4 + Goldstein L d3/2 delta-1 epsilon-4)$ 0次複雑性を必要とする。
論文 参考訳（メタデータ） (2023-01-16T13:33:37Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
Decentralized Recursive Dec. Method (DREAM)
具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。
我々の数値実験は,従来の手法の優越性を検証した。
論文 参考訳（メタデータ） (2022-12-05T16:09:39Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - 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) - Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。
SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。
我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
論文 参考訳（メタデータ） (2021-10-25T07:20:05Z) - Greedy Adversarial Equilibrium: An Efficient Alternative to
Nonconvex-Nonconcave Min-Max Optimization [28.431572772564518]
リプシッツの$varepsilon$-greedy逆数モデルは任意の出発点から$max_z f(x, z)$に収束することを示す。
また、リプシッツの$nabla_y f(x,y)$が$d$, $1/varepsilon$であり、$nabla2_y f(x,y)$上の境界は$nabla2_yであることを示す。
論文 参考訳（メタデータ） (2020-06-22T16:03:41Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z) - Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。
また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
論文 参考訳（メタデータ） (2020-02-05T16:49:09Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。