Reviews: Nonlinear Acceleration of Stochastic Algorithms

The paper extends recent work of Scieur et al [2016] on nonlinear acceleration via extrapolation of sequences from deterministic to stochastic optimization. The work by Scieur itself generalizes and extends results developed in the late 60s and 70s from quadratics to non-quadratics (whence the name "nonlinear"). Sequence extrapolation methods seem to have been "forgotten" or simply "not in use" by the ML and optimization community until recently, and have some interesting theoretical and practical properties. For instance, nonlinear regularized acceleration (NRA) is capable to accelerate the sequence of iterates formed by the gradient descent method and obtain the optimal accelerated rate. This is done via what essentially amounts to a "bootstrapping" extrapolation process.