Variance reduction methods which use a mixture of large and small batch gradients, such as SVRG (Johnson & Zhang, 2013) and SpiderBoost (Wang et al.,  2018), require significantly more computational resources per update than SGD (Robbins & Monro, 1951). We reduce the computational cost per update of variance reduction methods by introducing a sparse gradient operator blending the top-K operator (Stich et al., 2018;Aji & Heafield, 2017) and the randomized coordinate descent operator. While the computational cost of computing the derivative of a model parameter is constant, we make the observation that the gains in variance reduction are proportional to the magnitude of the derivative. In this paper, we show that a sparse gradient based on the magnitude of past gradients reduces the computational cost of model updates without a significant loss in variance reduction. Theoretically, our algorithm is at least as good as the best available algorithm (e.g. SpiderBoost) under appropriate settings of parameters and can be much more efficient if our algorithm succeeds in capturing the sparsity of the gradients. Empirically, our algorithm consistently outperforms SpiderBoost using various models to solve various image classification tasks. We also provide empirical evidence to support the intuition behind our algorithm via a simple gradient entropy computation, which serves to quantify gradient sparsity at every iteration.
This paper aims at improving the computational cost of variance reduction methods while preserving their benefits regarding the fast provable convergence. The existing variance reduction based methods suffer from higher per-iteration gradient query complexity as compared to the vanilla mini-batch SGD, which limits their utility in many practical settings. This paper notices that, for many models, as the training progresses the gradient vectors start exhibiting structure in the sense that only a small number of coordinates have large magnitude. Based on this observation, the paper proposes a modified variance reduction method (by modifying the SpiderBoost method), where a 'memory vector' keeps track of the coordinates of the gradient vectors with large variance. Let $d$ be the size of the model parameter. During each iteration, one computes the gradient for $k_1$ coordinates with the highest variance (according to the memory vector) and an additional $k_2$ random coordinates. 
The paper shows that in the worst case, the proposed method has the same gradient query complexity as the SpiderBoost variance reduction method. Assuming that the proposed method can track the sparsity of the gradient vector, the proposed method achieves a gradient query complexity which is $O(\sqrt{(k_1 + k_2)/d})$ times that of the SpiderBoost method. The paper demonstrates the gradient query complexity improvement over the SpiderBoost method on MNIST and CIFAR-10 data set.
The paper presents novel results by utilizing the ideas from the field of communication-efficient distributed optimization. As far as the reviewer can tell, the results in the paper are correct. That said, there is quite a bit of room for improvement in terms of the writing of the paper. 
The paper appears to have way too many typos. For example, 
In Section 2.1:
- Why is $k$ introduced?
- $S$ denotes a random subset with size $k$ ---> $k_2$?
- drawn from the set ${\ell : |y_{\ell}| < |y_{(k)}|}$ ----> ${\ell : |x_{\ell}| < |x_{(k_2)}|}$?
- $rtop(x, y) = (0, 12, 0, 0, 1)$ --> $rtop(x, y) = (0, 16, 0, 0, 1)$
In Lemma 1: 
 - while defining $top_{-k_1}(x, y)$, ".... if |x_{\ell}| >= |x_{(k_1)}|" ----> ".... if |x_{\ell}| <= |x_{(k_1)}|"?
In Section 2.2:
 - What are $g_0, g_1,..., g_{L-1}$? Shouldn't these be $\phi_0, \phi_1,..., \phi_{L-1}$?
In A1: 
 - right after (5), what is $\tilde{x}_0$ in the definition of $\Delta_f$?
The authors may also consider making the empirical evaluation more comprehensive by considering tasks from the NLP domain, e.g., language modeling. This would further help asses the utility of the proposed method.