論文の概要: Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point
Analysis
- arxiv url: http://arxiv.org/abs/2109.14176v1
- Date: Wed, 29 Sep 2021 03:42:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-30 14:34:35.575336
- Title: Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point
Analysis
- Title（参考訳）: Anderson Acceleration の線形漸近収束:固定点解析
- Authors: Hans De Sterck and Yunhui He
- Abstract要約: AA($m$)、すなわち窓サイズ$m$のアンダーソン加速度の収束性について検討する。
我々は$Psi(z)$と$beta(z)$の連続性と微分可能性特性を分析する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the asymptotic convergence of AA($m$), i.e., Anderson acceleration
with window size $m$ for accelerating fixed-point methods $x_{k+1}=q(x_{k})$,
$x_k \in R^n$. Convergence acceleration by AA($m$) has been widely observed but
is not well understood. We consider the case where the fixed-point iteration
function $q(x)$ is differentiable and the convergence of the fixed-point method
itself is root-linear. We identify numerically several conspicuous properties
of AA($m$) convergence: First, AA($m$) sequences $\{x_k\}$ converge
root-linearly but the root-linear convergence factor depends strongly on the
initial condition. Second, the AA($m$) acceleration coefficients $\beta^{(k)}$
do not converge but oscillate as $\{x_k\}$ converges to $x^*$. To shed light on
these observations, we write the AA($m$) iteration as an augmented fixed-point
iteration $z_{k+1} =\Psi(z_k)$, $z_k \in R^{n(m+1)}$ and analyze the continuity
and differentiability properties of $\Psi(z)$ and $\beta(z)$. We find that the
vector of acceleration coefficients $\beta(z)$ is not continuous at the fixed
point $z^*$. However, we show that, despite the discontinuity of $\beta(z)$,
the iteration function $\Psi(z)$ is Lipschitz continuous and directionally
differentiable at $z^*$ for AA(1), and we generalize this to AA($m$) with $m>1$
for most cases. Furthermore, we find that $\Psi(z)$ is not differentiable at
$z^*$. We then discuss how these theoretical findings relate to the observed
convergence behaviour of AA($m$). The discontinuity of $\beta(z)$ at $z^*$
allows $\beta^{(k)}$ to oscillate as $\{x_k\}$ converges to $x^*$, and the
non-differentiability of $\Psi(z)$ allows AA($m$) sequences to converge with
root-linear convergence factors that strongly depend on the initial condition.
Additional numerical results illustrate our findings.
- Abstract（参考訳）: AA($m$) の漸近収束、すなわち、固定点法を加速する$x_{k+1}=q(x_{k})$,$x_k \in R^n$に対して、窓サイズ$m$のアンダーソン加速度を研究する。
AA($m$)による収束加速は広く観測されているが、よく理解されていない。
固定点反復関数 $q(x)$ が微分可能であり、固定点法自体の収束がルート線型である場合を考える。
AA($m$) 収束のいくつかの顕著な性質を数値的に同定する: まず、AA($m$) 列が$\{x_k\}$ 収束するが、根線形収束係数は初期条件に強く依存する。
次に、AA($m$)加速度係数$\beta^{(k)}$は収束しないが、$\{x_k\}$が$x^*$に収束すると振動する。
これらの観測に光を当てるために、AA($m$) 反復を拡張固定点反復 $z_{k+1} =\Psi(z_k)$, $z_k \in R^{n(m+1)}$ と書き、$\Psi(z)$ と $\beta(z)$ の連続性と微分性を分析する。
加速度係数のベクトル $\beta(z)$ が固定点 $z^*$ において連続でないことが分かる。
しかし、$\beta(z)$ の不連続性にもかかわらず、反復関数 $\Psi(z)$ はリプシッツ連続かつ AA(1) に対して$z^*$ で方向微分可能であることを示し、ほとんどの場合、$m>1$ でこれを AA($m$) に一般化する。
さらに、$\psi(z)$ は$z^*$ で微分可能でないことが分かる。
次に、これらの理論的な発見が、観測されたAA($m$)の収束挙動にどのように関係するかを論じる。
z^*$ における $\beta(z)$ の不連続性により、$\beta^{(k)}$ は $\{x_k\}$ で振動し、$x^*$ に収束し、$\psi(z)$ の非微分性により aa($m$) 列は初期条件に強く依存するルート線形収束因子に収束する。
さらなる数値的な結果が得られた。
関連論文リスト
- Evidence for simple "arrow of time functions" in closed chaotic quantum systems [0.0]
$C(t)$から$alphan(t)$を構成するには、$C(t)$の最初の2n$時間微分を 0$ と $t$ でなければならない。
私たちの焦点は$alphan(t)$であり、(ほとんど)単調に減少し、これらの時間関数の矢印(AOTF)と呼ばれます。
論文 参考訳（メタデータ） (2024-08-15T08:17:10Z) - Convergence of Gradient Descent with Small Initialization for
Unregularized Matrix Completion [21.846732043706318]
バニラ勾配降下は、明示的な正則化を必要とせず、必ず基底真理$rmXstar$に収束することを示す。
驚くべきことに、収束率も最終的な精度もオーバーパラメータ化された検索ランク$r'$に依存しておらず、それらは真のランク$r$によってのみ支配される。
論文 参考訳（メタデータ） (2024-02-09T19:39:23Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing:
The Curses of Symmetry and Initialization [46.55524654398093]
過パラメータ化が降下の収束挙動をどのように変化させるかを示す。
目的は、ほぼ等方的線形測定から未知の低ランクの地上構造行列を復元することである。
本稿では,GDの一段階だけを修飾し,$alpha$に依存しない収束率を求める手法を提案する。
論文 参考訳（メタデータ） (2023-10-03T03:34:22Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54: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) - 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) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Convergence Rate of the (1+1)-Evolution Strategy with Success-Based
Step-Size Adaptation on Convex Quadratic Functions [20.666734673282498]
1+1)-進化戦略(ES)と成功に基づくステップサイズ適応を一般凸二次関数で解析する。
1+1)-ES の収束速度は、一般凸二次函数上で明示的に厳密に導かれる。
論文 参考訳（メタデータ） (2021-03-02T09:03:44Z) - Asymptotic behaviour of learning rates in Armijo's condition [0.0]
x_n$ が非退化臨界点に収束すると、$delta _n$ は有界でなければならない。
これは、Unbounded Backtracking GDに関する最初の著者の結果を補完する。
論文 参考訳（メタデータ） (2020-07-07T16:49:25Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。