論文の概要: On the Asymptotic Linear Convergence Speed of Anderson Acceleration,
Nesterov Acceleration, and Nonlinear GMRES
- arxiv url: http://arxiv.org/abs/2007.01996v4
- Date: Sat, 7 Nov 2020 16:24:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-13 14:00:06.649537
- Title: On the Asymptotic Linear Convergence Speed of Anderson Acceleration,
Nesterov Acceleration, and Nonlinear GMRES
- Title（参考訳）: Anderson Acceleration, Nesterov Accelerationおよび非線形GMRESの漸近線形収束速度について
- Authors: Hans De Sterck and Yunhui He
- Abstract要約: Anderson iteration (AA)、GMRES (NGMRES)、Nesterov$typeメソッドが検討されている。
両手法が有限ウィンドウサイズを持つ非定常AAおよびNGMRESの収束を推定できることを示す。
- 参考スコア（独自算出の注目度）: 1.2183405753834562
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider nonlinear convergence acceleration methods for fixed-point
iteration $x_{k+1}=q(x_k)$, including Anderson acceleration (AA), nonlinear
GMRES (NGMRES), and Nesterov-type acceleration (corresponding to AA with window
size one). We focus on fixed-point methods that converge asymptotically
linearly with convergence factor $\rho<1$ and that solve an underlying fully
smooth and non-convex optimization problem. It is often observed that AA and
NGMRES substantially improve the asymptotic convergence behavior of the
fixed-point iteration, but this improvement has not been quantified
theoretically. We investigate this problem under simplified conditions. First,
we consider stationary versions of AA and NGMRES, and determine coefficients
that result in optimal asymptotic convergence factors, given knowledge of the
spectrum of $q'(x)$ at the fixed point $x^*$. This allows us to understand and
quantify the asymptotic convergence improvement that can be provided by
nonlinear convergence acceleration, viewing $x_{k+1}=q(x_k)$ as a nonlinear
preconditioner for AA and NGMRES. Second, for the case of infinite window size,
we consider linear asymptotic convergence bounds for GMRES applied to the
fixed-point iteration linearized about $x^*$. Since AA and NGMRES are
equivalent to GMRES in the linear case, one may expect the GMRES convergence
factors to be relevant for AA and NGMRES as $x_k \rightarrow x^*$. Our results
are illustrated numerically for a class of test problems from canonical tensor
decomposition, comparing steepest descent and alternating least squares (ALS)
as the fixed-point iterations that are accelerated by AA and NGMRES. Our
numerical tests show that both approaches allow us to estimate asymptotic
convergence speed for nonstationary AA and NGMRES with finite window size.
- Abstract（参考訳）: 固定点反復 $x_{k+1}=q(x_k)$ に対する非線形収束加速度法は、アンダーソン加速度(AA)、非線形GMRES(NGMRES)、ネステロフ型加速度(窓サイズ1のAAに対応する)を含む。
我々は, 収束係数$\rho<1$で漸近的に線形に収束し, 基礎となる完全滑らかかつ非凸最適化問題を解く固定点法に着目した。
AAとNGMRESは固定点反復の漸近収束挙動を著しく改善するが、この改善は理論的には定量化されていない。
我々はこの問題を簡易な条件で検討する。
まず AA と NGMRES の定常バージョンを検討し、固定点 $x^*$ における$q'(x)$ のスペクトルの知識が与えられたとき、最適な漸近収束因子をもたらす係数を決定する。
これにより、AA と NGMRES の非線形事前条件として $x_{k+1}=q(x_k)$ を眺めながら、非線形収束加速度によって得られる漸近収束改善の理解と定量化が可能になる。
第二に、無限ウィンドウサイズの場合、約$x^*$ で線型化された固定点反復に適用されたGMRESの線形漸近収束境界を考える。
線形の場合、AA と NGMRES は GMRES と等価であるため、GMRES 収束係数は AA と NGMRES に$x_k \rightarrow x^*$ として関係していると期待できる。
AAとNGMRESによって加速される固定点反復として、最も急降下と最小二乗(ALS)を交互に比較し、正準テンソル分解による一連の試験問題を数値的に示す。
数値実験により,非定常AAおよびNGMRESの漸近収束速度を有限ウィンドウサイズで推定できることがわかった。
関連論文リスト
- Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。
これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
論文 参考訳（メタデータ） (2024-10-03T16:08:16Z) - Improved Convergence Rates of Windowed Anderson Acceleration for
Symmetric Fixed-Point Iterations [15.420927564123193]
本稿では,固定点法によく用いられるウィンドウ付きアンダーソン加速度(AA)アルゴリズムについて検討する。
異なるデータモデルを用いた実験では、AAはタイラーのM推定の標準的な固定点法よりもはるかに優れていることが示された。
論文 参考訳（メタデータ） (2023-11-04T19:23:21Z) - On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity,
Non-Asymptotic Rate and Acceleration [33.247600151322466]
我々は、滑らかな凸関数の標準設定において、AdaGradとその変種についてより深く理解する。
まず、制約のない問題に対して、バニラ AdaGrad の収束率を明示的に拘束する新しい手法を示す。
第二に、平均的な反復ではなく、最後の反復の収束を示すことのできる AdaGrad の変種を提案する。
論文 参考訳（メタデータ） (2022-09-29T14:44:40Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Anderson Acceleration as a Krylov Method with Application to Asymptotic
Convergence Analysis [0.0]
アンダーソン加速度は固定点法の収束を加速するために広く用いられている。
線形固定点法の場合、$x_k+1=q(x_k)$,$x_k。
論文 参考訳（メタデータ） (2021-09-29T03:53:15Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文 参考訳（メタデータ） (2021-02-09T05:35:53Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z) - Asymptotic errors for convex penalized linear regression beyond Gaussian
matrices [23.15629681360836]
雑音線形観測から係数ベクトル$x_0$ in$RN$を学習する問題を考察する。
平均二乗誤差に対する明示的な式を厳密に導出する。
我々の予測は、非常に適度なサイズであっても、数値と非常によく一致していることを示す。
論文 参考訳（メタデータ） (2020-02-11T13:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。