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.

本研究提出了两种基于随机梯度下降的算法(即随机样本平均梯度(SSAG)和随机SAGA(S-SAGA))，以解决使用随机噪声来影响数据集时的期望风险最小化问题，其中SSAG收敛速度比SGD快，而S-SAGA在迭代复杂度和存储方面均优于S-MISO，并且SSAG的存储成本不依赖样本大小，而S-SAGA的存储成本与未被扰动的数据上的方差降低方法相同。

轻量级随机优化方法用于最小化包含无限数据的有限和