Fugu-MT 論文翻訳(概要): The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization

論文の概要: The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization

arxiv url: http://arxiv.org/abs/2205.05653v1
Date: Wed, 11 May 2022 17:33:07 GMT
ステータス: 処理完了
システム内更新日: 2022-05-12 21:39:30.615492
Title: The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization
Title（参考訳）: Smooth and strong-convex-Strongly-Concave Minimax Optimizationのための第1次最適アルゴリズム
Authors: Dmitry Kovalev, Alexander Gasnikov
Abstract要約: 本稿では,スムーズで強靭なミニマックス最適化問題を再考する。既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
参考スコア（独自算出の注目度）: 88.91190483500932
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we revisit the smooth and strongly-convex-strongly-concave minimax optimization problem. Zhang et al. (2021) and Ibrahim et al. (2020) established the lower bound $\Omega\left(\sqrt{\kappa_x\kappa_y} \log \frac{1}{\epsilon}\right)$ on the number of gradient evaluations required to find an $\epsilon$-accurate solution, where $\kappa_x$ and $\kappa_y$ are condition numbers for the strong convexity and strong concavity assumptions. However, the existing state-of-the-art methods do not match this lower bound: algorithms of Lin et al. (2020) and Wang and Li (2020) have gradient evaluation complexity $\mathcal{O}\left( \sqrt{\kappa_x\kappa_y}\log^3\frac{1}{\epsilon}\right)$ and $\mathcal{O}\left( \sqrt{\kappa_x\kappa_y}\log^3 (\kappa_x\kappa_y)\log\frac{1}{\epsilon}\right)$, respectively. We fix this fundamental issue by providing the first algorithm with $\mathcal{O}\left(\sqrt{\kappa_x\kappa_y}\log\frac{1}{\epsilon}\right)$ gradient evaluation complexity. We design our algorithm in three steps: (i) we reformulate the original problem as a minimization problem via the pointwise conjugate function; (ii) we apply a specific variant of the proximal point algorithm to the reformulated problem; (iii) we compute the proximal operator inexactly using the optimal algorithm for operator norm reduction in monotone inclusions.
Abstract（参考訳）: 本稿では,スムーズかつ強凸・強凸極小最適化問題を再考する。 zhang et al. (2021) と ibrahim et al. (2020) は、下限の $\omega\left (\sqrt{\kappa_x\kappa_y} \log \frac{1}{\epsilon}\right) を、$\epsilon$-accurate の解を見つけるのに必要な勾配評価の数に基づいて定式化した。 lin et al. (2020) と wang と li (2020) のアルゴリズムは勾配評価複雑性$\mathcal{o}\left( \sqrt{\kappa_x\kappa_y}\log^3\frac{1}{\epsilon}\right)$ と $\mathcal{o}\left( \sqrt{\kappa_x\kappa_y}\log^3 (\kappa_x\kappa_y)\log\frac{1}{\epsilon}\right)$ を持つ。この根本的な問題は、$\mathcal{O}\left(\sqrt{\kappa_x\kappa_y}\log\frac{1}{\epsilon}\right)$グラデーション評価の複雑さによって解決する。アルゴリズムを3つのステップで設計します (i)点共役関数による最小化問題として元の問題を再構成する。 (ii) 近似点アルゴリズムの特定の変種を再構成問題に適用する。 3) 単調包摂における演算子ノルム低減のための最適アルゴリズムを用いて, 近似演算子を不正確に計算する。

関連論文リスト

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)
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 Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-19T16:04:40Z)
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)
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)
Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
論文参考訳（メタデータ） (2020-02-05T16:49:09Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。