  Nowadays, algorithms with fast convergence, small memory footprints, and low
per-iteration complexity are particularly favorable for artificial intelligence
applications. In this paper, we propose a doubly stochastic algorithm with a
novel accelerating multi-momentum technique to solve large scale empirical risk
minimization problem for learning tasks. While enjoying a provably superior
convergence rate, in each iteration, such algorithm only accesses a mini batch
of samples and meanwhile updates a small block of variable coordinates, which
substantially reduces the amount of memory reference when both the massive
sample size and ultra-high dimensionality are involved. Empirical studies on
huge scale datasets are conducted to illustrate the efficiency of our method in
practice.
