論文の概要: 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)の新しい変種を導出する。
関連論文リスト
- A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
Lipschitz-of-$nabla f$
$mathcalS_k|p$。
$mathcalS_k|p$。
$nabla f$.
$mathcalS_k|p$。
論文 参考訳（メタデータ） (2024-09-28T18:16:32Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - 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) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - 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) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳（メタデータ） (2022-05-11T14:29:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。