Lightweight Stochastic Optimization for Minimizing Finite Sums with Infinite Data
This work addresses memory efficiency in stochastic optimization for data augmentation scenarios, offering incremental improvements over existing methods like S-MISO.
The paper tackles the problem of expected risk minimization with infinite data from random perturbations, proposing two SGD-like algorithms (SSAG and S-SAGA) that reduce memory costs while improving convergence rates. Experimental results on logistic regression and AUC maximization show SSAG converges faster than SGD with similar space, and S-SAGA outperforms S-MISO in iteration complexity and storage.
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.