On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES

• URL: http://arxiv.org/abs/2007.01996v4
• Date: Sat, 7 Nov 2020 16:24:46 GMT
• Title: On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES
• Abstract summary: Anderson iteration (AA), GMRES (NGMRES), and Nesterov$type methods are considered. We show that both approaches allow us to estimate convergence for nonstationary AA and NGMRES with finite finite window size.
• Score: 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.

Related papers

• Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
  We prove a global convergence rate of $O(min1/k,sqrtd/k1.25)$ in terms of the duality gap. These results are the first global convergence results to demonstrate a provable advantage of a quasi-Newton method over the extragradient method.
  arXiv  Detail & Related papers  (2024-10-03T16:08:16Z)
• Improved Convergence Rates of Windowed Anderson Acceleration for Symmetric Fixed-Point Iterations [15.420927564123193]
  This paper studies the commonly utilized windowed Anderson acceleration (AA) algorithm for fixed-point methods. Experiments with different data models demonstrate AA is significantly superior to the standard fixed-point methods for Tyler's M-estimation.
  arXiv  Detail & Related papers  (2023-11-04T19:23:21Z)
• On the Convergence of AdaGrad(Norm) on $\R^{d}$: Beyond Convexity, Non-Asymptotic Rate and Acceleration [33.247600151322466]
  We develop a deeper understanding of AdaGrad and its variants in the standard setting of smooth convex functions. First, we demonstrate new techniques to explicitly bound the convergence rate of the vanilla AdaGrad for unconstrained problems. Second, we propose a variant of AdaGrad for which we can show the convergence of the last iterate, instead of the average iterate.
  arXiv  Detail & Related papers  (2022-09-29T14:44:40Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Anderson Acceleration as a Krylov Method with Application to Asymptotic Convergence Analysis [0.0]
  Anderson acceleration is widely used for accelerating the convergence of fixed-point methods. We study the case of linear fixed-point methods $x_k+1=q(x_k)$, $x_k.
  arXiv  Detail & Related papers  (2021-09-29T03:53:15Z)
• Proximal Gradient Descent-Ascent: Variable Convergence under K{\L} Geometry [49.65455534654459]
  The finite descent-ascent parameters (GDA) has been widely applied to solve minimax optimization problems. This paper fills such a gap by studying the convergence of the KL-Lized geometry.
  arXiv  Detail & Related papers  (2021-02-09T05:35:53Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  Two timescale approximation (SA) has been widely used in value-based reinforcement learning algorithms. We study the non-asymptotic convergence rate of two timescale linear and nonlinear TDC and Greedy-GQ algorithms.
  arXiv  Detail & Related papers  (2020-11-10T11:36:30Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  We study the problem of solving strongly convex and smooth unconstrained optimization problems using first-order algorithms. We devise a novel, referred to as Recursive One-Over-T SGD, based on an easily implementable, averaging of past gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an sense.
  arXiv  Detail & Related papers  (2020-08-28T14:46:56Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  We show a proof of convergence between the Adam Adagrad and $O(d(N)/st)$ algorithms. Adam converges with the same convergence $O(d(N)/st)$ when used with the default parameters.
  arXiv  Detail & Related papers  (2020-03-05T01:56:17Z)
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices [23.15629681360836]
  We consider the problem of learning a coefficient vector $x_0$ in $RN$ from noisy linear observations. We provide a rigorous derivation of an explicit formula for the mean squared error. We show that our predictions agree remarkably well with numerics even for very moderate sizes.
  arXiv  Detail & Related papers  (2020-02-11T13:43:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.