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

• arxiv url: http://arxiv.org/abs/2205.03202v6
• Date: Thu, 15 Feb 2024 01:00:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-17 00:22:23.668003
• Title: Perseus: A Simple and Optimal High-Order 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 を見つける。 そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
• 参考スコア（独自算出の注目度）: 81.32967242727152
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper settles an open and challenging question pertaining to the design of simple and optimal high-order 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}$. We consider the setting in which $F$ is smooth with up to $(p-1)^{th}$-order derivatives. For $p = 2$, the cubic regularized Newton method was extended to VIs with a global rate of $O(\epsilon^{-1})$. An improved rate of $O(\epsilon^{-2/3}\log\log(1/\epsilon))$ can be obtained via an alternative second-order method, but this method requires a nontrivial line-search procedure as an inner loop. Similarly, high-order methods based on line-search procedures have been shown to achieve a rate of $O(\epsilon^{-2/(p+1)}\log\log(1/\epsilon))$. As emphasized by Nesterov, however, such procedures do not necessarily imply practical applicability in large-scale applications, and it would be desirable to complement these results with a simple high-order VI method that retains the optimality of the more complex methods. We propose a $p^{th}$-order method that does \textit{not} require any line search procedure and provably converges to a weak solution at a rate of $O(\epsilon^{-2/(p+1)})$. We prove that our $p^{th}$-order method is optimal in the monotone setting by establishing a matching lower bound under a generalized linear span assumption. Our method with restarting attains a linear rate for smooth and uniformly monotone VIs and a local superlinear rate for smooth and strongly monotone VIs. Our method also achieves a global rate of $O(\epsilon^{-2/p})$ for solving smooth and nonmonotone VIs satisfying the Minty condition and when augmented with restarting it attains a global linear and local superlinear rate for smooth and nonmonotone VIs satisfying the uniform/strong Minty condition.
• Abstract（参考訳）: 本稿では、スムーズかつ単調な変分不等式(VIs)を解くための単純で最適な高次法の設計に関するオープンで挑戦的な問題を解決する。 VI は$x^\star \in \mathcal{X}$ を$\langle F(x), x - x^\star\rangle \geq 0$ とする。 我々は、$f$が最大$(p-1)^{th}$次微分を持つ滑らかな設定を考える。 p = 2$ の場合、立方体正規化ニュートン法を vis に拡張し、グローバルレートは $o(\epsilon^{-1})$ である。 改良された$O(\epsilon^{-2/3}\log\log(1/\epsilon))$は、代替の2階法によって得ることができるが、この方法は内部ループとして非自明な線探索手順を必要とする。 同様に、行探索手順に基づく高階法では、$o(\epsilon^{-2/(p+1)}\log\log(1/\epsilon))$となることが示されている。 しかし、Nesterovが強調したように、このような手順は必ずしも大規模アプリケーションに実用的な適用性を示すものではなく、より複雑な手法の最適性を保った単純な高階VI法でこれらの結果を補完することが望ましい。 我々は、$O(\epsilon^{-2/(p+1)})$の速度で、行探索手順を必要とせず、確実に弱解に収束する、$p^{th}$-order法を提案する。 p^{th}$-次法は一般線形スパン仮定の下で一致した下界を確立することによって単調設定において最適であることを示す。 本手法は,滑らかで均一な単調visの線形速度と,滑らかで強い単調visの局所超線形速度を達成する。 また,Minty条件を満たすスムーズかつ非モノトン VI の解法として約$O(\epsilon^{-2/p})$のグローバルレートを達成し,再起動によって拡張された場合,均一・強いミンティ条件を満たすスムーズかつ非モノトン VI に対して大域的線形および局所超線形レートを達成する。

関連論文リスト

• 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)

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

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