A Simple Stochastic Variance Reduced Algorithm with Fast Convergence
  Rates
  Recent years have witnessed exciting progress in the study of stochastic
variance reduced gradient methods (e.g., SVRG, SAGA), their accelerated
variants (e.g, Katyusha) and their extensions in many different settings (e.g.,
online, sparse, asynchronous, distributed). Among them, accelerated methods
enjoy improved convergence rates but have complex coupling structures, which
makes them hard to be extended to more settings (e.g., sparse and asynchronous)
due to the existence of perturbation. In this paper, we introduce a simple
stochastic variance reduced algorithm (MiG), which enjoys the best-known
convergence rates for both strongly convex and non-strongly convex problems.
Moreover, we also present its efficient sparse and asynchronous variants, and
theoretically analyze its convergence rates in these settings. Finally,
extensive experiments for various machine learning problems such as logistic
regression are given to illustrate the practical improvement in both serial and
asynchronous settings.
