論文の概要: Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity with applications to variational inequality, conic constrained saddle point, and convex conic optimization problems

• arxiv url: http://arxiv.org/abs/2206.00973v1
• Date: Thu, 2 Jun 2022 10:31:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-03 14:04:17.679662
• Title: Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity with applications to variational inequality, conic constrained saddle point, and convex conic optimization problems
• Title（参考訳）: 局所リプシッツ連続性の下での単調包有物の主双対外挿法と変分不等式、円錐制約サドル点、凸錐最適化問題への応用
• Authors: Zhaosong Lu and Sanyou Mei
• Abstract要約: 2つの単調作用素の和の零点を求めることからなる構造的単調包含問題(MI)のクラスを考える。 まず,従来の前方分割法を改良し,構造化されたMI問題を解くためのPDE法を提案する。 次に、上記のPDE法を適用して、構造化された強いMI問題の列を近似的に解くことで、構造化された非強MI問題を解く別のPDE法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we consider a class of structured monotone inclusion (MI) problems that consist of finding a zero in the sum of two monotone operators, in which one is maximal monotone while another is locally Lipschitz continuous. In particular, we first propose a primal-dual extrapolation (PDE) method for solving a structured strongly MI problem by modifying the classical forward-backward splitting method by using a point and operator extrapolation technique, in which the parameters are adaptively updated by a backtracking line search scheme. The proposed PDE method is almost parameter-free, equipped with a verifiable termination criterion, and enjoys an operation complexity of ${\cal O}(\log \epsilon^{-1})$, measured by the amount of fundamental operations consisting only of evaluations of one operator and resolvent of another operator, for finding an $\epsilon$-residual solution of the structured strongly MI problem. We then propose another PDE method for solving a structured non-strongly MI problem by applying the above PDE method to approximately solve a sequence of structured strongly MI problems. The resulting PDE method is parameter-free, equipped with a verifiable termination criterion, and enjoys an operation complexity of ${\cal O}(\epsilon^{-1}\log \epsilon^{-1})$ for finding an $\epsilon$-residual solution of the structured non-strongly MI problem. As a consequence, we apply the latter PDE method to convex conic optimization, conic constrained saddle point, and variational inequality problems, and obtain complexity results for finding an $\epsilon$-KKT or $\epsilon$-residual solution of them under local Lipschitz continuity. To the best of our knowledge, no prior studies were conducted to investigate methods with complexity guarantees for solving the aforementioned problems under local Lipschitz continuity. All the complexity results obtained in this paper are entirely new.
• Abstract（参考訳）: 本稿では, 2 つの単調作用素の和で 0 を見つけ, 1 を極大単調,もう 1 を局所リプシッツ連続とする構造的単調包含問題 (mi) のクラスを考える。 特に,まず,各パラメータをバックトラックライン探索方式により適応的に更新する点と演算子外挿手法を用いて,古典的前方後方分割法を改良することにより,構造化された強mi問題を解くためのpde(primal-dual extrapolation)法を提案する。 提案手法は, ほぼパラメータフリーであり, 検証可能な終端基準を備えており, 1 つの演算子と他の演算子の分解剤のみからなる基本演算量から, 構成された強い MI 問題の$\epsilon$-Residual解を求めると, 演算複雑性が$$${\cal O}(\log \epsilon^{-1})$となる。 次に、上記のPDE法を適用して、構造化された非強MI問題を解くための別のPDE法を提案する。 得られたPDE法はパラメータフリーで、検証可能な終端基準を備え、構造化された非強MI問題の$\epsilon$-residual解を求めるために$${\cal O}(\epsilon^{-1}\log \epsilon^{-1})$の演算複雑性を享受する。 その結果、円錐最適化、円錐制約サドル点、変分不等式問題に対して後者のPDE法を適用し、局所リプシッツ連続性の下でのこれらの解の$\epsilon$-KKT あるいは $\epsilon$-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)

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

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