On Stochastic Sign Descent Methods
Authors: Mher Safaryan
Peter Richtárik
Venue:  (2020)
Keywords: non-convex optimization
stochastic optimization
gradient compression

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.

Under review as a conference paper at ICLR 2020
ON STOCHASTIC SIGN DESCENT METHODS
A Anonymout mous authors
Paper under double-blind review
ABSTRACT
Various gradient compression schemes have been proposed to mitigate the com- munication cost in distributed training of large scale machine learning models. Sign-based methods, such as signSGD (Bernstein 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 general analy- sis of sign-based methods for non-convex optimization. Our analysis is built on intuitive bounds on success probabílities and does not rely on special noise distri- butions nor on the boundedness of the variance of stochastic gradients. Extending the theory to distributed setting within 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.
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 state-of-theeart deep learning models deployed in industry typically rely on datasets large to fit the memory of a single computer, and hence the training data is typically split and stored across number of compute nodes capable of working in parallel. Training such models then amounts solving optimization problems of the form
min f(x) =
Σ (z).
where fm : Rd + represents the non-convex loss of a deep learning model parameterized by Rdd associated with data stored on node m.
Arguably, stochastic gradient descent (SGD) (Robbins & Monro 1951] Vaswani et al. 2019 Qian
al. 2019) in of its many variants (Kingma & Baj (015) Duchi al. 201 Schmidt al., 2017] Zeiler 2012) Ghadimi & Lan, (013) is the most popular algorithm for solving ( In its basic implementation, all workers m {1,2,... M) in parallel compute a random approximation
(Ix) of V fm (Zx), known as the stochastic gradient. These approximations are then sent to
master node which performs the aggregation
M g(xx) = E
The aggregated vector is subsequently broadcast back to the nodes, each of which performs update of the form
Tk+1 3g 7x. (xxx,, thus updating their local copies of the parameters of the model.
1.1 GRADIENT COMPRESSION
Typically, communication the local gradient estimators gTt (#xz to the master forms the bottleneck of such system (Seide et al.] 2014 Zhang al.) [017]] Lin et al.) 2018). In an attempt 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 al. 2017 Khirirat et al. 2018

---

Under review as a conference paper at ICLR 2020
Table I: 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
This work
SGD (Sec.
[Brrsttii et al. 2019) SignSGDD Thcorem
Theorem
Theorem
Step size
O+
O
x
7k = ?
R
Step size
7/k
y
70
Vx
VR
Vx
x
Step size
O
1
7
O
VK
VR
VR
VR
VK
Can handle biased estimators?
x
x
Weak dependence smoothness parameters?
Σ
Σ
T
x max I,, c=l
1/ I,
Σ
6m
im1
x unimodal, symmetric & Varlg:] S of
Weak noise assumptions?
/
x B B 3 v c
Ps 1
P >
Gradient norm used in theory
A mix ( and 12 norms
p-norm
p-norm
(squared) 1
Mishchenko et al. 2019). A compression scheme is (possibly randomized) mapping Q: : Rd + Rd applied by the nodes to g''((rx (ax) (and possibly also by the master to aggregated update in situations when broadcasting is expensive well) in order to reduce the number of bits of the communicated message.
Sign-based compression. Although most of the existing theory is limited unbiased compression schemes, i.e., on operators Q satisfying [QQ(x)) = I, biased schemes such as those based on communicating signs of the update entries only often perform much better (Seide al., 2014 Strom
2015; Wen et al. 2017 Carlson et al. 2015: Balles & Hennig 2018 Bernstein et al. 2018 2019
Zaheer al. 2018 Liu et al.] 2019). The simplest among these sign-based methods is signSGD (see
also Algorithm| | Option 1), whose update direction is assembled from the component-wee wiiee 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 signSGD. Connection between sign-based and adaptive methods has long history, originating at least in Rprop (Riedmiller & Braun [993) and
RMSprop (Tieleman Hinton 2012). Therefore, investigating the behavior of signSGD can improve understanding on the convergence of adaptive methods such as ADAM.
1.2 CONTRIBUTIONS
We now summarize the main contributions of this work. Our key results are summarized in Table
In fact, bounded variance assumption, being weaker than bounded second moment assumption, is stronger (or, be strict, more curtain) than SPB assumption in 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. /en.
wi wwl.iipdaaaa.ro... iferentt a___etttetttteeeee __entrorpyy ropy).
2

---

Under review as a conference paper at ICLR 2020
2 methods for 1-node setup. In the M case, study two general classes of sign based methods for minimizing a smooth non-convex function f. The first method has the standard form"
Ik+1 - 2k - Yi sign ((*x),
(2)
while the second has a new form not considered in the literature hefore:
1h41 arg min ( (mx), f Th sign ((*)))}
(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 ((Tx) of the true gradient V fx("). In sharp contrast with existing approaches, we allow g(Tx) to be biased. Remarkably, we only need one additional and rather weak assumption
f(xx) for the methods provably converge: we require the signs of the
entries of (zzz) to be equal to the signs of the entries of V v=(x") with a probability strietly larger
than 1/2 (see Section 2 Assumption Ip. We show through counterexample (see Section 2.2 that
this assumption is necessary.
Geometry. As a byproduct of our analysis, we uncover a mixed [1222 geometry of sign descent methods (see Section 3).
Convergence theory. We perform a complexity analysis of methods ( and (see Section Theorem D). While our complexity bounds have the same O(//K) dependence on the number of iterations, they have a better dependence on the smoothness parameters associated with f. Theorem is the first result on signSGID for non-convex functions which does not rely on mini-batching, and which allows for step sizes independent the total number of iterations K. Finally, Theorem in Bernstein et al. (2019) can be recovered from our general Theorem I Our bounds are cast in terms of a novel norm-like function, which we call the p-norm, which is a weighted / 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 bignbbseed compression of the aggregated gradients.
SUCCESS PROBABILITIES AND GRADIENT NOISE
In this section we describe our key (and weak) assumption on the gradient estimator ((x) of the true gradient fxx), and give example which shows that without this assumption, method ( can fail.
2.1 SUCCESS PROBABILITY BOUNDS
Assumption (SPB: Success Probability Bounds). For any Rd, have access indepen- dent (and not necessarily unbiased) estimator g(x) of the true gradient g(x) == ff(x) that satisfies
(x = Prob ()) sign (x())) > 2/2 if g(x) #
(4)
for all x E Rd and all i (1,2....
We will refer to the probabilities p as success probabilities. As we will see, they play a central role the convergence of sign based methods. We stress that Assumption iss 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 P 1, and an overly noisy stochastic gradient, in which case P; 1
Remark 1. Assumption 7 can be relaxed by replacing bounds ( with
E [siign (ā:(x)) g (x))) > O, if gi(x) #0.
However, if Prob(sign (x) 0) (e.g. in the case of (x( has continuous distributions), then these two bounds are identical.
siggn g is applied element the entries f1,02, .......... Ie of E Rd, For E R we define sign f if t signt 0 lift 0, and signt -1 if
3

---

Under review as a conference paper at ICLR 2020
Extension to stochastic sign oracle. Notice that we do not require be unbiased. Moreover, do not assume uniform boundedness of the variance, or of the second moment. This observation allows to extend existing theory to more general Signbaseed methods with stochastic sign oracle. By a stochastic sign oracle we mean an oracle that takes F& E IR as an input, and outputs a random vector & Rd with entries in +1. However, for the sake of simplicity, in the rest of the paper will work with the signSGD formulation, i.c., we let & sign ((r))
2.2 A COUNTRREXAMPLE 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,
min (=) = 1 [ z)² (a2, =} a1 [[ite]] 02 = 1 =ER2
where ε E (0, 1) and stochastic gradient ī(x) = V (a;, x)² 2(a;, x)); with probabilities 1/2 for [[21, ²2): 21 + 22 2] initial point 20 for the algorithm and notice that sign (x) = =(1, -1) for any I E L. Therefore, signSGD with any step-size sequence remains stuck along the line I, whereas the problem has a unique minimizer the origin.
i = 1, Let take any point from the line
We now investigate the cause of the divergence. In this counterexample, Assumption iis violated. Indeed, note that
sign ((x) (-1)) sign(a,;) [T'] with probabilities
1 for i= 1,2.
By S = {I E IR:; (01.x). (a2,z) > 0} # 0 denote the open cone of points having either an acute or an obtuse angle with both as's. Then for any x E S, the sign of the stochastic gradient is (1, (1,-1) with probabilities 1/2. Hence for any x E S, we have low success probabilities:
(x(x)= Prob (sign 9 (x) sign (x)) 2 i 1=1,2
So, in this case have entire conic region with low success probabilities, which clearly violates (4). Furthermore, if we take a point from the complement open cone S", then the sign of stochastic gradient equals to the sign of gradient, which is perpendícular to the axis of (thus in the next step of the iteration we get closer to S). For example, if (01, x) < O and (az, æ) > 0, then signg(z) = 11) with probability in which case - sign (zz) gets closer low success probability region S.
In summary, this counterexample there is conic region where the sign of the stochastic gradient is useless (or behaves adversarially), and for any point outside that region, moving direction (which 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 gradient noise. Lemma 1 (see B. Assume that for any point x E Rd, we have access to an independent and unbiased estimator g(x) of the true gradient g(x). Assume further that each coordinate ýi has a unimodal and symmetric distribution with variance o² = of(x)), S i S d. Then Pi 2
19:1 33, 9/30
if 9: # O.
Next, we remove the distribution condition and add a strong growth condition (Schmidt & Le Roux 2013
Vaswani al. 2019) together with fixed mini-bate size.
Lemma 2 (see B.2 Assume that for any point x E gd, we have access to an independent, unbiased estimator g(x) of the true gradient g gxx), with coordinate-wise bounded variances of (x) S cg (a)
for some constant Then, choosing mini-batch size 2c, we get p. 2 - o/T 2 if + 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 Ed we have access an independent and unbiased estimator ((x) of the true gradient g(x). Let of = (x be the variance and v² = vž (x)
be the 3th central moment of (x)),, 1 I i S d. Then SPB assumption holds if mini-batch size
2 min (07/02, 22/10,12/1o.00)) v2/1..)3).
4

---

Under review as a conference paper at ICLR 2020
20
40
900
100
-10
-05
0.0
1.0
Figure 1: Contour plots of the 11.2 norm (5) at 4 different scales with fixed noise
3 A NEW "NORM" FOR MEASURING THE SIZE OF THE GRADIENTS
In this section we introduce the concept of norm-like function, which call p-norm, induced from success probabilities. Used to measure gradients in convergence rates, p-norm is technical tool enabling the analysis.
Definition (p-norm). Let p= {pi())}i be the collection of probability functions from the SPB assumption. We define the p-norm of gradient g(x) via [[g()))le = Ei=1(2p:22) 1))9<()))-
Note that p-norm is norm it may satisfy the triangle inequality. However, under SPB assumption, p-norm is positive definite as it is a weighted I norm with positive (and variable) weights (x) > 0. That is, lIglIe 0, and ||l||p
if and only g O. Under the assumptions of Lemma 2 p-norm can be lower bounded by weighted 1 norm with positive constant weights 1 1-2c 2eg IIlll Σ (2p, 1) 2 Σi= 2c 19a|. Under the assumptions of Lemma p-norm can be lower bounded by mixture of the 12 and squared 1 norms:
||le| = Σ (2p: - 1)
Bll+v30. = l 1g
(5)
Note that n1-2-norm is again not a norm. However, is positive definite, continuous and order preserving, i.e., for any g², 9. 9 Rd we have: [ Ip and ||g||n.2 0 if and only g 0: ii) g" + (in sense) implies l1g" + ||l||r. and iii) 0 < S 9. for any 1 < S d implies |لg||a. S || From these three properties follows that | ll - implies g 0. These properties are important as we will measure convergence rate in terms of the 11.2 norm in the case of unimodal and symmetric noise assumption. To understand the nature of the f1.2 norm, consider the following two cases when (x) I (2)) + for some constants c, é 2 0. If the iterations are in e-neighbourhood of minimizer x² with respect to the f norm (i.e., maxigiçd [9:| S E), then f1.2 norm is equivalent scaled (2 norm squared:
1 11 On (1+V3c)e+v3ā |1 113 < [[9 [g]122.2 Vie
the other hand, if iterations are away from minimizer (i.e., minigiga [g.1 > L), then the 1.22-morm is equivalent to scaled norm: I+v3(cte/L) ||g|] S Ilol|n.> 3 I+V3c 1 These equivalences are visible in Figure where we plot the level sets of >> || at various distances from the origin. Similar mixed norm observation also noted in Bernstein al. (2019).
4 CONVERGENCE THEORY
Now we turn to our theoretical results of sign based methods. First 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 + is lower bounded, i.c., f(x) 2 fr, e Rd and is L-smooth with some non-negative constants L [In,..., La). That is, assume that (v) < f(x) +V)))()(()))))) x) + Ei= Li (y x2)² for all x, y E Rd, We allow f to be nonconvex. Let 1, E, L, and Lmax = max; Li-
4.1 CONVERGENCE ANALYSIS FOR M =
We now state convergence result for Algorithm 1 under the general SPB assumption.
5

---

Under review as a conference paper at ICLR 2020
Algorithm 1 SIGNSGD
Input: step size 7h. current point 2%
2: Øt f- StochasticGradien((()
3: Option 1: 3+++1 + It * sign 9k
4: Option 2: 74+1 < arg min (f (Tx), f(rx - 7A sign (k)}
Theorem (Non-convex convergence of signSGD, see B.4 Under the SPB assumption, signSGD
(Algorithm /
with Option 1) with step sizes "ik = 7u/ V converges as follows
min OSkCK
[[V[((>)]l>>> S VK %
((a)-f + vodī.
+
JodT. log K
(6)
VK
7h y O, we get 1/K convergence neighbourhood of the solution:
# Σ ElVS(a>)ll S f(x0)=1"
K-1
7K + al
27
We now comment on the above result:
Generalization. Theorem 1 is the first general result on signSGD for non-convex functions without 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 stronger assumptions than our SPB assumption (see Lemma Dp. Finally, Theorem 1 in Bernstein et al. 2019) can be recovered from Theorem (see Section D for the details).
Convergence rate. Rates (6) and 7 can be arbitrarily slow, depending on the probabilities p. This is to be expected. At one extreme, if the gradient noise was completely random, i..., if pj = 1/2, then the p-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., = 1, then the p-norm would be just the I norm and from (6) we get the rate (1/VK) with respect the I norm. However, if we know that p; 1/2, then eventually converge.
ensure that the method will
Geometry. The presence of the p-norm in these rates suggests that there no particular geometry (e.g.. 1- or (2) associated with signSGD. Instead, the geometry induced from the success probabili- ties. For example, the case of unbiased and unimodal symmetric noise, the geometry is described by the mixture norm 11.2
Practicality. The rate 7 (as well as (30) supports the common learning schedule practice of using a constant step size for period of time, and then halving the step-size and continuing this process.
For reader interested in comparing Theorem I with a standard result for SGD, we state the standard We now state general convergence rate for Algorithm with Option 2.
result in the Section C
Theorem (see
B.5
Under the SPB assumption, Algorithm 7 (Option 2) with step sizes 7
Jo/ Vi: converges as follows: K EK- E (())) S VK
[x00) +/odL In the case
of constant step size "
=1 > O, the same rate as is achieved.
Comparing Theorem 2 with Theorem notice that a small modification in Algorithm C 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 (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 present the convergence result of distributed signSGD (Algorithm () 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

---

Under review as a conference paper at ICLR 2020
2003
00.0 Ve4
(330
9g
4y500.
583
131
#gr0c0 75m
dg1500 2077
45 0540
100
125
230
louddon
Figure 2: Experiments on distributed signSGD with majority vote using Rosenbrock function. Plots show function values with respect to iterations averaged over repetitions. Left plot used constant step size 0.02, right plot used variable step size with " = 0.02. We set mini-batch size 1 and used the same initial point. Dashed blue lines show the minimum value.
back the sign sent by the majority of nodes. Known convergence results (Bernstein et al. 2018 2019) use ((K) mini-batch size as well as O(1/K) constant step size. In the sequel we remove this limitations extending Theorem T to distributed training. In distributed setting the number of nodes M get involved in geometry introducing new Par-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 ], current point Tk, # of nodes M
2: on each node
9 (**) + StochasticGradien((z))
4: server
5: pull sign ('r(((((()))) (Ix) from each node
6: push sign Em=il sign (xxx) to each node
M
7: on each node
8: Ek+1 f- " sign
EM
sign 9"r (x*)
Definition 2 (pmr-norm) Let M 2 1 be the number of nodes and | = M+1 Define pM noon of
gradient g(x) at x E Id as [lg()))lp. Σi= (2)()) - 1) [g:(
Now we can state the convergence rate of distributed signSGD with majority vote. Theorem (Non-convex convergence of distributed signSGD, see B.6]. Under SPB assumption,,
distributed signSGD (Algorithm with step sizes 7 70/ /k: + converges follows
f(zo)_f' rod 2nd2 log K minoskeK K E V (xx))les I VR 70
(8)
JK
For constant step sizes = > 0, we have convergence to a level proportional to step size "y:
K K
( <
f(2o)-8' 7K
+
si. 2
Variance Reduction. Using Hoeffding's inequality, we show that [[g()))] PM + [|g(x) expo- nentially fast as M + 0o: [1 - exp (-(2p(x) - 1)) [|g(z)]lı < [lg(x))))x < 1|g(=)]lı, where p(x) = minggiga (x(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 2 and 2/ nodes, and this in not limitation of the analysis. Indeed, it is shown the proof, expected sign vector the master with 2/ nodes the same as with M = nodes: E sign( (21) g:) E signn() (2t-1) g,), where ((a)) 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 21, fails to provide any sign
7

---

Under review as a conference paper at ICLR 2020
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 = 21 - 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 parameter server framework with odd number of nodes.
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:
-<=)=EE - f1(z== > 100(z,41 x])² (1 (1-zz)) zz)², E R
(10)
Stochastic formulation of minimization problem for Rosenbrock function is as follows: at any point Rd we have access to biased stochastic gradient ((x) f(())) + &. where index is chosen uniformly at random from (1,2.... 1} and & ~ NO0, 2² with v > 0.
42400
Tool
Men 112
Figure 3: Comparison of signSGD and SGD on MNIST dataset with fixed budget of gradient communication (MB) using single hidden layer FNN. For each batch size, first the constant step size over logarithmic scale {10, 1, 0.1, 0.01, 0.001} and then fine tune it. Clearly, signSGD beats SGD we compare their accuracies against communication. As suggested by the theory (see Lemma 3) bigger mini-batch size increases the success probabilities and thus improves the convergence.
Figure illlstrates the effect of multiple nodes in distributed training with majority vote. As increasing the number of nodes improves the convergence rate. It also supports the claim that in expectation there is no improvement from 2/ nodes to 2/ 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 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 1.
8

---

Under review as a conference paper at ICLR 2020
1100
Figure 4: Performance of signSGD with constant step size (7 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.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances in Neural Information Process- ing Systems 30, pp. 1709-1720, 2017.
Lukas Balles and Philipp Hennig. Dissecting Adam: The sign, magnitude and variance of stochastic gradients. In Proceedings of the 35th International Conference on Machine Learning, pp. 404-413, 2018.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Proceedings of the 35th Interna- tional Conference on Machine Learning, volume 80, pp. 560-569, PMLR, 2018
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In International Conference on Learning Representations, 2019.
Léon Bottou and Yann Le Cun. Large scale online learning. In Advances in Neural Information Processing Systems, 2003.
David Carlson, Volkan Cevher, and Lawrence Carin. Stochastic spectral descent for restricted boltz- mann machines. In International Conference on Artificial Intelligence and Statistics (AISTATS),
pp. 111-119, 2015.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Journal of Machine Learning Research, pp. 2121-2159, 2011.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. In SIAM Journal on Optimization, volume 23(4), pp. 2341-2368. 2013.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. Proceedings of the 36th International Conference Machine Learning, volume 97, pp. 3252-3261, 2019.

---

Under review as a conference paper at ICLR 2020
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. In arXiv preprint arXiv:1806.06577 2018.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations 2015.
Alex Krizhevsky, nya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
Yujun Lin, Song Han, Huizi Mao. Yu Wang, and William J. Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. International Conference on Learning Representations, 2018.
Sijia Liu, Pin-Yu Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In International Conference Learning Representations, 2019.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. In arXiv preprint SEti::9911002669 2019.
Xun Qian, Peter Richtárik, Robert Mansel Gower, Alibek Sailanbayev, Nicolas Loizou, and Egor Shulgin. SGD with arbitrary sampling: General analysis and improved rates. In International Conference on Machine Learning, 2019.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2019.
Martin Riedmiller and Heinrich Braun. A direct adaptive method for faster backpropagation learning: The Rprop algorithm. In IEEE International Conference on Neural Networks, pp. 586-591, 1993.
Herbert Robbins and Sutton Monro. A stochastic approximation method. In The Annals of Mathe- matical Statistics, volume 22(3), pp. 400-407, 1951.
Jürgen Schmidhuber. Deep learning neural networks: An overview. In Neural networks, volume 61, pp. 85-117, 2015.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. In arXiv preprint arXiv: 6370, 2013.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. In Mathematical Programming, volume 162(1-2), pp. 83 13-112, 2017.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and application to data-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Irina Shevtsova. On the absolute constants in the berry-esseen type inequalities for identically distributed summands. In arXiv preprint arXiv:1111.6554 2011.
Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In Sixteenth Anmual Conference of the International Speech Communication Association, 2015.
Tijmen Tieleman and Geoffrey E. Hinton. RMSprop. In Coursera: Neural Networks for Machine Learning, Lecture 6.5, 2012.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over- parameterized models (and an accelerated perceptron). In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, PMLR, volume 89, 2019.
Roman Vershynin. High- Dighe-Dimesiooall Probability: An Introduction with Applications in Data Science. Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi: 10.1017/978 108231596.
10

---

Under review as a conference paper at ICLR 2020
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-effcee -efficinnn learning via atomic sparsification. In Advances in Neural Information Processing Systems, 2018.
Wei Wen, Cong Xu, Feng Yan, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternry gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, pp. 1509-1519, 2017.
Ashia Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal
value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148-4158, 2017.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 9815- 9825, 2018.
Matthew D. Zeiler. ADADELTA: An Adaptive Learning Rate Method. In arXiv e-prints, 122.5512 2012.
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipMI: Training linear models with end-to-end low precision, and little bit of deep learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 4035-4043, 2017.

---

Under review as a conference paper at ICLR 2020
Appendix: "On Stochastic Sign Descent Methods
A EXTRA EXPERIMENTS
In this section we perform several additional experiments for further insights.
641
Figure 5: Performance of signSGD with variable step size (7o 0.25) under four different noise levels (mini-batch size 1, 2, 5, 7) using Rosenbrock function. As the experiments of Figure with 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.
12

---

Under review as a conference paper at ICLR 2020
24
14
130
Figure 6: In this part of experiments we investigated convergence rate ( to neighborhood of the solution. We fixed gradient noise level by setting mini-batch size 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 y 0.1 and y = 0.05 to expose the convergence to neighborhood of the minimizer. For the forth column we set even smaller step size y 0.01 to observe a slower convergence.
0=0
0=1.0
d=2.0
-2
Figure Unit balls in 11. norm 5 with different noise levels.
13

---

Under review as a conference paper at ICLR 2020
B PROOFS
B. SUFFICIENT CONDITIONS FOR SPB: PROOF OF LEMMA 1
Here state the well-known Gauss's inequality unimodal distributions
Theorem (Gauss's 's inequality). Let X be a unimodal random variable with mode m, and let o be the expected value of (X m)². Then for any positive value of
if
V3 0m
3
Prob([X ml
otherwise
Applying this inequality unimodal and symmetric distributions, direct algebraic manipulations give the following bound:
1 4
(g) 9
if S otherwise
r/o r/o v3
Prob[|X 1r)
v3
where I and oft x² are the mean and variance of unimodal, symmetric random variable X, and 2 O. Now, using the assumption that each (x) has unimodal and symmetric distribution, we apply this bound for X (x),, / (x),, o² (xx) and get bound for success probabilities
Prob(i 2 0). if gf > 0
Prob(sign 9: = sign 9i)
Prob(u: $ 0). if <
+ Prob(0 S Å: $ 9t),
if > 0 if <0 0 if gi if gi <
2 + Prob(g, $ 9; $ 0),
[] PPobb(O < 9. 2g:);
2 + 2 Prob((2g: S ÿ: S 0);
-
Probbll:: gil S (g:l)
1 Vul/o:
2
2 1//l/ar + v3
[gi
2
2 1gal + V30g
Improvment Lemma and (1.2 norm: The bound after Gauss inequality can be improved
including a second order term
1
(g)
if
3 2
Prob(IX 11 ()) 2
2 1 1 4t/3/50 + (3/v36)22
otherwise
v
1+2+22 it reduces to 23z" - 44= 4 0. Otherwise, 0 2/3, then I+ as reduces to 23 The improvement tighter as
Indeed, letting ::=-/v8 > 2/3, we get 32
r/a r/o + v3 1 1/v3r
$1
1 r/V3o (3/V30)2
Hence, continuing the proof of Lemma
we get
1
1
Prob(sign 9. sign g.) 2
2 214 la /V3a, + (la1l/30.)2
and we could have defined 1l.2- -orm in bit more complicated form as
|
:= Σ
1 i 1+ la: //lll///,,, (la.)/ (1l/
lg.
httph:tt///// www.wwkippdd.
14

---

- of T Under review as a conference paper at ICLR 2020
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(r) is dropped by at least factor of т, i.e.
Hence, estimating the failure probabilities of sign g(T) when 9: # 0, we have
Prob(signg))" () + sign gi)
= Prob(lg! gil = 1 + [g:
< Prob(lg) yil 2 [g:
= Prob((e! -gi)² 2 g.
E((0)" - 9:
9
of T9i
which imples
of
6
P: = Prob(sign 0: = sign 9i) 2
2
T9;
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.00 X2..... X, be i.i.d. random variables with non-zero mean == EX1 # 0. finite variance a² == E|X1 112 so. Then for any mini-batch size T 2
a²
Prob
sign
Σ
X,
sign 1
2
(11)
TH²
Proof. Without loss of generality, assume from the Chebyshev's 's inequality:
0. Then, after some adjustments, the proof follows
Prob
sign
Σ i=1
X
sign /
Prob
X, >
2 Prob
Σ
<H
(1:
Prob
Σ
X₂ - 21
1=1
2
Var
Σ X,
412
a2
T
where in the last step we used independence of random variables X,, X X X,.
Obviously, bound 111) is not optimal for big variance as it becomes trivial inequality. In the case of non-small randomness a better bound is achievable additionally assuming the finitness of 3th central moment.
15

---

Under review as a conference paper at ICLR 2020
Lemma 5. Let X2 X1, .,....,,, x be i.i.d random variables with non-zero μ = EX2 # 0.
positive variance o² == 1| 4/? > 0 and finite 3th central moment v = E - 11/² < 00.
Then for any mini-batch size 2 1
1/1 + orf
[IlvT) /20
o³ o2/7):
23
Prob
sign
X;
sign μ
2
(12)
where error function erf is defined as
2 erf(x) Vir 0 e e-2 dt, ZER.
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- -essen incquality on the rate of approximation in CLT (Shevtsova) 2011
v3 2 tER,
Prob
Σ (x, -(=+))>+)) 1=1
[x,
Prob (N > t) S
oVT
where ~ NO 1) has the standard normal distribution. Setting t = -u/T/// 0 we get
Prob Σ X =0)
0)
0)
- Prob (N> PVT
في
S 2 203/
(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:
1
{ X;
Prob
sign
X; i=1
sign /
Prob
> 0
i=1
MVT
1 33
Prob
N
2 20 VT
1
11 dt
D3
2T
203
2
/VTio
e - dt
13
1+ V
2
0
03 /
1
HVT
v3
1 erf
2
/2a
σ VT
Clearly, bound (2) is better than (I] when randomness is high. On the other hand, bound 12 not optimal for small randomness (a zs 0). Indeed, one can show that in a small randomness regime, while both variance o² and third moment 3 small, the ration v/a might blow up to infinity producing trivial inequality. For instance, taking X; ~ Bernoulli(p) and letting + 1 gives v/o= = O ((1 p) -Vo). This behaviour stems from the fact that we are using CLT: less randomness implies slower rate of approximation in CLT.
As result of these two bounds on success probabilities, we conclude a condition on mini-batch size for the SPB assumption to hold.
/en. wi ht
16

---

Under review as a conference paper at ICLR 2020
Lemma 6. Let X2, X, be i.id. random variables with non-zero mean o 0 and finite variance o² < co. Then
X2......
1 322" )>
o² في
Prob
sign
X;
sign j
if T
2mi
(14)
n12 |u|o2)
where v is (possibly infinite) 3th central moment.
Proof. First, if then the lemma holds trivially. If v oc, then follows immediately from Lemma 4 Assume both a and are positive and finite.
In case of > 20²/p² we apply Lemma again. Consider the case S <202/p² which implies PvT < 1. It is easy to check that er) is concave on [0, 1] (in fact on [0, oo)), therefore erf(x) 2 V2a
(1) for any x E [0, 1]. Setting x
we get
v2o
erf PVT
erf(1) uVT
/20
V2
which together with 12 gives
(
erf(1) PVF
1
Prob
sign
X,
sign
2
1
V2
σ V
1=1
Hence, SPB assumption holds if
V2 v3
erf(l) μO²2
e" It remains show that e1f(1) > 1/V2. Convexity e" E [-1,0] implics e" 1+ (1 1/e)x for any æ E [-,,0]. Therefore
erf(l)
2
-- dt
TT
1
2
(1 - (1 - 1/0)(²) dl
nT
0
2
>
= >
VT
3e
4
3
9
22
Lemma 3
follows from Lemma
applying it to ii.d. data (x). ......... .M. (x).
B.4 CONVERGENCE ANALYSIS: PROOF OF THEOREM
First, from I-smoothness assumption we have
(xx+11 = [( - 7 sign (R)
L;
< ((xx) - (gk, 7hh sign 9K) +
(7x sign )
2
1=1
dL
= =((x)) - 7h (gt, sign (k)
2 7k-
g is the i-th component of ÔR and L is the average value of L,'s. Taking conditional expectation given current iteration Fa gives
where 9b = ( åx = g(xx),
dī
()f( < f(xx) - Egg sign 9x)] +
2 7
(15)
17

---

Under review as a conference paper at ICLR 2020
Using the definition of success probabilities Ps get
E (gk: sign gu)l
(gk, 12 siggn gu])
(16)
Tk.s E sign 9R,1 = Σ gk.t Elsign 9k,e]
(17)
1sisd
9k,1%
Σ
Ikss (ps (3Ta) sign Ia.t + (1 - (===p((=))( sign 9k.i))
(18)
1stsd
90,150
d
Σ (2pz(ark) - 1) = Σ (2p((Tx)) -
(19)
1=1
Plugging this into 15 and taking full expectation, we get
[[[(xx)] - (Fx((xx))))
dL
E g ll S
+
(20)
7k
2
Therefore
dL
Σ LE (f(10) -
Σ
7k
2
(21)
Now, in case of decreasing step sizes 7 = /kt
1
K-1
min oskck
7o
Bl
Σ
VK
V
k=0
h=0
dl f(xo) f-
Σ k
K
To
2
10
++1
f(xo) -f"
+ todL + YodL
log K
VK
[(xO) -
+ TdL log
+ mad..
K
YO
2 K
where we have used the following standard inequalities
K
K
2
K,
Σ
< 2 + log K.
(22)
VT
k
1=1
In the case of constant step size 7/k 7
K-1
Σ
Ellaulle v
- [(((a))))++ -
dī.
= f(xa) 8 dī.
K +
2 7.
K 0==
7
2
18

---

Under review as a conference paper at ICLR 2020
B.5
CONVERGENCE ANALYSIS: PROOF OF THEOREM 2
Clearty, the iterations J220 of Algorithm (Option 2) do not increase the function value in any iteration, i.e. ([((+++) 1)( S (xx). Continuing the proof of Theorem from 20 we get
K-1
K
- -B(f(x++)]]())
+ di
Σ
B 1llgllee -
K K=
K
7
B[f(xx)] - [[[([R++]]
Vk ++
dL
70
K
70
2K k=0
k
+
B[f(r))] ((((+++)
RodL.
7o
K
K=O
(I0) [[f(x))] RodE
T0 YoVK
VK
fzo) - f
+ rodL
70
where we have used the following inequality
k
Σ
S 2VK.
The proof for constant step size is the same as in Theorem
B.6 CONVERGENCE ANALYSIS IN DISTRIBUTED SETTING: PROOF OF THEOREM 3
First, denote by (p: a, b) the regularized incomplete beta function, which is defined as follows
a( B(p; b) fht tat=-( (1 t)6-1 dt
B)a,b) fo ta-1(1 t)² h- di a, 0, p E (0, 1].
(23)
The proof of Theorem 3 goees with the same steps as Theorem I except the derivation 16 replaced by
19 is
E (ok sign (("r)) (gh, E Eiiign ok (1))
(M) 9k.t Elsign Ik.t
law.el E. [sign (g( ge.ss
15idd
Σ Isidd
Igw.el (2)() -1= 11ghllew
where we have used the following lemma.
Lemma 7. Assume that for some point Rd and some coordinate i (1,2,.... d}, master node receives M independent stochastic signs sign (r' (I), m = 1,..., M of true gradient (( # 0. Let (x) be the sum of stochastic signs aggregated from nodes:
M
g(a))
sign gmH
Then
E sign
9
(M)
91
= 21 21
(24)
where [(M+1)/2] and P 1/2 the success probablity for coordinate i.
19

---

Under review as a conference paper at ICLR 2020
Proof. Denote S the Bernoulli trial of node corresponding to ith coordinate, where "success" the sign match between stochastic gradient and gradient:
1, if sign O."h = sign Bernoulli(p)).
(25)
0. otherwise
Since nodes have their independent stochastic gradients and the objective function (or dataset) is shared, then master node receives i..dd trials S,", which sum up to binomial random variable S,:
S. = S. Binomial(M)) M, Pt).
(26)
m==
First, let us consider the case when there are odd number of nodes, i.e. M = 21 - 1, 2 1. In this case, taking into account (25) and (6)). we have
Prob sign 9 (()) = =0) 0,
P
(M) Prob sign 9 (M)
sign gi Prob(S; 2 1),
Pi
(M)
Prob
sign 9
(M) sign gi
It is well known that cumulative distribution function of binomial random variable can be expressed with regularized incomplete beta function:
Prob(S, 2 () = (pnl - 1+ (pp),,))
(27)
Therefore,
E sign (0( 9.)] = (M) 1 11 (-1) = (31) (x)) -
2Prob(S; 2 21 -
21(pri,11) 1.
In the case of even number of nodes, i.e. M 21, 2 1, there probability to fail the vote
Prob sigu 9j (M) 0) 0. However using (7) and properties of beta function gives
sign (2)) 99 = Prob(S: 2 1 Prob(S, -1- (-1)
I(pel + 1,4) [(pa1,++)
1, -
E sign g
(2-1)
gi
This also shows that in expectation there is no difference between having 21 - and 2/ 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- Hoeffding's inequality:
Theorem (Hoeffding's 's inequality for general bounded random variables; see (Vershynin 2018).
Theorem 2.2.6). Let XI, X2,..., .....,X,, XM independent random variables. Assume that Xm (Am, Bm) for every m. Then, for any > 0, we huve
2t2
Prob
Σ ( EXm) 2
S exp
Em= (Bm,
Am )
httth:ttt/ee... wiiipiiia wrr./wkwiii wttp:iiiiiieaaaaae /at////ttaaafttoaaeeeeeeeae on Incompl beta_ aate_beta_uunction
20

---

Under review as a conference paper at ICLR 2020
Define random variables X;", 1, 2, M showing the missmatch between stochastic gradient sign and full gradient sign from node m and coordinate t:
1, if sign 0."h sign otherwise
(28)
Clearly EX;;" =
=1- 2p; and Hoeffding's s inequality gives
t²
Prob
Σ
X
M(1 2p:) 2t S exp
t 0.
2M
m==1
Choosing / - (2p; 1) > 0 (because of SPB assumption) yields
exp (-2 (2p: - 113MM
Prob
Σ X 20
m=1
Using Lemma
24
we get
M Σ
(p;,,1;1)) - = E sign (M)
9t ] 1- Prob
X 0 2 1 exp (-(2pt - 1))2),
m=
which provides the following estimate for Par-norm:
(1 - exp (-(2p(x) 1))() [[x())] - (lx()))lex S I1g(<))11,
where p(z) (in 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 (Non-conves convergence of SGD). Let 9 be an unbiased estimator of the gradient f and assume that || S C' for some C > Then SGD with step sizes Vik = =10/ Vk converges as follows
[(xo) - S + Lmax + C0 log K
min
(29)
o<k<k
70
2
K
In the case of constant step size 7/k = 7 >
f(zo) fr
CLiaxx 7.
f
+
(30)
JK
2
Proof. From L-smoothness assumption we have
B[f(#x+1)lzz] = [I] 7x.k [
Lmax 11
S f(xx) - (g mH +
2
Limax
= f(xx) - 7* 11g 12 +
72 Ellláx
2
Taking full expectation, using variance bound assumption, we have
L
- < -7x E11g
22
2
Therefore
CLuax
E1 < E[f(xx)] (ff()x+1)]
2
21

---

Under review as a conference paper at ICLR 2020
Summing & = 0, ,K., gives
K
Clmax
K-1
Blg - (f(zo) 1*)
2 Tkk
k=0
Now, in case of decreasing step sizes .k = =0/vk++ +1
1
K-1
min 0Skck
9
2
S
Ta
Bllgall
7o
Vk +
0=0
Rm
1
f(00) f +
C'Imax
Σ k
70
VK
70
(300) - + To CL
Tumax
log K
K
Yu
f(x0) -f + 3a CL
70 70C
log K
VK
Y0
2 vK K
where again have used inequalities
22
In the of constant step size 7 ?
Σ
Elgh
1
(f(xo) - -() C. 22K
f(0u) f
C
2 7.
gk
2
D RECOVERING THEOREM IN (BERNSTEIN ET AL., 2019) FROM
THEOREM I
To recover Theorem in (Bernstein et al. 2019), first note that choosing a particular step size y in yields
2dL f*)
with 7 2(f(xo) fr) dLK
E gl
(31)
K
K
Then, due to Lemma 1 under unbiasedness and unimodal symmetric noise assumption, can lower bound general p-norm by mixed [1.2 norm. Finally we further lower bound our (1.2 norm to obtain the mixed norm used in Theorem of Bernstein et al. (0019) let H₂ {1 i S d: < v3/2|gr..l3
di(s(ro) S*)
5
K
5
E Ellgl
K
22
K
K-1 1
5
5
E El
2 K
/2
K
9i
+
130
k=
km
i=1
5
K
2
v3
FE.
E
l9h.el +
2 K
5
A=
iEHt
i 11
K
Ihat
E
Ig
+
k=0
EEH.
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 overcome SPB assumption and make signSGD work in general, e.g.
22

---

Under review as a conference paper at ICLR 2020
scaled version of signSGD with error feedback (Karimireddy et al. 2019). Here present simple way fixing this issue, which is more natural to signSGD. The issue with signSGD that sign of stochastic gradient is biased, which also complicates the analysis.
We define stochastic sign operator sign, which unlike the deterministic sign operator is unbiased with appropriate scaling factor.
Definition (Stochastic Sign), Define the stochastic sign operator sign RR + R
sign 9);
+1,
with prob. 2
+ 3 lala
9:
isisd,
-1,
with prob. islla
and sign 0 O with probability 1.
Furthermore, we define stochastic compression operator C Rd R2 as C(x) ||^|| sign æ, which compresses rd bits to r + bits (r bits per one floating point number). Then for any unbiased estimator 9 we get
1
9
)
E [C(O) E [ 0l E
|1
+
Elgl 9.
2
1|ā1||
|1
Var [C(Ø)] E
[C(()) 0122 = E [|((()) - E ||061
1
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 Cz ||||| sign x. It is shown (see Karimireddy
al. (2019), Theorem II) converge as
K-1 Σ K
(f((z)) -f) f*) BlVS(EI)
Imaa + 4d(d 11---)12220 L
K
2
where the error of current gradient compression is stored to be used in next step. On the other hand, adopting the analysis of Theorem 6 for the stochastic compression operator C, we get bound
M(x)) S
Immax
Σ E [
K
2
where data needs to be stored. Furthermore, ignoring the factor 2 at the first term, later bound is better if 7 2 1/8dLmax.
23


Reviews:
[{"review_id": "rJxqaMwTtS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nI 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. \n\nHow 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. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJeobaJAFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nThis 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.\n\nThis paper is well-written and nicely structured and I like the relationships of SPB with other conditions. However, I have some concerns on the generality of SPB that I will detail below.\n\n- First of all, Lemma 2 is not clear to me at all. The authors say that the variance is bounded by a constant (0 \\leq c_i < 1/sqrt{2}) multiplied by the true gradient norm and then they show that this assumption implies SPB. I do not know how restrictive this condition is. For example, what happens when all elements of true gradient is close to zero, I don’t know if it is reasonable to assume the noise to be small for this case. I cannot make the connection of this assumption and the classical bounded variance assumption (E((\\hat{g_i}-g_i)^2)\\leq\\sigma_i). I can believe the result of Lemma 3 with specific constants $c_i$ as given, but I feel that it is then much stronger than standard bounded variance assumption. Because it would be asking the variance to be smaller than some specific constant.\n\n- Related to first point, I did not understand the remark in the first footnote of page 2. The authors argue that SPB is weaker than bounded variance assumption. But at the same time, it is known that bounded variance assumption is not enough to make signSGD work, with counterexamples given in Karimireddy et. al. 2019. So, it is quite weird that an assumption weaker than bounded variance (for which signSGD provably does not convergence) makes signSGD converge. So I think it is more natural for SPB to be stronger than bounded variance, because it is enough to make signSGD work. The only proof in the paper that would support this claim is Lemma 2, as I discussed above is stronger than standard variance bound. I hope that authors can clarify this point.\n\n- After Theorem 1, the authors compare their result with Bernstein et. al. 2019 and mention that Bernstein et. al. needs to use mini-batches depending on $K$ where $K$ is the iteration and unimodal symmetric noise assumption. But when I check Bernstein et. al. 2019, I see that these are different cases. Specifically, Theorem 1 in Bernstein et. al. 2019, uses mini-batch size 1 under unimodal symmetric noise assumption. The case where they would use mini-batches of size $K$ is in Section 3.3 of Bernstein et. al. 2019 where they *drop* unimodal symmetric noise assumption. So, I would suggest the authors to be more exact on this comparison because it is confusing. In fact, in Section 3.3 of Bernstein et. al. 2019, the authors also identify SPB as it is implied by unimodal symmetric noise assumption. It is the paragraph under Lemma 1 in Bernstein et. al. 2019.\n\n- My other concern is the comparison with Karimireddy et. al. 2019 both in theory and practice. Karimireddy et. al. 2019 modifies signSGD and under unbiased stochastic gradients and bounded variance assumption, obtains similar guarantees as this paper. I am aware that this paper does not assume unbiasedness, but like I said before, I do not know how SPB compares to variance bound. So, I see Karimireddy et. al. 2019 and this paper as similar results, so I would want to see some practical comparison as well. In Appendix E, the authors mention that Karimireddy et. al. 2019 has storage need but I think that need is negligible since they only need to store one more vector.\n\n- A side-effect of SPB is that now the convergence results are given in $\\rho$-norm where $\\rho$ is determined by SPB. I understand why this is needed from the proof of Theorem 1, and its implications in the theorem, but given that Karimireddy et. al. 2019’s result is given in l_2 norm which is easier to interpret, I think more comparison is needed.\n\n- Lastly, I like the fact that SPB is implied by the previous assumption in Bernstein et. al. 2019, namely unimodal symmetric noise, I am not convinced that SPB is much weaker than this assumption. The authors mention in several places in the paper that their assumption is very weak, but looking at Lemma 1, Lemma 2 and Lemma 3: Lemma 1 and Lemma 3 are the already known cases where signSGD works, and Lemma 2 is a new case where signSGD works but as I explained before, it is not clear to me how restrictive this assumption is. Therefore, I am rather unsure if this generalization of SPB is practically significant.\n\nMinor comments:\n- page 2, Table 1: I think it would be useful to add the results of Karimireddy et. al. 2019.\n- page 2, Table 1 and footnote 1: Footnote sign is given for the bounded stochastic gradient assumption but the explanation in the footnote text talks about the bounded variance assumption. Of course bounded stochastic gradient implies bounded variance, but this should be clarified. In addition, the footnote text is not clear to me, could the authors either point out to some references or give a proof?\n- page 2, Adaptive methods paragraph: The end of the paragraph says that signSGD is similar to Adam so, studies on signSGD *can* improve the understanding of Adam. I would be happy if the authors are more exact about this, such as when signSGD is equivalent to Adam etc.\n- page 3 discussion after Assumption 1: I do not understand the sentence starting with ‘Moreover, we argue that’. Can the authors give more details on why it is reasonable?\n- page 4 Lemma 2: I think the authors should include the definition of variance in the paper. Since the assumption in this Lemma is rather non-standard, I think it makes sense to be as exact as possible.\npage 21, Appendix E: It is written that ‘SPB is roughly a necessary and sufficient condition’. I could not understand what *roughly* means in this sentence. From what I have read, the authors have a counter-example showing without SPB, signSGD does not work and with SPB, it works, so I could not understand why it is written roughly here.\n\nOverall, I like the generalization of SPB, but as I detail above, I am not sure how significant the generalization is compared to other results and more specifically how it compares to standard bounded variance (which I believe is weaker than Lemma 2). Therefore, I remain not convinced about the impact of this generalization hence the results. In addition, I would have liked to see more comparisons (both theoretical and practical) with Karimireddy et. al. 2019.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJl9kDNE5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nIn my view the paper presents a relatively minor but still interesting extension of the work in Bernstein (2019). The main problem is that the relaxation is not well motivated in terms of scenarios where this might be applicable. Experimental validation is also very weak.\n\nIt is claimed in the experiment section that the stochastic gradient of the Rosenbrock function g(x) = \\del f_i(x) + eps, where eps is a 0-mean Gaussian and i is uniform random is biased. This seems incorrect to me and the gradient estimate should be unbiased when the expectation is taken over the randomness in i and eps.\n\nA key claim of the paper is the ability to use biased gradient estimates. Experimental validation of this (in light of the above) is completely missing.\n\nThe experiments that are presented on MNIST are very general and not very closely connected to the specific claims of the paper. The only real conclusion drawn is that larger batch sizes improve convergence.\n\nI think the paper needs better targeted experiments. They need to show covergence in a case where the conditions in Berstein (2019) do not hold.\n\nHow are the properties of the \\rho norm related to the observations on l_1 norm for high and l_2 norm for low SNR components in Bernstein (2019)? If they are related this should be referenced.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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

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

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