Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 8: Accept
review_content: Summary: This paper introduces a sparse variant to SpiderBoost which reduces the complexity cost of updating gradient estimates by way of sparse updates. The authors prove that this variant incurs a negligible increase in worst case complexities as soon as certain assumptions are satisfied, and that when their algorithm captures sparsity correctly, they improve upon SpiderBoost's complexity.

This paper is clearly, and the experiments support the theoretical contributions. 

In Figure 1, you report results as a function of gradient queries/N. Given Theorem 2, I assume that the graphs would look similar as a function of wall-clock time; can you confirm this?

Recommendation: Accept. 

Minor comments and questions for the author:
- I am slightly confused by the introduction of the rtop operator. Specifically, 
  1) What is the relation between k1, k2, and k?
  2) You write that S is a random subset of size k. Should this be k2?
  3) In your first example, should we have rtop(x,y) = (0, 16, 0, 0, 1), since for \ell = 2, y_\ell = 4, d-k1 = 4, k2=1? Am I missing something?
  More generally, my understanding is that the rtop(x,y) operator randomly sparsifies y based on x, which essentially provides indication of where sparsity would be least harmful; when not sparsifying, rtop applies a rescaling that guarantees unbiased estimates. If this is correct, I would recommend making that intuition more clear early on in the paper, in order to improve upon the clarity of the paper.

- You state that rtop is linear in y; since rtop depends on the random variable S, is the claim that E[rtop(x, y+y')] = E[rtop(x, y)]+E[rtop(x,y')] (which follows from unbiasedness)?

- For your experiments, could you discuss how your choice of hyperparameters relates to the constraints in Theorem 1 and 2? 

- I believe Table 1 would be more impactful if it also included the initial entropy ratios at the beginning of training, rather than reporting those values below.

- Other variance reduction techniques for minibatching focus on choosing the minibatches themselves with non-uniform sampling. Under such a sampling mechanism, do you foresee any complications to using SpiderBoost with Sparse Gradients, eg., decrease in overall sparsity?
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: Summary: 
The author(s) provide a method which combines some property of SCGS method and SpiderBoost. Theoretical results are provided and achieve the state-of-the-art complexity, which match the one of SpiderBoost. Numerical experiments show some advantage compared to SpiderBoost on some deep neural network architecture for some standard datasets MNIST, SVHN, and CIFAR-10. 

Comments: 

1) It is true that variance reduction methods achieve the state-of-the-art complexity theory for finding first order stationary point of general nonconvex optimization problems. However, it is well-known that variance reduction methods are not very efficient for training deep neural networks. All of the experiments in this paper are focusing on deep learning problems. If the author(s) would like to show good performance, I would suggest to compare the algorithms with the state-of-the-art algorithms in Deep Learning such as Adam, SGD-Momentum. Showing some improvement over SpiderBoost for deep learning problems would have low impact. 

2) I would suggest the author(s) to switch directions to focus on general nonconvex problems, that is, to find some different examples on general non-convex optimization problems rather than for deep learning problems. In other words, to find examples which show that your algorithm has more advantage than SGD-type algorithms, SVRG-type. 

3) I would also suggest the author(s) to plot all figures in log-scale in order to see in more detail performance. 

4) According to my knowledge, SpiderBoost is an alternative way of re-writing the SARAH algorithm [1, 2] with some small modification, that is a variant of SARAH. Therefore, the SARAH algorithm should be highly related to this paper and need to be discussed and mentioned more clearly. 

[1] Nguyen et al 2017a, “SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient”.
[2] Nguyen et al 2017b, “Stochastic Recursive Gradient Algorithm for Nonconvex Optimization”. 

review_title: Official Blind Review #2

Meta-review: Congratulations on getting your paper accepted to ICLR. Please make sure to incorporate the reviewers' suggestions for the final version.
Decision: Accept (Poster)