Anderson Acceleration as a Krylov Method with Application to Asymptotic Convergence Analysis

• URL: http://arxiv.org/abs/2109.14181v1
• Date: Wed, 29 Sep 2021 03:53:15 GMT
• Title: Anderson Acceleration as a Krylov Method with Application to Asymptotic Convergence Analysis
• Authors: Hans De Sterck and Yunhui He
• Abstract summary: 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.
• Score: 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).

Related papers

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent [17.73720530889677]
  Preconditioning methods have been proposed to accelerate the convergence of matrix sensing problem. We propose an alternating preconditioned descent (APGD) algorithm, which alternately updates the two factor parameter. We theoretically prove that APGD achieves near-optimal convergence at a linear rate, starting from arbitrary randoms.
  arXiv  Detail & Related papers  (2025-02-01T15:44:39Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
  We present a new class of preconditioned iterative methods for solving linear systems of the form $Ax = b$.<n>Our methods are based on constructing a low-rank Nystr"om approximation to $A$ using sparse random sketching matrix.<n>We prove that the convergence of our methods depends on a natural average condition number of $A$, which improves as the rank of the Nystr"om approximation increases.
  arXiv  Detail & Related papers  (2024-05-09T15:53:43Z)
• 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)
• Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point Analysis [0.0]
  We study the convergence of AA($m$), i.e., Anderson acceleration with window size $m$ for accelerating fixed-point methods. We analyze the continuity and differentiability properties of $Psi(z)$ and $beta(z)$.
  arXiv  Detail & Related papers  (2021-09-29T03:42:41Z)
• Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
  We study the problem of list-decodable linear regression, where an adversary can corrupt a majority of the examples. Our main result is a Statistical Query (SQ) lower bound of $dmathrmpoly (1/alpha)$ for this problem.
  arXiv  Detail & Related papers  (2021-06-17T17:45:21Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset. We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
  arXiv  Detail & Related papers  (2021-06-16T03:34:14Z)
• Conditional Uncorrelation and Efficient Non-approximate Subset Selection in Sparse Regression [72.84177488527398]
  We consider sparse regression from the view of correlation, and propose the formula of conditional uncorrelation. By the proposed method, the computational complexity is reduced from $O(frac16k3+mk2+mkd)$ to $O(frac16k3+frac12mk2)$ for each candidate subset in sparse regression.
  arXiv  Detail & Related papers  (2020-09-08T20:32:26Z)
• Truncated Linear Regression in High Dimensions [26.41623833920794]
  In truncated linear regression, $(A_i, y_i)_i$ whose dependent variable equals $y_i= A_irm T cdot x* + eta_i$ is some fixed unknown vector of interest. The goal is to recover $x*$ under some favorable conditions on the $A_i$'s and the noise distribution. We prove that there exists a computationally and statistically efficient method for recovering $k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated samples.
  arXiv  Detail & Related papers  (2020-07-29T00:31:34Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (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), 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.
  arXiv  Detail & Related papers  (2020-07-04T03:35:35Z)
• 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.