論文の概要: 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 を求める複雑性結果を得る。
我々の知る限りでは、局所的なリプシッツ連続性の下で上記の問題を解決するための複雑さを保証した手法を検討する以前の研究は行われなかった。
本論文で得られた複雑さはすべて全く新しいものである。
関連論文リスト
- Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。
我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。
我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
論文 参考訳(メタデータ) (2023-10-04T17:24:45Z) - Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
我々は分散環境でスティーフェル多様体に焦点をあて、$nMn log-1)$のエージェントの連結ネットワークをテストする。
そこで本研究では,nMn log-1 以下の自然ステーションを強制的に強制する分散下位段階法 (DRSM)$ という手法を提案する。
論文 参考訳(メタデータ) (2023-03-31T02:56:23Z) - A Newton-CG based barrier-augmented Lagrangian method for general
nonconvex conic optimization [77.8485863487028]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳(メタデータ) (2022-09-12T06:53:24Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳(メタデータ) (2022-06-30T02:17:11Z) - 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) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion
and Strong Solutions to Variational Inequalities [14.848525762485872]
非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。
これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
論文 参考訳(メタデータ) (2020-02-20T17:12:49Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳(メタデータ) (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。