Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
This work offers a unified framework for stochastic optimization methods, potentially benefiting researchers and practitioners in machine learning by simplifying analysis and improving algorithm robustness, though it is incremental in extending existing concepts.
The paper tackles stochastic convex composite optimization by extending Nesterov's estimate sequence to unify gradient-based algorithms, providing a generic convergence proof, new algorithms, and robustness strategies, and introduces accelerated stochastic gradient descent and SVRG algorithms with optimal complexity and noise robustness.
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. More precisely, we interpret a large class of stochastic optimization methods as procedures that iteratively minimize a surrogate of the objective, which covers the stochastic gradient descent method and variants of the incremental approaches SAGA, SVRG, and MISO/Finito/SDCA. This point of view 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 propose a new accelerated stochastic gradient descent algorithm and an accelerated SVRG algorithm with optimal complexity that is robust to stochastic noise.