論文の概要: Halpern-Type Accelerated and Splitting Algorithms For Monotone
Inclusions
- arxiv url: http://arxiv.org/abs/2110.08150v1
- Date: Fri, 15 Oct 2021 15:26:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-18 16:58:33.773352
- Title: Halpern-Type Accelerated and Splitting Algorithms For Monotone
Inclusions
- Title(参考訳): モノトン包摂に対するハルパーン型加速分割アルゴリズム
- Authors: Quoc Tran-Dinh and Yang Luo
- Abstract要約: 我々は、最大単調方程式のクラスを解くために、新しいタイプの加速アルゴリズムを開発する。
我々の手法は[32]におけるハルパーン型固定点反復と呼ばれるものに依存しており、近年多くの研究者が利用している。
- 参考スコア(独自算出の注目度): 14.445131747570962
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we develop a new type of accelerated algorithms to solve some
classes of maximally monotone equations as well as monotone inclusions. Instead
of using Nesterov's accelerating approach, our methods rely on a so-called
Halpern-type fixed-point iteration in [32], and recently exploited by a number
of researchers, including [24, 70]. Firstly, we derive a new variant of the
anchored extra-gradient scheme in [70] based on Popov's past extra-gradient
method to solve a maximally monotone equation $G(x) = 0$. We show that our
method achieves the same $\mathcal{O}(1/k)$ convergence rate (up to a constant
factor) as in the anchored extra-gradient algorithm on the operator norm $\Vert
G(x_k)\Vert$, , but requires only one evaluation of $G$ at each iteration,
where $k$ is the iteration counter. Next, we develop two splitting algorithms
to approximate a zero point of the sum of two maximally monotone operators. The
first algorithm originates from the anchored extra-gradient method combining
with a splitting technique, while the second one is its Popov's variant which
can reduce the per-iteration complexity. Both algorithms appear to be new and
can be viewed as accelerated variants of the Douglas-Rachford (DR) splitting
method. They both achieve $\mathcal{O}(1/k)$ rates on the norm $\Vert
G_{\gamma}(x_k)\Vert$ of the forward-backward residual operator
$G_{\gamma}(\cdot)$ associated with the problem. We also propose a new
accelerated Douglas-Rachford splitting scheme for solving this problem which
achieves $\mathcal{O}(1/k)$ convergence rate on $\Vert G_{\gamma}(x_k)\Vert$
under only maximally monotone assumptions. Finally, we specify our first
algorithm to solve convex-concave minimax problems and apply our accelerated DR
scheme to derive a new variant of the alternating direction method of
multipliers (ADMM).
- Abstract(参考訳): 本稿では,最大単調方程式のクラスと単調包摂関数のクラスを解くために,新しいタイプの加速アルゴリズムを開発する。
nesterovの高速化アプローチを使う代わりに、この手法は[32]でhalpern型固定点反復と呼ばれるものに依存しており、最近では[24,70]を含む多くの研究者によって活用されている。
まず, [70] におけるアンカー付き超勾配スキームの新しい変種をポポフの過去の超勾配法に基づいて導出し, 極大単調方程式 $g(x) = 0$ を解く。
我々は,演算子のノルムである$\Vert G(x_k)\Vert$ の固定外勾配アルゴリズムと同じ$\mathcal{O}(1/k)$収束率(定数係数まで)を達成するが,各イテレーションにおいて$k$が反復カウンタである場合,$G$の1つの評価しか必要としないことを示す。
次に、2つの最大単調作用素の和の零点を近似する2つの分割アルゴリズムを開発する。
第1のアルゴリズムは、分割技法と組み合わせたアンカー付き超勾配法から派生し、第2のアルゴリズムはポポフの変種であり、イテレーション毎の複雑性を低減できる。
どちらのアルゴリズムも新しいようで、ダグラス・ラフフォード(DR)分割法の加速変種と見なすことができる。
どちらも、問題に関連する前向き残留作用素 $G_{\gamma}(\cdot)$ のノルム $\Vert G_{\gamma}(x_k)\Vert$ で $\mathcal{O}(1/k)$ を達成する。
また, 最大単調仮定下での$\vert g_{\gamma}(x_k)\vert$ 上の$\mathcal{o}(1/k)$ 収束率を達成するための, 新たな加速ダグラス・ラッチフォード分割スキームを提案する。
最後に、凸凹極小問題を解くための最初のアルゴリズムを特定し、加速DRスキームを適用して乗算器の交互方向法(ADMM)の新しい変種を導出する。
関連論文リスト
- Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳(メタデータ) (2024-01-14T14:14:19Z) - First and zeroth-order implementations of the regularized Newton method
with lazy approximated Hessians [4.62316736194615]
我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。
また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
論文 参考訳(メタデータ) (2023-09-05T17:40:54Z) - A Spectral Algorithm for List-Decodable Covariance Estimation in
Relative Frobenius Norm [41.03423042792559]
我々は、相対的なフロベニウスノルムにおいて、$Sigma$に近い仮説のリストを作成する。
結論として,ガウス混合モデルのロバストな部分クラスタリングのための効率的なスペクトルアルゴリズムを得る。
提案手法は, GMM を頑健に学習する最初の Sum-of-Squares-free アルゴリズムである。
論文 参考訳(メタデータ) (2023-05-01T17:54:35Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳(メタデータ) (2023-01-08T21:46:27Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳(メタデータ) (2022-05-11T14:29:39Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳(メタデータ) (2020-09-03T22:43:55Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳(メタデータ) (2020-08-12T15:40:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。