Nonlinear Acceleration of Stochastic Algorithms
Extrapolation methods use the last few iterates of an optimization algorithm to produce a better estimate of the optimum. They were shown to achieve optimal convergence rates in a deterministic setting using simple gradient iterates. Here, we study extrapolation methods in a stochastic setting, where the iterates are produced by either a simple or an accelerated stochastic gradient algorithm. We first derive convergence bounds for arbitrary, potentially biased perturbations, then produce asymptotic bounds using the ratio between the variance of the noise and the accuracy of the current point. Finally, we apply this acceleration technique to stochastic algorithms such as SGD, SAGA, SVRG and Katyusha in different settings, and show significant performance gains.
Summary of the paper
====================
In principle, the extrapolation algorithm devised by Scieur et al. (2016) forms a scheme which allows one to speed up a given optimization algorithm by averaging iterates. The current paper extends this idea to the stochastic case by using the same the averaging technique only this time for noisy iterates. After recalling the results for the deterministic case (as shown in Scieur et al. (2016)), a theoretical upper bound is derived, based on theses results, by quantifying the amount of noise introduced into the optimization process. Finally, numerical experiments which demonstrate the speed-up offered by this technique for least-square and finite sum problems are provided. 
Evaluation
==========
Extending this technique for stochastic algorithms is a crucial step for this technique as this family of algorithms dominants many modern applications. From practical point of view, this seems to provide a significantly acceleration to some (but not all) of the state-of-the-art algorithms. Moreover, the theoretical analysis provided in the paper shows that this stochastic generalization effectively subsumes the deterministic case. However, this paper does not provide a satisfying analysis of the theoretical convergence rate expected by applying the Algorithm 1 on existing stochastic algorithms (especially, for finite sum problems). It is therefore hard to predict in what settings, for which algorithms and to what extent should we expect acceleration. In my opinion, this forms a major weakness point of this paper. 
General Comments
================
- As mentioned above, I would suggest providing a more comprehensive discussion which allows more intuition regarding the benefits of this technique with respect to other existing algorithms.
- Consider adding a more precise statement to address the theoretical convergence rate expected when applying this technique to a given optimization algorithm with a given convergence rate.
Minor Comments
==============
L13: f(x) -> f ?
L13: Smooth and strong convexity are not defined\addressed at this point of the paper.
L25: depends on
L31: Many algorithms do exhibit convergence properties which are adaptive to the effective strong convexity of the problem: vanilla gradient descent, SAG (https://arxiv.org/abs/1309.2388, Page 8, 'an interesting consequence').
L52: f(x) -> f ?
L55: Might be somewhat confusing to diverse from the conventional way of defining condition number.
L61: The linear approximation may not be altogether trivial (also may worth to mention that the gradient vanishes..)
L72: in the description of Algorithm 1, using boldface font to denote the vector of all ones is not aligned with vector notation used throughout the paper, and thus, is not defined a-priori.
L81: can you elaborate more on why 'Convergence is guaranteed as long as the errors' implies to 'ensures a good rate of decay for the regularization parameter'.
L103: lambda..
L118: I would split the technical statement from the concrete application fro SGD.
L121: Maybe elaborate more on the technical difficulty you encounter to prove a 'finite-step' version without lim?
L136: G is symmetric?
L137: corresponds?
L137: I'd suggest further clarifying the connection with Taylor reminder by making it more concrete.
L140: corresponds
L140: h in I-h A^\top A
L149: The
Figure 2 Legend: the 'acc' prefix is a bit confusing as 'acceleration' in the context of continuous optimization this term is used somewhat differently.
L227: Can you give more intuition on why 'the algorithm has a momentum term' implies 'underlying dynamical system is harder to extrapolate.'?