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.
There are many sequence acceleration methods in the numerical analysis literatures. In particular, the well-known Aitken's @math process @cite_12 accelerated the convergence of a sequence that is converging linearly. Shanks generalized the Aitken extrapolation which was known as Shanks transformation @cite_21 . Recently, @cite_1 proposed a general framework for Shanks sequence transformations which includes many vector sequence acceleration methods. One fundamental difference between Anderson mixing and other sequence acceleration methods (such as MPE, RRE (reduced rank extrapolation) @cite_19 @cite_18 , etc.) is that Anderson mixing is a fully dynamic method @cite_14 . Here means all iterations are in the same sequence, and it does not require to restart the procedure. It can be seen from Algorithm that all iterations are applied to the same sequence @math . In fact, in Capehart's PhD thesis @cite_14 , several experiments were conducted to demonstrate the superior performance of Anderson mixing over other semi-dynamic methods such as MPE, RRE (semi-dynamic means that the algorithm maintains more than one sequences or needs to restart several times).
@cite_18 @cite_14 @cite_21 @cite_1 @cite_19 @cite_12
2004162424 1641427606 2324838733 2886987088 1968796795 2331034993
This is an expository paper that describes and compares five methods for extrapolating to the limit (or anti-limit) of a vector sequence without explicit knowledge of the sequence generator. The methods are the minimal polynomial extrapolation (MPE) studied by Cabay and Jackson, Mesina, and Skelboe; the reduced rank extrapolation (RRE) of Eddy (which we show to be equivalent to Mesina’s version of MPE); the vector and scalar versions of the epsilon algorithm (VEA, SEA) introduced by Wynn and extended by Brezinski and Gekeler; and the topological epsilon algorithm (TEA) of Brezinski. We cover the derivation and error analysis of iterated versions of the algorithms, as applied to both linear and nonlinear problems, and we show why these versions tend to converge quadratically. We also present samples from extensive numerical testing that has led us to the following conclusions: (a) TEA, in spite of its role as a theoretical link between the polynomial-type and the epsilon-type methods, has no practical appl... Abstract : Mathematical problems can be solved numerically by deriving an iteration scheme that generates a sequence, the limit of which is the solution of the problem. However, quite often the generated sequence converges very slowly or even diverges. This study describes and compares methods designed to accelerate a slowly convergent sequence or to obtain the solution of the problem from a divergent sequence. The methods studied are Aitken's Delta-Squared method, Wynn's epsilon and modified epsilon methods, the minimal polynomial extrapolation method, the reduced rank extrapolation method, and Anderson's generalized secant algorithms. The derivation of these methods, as applied to both linear and nonlinear problems, are presented. In addition, the acceleration methods are compared theoretically and numerically. Results are presented from extensive numerical testing of problems in an m-dimensional vector space. This paper discusses a family of non-linear sequence-to-sequence transformations designated as ek, ekm, ẽk, and ed. A brief history of the transforms is related and a simple motivation for the transforms is given. Examples are given of the application of these transformations to divergent and slowly convergent sequences. In particular the examples include numerical series, the power series of rational and meromorphic functions, and a wide variety of sequences drawn from continued fractions, integral equations, geometry, fluid mechanics, and number theory. Theorems are proven which show the effectiveness of the transformations both in accelerating the convergence of (some) slowly convergent sequences and in inducing convergence in (some) divergent sequences. The essential unity of these two motives is stressed. Theorems are proven which show that these transforms often duplicate the results of well-known, but specialized techniques. These special algorithms include Newton's iterative process, Gauss's numerical integration, an identity of Euler, the Pade Table, and Thiele's reciprocal differences. Difficulties which sometimes arise in the use of these transforms such as irregularity, non-uniform convergence to the wrong answer, and the ambiguity of multivalued functions are investigated. The concepts of antilimit and of the spectra of sequences are introduced and discussed. The contrast between discrete and continuous spectra and the consequent contrasting response of the corresponding sequences to the e1 transformation is indicated. The characteristic behaviour of a semiconvergent (asymptotic) sequence is elucidated by an analysis of its spectrum into convergent components of large amplitude and divergent components of small amplitude. This paper presents a general framework for Shanks transformations of sequences of elements in a vector space. It is shown that Minimal Polynomial Extrapolation (MPE), Modified Minimal Polynomial E... A general approach to the construction of convergence acceleration methods for vector sequences is proposed. Using this approach, one can generate some known methods, such as the minimal polynomial extrapolation, the reduced rank extrapolation, and the topological epsilon algorithm, and also some new ones. Some of the new methods are easier to implement than the known methods and are observed to have similar numerical properties. The convergence analysis of these new methods is carried out, and it is shown that they are especially suitable for accelerating the convergence of vector sequences that are obtained when one solves linear systems of equations iteratively. A stability analysis is also given, and numerical examples are provided. The convergence and stability properties of the topological epsilon algorithm are likewise given.