Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Dear Authors,
After reading the revised version I still believe that the assumption about the gradients + their variances to be distributed equivalently among all direction is very non-realistic, also for the case of deep learning applications.

I think that the direction you are taking is very interesting, yet the theoretical work is still too preliminary and I believe that further investigation should be made in order to make a more complete manuscript.

The additional experiments are nice.  I therefore raised my score by a bit.


$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
 The paper explores SignGD --- an algorithm that uses the sign of the gradients instead of actual gradients for training deep models. The authors provide some guarantees regarding the convergence of SignGD to local minima in the stochastic optimization setting, and later compare SignSG to GD in two deep learning tasks.

Exploring signSGD is an important and interesting line of research, and this paper provides some preliminary result in this direction.
However, in my view, this work is too preliminary and not ready for publish. This is since the authors do not illustrate any clear benefits of signSGD over SGD neither in theory nor in practice. I elaborate on this below:

-The theory part shows that under some conditions, signGD  finds a local minima. Yet, as the authors themselves 
mention, the dependence on the dimension is much worse compared to SGD.
Moreover, the authors do not mention that if the noise variance does not scale with the dimension (as is often the case), then the convergence of SGD will not depend on the dimension, while it seems that the convergence of signGD will still depend on the dimension.

-The experiments are nice as a preliminary investigation, but not enough in order to illustrate the benefits of signSGD over SGD. In order to do so, the authors should make a more extensive experimental study.


review_title: Preliminary work that requires further investigation

final_score: rating: 4: Ok but not good enough - rejection
review_content: UPDATED REVIEW:

I have checked all the reviews, also checked the most recent version.
I like the new experiments, but I am not impressed much with them to increase my score. The assumption about the variance is fixing my concern, but as you have pointed out, it is a bit more tricky :) I would really suggest you work on the paper a bit more and re-submit it.

--------------------------------------------------------------------
In this paper, authors provided a convergence analysis of Sign SGD algorithm for non-covex case.
The crucial assumption for the proof was Assumption 3, otherwise, the proof technique is following a standard path in non-convex optimization.   

In general, the paper is written nicely, easy to follow.

==============================================
"The major issue":
Why Assumption 3 can be problematic in practice is given below:
Let us assume just a convex case and assume we have just 2 kids of function in 2D:  f_1(x) = 0.5 x_1^2 and f_2(x) = 0.5 x_2^2.
Then define the function f(x) = E [ f_i(x)  ].   where $i =1$  with prob 0.5 and $i=2$ with probability 0.5. 
We have that   g(x) = 0.5 [ x_1, x_2 ]^T.
Let us choose $i=1$ and choose $x = [a,a]^T$, where $a$ is some parameter.

Then (4) says, that there has to exist a $\sigma$ such that
P [   | \bar g_i(x) - g_i(x) | > t ] \leq 2 exp( - t^2 / 2\sigma^2).  forall "x".

plugging our function inside it should be true that

P [   | [ B ] - 0.5 a | > t ] \leq 2 exp( - t^2 / 2\sigma^2).  forall "x".
where B is a random variable which has value "a" with probability 0.5 and value "0" with probability 0.5.

If we choose $t = 0.1a$ then we have that it has to be true that

1 = P [   | [ B ] - 0.5 a | > 0.1a ] \leq 2 exp( - 0.01 a^2 / 2\sigma^2)   ---->  0 as $a \to \infty$.

Hence, even in this simple example, one can show that this assumption is violated unless $\sigma = \infty$.

One way to ho improve this is to put more assumption + maybe put some projection into a compact set?
==============================================

Hence, I think the theory should be improved.

In terms of experiments, I like the discussion about escaping saddle points, it is indeed a good discussion. However, it would be nicer to have more numerical experiments.
One thing I am also struggling is the "advantage" of using signSGD: one saves on communication (instead of sending 4*8 bits per dimension, one just send only 1 bit, however, one needs "d"times more iterations, hence, the theory shows that it is much worse then SGD (see (11) ).





review_title: [UPDATED] Would rate more confidently, if stronger numerical experiments are present :) and Assumption 3 is more explained and defended

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper presents convergence rate of a quantized SGD, with biased quantization - simply taking a sign of each element of gradient.

The stated Theorem 1 is incorrect. Even if the stated result was correct, it presents much worse rate for a weaker notion of convergence.

Major flaws:
1. As far as I can see, Theorem 1 should depend on 4th root of N_K, the last (omitted) step from the proof is done incorrectly. This makes it much worse than presented.
2. Even if this was correct, the main point is that this is "only" d times worse - see eq (11). That is enormous difference, particularly in settings where such gradient compression can be relevant. Also, it is lot more worse than just d times:
3. Again in eq (11), you compare different notions of convergence - E[||g||_1]^2 vs. E[||g||_2^2]. In particular, the one for signSGD is the weaker notion - squared L1 norm can be d times bigger again. If this is not the case for some reason, more detailed explanation is needed.

Other than that, the paper contains several attempts at intuitive explanation, which I don't find correct. Inclusion of Assumption 3 would in particular require better justification.

Experiments are also inconclusive, as the plots show convergence to significantly worse accuracy than what the models converged to in original contributions.
review_title: Not correct

Meta-review: Dear authors,

After carefully reading the reviews, the rebuttal, and going through the paper, I regret to inform you that this paper does not meet the requirements for publication at ICLR.

While the variance analysis is definitely of interest, the reality of the algorithm does not match the claims. The theoretical rate is worse than that of SG but this could be an artefact of the analysis. Sadly, the experimental setup lacks in several ways:
- It is not yet clear whether escaping the saddle points is really an issue in deep learning as the loss function is still poorly understood.
- This analysis is done in the noiseless setting despite your argument being based around the variance of the gradients.
- You report the test error on CIFAR-10. While interesting and required for an ML paper, you introduce an optimization algorithm and so the quantity that matters the most is the speed at which you achieve a given training accuracy. Also, your table lists the value of the test accuracy rather than the speed of increase. Thus, you test the generalization ability of your algorithm while making claims about the optimization performance.
Decision: Reject