論文の概要: Perseus: A Simple High-Order Regularization Method for Variational Inequalities

• arxiv url: http://arxiv.org/abs/2205.03202v1
• Date: Fri, 6 May 2022 13:29:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-09 14:26:31.269356
• Title: Perseus: A Simple High-Order Regularization Method for Variational Inequalities
• Title（参考訳）: Perseus: 変分不等式に対する簡易な高次規則化法
• Authors: Tianyi Lin and Michael. I. Jordan
• Abstract要約: VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。 citetNesterov-2006-Constrained は立方体正規化ニュートン法を、グローバルレート$O(epsilon-1)$で VI に拡張した。 citetMonteiro-2012-Iterationは、改善率を達成した別の2階法を提案した。
• 参考スコア（独自算出の注目度）: 102.08678737900541
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper settles an open and challenging question pertaining to the design of simple high-order regularization methods for solving smooth and monotone variational inequalities (VIs). A VI involves finding $x^\star \in \mathcal{X}$ such that $\langle F(x), x - x^\star\rangle \geq 0$ for all $x \in \mathcal{X}$ and we consider the setting where $F: \mathbb{R}^d \mapsto \mathbb{R}^d$ is smooth with up to $(p-1)^{th}$-order derivatives. For the case of $p = 2$,~\citet{Nesterov-2006-Constrained} extended the cubic regularized Newton's method to VIs with a global rate of $O(\epsilon^{-1})$. \citet{Monteiro-2012-Iteration} proposed another second-order method which achieved an improved rate of $O(\epsilon^{-2/3}\log(1/\epsilon))$, but this method required a nontrivial binary search procedure as an inner loop. High-order methods based on similar binary search procedures have been further developed and shown to achieve a rate of $O(\epsilon^{-2/(p+1)}\log(1/\epsilon))$. However, such search procedure can be computationally prohibitive in practice and the problem of finding a simple high-order regularization methods remains as an open and challenging question in optimization theory. We propose a $p^{th}$-order method which does \textit{not} require any binary search scheme and is guaranteed to converge to a weak solution with a global rate of $O(\epsilon^{-2/(p+1)})$. A version with restarting attains a global linear and local superlinear convergence rate for smooth and strongly monotone VIs. Further, our method achieves a global rate of $O(\epsilon^{-2/p})$ for solving smooth and non-monotone VIs satisfying the Minty condition; moreover, the restarted version again attains a global linear and local superlinear convergence rate if the strong Minty condition holds.
• Abstract（参考訳）: 本稿では、スムーズかつ単調な変分不等式(VIs)を解くための単純な高次正則化法の設計に関するオープンで挑戦的な問題を解決する。 VI は$x^\star \in \mathcal{X}$ を$\langle F(x), x - x^\star\rangle \geq 0$ for all $x \in \mathcal{X}$ とし、$F: \mathbb{R}^d \mapsto \mathbb{R}^d$ が$(p-1)^{th}$-階微分で滑らかであるような設定を考える。 p = 2$,~\citet{nesterov-2006-constrained} の場合、立方体正規化ニュートン法を vis に拡張し、グローバルレートは $o(\epsilon^{-1})$ である。 \citet{Monteiro-2012-Iteration} は$O(\epsilon^{-2/3}\log(1/\epsilon))$を改良した別の2階法を提案したが、この方法は内部ループとして非自明な二項探索手順を必要とした。 類似した二項探索手順に基づく高階法がさらに開発され、$o(\epsilon^{-2/(p+1)}\log(1/\epsilon))$となることが示されている。 しかし、そのような探索手順は実際は計算が禁止され、単純な高次正規化法を見つけるという問題は、最適化理論においてオープンで挑戦的な問題として残されている。 我々は、$p^{th}$-orderメソッドを提案し、これは \textit{not} が任意のバイナリ検索スキームを必要とし、大域レート$O(\epsilon^{-2/(p+1)})$で弱解に収束することを保証している。 再スタートを伴うバージョンは、滑らかで強い単調 vis に対する大域的な線形および局所超線形収束率を達成する。 さらに,Minty条件を満たすスムーズかつ非モノトン VI の解法として大域的な$O(\epsilon^{-2/p})$を達成し,さらに,強いMinty条件が成立すれば,再起動版が再び大域的線形および局所超線形収束率を達成する。

関連論文リスト

• 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)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
  我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。 提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。 我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
  論文  参考訳（メタデータ） (2024-05-09T15:53:43Z)
• 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)
• Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity [15.18055488087588]
  上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。 我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
  論文  参考訳（メタデータ） (2022-08-07T20:53:42Z)
• Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
  双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。 Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
  論文  参考訳（メタデータ） (2022-01-19T05:56:19Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。