論文の概要: Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity

• arxiv url: http://arxiv.org/abs/2206.00973v3
• Date: Sat, 31 Aug 2024 13:59:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-04 23:16:54.107829
• Title: Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity
• Title（参考訳）: 局所リプシッツ連続性下における単調包有物の一次二重外挿法
• Authors: Zhaosong Lu, Sanyou Mei,
• Abstract要約: 単調な包摂問題の解法として, 単調な外挿法を提案する。 提案手法は$cal O(log epsilon-1)$の演算複雑性を享受する。 また、凸円錐最適化の $varepsilon$-KKT や $varepsilon$-residual の解を求めるためにも得られる。
• 参考スコア（独自算出の注目度）: 1.0742675209112622
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we consider a class of monotone inclusion (MI) problems of finding a zero of the sum of two monotone operators, in which one operator is maximal monotone while the other is {\it locally Lipschitz} continuous. We propose primal-dual extrapolation methods to solve them using a point and operator extrapolation technique, whose parameters are chosen by a backtracking line search scheme. The proposed methods enjoy an operation complexity of ${\cal O}(\log \epsilon^{-1})$ and ${\cal O}(\epsilon^{-1}\log \epsilon^{-1})$, measured by the number of fundamental operations consisting only of evaluations of one operator and resolvent of the other operator, for finding an $\varepsilon$-residual solution of strongly and non-strongly MI problems, respectively. The latter complexity significantly improves the previously best operation complexity ${\cal O}(\varepsilon^{-2})$. As a byproduct, complexity results of the primal-dual extrapolation methods are also obtained for finding an $\varepsilon$-KKT or $\varepsilon$-residual solution of convex conic optimization, conic constrained saddle point, and variational inequality problems under {\it local Lipschitz} continuity. We provide preliminary numerical results to demonstrate the performance of the proposed methods.
• Abstract（参考訳）: 本稿では、2つの単調作用素の和の零点を求めるような単調包含(MI)問題のクラスについて考察する。 本稿では,バックトラックライン探索方式によってパラメータが選択される点外挿法と演算子外挿法を用いて,2次元外挿法を提案する。 提案手法の演算複雑性は${\cal O}(\log \epsilon^{-1})$と${\cal O}(\epsilon^{-1}\log \epsilon^{-1})$で、それぞれ強いMI問題に対する$\varepsilon$-residual解を見つけるために、一方の演算子と他方の演算子の分解剤のみからなる基本演算数で測定される。 後者の複雑さは、以前最高の演算複雑性である${\cal O}(\varepsilon^{-2})$を大幅に改善する。 副生成物として、原始双対外挿法の複雑性結果は、凸円錐最適化、円錐制約サドル点、および局所リプシッツ連続性の下での変分不等式問題の$\varepsilon$-KKT あるいは$\varepsilon$-Residual解を求めるためにも得られる。 提案手法の性能を実証するために,予備的な数値計算結果を提案する。

関連論文リスト

• Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
  そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。 我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• 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)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• 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)
• A Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusion Problems [17.597000481404883]
  機械学習アプリケーションで広く見られるモノトーン包摂問題について検討する。 我々のアルゴリズムは、$mathcalO(frac1epsilon3)$演算子の評価で演算子に$epsilon$ノルムを得る。
  論文  参考訳（メタデータ） (2022-03-17T16:48:57Z)
• 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)
• 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)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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