Title: Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise,
Abstract: In this paper, we propose a unified view of gradient-based algorithms for
stochastic convex composite optimization. By extending the concept of estimate
sequence introduced by Nesterov, we interpret a large class of stochastic
optimization methods as procedures that iteratively minimize a surrogate of the
objective. This point of view covers stochastic gradient descent (SGD), the
variance-reduction approaches SAGA, SVRG, MISO, their proximal variants, and
has several advantages: (i) we provide a simple generic proof of convergence
for all of the aforementioned methods; (ii) we naturally obtain new algorithms
with the same guarantees; (iii) we derive generic strategies to make these
algorithms robust to stochastic noise, which is useful when data is corrupted
by small random perturbations. Finally, we show that this viewpoint is useful
to obtain accelerated algorithms.