論文の概要: Anderson Acceleration as a Krylov Method with Application to Asymptotic
Convergence Analysis
- arxiv url: http://arxiv.org/abs/2109.14181v1
- Date: Wed, 29 Sep 2021 03:53:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-30 14:33:33.810958
- Title: Anderson Acceleration as a Krylov Method with Application to Asymptotic
Convergence Analysis
- Title（参考訳）: クリロフ法としてのアンダーソン加速と漸近収束解析への応用
- Authors: Hans De Sterck and Yunhui He
- Abstract要約: アンダーソン加速度は固定点法の収束を加速するために広く用いられている。
線形固定点法の場合、$x_k+1=q(x_k)$,$x_k。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Anderson acceleration is widely used for accelerating the convergence of
fixed-point methods $x_{k+1}=q(x_{k})$, $x_k \in \mathbb{R}^n$. We consider the
case of linear fixed-point methods $x_{k+1}=M x_{k}+b$ and obtain polynomial
residual update formulas for AA($m$), i.e., Anderson acceleration with window
size $m$. We find that the standard AA($m$) method with initial iterates $x_k$,
$k=0, \ldots, m$ defined recursively using AA($k$), is a Krylov space method.
This immediately implies that $k$ iterations of AA($m$) cannot produce a
smaller residual than $k$ iterations of GMRES without restart (but without
implying anything about the relative convergence speed of (windowed) AA($m$)
versus restarted GMRES($m$)). We introduce the notion of multi-Krylov method
and show that AA($m$) with general initial iterates $\{x_0, \ldots, x_m\}$ is a
multi-Krylov method. We find that the AA($m$) residual polynomials observe a
periodic memory effect where increasing powers of the error iteration matrix
$M$ act on the initial residual as the iteration number increases. We derive
several further results based on these polynomial residual update formulas,
including orthogonality relations, a lower bound on the AA(1) acceleration
coefficient $\beta_k$, and explicit nonlinear recursions for the AA(1)
residuals and residual polynomials that do not include the acceleration
coefficient $\beta_k$. We apply these results to study the influence of the
initial guess on the asymptotic convergence factor of AA(1).
- Abstract（参考訳）: アンダーソン加速度は、固定点法 $x_{k+1}=q(x_{k})$, $x_k \in \mathbb{R}^n$ の収束を加速するために広く用いられる。
線形固定点法 $x_{k+1}=Mx_{k}+b$ の場合、AA($m$) の多項式残差更新式、すなわちウィンドウサイズ $m$ のアンダーソン加速度を得る。
aa($k$) を使って再帰的に定義された初期イテレート $x_k$, $k=0, \ldots, m$ の標準的な aa($m$) メソッドは、クリロフ空間法である。
これは直ちに、AA($m$) の $k$ 反復は再起動せずに$k$ の残余を GMRES の $k$ の繰り返しより小さな残余を生成できないことを意味する(ただし、(ウィンドウ化された) AA($m$) と再起動された GMRES($m$) の相対収束速度については何も示さない)。
多重クリロフ法の概念を導入し、一般の初期イデアルが $\{x_0, \ldots, x_m\}$ を多重クリロフ法とすることを示す。
AA($m$)残差多項式は、繰り返し数が増えるにつれてエラー反復行列$M$のパワーが初期残差に作用する周期記憶効果を観測する。
直交関係, AA(1) 加速度係数 $\beta_k$ 上の下界, 加速度係数 $\beta_k$ を含まない AA(1) 残留および残留多項式に対する明示的な非線形再帰など, これらの多項式残差更新式に基づいてさらにいくつかの結果を得る。
これらの結果を用いて,AA(1)の漸近収束係数に対する初期推定の影響について検討した。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Improved Convergence Rates of Windowed Anderson Acceleration for
Symmetric Fixed-Point Iterations [15.420927564123193]
本稿では,固定点法によく用いられるウィンドウ付きアンダーソン加速度(AA)アルゴリズムについて検討する。
異なるデータモデルを用いた実験では、AAはタイラーのM推定の標準的な固定点法よりもはるかに優れていることが示された。
論文 参考訳（メタデータ） (2023-11-04T19:23:21Z) - Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point
Analysis [0.0]
AA($m$)、すなわち窓サイズ$m$のアンダーソン加速度の収束性について検討する。
我々は$Psi(z)$と$beta(z)$の連続性と微分可能性特性を分析する。
論文 参考訳（メタデータ） (2021-09-29T03:42:41Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳（メタデータ） (2020-09-08T20:32:26Z) - Truncated Linear Regression in High Dimensions [26.41623833920794]
truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。
我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
論文 参考訳（メタデータ） (2020-07-29T00:31:34Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - 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 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。