論文の概要: Improved Algorithms for Convex-Concave Minimax Optimization

• arxiv url: http://arxiv.org/abs/2006.06359v2
• Date: Mon, 19 Oct 2020 01:27:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 09:52:43.276803
• Title: Improved Algorithms for Convex-Concave Minimax Optimization
• Title（参考訳）: 凸凸ミニマックス最適化のための改良アルゴリズム
• Authors: Yuanhao Wang and Jian Li
• Abstract要約: 本稿では、ミニマックス最適化問題$min_x max_y f(x,y)$, $f(x,y)$が$x$, $m_y$-strongly concaveに対して$m_x$-strongly convexが$y$および$(L_x,L_xy,L_y)$-smoothに関して$m_x$-strongly concaveについて検討する。
• 参考スコア（独自算出の注目度）: 10.28639483137346
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies minimax optimization problems $\min_x \max_y f(x,y)$, where $f(x,y)$ is $m_x$-strongly convex with respect to $x$, $m_y$-strongly concave with respect to $y$ and $(L_x,L_{xy},L_y)$-smooth. Zhang et al. provided the following lower bound of the gradient complexity for any first-order method: $\Omega\Bigl(\sqrt{\frac{L_x}{m_x}+\frac{L_{xy}^2}{m_x m_y}+\frac{L_y}{m_y}}\ln(1/\epsilon)\Bigr).$ This paper proposes a new algorithm with gradient complexity upper bound $\tilde{O}\Bigl(\sqrt{\frac{L_x}{m_x}+\frac{L\cdot L_{xy}}{m_x m_y}+\frac{L_y}{m_y}}\ln\left(1/\epsilon\right)\Bigr),$ where $L=\max\{L_x,L_{xy},L_y\}$. This improves over the best known upper bound $\tilde{O}\left(\sqrt{\frac{L^2}{m_x m_y}} \ln^3\left(1/\epsilon\right)\right)$ by Lin et al. Our bound achieves linear convergence rate and tighter dependency on condition numbers, especially when $L_{xy}\ll L$ (i.e., when the interaction between $x$ and $y$ is weak). Via reduction, our new bound also implies improved bounds for strongly convex-concave and convex-concave minimax optimization problems. When $f$ is quadratic, we can further improve the upper bound, which matches the lower bound up to a small sub-polynomial factor.
• Abstract（参考訳）: ここでは、$f(x,y)$が$m_x$-strongly convexに対して$x$,$m_y$-strongly concaveに対して$y$と$(L_x,L_{xy},L_y)$-smoothに対して$f(x,y)$が$m_x$-strongly convexとなる。 Zhang et al. は、任意の一階法の勾配複雑性の以下の下界を与えた: $\Omega\Bigl(\sqrt {\frac{L_x}{m_x}+\frac{L_{xy}^2}{m_x m_y}+\frac{L_y}{m_y}}\ln(1/\epsilon)\Bigr。 この論文は、勾配複雑性の上限値$\tilde{o}\bigl(\sqrt{\frac{l_x}{m_x}+\frac{l\cdot l_{xy}}{m_x m_y}+\frac{l_y}{m_y}}\ln\left(1/\epsilon\right)\bigr)$l=\max\{l_x,l_{xy},l_y\}$を持つ新しいアルゴリズムを提案する。 これはLin et al による最もよく知られた上界 $\tilde{O}\left(\sqrt {\frac{L^2}{m_x m_y}} \ln^3\left(1/\epsilon\right)\right)$よりも改善される。 我々の境界は、特に$L_{xy}\ll L$(例えば$x$と$y$の間の相互作用が弱いとき)の条件数に対する線形収束率とより厳密な依存を達成する。 縮小により、新しい境界は、強い凸凸および凸凸ミニマックス最適化問題に対する境界の改善も含意する。 f$ が二次であるとき、より上界を改善することができ、これは下界を小さな部分多項式因子に一致する。

関連論文リスト

• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• 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)
• Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods [39.87865197769047]
  分離可能なミニマックス最適化問題 $min_x max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(Lx, mux)$, $(Ly, muy)$, and $h$ is convex-concave with a $(Lambdaxx, Lambdaxy, Lambdayymuyright)$。
  論文  参考訳（メタデータ） (2022-02-09T18:57:47Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
  改良された$Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$。 高速化されたEXTRAの通信複雑性は、$left(logfracLmu (1-sigma_2(W))right)$と$left(logfrac1epsilon (1。
  論文  参考訳（メタデータ） (2020-02-24T08:07:08Z)

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

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