Descent Properties of an Anderson Accelerated Gradient Method with Restarting

.Anderson acceleration (\(\mathsf{AA}\)) is a popular acceleration technique to enhance the convergence of fixed-point schemes. The analysis of \(\mathsf{AA}\) approaches often focuses on the convergence behavior of a corresponding fixed-point residual, while the behavior of the underlying objective function values along the accelerated iterates is currently not well understood. In this paper, we investigate local properties of \(\mathsf{AA}\) with restarting applied to a basic gradient scheme (\(\mathsf{AA}\mbox{-}\mathsf{R}\)) in terms of function values. Specifically, we show that \(\mathsf{AA}\mbox{-}\mathsf{R}\) is a local descent method and that it can decrease the objective function at a rate no slower than the gradient method up to higher-order error terms. These new results theoretically support the good numerical performance of \(\mathsf{AA}(\mbox{-}\mathsf{R})\) when heuristic descent conditions are used for globalization and they provide a novel perspective on the convergence analysis of \(\mathsf{AA}\mbox{-}\mathsf{R}\) that is more amenable to nonconvex optimization problems. Numerical experiments are conducted to illustrate our theoretical findings.KeywordsAnderson accelerationdescent propertiesrestartingMSC codes90C3065K0590C0690C53