論文の概要: Nonsmooth Composite Nonconvex-Concave Minimax Optimization

• arxiv url: http://arxiv.org/abs/2209.10825v1
• Date: Thu, 22 Sep 2022 07:12:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-23 14:35:26.547100
• Title: Nonsmooth Composite Nonconvex-Concave Minimax Optimization
• Title（参考訳）: 非平滑複合非凸凹極小最適化
• Authors: Jiajin Li, Linglingzhi Zhu and Anthony Man-Cho So
• Abstract要約: ノンコンケーブのミニマックス最適化は、データ分散に対する堅牢性のある学習を含む、機械学習に強い関心を集めている。 既存のミニマックス問題の多くはスムーズな設定でしか適用できない。 本稿では,GDAcitezhang とスムーズな設定で一致した PLDA アルゴリズムを提案する。 我々の知る限りでは、これは非滑らかな非凹問題に対する証明可能なアルゴリズムとしては初めてのものである。
• 参考スコア（独自算出の注目度）: 28.575516056239575
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonconvex-concave minimax optimization has received intense interest in machine learning, including learning with robustness to data distribution, learning with non-decomposable loss, adversarial learning, to name a few. Nevertheless, most existing works focus on the gradient-descent-ascent (GDA) variants that can only be applied in smooth settings. In this paper, we consider a family of minimax problems whose objective function enjoys the nonsmooth composite structure in the variable of minimization and is concave in the variables of maximization. By fully exploiting the composite structure, we propose a smoothed proximal linear descent ascent (\textit{smoothed} PLDA) algorithm and further establish its $\mathcal{O}(\epsilon^{-4})$ iteration complexity, which matches that of smoothed GDA~\cite{zhang2020single} under smooth settings. Moreover, under the mild assumption that the objective function satisfies the one-sided Kurdyka-\L{}ojasiewicz condition with exponent $\theta \in (0,1)$, we can further improve the iteration complexity to $\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$. To the best of our knowledge, this is the first provably efficient algorithm for nonsmooth nonconvex-concave problems that can achieve the optimal iteration complexity $\mathcal{O}(\epsilon^{-2})$ if $\theta \in (0,1/2]$. As a byproduct, we discuss different stationarity concepts and clarify their relationships quantitatively, which could be of independent interest. Empirically, we illustrate the effectiveness of the proposed smoothed PLDA in variation regularized Wasserstein distributionally robust optimization problems.
• Abstract（参考訳）: nonconvex-concave minimax最適化は、データ分散に堅牢な学習、非可逆的損失による学習、敵対的学習など、機械学習に大きな関心を集めている。 しかしながら、既存のほとんどの研究は、スムーズな設定でしか適用できないグラデーション・ディフレッシュ・アセット(GDA)の変種に焦点を当てている。 本稿では、最小化の変数における非滑らかな合成構造を目的関数が享受し、最大化の変数において凹凸となるミニマックス問題の族を考える。 複合構造を十分に活用することにより,滑らかな近位線形降下法 (\textit{smoothed} plda) アルゴリズムを提案し,滑らかな設定下での平滑化 gda~\cite{zhang2020single} のそれと一致する$\mathcal{o}(\epsilon^{-4})$ の反復複雑性を確立する。 さらに、目的関数が片面のクルディカ-\L{}ojasiewicz条件を指数$\theta \in (0,1)$で満たすという軽微な仮定の下では、反復複雑性をさらに$\mathcal{O}(\epsilon^{-2\max\{2\theta,1\}})$に改善することができる。 我々の知る限りでは、このアルゴリズムは非滑らかな非凸凸凸問題に対する最初の証明可能なアルゴリズムであり、最適な反復複雑性である$\mathcal{o}(\epsilon^{-2})$ if $\theta \in (0,1/2]$ を達成することができる。 副産物として,異なる定常性の概念を議論し,それらの関係を定量的に明らかにした。 実験により,変動正規化ワッサースタイン分布にロバストな最適化問題に対して提案する平滑化pldaの有効性を示す。

関連論文リスト

• 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)

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

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