論文の概要: 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$ケースでアルゴリズム全体をインスタンス化する。
関連論文リスト
- First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。
線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
論文 参考訳（メタデータ） (2024-06-18T16:41:21Z) - Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。
解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
論文 参考訳（メタデータ） (2024-02-07T18:22:41Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - 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) - 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 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。