論文の概要: Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization

• arxiv url: http://arxiv.org/abs/2104.08708v1
• Date: Sun, 18 Apr 2021 04:30:01 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-20 14:21:29.724902
• Title: Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• Title（参考訳）: 非凸強凹min-max最適化における複雑性下限
• Authors: Haochuan Li, Yi Tian, Jingzhao Zhang, Ali Jadbabaie
• Abstract要約: min-max最適化問題の定常点を求めるための1次オラクル下界を提供する。 私たちの分析は、上限が$epsilon$依存性最大$kappa$で最適であることを示しています。 この結果から, 上の$mathcalOkappa3 epsilon-4)$ in (Lin et al., 2020a) と, 近似数依存性の下位境界との間には, 有意な差があることが示唆された。
• 参考スコア（独自算出の注目度）: 31.0295459253155
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We provide a first-order oracle complexity lower bound for finding stationary points of min-max optimization problems where the objective function is smooth, nonconvex in the minimization variable, and strongly concave in the maximization variable. We establish a lower bound of $\Omega\left(\sqrt{\kappa}\epsilon^{-2}\right)$ for deterministic oracles, where $\epsilon$ defines the level of approximate stationarity and $\kappa$ is the condition number. Our analysis shows that the upper bound achieved in (Lin et al., 2020b) is optimal in the $\epsilon$ and $\kappa$ dependence up to logarithmic factors. For stochastic oracles, we provide a lower bound of $\Omega\left(\sqrt{\kappa}\epsilon^{-2} + \kappa^{1/3}\epsilon^{-4}\right)$. It suggests that there is a significant gap between the upper bound $\mathcal{O}(\kappa^3 \epsilon^{-4})$ in (Lin et al., 2020a) and our lower bound in the condition number dependence.
• Abstract（参考訳）: 目的関数が滑らかで、最小化変数が非凸で、最大化変数が強凹であるmin-max最適化問題の定常点を見つけるために、oracleの1階の複雑性を低く抑える。 我々は、決定論的オラクルに対して$\Omega\left(\sqrt{\kappa}\epsilon^{-2}\right)$の下位境界を確立し、$\epsilon$は近似定常性のレベルを定義し、$\kappa$は条件番号である。 解析の結果, (lin et al., 2020b) で達成される上限は, 対数因子に対する $\epsilon$ と $\kappa$ の順に最適であることが判明した。 確率的オラクルに対しては、$\Omega\left(\sqrt{\kappa}\epsilon^{-2} + \kappa^{1/3}\epsilon^{-4}\right)$を下限とする。 これは、上界$\mathcal{O}(\kappa^3 \epsilon^{-4})$ in (Lin et al., 2020a) と条件数依存性の下位境界との間に大きなギャップがあることを示唆している。

関連論文リスト

• On the Complexity of First-Order Methods in Stochastic Bilevel Optimization [9.649991673557167]
  両レベル最適化における定常点を求める問題は、下層問題に制約がなく、強い凸がある場合に考慮する。 既存のアプローチは、それらの分析を低レベルの解を知っているジェニーアルゴリズムに結びつける。 我々は、$O(epsilon-6), O(epsilon-4)$ 1次$y*$-aware oraclesを使って、$epsilon$固定点に収束する単純な一階法を提案する。
  論文  参考訳（メタデータ） (2024-02-11T04:26:35Z)
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• 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)
• Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
  オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。 非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
  論文  参考訳（メタデータ） (2021-05-04T21:49:15Z)
• 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)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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