AQUILA: COMMUNICATION EFFICIENT FEDER-
Year: 2021

Abstract:
The development and deployment of federated learning (FL) have been bottlenecked by the heavy communication overheads of high-dimensional models between the distributed client nodes and the central server. To achieve better errorcommunication tradeoffs, recent efforts have been made to either adaptively reduce the communication frequency by skipping unimportant updates, a.k.a. lazilyaggregated quantization (LAQ), or adjust the quantization bits for each communication. In this paper, we propose a unifying communication efficient framework for FL based on adaptive quantization of lazily-aggregated gradients (AQUILA), which adaptively adjusts two mutually-dependent factors, the communication frequency and the quantization level, in a synergistic way. Specifically, we start from a careful investigation on the classical LAQ scheme and formulate AQUILA as an optimization problem where the optimal quantization level per communication is selected by minimizing the gradient loss caused by updates skipping. Meanwhile, we adjust the LAQ strategy to better fit the novel quantization criterion and thus keep the communication frequency at an appropriate level. The effectiveness and convergence of the proposed AQUILA framework are theoretically verified. The experimental results demonstrate that AQUILA can reduce around 50% of overall transmitted bits compared to existing methods while achieving the same level of model accuracy in a number of non-homogeneous FL scenarios, including Non-IID data distribution and heterogeneous model architecture. The proposed AQUILA is highly adaptive and compatible to existing FL settings.

heading: 1 INTRODUCTION
text: With the deployment of ubiquitous sensing and computing devices, the Internet of things (IoT) as well as many other distributed systems have gradually grown from concept to reality, bringing dramatic convenience to people’s daily life (Du et al., 2020; Liu et al., 2020a; Hard et al., 2018). To fully utilize such distributed computing resources, distributed learning provides a promising framework that can achieve comparable performance with the traditional centralized learning scheme. However, the privacy and security of sensitive data during the updating and transmitting processes in distributed learning have been a growing concern. In this context, federated learning (FL) (McMahan et al., 2017; Yang et al., 2019) has been developed, enabling distributed devices to collaboratively learn a global model without privacy leakage by keeping private data sets isolated and masking transmitted information with secure approaches like differential privacy (Abadi et al., 2016), secret sharing techniques (Bonawitz et al., 2017) and homomorphic encryption (Liu et al., 2020b). Due to its privacy and security preserving property and great potentials in some distributed but privacysensitive fields like finance and health, FL has attracted tremendous attentions from both academia and industry in recent years.
Unfortunately, in many FL applications like image classification and objective recognition, the models to be trained tend to be high-dimensional, which lead to heavy communication overheads, for example, a Resnet-152 network has over 58 million parameters (He et al., 2016). Hence, communication efficiency has become one of the key bottlenecks of FL. To this end, recent researches have tried to reduce the communication frequency, for example, Sun et al. (2020) proposes the lazily-aggregated quantization (LAQ) method to reduce communication rounds by skipping some
unnecessary parameter uploads. To further reduce transmitted bits per communication, LAQ can be used jointly with gradient compression techniques, e.g. quantization and sparsification (Strom, 2015; Wangni et al., 2018; Lin et al., 2018; Han et al., 2020). Moreover, Mao et al. (2021) develops the Adaptive Quantized Gradient (AQG) for LAQ to adjust the quantization bit among multiple given levels during training. However, the AQG is not sufficiently adaptive, for example, in the two-level AQG with 4 bit and 2 bit, the situation of 3 bit and 1 bit is not covered at all. In a separate line of work, Jhunjhunwala et al. (2021) develops an adaptive quantization rule (AdaQuantFL) for FL which can search in a given range for an optimal quantization level and achieve a better error-communication tradeoff.
Previous work has investigated how to optimize communication frequency or adjust quantization levels in a highly adaptive fashion, but not both. Intuitively, we ask the question, can we adaptively adjust the quantization level in LAQ to further reduce communication rounds and transmitted bits simultaneously? A straightforward approach is to train LAQ jointly with state-of-the-art adaptive quantization methods like AdaQuantFL. However, quantization level and communication frequency are mutually dependent in establishing the model convergence and must be adjusted together. For example, lazy aggregation leads to the skip of some gradients that no longer require quantization, while the choice of quantization levels directly affects the quality of a gradient update and thus whether it is selected for transmission and aggregation. Therefore, the key question of our work is how to jointly leverage these two complementary yet mutually-dependent degrees of freedom for further optimizing communication efficiency in FL.
The key idea of this paper is to select the optimal quantization bits for each communication round in LAQ by optimizing the gradient loss caused by skipping quantized updates, which gives a novel quantization criterion that can cooperate with LAQ strategy to further reduce overall transmitted bits while maintaining the desired convergence properties of LAQ. The contributions of this paper are trifold and summarized as follows. 1) We propose a FL framework with adaptive quantization of lazily-aggregated gradients termed AQUILA, which simultaneously adjusts the communication frequency and quantization level in a synergistic fashion. 2) We formulate AQUILA as an optimization problem and develop an upperbound for the gradient loss caused by communication skipping, which gives a novel adaptive quantization criterion which is theoretically proven to be more efficient compared to AdaQuantFL while maintaining the same convergence properties. 3) We experimentally evaluate the performance of AQUILA in a number of non-homogeneous FL settings, including Non-IID data distribution and various heterogeneous model architecture. The experimental results show that AQUILA can significantly mitigate the communication overhead over a number of baselines including fixed-bit LAQ and the naive combination of LAQ and AdaQuantFL. Our approach is highly adaptive and compatible to existing FL settings.

heading: 2 BACKGROUND AND RELATED WORK
text: Consider a FL system with one central server and a clients set M of M distributed clients to collaboratively train a global model parameterized by θ∗. At iteration k, each client m ∈ M first trains the global model θk on its local data Dkm, and sends the local gradient g k m = ∇fm(Dkm;θ
k) to the central server. Then the server aggregates the parameters and updates the global parameter by:
θk+1 = θk − α M ∑ m∈M gkm. (1)
To reduce communication overheads with gradient quantization, the stochastic uniform quantizer (Alistarh et al., 2017) is usually adopted. For any local gradient g ∈ Rd, the quantized value of its i-th dimension with quantization level b is defined as:
Qb (gi) = ∥g∥2 · sign (gi) · ξi(g, b), (2)
where ξi(g, b) is a random variable defined as follows. Let l ∈ {0, 1, 2, ..., b−1} be an integer satisfying |gi| /∥g∥2 ∈ [ l/b, (l + 1)/b ), then:
ξi(g, b) = { (ℓ+ 1)/b with probability (b · ∥gi∥)/∥g∥2 − l ℓ/b otherwise.
(3)
It is clear that with quantization level b, the number of bits for transmitting a quantized gradient from a client to the central server is Cb = d ⌈log2(b+ 1)⌉+ d+ 32, with 32 bits for ∥g∥2, 1 bit for each sign (gi), and log2(b+ 1) bits for each ξi(g, b).
For communication rounds reduction, the LAQ proposes to let the client m ∈ M upload its newlyquantized local gradient Qb(gkm) at iteration k only when the change in local gradient is sufficiently large, i.e.,
∥∥∥Qb(gkm)−Qb(ĝk−1m )∥∥∥2 2 ≥
∑D d=1 ξd ∥∥∥θk+1−d − θk−d∥∥∥2 2
α2M2 + 3(∥εb(ĝk−1m )∥22 + ∥∥εb(gkm)∥∥22), (4) where Qb(ĝ k−1 m ) is the last quantized upload from client m, εb(ĝ k−1 m ) and εb(g k m) denote quantization errors, and {ξd}Dd=1 are some predetermined constant weights. Notice here a fixed quantization level b is used. In LAQ, if the difference between client m’s newly-quantized local gradient Qb(gkm) and the last upload is smaller than a threshold involving quantization errors and global model’s innovation, client m will skip the upload of Qb(gkm) at iteration k and the central server will reuses Qb(ĝ k−1 m ) for such lazy aggregation:
θ̂ k+1 = θk − α M ∑ m∈M Qb(ĝ k m) = θ k − α M ∑ m∈M\Mk0 Qb(g k m)− α M ∑ m∈Mk0 Qb(ĝ k−1 m ), (5)
where Mk0 denotes the subset of clients that skip the new gradient update and reuse the old quantized gradient at iteration k. Besides, ĝkm represents the actual gradient for aggregation from client m, which is gkm for m ∈ M \Mk0 , while ĝ k−1 m for m ∈ Mk0 .
Recently, AdaQuantFL is proposed to achieve a better error-communication tradeoff by adaptively adjusting the quantization levels during FL training (Jhunjhunwala et al., 2021). Specifically, AdaQuantFL computes iteration k’s optimal quantization level b∗k based on the following criterion involving training loss and initial quantization level b0:
b∗k =
√ f ( θ0 ) /f ( θk ) · b0, (6)
where f(θ0) and f(θk) are the global training loss at iteration 0 and k, respectively.
However, AdaQuantFL transmits quantized gradients at every iteration. In order to skip unnecessary communication rounds and adaptively adjust quantization level for each communication jointly, an naive approach is to quantize lazily aggregated gradients with AdaQuantFL. Nevertheless, it fails to achieve efficient communication due to a number of reasons. Firstly, given the descending trend of training loss, AdaQuantFL’s criterion (6) may lead to high quantization bit number even exceeding 32 late in the training process, which is too much for cases where the global convergence is already approaching. Secondly, higher quantization level results in smaller quantization error, which will lead to lower communication threshold in LAQ’s criterion (4) and thus higher frequency of transmission. Therefore it is desirable to develop more efficient adaptive quantization method in the lazily-aggregated setting to systematically improve communication efficiency in FL.

heading: 3 METHOD

heading: 3.1 ADAPTIVE QUANTIZATION OF LAZILY-AGGREGATED GRADIENTS (AQUILA)
text: Given the above limitations of the naive joint use of existing adaptive quantization criterion and lazy aggregation strategy, this paper aims to design a unifying framework for communication efficiency optimization where the quantization level and communication frequency are adjusted in a synergistic and interactive way. Based on a careful investigation on LAQ, we design a novel quantization criterion where the optimal quantization level is selected by minimizing the expected gradient loss caused by skipping quantized updates. The rationale behind such strategy is, by formulating the adaptive quantization problem of lazily-aggregated gradients as optimizing the expected gradient loss with respect to the number of quantization bits, we can get an adaptive quantization criterion based on local gradient updates while maintaining or even improving the convergence property of
LAQ. To get the optimization target, we first derive an upperbound for the expected gradient loss in terms of quantization bits as elaborated in Section 3.2, which gives a novel adaptive quantization criterion (7) that selects the quantization level for client m at iteration k based on initial quantization level b0 and the change between client m’s newly computed gradient gkm and the last uploaded gradient ĝk−1m :
(bkm) ∗ = b0 · √∥∥g1m − ĝ0m∥∥22/∥∥gkm − ĝk−1m ∥∥22. (7) The superiority of (7) comes from the following two aspects. Firstly, the gradient updates tend to fluctuate along with the training process instead of keeping descending like the loss value, and thus prevent the quantization level from increasing tremendously compared with the initial level. Secondly, with lazy aggregation criterion based on gradient updates like (4), the transmitted bits in AQUILA is further controlled, since the gradient update for actual transmission in (7) is lower bounded by the lazy aggregation criterion, and therefore high-bit transmission for small update is more likely to be skipped.
To better fit the larger quantization errors induced by fewer quantization bits in (7), we modify the communication criterion as follows to avoid the potential expansion of clients group to be skipped:
∥∥∥Qbkm(gkm)−Qb̂k−1m (ĝk−1m )∥∥∥22≥ ∑D d=1ξd ∥∥∥θk+1−d−θk−d∥∥∥2 2 α2M2 +2
∥∥∥εbkm(gkm)−εb̂k−1m (ĝk−1m )∥∥∥22, (8) where all the notations are the same as in (4) except the heterogeneous quantization level bkm and b̂k−1m for each client. For detailed development of (8), please refer to the Appendix.
The cooperation of the novel adaptive quantization criterion (7) and the modified lazy aggregation strategy (8) is illustrated in Fig. 1a. Compared to the naive combination of AdaQuantFL and LAQ where the mutual influence between adaptive quantization and lazy aggregation has not been considered as shown in Fig. 1b, our AQUILA framework adaptively optimizes the allocation of quantization bits throughout training to promote the convergence of lazy aggregation, and at the same time utilizes the lazy aggregation strategy to improve the efficiency of adaptive quantization by skipping high-bit transmission. The proposed AQUILA’s effect of suppressing the transmission of high quantization bits has been verified in our experiments, as shown in Fig. 20 in the Appendix. Besides, with the adjusted lazy aggregation strategy (8), AQUILA well addresses the problem of high communication frequency in the late training process of naive combination of AdaQuantFL and LAQ, as indicated by Fig. 2.
The proposed AQUILA is summarized as follows in Algorithm 1. At iteration k = 0, all clients are forced to transmit local gradients quantized with the initial level b0. At iteration k ∈ {1, 2, ...,K}, the server first broadcasts the global model θk to all clients. Each client m computes gkm with local training data, and then uses it to select an optimal quantization level by (7). Then, each client
computes its gradient update after quantization and determines whether to upload the update or not based on the communication criterion (8). Finally, the server updates the new global model θk+1 with up-to-date quantized gradients Qbkm(g k m) for those clients who send the uploads at iteration k, while reusing the old quantized gradients Qb̂k−1m (ĝ k−1 m ) for those who skip the uploads.
Algorithm 1 Communication Efficient FL with AQUILA Input: the number of communication rounds K, the learning rate α, the maximum communication
level bmax Initialize: the initial global model parameter θ0 and the initial quantization level b0.
1: Server broadcasts θ0 to all clients. 2: for each client m ∈ M in parallel do 3: Calculates local gradient g0m and sends the quantized gradient Qb0(g 0 m). 4: Set ĝ0m = g 0 m and b̂ 0 m = b0 on both sides. 5: end for 6: for k = 1, 2, ...,K do 7: Server broadcasts θk to all clients. 8: for each client m ∈ M in parallel do 9: Calculates local gradient gkm.
10: Computes the optimal local quantization level bkm by (7). 11: if bkm ≥ bmax then 12: bkm = bmax. 13: end if 14: if (8) holds for client m then 15: Client m computes and sends the quantized gradient Qbkm(g k m). 16: Set ĝkm = g k m and b̂ k m = b k m on both sides. 17: else 18: Client m sends nothing. 19: Set ĝkm = ĝ k−1 m and b̂ k m = b̂ k−1 m on both sides. 20: end if 21: end for 22: Server updates θk+1 by θk − α ∑M m=1 Qb̂km (ĝkm). 23: end for

heading: 3.2 THEORETICAL DERIVATION AND ANALYSIS OF AQUILA
text: As mentioned before, in this work we bound the expected gradient loss caused by skipping updates with respect to quantization bits. Specifically, if the communication criterion (8) holds for client m at iteration k, it does not contribute to iteration k’s gradient loss, otherwise, the loss caused by client m will be minimized with the optimal quantization criterion (7). In this section, the theoretical derivation of the target upper bound is based on following standard assumptions: Assumption 1. Loss function f(θ) = ∑
m∈M fm(θ) is L-smooth, and fm(θ) is Lm-smooth.
Assumption 2. The quantization operation is unbiased with E[Qb(w)|w] = w, and its variance satisfy: ∀w ∈ Rd,E[∥Qb(w)− w∥22 |w] ≤ qb ∥w∥ 2 2, where qb is a positive constant.
Here we adopt the definition of B in AdaQuantFL, but modified it as follows: Definition 1 (Number of Bits sent from client m to the server, Bm). The total number of bits that has been sent from client m to the central server until a given time instant is denoted by Bm. With the definition of Bm, the upper bound of the loss induced by gradient skipping is indicated by the following theorem: Theorem 1. Under Assumption 1 and 2, the expected gradient loss caused by lazy aggregation has the following upper bound:
E[ ∥∥∥θ̂k+1 − θk+1∥∥∥2
2 ] ≤ 3α
2
M ∑ m∈M
dmd ⌈ log2(4b k m) ⌉ Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2
+ 3α2
M ∑ m∈M ( dσ2 (b̂k−1m )2 + dσ2 (bkm) 2 ) + 3α2 M ∑ m∈M dm(d+ 32) Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2 ,
(9)
where σ2 denotes the maximum ∥w∥22, and dm is a positive constant determined by Lm. See the Appendix for proof details.
For each client m, the optimal bkm is selected by setting the first derivative of the upper bound (9) to zero:
(bkm) ∗ = √( 2σ2Bmloge(2) ) / ( dm ∥∥∥gkm − ĝk−1m ∥∥∥2 2 ) . (10)
Therefore, an adaptive quantization criterion which does not rely on unknown parameters such as σ and dm can be achieved through dividing bkm by b 1 m, which gives the adaptive selection criterion in (7) if b1m for each client m is chosen as the initial quantization level b0.
Comparison with AdaQuantFL. In AdaQuantFL, the optimal quantization level is selected by minimizing the upper bound of the expected squared norm of the gradient ∇f(θk) of a non-convex objective function, and thus the convergence of AdaQuantFL is guaranteed. However, the proposed AQUILA is proven to be more efficient with sufficiently small learning rates as shown in Theorem 2. Besides, it is theoretically guaranteed that the squared norm of the global gradient ∇f(θk) is also able to converge under AQUILA’ s adaptive quantization criterion developed for lazy aggregation.
Theorem 2. Under Assumption 1 and 2, if the learning rate α satisfies α ≤ (1/ML) · √ 2Pξ/L, the following inequality holds:
(bkm) ∗ = b0 √√√√√ ∥∥g1m − ĝ0m∥∥22∥∥∥gkm − ĝk−1m ∥∥∥2 2 ≤ b0 √√√√α2M2L3 ∥∥θ1 − θ0∥∥22 2ξ[f(θk)− f(θ∗)] ≤ b0 √ f(θ0)− f(θ∗) f(θk)− f(θ∗) , (11)
where ξ and P are both positive constants. See the Appendix for proof details.
Theorem 2 indicates that with appropriate learning rate, the proposed AQUILA uses less number of bits per communication compared to AdaQuantFL.
Convergence analysis. The Lyapunov function of AQUILA is defined in the same way as LAQ and AQG (Mao et al., 2021):
V(θk) = f(θk)− f(θ∗) + D∑
d=1 D∑ j=d ξj α ∥∥∥θk+1−d − θk−d∥∥∥2 2 , (12)
where θ∗ is the optimal solution of minθf(θ).
Convergence guarantee of federated learning with lazy aggregation has been well discussed in Sun et al. (2020). More specifically, both the objective residual f(θk) − f(θ∗) and the parameter differences term in Lyapunov function are guaranteed to descend along with the training process. Therefore, the squared norm of the gradient ∇f(θk) is also guaranteed to converge based on the L-smoothness assumption which results in: ∥∇f(θk)∥22 ≤ 2L[f(θ k)− f(θ∗)].

heading: 4 EXPERIMENTS AND DISCUSSION

heading: 4.1 EXPERIMENT SETUP
text: Dataset. In this paper, we evaluate our method with MNIST and CIFAR10 dataset, considering both IID and Non-IID data distribution. To simulate Non-IID situation, each client is assigned with two classes of data at most and the amount of data for each class is balanced.
Parameters. We set total client number M = 10, and follow the settings in LAQ, where D = 10 and ξ1 = ξ2 = · · · = ξD = 0.8/D. In terms of initial quantization level, a low level b0 = 2 is chosen for simpler tasks with MNIST, and a larger level b0 = 6 is selected for more complex tasks with CIFAR10. For both AdaQuantFL and AQUILA, we set an upperbound for quantization level as bmax = 16 in case that the level grows too high.
Training. We train a CNN with MNIST and a Resnet18 network with CIFAR10. The hyperparameters of our experiments are shown in Table 1 in Appendix.
We first evaluate our proposed AQUILA with homogeneous settings where all the local models share the same architecture as the global model. The performance of AQUILA is compared with several state-of-the-art methods including FedAvg (McMahan et al., 2017), QSGD (Alistarh et al., 2017), AdaQuantFL, fixed-bit LAQ and the naive combination of AdaQuantFL with LAQ. For the choice of quantization level for fixed-bit LAQ, since AQUILA’s initial level b0 is 2 for MNIST and 6 for CIFAR10, we compare AQUILA with LAQ-2 and LAQ-6 for MNIST and CIFAR 10 respectively. Besides, the performance of LAQ with the upperbound bmax = 16 is also evaluated.
We also evaluate our proposed AQUILA with HeteroFL (Diao et al., 2020), where the local models trained at clients’ side are heterogeneous. Assume the global model at iteration k is θkg and its size is dg · hg , then the local model of each client m can be selected by θkm = θkg [: dm, : hm], where dm = rmdg and hm = rmhg respectively. In this paper, we choose three various model complexity levels r = {a, b, c} = {1, 0.5, 0.25}. Fig. 3 shows the training loss vs total transmitted bits curve of experiments with IID MNIST / CIFAR10 for homogeneous model architecture, IID MNIST / CIFAR10 for 100%-50% heterogeneous model architecture, and Non-IID MNIST / CIFAR10 for 100%-25% heterogeneous model architecture. The corresponding transmitted bits vs steps curves of the above experiment settings are shown in Fig. 4, which represents how many bits are transmitted in each step. Methods without adaptive quantization and lazy aggregation like FedAvg and QSGD are not included in Fig. 4 for simplicity. All the other experiment results are provided in Appendix, with Fig. 5 to Fig. 9 for homogeneous models, and Fig. 10 to Fig. 19 for heterogeneous models.

heading: 4.2 PERFORMANCE ANALYSIS
text: In this part, we analyze the performance of AQUILA with various experiment settings including Non-IID data distribution and heterogeneous model architecture. From figures in this paper, we can observe that:
• AQUILA achieves a significant transmission reduction on both MNIST and CIFAR10 as compared to AdaQuantFL and the naive combination of LAQ and AdaQuantFL. For instance, AQUILA saves 65.98% of transmitted bits compared with AdaQuantFL and 62.05% compared with the naive combination of LAQ and AdaQuantFL in the IID scenario with CIFAR10 dataset as shown in Fig. 3d, and other figures all show an obvious reduction in terms of the total transmitted bits required for convergence. Fig. 4 verifies that the quantization level selected by AQUILA will not continuously increase during training like AdaQuantFL and LAQ with AdaQuantFL.
• Similarly, AQUILA outperforms all fixed-level LAQ in terms of overall transmitted bits for both MNIST and CIFAR10, as shown in Fig. 3. For example, Fig. 3a indicates that AQUILA reduces 42.6% of total transmitted bits compared with LAQ-2 and 92.32% compared with LAQ-16 in MNIST. The transmission reduction is 38.76% for LAQ-6 and 78.09% for LAQ-16 in CIFAR10 as shown in Fig. 3e. Besides, Fig. 3 and Fig. 4 indicate that although LAQ with fixed but low quantization level like LAQ-2 and LAQ-4 sometimes transmit smaller amount of bits per step compared with AQUILA, they suffer from lower accuracy and slower convergence. It further verifies the necessity and effectiveness of our well-designed adaptive quantization criterion which achieves fast convergence with similar low-bit transmission but without degradation of the model performance.
• AQUILA also works well with heterogeneous local models. With the two various ways of distributing the heterogeneous local models in this paper, our proposed AQUILA still outperforms other methods by significantly reducing overall transmitted bits while maintaining the same convergence property and model accuracy. Please refer to Fig. 10 to Fig. 19 in the Appendix for more detailed information. These experimental results in nonhomogeneous FL settings prove that our proposed AQUILA can be used in a more general and complicated federated learning scenarios.

heading: 5 CONCLUSIONS AND FUTURE WORK
text: This paper proposes a communication efficient FL framework to simultaneously adjust two mutually-dependent degrees of freedom: communication frequency and quantization level. With the close cooperation of the novel adaptive quantization and adjusted lazy aggregation strategy developed in this paper, the proposed AQUILA has been proven to be capable of reducing the transmitted bits while maintaining the same convergence property and model performance compared against existing methods both theoretically and experimentally. The evaluation with Non-IID data distribution and various heterogeneous model architectures demonstrates that AQUILA is compatible to existing FL settings. Future works include further improvements and theoretical guarantee for FL systems with heterogeneity.

heading: A APPENDIX

heading: A.1 SUPPLEMENTARY EXPERIMENTAL RESULTS
text: The appendix includes supplementary experimental results, mathematical proof of Theorem 1 and Theorem 2, and detailed derivation of the novel adaptive quantization criterion and lazy aggregation strategy. Compared to Fig. 3 and Fig. 4 in the main text, result figures in appendix show a more comprehensive evaluation with AQUILA, which contain more detailed information including but not limited to accuracy vs steps and training loss vs steps curves.

heading: A.2 MATHEMATICAL PROOF

heading: A.2.1 PROOF OF THEOREM 1
text: Without lazy aggregation, the aggregated model at iteration k should be:
θk+1 = θk − α M ∑ m∈M Qbkm(g k m). (13)
With lazy aggregation, the actual aggregated model at iteration k is:
θ̂ k+1 = θk − α M ∑ m∈M\Mk0 Qbkm(g k m)− α M ∑ m∈Mk0 Qb̂k−1m (ĝ k−1 m ). (14)
With (13) and (14), the gradient loss caused by skipping can be written as:∥∥∥θ̂k+1 − θk+1∥∥∥2 2 = ∥∥∥∥∥∥ αM ∑
m∈Mk0
Qbkm(g k m)−Qb̂k−1m (ĝ k−1 m ) ∥∥∥∥∥∥ 2
2
≤ α 2M
M2 ∑ m∈M ∥∥∥Qbkm(gkm)−Qb̂k−1m (ĝk−1m )∥∥∥22 = α2
M ∑ m∈M ∥∥∥[Qbkm(gkm)− gkm]− [Qb̂k−1m (ĝk−1m )− (ĝk−1m )] + (gkm − ĝk−1m )∥∥∥22 ≤ 3α 2
M ∑ m∈M ∥∥∥gkm − ĝk−1m ∥∥∥2 2 + 3α2 M ∑ m∈M ( ∥∥εbkm(gkm)∥∥22 + ∥∥∥εb̂k−1m (ĝk−1m )∥∥∥22), (15)
where the two inequalities follow from: ∥∥∥∥∥ n∑
i=1
ai ∥∥∥∥∥ 2
2
≤ n n∑
i=1
∥ai∥22.
Take expectation of both sides of (15):
E[ ∥∥∥θ̂k+1 − θk+1∥∥∥2
2 ] ≤ 3α
2
M ∑ m∈M E[ ∥∥∥gkm − ĝk−1m ∥∥∥2 2 ] + 3α2 M ∑ m∈M (E[ ∥∥εbkm(gkm)∥∥22] + E[∥∥∥εb̂k−1m (ĝk−1m )∥∥∥22)]
≤ 3α 2
M ∑ m∈M E[ ∥∥∥gkm − ĝk−1m ∥∥∥2 2 ] + 3α2 M ∑ m∈M ( dσ2 (b̂k−1m )2 + dσ2 (bkm) 2 )
≤ 3α 2
M ∑ m∈M dm K ∥∥∥gkm − ĝk−1m ∥∥∥2 2 + 3α2 M ∑ m∈M ( dσ2 (b̂k−1m )2 + dσ2 (bkm) 2 ), (16)
where the second inequality follows from Assumption 2 with σ2 denoting the maximum ∥w∥22 and qb = d/b
2, and the last inequality is resulted from the conclusion in LAQ (Sun et al., 2020), which indicates that the client m communicates with the server at most dm rounds in total K iterations, where dm is a constant related to Lm.
With the definition of Bm and Ckm = d ⌈ log2(b k m + 1) ⌉ + d+ 32, the expected gradient loss can be written as:
E[ ∥∥∥θ̂k+1 − θk+1∥∥∥2
2 ] ≤ 3α
2
M ∑ m∈M dmC k m Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2 + 3α2 M ∑ m∈M ( dσ2 (b̂k−1m )2 + dσ2 (bkm) 2 )
= 3α2
M ∑ m∈M
dmd ⌈ log2(b k m + 1) ⌉ Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2 + 3α2 M ∑ m∈M ( dσ2 (b̂k−1m )2 + dσ2 (bkm) 2 )
+ 3α2
M ∑ m∈M dm(d+ 32) Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2
≤ 3α 2
M ∑ m∈M
dmd ⌈ log2(4b k m) ⌉ Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2 + 3α2 M ∑ m∈M ( dσ2 (b̂k−1m )2 + dσ2 (bkm) 2 )
+ 3α2
M ∑ m∈M dm(d+ 32) Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2 . (17)
This completes the proof for Theorem 1.

heading: A.2.2 DERIVATION DETAILS OF ADAPTIVE QUANTIZATION CRITERION (7)
text: Let H be the upper bound to be minimized:
H = 3α2
M ∑ m∈M
dmd ⌈ log2(4b k m) ⌉ Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2 + 3α2 M ∑ m∈M ( dσ2 (b̂k−1m )2 + dσ2 (bkm) 2 )
+ 3α2
M ∑ m∈M dm(d+ 32) Bm ∥∥∥gkm − ĝk−1m ∥∥∥2 2 . (18)
The first derivative is:
∂H ∂bkm =
3α2did ∥∥∥gkm − ĝk−1m ∥∥∥2
2 ⌈log2 e⌉
BmMbkm − 6α
2dσ2
M(bkm) 3 . (19)
Let ∂H
∂bkm = 0, there is:
(bkm) ∗ = √√√√ 2σ2Bmloge(2) di ∥∥∥gkm − ĝk−1m ∥∥∥2 2 . (20)
Dividing (bkm) ∗ by (b1m):
(bkm) ∗ = b1m √√√√√ ∥∥g1m − ĝ0m∥∥22∥∥∥gkm − ĝk−1m ∥∥∥2 2 . (21)
For iteration k = 1, we set b1m for each client m as the intial quantization level b0, and thus we get the adaptive quantization criterion (7) for iteration k = 1, 2, ...,K:
(bkm) ∗ = b0 √√√√√ ∥∥g1m − ĝ0m∥∥22∥∥∥gkm − ĝk−1m ∥∥∥2 2 . (22)

heading: A.2.3 PROOF OF THEOREM 2
text: With the adjusted communication criterion (8), all transmitted gradient updates are larger than a threshold after quantization. Therefore, all transmitted gradient updates satisfy:
∥∥∥gkm − ĝk−1m ∥∥∥2 2 = ∥∥∥gkm −Qbkm (gkm)+Qb̂k−1m (ĝk−1m )− ĝk−1m +Qbkm (gkm)−Qb̂k−1m (ĝk−1m )∥∥∥22 ≈
∥∥∥Qbkm (gkm)−Qb̂k−1m (ĝk−1m )∥∥∥22 ≥ ∑D d=1 ξd ∥∥∥θk+1−d−θk−d∥∥∥2 2
α2M2 +3 (∥∥εbkm(gkm)∥∥22+∥∥∥εb̂k−1m (ĝk−1m )∥∥∥22 ) . (23)
then,
(bkm) ∗ = b0 √√√√√ ∥∥g1m − ĝ0m∥∥22∥∥∥gkm − ĝk−1m ∥∥∥2 2
≤ b0 √√√√√√ ∥∥g1m − ĝ0m∥∥22
1 α2M2 ∑D d=1 ξd ∥∥∥θk+1−d − θk−d∥∥∥2 2 + 3 (∥∥εbkm(gkm)∥∥22 + ∥∥∥εb̂k−1m (ĝk−1m )∥∥∥22 )
≤ b0 √√√√√√ ∥∥g1m − ĝ0m∥∥22
2 α2M2L ∑D d=1 ξd(f(θ k+1−d)− f(θk−d)) + 3 (∥∥εbkm(gkm)∥∥22 + ∥∥∥εb̂k−1m (ĝk−1m )∥∥∥22 )
≤ b0 √√√√√√ ∥∥g1m − ĝ0m∥∥22
2ξd α2M2L [f(θ k)− f(θk−D)] + 3 (∥∥εbkm(gkm)∥∥22 + ∥∥∥εb̂k−1m (ĝk−1m )∥∥∥22 )
≤ b0 √√√√ ∥∥g1m − ĝ0m∥∥22 2ξd
α2M2L [f(θ k)− f(θ∗)]
≤ b0 √√√√ (Lm)2 ∥∥θ1 − θ0∥∥22 2ξd
α2M2L [f(θ k)− f(θ∗)]
, (24)
where the second inequality comes from Assumption 1. Let P = f(θ0)− f(θ∗) L ∥∥θ1 − θ0∥∥2
2
. Therefore, if
α ≤ (1/ML) √ 2Pξ/L holds, then in the experiment setting where ξ1 = ξ2 = ... = ξD = ξ and L ≈ Lm for all m ∈ M, there is:
(bkm) ∗ ≤ b0 √√√√ (Lm)2 ∥∥θ1 − θ0∥∥22 2ξd
α2M2L [f(θ k)− f(θ∗)]
≤ b0 √ f(θ0)− f(θ∗) f(θk)− f(θ∗) . (25)

heading: A.2.4 DEVELOPMENT OF LAZY AGGREGATION CRITERION (8)
text: ∥∥∥Qbkm (gkm)−Qb̂k−1m (ĝk−1m )∥∥∥22 =
∥∥∥Qbkm (gkm)− gkm −Qb̂k−1m (ĝk−1m )+ ĝk−1m + gkm − ĝk−1m ∥∥∥22 ≤ 2 ∥∥∥gkm − ĝk−1m ∥∥∥2 2 + 2
∥∥∥εbkm(gkm)− εb̂k−1m (ĝk−1m )∥∥∥22 ≤ 2L2m ∥∥∥θk − θk−d′∥∥∥2 2 + 2
∥∥∥εbkm(gkm)− εb̂k−1m (ĝk−1m )∥∥∥22 = 2L2m ∥∥∥∥∥∥ d′∑
d=1
θk+1−d − θk−d ∥∥∥∥∥∥ 2
2
+ 2 ∥∥∥εbkm(gkm)− εb̂k−1m (ĝk−1m )∥∥∥22
≤ 2L2md′ d′∑
d=1
∥∥∥θk+1−d − θk−d∥∥∥2 2 + 2 ∥∥∥εbkm(gkm)− εb̂k−1m (ĝk−1m )∥∥∥22 , (26) where the second inequality comes from:
ĝk−1m = ∇fm(θ k−d′). (27) gkm = ∇fm(θ k). (28)∥∥∥∇fm(θk)−∇fm(θk−d′)∥∥∥2
2 ≤ L2m ∥∥∥θk − θk−d′∥∥∥2 2 . (29)
Following LAQ’s definition, redefine dm,m ∈ M as:
dm := max d
{ d|L2m ≤ ξd/(2α2M2D), d ∈ 1, 2, ..., D } . (30)
With the definition of dm and ξ1 ≥ ξ2 ≥ ... ≥ ξD, there is:
L2m ≤ ξd′
2α2M2D , for all d′ satisfying1 ≤ d′ ≤ dm. (31)
With (26) and (31), we have:
∥∥∥Qbkm (gkm)−Qb̂k−1m (ĝk−1m )∥∥∥22 ≤ 1
α2M2 d′∑ d=1 ξd′ ∥∥∥θk+1−d − θk−d∥∥∥2 2 + 2 ∥∥∥εbkm(gkm)− εb̂k−1m (ĝk−1m )∥∥∥22 ≤ 1
α2M2 D∑ d=1 ξd ∥∥∥θk+1−d − θk−d∥∥∥2 2 + 2 ∥∥∥εbkm(gkm)− εb̂k−1m (ĝk−1m )∥∥∥22 . (32)

Review summaries:
The paper proposes combining two orthogonal algorithms -- the lazily aggregated gradient(LAQ)method and adaptive quantization (AdaQuantFL)-- to reduce communication complexity in federated learning. In particular, while LAQ focuses on the frequency of gradient updates in each iteration, AdaQuantFL focuses on the adaptive allocation of bits across iterations. This paper proposes to combine both of these approaches for better communication complexity in federated learning.   At the heart of the combining strategy is Eq. 7, which allocates the bits used in each iteration. This equation is intern based on minimizing the upper bound on the expected deviation in the path of the iterate due to gradient skipping. The authors theoretically show that such a bit allocation strategy leads to reduced communication compared to the bit allocation strategy of AdaQuantFl.