Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning

In this paper, we propose a communication-efficient decentralized machine learning (ML) algorithm, coined quantized group ADMM (Q-GADMM). Every worker in Q-GADMM communicates only with two neighbors, and updates its model via the alternating direct method of multiplier (ADMM), thereby ensuring fast convergence while reducing the number of communication rounds. Furthermore, each worker quantizes its model updates before transmissions, thereby decreasing the communication payload sizes. We prove that Q-GADMM converges for convex loss functions, and numerically show that Q-GADMM yields 7x less communication cost while achieving almost the same accuracy and convergence speed compared to a baseline without quantization, group ADMM (GADMM).

T H Z v / M g S 9 0 k 8 w g R e 3 f 5 k 8 1 K g 2 T u R T + t 7 V 3 e 9 N t I V M u w K Y u n V e L K z W q g J 7 v D k d G 8 Y C r q X u P d e v j I r L B 6 Y O X P P B 0 V S y v 2 p r O q u F J W r u j i a 1 3 7 W p d 9 u 6 y 3 Z N X c 1 h F W d d r r M u J a F 2 9 0 / Y 2 + Y e f 3 f h I 4 6 g K p t F N X S T 0 h 7 P z O r w d n c 5 U u x V N J 7 Q U n k 1 8 X n + 5 6 G M 7 z r F H U 1 V S d b 5 a P q X g k + + o 1 w S H Z x D Y 1 a a s m 1 T W U q G k L 9 i D U 0 g w y U h 2 a p Y u o e i Z F E 3 o r Q 1 C e T y W u 9 F 5 X P J K j i Z U / / X W x C C q p G V f j E E M v x t U c Z L W w V V 3 5 P Z E r e e N V Y X o c S P M + M z B n O Z D q L A e m y P M i r 4 r 7 a L F f n 9 Z I z U r 2 1 I t L l S 2 j r F 4 9 a F c P S D 3 A Y U X 7 / g + 0 d 9 i g X V 1 v r x I z k N a 9 5 z D h + W q N r D J T i z p R L o y o y r 4 T p u r + Y v r Z y G 4 t p n a U P t X T 2 k h X p W 5 s e G u E n r u e 7 3 f z E W R 6 A r W 6 Y r B / l F Y e k / 0 9 D 7 L U T T K P E L F 3 l z + G r D R I F l 7 0 w 9 r e 5 U 2 / i U S 1 D B u y e K w k r t y o B n q y M x o b z Q u m o u 4 1 3 q m H j 8 0 K q + e X z 1 y h o 2 J p x d 5 s X h V X y s o V X X y j a 9 / o s m + X 9 Z a s m t s 6 w q p O e 1 1 G X O v i j a 6 / 0 T f s / N 5 P A k d d I J V 2 6 i q p J 4 S d 3 / n 1 4 G y u 0 q V 4 K q m 9 4 G T y z 8 W n u x 6 G i z x r F H U 1 V e e b 5 2 M q n t C + e q Y 7 J J v a p i Z t 1 a S 6 h h I 1 b c E e h F q a Q U a q Q 7 N 0 E V X P p G h K b 2 U I y v O p x J X e m 4 r H c j y 1 8 p c B X S y C S m r G 1 T j E 0 I t x N Q d Z L W x V V 3 5 P 5 U r e e F W Y H g f S v H g M z F k O p D r L g S n y v M i r 4 j 5 a 7 N e n N V a z k j 3 1 5 l J l y z i r V w / a 1 Q N S D 3 B Y 0 b 7 / P e 0 d N m h X 1 9 u r x A y k d e 8 5 T H i + W i O r z N S i T p Q L I 6 q y 7 4 S p u r < l a t e x i t s h a 1 _ b a s e 6 4 = " n W 2 H + s g R m L D z 9 S J P V R k m N H v p e I X u 8 / n 3 z 6 o x / / 5 K c / + + z n S 7 / 4 5 a 9 + / Z s X n 3 9                can be accelerated via collaboratively adjusting the training momentum [14,15]. However, these methods commonly postulate a central server that collects model update information, which may not be scalable. In decentralized ML architectures without any central entity, communication payload sizes can be reduced by a quantized weight gossiping algorithm [16]. On the other hand, both communication links and rounds can be decreased using the group ADMM (GADMM) algorithm proposed in our prior work [17]. Spurred by these preceeding works, in this article we further integrate quantization into GADMM, and propose a communicationefficient decentralized ML algorithm, coined quantized group ADMM (Q-GADMM), thereby reducing communication rounds, links, and payload sizes altogether. Quantized Group GADMM (Q-GADMM). As shown in Fig. 1, Q-GADMM divides workers into head and tail groups as done in GADMM. For less communication rounds via faster convergence, the workers in the same group update their models in parallel, whereas the workers in different groups update the models in an alternating way using ADMM [18]. Every alternation entails a single communication round, in which each worker communicates only with two neighboring workers in the opposite group, reducing communication links. Lastly, before every transmission, the workers quantize their model parameters, decreasing communication payload sizes.

X K A m L s z a v E D a d 3 p R X o A 1 h 6 l A Q D V M Z J D K w b T k N D J o G 7 T n B i O D E T X o G H S C C o e p H E 4 l B q 3 Y A T u Y 2 y h V l f 4 8 e + S A a 9 m T V E 7 u 2 v O d O A Y x C 5 F K 8 c K 4 w g H X x k 1 l e 1 B H t k e 8 L 8 V 2 5 X 3 t J G g y 5 2 B X 9 9 s 1 B 9 / W s r l p b h G u p t F 2 R W 5 5 O t V I r p m q v t X J 8 9 h Q K L S p r Q q p u j D 1 S T D D x Z / M L q 6 3 i z J 7 o 4 r J d 7 p + + K B e u N Q L r J 7 c k / p f v v 9 z N V c i z T x I f n D e d K s 1 G L d R V h R K o Q 7 U g T I G Z r W r 0 Z X 1 l V c 8 g 8 6 g c + g c 6 k E 9 6 A f o B + g C u o D 6 U B / K o R w a Q O s X G D S E R l B U o P 0 R + h E a Q 2 N o A k 2 g A o p L 2 U 6 h K f Q e e g 9 9 g D 5 A H 6 G P 0 C f o E / Q T 9 B O 0 B + 0 V t z d d d p R E n i B + 1 2 d C / d h I d P Y G s j c w x i Z 0 E 9 q H 9 q E D 6 A C 6 B d 2 C b k O 3 o T v Q H e g u d B e 6 B 9 2 D 7 k P 3 o Q f Q A + g h 9 B B 6 B D 2 C D q F D 6 D H 0 G H o C P Y G e Q k + h I y g e 5 / Y Z 9 A x 6 D j 2 H j q F j 6 A X 0 A j q B T q C X 0 E v o F f Q K e g 2 9 1 j V V N O 3 / U 1 r c l J Z d K y 2 + C U V p 8 T 4 U p c U H U J Q W 3 4 K i t P g 2 F K X F d 6 A o L b 4 L R W n x P S h K i + 9 D U V r 8 A I r S 4 o d Q l B Y / g q K 0 + B C K 0 u L H U J Q W P 4 G i t P g p F K X F R 1 C U F j + D o r T 4 O R S l x c d Q l B a / g K K 0 + A S K 0 u K X U J Q W v 4 K i t P g 1 t C q t P v G 9 W U y i u U d f L i 2 6 g T e v D f M M 3 g S a x z x 9 6 U 2 f D o A D g 1 t A 8 7 O R b g P N g 5 3 u A H c M 7 g L N e w f d A + 4 Z 3 A f u G z w A H h h 8 6 U c H P Q K a H y t 0 C B w a P A Y e G z w B n h g 8 B Z 4 a H
Contributions. It is non-trivial to prove the convergence of Q-GADMM, in which quantization errors may lead to high unintended variance in model parameter updates. Its neighbor-based communications aggravate this problem, since the errors may easily propagate across iterations. To mitigate these problems, in this article we propose a novel stochastic quantization scheme that ensures unbiased model updates and non-increasing quantization step sizes, by adjusting the quantization levels and probabilities over iterations. We thereby prove that with exchanging the maximum range of quantization and the number of quantization levels, Q-GADMM achieves the convergence and the optimality of GADMM for convex, closed, and proper functions. Numerical results show that Q-GADMM converges as fast as GADMM with up to 7x less communication cost than GADMM.

PROBLEM FORMULATION
We consider a set of N workers storing their local batch of input samples. The n-th worker has its model vector θn ∈ R d , and aims to learn a global model vector θ that solves the following decentralized learning problem: subject to θn = θn+1, ∀n = 1, · · · , N − 1. (1) The constraint in (1) dictates that θn−1 = θn and θn = θn+1, ∀n, making worker n have joint constraints with only two neighbors. In our prior work [17], GADMM was proposed to solve (1) in a decentralized manner. To this end, workers are split into two groups, heads and tails, such that each worker in the head (or tail) group is communicating with two tail (or head) workers. As Fig. 1 illustrates, the primal variables, i.e., model vectors, of head workers are updated in parallel, and then downloaded by their neighboring tail workers. Likewise, the primal variables of tail workers are updated in parallel, and downloaded by their neighboring head workers. Lastly, the dual variables are updated locally at each worker. To improve communication efficiency, quantization will be introduced to GADMM in the next section.

PROPOSED ALGORITHM: Q-GADMM
In this section, we propose a stochastic quantization scheme that guarantees the convergence of Q-GADMM, and then describe the overall operational procedures of Q-GADMM. Following [5], worker n in Q-GADMM at iteration k quantizes its model vector θ k n asθ k n = Qn(θ k n ,θ k−1 n ), based on its previously quantized model vectorθ k−1 n . The function Qn(·) is a stochastic quantization operator that depends on the quantization probability p k n,i for each model vector's dimension i ∈ {1, 2, · · · , d}, and on b k n bits used for representing each model vector dimension. To ensure the convergence of Q-GADMM, p k n,i and b k Second, every θ k+1 n such that n ∈ N h minimizes (12) at iteration k + 1. Therefore Using ε k+1 n = θ k+1 n−1 −θ k+1 n−1 and λ k+1 can be re-written as Let r k+1 n−1,n = θ k+1 n−1 − θ k+1 n and r k+1 n,n+1 = θ k+1 n − θ k+1 n+1 be the primal residual of each agent n, and s k+1 n∈N h = ρ(θ k+1 n−1 −θ k n−1 )+ ρ(θ k+1 n+1 −θ k n+1 ) denote the dual residual of worker n ∈ N h at iteration k + 1.
To prove the convergence of the proposed algorithms, we first provides the upper and lower bounds on the optimality gap in Lemma 1. Then we prove the decrement of the Lyapunov function in Lemma 2 and finally present the convergence result in Theorem 1. where LB1 and UB1 are given in (20) and (21), respectively, at the bottom of this page.
Before we introduce the next lemma, we define a Lyapunov function V k = n (1/ρ) λ k n − λ * 2 2 + n∈N h [ρ θ k n−1 − θ * + ρ θ k n+1 −θ * ]. Next lemma shows that E {V k −V k+1 } is bounded above. This property is then used in Theorem 1 to prove that V k is monotonically decreasing at each iteration k of the proposed algorithm and the primal residual go to zero as k → ∞ when the quantization step size is reduced as k increases. Lemma 2 When f n (θ n ) is closed, proper, and convex, and the Lagrangian L 0 has a saddle point, then the following inequality holds true at the (k + 1)-th iteration of Q-GADMM: where H v is given in (22) at the bottom of the previous page.
Using Lemmas 1 and 2, we derive our main theorem stating the convergence and the optimality of Q-GADMM in solving (1).
Intuitively, when ∆ k n is non-increasing, the RHS of (23) is always positive. For such positive E {V k − V k+1 }, iteration k + 1 is one more step towards the optimal solution. Therefore, following the same proof of theorem 1 for GADMM [17], as k → ∞, Q-GADMM converges to the optimal solution. The detailed proofs of lemmas and the theorem are omitted due to the lack of space.

NUMERICAL RESULTS
To validate the performance of Q-GADMM and to verify its communication efficiency compared to GADMM, we conducted experiments for decentralized machine learning tasks. In particular, we evaluated the performance of Q-GADMM for decentralized linear regression using California Housing dataset [19]. We used 4000 samples for training, and we uniformly distributed them across 10 workers. To benchmark Q-GADMM, we compare it with GADMM [17], GD, and quantized GD (QGD) [5]. In GD, each worker computes its gradient locally and then sends it to a parameter server. The server updates the global model using aggregated gradient descent and broadcasts it to all workers. In QGD, each worker sends a quantized version of its local model. Therefore, in GD and QGD, each iteration involves N +1 communication rounds. On the other hand, for GADMM and QGADMM, each iteration involves N communication rounds since each worker needs to broadcast its updated model. Finally, for quantized versions of GADMM and GD, we assume that b k n = 2 for all n and k, so the number of quantization levels is 4, and it remains constant over iterations and across workers. Finally, we choose ρ = 1 for all experiments. Figure 2(a) shows the convergence speed in the objective value for the linear regression task. Clearly, Figure 2(a) verifies Theorem 1, and shows the convergence of Q-GADMM for convex loss function with the same speed as GADMM. Moreover, Figure 2(b), shows that both GADMM and Q-GADMM-2bits achieves the loss of 10 −5 with almost the same number of communication rounds (32600 for Q-GADMM-2bits vs 32560 for GADMM) which is around 50% less compared to GD and QGD-2bits. However, as shown in Figure 2(c), Q-GADMM-2bits requires significantly less number of bits as compared to GADMM (7x less number of bits). Moreover, compared to GD and QGD-2bits, Q-GADMM-2bits requires around 15x and 3x less number of transmitted bits to achieve the loss of 10 −5 . Thanks to the fast convergence inherited from GADMM, and our proposed stochastic quantization, the number of transmitted bits at every iteration are significantly reduced while ensuring unbiased and zero mean quantization error. Finally, it worth mentioning that in real scenarios, the communication cost to the parameter server is significantly higher than communicating with neighbors; hence savings in communication overhead by utilizing GADMM/Q-GADMM are more significant compared to GD/QGD.

CONCLUSIONS
This article proposed a communication-efficient decentralized ML algorithm, Q-GADMM. Compared to the original GADMM without quantization, Q-GADMM not only enjoys the same convergence rate as GADMM, but also is more communicationefficient. Numerical tests in a convex regularized linear regression task corroborate the advantages of Q-GADMM over GADMM, as well as GD and QGD.