Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: The paper presents an improved analysis of the signSGD gradient estimator. The authors propose to relax the requirements on the gradient estimator in Bernstein (2019). The only requirement imposed on the gradient is that it should have the correct sign with probability greater than 1/2. In particular this approach allows the gradient estimate to be biased as opposed to Bernstein (2019) which requires unbiased gradients. The authors also show this condition to be necessary by a small counterexample.

In my view the paper presents a relatively minor but still interesting extension of the work in Bernstein (2019). The main problem is that the relaxation is not well motivated in terms of scenarios where this might be applicable. Experimental validation is also very weak.

It is claimed in the experiment section that the stochastic gradient of the Rosenbrock function g(x) = \del f_i(x) + eps, where eps is a 0-mean Gaussian and i is uniform random is biased. This seems incorrect to me and the gradient estimate should be unbiased when the expectation is taken over the randomness in i and eps.

A key claim of the paper is the ability to use biased gradient estimates. Experimental validation of this (in light of the above) is completely missing.

The experiments that are presented on MNIST are very general and not very closely connected to the specific claims of the paper. The only real conclusion drawn is that larger batch sizes improve convergence.

I think the paper needs better targeted experiments. They need to show covergence in a case where the conditions in Berstein (2019) do not hold.

How are the properties of the \rho norm related to the observations on l_1 norm for high and l_2 norm for low SNR components in Bernstein (2019)? If they are related this should be referenced.

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: 

This paper focuses on signSGD with the aim of improving theoretical understanding of the method. The main contribution of the paper is to identify a condition SPB (success probability bounds), which is necessary for convergence of signSGD and study its connections with the other conditions known in the literature for signSGD analysis. One important point here is that the norm in which the authors show convergence now depends on SPB, meaning that the probabilities in SPB are used to define the norm-like function they use in the theorems.

This paper is well-written and nicely structured and I like the relationships of SPB with other conditions. However, I have some concerns on the generality of SPB that I will detail below.

- First of all, Lemma 2 is not clear to me at all. The authors say that the variance is bounded by a constant (0 \leq c_i < 1/sqrt{2}) multiplied by the true gradient norm and then they show that this assumption implies SPB. I do not know how restrictive this condition is. For example, what happens when all elements of true gradient is close to zero, I don’t know if it is reasonable to assume the noise to be small for this case. I cannot make the connection of this assumption and the classical bounded variance assumption (E((\hat{g_i}-g_i)^2)\leq\sigma_i). I can believe the result of Lemma 3 with specific constants $c_i$ as given, but I feel that it is then much stronger than standard bounded variance assumption. Because it would be asking the variance to be smaller than some specific constant.

- Related to first point, I did not understand the remark in the first footnote of page 2. The authors argue that SPB is weaker than bounded variance assumption. But at the same time, it is known that bounded variance assumption is not enough to make signSGD work, with counterexamples given in Karimireddy et. al. 2019. So, it is quite weird that an assumption weaker than bounded variance (for which signSGD provably does not convergence) makes signSGD converge. So I think it is more natural for SPB to be stronger than bounded variance, because it is enough to make signSGD work. The only proof in the paper that would support this claim is Lemma 2, as I discussed above is stronger than standard variance bound. I hope that authors can clarify this point.

- After Theorem 1, the authors compare their result with Bernstein et. al. 2019 and mention that Bernstein et. al. needs to use mini-batches depending on $K$ where $K$ is the iteration and unimodal symmetric noise assumption. But when I check Bernstein et. al. 2019, I see that these are different cases. Specifically, Theorem 1 in Bernstein et. al. 2019, uses mini-batch size 1 under unimodal symmetric noise assumption. The case where they would use mini-batches of size $K$ is in Section 3.3 of Bernstein et. al. 2019 where they *drop* unimodal symmetric noise assumption. So, I would suggest the authors to be more exact on this comparison because it is confusing. In fact, in Section 3.3 of Bernstein et. al. 2019, the authors also identify SPB as it is implied by unimodal symmetric noise assumption. It is the paragraph under Lemma 1 in Bernstein et. al. 2019.

- My other concern is the comparison with Karimireddy et. al. 2019 both in theory and practice. Karimireddy et. al. 2019 modifies signSGD and under unbiased stochastic gradients and bounded variance assumption, obtains similar guarantees as this paper. I am aware that this paper does not assume unbiasedness, but like I said before, I do not know how SPB compares to variance bound. So, I see Karimireddy et. al. 2019 and this paper as similar results, so I would want to see some practical comparison as well. In Appendix E, the authors mention that Karimireddy et. al. 2019 has storage need but I think that need is negligible since they only need to store one more vector.

- A side-effect of SPB is that now the convergence results are given in $\rho$-norm where $\rho$ is determined by SPB. I understand why this is needed from the proof of Theorem 1, and its implications in the theorem, but given that Karimireddy et. al. 2019’s result is given in l_2 norm which is easier to interpret, I think more comparison is needed.

- Lastly, I like the fact that SPB is implied by the previous assumption in Bernstein et. al. 2019, namely unimodal symmetric noise, I am not convinced that SPB is much weaker than this assumption. The authors mention in several places in the paper that their assumption is very weak, but looking at Lemma 1, Lemma 2 and Lemma 3: Lemma 1 and Lemma 3 are the already known cases where signSGD works, and Lemma 2 is a new case where signSGD works but as I explained before, it is not clear to me how restrictive this assumption is. Therefore, I am rather unsure if this generalization of SPB is practically significant.

Minor comments:
- page 2, Table 1: I think it would be useful to add the results of Karimireddy et. al. 2019.
- page 2, Table 1 and footnote 1: Footnote sign is given for the bounded stochastic gradient assumption but the explanation in the footnote text talks about the bounded variance assumption. Of course bounded stochastic gradient implies bounded variance, but this should be clarified. In addition, the footnote text is not clear to me, could the authors either point out to some references or give a proof?
- page 2, Adaptive methods paragraph: The end of the paragraph says that signSGD is similar to Adam so, studies on signSGD *can* improve the understanding of Adam. I would be happy if the authors are more exact about this, such as when signSGD is equivalent to Adam etc.
- page 3 discussion after Assumption 1: I do not understand the sentence starting with ‘Moreover, we argue that’. Can the authors give more details on why it is reasonable?
- page 4 Lemma 2: I think the authors should include the definition of variance in the paper. Since the assumption in this Lemma is rather non-standard, I think it makes sense to be as exact as possible.
page 21, Appendix E: It is written that ‘SPB is roughly a necessary and sufficient condition’. I could not understand what *roughly* means in this sentence. From what I have read, the authors have a counter-example showing without SPB, signSGD does not work and with SPB, it works, so I could not understand why it is written roughly here.

Overall, I like the generalization of SPB, but as I detail above, I am not sure how significant the generalization is compared to other results and more specifically how it compares to standard bounded variance (which I believe is weaker than Lemma 2). Therefore, I remain not convinced about the impact of this generalization hence the results. In addition, I would have liked to see more comparisons (both theoretical and practical) with Karimireddy et. al. 2019.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: This paper performs a general analysis of sign-based methods for non-convex optimization. They define a new norm-like function depending on the success probabilities. Using this new norm-like function and under an assumption, they prove exponentially variance reduction properties in both directions and small mini-batch sizes. 

I am not convinced about assumption 1, which plays the key role of the proof. It assumes that success probabilities are always large or equal to 1/2. 

How can we guarantee this property hold for an algorithm? I suggest the authors provide some real learning examples, under which it will satisfy the condition.  I may revise my rating according to this. 

review_title: Official Blind Review #2

Meta-review: This paper proposes an analysis of signSGD in some special cases. SignGD has been shown to be of interest, whether because of its similarity to Adam or in quasi-convex settings.

The complaint shared by reviewers was the strength of the conditions. SGC is really strong, I have yet to see increasing mini-batch sizes to be used in practice (although there are quite a  few papers mentioning this technique to get a convergence rate) and the strength of the other two are harder to assess. With that said, the improvement compared to existing work such as Karimireddy et. al. 2019 is unclear.

I encourage the authors to address the comment of the reviewers and to submit an improved version to a later, or perhaps to a more theoretical, convergence.
Decision: Reject