Anderson mixing (or Anderson acceleration) is an efficient acceleration method for fixed point iterations (i.e., @math ), e.g., gradient descent can be viewed as iteratively applying the operation @math . It is known that Anderson mixing is quite efficient in practice and can be viewed as an extension of Krylov subspace methods for nonlinear problems. First, we show that Anderson mixing with Chebyshev polynomial parameters can achieve the optimal convergence rate @math , which improves the previous result @math provided by [Toth and Kelley, 2015] for quadratic functions. Then, we provide a convergence analysis for minimizing general nonlinear problems. Besides, if the hyperparameters (e.g., the Lipschitz smooth parameter @math ) are not available, we propose a Guessing Algorithm for guessing them dynamically and also prove a similar convergence rate. Finally, the experimental results demonstrate that the proposed Anderson-Chebyshev mixing method converges significantly faster than other algorithms, e.g., vanilla gradient descent (GD), Nesterov's Accelerated GD. Also, these algorithms combined with the proposed guessing algorithm (guessing the hyperparameters dynamically) achieve much better performance.
Many applications in science and engineering lead to models which require solving large-scale fixed point problems, or equivalently, systems of nonlinear equations. Several successful techniques for handling such problems are based on quasi-Newton methods that implicitly update the approximate Jacobian or inverse Jacobian to satisfy a certain secant condition. We present two classes of multisecant methods which allows to take into account a variable number of secant equations at each iteration. The first is the Broyden-like class, of which Broyden’s family is a subclass, and Anderson mixing is a particular member. The second class is that of the nonlinear Eirola-Nevanlinna-type methods. This work was motivated by a problem in electronic structure calculations, whereby a fixed point iteration, known as the self-consistent field (SCF) iteration, is accelerated by various strategies termed ‘mixing’. We discuss several methods for accelerating the convergence of the iterative solution of nonlinear equation systems commonly in use and point to interrelations between them. In particular we investigate two of the most sophisticated schemes, namely the Anderson mixing and the Broyden update, both generalized to the consideration of arbitrarily many previous iterations. For the Broyden method we give a new derivation which is much simpler than that recently proposed by Vanderbilt and Louie. We show that if the additional parameters invented by these authors in order to increase flexibility are used to optimize the convergence of the iteration process they in fact cancel out. In addition we prove that in this (optimal) case the Anderson mixing and the Broyden update as applied to the inverse Jacobian are fully identical. Thus we come to the conclusion that neither of these schemes is superior. Moreover, we show that Broyden update of the inverse Jacobian is superior to updating the Jacobian itself. Finally we propose an extension of the Anderson mixing which avoids the numerical difficulties all these methods are faced with.