論文の概要: Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced
Convex-Concave Minimax Optimization
- arxiv url: http://arxiv.org/abs/2106.01761v1
- Date: Thu, 3 Jun 2021 11:30:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-04 21:24:02.294649
- Title: Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced
Convex-Concave Minimax Optimization
- Title（参考訳）: 有限和不平衡凸凸ミニマックス最適化のための近似最適確率アルゴリズム
- Authors: Luo Luo, Guangzeng Xie, Tong Zhang, Zhihua Zhang
- Abstract要約: 本稿では,$min_bf xmax_yf(bfbf y)という形の凸-凸最小値問題の1次アルゴリズムを同時に検討する。
我々の手法は、より一般的な不均衡なミニマックス問題を解くために使用することができ、また、ほぼ最適である。
- 参考スコア（独自算出の注目度）: 41.432757205864796
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: This paper considers stochastic first-order algorithms for convex-concave
minimax problems of the form $\min_{\bf x}\max_{\bf y}f(\bf x, \bf y)$, where
$f$ can be presented by the average of $n$ individual components which are
$L$-average smooth. For $\mu_x$-strongly-convex-$\mu_y$-strongly-concave
setting, we propose a new method which could find a $\varepsilon$-saddle point
of the problem in $\tilde{\mathcal O}
\big(\sqrt{n(\sqrt{n}+\kappa_x)(\sqrt{n}+\kappa_y)}\log(1/\varepsilon)\big)$
stochastic first-order complexity, where $\kappa_x\triangleq L/\mu_x$ and
$\kappa_y\triangleq L/\mu_y$. This upper bound is near optimal with respect to
$\varepsilon$, $n$, $\kappa_x$ and $\kappa_y$ simultaneously. In addition, the
algorithm is easily implemented and works well in practical. Our methods can be
extended to solve more general unbalanced convex-concave minimax problems and
the corresponding upper complexity bounds are also near optimal.
- Abstract（参考訳）: 本稿では, 平均値が$L$の個々の成分の平均値で$f$を提示できるような, $\min_{\bf x}\max_{\bf y}f(\bf x, \bf y)$という形で, 凸-凹最小値問題の確率的一階法を提案する。
$\mu_x$-strongly-convex-$\mu_y$-strongly-concave の設定に対して、$\tilde{\mathcal O} \big(\sqrt{n(\sqrt{n}+\kappa_x)(\sqrt{n}+\kappa_y)}\log(1/\varepsilon)\big)$ stochastic first-order complexity, where $\kappa_x\triangleq L/\mu_x$ and $\kappa_y\triangleq L/\mu_y$\mu_y\triangleq L/\mu_y$} という問題の新しい方法を提案する。
この上限は、同時に$\varepsilon$, $n$, $\kappa_x$, $\kappa_y$に関して最適に近い。
さらに、このアルゴリズムは容易に実装でき、実用的にも機能する。
提案手法は,より一般の非平衡凸凸ミニマックス問題を解くために拡張することができ,それに対応する上複雑性境界もほぼ最適である。
関連論文リスト
- Faster Stochastic Algorithms for Minimax Optimization under
Polyak--{\L}ojasiewicz Conditions [12.459354707528819]
我々は、$min_x max_y f(x,y)triqangle frac1n sum_i=1n f_i(x,y)$という形の有限サム問題を解くためのSPIDER-GDAを提案する。
SPIDER-GDA は $mathcal Oleft((n + sqrtn,kappa_xkappa_y2)log (1/epsilon) の中で $epsilon$-optimal Solution を見つけることができる。
論文 参考訳（メタデータ） (2023-07-29T02:26:31Z) - An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - The First Optimal Algorithm for Smooth and
Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。
既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。
我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-11T17:33:07Z) - 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) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。
また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
論文 参考訳（メタデータ） (2020-02-05T16:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。