  Regularized nonlinear acceleration (RNA) estimates the minimum of a function
by post-processing iterates from an algorithm such as the gradient method. It
can be seen as a regularized version of Anderson acceleration, a classical
acceleration scheme from numerical analysis. The new scheme provably improves
the rate of convergence of fixed step gradient descent, and its empirical
performance is comparable to that of quasi-Newton methods. However, RNA cannot
accelerate faster multistep algorithms like Nesterov's method and often
diverges in this context. Here, we adapt RNA to overcome these issues, so that
our scheme can be used on fast algorithms such as gradient methods with
momentum. We show optimal complexity bounds for quadratics and asymptotically
optimal rates on general convex minimization problems. Moreover, this new
scheme works online, i.e., extrapolated solution estimates can be reinjected at
each iteration, significantly improving numerical performance over classical
accelerated methods.
