論文の概要: Accelerated Single-Call Methods for Constrained Min-Max Optimization
- arxiv url: http://arxiv.org/abs/2210.03096v1
- Date: Thu, 6 Oct 2022 17:50:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 18:04:36.888762
- Title: Accelerated Single-Call Methods for Constrained Min-Max Optimization
- Title（参考訳）: 制約付き最小値最適化のための高速化シングルコール法
- Authors: Yang Cai, Weiqiang Zheng
- Abstract要約: メソッドは、各イテレーションで2つの呼び出しか2つのプロジェクションを必要とする。
我々は、最適勾配 (OG) が acavefrac1sqrtT)$ の制約付き凸コライト min-max 最適化に対する最終研究収束率を持つことを示す。
また, 負のコモノトニック性を満たす包摂問題に対する最適$O(frac1T)収束率をARG法で達成することを示す。
- 参考スコア（独自算出の注目度）: 5.266784779001398
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study first-order methods for constrained min-max optimization. Existing
methods either requires two gradient calls or two projections in each
iteration, which may be costly in applications. In this paper, we first show
that the Optimistic Gradient (OG) method, a single-call single-projection
algorithm, has $O(\frac{1}{\sqrt{T}})$ convergence rate for inclusion problems
with operators that satisfy the weak Minty variation inequality (MVI). Our
second result is the first single-call single-projection algorithm -- the
Accelerated Reflected Gradient (ARG) method that achieves the optimal
$O(\frac{1}{T})$ convergence rate for inclusion problems that satisfy negative
comonotonicity. Both the weak MVI and negative comonotonicity are well-studied
assumptions and capture a rich set of non-convex non-concave min-max
optimization problems. Finally, we show that the Reflected Gradient (RG)
method, another single-call single-projection algorithm, has
$O(\frac{1}{\sqrt{T}})$ last-iterate convergence rate for constrained
convex-concave min-max optimization, answering an open problem of [Hsieh et al,
2019].
- Abstract（参考訳）: 制約最小値最適化のための一階法について検討する。
既存のメソッドは、各イテレーションで2つのグラデーションコールまたは2つのプロジェクションを必要とする。
本稿では,単射単射影アルゴリズムである楽観的勾配 (og) 法は,弱ミント変分不等式 (mvi) を満たす演算子を用いた包含問題に対して$o(\frac{1}{\sqrt{t}})$ の収束率を持つことを示す。
第二の結果は、最初の単呼単射アルゴリズムである Accelerated Reflected Gradient (ARG) 法であり、負のコモノトニック性を満たす包摂問題に対する最適$O(\frac{1}{T})$収束率を達成する。
弱いMVIと負のコモノトニック性はともによく研究された仮定であり、非凸なmin-max最適化問題のリッチな集合を捉えている。
最後に、リフレクテッド・グラディエント(RG)法は、別の単発単発単射アルゴリズムであり、制約付き凸凸凹最小値最適化における最終点収束率を$O(\frac{1}{\sqrt{T}}) とし、[Hsieh et al, 2019] の開問題に答えることを示した。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion [9.551565016483833]
非コンケーブなmin-max最適化問題の構造化クラスであるコモノトンmin-max最適化について検討する。
最初のコントリビューションでは、extra Anchored Gradient (EAG)アルゴリズムを制約付きコモノトン min-max 最適化に拡張する。
第2のコントリビューションでは、FEG(Fast Extra Gradient)アルゴリズムを制約のないmin-max最適化に拡張する。
論文 参考訳（メタデータ） (2022-06-10T17:44:06Z) - Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-03T14:39:33Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。