論文の概要: A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for
Nonconvex-Concave Min-Max Problems
- arxiv url: http://arxiv.org/abs/2010.15768v2
- Date: Mon, 4 Jul 2022 23:17:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-01 23:47:05.487007
- Title: A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for
Nonconvex-Concave Min-Max Problems
- Title（参考訳）: 非凸凹最小値問題に対する単ループ平滑勾配勾配勾配アルゴリズム
- Authors: Jiawei Zhang, Peijun Xiao, Ruoyu Sun and Zhi-Quan Luo
- Abstract要約: 非con-max問題は、このロバストな問題を解決するために、ポイントワイズな非函数の集合を最小化するなど、多くのアプリケーションで発生する。
A.A.アルゴリズムは、有限個の非函数の集合に対して$(/A-O-)の$(/A-O-)を達成できる。
- 参考スコア（独自算出の注目度）: 33.83671897619922
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nonconvex-concave min-max problem arises in many machine learning
applications including minimizing a pointwise maximum of a set of nonconvex
functions and robust adversarial training of neural networks. A popular
approach to solve this problem is the gradient descent-ascent (GDA) algorithm
which unfortunately can exhibit oscillation in case of nonconvexity. In this
paper, we introduce a "smoothing" scheme which can be combined with GDA to
stabilize the oscillation and ensure convergence to a stationary solution. We
prove that the stabilized GDA algorithm can achieve an $O(1/\epsilon^2)$
iteration complexity for minimizing the pointwise maximum of a finite
collection of nonconvex functions. Moreover, the smoothed GDA algorithm
achieves an $O(1/\epsilon^4)$ iteration complexity for general
nonconvex-concave problems. Extensions of this stabilized GDA algorithm to
multi-block cases are presented. To the best of our knowledge, this is the
first algorithm to achieve $O(1/\epsilon^2)$ for a class of nonconvex-concave
problem. We illustrate the practical efficiency of the stabilized GDA algorithm
on robust training.
- Abstract（参考訳）: 非凸-凸 min-max 問題は、一連の非凸関数のポイントワイド最大値の最小化や、ニューラルネットワークの堅牢な逆トレーニングを含む、多くの機械学習アプリケーションで発生する。
この問題を解決する一般的なアプローチは勾配降下・上昇(gda)アルゴリズムであり、不運にも非凸の場合の振動を示すことができる。
本稿では,振動の安定化と定常解の収束を確保するため,GDAと組み合わせることができる「平滑化」方式を提案する。
安定化gdaアルゴリズムは、非凸関数の有限集合のポイントワイズ最大を最小化するために、$o(1/\epsilon^2)$の反復複雑性を実現できることを証明した。
さらに、スムーズなGDAアルゴリズムは一般的な非凸凹問題に対して$O(1/\epsilon^4)$反復複雑性を実現する。
この安定化GDAアルゴリズムのマルチブロックケースへの拡張を示す。
我々の知る限りでは、これは非凸凹問題のクラスに対して$O(1/\epsilon^2)$を達成した最初のアルゴリズムである。
本稿では,安定GDAアルゴリズムのロバストトレーニングにおける実用性について述べる。
関連論文リスト
- Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for
Nonconvex Minimax Problems with Coupled linear Constraints [3.898056433020865]
線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。
我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
論文 参考訳（メタデータ） (2024-01-26T11:22:13Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for
Nonconvex Functional Constrained Optimization [27.07082875330508]
制約のない不等式問題は、マルチクラスネイマンオラクルのような多くの機械学習問題をモデル化するために用いられる。
このような緩やかな規則性の条件下では、値損失の交互化と制約違反の低減のバランスをとることは困難である。
本稿では,新しい不等式制約問題アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-12T16:30:34Z) - Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex
Minimax Machine Learning [12.069630105460766]
AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。
本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-22T04:33:27Z) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳（メタデータ） (2021-08-01T15:23:49Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文 参考訳（メタデータ） (2020-06-03T04:00:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。