論文の概要: Extragradient-Type Methods with $\mathcal{O} (1/k)$ Last-Iterate
Convergence Rates for Co-Hypomonotone Inclusions
- arxiv url: http://arxiv.org/abs/2302.04099v2
- Date: Sat, 14 Oct 2023 14:57:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 06:10:05.266398
- Title: Extragradient-Type Methods with $\mathcal{O} (1/k)$ Last-Iterate
Convergence Rates for Co-Hypomonotone Inclusions
- Title(参考訳): Co-ヒポモノトン包有物に対する$\mathcal{O} (1/k)$Last-Iterate Convergence Ratesの漸進型法
- Authors: Quoc Tran-Dinh
- Abstract要約: 我々は、コヒポモノトン包摂の解を近似するために、よく知られた過次法(英語版)の2つの「ネステロフ加速」変種を開発した。
我々の結果は、ルートフィリング問題に対する最近のハルパーン型手法の代替と見なすことができる。
- 参考スコア(独自算出の注目度): 8.0153031008486
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We develop two "Nesterov's accelerated" variants of the well-known
extragradient method to approximate a solution of a co-hypomonotone inclusion
constituted by the sum of two operators, where one is Lipschitz continuous and
the other is possibly multivalued. The first scheme can be viewed as an
accelerated variant of Tseng's forward-backward-forward splitting (FBFS)
method, while the second one is a Nesterov's accelerated variant of the "past"
FBFS scheme, which requires only one evaluation of the Lipschitz operator and
one resolvent of the multivalued mapping. Under appropriate conditions on the
parameters, we theoretically prove that both algorithms achieve
$\mathcal{O}(1/k)$ last-iterate convergence rates on the residual norm, where
$k$ is the iteration counter. Our results can be viewed as alternatives of a
recent class of Halpern-type methods for root-finding problems. For comparison,
we also provide a new convergence analysis of the two recent extra-anchored
gradient-type methods for solving co-hypomonotone inclusions.
- Abstract(参考訳): 2つの演算子の和によって構成される共ハイポモノトン包含の解を近似するために、よく知られた超勾配法の2つの「ネステロフ加速」変種を開発し、一方はリプシッツ連続であり、もう一方は多値である可能性がある。
第1のスキームは tseng の forward-backward-forward split (fbfs) 法の高速化変種と見なすことができ、第2のスキームは "past" fbfs のネステロフの加速変種であり、リプシッツ作用素の1つの評価と多値写像の1つの解法のみを必要とする。
パラメータの適切な条件の下で、理論上、両方のアルゴリズムが残差ノルム上で$\mathcal{o}(1/k)$ last-iterate convergence rate を達成することを証明している。
この結果は,近年の根探り問題に対するhalpern型手法の代替案と見なすことができる。
比較のために, 共ハイポモノトン包含物を解くために, 最近の2つのアンコレード勾配型手法の新しい収束解析も提供する。
関連論文リスト
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳(メタデータ) (2023-12-13T21:41:06Z) - A Unified Analysis for the Subgradient Methods Minimizing Composite
Nonconvex, Nonsmooth and Non-Lipschitz Functions [8.960341489080609]
非Lipschitzおよび非滑らかな最適化問題の文脈における新しい収束解析を提案する。
論文で導入すべき下次上界条件のいずれかの下では、$O (1/stqrT)$がエンベロープ関数の平方勾配で成り立つことを示し、さらに1/2$指数を持つ一様KL条件が成り立つ場合、$O (1/T)$に改善される。
論文 参考訳(メタデータ) (2023-08-30T23:34:11Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳(メタデータ) (2022-09-12T06:53:24Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum
Optimization [7.014966911550542]
スパースサブ構造を検索するために,非滑らかな正規化を伴うディープニューラルネットワークをトレーニングする問題を考察する。
我々は、収束と最悪のケースの複雑さが勾配のリプシッツ定数の知識や近似なしで確立されるSR2と呼ばれる新しい解法を導出する。
CIFAR-10とCIFAR-100で訓練されたネットワークインスタンスの実験により、SR2はProxGENやProxSGDのような関連する手法よりも常に高い空間性と精度を達成することが示された。
論文 参考訳(メタデータ) (2022-06-14T00:28:44Z) - Halpern-Type Accelerated and Splitting Algorithms For Monotone
Inclusions [14.445131747570962]
我々は、最大単調方程式のクラスを解くために、新しいタイプの加速アルゴリズムを開発する。
我々の手法は[32]におけるハルパーン型固定点反復と呼ばれるものに依存しており、近年多くの研究者が利用している。
論文 参考訳(メタデータ) (2021-10-15T15:26:32Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳(メタデータ) (2020-03-03T03:59:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。