Title: ON STOCHASTIC SIGN DESCENT METHODS

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.

1. INTRODUCTION:

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

EQUATION

where f m : R d → R represents the non-convex loss of a deep learning model parameterized by x ∈ R d 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 ĝm (x k ) of ∇f m (x k ), known as the stochastic gradient. These approximations are then sent to a master node which performs the aggregation

ĝ(x k ) := 1 M M m=1 ĝm (x k ).

The aggregated vector is subsequently broadcast back to the nodes, each of which performs an update of the form

x k+1 = x k -γ k ĝ(x k ),

thus updating their local copies of the parameters of the model.

1.1. GRADIENT COMPRESSION:

Typically, communication of the local gradient estimators ĝm (x k ) 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;  Table 1 : Summary of the theoretical results obtained in this work. Õ notation ignores logarithmic factors and O * notation shows the rate to a neighbourhood of the solution.

This work Theorem 1:

This work Theorem 2 SGD (Sec. C) Theorem 6 (Bernstein et al., 2019) signSGD, Theorem 1

Step size

γ k ≡ γ O * 1 K O * 1 K O * 1 K

Step size γ k = γ 0

• 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 

EQUATION

while the second has a new form not considered in the literature before:

x k+1 ← arg min{f (x k ), f (x k -γ k sign ĝ(x k ))}.

(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 ĝ(x k ) of the true gradient ∇f (x k ). In sharp contrast with existing approaches, we allow ĝ(x k ) to be biased. Remarkably, we only need one additional and rather weak assumption on ĝ(x k ) for the methods to provably converge: we require the signs of the entries of ĝ(x k ) to be equal to the signs of the entries of ∇f (x k ) 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 l 1 -l 2 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 l 1 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.

2. SUCCESS PROBABILITIES AND GRADIENT NOISE:

In this section we describe our key (and weak) assumption on the gradient estimator ĝ(x) of the true gradient ∇f (x), and give an example which shows that without this assumption, method (2) can fail.

2.1. SUCCESS PROBABILITY BOUNDS:

Assumption 1 (SPB: Success Probability Bounds). For any x ∈ R d , we have access to an independent (and not necessarily unbiased) estimator ĝ(x) of the true gradient g(x) := ∇f (x) that satisfies

ρ i (x) := Prob (sign ĝi (x) = sign g i (x)) > 1 2 , if g i (x) = 0 (4)

for all x ∈ R d 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 ≈ 1 2 . Remark 1. Assumption 1 can be relaxed by replacing bounds (4) with

E [sign (ĝ i (x) • g i (x))] > 0, if g i (x) = 0.

However, if Prob(sign ĝi (x) = 0) = 0 (e.g. in the case of ĝi (x) has continuous distributions), then these two bounds are identical.

Extension to stochastic sign oracle. Notice that we do not require ĝ 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 x k ∈ R d as an input, and outputs a random vector ŝk ∈ R d 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 ŝk = sign ĝ(x k ).

2.2. A COUNTEREXAMPLE TO SIGNSGD:

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∈R 2 f (x) = 1 2 a 1 , x 2 + a 2 , x 2 , a 1 = 1+ε -1+ε , a 2 = -1+ε 1+ε ,

where ε ∈ (0, 1) and stochastic gradient ĝ(x) = ∇ a i , x 2 = 2 a i , x a i with probabilities 1/2 for i = 1, 2. Let us take any point from the line l = {(z 1 , z 2 ) : z 1 + z 2 = 2} as initial point x 0 for the algorithm and notice that sign ĝ(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 ĝ(x) = (-1) i sign a i , x -1 1 with probabilities 1 2 for i = 1, 2. By S := {x ∈ R 2 : a 1 , x • a 2 , x > 0} =

∅ denote the open cone of points having either an acute or an obtuse angle with both a i '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 ĝi (x) = sign g i (x)) ≤ 1 2 , 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 Sc , 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 a 1 , x < 0 and a 2 , x > 0, then sign ĝ(x) = (1, -1) with probability 1, in which case x -γ sign ĝ(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.

2.3. SUFFICIENT CONDITIONS FOR SPB:

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 ∈ R d , we have access to an independent and unbiased estimator ĝ(x) of the true gradient g(x). Assume further that each coordinate ĝi has a unimodal and symmetric distribution with variance

σ 2 i = σ 2 i (x), 1 ≤ i ≤ d. Then ρ i ≥ 1 2 + 1 2 |gi| |gi|+ √ 3σi > 1 2 if g i = 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 ∈ R d , we have access to an independent, unbiased estimator ĝ(x) of the true gradient g(x), with coordinate-wise bounded variances σ 2 i (x) ≤ c g 2 i (x) for some constant c. Then, choosing a mini-batch size τ > 2c, we get

ρ i ≥ 1 -c /τ > 1 2 , if g i = 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 ∈ R d we have access to an independent and unbiased estimator ĝ(x) of the true gradient g(x). Let σ 2 i = σ 2 i (x) be the variance and

ν 3 i = ν 3 i (x) be the 3th central moment of ĝi (x), 1 ≤ i ≤ d. Then SPB assumption holds if mini-batch size τ > 2 min σ 2 i/g 2 i , ν 3 i /|gi|σ 2 i .

- 

3. A NEW "NORM" FOR MEASURING THE SIZE OF THE GRADIENTS:

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)} d i=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)|g i (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 l 1 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 l 1 norm with positive constant weights

1 -2c 2 i > 0: g ρ = d i=1 (2ρ i -1)|g i | ≥ d i=1 (1 -2c 2 i )|g i |.

Under the assumptions of Lemma 1, ρ-norm can be lower bounded by a mixture of the l 1 and squared l 2 norms:

EQUATION

Note that l 1,2 -norm is again not a norm. However, it is positive definite, continuous and order preserving, i.e., for any g k , g, g ∈ R d we have: i) g l 1,2 ≥ 0 and g l 1,2 = 0 if and only if g = 0;

ii) g k → g (in l 2 sense) implies g k l 1,2 → g l 1,2 , and iii) 0 ≤ g i ≤ gi for any 1 ≤ i ≤ d implies g l 1,2 ≤ g l 1,2 . From these three properties it follows that g k l 1,2 → 0 implies g k → 0. These properties are important as we will measure convergence rate in terms of the l 1,2 norm in the case of unimodal and symmetric noise assumption. To understand the nature of the l 1,2 norm, consider the following two cases when σ i (x) ≤ c|g i (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., max 1≤i≤d |g i | ≤ ε), then the l 1,2 norm is equivalent to scaled l 2 norm squared:

1 (1+ √ 3c)ε+ √ 3c g 2 2 ≤ g l 1,2 ≤ 1 √ 3c g 2 2 .

On the other hand, if iterations are away from a minimizer (i.e., min 1≤i≤d |g i | ≥ L), then the l 1,2 -norm is equivalent to scaled l 1 norm:

1 1+ √ 3(c+c/L) g 1 ≤ g l 1,2 ≤ 1 1+ √ 3c g 1 .

These equivalences are visible in Figure 1 , where we plot the level sets of g → g l 1,2 at various distances from the origin. Similar mixed norm observation was also noted in Bernstein et al. (2019) .

4. CONVERGENCE THEORY:

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 :

R d → R is lower bounded, i.e., f (x) ≥ f * , x ∈ R d and is L-smooth with some non-negative constants L = [L 1 , . . . , L d ]. That is, we assume that f (y) ≤ f (x) + ∇f (x), y -x + d i=1 Li 2 (y i -x i ) 2 for all x, y ∈ R d . We allow f to be nonconvex. Let L := 1 d i L i and L max = max i L i .

4.1. CONVERGENCE ANALYSIS FOR M = 1:

We now state our convergence result for Algorithm 1 under the general SPB assumption.

Algorithm 1 SIGNSGD 1: Input: step size γ k , current point x k 2: ĝk ← StochasticGradient(x k ) 3: Option 1: x k+1 ← x k -γ k sign ĝk 4: Option 2: x k+1 ← arg min{f (x k ), f (x k -γ k sign ĝk )}

Theorem 1 (Non-convex convergence of signSGD, see B.4). Under the SPB assumption, signSGD (Algorithm 1 with Option 1) with step sizes

EQUATION

)

If γ k ≡ γ > 0, we get 1 /K convergence to a neighbourhood of the solution:

EQUATION

)

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 l 1 norm and from ( 6) we get the rate Õ(1/ √ K) with respect to the l 1 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., l 1 or l 2 ) 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 l 1,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: 1 K K-1 k=0 E ∇f (x k ) ρ ≤ 1 √ K f (x0)-f * γ0 + γ 0 d L .

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.

4.2. CONVERGENCE ANALYSIS IN DISTRIBUTED SETTING:

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) 

x k+1 ← x k -γ k sign M m=1 sign ĝm (x k ) 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 ∈ R d as g(x) ρ M = d i=1 (2I(ρ i (x); l, l) -1) |g i (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

EQUATION

)

For constant step sizes γ k ≡ γ > 0, we have convergence up to a level proportional to step size γ:

EQUATION

)

Variance Reduction. Using Hoeffding's inequality, we show that g(x

) ρ M → g(x) 1 expo- nentially fast as M → ∞: 1 -exp -(2ρ(x) -1) 2 l g(x) 1 ≤ g(x) ρ M ≤ g(x) 1 , where ρ(x) = min 1≤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(ĝ

(2l) i • g i ) = E sign(ĝ (2l-1) i • g i ),

where ĝ(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.

5. EXPERIMENTS:

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

EQUATION

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. 

Appendix: "On Stochastic Sign Descent Methods":

A EXTRA EXPERIMENTS

In this section we perform several additional experiments for further insights. We fixed gradient noise level by setting mini-batch size 2 and altered the constant step size.

For the first column we set bigger step size γ = 0.25 to detect the divergence (as we slightly violated SPB assumption). Then for the second and third columns we set γ = 0.1 and γ = 0.05 to expose the convergence to a neighborhood of the minimizer. For the forth column we set even smaller step size γ = 0.01 to observe a slower convergence. 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 σ 2 m 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 -4 9 σ r 2 , if σ r ≤ √ 3 2 1 √ 3 r σ , otherwise ≥ r/σ r/σ + √ 3 ,

where m = µ and σ 2 m = σ 2 are the mean and variance of unimodal, symmetric random variable X, and r ≥ 0. Now, using the assumption that each ĝi (x) has unimodal and symmetric distribution, we apply this bound for X = ĝi (x), µ = g i (x), σ 2 = σ 2 i (x) and get a bound for success probabilities

Prob(sign ĝi = sign g i ) = Prob(ĝ i ≥ 0), if g i > 0 Prob(ĝ i ≤ 0), if g i < 0 = 1 2 + Prob(0 ≤ ĝi ≤ g i ), if g i > 0 1 2 + Prob(g i ≤ ĝi ≤ 0), if g i < 0 = 1 2 + 1 2 Prob(0 ≤ ĝi ≤ 2g i ), if g i > 0 1 2 + 1 2 Prob(2g i ≤ ĝi ≤ 0), if g i < 0 = 1 2 + 1 2 Prob(|ĝ i -g i | ≤ |g i |) ≥ 1 2 + 1 2 |g i |/σ i |g i |/σ i + √ 3 = 1 2 + 1 2 |g i | |g i | + √ 3σ i

Improvment on Lemma 1 and l 1,2 norm: The bound after Gauss inequality can be improved including a second order term

Prob(|X -µ| ≤ r) ≥ 1 -4 9 σ 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 -4 9 1 3z 2 ≥ 1 - 1 1+z+z 2 as it reduces to 23z 2 -4z -4 ≥ 0. Otherwise, if 0 ≤ z ≤ 2 /3, then z ≥ 1 - 1 1+z+z 2 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 ĝi = sign g i ) ≥ 1 - 1 2 1 1 + |gi| / √ 3σi + ( |gi| / √ 3σi) 2

and we could have defined l 1,2 -norm in a bit more complicated form as

g l 1,2 := d i=1 1 - 1 1 + |gi| / √ 3σi + ( |gi| / √ 3σi) 2 |g i |.

B.2 CONDITIONS FOR SPB: PROOF OF LEMMA 2:

Let ĝ(τ) be the gradient estimator with mini-batch size τ . It is known that the variance for ĝ(τ) is dropped by at least a factor of τ , i.e.

E[(ĝ:

(τ ) i -g i ) 2 ] ≤ σ 2 i τ .

Hence, estimating the failure probabilities of sign ĝ(τ) when g i = 0, we have

Prob(sign ĝ(τ) i = sign g i ) = Prob(|ĝ (τ ) i -g i | = |ĝ (τ ) i | + |g i |) ≤ Prob(|ĝ (τ ) i -g i | ≥ |g i |) = Prob((ĝ (τ ) i -g i ) 2 ≥ g 2 i ) ≤ E[(ĝ (τ ) i -g i ) 2 ] g 2 i = σ 2 i τ g 2 i ,

which imples

ρ i = Prob(sign ĝi = sign g i ) ≥ 1 - σ 2 i τ g 2 i ≥ 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 X 1 , X 2 , . . . , X τ be i.i.d. random variables with non-zero mean µ := EX 1 = 0, finite variance σ 2 := E|X 1 -µ| 2 < ∞. Then for any mini-batch size τ ≥ 1

Prob sign 1 τ τ i=1

EQUATION

)

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 X i = sign µ = Prob 1 τ τ i=1 X i > 0 ≥ Prob 1 τ τ i=1 X i -µ < µ = 1 -Prob 1 τ τ i=1 X i -µ ≥ µ ≥ 1 - 1 µ 2 Var 1 τ τ i=1 X i = 1 - σ 2 τ µ 2

, where in the last step we used independence of random variables X 1 , X 2 , . . . , 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. X 1 , X 2 , . . . , X τ be i.i.d. random variables with non-zero mean µ := EX 1 = 0, positive variance σ 2 := E|X 1 -µ| 2 > 0 and finite 3th central moment ν

EQUATION

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 (X i -µ) > t -Prob (N > t) ≤ 1 2 ν 3 σ 3 √ τ , t ∈ R,

where N ∼ N (0, 1) has the standard normal distribution.

EQUATION

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 X i = sign µ = Prob 1 τ τ i=1 X i > 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 X i ∼ 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.

Lemma 6. Let X 1 , X 2 , . . . , τ be i.i.d. random variables with non-zero mean µ = 0 and finite variance σ 2 < ∞. Then

EQUATION

)

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 X i = 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 e x on x ∈ [-1, 0] implies e x ≥ 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)t 2 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 ĝ1 i (x), ĝ2 i (x), . . . , ĝM i (x).

B.4 CONVERGENCE ANALYSIS: PROOF OF THEOREM 1:

First, from L-smoothness assumption we have

f (x k+1 ) = f (x k -γ k sign ĝk ) ≤ f (x k ) -g k , γ k sign ĝk + d i=1 L i 2 (γ k sign ĝk,i ) 2 = f (x k ) -γ k g k , sign ĝk + d L 2 γ 2 k ,

where g k = g(x k ), ĝk = ĝ(x k ), ĝk,i is the i-th component of ĝk and L is the average value of L i 's.

Taking conditional expectation given current iteration x k gives

EQUATION

)

Using the definition of success probabilities ρ i we get

EQUATION

Plugging this into (15) and taking full expectation, we get

EQUATION

EQUATION

Now, in case of decreasing step sizes

γ k = γ 0 / √ k + 1 min 0≤k<K E g k ρ ≤ K-1 k=0 γ 0 √ k + 1 E g k ρ K-1 k=0 γ 0 √ k + 1 ≤ 1 √ K f (x 0 ) -f * γ 0 + d L 2 γ 0 K-1 k=0 1 k + 1 ≤ 1 √ K f (x 0 ) -f * γ 0 + γ 0 d L + γ 0 d L 2 log K = 1 √ K f (x 0 ) -f * γ 0 + γ 0 d L + γ 0 d L 2 log K √ K .

where we have used the following standard inequalities

EQUATION

In the case of constant step size γ k = γ

1 K K-1 k=0 E g k ρ ≤ 1 γK (f (x 0 ) -f * ) + d L 2 γ 2 K = f (x 0 ) -f * γK + d L 2 γ.

B.5 CONVERGENCE ANALYSIS: PROOF OF THEOREM 2:

Clearly, the iterations {x k } k≥0 Algorithm 1 (Option 2) do not increase the function value in any iteration, i.e. E[f (x k+1 )|x k ] ≤ f (x k ). Continuing the proof of Theorem 1 from (20), we get

1 K K-1 k=0 E g k ρ ≤ 1 K K-1 k=0 E[f (x k )] -E[f (x k+1 )] γ k + d L 2 γ k = 1 K K-1 k=0 E[f (x k )] -E[f (x k+1 )] γ 0 √ k + 1 + d L 2K K-1 k=0 γ 0 √ k + 1 ≤ 1 √ K K-1 k=0 E[f (x k )] -E[f (x k+1 )] γ 0 + γ 0 d L √ K = f (x 0 ) -E[f (x K )] γ 0 √ K + γ 0 d L √ K ≤ 1 √ K f (x 0 ) -f * γ 0 + γ 0 d L ,

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. 

EQUATION

)

The proof of Theorem 3 goes with the same steps as in Theorem 1, except the derivation ( 16)-( 19) is replaced by

E[ g k , sign ĝ(M) k ] = g k , E[sign ĝ(M) k ] = d i=1 g k,i • E[sign ĝ(M) k,i ] = 1≤i≤d g k,i =0 |g k,i | • E sign ĝ(M) k,i • g k,i = 1≤i≤d g k,i =0 |g k,i | (2I(ρ i (x k ); l, l) -1) = g k ρ M ,

where we have used the following lemma. Lemma 7. Assume that for some point x ∈ R d and some coordinate i ∈ {1, 2, . . . , d}, master node receives M independent stochastic signs sign ĝm i (x), m = 1, . . . , M of true gradient g i (x) = 0. Let ĝ(M) (x) be the sum of stochastic signs aggregated from nodes:

EQUATION

where l = [ (M +1) /2] and ρ i > 1 /2 is the success probablity for coordinate i.

Proof. Denote by S m i the Bernoulli trial of node m corresponding to ith coordinate, where "success" the sign match between stochastic gradient and gradient:

EQUATION

Since nodes have their own independent stochastic gradients and the objective function (or dataset) is shared, then master node receives i.i.d. trials S m i , which sum up to a binomial random variable S i :

EQUATION

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 ĝ(M) i = 0 = 0, ρ (M ) i := Prob sign ĝ(M) i = sign g i = Prob(S i ≥ l), 1 -ρ (M ) i = Prob sign ĝ(M) i = -sign g i .

It is well known that cumulative distribution function of binomial random variable can be expressed with regularized incomplete beta function:

EQUATION

Therefore,

E sign ĝ(M) i • g i = ρ (M ) i • 1 + (1 -ρ (M ) i ) • (-1) = 2ρ (M ) i -1 = 2Prob(S i ≥ 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 ĝ(M) i = 0 > 0. However using ( 27) and properties of beta function5 gives

E sign ĝ(2l) i • g i = Prob(S i ≥ l + 1) • 1 + Prob(S i ≤ l -1) • (-1) = I(ρ i ; l + 1, l) + I(ρ i ; l, l + 1) -1 = 2I(ρ i ; l, l) -1 = E sign ĝ(2l-1) i • g i .

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 X 1 , X 2 , . . . , X M be independent random variables. Assume that X m ∈ [A m , B m ] for every m. Then, for any t > 0, we have

Prob M m=1 (X m -EX m ) ≥ t ≤ exp - 2t 2 M m=1 (B m -A m ) 2 .

Define random variables X m i , m = 1, 2, . . . , M showing the between stochastic gradient sign and full gradient sign from node m and coordinate i:

EQUATION

Clearly EX m i = 1 -2ρ i and Hoeffding's inequality gives

Prob M m=1 X m i -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 X m i ≥ 0 ≤ exp - 1 2 (2ρ i -1) 2 M .

Using Lemma 24, we get

2I(ρ i , l; l) -1 = E sign ĝ(M) i • g i = 1 -Prob M m=1 X m i ≥ 0 ≥ 1 -exp -(2ρ i -1) 2 l ,

which provides the following estimate for ρ M -norm:

1 -exp -(2ρ(x) -1) 2 l g(x) 1 ≤ g(x) ρ M ≤ g(x) 1 , where ρ(x) = min 1≤i≤d ρ i (x) > 1 /2.

C CONVERGENCE RESULT FOR STANDARD SGD:

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 ĝ be an unbiased estimator of the gradient ∇f and assume that E ĝ 2 2 ≤ C for some C > 0. Then SGD with step sizes

EQUATION

In the case of constant step size

EQUATION

Proof. From L-smoothness assumption we have

E[f (x k+1 )|x k ] = E[f (x k -γ k ĝk )|x k ] ≤ f (x k ) -E[ g k , γ k ĝk ] + L max 2 γ 2 k E[ ĝk 2 2 ] = f (x k ) -γ k g k 2 2 + L max 2 γ 2 k E[ ĝk 2 2 ].

Taking full expectation, using variance bound assumption, we have

E[f (x k+1 )] -E[f (x k )] ≤ -γ k E g k 2 2 + L max 2 γ 2 k C Therefore γ k E g k 2 2 ≤ E[f (x k )] -E[f (x k+1 )] + CL max 2 γ 2 k Summing k = 0, 1, . . . , K -1 gives K-1 k=0 γ k E k 2 2 ≤ (f (x 0 ) -f * ) + CL max 2 K-1 k=0 γ 2 k .

Now, in case of decreasing step sizes

γ k = γ 0 / √ k + 1 min 0≤k<K E g k 2 2 ≤ K-1 k=0 γ 0 √ k + 1 E g k 2 2 K-1 k=0 γ 0 √ k + 1 ≤ 1 √ K f (x 0 ) -f * γ 0 + CL max 2 γ 0 K-1 k=0 1 k + 1 ≤ 1 √ K f (x 0 ) -f * γ 0 + γ 0 CL max + γ 0 CL max 2 log K = 1 √ K f (x 0 ) -f * γ 0 + γ 0 CL max + γ 0 CL max 2 log K √ K .

where again we have used inequalities ( 22). In the case of constant step size γ k = γ

1 K K-1 k=0 E g k 2 2 ≤ 1 γK (f (x 0 ) -f * ) + CL max 2 γ 2 K = f (x 0 ) -f * γK + CL max 2 γ.

D RECOVERING THEOREM 1 IN (BERNSTEIN ET AL., 2019) FROM THEOREM 1

To recover Theorem 1 in (Bernstein et al., 2019) , first note that choosing a particular step size γ in (7) yields

EQUATION

)

Then, due to Lemma 1, under unbiasedness and unimodal symmetric noise assumption, we can lower bound general ρ-norm by mixed l 1,2 norm. Finally we further lower bound our l 1,2 norm to obtain the mixed norm used in Theorem 1 of Bernstein et al. (2019) : let

H k = {1 ≤ i ≤ d : σ i < √ 3 /2|g k,i |} 5 d L(f (x 0 ) -f * ) K ≥ 5 √ 2 1 K K-1 k=0 E g k ρ ≥ 5 √ 2 1 K K-1 k=0 E g k l 1,2 = 5 √ 2 1 K K-1 k=0 d i=1 g 2 i |g i | + √ 3σ i ≥ 5 √ 2 1 K K-1 k=0 E   2 5 i∈H k |g k,i | + √ 3 5 i / ∈H k g 2 k,i σ i   ≥ 1 K K-1 k=0 E   i∈H k |g k,i | + i / ∈H k g 2 k,i σ i   .

E STOCHASTIC SIGNSGD:

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, also complicates the analysis.

We define stochastic sign operator sign, which unlike the deterministic sign operator is unbiased with appropriate scaling factor. Furthermore, we define stochastic compression operator C : R d → R d as C(x) = x 2 • sign x, which compresses rd bits to r + d bits (r bits per one floating point number). Then for any unbiased estimator ĝ we get

E [C(ĝ)] = E [E[C(ĝ) | ĝ]] = E ĝ 2 1 2 + 1 2 ĝ ĝ 2 -ĝ 2 1 2 - 1 2 ĝ ĝ 2 = E[ĝ] = g, Var [C(ĝ)] = E C(ĝ) -ĝ 2 2 = E C(ĝ) 2 2 -E ĝ 2 2 = (d -1)E ĝ 2 2 .

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. 2019), Theorem II) to converge as

1 K K-1 k=0 E ∇f (x k ) 2 2 ≤ 2 (f (x 0 ) -f * ) γK + γL max C 2 + 4d(d -1)γ 2 L 2 max C,

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 (x k ) 2 2 ≤ f (x 0 ) -f * γK + γL max Cd 2 ,

where no data needs to be stored. Furthermore, ignoring the factor 2 at the first term, later bound is better if γ ≥ 1 /8dLmax.

:

sign g is applied element-wise to the entries g1, g2, . . . , g d of g ∈ R d . For t ∈ R we define sign t = 1 if t > 0, sign t = 0 if t = 0, and sign t = -1 if t < 0.

see https://en.wikipedia.org/wiki/Gauss%27s_inequality

see https://en.wikipedia.org/wiki/Berry-Esseen_theorem

see https://en.wikipedia.org/wiki/Beta_function#Incomplete_beta_function

Figures and Tables:

Figure 1: Contour plots of the l 1,2 norm (5) at 4 different scales with fixed noise σ = 1.

Figure 2: Experiments on distributed signSGD with majority vote using Rosenbrock function. Plots show function values with respect to iterations averaged over 10 repetitions. Left plot used constant step size γ = 0.02, right plot used variable step size with γ 0 = 0.02. We set mini-batch size 1 and used the same initial point. Dashed blue lines show the minimum value.

Figure3: Comparison of signSGD and SGD on MNIST dataset with a fixed budget of gradient communication (MB) using single hidden layer FNN. For each batch size, we first tune the constant step size over logarithmic scale {10, 1, 0.1, 0.01, 0.001} and then fine tune it. Clearly, signSGD beats SGD if we compare their accuracies against communication. As suggested by the theory (see Lemma 3) bigger mini-batch size increases the success probabilities ρ i and thus improves the convergence.

Figure 4: Performance of signSGD with constant step size (γ = 0.25) under four different noise levels (mini-batch size 1, 2, 5, 8) using Rosenbrock function. Each column represent a separate experiment with function values, evolution of minimum success probabilities and the histogram of success probabilities throughout the iteration process. Dashed blue line in the first row is the minimum value. Dashed red lines in second and third rows are thresholds 1/2 of success probabilities. The shaded area in first and second rows shows standard deviation obtained from ten repetitions.

Figure5: Performance of signSGD with variable step size (γ 0 = 0.25) under four different noise levels (mini-batch size 1, 2, 5, 7) using Rosenbrock function. As in the of Figure4with constant step size, these plots show the relationship between success probabilities and the convergence rate (6). In low success probability regime (first and second columns) we observe oscillations, while in high success probability regime (third and forth columns) oscillations are mitigated substantially.

Figure 7: Unit balls in l 1,2 norm (5) with different noise levels.

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)

Stochastic Sign). Define the stochastic sign operator sign : R d → R d as ≤ i ≤ d, and sign 0 = 0 with probability 1.

Another scaled version of signSGD investigated in Karimireddy et al. (2019) uses non-stochastic compression operator C : R d → R d defined as C (x) = x 1 d sign x. It is shown (see Karimireddy et al. (

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).

Table content: <table><tr><td colspan="3">Algorithm 2 DISTRIBUTED SIGNSGD WITH MAJORITY VOTE</td></tr><tr><td>6:</td><td>push sign</td><td>M m=1 sign ĝm (x k ) to each node</td></tr><tr><td colspan="2">7: on each node</td><td/></tr><tr><td>8:</td><td/><td/></tr></table>

Peer review (iclr2020):
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.