論文の概要: Global Convergence Rate Analysis of Nonsmooth Nonconvex-Nonconcave Minimax Optimization

• arxiv url: http://arxiv.org/abs/2209.10825v2
• Date: Mon, 29 May 2023 16:22:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-31 03:43:30.305678
• Title: Global Convergence Rate Analysis of Nonsmooth Nonconvex-Nonconcave Minimax Optimization
• Title（参考訳）: 非平滑非凸非凸極小最適化のグローバル収束速度解析
• Authors: Jiajin Li, Linglingzhi Zhu and Anthony Man-Cho So
• Abstract要約: 本稿では,$mathcalO(epsilonmax2theta,1)$,PLDAの新しい分析フレームワークを提案する。 PLDA は [0,1/2] の $theta が最適の $mathcalO(epsilonmax2theta,1)$ を軽度の仮定で達成する。
• 参考スコア（独自算出の注目度）: 28.575516056239575
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonconvex-nonconcave minimax optimization has gained widespread interest over the last decade. However, most existing work focuses on variants of gradient descent-ascent (GDA) algorithms, which are only applicable in smooth nonconvex-concave settings. To address this limitation, we propose a novel algorithm named smoothed proximal linear descent-ascent (smoothed PLDA), which can effectively handle a broad range of structured nonsmooth nonconvex-nonconcave minimax problems. Specifically, we consider the setting where the primal function has a nonsmooth composite structure and the dual function possesses the Kurdyka-\L{}ojasiewicz (K\L{}) property with exponent $\theta \in [0,1)$. We introduce a novel convergence analysis framework for smoothed PLDA, the key components of which are our newly developed nonsmooth primal error bound and dual error bound properties. Using this framework, we show that smoothed PLDA can find both $\epsilon$-game-stationary points and $\epsilon$-optimization-stationary points of the problems of interest in $\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$ iterations. Furthermore, when $\theta \in [0,1/2]$, smoothed PLDA achieves the optimal iteration complexity of $\mathcal{O}(\epsilon^{-2})$. To further demonstrate the effectiveness and wide applicability of our analysis framework, we show that certain max-structure problem possesses the K\L{} property with exponent $\theta=0$ under mild assumptions. As a by-product, we establish algorithm-independent quantitative relationships among various stationarity concepts, which may be of independent interest.
• Abstract（参考訳）: nonconvex-nonconcave minimaxの最適化は、過去10年間で広く関心を集めている。 しかし、既存の研究のほとんどは、スムーズな非凸・凹面設定にのみ適用可能な勾配降下度アルゴリズム(GDA)の変種に焦点を当てている。 この制限に対処するため、スムーズな近位線形降下指数(smoothed PLDA)と呼ばれる新しいアルゴリズムを提案する。 具体的には、原始函数が非滑らかな合成構造を持ち、双対函数が指数 $\theta \in [0,1)$ を持つクルディカ-\L{}ojasiewicz (K\L{}) 性質を持つような集合を考える。 提案手法は, 新たに開発した非スムース主項誤りバウンドと2重誤差バウンド特性を主成分とする, 平滑化pldaのための新しい収束解析フレームワークを提案する。 このフレームワークを用いて、平滑化pldaは$\epsilon$-game-stationary pointと$\epsilon$-optimization-stationary pointの両方を$\mathcal{o}(\epsilon^{-2\max\{2\theta,1\}})$イテレーションの興味のある問題から見つけることができる。 さらに、$\theta \in [0,1/2]$のとき、滑らかなPLDAは$\mathcal{O}(\epsilon^{-2})$の最適反復複雑性を達成する。 さらに分析フレームワークの有効性と適用性を示すために、ある最大構造問題は、軽度の仮定の下で指数$\theta=0$のK\L{}特性を持つことを示した。 副産物として,様々な定常性概念間のアルゴリズム非依存な定量的関係を確立する。

関連論文リスト

• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions [19.008521454738425]
  重み付き勾配を持つ差分プライベート凸最適化(DP-SCO)の問題を考察し、一様境界ではなく、サンプル関数のリプシッツ定数上の$ktextth$-momentを仮定する。 Gcdot frac 1 sqrt n + G_k cdot (fracsqrt dnepsilon) 1 の誤差を達成し、重み付け設定における第1次最適率(対数係数まで)を得るための新しい還元ベースのアプローチを提案する。
  論文  参考訳（メタデータ） (2024-06-04T21:26:29Z)
• Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
  我々は分散環境でスティーフェル多様体に焦点をあて、$nMn log-1)$のエージェントの連結ネットワークをテストする。 そこで本研究では,nMn log-1 以下の自然ステーションを強制的に強制する分散下位段階法 (DRSM)$ という手法を提案する。
  論文  参考訳（メタデータ） (2023-03-31T02:56:23Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
  円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
  論文  参考訳（メタデータ） (2021-04-14T10:42:45Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。 提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。 提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
  論文  参考訳（メタデータ） (2021-03-29T18:53:57Z)
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization [61.66927778694731]
  エポッチ勾配降下法(エポッチ勾配降下法、Epoch-GD)は、2011年にHazan and Kaleによって提唱された。 Epoch-GDA が SCSC min-max 問題の双対性ギャップに対して$O (1/T) の最適レートを達成できることを示す最初の実験である。
  論文  参考訳（メタデータ） (2020-02-13T02:16:57Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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