论文标题
在安德森加速度，Nesterov加速和非线性GMRE的渐近线性收敛速度上
On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES
论文作者
论文摘要
我们考虑定点迭代的非线性收敛加速度方法$ x_ {k+1} = q（x_k）$，包括Anderson Acceleration（AA），非线性GMRES（NGMRES）和Nesterov-type type加速度（与窗口尺寸的AA相对应）。我们专注于定点方法，这些方法与收敛因子$ρ<1 $渐近地收敛，并解决了基础完全平滑和非凸优化问题。通常观察到，AA和NGMRE基本上改善了固定点迭代的渐近收敛行为，但是从理论上讲，这种改进尚未进行量化。我们在简化条件下研究了这个问题。首先，我们考虑AA和NGMRE的固定版本，并确定导致最佳渐近收敛因子的系数，鉴于在固定点$ x^*$处的$ q'（x）$的频谱的知识。这使我们能够理解并量化非线性收敛加速器可以提供的渐近收敛改进，将$ x_ {k+1} = q（x_k）$作为AA和NGMRE的非线性预处理器。其次，对于无限窗口尺寸的情况，我们考虑用于应用于$ x^*$的定点迭代的GMRE线性渐近收敛范围。由于在线性情况下，AA和NGMRE等同于GMRE，因此人们可能期望GMRES收敛因子与AA和NGMRE相关，为$ x_k \ rightArrow X^*$。我们的结果在数值上说明了来自规范张量分解的一类测试问题，将最陡峭的下降和交替的最小二乘（ALS）比较为被AA和NGMRES加速的固定点迭代。我们的数值测试表明，这两种方法都使我们能够估算具有有限窗口大小的非组织AA和NGMRE的渐近收敛速度。
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 $ρ<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.
