論文の概要: Higher-order methods for convex-concave min-max optimization and
monotone variational inequalities
- arxiv url: http://arxiv.org/abs/2007.04528v1
- Date: Thu, 9 Jul 2020 03:12:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 03:59:13.544929
- Title: Higher-order methods for convex-concave min-max optimization and
monotone variational inequalities
- Title(参考訳): 凸凸min-max最適化の高次法と単調変分不等式
- Authors: Brian Bullins and Kevin A. Lai
- Abstract要約: 制約付き凸凹 min-max 問題に対する収束率の改善と高次滑らかな単調変分不等式を提供する。
p>2$の場合、ネミロフスキーの1階ミラープロキシ法の反復複雑性を改善する。
さらに、制約のない$p=2$ケースでアルゴリズム全体をインスタンス化する。
- 参考スコア(独自算出の注目度): 7.645449711892907
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide improved convergence rates for constrained convex-concave min-max
problems and monotone variational inequalities with higher-order smoothness. In
min-max settings where the $p^{th}$-order derivatives are Lipschitz continuous,
we give an algorithm HigherOrderMirrorProx that achieves an iteration
complexity of $O(1/T^{\frac{p+1}{2}})$ when given access to an oracle for
finding a fixed point of a $p^{th}$-order equation. We give analogous rates for
the weak monotone variational inequality problem. For $p>2$, our results
improve upon the iteration complexity of the first-order Mirror Prox method of
Nemirovski [2004] and the second-order method of Monteiro and Svaiter [2012].
We further instantiate our entire algorithm in the unconstrained $p=2$ case.
- Abstract(参考訳): 制約付き凸凹 min-max 問題に対する収束率の改善と高次滑らかな単調変分不等式を提供する。
p^{th}$次微分がリプシッツ連続であるmin-maxの設定では、$p^{th}$次方程式の不動点を見つけるためにオラクルへのアクセスが与えられると、反復複雑性が$o(1/t^{\frac{p+1}{2}}) となるアルゴリズムhigherordermirrorproxを与える。
弱単調変分不等式問題に対して類似率を与える。
p>2$の場合、nemirovski [2004] の 1-order mirror prox 法と monteiro と svaiter [2012] の 2-order method の反復複雑性を改善する。
さらに、制約のない$p=2$ケースでアルゴリズム全体をインスタンス化する。
関連論文リスト
- Extending the Reach of First-Order Algorithms for Nonconvex Min-Max
Problems with Cohypomonotonicity [20.710343135282123]
我々は$fracKMLotonicity が弱MVrhon$coords または弱MVrhonLotonicity または弱MVrhonKML$ を保証することを予想する。
また、同じ範囲の$$の場合には、アルゴリズムや複雑性の保証も提供します。
論文 参考訳(メタデータ) (2024-02-07T18:22:41Z) - Beyond first-order methods for non-convex non-concave min-max
optimization [6.097141897343098]
モノトーンおよびミンティ条件設定を超える改善が達成できることを示す。
具体的には、離散時間最小化の新しい理解を提供する。
離散時間設定に適合する連続時間解析を提示する。
論文 参考訳(メタデータ) (2023-04-17T15:55:40Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (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) - Perseus: A Simple and Optimal High-Order Method for Variational
Inequalities [81.32967242727152]
VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。
そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
論文 参考訳(メタデータ) (2022-05-06T13:29:14Z) - Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
この楽観的な手法は凸凹点問題の解法として人気が高まっている。
我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
論文 参考訳(メタデータ) (2022-02-19T20:31:05Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳(メタデータ) (2022-02-09T06:05:38Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:19:30Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳(メタデータ) (2020-06-24T04:41:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。