Estimate Sequences for Variance-Reduced Stochastic Composite Optimization

While the finite-sum setting is a particular case of expectation, the deterministic nature of the resulting cost function In this paper, we propose a unified view of drastically changes the performance guarantees an optimization gradient-based algorithms for stochastic convex method may achieve to solve (1). In particular, when an composite optimization by extending the concept algorithm is only allowed to access unbiased measurements of estimate sequence introduced by Nesterov. of the objective and gradient, it may be shown that the worstcase This point of view covers the stochastic gradient convergence rate in expected function value cannot be descent method, variants of the approaches better than O(1/k) in general, where k is the number of SAGA, SVRG, and has several advantages: (i) iterations (Nemirovski et al., 2009; Agarwal et al., 2012).