The sign stochastic gradient descent method (signSGD) utilises only the sign of the stochastic gradient in its updates. For deep networks, this one-bit quantisation has surprisingly little impact on convergence speed or generalisation performance compared to SGD. Since signSGD is effectively compressing the gradients, it is very relevant for distributed optimisation where gradients need to be aggregated from different processors. What's more, signSGD has close connections to common deep learning algorithms like RMSprop and Adam. We study the base theoretical properties of this simple yet powerful algorithm. For the first time, we establish convergence rates for signSGD on general non-convex functions under transparent conditions. We show that the rate of signSGD to reach first-order critical points matches that of SGD in terms of number of stochastic gradient calls, but loses out by roughly a linear factor in the dimension for general non-convex functions. We carry out simple experiments to explore the behaviour of sign gradient descent (without the stochasticity) close to saddle points and show that it can help to completely avoid certain kinds of saddle points without using either stochasticity or curvature information.
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) ).