論文の概要: Tight Analysis of Extra-gradient and Optimistic Gradient Methods For
Nonconvex Minimax Problems
- arxiv url: http://arxiv.org/abs/2210.09382v1
- Date: Mon, 17 Oct 2022 19:26:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-19 14:14:36.321990
- Title: Tight Analysis of Extra-gradient and Optimistic Gradient Methods For
Nonconvex Minimax Problems
- Title(参考訳): 非凸ミニマックス問題に対する超勾配および楽観勾配法の厳密な解析
- Authors: Pouria Mahdavinia, Yuyang Deng, Haochuan Li, Mehrdad Mahdavi
- Abstract要約: 凸コンマックス問題に対する最適勾配上昇法(OGDA)が確立されているにもかかわらず、これらの手法の極小厳密性についてはほとんど分かっていない。
我々は,GAN(Generative Adversarial Networks)やロバストニューラルネットワークなど,複雑な非最小の現実問題を解くための理論EGDA手法の理解を支援する実験を行う。
- 参考スコア(独自算出の注目度): 14.45488378956343
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Despite the established convergence theory of Optimistic Gradient Descent
Ascent (OGDA) and Extragradient (EG) methods for the convex-concave minimax
problems, little is known about the theoretical guarantees of these methods in
nonconvex settings. To bridge this gap, for the first time, this paper
establishes the convergence of OGDA and EG methods under the
nonconvex-strongly-concave (NC-SC) and nonconvex-concave (NC-C) settings by
providing a unified analysis through the lens of single-call extra-gradient
methods. We further establish lower bounds on the convergence of GDA/OGDA/EG,
shedding light on the tightness of our analysis. We also conduct experiments
supporting our theoretical results. We believe our results will advance the
theoretical understanding of OGDA and EG methods for solving complicated
nonconvex minimax real-world problems, e.g., Generative Adversarial Networks
(GANs) or robust neural networks training.
- Abstract(参考訳): 楽観的勾配降下法(ogda)と凸凸ミニマックス問題の超勾配法(eg)の確立された収束理論にもかかわらず、非凸設定におけるこれらの方法の理論的保証についてはほとんど知られていない。
このギャップを埋めるために,本論文では, 単呼外勾配法のレンズによる統一解析を提供することにより, 非凸凹(NC-SC)および非凸凹(NC-C)設定下でのOGDA法とEG法の収束を初めて確立する。
さらに,GDA/OGDA/EGの収束度を低くし,分析の厳密性に光を当てる。
理論的結果を支持する実験も行います。
我々は,GAN(Generative Adversarial Networks)やロバストニューラルネットワークトレーニングなど,複雑な非凸ミニマックスの問題を解くためのOGDA法とEG法の理論的理解を進めていくと信じている。
関連論文リスト
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-24T02:19:39Z) - Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax
Problems [39.197569803430646]
最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。
近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
論文 参考訳(メタデータ) (2023-04-21T11:38:41Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳(メタデータ) (2023-02-08T01:42:45Z) - Stability and Generalization of Stochastic Gradient Methods for Minimax
Problems [71.60601421935844]
多くの機械学習問題は、GAN(Generative Adversarial Networks)のようなミニマックス問題として定式化できる。
ミニマックス問題に対するトレーニング勾配法から例を包括的に一般化解析する。
論文 参考訳(メタデータ) (2021-05-08T22:38:00Z) - Learning Fast Approximations of Sparse Nonlinear Regression [50.00693981886832]
本研究では,Threshold Learned Iterative Shrinkage Algorithming (NLISTA)を導入することでギャップを埋める。
合成データを用いた実験は理論結果と相関し,その手法が最先端の手法より優れていることを示す。
論文 参考訳(メタデータ) (2020-10-26T11:31:08Z) - Improved Analysis of Clipping Algorithms for Non-convex Optimization [19.507750439784605]
最近、citetzhang 2019gradient show that clipped (stochastic) Gradient Descent (GD) converges faster than vanilla GD/SGD。
実験は、深層学習におけるクリッピングに基づく手法の優位性を確認する。
論文 参考訳(メタデータ) (2020-10-05T14:36:59Z) - Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。
原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。
underline Decentralized with compression, LEAD。
論文 参考訳(メタデータ) (2020-07-01T04:35:00Z) - Unified Analysis of Stochastic Gradient Methods for Composite Convex and
Smooth Optimization [15.82816385434718]
本稿では、滑らかで凸な損失と凸正則化器を最小化するための勾配アルゴリズムの収束解析のための統一定理を提案する。
我々は、Gorbunov, Hanzely & Richt'arik (2020) の統一解析を拡張し、損失関数が強く凸であるという要求を下げる。
我々の統一解析は、近位SGD、分散還元法、量子化、およびいくつかの座標降下型法などの既存のアルゴリズムのホストに適用できる。
論文 参考訳(メタデータ) (2020-06-20T13:40:27Z) - On Distributed Non-convex Optimization: Projected Subgradient Method For
Weakly Convex Problems in Networks [13.385373310554327]
Moreau subgradient 法は、機械学習における線形シャープネス問題を収束させる。
理論的保証を伴う下位段階法の分散実装を提案する。
論文 参考訳(メタデータ) (2020-04-28T01:01:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。