論文の概要: Near-Optimal Algorithms for Minimax Optimization
- arxiv url: http://arxiv.org/abs/2002.02417v6
- Date: Mon, 26 Jul 2021 17:48:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-03 21:19:55.006551
- Title: Near-Optimal Algorithms for Minimax Optimization
- Title（参考訳）: ミニマックス最適化のための近接最適アルゴリズム
- Authors: Tianyi Lin, Chi Jin and Michael. I. Jordan
- Abstract要約: 本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。
また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
- 参考スコア（独自算出の注目度）: 115.21519161773287
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper resolves a longstanding open question pertaining to the design of
near-optimal first-order algorithms for smooth and
strongly-convex-strongly-concave minimax problems. Current state-of-the-art
first-order algorithms find an approximate Nash equilibrium using
$\tilde{O}(\kappa_{\mathbf x}+\kappa_{\mathbf y})$ or
$\tilde{O}(\min\{\kappa_{\mathbf x}\sqrt{\kappa_{\mathbf y}},
\sqrt{\kappa_{\mathbf x}}\kappa_{\mathbf y}\})$ gradient evaluations, where
$\kappa_{\mathbf x}$ and $\kappa_{\mathbf y}$ are the condition numbers for the
strong-convexity and strong-concavity assumptions. A gap still remains between
these results and the best existing lower bound
$\tilde{\Omega}(\sqrt{\kappa_{\mathbf x}\kappa_{\mathbf y}})$. This paper
presents the first algorithm with $\tilde{O}(\sqrt{\kappa_{\mathbf
x}\kappa_{\mathbf y}})$ gradient complexity, matching the lower bound up to
logarithmic factors. Our algorithm is designed based on an accelerated proximal
point method and an accelerated solver for minimax proximal steps. It can be
easily extended to the settings of strongly-convex-concave, convex-concave,
nonconvex-strongly-concave, and nonconvex-concave functions. This paper also
presents algorithms that match or outperform all existing methods in these
settings in terms of gradient complexity, up to logarithmic factors.
- Abstract（参考訳）: 本稿では,滑らかかつ強凸かつ強凸なミニマックス問題に対する最適に近い一階アルゴリズムの設計に関する長年の疑問を解決する。
現在の最先端の1次アルゴリズムは、$\tilde{O}(\kappa_{\mathbf x}+\kappa_{\mathbf y})$または$\tilde{O}(\min\{\kappa_{\mathbf x}\sqrt{\kappa_{\mathbf y}}, \sqrt{\kappa_{\mathbf x}}\kappa_{\mathbf y}\})$グリート評価を用いて、近似的なナッシュ均衡を求める。
これらの結果と、既存の最下限の$\tilde{\Omega}(\sqrt{\kappa_{\mathbf x}\kappa_{\mathbf y}})$の間にはまだギャップが残っている。
本稿では,下界を対数的因子に整合させるような勾配複雑性を$\tilde{O}(\sqrt{\kappa_{\mathbf x}\kappa_{\mathbf y}})で表した最初のアルゴリズムを提案する。
本アルゴリズムは, 最小近位ステップのための高速化された近位点法と高速化解法に基づいて設計する。
強凸凹、凸凹、非凸凸凸、非凸凸凸関数の設定に容易に拡張できる。
本論文は, 勾配の複雑さから対数係数まで, 既存の手法のすべてに匹敵するアルゴリズムも提示する。
関連論文リスト
- A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文 参考訳（メタデータ） (2024-06-26T18:19:10Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - 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) - Finding Second-Order Stationary Point for Nonconvex-Strongly-Concave
Minimax Problem [16.689304539024036]
本稿では,ミニマックス問題の2階定常点を求める非同相的挙動について考察する。
高次元問題に対して、降下とチェビシェフ展開による勾配の立方体部分確率を解く2階オラクルのコスト対費用について提案する。
論文 参考訳（メタデータ） (2021-10-10T14:54:23Z) - Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced
Convex-Concave Minimax Optimization [41.432757205864796]
本稿では,$min_bf xmax_yf(bfbf y)という形の凸-凸最小値問題の1次アルゴリズムを同時に検討する。
我々の手法は、より一般的な不均衡なミニマックス問題を解くために使用することができ、また、ほぼ最適である。
論文 参考訳（メタデータ） (2021-06-03T11:30:32Z) - DIPPA: An improved Method for Bilinear Saddle Point Problems [18.65143269806133]
本稿では,min_bfx max_bfy g(fracx) + bfxtop bfbftop fracbfa kappa_x kappa_x (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y) kappa_y (kappa_x + kappa_y)について述べる。
論文 参考訳（メタデータ） (2021-03-15T10:55:30Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。