論文の概要: Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual
Balancing and Iteration Complexity Analysis
- arxiv url: http://arxiv.org/abs/2209.10825v3
- Date: Wed, 26 Jul 2023 23:09:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-28 20:40:43.905174
- Title: Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual
Balancing and Iteration Complexity Analysis
- Title(参考訳): 非滑らかな非凸非凸最小値最適化:2次元バランスと反復複雑度解析
- Authors: Jiajin Li, Linglingzhi Zhu and Anthony Man-Cho So
- Abstract要約: PLDAの新たな解析手法を導入し,その鍵となるのは,新たに開発された非滑らかかつ二重なエラー反復である。
PLDA が $thetain [0,12]$ のとき、緩やかな仮定の下で最適な $mathcalO()$ を達成する。
- 参考スコア(独自算出の注目度): 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 works focus on variants of gradient
descent-ascent (GDA) algorithms, which are only applicable to 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-Lojasiewicz (KL) 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. 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,\frac{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-structured problem possesses the KL 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)$のクルディカ・ロジャシエヴィチ(KL)性質を持つような集合を考える。
提案手法は, 新たに開発した非スムース主元誤差境界と2重誤差境界を主成分とする, 平滑化pldaのための新しい収束解析フレームワークを提案する。
このフレームワークを用いて、平滑化pldaは$\epsilon$-game-stationary pointと$\epsilon$-optimization-stationary pointの両方を$\mathcal{o}(\epsilon^{-2\max\{2\theta,1\}})$イテレーションの興味のある問題から見つけることができる。
さらに、$\theta \in [0,\frac{1}{2}]$の場合、平滑化pldaは$\mathcal{o}(\epsilon^{-2})$の最適な反復複雑性を達成する。
分析フレームワークの有効性と適用性をさらに高めるために、ある最大構造問題は、軽度仮定の下で指数$\theta=0$のKL特性を持つことを示した。
副産物として,様々な定常性概念間のアルゴリズム非依存な定量的関係を確立する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Projective Proximal Gradient Descent for A Class of Nonconvex Nonsmooth
Optimization Problems: Fast Convergence Without Kurdyka-Lojasiewicz (KL)
Property [22.232788341658924]
非滑らかな最適化問題は、学習にとって重要かつ困難である。
本稿では,PSGDの高速収束を示す新しい解析法について述べる。
論文 参考訳(メタデータ) (2023-04-20T17:39:24Z) - 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) - Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction [18.65143269806133]
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
論文 参考訳(メタデータ) (2021-03-15T11:20:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。