論文の概要: 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の有効性を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。