Year: 2019

Abstract:
Various gradient compression schemes have been proposed to mitigate the communication cost in distributed training of large scale machine learning models. Sign-based methods, such as signSGD (Bernstein et al., 2018), have recently been gaining popularity because of their simple compression rule and connection to adaptive gradient methods, like ADAM. In this paper, we perform a general analysis of sign-based methods for non-convex optimization. Our analysis is built on intuitive bounds on success probabilities and does not rely on special noise distributions nor on the boundedness of the variance of stochastic gradients. Extending the theory to distributed setting within a parameter server framework, we assure exponentially fast variance reduction with respect to number of nodes, maintaining 1-bit compression in both directions and using small mini-batch sizes. We validate our theoretical findings experimentally.

heading: 1 INTRODUCTION
text: One of the key factors behind the success of modern machine learning models is the availability of large amounts of training data (Bottou & Le Cun, 2003; Krizhevsky et al., 2012; Schmidhuber, 2015). However, the state-of-the-art deep learning models deployed in industry typically rely on datasets too large to fit the memory of a single computer, and hence the training data is typically split and stored across a number of compute nodes capable of working in parallel. Training such models then amounts to solving optimization problems of the form
minx∈Rd f(x) := 1 M M∑ m=1 fm(x), (1)
where fm : Rd → R represents the non-convex loss of a deep learning model parameterized by x ∈ Rd associated with data stored on node m. Arguably, stochastic gradient descent (SGD) (Robbins & Monro, 1951; Vaswani et al., 2019; Qian et al., 2019) in of its many variants (Kingma & Ba, 2015; Duchi et al., 2011; Schmidt et al., 2017; Zeiler, 2012; Ghadimi & Lan, 2013) is the most popular algorithm for solving (1). In its basic implementation, all workers m ∈ {1, 2, . . . ,M} in parallel compute a random approximation ĝm(xk) of ∇fm(xk), known as the stochastic gradient. These approximations are then sent to a master node which performs the aggregation
ĝ(xk) := 1 M M∑ m=1 ĝm(xk).
The aggregated vector is subsequently broadcast back to the nodes, each of which performs an update of the form xk+1 = xk − γkĝ(xk), thus updating their local copies of the parameters of the model.

heading: 1.1 GRADIENT COMPRESSION
text: Typically, communication of the local gradient estimators ĝm(xk) to the master forms the bottleneck of such a system (Seide et al., 2014; Zhang et al., 2017; Lin et al., 2018). In an attempt to alleviate this communication bottleneck, a number of compression schemes for gradient updates have been proposed and analyzed (Alistarh et al., 2017; Wang et al., 2018; Wen et al., 2017; Khirirat et al., 2018;
Mishchenko et al., 2019). A compression scheme is a (possibly randomized) mapping Q : Rd → Rd, applied by the nodes to ĝm(xk) (and possibly also by the master to aggregated update in situations when broadcasting is expensive as well) in order to reduce the number of bits of the communicated message.
Sign-based compression. Although most of the existing theory is limited to unbiased compression schemes, i.e., on operators Q satisfying EQ(x) = x, biased schemes such as those based on communicating signs of the update entries only often perform much better (Seide et al., 2014; Strom, 2015; Wen et al., 2017; Carlson et al., 2015; Balles & Hennig, 2018; Bernstein et al., 2018; 2019; Zaheer et al., 2018; Liu et al., 2019). The simplest among these sign-based methods is signSGD (see also Algorithm 1; Option 1), whose update direction is assembled from the component-wise signs of the stochastic gradient.
Adaptive methods. While ADAM is one of the most popular adaptive optimization methods used in deep learning (Kingma & Ba, 2015), there are issues with its convergence (Reddi et al., 2019) and generalization (Wilson et al., 2017) properties. It was noted in Balles & Hennig (2018) that the behaviour of ADAM is similar to a momentum version of signSGD. Connection between sign-based and adaptive methods has long history, originating at least in Rprop (Riedmiller & Braun, 1993) and RMSprop (Tieleman & Hinton, 2012). Therefore, investigating the behavior of signSGD can improve our understanding on the convergence of adaptive methods such as ADAM.

heading: 1.2 CONTRIBUTIONS
text: We now summarize the main contributions of this work. Our key results are summarized in Table 1.
1In fact, bounded variance assumption, being weaker than bounded second moment assumption, is stronger (or, to be strict, more curtain) than SPB assumption in the sense of differential entropy, but not in the direct sense. The entropy of probability distribution under the bounded variance assumption is bounded, while under the SPB assumption it could be arbitrarily large. This observation is followed by the fact that for continuous random variables, the Gaussian distribution has the maximum differential entropy for a given variance (see https://en.wikipedia.org/wiki/Differential_entropy).
• 2 methods for 1-node setup. In the M = 1 case, we study two general classes of sign based methods for minimizing a smooth non-convex function f . The first method has the standard form2
xk+1 ← xk − γk sign ĝ(xk), (2)
while the second has a new form not considered in the literature before:
xk+1 ← arg min{f(xk), f(xk − γk sign ĝ(xk))}. (3)
• Key novelty. The key novelty of our methods is in a substantial relaxation of the requirements that need to be imposed on the gradient estimator ĝ(xk) of the true gradient ∇f(xk). In sharp contrast with existing approaches, we allow ĝ(xk) to be biased. Remarkably, we only need one additional and rather weak assumption on ĝ(xk) for the methods to provably converge: we require the signs of the entries of ĝ(xk) to be equal to the signs of the entries of ∇f(xk) with a probability strictly larger than 1/2 (see Section 2; Assumption 1). We show through a counterexample (see Section 2.2) that this assumption is necessary.
• Geometry. As a byproduct of our analysis, we uncover a mixed l1-l2 geometry of sign descent methods (see Section 3).
• Convergence theory. We perform a complexity analysis of methods (2) and (3) (see Section 4.1; Theorem 1). While our complexity bounds have the same O(1/√K) dependence on the number of iterations, they have a better dependence on the smoothness parameters associated with f . Theorem 1 is the first result on signSGD for non-convex functions which does not rely on mini-batching, and which allows for step sizes independent of the total number of iterations K. Finally, Theorem 1 in Bernstein et al. (2019) can be recovered from our general Theorem 1. Our bounds are cast in terms of a novel norm-like function, which we call the ρ-norm, which is a weighted l1 norm with positive variable weights.
• Distributed setup. We extend our results to the distributed setting with arbitrary M (Section 4.2), where we also consider sign-based compression of the aggregated gradients.

heading: 2 SUCCESS PROBABILITIES AND GRADIENT NOISE
text: In this section we describe our key (and weak) assumption on the gradient estimator ĝ(x) of the true gradient∇f(x), and give an example which shows that without this assumption, method (2) can fail.

heading: 2.1 SUCCESS PROBABILITY BOUNDS
text: Assumption 1 (SPB: Success Probability Bounds). For any x ∈ Rd, we have access to an independent (and not necessarily unbiased) estimator ĝ(x) of the true gradient g(x) := ∇f(x) that satisfies
ρi(x) := Prob (sign ĝi(x) = sign gi(x)) > 1 2 , if gi(x) 6= 0 (4)
for all x ∈ Rd and all i ∈ {1, 2, . . . , d}.
We will refer to the probabilities ρi as success probabilities. As we will see, they play a central role in the convergence of sign based methods. We stress that Assumption 1 is the only assumption on gradient noise in this paper. Moreover, we argue that it is reasonable to require from the sign of stochastic gradient to show true gradient direction more likely than the opposite one. Extreme cases of this assumption are the absence of gradient noise, in which case ρi = 1, and an overly noisy stochastic gradient, in which case ρi ≈ 12 . Remark 1. Assumption 1 can be relaxed by replacing bounds (4) with
E [sign (ĝi(x) · gi(x))] > 0, if gi(x) 6= 0.
However, if Prob(sign ĝi(x) = 0) = 0 (e.g. in the case of ĝi(x) has continuous distributions), then these two bounds are identical.
2sign g is applied element-wise to the entries g1, g2, . . . , gd of g ∈ Rd. For t ∈ R we define sign t = 1 if t > 0, sign t = 0 if t = 0, and sign t = −1 if t < 0.
Extension to stochastic sign oracle. Notice that we do not require ĝ to be unbiased. Moreover, we do not assume uniform boundedness of the variance, or of the second moment. This observation allows to extend existing theory to more general sign-based methods with a stochastic sign oracle. By a stochastic sign oracle we mean an oracle that takes xk ∈ Rd as an input, and outputs a random vector ŝk ∈ Rd with entries in ±1. However, for the sake of simplicity, in the rest of the paper we will work with the signSGD formulation, i.e., we let ŝk = sign ĝ(xk).

heading: 2.2 A COUNTEREXAMPLE TO SIGNSGD
text: Here we analyze a counterexample to signSGD discussed in Karimireddy et al. (2019). Consider the following least-squares problem with unique minimizer x∗ = (0, 0):
min x∈R2
f(x) = 12 [ 〈a1, x〉2 + 〈a2, x〉2 ] , a1 = [ 1+ε −1+ε ] , a2 = [−1+ε 1+ε ] ,
where ε ∈ (0, 1) and stochastic gradient ĝ(x) = ∇〈ai, x〉2 = 2〈ai, x〉ai with probabilities 1/2 for i = 1, 2. Let us take any point from the line l = {(z1, z2) : z1 + z2 = 2} as initial point x0 for the algorithm and notice that sign ĝ(x) = ±(1,−1) for any x ∈ l. Therefore, signSGD with any step-size sequence remains stuck along the line l, whereas the problem has a unique minimizer at the origin.
We now investigate the cause of the divergence. In this counterexample, Assumption 1 is violated. Indeed, note that
sign ĝ(x) = (−1)i sign〈ai, x〉 [−1
1 ] with probabilities 12 for i = 1, 2.
By S := {x ∈ R2 : 〈a1, x〉 · 〈a2, x〉 > 0} 6= ∅ denote the open cone of points having either an acute or an obtuse angle with both ai’s. Then for any x ∈ S, the sign of the stochastic gradient is ±(1,−1) with probabilities 1/2. Hence for any x ∈ S, we have low success probabilities:
ρi(x) = Prob (sign ĝi(x) = sign gi(x)) ≤ 12 , i = 1, 2. So, in this case we have an entire conic region with low success probabilities, which clearly violates (4). Furthermore, if we take a point from the complement open cone S̄c, then the sign of stochastic gradient equals to the sign of gradient, which is perpendicular to the axis of S (thus in the next step of the iteration we get closer to S). For example, if 〈a1, x〉 < 0 and 〈a2, x〉 > 0, then sign ĝ(x) = (1,−1) with probability 1, in which case x − γ sign ĝ(x) gets closer to low success probability region S.
In summary, in this counterexample there is a conic region where the sign of the stochastic gradient is useless (or behaves adversarially), and for any point outside that region, moving direction (which is the opposite of the sign of gradient) leads toward that conic region.

heading: 2.3 SUFFICIENT CONDITIONS FOR SPB
text: To justify our SPB assumption, we show that it holds under general assumptions on gradient noise. Lemma 1 (see B.1). Assume that for any point x ∈ Rd, we have access to an independent and unbiased estimator ĝ(x) of the true gradient g(x). Assume further that each coordinate ĝi has a unimodal and symmetric distribution with variance σ2i = σ 2 i (x), 1 ≤ i ≤ d. Then ρi ≥ 1 2 + 1 2 |gi| |gi|+ √ 3σi > 12 if gi 6= 0.
Next, we remove the distribution condition and add a strong growth condition (Schmidt & Le Roux, 2013; Vaswani et al., 2019) together with fixed mini-batch size. Lemma 2 (see B.2). Assume that for any point x ∈ Rd, we have access to an independent, unbiased estimator ĝ(x) of the true gradient g(x), with coordinate-wise bounded variances σ2i (x) ≤ c g2i (x) for some constant c. Then, choosing a mini-batch size τ > 2c, we get ρi ≥ 1− c/τ > 12 , if gi 6= 0.
Finally, we give an adaptive condition on mini-batch size for the SPB assumption to hold. Lemma 3 (see B.3). Assume that for any point x ∈ Rd we have access to an independent and unbiased estimator ĝ(x) of the true gradient g(x). Let σ2i = σ 2 i (x) be the variance and ν 3 i = ν 3 i (x) be the 3th central moment of ĝi(x), 1 ≤ i ≤ d. Then SPB assumption holds if mini-batch size τ > 2 min ( σ2i/g2i , ν 3 i/|gi|σ2i ) .

heading: 3 A NEW “NORM” FOR MEASURING THE SIZE OF THE GRADIENTS
text: In this section we introduce the concept of a norm-like function, which call ρ-norm, induced from success probabilities. Used to measure gradients in our convergence rates, ρ-norm is a technical tool enabling the analysis. Definition 1 (ρ-norm). Let ρ := {ρi(x)}di=1 be the collection of probability functions from the SPB assumption. We define the ρ-norm of gradient g(x) via ‖g(x)‖ρ := ∑d i=1(2ρi(x)− 1)|gi(x)|.
Note that ρ-norm is not a norm as it may not satisfy the triangle inequality. However, under SPB assumption, ρ-norm is positive definite as it is a weighted l1 norm with positive (and variable) weights 2ρi(x) − 1 > 0. That is, ‖g‖ρ ≥ 0, and ‖g‖ρ = 0 if and only if g = 0. Under the assumptions of Lemma 2, ρ-norm can be lower bounded by a weighted l1 norm with positive constant weights 1− 2c2i > 0: ‖g‖ρ = ∑d i=1(2ρi− 1)|gi| ≥ ∑d i=1(1− 2c2i )|gi|. Under the assumptions of Lemma 1, ρ-norm can be lower bounded by a mixture of the l1 and squared l2 norms:
‖g‖ρ = d∑ i=1 (2ρi − 1)|gi| ≥ d∑ i=1 g2i |gi|+ √ 3σi := ‖g‖l1,2 . (5)
Note that l1,2-norm is again not a norm. However, it is positive definite, continuous and order preserving, i.e., for any gk, g, g̃ ∈ Rd we have: i) ‖g‖l1,2 ≥ 0 and ‖g‖l1,2 = 0 if and only if g = 0; ii) gk → g (in l2 sense) implies ‖gk‖l1,2 → ‖g‖l1,2 , and iii) 0 ≤ gi ≤ g̃i for any 1 ≤ i ≤ d implies ‖g‖l1,2 ≤ ‖g̃‖l1,2 . From these three properties it follows that ‖gk‖l1,2 → 0 implies gk → 0. These properties are important as we will measure convergence rate in terms of the l1,2 norm in the case of unimodal and symmetric noise assumption. To understand the nature of the l1,2 norm, consider the following two cases when σi(x) ≤ c|gi(x)|+ c̃ for some constants c, c̃ ≥ 0. If the iterations are in ε-neighbourhood of a minimizer x∗ with respect to the l∞ norm (i.e., max1≤i≤d |gi| ≤ ε), then the l1,2 norm is equivalent to scaled l2 norm squared: 1
(1+ √ 3c)ε+ √ 3c̃ ‖g‖22 ≤ ‖g‖l1,2 ≤ 1√3c̃‖g‖ 2 2. On
the other hand, if iterations are away from a minimizer (i.e., min1≤i≤d |gi| ≥ L), then the l1,2-norm is equivalent to scaled l1 norm: 1
1+ √ 3(c+c̃/L) ‖g‖1 ≤ ‖g‖l1,2 ≤ 11+√3c‖g‖1. These equivalences are
visible in Figure 1, where we plot the level sets of g 7→ ‖g‖l1,2 at various distances from the origin. Similar mixed norm observation was also noted in Bernstein et al. (2019).

heading: 4 CONVERGENCE THEORY
text: Now we turn to our theoretical results of sign based methods. First we give our general convergence results under the SPB assumption. Afterwards, we present convergence result in the distributed setting under the unimodal and symmetric noise assumptions.
Throughout the paper we assume that f : Rd → R is lower bounded, i.e., f(x) ≥ f∗, x ∈ Rd and is L-smooth with some non-negative constants L = [L1, . . . , Ld]. That is, we assume that f(y) ≤ f(x)+ 〈∇f(x), y−x〉+ ∑d i=1 Li 2 (yi−xi)
2 for all x, y ∈ Rd. We allow f to be nonconvex. Let L̄ := 1d ∑ i Li and Lmax = maxi Li.

heading: 4.1 CONVERGENCE ANALYSIS FOR M = 1
text: We now state our convergence result for Algorithm 1 under the general SPB assumption.
Algorithm 1 SIGNSGD 1: Input: step size γk, current point xk 2: ĝk ← StochasticGradient(xk) 3: Option 1: xk+1 ← xk − γk sign ĝk 4: Option 2: xk+1 ← arg min{f(xk), f(xk − γk sign ĝk)}
Theorem 1 (Non-convex convergence of signSGD, see B.4). Under the SPB assumption, signSGD (Algorithm 1 with Option 1) with step sizes γk = γ0/ √ k + 1 converges as follows
min 0≤k<K E‖∇f(xk)‖ρ ≤ 1√K [ f(x0)−f∗ γ0 + γ0dL̄ ] + γ0dL̄2 logK√ K . (6)
If γk ≡ γ > 0, we get 1/K convergence to a neighbourhood of the solution:
1 K K−1∑ k=0 E‖∇f(xk)‖ρ ≤ f(x0)−f ∗ γK + dL̄ 2 γ . (7)
We now comment on the above result:
• Generalization. Theorem 1 is the first general result on signSGD for non-convex functions without mini-batching, and with step sizes independent of the total number of iterations K. Known convergence results (Bernstein et al., 2018; 2019) on signSGD use mini-batches and/or step sizes dependent on K. Moreover, they also use unbiasedness and unimodal symmetric noise assumptions, which are stronger assumptions than our SPB assumption (see Lemma 1). Finally, Theorem 1 in Bernstein et al. (2019) can be recovered from Theorem 1 (see Section D for the details).
• Convergence rate. Rates (6) and (7) can be arbitrarily slow, depending on the probabilities ρi. This is to be expected. At one extreme, if the gradient noise was completely random, i.e., if ρi ≡ 1/2, then the ρ-norm would become identical zero for any gradient vector and rates would be trivial inequalities, leading to divergence as in the counterexample. At other extreme, if there was no gradient noise, i.e., if ρi ≡ 1, then the ρ-norm would be just the l1 norm and from (6) we get the rate Õ(1/ √ K) with respect to the l1 norm. However, if we know that ρi > 1/2, then we can ensure that the method will eventually converge.
• Geometry. The presence of the ρ-norm in these rates suggests that there is no particular geometry (e.g., l1 or l2) associated with signSGD. Instead, the geometry is induced from the success probabilities. For example, in the case of unbiased and unimodal symmetric noise, the geometry is described by the mixture norm l1,2.
• Practicality. The rate (7) (as well as (30)) supports the common learning schedule practice of using a constant step size for a period of time, and then halving the step-size and continuing this process.
For a reader interested in comparing Theorem 1 with a standard result for SGD, we state the standard result in the Section C. We now state a general convergence rate for Algorithm 1 with Option 2. Theorem 2 (see B.5). Under the SPB assumption, Algorithm 1 (Option 2) with step sizes γk = γ0/ √ k + 1 converges as follows: 1K ∑K−1 k=0 E‖∇f(xk)‖ρ ≤ 1√ K [ f(x0)−f∗ γ0 + γ0dL̄ ] . In the case of constant step size γk = γ > 0, the same rate as (7) is achieved.
Comparing Theorem 2 with Theorem 1, notice that a small modification in Algorithm 1 can remove the log-dependent factor from (6); we then bound the average of past gradient norms instead of the minimum. On the other hand, in a big data regime, function evaluations in Algorithm 1 (Option 2, line 4) are infeasible. Clearly, Option 2 is useful only when one can afford function evaluations and has rough estimates about the gradients (i.e., signs of stochastic gradients). This option should be considered within the framework of derivative-free optimization.

heading: 4.2 CONVERGENCE ANALYSIS IN DISTRIBUTED SETTING
text: In this part we present the convergence result of distributed signSGD (Algorithm 2) with majority vote introduced in Bernstein et al. (2018). Majority vote is considered within a parameter server framework, where for each coordinate parameter server receives one sign from each node and sends
back the sign sent by the majority of nodes. Known convergence results (Bernstein et al., 2018; 2019) use O(K) mini-batch size as well as O(1/K) constant step size. In the sequel we remove this limitations extending Theorem 1 to distributed training. In distributed setting the number of nodes M get involved in geometry introducing new ρM -norm, which is defined by the regularized incomplete beta function I (see B.6).
Algorithm 2 DISTRIBUTED SIGNSGD WITH MAJORITY VOTE 1: Input: step sizes {γk}, current point xk, # of nodes M 2: on each node 3: ĝm(xk)← StochasticGradient(xk) 4: on server 5: pull sign ĝm(xk) from each node 6: push sign [∑M m=1 sign ĝ m(xk) ]
to each node 7: on each node 8: xk+1 ← xk − γk sign [∑M m=1 sign ĝ m(xk) ]
Definition 2 (ρM -norm). Let M ≥ 1 be the number of nodes and l = [ M+1
2
] . Define ρM -norm of
gradient g(x) at x ∈ Rd as ‖g(x)‖ρM = ∑d i=1 (2I(ρi(x); l, l)− 1) |gi(x)|.
Now we can state the convergence rate of distributed signSGD with majority vote. Theorem 3 (Non-convex convergence of distributed signSGD, see B.6). Under SPB assumption, distributed signSGD (Algorithm 2) with step sizes γk = γ0/ √ k + 1 converges as follows
min0≤k<K E‖∇f(xk)‖ρM ≤ 1√K [ f(x0)−f∗ γ0 + γ0dL̄ ] + γ0dL̄2 logK√ K . (8)
For constant step sizes γk ≡ γ > 0, we have convergence up to a level proportional to step size γ:
1 K K−1∑ k=0 E‖∇f(xk)‖ρM ≤ f(x0)−f∗ γK + dL̄ 2 γ. (9)
Variance Reduction. Using Hoeffding’s inequality, we show that ‖g(x)‖ρM → ‖g(x)‖1 exponentially fast as M → ∞: ( 1− exp ( −(2ρ(x)− 1)2l )) ‖g(x)‖1 ≤ ‖g(x)‖ρM ≤ ‖g(x)‖1, where ρ(x) = min1≤i≤d ρi(x) > 1/2. Hence, in some sense, we have exponential variance reduction in terms of number of nodes (see B.7).
Number of nodes. Notice that theoretically there is no difference between 2l−1 and 2l nodes, and this in not a limitation of the analysis. Indeed, as it is shown in the proof, expected sign vector at the master with M = 2l − 1 nodes is the same as with M = 2l nodes: E sign(ĝ(2l)i · gi) = E sign(ĝ (2l−1) i · gi), where ĝ(M) is the sum of stochastic sign vectors aggregated from nodes. The intuition behind this phenomenon is that majority vote with even number of nodes, e.g. M = 2l, fails to provide any sign
with little probability (it is the probability of half nodes voting for +1, and half nodes voting for −1). However, if we remove one node, e.g. M = 2l − 1, then master receives one sign-vote less but gets rid of that little probability of failing the vote (sum of odd number of ±1 cannot vanish). So, somehow this two things cancel each other and we gain no improvement in expectation adding one more node to parameter server framework with odd number of nodes.

heading: 5 EXPERIMENTS
text: We verify our theoretical results experimentally using the MNIST dataset with feed-forward neural network (FNN) and the well known Rosenbrock (non-convex) function with d = 10 variables:
f(x) = ∑d−1 i=1 fi(x) = ∑d−1 i=1 100(xi+1 − x2i )2 + (1− xi)2, x ∈ Rd. (10)
Stochastic formulation of minimization problem for Rosenbrock function is as follows: at any point x ∈ Rd we have access to biased stochastic gradient ĝ(x) = ∇fi(x) + ξ, where index i is chosen uniformly at random from {1, 2, . . . , d− 1} and ξ ∼ N (0, ν2I) with ν > 0.
Figure 2 illustrates the effect of multiple nodes in distributed training with majority vote. As we see increasing the number of nodes improves the convergence rate. It also supports the claim that in expectation there is no improvement from 2l − 1 nodes to 2l nodes. Figure 4 shows the robustness of SPB assumption in the convergence rate (7) with constant step size. We exploited four levels of noise in each column to demonstrate the correlation between success probabilities and convergence rate. In the first experiment (first column) SPB assumption is violated strongly and the corresponding rate shows divergence. In the second column, probabilities still violating SPB assumption are close to the threshold and the rate shows oscillations. Next columns show the improvement in rates when success probabilities are pushed to be close to 1.

heading: Appendix: “On Stochastic Sign Descent
text: Methods”

heading: A EXTRA EXPERIMENTS
text: In this section we perform several additional experiments for further insights.

heading: B PROOFS
text: B.1 SUFFICIENT CONDITIONS FOR SPB: PROOF OF LEMMA 1
Here we state the well-known Gauss’s inequality on unimodal distributions3. Theorem 4 (Gauss’s inequality). Let X be a unimodal random variable with mode m, and let σ2m be the expected value of (X −m)2. Then for any positive value of r,
Prob(|X −m| > r) ≤
{ 4 9 ( σm r )2 , if r ≥ 2√ 3 σm
1− 1√ 3 r σm , otherwise
Applying this inequality on unimodal and symmetric distributions, direct algebraic manipulations give the following bound:
Prob(|X − µ| ≤ r) ≥
{ 1− 49 ( σ r )2 , if σr ≤ √ 3
2 1√ 3 r σ , otherwise ≥ r/σ r/σ + √ 3 ,
where m = µ and σ2m = σ 2 are the mean and variance of unimodal, symmetric random variable X , and r ≥ 0. Now, using the assumption that each ĝi(x) has unimodal and symmetric distribution, we apply this bound for X = ĝi(x), µ = gi(x), σ2 = σ2i (x) and get a bound for success probabilities
Prob(sign ĝi = sign gi) = { Prob(ĝi ≥ 0), if gi > 0 Prob(ĝi ≤ 0), if gi < 0
= { 1 2 + Prob(0 ≤ ĝi ≤ gi), if gi > 0 1 2 + Prob(gi ≤ ĝi ≤ 0), if gi < 0
=
{ 1 2 + 1 2Prob(0 ≤ ĝi ≤ 2gi), if gi > 0
1 2 + 1 2Prob(2gi ≤ ĝi ≤ 0), if gi < 0
= 1
2 +
1 2 Prob(|ĝi − gi| ≤ |gi|)
≥ 1 2 + 1 2 |gi|/σi |gi|/σi + √ 3
= 1
2 +
1
2 |gi| |gi|+ √ 3σi
Improvment on Lemma 1 and l1,2 norm: The bound after Gauss inequality can be improved including a second order term
Prob(|X − µ| ≤ r) ≥
{ 1− 49 ( σ r )2 , if σr ≤ √ 3
2 1√ 3 r σ , otherwise
≥ 1− 1 1 + r/ √ 3σ + (r/ √ 3σ)2 .
Indeed, letting z := r/√3σ ≥ 2/3, we get 1− 49 1 3z2 ≥ 1− 1 1+z+z2 as it reduces to 23z 2− 4z− 4 ≥ 0. Otherwise, if 0 ≤ z ≤ 2/3, then z ≥ 1− 11+z+z2 as it reduces to 1 ≥ 1− z 3. The improvement is tighter as r/σ
r/σ + √ 3 = 1− 1 1 + r/ √ 3σ ≤ 1− 1 1 + r/ √ 3σ + (r/ √ 3σ)2 .
Hence, continuing the proof of Lemma 1, we get
Prob(sign ĝi = sign gi) ≥ 1− 1
2
1
1 + |gi|/ √ 3σi + (|gi|/ √ 3σi)2
and we could have defined l1,2-norm in a bit more complicated form as
‖g‖l1,2 := d∑ i=1 ( 1− 1 1 + |gi|/ √ 3σi + (|gi|/ √ 3σi)2 ) |gi|.
3see https://en.wikipedia.org/wiki/Gauss%27s_inequality
B.2 SUFFICIENT CONDITIONS FOR SPB: PROOF OF LEMMA 2
Let ĝ(τ) be the gradient estimator with mini-batch size τ . It is known that the variance for ĝ(τ) is dropped by at least a factor of τ , i.e.
E[(ĝ(τ)i − gi) 2] ≤ σ
2 i
τ .
Hence, estimating the failure probabilities of sign ĝ(τ) when gi 6= 0, we have
Prob(sign ĝ (τ) i 6= sign gi) = Prob(|ĝ (τ) i − gi| = |ĝ (τ) i |+ |gi|)
≤ Prob(|ĝ(τ)i − gi| ≥ |gi|)
= Prob((ĝ (τ) i − gi) 2 ≥ g2i )
≤ E[(ĝ (τ) i − gi)2] g2i = σ2i τg2i ,
which imples
ρi = Prob(sign ĝi = sign gi) ≥ 1− σ2i τg2i ≥ 1− c τ .
B.3 SUFFICIENT CONDITIONS FOR SPB: PROOF OF LEMMA 3
We will split the derivation into three lemmas providing some intuition on the way. The first two lemmas establish success probability bounds in terms of mini-batch size. Essentially, we present two methods: one works well in the case of small randomness, while the other one in the case of non-small randomness. In the third lemma, we combine those two bounds to get the condition on mini-batch size ensuring SPB assumption. Lemma 4. Let X1, X2, . . . , Xτ be i.i.d. random variables with non-zero mean µ := EX1 6= 0, finite variance σ2 := E|X1 − µ|2 <∞. Then for any mini-batch size τ ≥ 1
Prob ( sign [ 1
τ τ∑ i=1 Xi
] = signµ ) ≥ 1− σ 2
τµ2 . (11)
Proof. Without loss of generality, we assume µ > 0. Then, after some adjustments, the proof follows from the Chebyshev’s inequality:
Prob ( sign [ 1
τ τ∑ i=1 Xi
] = signµ ) = Prob ( 1
τ τ∑ i=1 Xi > 0
)
≥ Prob (∣∣∣∣∣1τ τ∑ i=1 Xi − µ ∣∣∣∣∣ < µ )
= 1− Prob (∣∣∣∣∣1τ τ∑ i=1 Xi − µ ∣∣∣∣∣ ≥ µ )
≥ 1− 1 µ2 Var
[ 1
τ τ∑ i=1 Xi
]
= 1− σ 2
τµ2 ,
where in the last step we used independence of random variables X1, X2, . . . , Xτ .
Obviously, bound (11) is not optimal for big variance as it becomes a trivial inequality. In the case of non-small randomness a better bound is achievable additionally assuming the finitness of 3th central moment.
Lemma 5. Let X1, X2, . . . , Xτ be i.i.d. random variables with non-zero mean µ := EX1 6= 0, positive variance σ2 := E|X1 − µ|2 > 0 and finite 3th central moment ν3 := E|X1 − µ|3 < ∞. Then for any mini-batch size τ ≥ 1
Prob ( sign [ 1
τ τ∑ i=1 Xi
] = signµ ) ≥ 1
2
( 1 + erf ( |µ| √ τ√
2σ
) − ν 3
σ3 √ τ
) , (12)
where error function erf is defined as
erf(x) = 2√ π ∫ x 0 e−t 2 dt, x ∈ R.
Proof. Again, without loss of generality, we may assume that µ > 0. Informally, the proof goes as follows. As we have an average of i.i.d. random variables, we approximate it (in the sense of distribution) by normal distribution using the Central Limit Theorem (CLT). Then we compute success probabilities for normal distribution with the error function erf . Finally, we take into account the approximation error in CLT, from which the third term with negative sign appears. More formally, we apply Berry–Esseen inequality4 on the rate of approximation in CLT (Shevtsova, 2011):∣∣∣∣∣Prob ( 1 σ √ τ τ∑ i=1 (Xi − µ) > t ) − Prob (N > t)
∣∣∣∣∣ ≤ 12 ν3σ3√τ , t ∈ R, where N ∼ N (0, 1) has the standard normal distribution. Setting t = −µ
√ τ/σ, we get∣∣∣∣∣Prob ( 1 τ τ∑ i=1 Xi > 0 ) − Prob ( N > −µ √ τ σ )∣∣∣∣∣ ≤ 12 ν3σ3√τ . (13) It remains to compute the second probability using the cumulative distribution function of normal distribuition and express it in terms of the error function:
Prob ( sign [ 1
τ τ∑ i=1 Xi
] = signµ ) = Prob ( 1
τ τ∑ i=1 Xi > 0 ) (13)
≥ Prob ( N > −µ √ τ
σ
) − 1
2
ν3
σ3 √ τ
= 1√ 2π ∫ ∞ −µ √ τ/σ e−t 2/2 dt− 1 2 ν3 σ3 √ τ
= 1
2
( 1 + √ 2
π ∫ µ√τ/σ 0 e−t 2/2 dt− ν 3 σ3 √ τ )
= 1
2
( 1 + erf ( µ √ τ√
2σ
) − ν 3
σ3 √ τ
) .
Clearly, bound (12) is better than (11) when randomness is high. On the other hand, bound (12) is not optimal for small randomness (σ ≈ 0). Indeed, one can show that in a small randomness regime, while both variance σ2 and third moment ν3 are small, the ration ν/σ might blow up to infinity producing trivial inequality. For instance, taking Xi ∼ Bernoulli(p) and letting p→ 1 gives ν/σ = O ( (1− p)−1/6 ) . This behaviour stems from the fact that we are using CLT: less randomness implies slower rate of approximation in CLT.
As a result of these two bounds on success probabilities, we conclude a condition on mini-batch size for the SPB assumption to hold.
4see https://en.wikipedia.org/wiki/Berry-Esseen_theorem
Lemma 6. Let X1, X2, . . . , Xτ be i.i.d. random variables with non-zero mean µ 6= 0 and finite variance σ2 <∞. Then
Prob ( sign [ 1
τ τ∑ i=1 Xi
] = signµ ) > 1
2 , if τ > 2 min
( σ2
µ2 , ν3 |µ|σ2
) , (14)
where ν3 is (possibly infinite) 3th central moment.
Proof. First, if σ = 0 then the lemma holds trivially. If ν = ∞, then it follows immediately from Lemma 4. Assume both σ and ν are positive and finite.
In case of τ > 2σ2/µ2 we apply Lemma 4 again. Consider the case τ ≤ 2σ2/µ2, which implies µ √ τ√
2σ ≤ 1. It is easy to check that erf(x) is concave on [0, 1] (in fact on [0,∞)), therefore erf(x) ≥
erf(1)x for any x ∈ [0, 1]. Setting x = µ √ τ√
2σ we get
erf ( µ √ τ√
2σ
) ≥ erf(1)√
2
µ √ τ
σ ,
which together with (12) gives
Prob ( sign [ 1
τ τ∑ i=1 Xi
] = signµ ) ≥ 1
2
( 1 +
erf(1)√ 2
µ √ τ
σ − ν
3
σ3 √ τ
) .
Hence, SPB assumption holds if
τ >
√ 2
erf(1)
ν3
µσ2 .
It remains to show that erf(1) > 1/√2. Convexity of ex on x ∈ [−1, 0] implies ex ≥ 1 + (1− 1/e)x for any x ∈ [−1, 0]. Therefore
erf(1) = 2√ π ∫ 1 0 e−t 2 dt
≥ 2√ π ∫ 1 0 ( 1− (1− 1/e)t2 ) dt
= 2√ π
( 2
3 +
1
3e
) >
2√ 4
( 2
3 +
1
3 · 3
) = 7
9 > 1√ 2 .
Lemma (3) follows from Lemma (6) applying it to i.i.d. data ĝ1i (x), ĝ 2 i (x), . . . , ĝ M i (x).
B.4 CONVERGENCE ANALYSIS: PROOF OF THEOREM 1
First, from L-smoothness assumption we have
f(xk+1) = f(xk − γk sign ĝk)
≤ f(xk)− 〈gk, γk sign ĝk〉+ d∑ i=1 Li 2 (γk sign ĝk,i) 2
= f(xk)− γk〈gk, sign ĝk〉+ dL̄
2 γ2k,
where gk = g(xk), ĝk = ĝ(xk), ĝk,i is the i-th component of ĝk and L̄ is the average value of Li’s. Taking conditional expectation given current iteration xk gives
E[f(xk+1)|xk] ≤ f(xk)− γkE[〈gk, sign ĝk〉] + dL̄
2 γ2k. (15)
Using the definition of success probabilities ρi we get
E[〈gk, sign ĝk〉] = 〈gk,E[sign ĝk]〉 (16)
= d∑ i=1 gk,i · E[sign ĝk,i] = ∑
1≤i≤d gk,i 6=0
gk,i · E[sign ĝk,i] (17)
= ∑
1≤i≤d gk,i 6=0
gk,i (ρi(xk) sign gk,i + (1− ρi(xk))(− sign gk,i)) (18)
= ∑
1≤i≤d gk,i 6=0
(2ρi(xk)− 1)|gk,i| = d∑ i=1 (2ρi(xk)− 1)|gk,i| = ‖gk‖ρ. (19)
Plugging this into (15) and taking full expectation, we get
E‖gk‖ρ ≤ E[f(xk)]− E[f(xk+1)] γk + dL̄ 2 γk. (20)
Therefore
K−1∑ k=0 γkE‖gk‖ρ ≤ (f(x0)− f∗) + dL̄ 2 K−1∑ k=0 γ2k. (21)
Now, in case of decreasing step sizes γk = γ0/ √ k + 1
min 0≤k<K E‖gk‖ρ ≤ K−1∑ k=0 γ0√ k + 1 E‖gk‖ρ /K−1∑ k=0 γ0√ k + 1
≤ 1√ K
[ f(x0)− f∗
γ0 + dL̄ 2 γ0 K−1∑ k=0 1 k + 1
]
≤ 1√ K
[ f(x0)− f∗
γ0 + γ0dL̄+
γ0dL̄
2 logK ] =
1√ K
[ f(x0)− f∗
γ0 + γ0dL̄
] + γ0dL̄
2 logK√ K .
where we have used the following standard inequalities
K∑ k=1 1√ k ≥ √ K, K∑ k=1 1 k ≤ 2 + logK. (22)
In the case of constant step size γk = γ
1
K K−1∑ k=0 E‖gk‖ρ ≤ 1 γK [ (f(x0)− f∗) + dL̄ 2 γ2K ] = f(x0)− f∗ γK + dL̄ 2 γ.
B.5 CONVERGENCE ANALYSIS: PROOF OF THEOREM 2
Clearly, the iterations {xk}k≥0 of Algorithm 1 (Option 2) do not increase the function value in any iteration, i.e. E[f(xk+1)|xk] ≤ f(xk). Continuing the proof of Theorem 1 from (20), we get
1
K K−1∑ k=0 E‖gk‖ρ ≤ 1 K K−1∑ k=0 E[f(xk)]− E[f(xk+1)] γk + dL̄ 2 γk
= 1
K K−1∑ k=0 E[f(xk)]− E[f(xk+1)] γ0 √ k + 1 + dL̄ 2K K−1∑ k=0 γ0√ k + 1
≤ 1√ K K−1∑ k=0 E[f(xk)]− E[f(xk+1)] γ0 + γ0dL̄√ K
= f(x0)− E[f(xK)]
γ0 √ K
+ γ0dL̄√ K
≤ 1√ K
[ f(x0)− f∗
γ0 + γ0dL̄
] ,
where we have used the following inequality K∑ k=1 1√ k ≤ 2 √ K.
The proof for constant step size is the same as in Theorem 1.
B.6 CONVERGENCE ANALYSIS IN DISTRIBUTED SETTING: PROOF OF THEOREM 3
First, denote by I(p; a, b) the regularized incomplete beta function, which is defined as follows
I(p; a, b) = B(p; a, b)
B(a, b) =
∫ p 0 ta−1(1− t)b−1 dt∫ 1
0 ta−1(1− t)b−1 dt
, a, b > 0, p ∈ [0, 1]. (23)
The proof of Theorem 3 goes with the same steps as in Theorem 1, except the derivation (16)–(19) is replaced by
E[〈gk, sign ĝ(M)k 〉] = 〈gk,E[sign ĝ (M) k ]〉
= d∑ i=1 gk,i · E[sign ĝ(M)k,i ]
= ∑
1≤i≤d gk,i 6=0
|gk,i| · E [ sign ( ĝ (M) k,i · gk,i )]
= ∑
1≤i≤d gk,i 6=0
|gk,i| (2I(ρi(xk); l, l)− 1) = ‖gk‖ρM ,
where we have used the following lemma. Lemma 7. Assume that for some point x ∈ Rd and some coordinate i ∈ {1, 2, . . . , d}, master node receives M independent stochastic signs sign ĝmi (x), m = 1, . . . ,M of true gradient gi(x) 6= 0. Let ĝ(M)(x) be the sum of stochastic signs aggregated from nodes:
ĝ(M) = M∑ m=1 sign ĝm.
Then E [ sign ( ĝ
(M) i · gi )] = 2I(ρi; l, l)− 1, (24)
where l = [(M+1)/2] and ρi > 1/2 is the success probablity for coordinate i.
Proof. Denote by Smi the Bernoulli trial of node m corresponding to ith coordinate, where “success” is the sign match between stochastic gradient and gradient:
Smi := { 1, if sign ĝmi = sign gi 0, otherwise ∼ Bernoulli(ρi). (25)
Since nodes have their own independent stochastic gradients and the objective function (or dataset) is shared, then master node receives i.i.d. trials Smi , which sum up to a binomial random variable Si:
Si := M∑ m=1 Smi ∼ Binomial(M,ρi). (26)
First, let us consider the case when there are odd number of nodes, i.e. M = 2l − 1, l ≥ 1. In this case, taking into account (25) and (26), we have
Prob (
sign ĝ (M) i = 0
) = 0,
ρ (M) i := Prob
( sign ĝ
(M) i = sign gi ) = Prob(Si ≥ l),
1− ρ(M)i = Prob ( sign ĝ (M) i = − sign gi ) .
It is well known that cumulative distribution function of binomial random variable can be expressed with regularized incomplete beta function:
Prob(Si ≥ l) = I(ρi; l,M − l + 1) = I(ρi; l, l). (27)
Therefore,
E [ sign ( ĝ
(M) i · gi
)] = ρ
(M) i · 1 + (1− ρ (M) i ) · (−1)
= 2ρ (M) i − 1 = 2Prob(Si ≥ l)− 1 = 2I(ρi; l, l)− 1.
In the case of even number of nodes, i.e. M = 2l, l ≥ 1, there is a probability to fail the vote Prob ( sign ĝ
(M) i = 0
) > 0. However using (27) and properties of beta function5 gives
E [ sign ( ĝ
(2l) i · gi )] = Prob(Si ≥ l + 1) · 1 + Prob(Si ≤ l − 1) · (−1)
= I(ρi; l + 1, l) + I(ρi; l, l + 1)− 1 = 2I(ρi; l, l)− 1
= E [ sign ( ĝ
(2l−1) i · gi
)] .
This also shows that in expectation there is no difference between having 2l − 1 and 2l nodes.
B.7 CONVERGENCE ANALYSIS IN DISTRIBUTED SETTING: VARIANCE REDUCTION
Here we show exponential variance reduction in distributed setting in terms of number of nodes. We first state the well-known Hoeffding’s inequality: Theorem 5 (Hoeffding’s inequality for general bounded random variables; see (Vershynin, 2018), Theorem 2.2.6). Let X1, X2, . . . , XM be independent random variables. Assume that Xm ∈ [Am, Bm] for every m. Then, for any t > 0, we have
Prob ( M∑ m=1 (Xm − EXm) ≥ t ) ≤ exp ( − 2t 2∑M m=1(Bm −Am)2 ) .
5see https://en.wikipedia.org/wiki/Beta_function#Incomplete_beta_function
Define random variables Xmi , m = 1, 2, . . . ,M showing the missmatch between stochastic gradient sign and full gradient sign from node m and coordinate i:
Xmi := { −1, if sign ĝmi = sign gi 1, otherwise
(28)
Clearly EXmi = 1− 2ρi and Hoeffding’s inequality gives
Prob ( M∑ m=1 Xmi −M(1− 2ρi) ≥ t ) ≤ exp ( − t 2 2M ) , t > 0.
Choosing t = M(2ρi − 1) > 0 (because of SPB assumption) yields
Prob ( M∑ m=1 Xmi ≥ 0 ) ≤ exp ( −1 2 (2ρi − 1)2M ) .
Using Lemma 24, we get 2I(ρi, l; l)− 1 = E [ sign ( ĝ (M) i · gi )] = 1− Prob ( M∑ m=1 Xmi ≥ 0 ) ≥ 1− exp ( −(2ρi − 1)2l ) ,
which provides the following estimate for ρM -norm:( 1− exp ( −(2ρ(x)− 1)2l )) ‖g(x)‖1 ≤ ‖g(x)‖ρM ≤ ‖g(x)‖1,
where ρ(x) = min1≤i≤d ρi(x) > 1/2.

heading: C CONVERGENCE RESULT FOR STANDARD SGD
text: For comparison, here we state and prove non-convex convergence rates of standard SGD with the same step sizes. Theorem 6 (Non-convex convergence of SGD). Let ĝ be an unbiased estimator of the gradient∇f and assume that E‖ĝ‖22 ≤ C for some C > 0. Then SGD with step sizes γk = γ0/ √ k + 1 converges as follows
min 0≤k<K E‖∇f(xk)‖22 ≤ 1√ K
[ f(x0)− f∗
γ0 + γ0CLmax
] + γ0CLmax
2
logK√ K . (29)
In the case of constant step size γk ≡ γ > 0
1
K K−1∑ k=0 E‖∇f(xk)‖22 ≤ f(x0)− f∗ γK + CLmax 2 γ. (30)
Proof. From L-smoothness assumption we have
E[f(xk+1)|xk] = E[f(xk − γkĝk)|xk]
≤ f(xk)− E[〈gk, γkĝk〉] + Lmax
2 γ2kE[‖ĝk‖22]
= f(xk)− γk‖gk‖22 + Lmax
2 γ2k E[‖ĝk‖22].
Taking full expectation, using variance bound assumption, we have
E[f(xk+1)]− E[f(xk)] ≤ −γk E‖gk‖22 + Lmax
2 γ2kC
Therefore γkE‖gk‖22 ≤ E[f(xk)]− E[f(xk+1)] +
CLmax 2 γ2k
Summing k = 0, 1, . . . ,K − 1 gives K−1∑ k=0 γkE‖gk‖22 ≤ (f(x0)− f∗) + CLmax 2 K−1∑ k=0 γ2k.
Now, in case of decreasing step sizes γk = γ0/ √ k + 1
min 0≤k<K E‖gk‖22 ≤ K−1∑ k=0 γ0√ k + 1 E‖gk‖22 /K−1∑ k=0 γ0√ k + 1
≤ 1√ K
[ f(x0)− f∗
γ0 + CLmax 2 γ0 K−1∑ k=0 1 k + 1
]
≤ 1√ K
[ f(x0)− f∗
γ0 + γ0CLmax + γ0CLmax 2 logK ] =
1√ K
[ f(x0)− f∗
γ0 + γ0CLmax
] + γ0CLmax
2
logK√ K .
where again we have used inequalities (22). In the case of constant step size γk = γ
1
K K−1∑ k=0 E‖gk‖22 ≤ 1 γK [ (f(x0)− f∗) + CLmax 2 γ2K ] = f(x0)− f∗ γK + CLmax 2 γ.

heading: D RECOVERING THEOREM 1 IN (BERNSTEIN ET AL., 2019) FROM
text: THEOREM 1
To recover Theorem 1 in (Bernstein et al., 2019), first note that choosing a particular step size γ in (7) yields
1
K K−1∑ k=0 E‖gk‖ρ ≤ √ 2dL̄(f(x0)− f∗) K , with γ = √ 2(f(x0)− f∗) dL̄K . (31)
Then, due to Lemma 1, under unbiasedness and unimodal symmetric noise assumption, we can lower bound general ρ-norm by mixed l1,2 norm. Finally we further lower bound our l1,2 norm to obtain the mixed norm used in Theorem 1 of Bernstein et al. (2019): let Hk = {1 ≤ i ≤ d : σi < √ 3/2|gk,i|}
5
√ dL̄(f(x0)− f∗)
K ≥ 5√
2
1
K K−1∑ k=0 E‖gk‖ρ
≥ 5√ 2 1 K K−1∑ k=0 E‖gk‖l1,2 = 5√ 2 1 K K−1∑ k=0 [ d∑ i=1 g2i |gi|+ √ 3σi ]
≥ 5√ 2 1 K K−1∑ k=0 E 2 5 ∑ i∈Hk |gk,i|+ √ 3 5 ∑ i/∈Hk g2k,i σi  ≥ 1 K K−1∑ k=0 E ∑ i∈Hk |gk,i|+ ∑ i/∈Hk g2k,i σi
 .

heading: E STOCHASTIC SIGNSGD
text: Our experiments and the counterexample show that signSGD might fail to converge in general. What we proved is that SPB assumption is roughly a necessary and sufficient for general convergence. There are several ways to overcome SPB assumption and make signSGD to work in general, e.g.
scaled version of signSGD with error feedback (Karimireddy et al., 2019). Here we to present a simple way of fixing this issue, which is more natural to signSGD. The issue with signSGD is that sign of stochastic gradient is biased, which also complicates the analysis.
We define stochastic sign operator s̃ign, which unlike the deterministic sign operator is unbiased with appropriate scaling factor.
Definition 3 (Stochastic Sign). Define the stochastic sign operator s̃ign : Rd → Rd as( s̃ign g ) i = { +1, with prob. 12 + 1 2 gi ‖g‖2
−1, with prob. 12 − 1 2 gi ‖g‖2
, 1 ≤ i ≤ d,
and s̃ign0 = 0 with probability 1.
Furthermore, we define stochastic compression operator C : Rd → Rd as C(x) = ‖x‖2 · s̃ignx, which compresses rd bits to r + d bits (r bits per one floating point number). Then for any unbiased estimator ĝ we get
E [C(ĝ)] = E [E[C(ĝ) | ĝ]] = E [ ‖ĝ‖2 ( 1
2 +
1
2
ĝ
‖ĝ‖2
) − ‖ĝ‖2 ( 1
2 − 1 2 ĝ ‖ĝ‖2
)] = E[ĝ] = g,
Var [C(ĝ)] = E [ ‖C(ĝ)− ĝ‖22 ] = E [ ‖C(ĝ)‖22 ] − E [ ‖ĝ‖22 ] = (d− 1)E‖ĝ‖22.
Using this relations, any analysis for SGD can be repeated for stochastic signSGD giving the same convergence rate with less communication and with (d− 1) times worse coefficients. Another scaled version of signSGD investigated in Karimireddy et al. (2019) uses non-stochastic compression operator C′ : Rd → Rd defined as C′(x) = ‖x‖1d signx. It is shown (see Karimireddy et al. (2019), Theorem II) to converge as
1
K K−1∑ k=0 E‖∇f(xk)‖22 ≤ 2 (f(x0)− f∗) γK + γLmaxC 2 + 4d(d− 1)γ2L2maxC,
where the error of current gradient compression is stored to be used in the next step. On the other hand, adopting the analysis of Theorem 6 for the stochastic compression operator C, we get a bound
1
K K−1∑ k=0 E‖∇f(xk)‖22 ≤ f(x0)− f∗ γK + γLmaxCd 2 ,
where no data needs to be stored. Furthermore, ignoring the factor 2 at the first term, later bound is better if γ ≥ 1/8dLmax.

Review summaries:
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.

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.