論文の概要: Accelerated Single-Call Methods for Constrained Min-Max Optimization
- arxiv url: http://arxiv.org/abs/2210.03096v2
- Date: Sun, 14 May 2023 20:11:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-17 00:33:06.696458
- Title: Accelerated Single-Call Methods for Constrained Min-Max Optimization
- Title（参考訳）: 制約付き最小値最適化のための高速化シングルコール法
- Authors: Yang Cai, Weiqiang Zheng
- Abstract要約: 既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。
本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。
私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
- 参考スコア（独自算出の注目度）: 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 require two gradient calls or two projections in each iteration,
which may be costly in some applications. In this paper, we first show that a
variant of the Optimistic Gradient (OG) method, a single-call single-projection
algorithm, has $O(\frac{1}{\sqrt{T}})$ best-iterate 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})$ last-iterate 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
[Heish et al, 2019]. Our convergence rates hold for standard measures such as
the tangent residual and the natural residual.
- Abstract（参考訳）: 制約最小値最適化のための一階法について検討する。
既存のメソッドは、各イテレーションで2つのグラデーションコールまたは2つのプロジェクションを必要とする。
本稿では,単射単射影アルゴリズムである楽観的勾配法 (og) の変種が,弱いミント変分不等式 (mvi) を満たす演算子を持つ包含問題に対して$o(\frac{1}{\sqrt{t}})$ のベストイテレート収束率を持つことを示す。
第二の結果は、最初の単呼単射アルゴリズムである Accelerated Reflected Gradient (ARG) 法であり、負のコモノトニック性を満たす包摂問題に対する最適$O(\frac{1}{T})$の最終点収束率を達成する。
弱いMVIと負のコモノトニック性はともによく研究された仮定であり、非凸なmin-max最適化問題のリッチな集合を捉えている。
最後に,single-call single-projectionアルゴリズムであるreflection gradient (rg)法は,制約付き凸凸凸min-max最適化に対して$o(\frac{1}{\sqrt{t}})$ last-iterate convergence rateを持つことを示す。
我々の収束率は、接残差や自然残差などの標準測度を定めている。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。