Regularized Nonlinear Acceleration
We describe a convergence acceleration technique for generic optimization problems. Our scheme computes estimates of the optimum from a nonlinear average of the iterates produced by any optimization method. The weights in this average are computed via a simple and small linear system, whose solution can be updated online. This acceleration scheme runs in parallel to the base algorithm, providing improved estimates of the solution on the fly, while the original optimization method is running. Numerical experiments are detailed on classical classification problems.
using classical results from control theory to obtain numerical bounds on convergence rates that match the optimal rates. Others have studied the second order ODEs obtained as the limit for small step sizes of classical accelerated schemes, to better understand their convergence [10,11]. Finally, recent results have also shown how to wrap classical algorithms in an outer optimization loop, to accelerate convergence [12] and reach optimal complexity bounds.
Here, we take a significantly different approach to convergence acceleration stemming from classical results in numerical analysis. We use the iterates produced by any (converging) optimization algorithm, and estimate the solution directly from this sequence, assuming only some regularity conditions on the function to minimize. Our scheme is based on the idea behind Aitken's ∆ 2 algorithm [13], generalized as the Shanks transform [14], whose recursive formulation is known as the ε-algorithm [15] (see e.g. [16,17] for a survey). In a nutshell, these methods fit geometrical models to linearly converging sequences, then extrapolate their limit from the fitted model.
In a sense, this approach is more statistical in nature. It assumes an approximately linear model holds for iterations near the optimum, and estimates this model using the iterates. In fact, Wynn's algorithm [15] is directly connected to the Levinson-Durbin algorithm [18,19] used to solve Toeplitz systems recursively and fit autoregressive models (the Shanks transform solves Hankel systems, but this is essentially the same problem [20]). The key difference here is that estimating the autocovariance operator is not required, as we only focus on the limit. Moreover, the method presents strong links with the conjugate gradient when applied to unconstrained quadratic optimization.
We start from a slightly different formulation of these techniques known as minimal polynomial extrapolation (MPE) [17,21] which uses the minimal polynomial of the linear operator driving iterations to estimate the optimum by nonlinear averaging (i.e., using weights in the average which are nonlinear functions of the iterates). So far, for all the techniques cited above, no proofs of convergence of these estimates were given in the case where the iterates made the estimation process unstable.
Our contribution here is to add a regularization in order to produce explicit bounds on the distance to optimality by controlling the stability through the regularization parameter, thus explicitly quantifying the acceleration provided by these techniques. We show in several numerical examples that these stabilized estimates often speed up convergence by an order of magnitude. Furthermore this acceleration scheme thus runs in parallel to the original algorithm, providing improved estimates of the solution on the fly, while the original method is progressing.
The paper is organized as follows. In section 2.1 we recall basic results behind MPE for linear iterations and we will introduce in section 2.2 a formulation of the approximate version of MPE and make a link with the conjugate gradient method. Then, in section 2.3, we generalize these results to generic nonlinear iterations and show, in section 2.4, how to fully control the impact of nonlinearity. We use these results to derive explicit bounds on the acceleration performance of our estimates.
Extrapolation, i.e., constructing a new, potentially better estimate from existing ones, is a ubiquitous tool in numerical analysis. This work applied this old idea to optimization, to construct on the fly a better iterate. A regularized version (by adding ell_2 regularization) of the classic minimal polynomial extrapolation is proposed. The authors provided some crude asymptotic error analysis. Limited experiments against Nesterov's accelerated gradient and the conjugate gradient are provided, and the results seems to favor the proposed method.
===== added after author response ===== The authors' rebuttal was somewhat helpful. There are a few points that I'd like to emphasize again so that the authors would prepare a better version.   "asymptotic analysis:" In line 199 and line 209, in order to deduce a meaningful bound from Proposition 2.6, you have to take the limit x_0 - x* --> 0 (and possibly k large), right? To me this is an asymptotic analysis. You need to be sufficiently close to the optimum so that the bound can kick in (i.e., its leading coefficient to be smaller than 1). It would seem a good idea to present line 199-207 in greater detail since this is a strong example. (But to note that the authors needed Lipschitz continuity of the second derivative, which is unusual.)  I do not agree with the authors in "A fair comparison, since the number of gradient oracle calls was identical in both cases and the grid search on lambda had only a marginal impact on complexity." Note that Nesterov backtracking, if implemented correctly, does not require additional gradient calls, very much the same as the authors backtracking on lambda. All experiments in this work are reported with x-axis being the number of gradient oracle calls. Another figure with x-axis the cumulative running time should also be presented, as RMPE has some overheads (solving Eq. (17) etc.).  ===== end =====  I very much like how the authors relate classical extrapolation methods to the more recent accelerated gradient methods (e.g., Nesterov's). No doubt this will provide new angles to understand acceleration. However, the presentation of this work needs some improvement, and the main results need to be better articulated and contrasted. The experiments are also week for reasons I will detail below.   Let me first comment that the approximate MPE method is NOT novel, in contrast to what the authors claimed in line 58. It is interesting that the authors cited [19] multiple times but did not appear to recall its main points. For instance, (APME) below line 98 is exactly Eq. (10.5) of [19], which attributed to Mesina. Also, the bound above line 102 is exactly Eq. (10.6) of [19]. From this point of view, claiming novelty of APME, or even renaming it as APME, is not appropriate. Another example: Theorem 1 in [19] did not prove the claim in footnote 2 at all (in fact the claim is not true: one needs q to be minimal). This kind of sloppiness is not unusual in the whole manuscript, which is hurting the credibility of this work. Other examples: Eq. (5) used U_0, which is never defined, and then in Eq. (5) and afterwards, it was changed to u_0; The derivations in Eqs. (6)-(9) should have the constraint deg(p) <= k; etc.  I would strongly suggest the authors spend more time on explaining their results, and better contrast with existing methods. For instance, it should be mentioned that under the condition (on A) in Prop. 2.2, the original sequence x_i is in fact converging at a linear rate. Shouldn't you care to mention this and compare the constants (e.g., slope of linear rate)? The discussions from line 119 to line 129 are very interesting, but they lack some details and references. These comparisons, to me, are the interesting part, and I wish the authors to be more elaborative and explicit.   The regularized AMPE in section 24 is not well-motivated. First, one should point out that all the analyses are asymptotic, namely that the approximation or expansion is only valid when x_i is sufficiently close to x_*. The asymptotic nature and the many implicit constants of this analysis make the justification of RAMPE shaky. Second, the authors' motivation to propose RAMPE is to avoid any near-singularity of U^T U. But, when U^T U is near singular, it clearly suggests that the principle behind AMPE may well be violated (e.g., x_i not converging linearly, k too small, etc.). In that case, it seems more useful to fix AMPE as suggested in the reference [19], instead of regularizing?  My biggest complaint comes from the experiment, in particular the selection of the parameter lambda. The authors used a backtracking strategy, which is fine but directly contradicts what is said in line 178, since multiple evaluation of the function f is indeed needed. In this regard, the experiment is not fair either: First, one should also compare the cumulative running time (on top of gradient evaluations), since Nesterov's acceleration does not cost any computational overhead while the proposed RAMPE does. Second, one should also allow Nesterov's algorithm to backtrack the Lipschitz constant and strong convexity parameter, like in [3, 4]. I suspect the main difference in Figs 1, 2 are because of this backtracking (of lambda). The authors need to convince me otherwise. Also, is the condition A < I satisfied in the experiments? (I suspect not since the condition number was deliberately set too large, e.g. tau = 10^2.)