  Variance reduction has been commonly used in stochastic optimization. It
relies crucially on the assumption that the data set is finite. However, when
the data are imputed with random noise as in data augmentation, the perturbed
data set be- comes essentially infinite. Recently, the stochastic MISO (S-MISO)
algorithm is introduced to address this expected risk minimization problem.
Though it converges faster than SGD, a significant amount of memory is
required. In this pa- per, we propose two SGD-like algorithms for expected risk
minimization with random perturbation, namely, stochastic sample average
gradient (SSAG) and stochastic SAGA (S-SAGA). The memory cost of SSAG does not
depend on the sample size, while that of S-SAGA is the same as those of
variance reduction methods on un- perturbed data. Theoretical analysis and
experimental results on logistic regression and AUC maximization show that SSAG
has faster convergence rate than SGD with comparable space requirement, while
S-SAGA outperforms S-MISO in terms of both iteration complexity and storage.
