ASVRG: Accelerated Proximal SVRG
This provides a more efficient optimization method for machine learning practitioners dealing with large-scale problems, though it appears to be an incremental improvement over existing stochastic variance reduction approaches.
The paper tackles the problem of high computational complexity in stochastic variance reduction methods by proposing ASVRG, a simpler accelerated method with only one additional variable and momentum parameter. The result is a method that achieves best known oracle complexities for both strongly convex and non-strongly convex objectives while maintaining comparable or better performance than state-of-the-art methods.
This paper proposes an accelerated proximal stochastic variance reduced gradient (ASVRG) method, in which we design a simple and effective momentum acceleration trick. Unlike most existing accelerated stochastic variance reduction methods such as Katyusha, ASVRG has only one additional variable and one momentum parameter. Thus, ASVRG is much simpler than those methods, and has much lower per-iteration complexity. We prove that ASVRG achieves the best known oracle complexities for both strongly convex and non-strongly convex objectives. In addition, we extend ASVRG to mini-batch and non-smooth settings. We also empirically verify our theoretical results and show that the performance of ASVRG is comparable with, and sometimes even better than that of the state-of-the-art stochastic methods.