論文の概要: On the Asymptotic Linear Convergence Speed of Anderson Acceleration
Applied to ADMM
- arxiv url: http://arxiv.org/abs/2007.02916v3
- Date: Mon, 30 Nov 2020 04:03:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-13 03:28:30.815365
- Title: On the Asymptotic Linear Convergence Speed of Anderson Acceleration
Applied to ADMM
- Title（参考訳）: ADMMに応用したアンダーソン加速度の漸近線形収束速度について
- Authors: Dawei Wang, Yunhui He, Hans De Sterck
- Abstract要約: AndersonAcceleration(AA)は、乗算器の交互方向法(ADMM)の線形収束速度を改善するための強力なメカニズムである。
本稿では,ADMM に適用された AA の定常バージョンに対して,この線形収束速度の改善について説明し,定量化する。
この定常AA-ADMM法の最適線形収束係数は、前回の定常AA加速度に関する研究に基づいて解析的または最適化的に計算される。
- 参考スコア（独自算出の注目度）: 9.410388161815218
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Empirical results show that Anderson acceleration (AA) can be a powerful
mechanism to improve the asymptotic linear convergence speed of the Alternating
Direction Method of Multipliers (ADMM) when ADMM by itself converges linearly.
However, theoretical results to quantify this improvement do not exist yet. In
this paper we explain and quantify this improvement in linear asymptotic
convergence speed for the special case of a stationary version of AA applied to
ADMM. We do so by considering the spectral properties of the Jacobians of ADMM
and the stationary version of AA evaluated at the fixed point, where the
coefficients of the stationary AA method are computed such that its asymptotic
linear convergence factor is optimal. The optimal linear convergence factors of
this stationary AA-ADMM method are computed analytically or by optimization,
based on previous work on optimal stationary AA acceleration. Using this
spectral picture and those analytical results, our approach provides new
insight into how and by how much the stationary AA method can improve the
asymptotic linear convergence factor of ADMM. Numerical results also indicate
that the optimal linear convergence factor of the stationary AA methods gives a
useful estimate for the asymptotic linear convergence speed of the
non-stationary AA method that is used in practice.
- Abstract（参考訳）: 実験の結果,ADMM自体が線形収束する場合,アンダーソン加速度(AA)は交互乗算器の交互方向収束法(ADMM)の漸近線形収束速度を改善する強力な機構であることが示された。
しかし、この改良を定量化する理論的な結果はまだ存在しない。
本稿では,ADMMに適用された定常バージョンのAAの特別な場合に対する線形漸近収束速度の改善について説明し,定量化する。
本稿では,ADMM のヤコビアンスペクトル特性と固定点で評価された AA の定常バージョンを考察し,その漸近線形収束係数が最適となるような定常 AA 法の係数を計算する。
この定常AA-ADMM法の最適線形収束係数は、前回の定常AA加速度に基づく解析的または最適化によって計算される。
このスペクトル図とそれらの解析結果を用いて,ADMMの漸近線形収束係数をどの程度向上させることができるか,またその方法によって新たな知見が得られる。
また, 定常 aa 法の最適線形収束係数は, 非定常 aa 法の漸近的線形収束速度の予測に有用であることを示した。
関連論文リスト
- Anderson Acceleration in Nonsmooth Problems: Local Convergence via Active Manifold Identification [11.495346367359037]
能動多様体同定特性を特徴とする非滑らかな最適化アルゴリズムのクラスについて検討する。
最適化問題が定常点に活性多様体を持つという仮定の下で、アンダーソン加速アルゴリズムの局所 R-線型収束速度を確立する。
論文 参考訳（メタデータ） (2024-10-12T07:55:06Z) - Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
本稿では,分散最適化のための乗算器の交互方向法(ADMM)の近位変種を提案する。
数値実験の結果,本手法は広く用いられている手法よりも高速かつ堅牢であることが示された。
論文 参考訳（メタデータ） (2023-08-31T14:16:30Z) - Online Learning Guided Curvature Approximation: A Quasi-Newton Method
with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。
古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
論文 参考訳（メタデータ） (2023-02-16T20:58:09Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳（メタデータ） (2022-09-16T19:15:50Z) - A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
最適化のための異なる手法を導出できる変分法を導入する。
我々は1対1の対応において最適化手法の2つのファミリを導出する。
自律システムのシンプレクティシティの保存は、ここでは繊維のみに行われる。
論文 参考訳（メタデータ） (2021-06-04T20:21:53Z) - Converting ADMM to a Proximal Gradient for Convex Optimization Problems [4.56877715768796]
融解ラッソや凸クラスタリングなどのスパース推定では、問題を解くために、近位勾配法またはマルチプライヤー(ADMM)の交互方向法のいずれかを適用します。
本論文では,制約と目的が強く凸であると仮定し,ADMM溶液を近位勾配法に変換する一般的な方法を提案する。
数値実験により, 効率の面で有意な改善が得られることを示した。
論文 参考訳（メタデータ） (2021-04-22T07:41:12Z) - Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix
Completion via Gradient Descent [22.851500417035947]
因数分解に基づく勾配降下は、因数分解行列の完備化を解くためのスケーラブルで効率的なアルゴリズムである。
勾配勾配降下は, 地球自然問題の解を推定するために, 高速収束を楽しむことを示す。
論文 参考訳（メタデータ） (2021-02-04T03:41:54Z) - On the Asymptotic Linear Convergence Speed of Anderson Acceleration,
Nesterov Acceleration, and Nonlinear GMRES [1.2183405753834562]
Anderson iteration (AA)、GMRES (NGMRES)、Nesterov$typeメソッドが検討されている。
両手法が有限ウィンドウサイズを持つ非定常AAおよびNGMRESの収束を推定できることを示す。
論文 参考訳（メタデータ） (2020-07-04T03:35:35Z) - A Dynamical Systems Approach for Convergence of the Bayesian EM
Algorithm [59.99439951055238]
我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。
本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。
高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
論文 参考訳（メタデータ） (2020-06-23T01:34:18Z) - Understanding Nesterov's Acceleration via Proximal Point Method [52.99237600875452]
近似点法(PPM)は最適化アルゴリズムを設計するためのビルディングブロックとしてよく用いられる。
本研究では、PPM法を用いて、Nesterovの加速度勾配法(AGM)の異なるバージョンの収束解析とともに、概念的に単純な導出を提供する。
論文 参考訳（メタデータ） (2020-05-17T17:17:18Z) - On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization [80.03647903934723]
我々は、勾配収束法を期待する適応勾配法を証明した。
解析では、非理解勾配境界の最適化において、より適応的な勾配法に光を当てた。
論文 参考訳（メタデータ） (2018-08-16T20:25:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。