AQUILA: Communication Efficient Federated Learning with Adaptive Quantization of Lazily-Aggregated Gradients
Authors: Zihao Zhao
Yuzhu Mao
Zhenpeng Shi
Muhammad Zeeshan
Yang Liu
Tian Lan
Wenbo Ding
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
communication efficiency
adaptive quantization

Abstract: The development and deployment of federated learning (FL) have been bottlenecked by the heavy communication overheads of high-dimensional models between the distributed device nodes and the central server. To achieve better error-communication trade-offs, recent efforts have been made to either adaptively reduce the communication frequency by skipping unimportant updates, a.k.a. lazily-aggregated 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 of the classical LAQ scheme and formulate AQUILA as an optimization problem where the optimal quantization level per communication is selected by minimizing the model deviation caused by update skipping. Meanwhile, we create a new lazy aggregation strategy to fit the novel quantization criterion better 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 60% 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 with existing FL settings.

Under review as a conference paper at ICLR 2023
AQUILA: COMMUNICATION EFFICIENT FEDERATED LEARNING WITH ADAPTIVE QUANTIZATION OF LAZILY- AGGREGATED GRADIENTS
Anonymous authors Paper under double-bling review
ABSTRACT
The development and deployment of federated learning (FL) have been bottle- necked by heavy communication overheads high-dimensional models between the distributed device nodes and the central server. To achieve better communication trade-offs, recent efforts have been made to either adaptively reduce the communication frequency by skipping unimportant updates, e.g., lazy aggregation, or adjust the quantization bits for each communication. In this pa- per, we propose unifying communication efficient framework for FI. based adaptive quantization of aazil-aggrreaaee gradients (AQUILA), which adaptively balances two nutually-dependent factors, the communication frequency, and the quantization level. Specifically, we start with a careful investigation of the classi- cal lazy aggregation scheme and formulate AQUILA as an optimization problem where the optimal quantization level is selected by minimizing the model deviation caused by update skipping. Furthermore, we devise a new lazy aggregation strategy to better fit the novel quantization criterion and retain the communication fre- quency at an appropriate level. The effectiveness and convergence of the proposed AQUILA framework are theoretically verified. The experimental results demon- strate that AQUILA can reduce around 60% of overall transmitted bits compared existing methods while achieving identical model performance in number of non-homogeneous FL scenarios, including Non-IID data and heterogeneous model architecture.
INTRODUCTION
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 s daily life (Du et al. 2020 Liu et al.) 2020 Hard et al.) 2018). To fully utilize such distributed computing resources, distributed learning provides 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 transmission processes in distributed learning have been a growing concern. In this context, fentext,federated federated learning (FL) (McMahan et al., (017)) has been developed, allowing distributed devices collaboratively learn global model without privacy leakage by keeping private data isolated and masking transmitted information with secure approaches. On account its privacy-preserve but
property and great potentiality in some distributed fields such as finance and health, FL has attracted tremendous attention from both academia and industry in recent years.
Unfortunately, in many FL applications, such as image classification and objective recognition, the trained model tends be digh-dimensional, resulting in significant communication costs. Hence, communication efficiency has become one of the key bottlenecks of FL. To this end. [Sun et al. (2020) proposes the lazily-aggregated quantization (LAQ) method to skip unnecessary parameter uploads by estimating the value of gradient innovation the difference between the current unquantized gradient and the previously quantized gradient. Moreover, Mao et al. (202I) devises an adaptive quantized gradient (AQG) strategy based LAQ to dynamically select the quantization level within some artificially given numbers during the training process. Nevertheless, the AQG is still not sufficiently adaptive because the pre-determined quantization levels are difficult to choose in complicated FL.

---

Under review as a conference paper at ICLR 2023
environments. In another separate line of work, whwnjhuuwaall al. (2021) introduces an adaptive quantization rule for FL (AdaQuantFL), which searches in given range for an optimal quantization level and achieves better cnorrcommmniiatton trade-off.
work,
Most previous research has investigated optimizing communication frequency or adjusting the quantization level in highly adaptive manner, but not both. Intuitively, ask a question, adaptively adjust the quantization level in the lazy aggregation fashion to simultaneously reduce transmitted amounts and communication frequency? In the paper, intend select the optimal quantization level for every participated device by optimizing the model deviation caused by skipping quantized gradient updates (i.e., lazy aggregation), which gives us novel quantization criterion cooperated with a new proposed lazy aggregation strategy to reduce overall communication costs further while still offering convergence guarantee. The contributions of this paper are trifold.
We propose innovative FL procedure with adaptive quantization of lazily aggregated gradients termed AQUILA, which simultancously adjusts the communication frequency and quantization level in synergistic fashion.
Instead of naively combining LAQ and AdaQuantFI., AQUILA owns completely different device selection method and quantitative level calculation method. Specifically, we derive adaptive quantization strategy from new perspective that minimizes the model deviation introduced by lazy aggregation. Subsequently, we present a new lazy aggregation criterion that is more precise and saves more device storage. Furthermore, provide a convergence analysis of AQUILA under the generally non-convex case and the condition.
Except for normal FL settings, such as independent and identically distributed (IID) data environment, we experimentally evaluate the performance of AQUILA a number of non-homogeneons FL settings, such as non-independent and non-identically distributed (Non-IID) local dataset and various heterogeneous model aggregations. The evaluation results reveal that AQUILA considerably mitigates the communication overhead compared to a variety of state-of-art a
BACKGROUND AND RELATED WORK
Consider an FL system with one central parameter server and a device set . with = | distributed devices to collaboratively train global model parameterized by 0 Rd. Each device
m M has a private local dataset D,,, = (ax (m) ()("))
(()) ( ..... (m)) (mm)) } of n.m samples. The
federated training process is typically performed by solving the following optimization problem
M
min f(0) BER
Σ (0) M m==1
with fm ( = 81l
(1)
where / Rdd - TR denotes the empirical risk, S. Rd - R denotes the local objective based on the private data Dm, the device m, denotes the local loss function, and he denotes the local model. The FL training process is conducted by iteratively performing local updates and global aggregation as proposed in (McMahan et al.) 2017). First, at communication round k. each device m receives the global model 8x from the parameter server and trains with its local data Dm- Subsequently, sends the local gradient V fm (0") to the central server, and the server will update the global model with learning rate a by
g++1 = 0
Σ fm
(2)
M
MEM
Definition 2.1 (Quantized gradient innovation). For more efficiency, each device only uploads the quantized deflection between the full gradient V fm and the last quantization value q utilizing quantization operator Q R IRd, i.e.
A Q(V fm (0")
- -
For communication frequency reduction, the lazy aggregation strategy allows the device m E . to upload its ewwly-quantized gradient innovation epoch lt only when the change in local gradient is
2

---

Under review as a conference paper at ICLR 2023
sufficiently larger than threshold. Hence, the quantization of the local gradient q of device epoch & can be calculated by
Q (0t) dtn ">1
mm
Threshold
4m
4m
1-11
Aqm.
otherwise
If the device m skips the upload of A the central server will reuse the last gradient gh aggregation. Therefore, the global aggregation rule can be changed from to:
for
0 = M
Σ MEM
4m
0
a
Σ MEML
(4m
+ Aq
Σ MEM
Im
(5)
M
where M denotes the subset devices that upload their quantized gradient innovation, and M MM \\  M denotes the subset of devices that skip the gradient update and reuse the old quantized gradient at epoch k.
For AdaQuantFL, it is proposed to achieve better commumicatiinn trade-off by adaptively adjusting the quantization levels during the FL training process. Specifically, AdaQuantFL, computes
the optimal quantization level (b*)* by (b²)* LV f(0))/ boJ. where f(0") and f(0") are
the global objective loss defined in T
However, AdaQuantFL transmits quantized gradients at every communication round. In order to skip unnccessary communication rounds and adaptively adjust the quantization level for each communication jointly, a naive approach is to quantize lazily aggregated gradients with AdaQuantFL.. Nevertheless, it fails achieve efficient communication for several reasons. First, given the descend- ing trend of training loss, AdaQuantFL's criterion may lead to high quantization bit number even exceeding 32 bits in the training process (assuming floating point represented by 32 bits in our case), which is too large for cases where the global convergence is already approaching and makes the quantization meaningless. Second, a higher quantization level results smaller quantization error, leading to a lower communication threshold in the lazy aggregation criterion (4) and thus higher transmission frequency.
Consequently, it is desirable to develop a more efficient adaptive quantization method in the lazily- aggregated setting to improve communication efficiency in FL systematically.
ADAPTIVE QUANTIZATION OF LAGILY-AGGRGGATE) GRADIENTS
Given the above limitations of the naive joint use of the existing adaptive quantization criterion and lazy aggregation strategy, this paper aims to design unifying procedure for communication efficiency optimization where the quantization level and communication frequency considered synergistically and interactively.
3.1 OPTIMAL QUANTIZATION LEVEL.
First, we introduce the definition of a deterministic rounding quantizer and augly-aggre model. Definition 3.1. (Deterministic mid-tread quantizer.) Every element of the gradient innovation of device m at epoch mapped to an integer [w as
fm (00)
# 11 +
R
1
Vi E 21,
(6)
2 Rk
2
where ( denotes the current unquantized gradient, R || (0*) - 11x denotes
the quantization range, byt denotes the quantization level, and - = 1/(2t - 1) denotes the quantization granularity. More explanations this quantizer are exhibited on Appendix A.2
Definition 3.2 (Fully-aggregated model). The fully-aggregated model θ without lazy aggregation epoch le is computed by
0 g
Σ MEA
(gth + Ag
3

---

Under review as a conference paper at ICLR 2023
Lemma 3.1. The inftuence of lazy aggregation communication round is can be bounded by
Ma M
Σ
(()V -t)
R l12) +4(R ( )² d) 2
(8)
mEM
Corresponding to Lemma 1.1, since R is independent of Th we can formulate an optimization problem minimize the upper bound this model deviation caused by update skipping for each device m:
minimize 0< 11
| R. 111))
1
subject to mm
(2% - 1)
Solving the below optimization problem gives AQUILA an adaptive strategy 10 that selects the optimal quantization level based on the quantization range R the dimension d' of the local model, the current gradient fm (O"), and the last uploaded quantized gradient gm
R Vd
(bth))=
loga
(10)
J (0*)
qm
The superiority of 10)) comes from the following three aspects. First, since R [g-- > -R the optimal quantization level (b%, must be greater than or equal to 1. Second, AQUILA can personalize an optimal quantization level for each device corresponding its own gra- dient, whereas. in AdaQuantFL, each device merely utilizes an identical quantization level according the global loss. Third, the gradient innovation and quantization range R tend fluctuate along with the training process instead of keeping descending, and thus prevent the quantization level from increasing tremendously compared with AdaQuantFI..
[m*)))))
3.2 PRECISE I.AZY AGGREGATION CRITERION
Definition 3.3 (Quantization error). The global quantization error e is defined by the subtraction between the current unquantized gradient V (((0)) and its quantized value g² + Aq iee
ch = -f(e)) 9" Aq"
(11)
where - fm gh - EmEMM g -
T A
To better fit the larger quantization errors induced by fewer quantization bits [O). AQUILA possesses a new communication criterion to avoid the potential expansion of the devices group being skipped:
A 1|
||
B a
g
0h-1l12
vm M
(12)
where 3 > O is tuning factor. Note that this skipping rule is employed at epoch k. in which each device m calculates its quantized gradient innovation Áqt, and quantization error e then utilizes this rule to decide whether uploads E
The comparison of AQUILA's skip rule and LAQ's 's is also shown Appendix A.2 Instead storing large number of previous model parameters as LAQ, the strength of (12) is that AQUILA directly utilizes the global model for two adjacent rounds as the skip condition, which does not need to estimate the global gradient (more precise), requires fewer hyperparameters to adjust, and considerably reduces the storage pressure of local devices. This especially important for small-capacity devices (e.g.. sensors) in practical IoT scenarios.
4

---

Under review as a conference paper at ICLR 2023
Algorithm I Communication Efficient FL with AQUILA
Input: the number of communication rounds K, the learning rate Initialize: the initial global model parameter 0"
1: Server broadcasts 0 to all devices.
D For the initial round i: 0.
2: for each device m . in parallel do
3: Calculates local gradient Sm (0%).
4: Compute (6 by setting qm O in 100 and the quantized gradient innovation Ag
and transmits it back to the server side.
5: end for
6: for == 1,
...... do
7: Server broadcasts 6² to all devices.
8: for each device E M in parallel do
Calculates local gradient Vmm(0") (0"), the optimal local quantization level (6%h by (10). and the quantized gradient innovation Aqm. if (I2) does not hold for device m then
9:
satisfies, skip uploading.
11:
device m transmits Aq to the server. end end for
12:
13:
14:
Server updates g by the saving previous global quantized gradient q 11 and the received quantized gradient innovation Agt. g == 8 a (9* x-1 + 1/M Emems Aq.))
15:
Server saves the average quantized gradient qb for the next aggregation. end for
The detailed process of AQUILA is comprehensively summarized in Algorithm T each device calculates 60, by setting 4 k-1 0 and uploads Ago to the server since the (2) is
At epoch k = 0,
not satisfied. At epoch E {1, K}. the server first broadcasts the global model e* to all
devices. Each device computes vf(e".) with local training data and then utilizes it to calculate an optimal quantization level by (10). Subsequently, each device computes its gradient innovation after quantization and determines whether
upload based the communication criterion 12) Finally, the server updates the new global model g*+1 with up-to-date quantized gradients + Agu for those devices who transmit the uploads at epoch k, while reusing the old quantized
gradients 4m 1-1 for those who skip the uploads.
THEORETICAL DERIVATION AND ANALYSIS OF AQUILA
As aforementioned, bound the model deviation caused by skipping updates with respect to quantization bits. Specifically, if the communication criterion (12) holds for the device m at epoch k, it does not contribute to epoch k's gradient. Otherwise, the loss caused by device will be minimized with the optimal quantization level selection criterion (10). In this section, the theoretical convergence derivation of AQUILA based on the following standard assumptions.
Assumption 4.1 (L-smoothness)) Each local objective function fm is Lm--smoti i.e., there exist constant Lm 0, such that Vx, y Rd
fm fym(y))l Lm ||x yl12.
(13)
which implies that the global objective function is L-smooth with == E
1m Lm.
Assumption 4.2 (Uniform lower bound). For all a Rd, there exist f such that f(x) f Lemma 4.1. Following the assumption that the function is L-smwoth, we have
((0t+1)- < a V
E Ag MEM!
+ c
+
L
g
- 0b/12
2
2a
(14)
5

---

Under review as a conference paper at ICLR 2023
4.1 CONVERGENCE ANALYSIS FOR GENERALLY NON-CONVEX CASE.
Theorem 4.1. Suppose Assumptions 4.1, 4.2, and B.I objective function f satisfies
29 be satisfied. If M + 2. the global
((0)+t)- a
1| ( L 1
g ghi
||=
By
0+
0
(15)
2a
Corollary 4.1. Let all the assumptions of Theorem 4.1 hold and requires
L
1 +
8r < 0, then the AQUILA
2
2a
2w1 K == =00
(16)
aE
communication rounds with W1 ( (0*)
8y |0
0 to achieve ming |V < e.
Compared to LAG. Corresponding to (70 Chen et al. (018). LAG defines Lyapunov
function Vk == f(0") - f(0") E 0 8 = and claims that it satisfies
pk+1 - v _5 (a, Bi) (1 p)a²) ||/
||
(17)
where E(a, L/2 1/a2)) + 31, B1 DE D2/(2am)) 1/D, and p 0. The above result indicates that LAG requires
2w
KLAG 0
(18)
(a 28 (a, 31) + p)a
communication rounds to converge. Since the non-negativity of the term ë (a. B1) (1 + p)aa, we can readily derive that a < a - 27 (a, 31) (1 p)a², which demonstrates AQUILA achieves better convergence rate than LAG with the appropriate selection of a.
4.2 CONVERGENCE ANALYSIS UNDER POLYAK-LOIASIEWICC CONDITION.
Assumption 4.3 (f-PE, condition). Function f satisfies the PL condition with a constant ps > 0, that
( 12 22(f((+)-5(0))
(19)
Theorem 4.2. Suppose Assumptions 4.1, 4.2, and 4.3 be satisfied and M + Ø. if the hyperparame- ters satisfy dn < - (1-opu) 2a - 4), then the global objective function satisfies
(
L
By
2
g
8h
0²
8
(20)
2a
2
2
and the AQUILA requires
K=0 (-
(-Tog(] log(1 oxp)
log W1
(21)
communication round with w1 f(0)) f(0") + (2 ( ||0
801 to achieve f ((K+1)
((0))+(( k] l 11 <
Compared to LAG. According to (50) in Chen et al. 2018 we have that
vk <(1 (1-ap au + apv DE)
(22)
where & < <1/D. Thus, we have that LAG requires
KLAG - (- log(1 au + ap DE
W1
log
(23)
communication rounds converge. Compared to Theorem 4.2, derive that log (1 azd)
log(1 ap + auuDDE); which indicates that AQUILA has faster convergence than LAG under the Pt. condition.

---

Under review as a conference paper at ICLR 2023
Remark. We want to emphasize that LAQ introduces the Lyapunov function into its proof, making extremely complicated.
addition, LAQ can only guarantee that the final objective function converges to range of the optimal solution rather than accurate optimum f(0"). Nevertheless, as discussed in Section 3.2 we utilize the precise model difference in AQUILA as a surrogate for the global gradient and thus simplify the proof.
5 EXPERIMENTS AND DISCUSSION
5.1 EXPERIMENT SETUP
In this paper, we evaluate AQUILA on CIFAR-10, CIFAR-100 (Krizhevsky et al., 2009). and WikiText- dataset (Merity et al. 2016), considering IID, Non-IID data scenario, and heteroge- neous model architecture (which is also a crucial challenge in FI.) simultaneously.
The FL environment is simulated in Python 3.9 with PyTorch 11.1 (Paszke al. 2019) im- plementation. For the diversity of the neural network structures, we train ResNet-18 8 (He et al.) 2016) at CIFAR- 0 dataset, Mobi leNet v2 (Sandler al. (018) CIFAR-100 dataset, and Transforme: (Vaswani et al. 2017) at Wiki Text 2 dataset.
As for the FL system setting, in the majority of our experiments, the whole system exists M 10 total devices. However, considering the large-scale feature of FL, we also validate AQUILA on larger system M 100/80 total devices for CIFAR / MikiText-2 dataset. The hyperparameters and additional details of our experiments are revealed in Appendix A.3
100%@CEAR 10GHD
100% 100g
(80 devites/@WiiTeat 2GHID
235
0560
0560
LAG
LAG
L40
ABUO
Adbo
LACAO
LAQO
LódeO
LOAA
LENA
Training Loss
1964
1.7
0.-
1:5-
10
25
25
30
10
14
319
200
358
418
758
Total Transiittedd
Bits
Total Transmitted (GB)
10)
100% 100
(c)
100%:gCIAR--10NNO--I
(1)
100% (80 devicesygwiileeee Z@HI
Thanomittdd Bits Eppch (46)
200
056n
L1N4
MARIA
Trnsmitte Bits, Epoch (MB)
4dv2
KAIRA AQUIA
Transmmtted Bits Egudh (48)
1750-
LAO
0360
WARMM
1250-
Macche
1000
56-
3te
Global Epoch
Global Epoch
Global Epoch
Figure 1: Comparison of AQUILA with other communication-effiieent algorithms on IID and Non- IID settings with homogeneous model structure. (a)-(c): training loss v.s. total transmitted bits, (d)-(f): transmitted bits per epoch v.s. global epoch.
5.2 HOMOGENEOUS ENVIRONMENT
We first evaluate AQUILA with homogeneous settings where all local models share the same model architecture as the global model. To better demonstrate the effectiveness AQUILA, its performance is compared with several state-of-the -oe-----thh--tttt methods, including AdaQuantFL, LAQ with fixed levels. LENA (Ghadikolaci et al. 2021. MARINA (Gorbunov et al.) 2021), and the naive combination of AdaQuantFL with LAQ, Note that based on this homogeneous setting, we conduct both IID and Non- IID evaluations on CIF AR-10 and CIF CIFAR- 100 dataset, and an IID evaluation on WikiText-2 To simulate the Non- NID FL setting (Dioo al. 2020h, each device is allocated two classes of data in CIFAR-10 and 10 classes data in CIFAR 00 at most, and the amount of data for each label balanced.
7

---

Under review as a conference paper at ICLR 2023
The experimental results presented in Fig. | where 100% implies all local models share similar structure with the global model (i.e., homogeneity). 100% (80 devices) denotes the experiment is conducted in 80 devices system, and LAdaQ represents the naive combination of AdaQuantFL and LAQ. For better illustration, the results have been smoothed by their standard deviation. The solid lines represent values after smoothing. and transparent shades of the same colors around them represent the true values. Additionally, Table shows the total number of bits transmitted by all devices throughout the FL training process. The comprehensive experimental results are established in Appendix A.4
5.3 NON-IIOMOGENEOUS SCENARIO
In this section, we also evaluate AQUILA with heterogeneous model structures as HeteroFL (Diao et all, (020), where the structures of local models trained the device side are heterogeneous. Suppose the global model epoch k is 0* and its size is d Wig hig then the local model of
each device m can be selected by 0% g [: Wm. hm], where Wm I'm " and hmm T'm hg-
respectively. In this paper, we choose model complexity levels I'm- 0.5.
100% BOOK--SSUCCIAA--OOO 10geD
(b)
100% Sww.gCIFAR-1000e 1D
100% 100%-50% Teatt-g ID
2.0
CSGD
06G0
14-
LAQ
18
Training Loss
LENA
LABSQ
1.6
LSN4
1Ade)
LABR
UBNA
MARRIA
144
MAR 84
MARM M
AQU
1.
AQULA
Tralning
AQULL
Ww
63-
10
15
50
100
200
Total Transmited Bits (GB)
Rital Transitteed Bits (GB)
Total Transitted Bits (G9)
SOSSCCIFR 100ND
(e)
30%GCCIAR 100
100% 50% 20
Transmitte Eparhh (140)
Tranomitted 0tss Epoch (40)
Trnnmitted Bits Epazhh (MB)
LAQ LAdO/
LENA
AQULA
LENA
AQULA
LAG
LENA
AQUAL
200
Lodo0
LAIBO
80-
20
20-
125
2013
$20
202
5000
Epoch
Epoch
Global
Epoch
Figure 2: Comparison of AQUILA with other communication-effiitn algorithms on IID and Non- IID settings with heterogeneous model structure. (a)-(c): training loss v.s. total transmitted bits, (d)-(f): transmitted bits per epoch v.s. global epoch.
Most of the symbols in Fig. 2 are identical to the Fig. 1 100%-50% is newly introduced symbol that implies half of the devices share the same structure with the global model while another half only have 50%* * 50% parameters as the global model.
Performance Analysis. First of all, AQUILA achieves a significant transmission reduction compared the naive combination of LAQ and AdaQuantFL in all datasets, which demonstrates the superiority of AQUILA's efficiency. Specifically, Table 2 indicates that AQUILA saves 57.49% of transmitted bits in the system of 80 devices at the WikiText- dataset and reduces 23. 23.08% of transmitted bits in the system of 100 devices at the CIFAR-1 1 00 dataset, compared to the naive combination. And other results in Table also show an obvious reduction terms of the total transmitted bits required for convergence.
Second, in Fig. and Fig. 2 the changing trend of AQUILA's communication bits per each round clearly verifies the necessity and effectiveness of our well-designed adaptive quantization level and skip criterion. In these two figures, the number of bits transmitted in each round of AQUILA fluctuates bit, indicating the effectiveness of AQUILA's selection rule. Meanwhile, the value of transmitted bits remains at quite a low level, suggesting that the adaptive guantization principle makes training more efficient. Moreover, the figures also inform that the quantization level selected by
8

---

Under review as a conference paper at ICLR 2023
AQUILA will not continuously increase during training instead of being as AdaQuantFL. In addition, based on these two figures, we can also conclude that AQUILA converges faster under the same communication costs.
Finally, AQUILA is capable of adapting to a wide range of challenging FL circumstances. In the Non-IID scenario and heterogeneous model structure, AQUILA still outperforms other algorithms by significantly reducing overall transmitted bits while maintaining the same convergence property and objective function value. In particular, AQUILA reduces 60.4% overall communication costs compared to LENA and 57.2% compared to MARINA on average. These experimental results in non-homogeneous FL settings prove that AQUILA can be stably employed in more general and complicated FL scenarios.
5.4 ABLATION STUDY ON THE IMPACT OF TUNING FACTOR 3
One key contribution of AQUILA is presenting a new lazy aggregation criterion 12) to reduce communication frequency. this part, we evaluate the effects of the loss performance of different tuning factor 3 value in Fig. 3 As 3 grows within certain range, the convergence speed of the model will slow down (due lazy aggregation). Still, it will eventually converge to the same model performance while considerably reducing the communication overhead. Nevertheless, increasing the value of /3 will lead to a decrease the final model performance since it skips so many essential uploads that make the training deficient. The accuracy (perplexity) comparison of AQUILA with various selections of the tuning factor 33 is shown in Fig. I0 which indicates the same trend. To sum up, should choose the value of factor / to maintain the model's performance and minimize the total transmitted amount of bits. Specifically, we select the value / = 0.1, 0.25, 1.25 for CIFAR-10 CIFAR-10C, and WikiText- datasets for our evaluation, respectively.
CIAR 10 Different bets
(o)
CIFAR-100 d Different bete
[c)
Wik 2 d Different Bets
beta-0 001
be00-0.001
beta-0
beta-0.1
4.
bela-2.1
betaw2
beta-0.15
beta-0.15
25
Taining Loss
Traninng Los5
b
betaw2.5
3.64
2.4
100
125
150
175
400
600
1000
200
450
605
000
1000
Globel Epoch
Globel Epoch
Gilobal Epoch
(4)
CIFAR-10 Different beta
(e)
@ Different
Wikilaxt-2 da Diffiennt
0.4
0 001
beta-0.1 0.1
beta-3.001
beta 1
beta
beta-] 0
beta 0
beta: 3 25
beta-o.22 25
beta-0.5
Accuracyy00
3.5
beta-0.22 0:25
betamo.5
Traiinng Loss
betam] 2.5
12
10
20
300
Total Transmitted (GB)
Total Transmitted Bits (GB)
Total
Transmitted (GB)
Figure 3: Comparison of AQUILA with various selections of the tuning factor B3 in three datasets.
CONCLUSIONS AND FUTURE WORK
This paper proposes communication-efficle FL. procedure 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 derived in this paper, the proposed AQUILA has been proven to be capable of reducing the transmitted costs while maintaining the convergence guarantee and model performance compared to existing methods. The evaluation with Non- IID data distribution and various heterogeneous model architectures demonstrates that AQUILA is compatible in non-homogeneous FL environment.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY
We present the overall theorem statements and proofs for our main results in the Appendix, well as necessary experimental plotting figures. Furthermore, we submit the code of AQUILA in the supplementary material part, including all the hyperparameters and requirements help the public reproduce our experimental results. Our algorithm is straightforward, well-described, and easy to implement.
ETНICS STATEMENT
All evaluations of AQUILA performed publicly available datasets for reproducibility purposes. This paper empirically studies the performance of various state-of-art algorithms, therefore, probably introduces no new ethical cultural problems. This paper does utilize any new dataset.
REFERENCES
Tianyi Chen, Georgios Giannakis, Tao Sun, and Wotao Yin. LAG: Lazily aggregated gradient for communication-efficcn distributed learning. In Proceedings of Advances in Neural Information Processing Systems, pp. 1 1-25, 2018.
Enmao Diao, Jie Ding, and Vahid Tarokh. HeteroFL: Computation and communication efficient
federated learning for heterogeneous clients. In Proceedings of the 8th International Conference Learning Representations, 2020.
Zhaoyang Du, Celimuge Wu, Tsutomu Yoshinaga, Kok-Lim Alvin Yau, Yusheng Ji, and Jie Li. Federated learning for vehicular Internet of things: Recent advances and open issues. IEEE
Computer Graphics and Applications, pp. 45-61, 2020.
Hossein Shokri Ghadikolaei, Sebastian Stich, and Martin Jaggi. LENA: Communication-efin distributed learning with self-triggered gradient uploads. In International Conference on Artificial Intelligence and Statistics, pp. 9941-395.. PMLR, 2021.
Eduard Gorbunov, Konstantin P Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In International Conference on Machine Learning. pp. 3788-3798. PMLR, 2021.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv:181 11/.////1.000 1.03604, 2018
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the 29th IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Divyansh Jhunjhunwala, Advait Gadhikar, Gauri Joshi, and Yonina C Eldar. Adaptive quantization of model updates for communication-cfie efficceent federated learning. In Proceedings of the 2021 IEEE International Conference Acoustics, Speech and Signal Processing, pp. 31 3110-3114, 2021.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009. URL https:: /topp://wwwwe wwwww/wwwww/w////w///wwwww cs www.ttoooooo.oooo www.:/tooo.uurrrraaaaaa ci .if...htmill..........
Yang Liu, Anbu Huang, Yun Luo, He Huang, Youzhi Liu, Yuanyuan Chen, Lican Feng, Tianjian Chen, Han Yu, and Qiang Yang. Fedvision: An online visual object detection platform powered by federated learning. Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 13172 13179, 2020.
Yuzhu Mao, Zihao Zhao, Guangfeng Yan, Yang Liu, Tian Lan, Lingi Song, and Wenbo Ding, Commu- nication efficient federated learning with adaptive quantization. arXiv preprint arXiv:2 /04000023, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication eefiicientiii learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282, 2017.
10

---

Under review as a conference paper at ICLR 2023
Stephen Merity, Pointer sentinel
Caiming
Xiong, models.
James
Bradbury, and Richard Socher. arXiv preprint arXiv:1609.077
mixture
2016.
URL
httpss//boggallffoocaaeeeeeoo.op
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style. high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4510-4520, 2018.
Jun Sun, Tianyi Chen, Georgios B Giannakis, Qinmin Yang, and Zaiyue Yang. Lazily aggregated quantized gradient innovation for communication-effiicee federated learning. IEEE Transactions on Pattern Analysis & Machine Intelligence, pp. 1-15, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.

---

Under review as a conference paper at ICLR 2023
A APPENDIX
The appendix includes supplementary experimental results, mathematical proof of the aforementioned theorems, and a detailed derivation of the novel adaptive quantization criterion and lazy aggregation strategy. Compared to Fig. [ and Fig. in the main text, the result figures in the appendix show a more comprehensive evaluation with AQUILA, which contains more detailed information including but not limited to accuracy vs steps and training loss vs steps curves.
A.1 OVERALL FRAMEWORK OF AQUILA
The cooperation of the novel adaptive quantization criterion (10) and lazy aggregation strategy (22 is illustrated in Fig. 4a. Compared the naive combination of AdaQuantFL and LAQ, where the mutual influence between adaptive quantization and lazy aggregation has not been considered, as shown Fig. pp. AQUILA 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 compress the transmission with a lower quantization level.
(a)
(b)
oi
skip
bes skip
AQUILA
Compress transmissiion with low
AdaQuantF11. +AA
Adaptive quantization level
Ap
aggregation strategy
AdaQuantFL
by
LAQ
Minimize model deviation caused skipping
Aoca
Desier
Devier
Devica
Dacke
Figure The schematic illustration of the communication--ffiiieenn FL. with AQUILA comparison with the naive combination of AdaQuantFL and LAQ. The blue lines indicating the transmission of quantized gradient innovation in AQUILA are drawn in different thicknesses to represent various sizes of quantized gradient innovation, considering the heterogeneous FL environment as in our evaluation part. For instance, the gradient innovation Aqğ of a PC larger than Aqš of a mobile phone.
A.2 EXPLANATION OF THE QUANTIZER AND THE SKIP RULE OF LAQ'S
The quantizer 6 is a deterministic quantizer that, at each dimension, maps the gradient innovation to the closest point at a middemmnnio grid. The range of the grid is R and the granularity is determined by quantization level - Each dimension of gradient innovation is mapped to an integer in (0, 1, 3,........ 2 1}. More precisely, the 1/2 ensures mapping to the closest integer instead of flooring to a smaller integer. The R in the numerator ensures that the mapped integer is nen-negative. As result, when the gradient innovation is transmitted to the central server, 32 bits are used for the range, and b d bits are used for the mapped integer. Thus, 32 + b d bits are transmitted total.
The difference between 66) and 32 (Lemma B.2) is that (6) encodes the gradient innovation vector to an integer vector, whilst (32) decodes the integer vector to a quantized gradient innovation vector. Specifically, in the training process, each client utilizes (6) to encode the gradient innovation to integer at each dimension, and afterwards, the integer vector & and 7/ are sent to central server. After receiving them, the central server can decode the quantized gradient innovation as (32 states.
12

---

Under review as a conference paper at ICLR 2023
The skip rule of LAQ is measured by the summation of the accumulated model difference and quantization error.
D Σ d'=1
Ex' -p0------i- + (11=m |
(24)
where Ea' series of manually selected scalars and D is also predetermined. e is the quantization error of client at epoch k, and é = the quantization of client m at last time it uploads its gradient innovation. Please refer to Sun al. (2020) for more details on (24). In order to compute the LAQ skip threshold, each client has to store enormous previous information.
The difference of AQUILA skipping criterion and LAQ skipping criterion is as follows. First, the AQUILA threshold is easier to compute for a local client. Compared to the LAQ skipping criterion, AQUILA skipping criterion is more concise and thus requires less storage and computing power. Second, the AQUILA criterion easier to tune because much fewer hyperparameters are introduced. Compared the LAQ criterion in which D and (Ear 18 only two hyperparameters a and 3 are introduced the AQUILA criterion. Third, with the given threshold, AQUILA has good theoretical property. The theoretical analysis of AQUILA is easier follow with no Lyapunov function introduced as in LAQ. And the result also shows that AQUILA can achieve a better convergence rate under the non-convex case and the PL condition.
all manually selected, whilst
A.3 EXPERIMENT SETUP
In this section, we provide some extra hyperparameter settings for our evaluation. For the LAQ. we set D = 10 and { & _... = ED 0 as the same as the setting in their paper. For LENA, set BLENA 40 in their trigger condition. And for MARINA, probability of Bernoulli distribution as p &q/d d as announced their paper. In addition, we choose the CrossEntropy function hyperparameter details of our evaluation.
calculate the uploading
objective function in the experiment part. Tshows the
Table I: The hyperparameters for CIFAR- -1FAR-10, CIFAR 100, and WikiText 2 datasets in the FL training process.
Dataset
CIFAR-10
CIFAR-100
WikiText-2
Model
ResNet-18
MobileNet-v2
Transformer
Data Distribution
IID
Non-IID
IID
Non-IID
IID
Global Epoch
200
200
1000
500
1000
Local Batch Size
256
256
256
256
64
Optimizer
SGD
SGD
SGD
SGD
SGD
Momentum
0.9
0.9
0.9
0.9
0.9
Weight Decay
5.00E-04
5.00E-04
5.00E-04
5,00E-04
5,00E-04
Learning Rate
0.1
0.1
0.1
0.1
0.5
Tuning factor /
0.1
0.005
0.25
0.003
1.25
A.4
COMPREHENSIVE EXPERIMENT RESULTS
This section will cover all the experimental results in paper.
13

---

Under review as a conference paper at ICLR 2023
Table 2: Numerical numbers of total communication bits in the homogeneous environment.
Total Comm Bits (GB)
QSGD
AdaQ
LAQ
LAdaQ
LENA
MARINA
AQUILA
IID-100
156.07
226.33
153.26
226.36
160.2
162.84
138.35
CIFAR-10
IID
15.61
34.19
15.22
34.18
15.95
16.28
4.59
Non-IID
13.61
20.39
14.48
19.86
17.64
16.28
11.53
IID-100
165.55
224.02
164.11
223.64
166.87
167.71
142.55
CIFAR-100
IID
16.56
28.68
16.28
14.41
16.63
16.77
3,98
Non-IID
8.28
14.54
8.27
14.25
9.19
8,49
6.12
IID-80
470.95
711.49
513.07
710.17
341.17
338.38
218.59
RikiText-2
IID
134.56
340.97
106.92
170.40
150.07
136.31
71.91
Table 3: Numerical numbers of total communication bits in the heterogeneous environment.
Total Comm Bits (GB)
QSGD
Ada
LAQ
Ada+LAQ
LENA
MARINA
AQUILA
IID
9.76
21.99
9.55
10.98
9.97
10.18
2.65
CIFAR-10
Non-IID
9.76
16.15
9.25
14.67
11.19
10.18
7.16
IID
10.56
19,42
10.56
9.7
10.61
10.7
2.51
CIFAR-100
Non-IID
5.28
10.07
5.28
5.02
5.56
5.42
3.66
WikiText-2
IID
99.09
248.87
92.74
124.47
119.83
100.38
53.84
14

---

Under review as a conference paper at ICLR 2023
100% 1100 SI
100% 1100 devises/ccCAAssoggg
100% (100 dinIcA//CCAAAAAAA
C002
Transnitedd Bts: Epoch (MB)
0500
A600
12:0
1440
1993
M4
CEG0
AQULA
L40
16600
330
AGULA
120
390
233
190
293
100 125
15
200
(a) Accuracy v.s. Transmitted Bits
(b) Loss v.s. Transmitted Bits
(c) Transmitted Bits per epoch
150% (150 dedreo BCIAAttnogga
100% (120 dedrreogaa7A--10001
100% (150 dedtroo@CTAAB-00000
200
L4D
330
LAG
LESA
AG.IAA
Loh
MM
220
Se00
330
209
Titel Thanamkteed Bics (CB)
Titel Thanmmited Dis (CB)
Global Epoch
(d) Accuracy v.s. Transmitted Bits
(c) Loss V.s. Transmitted Bits
(f) Transmitted Bits per epoch
100% (82 dedrregg/Wiilleiiii 201
102% (80 penicce///Wiillleeee
100% (60 destcee)gg/e Twati2 2013
CS6>
10+
Thromitted Bts Epoch 1W82
0600
Ad8o
10-
1990
LASIQ
Ldee0
MM
MA
AQULA
1993
350-
590
10.
250
300 203 X6
50 500
700
500
389
32
600
50
550
100
30
500
Total Tansmitted Bis
Tansmitted
(g) Perplexity v.s. Transmitted Bits
(h) Loss v.s. Transmitted Bits
(i) Transmitted Bits per epoch
300%
1100 deseestaCIPss:000
100% 1100 dedIcesSSOFAA 100G10
100% (60 desicesiSNN: 25HD
1400
1087-
LAG
LEVA
ACULA
Broe Eppch (46)
LBC
LOVA
AQULA
Tont metteetttd Bros Eporhh (ME)
3890
LAC
LEVA
ACUIAA
0000
1991
230-
350-
130-1
Global Spach
Global Epoch
Global Epoch
(i) Transmitted Bits per epoch
(k) Transmitted Bits per epoch
(1) Transmitted Bits per epoch
Figure 5: Comparison on 100 devices at CIFAR-10 0 and CIFAR- 00, 80 devices at Wi i Text-2 dataset in the IID, homogeneous scenario.
15

---

Under review as a conference paper at ICLR 2023
100%@CCM4-10010
100%@CIAH.10010
LAD
(MB)
UBD
LESA
40JIA
1:2-
130
LNOV2
Acurecys
LOM
AQULA
64-
40
Thtal Tansr Rled Bix
Tit Thanmmiteed Bicx (CB)
Global
(a) Accuracy v.s. Transmitted Bits
(b) Loss v.s. Transmitted Bits
(c) Transmitted Bits per epoch
190%.90144-120110
70-
Tranomitted Dite tooch (N0)
L40
2.5-
Loke
L4e30
C560
AQULA
160
10-
23
25
90c
Tttal Bix (Ga)
Tanurhiee Dis (CB)
Global Epoch
(d) Accuracy v.s. Transmitted Bits
(c) Loss v.s. Transmitted Bits
(f) Transmitted Bits per epoch
100
130%gg
LAO
LAG
LRQ
LACBO
MM No
AQUIA
Mi
AQULA
Thoomtteed
300
2-
290 Tansmitted Bits (CB)
Total Tansmkted
Global
(g) Perplexity v.s. Transmitted Bits
(h:) Loss v.s. Transmitted Bits
(i) Transmitted Bits per epoch
100%
Thire eeted Bits :ins: Feach (48)
ACJIA
01011
LAC
MORIA
AQULA
MONSO
There
220
1003
Global Spoch
Global Epoch
Global Epoch
(i) Transmitted Bits per epoch
(k) Transmitted Bits per epoch
(1) Transmitted Bits per epoch
Figure 6: Comparison on 10 devices at three datasets in the IID, homogeneous scenario.
16

---

Under review as a conference paper at ICLR 2023
100% Mlan-
10ONUECITA 10
240
0550
HARHHA
69-
L40
120
LPQ
LEVA
AQULA
LONA
5
A600
L40
65-
56 16o
Lis
15
Total banamiied Bis (00)
total Vanamited Bia (CB)
Global
(a) Accuracy v.s. Transmitted Bits
(b) Loss v.s. Transmitted Bits
(c) Transmitted Bits per epoch
1006@ciP44:000sooo-
10065CIFA--100aooolll
poneenttee pis Eyorh (H0)
0660
AQULA
Masshe
Liee0
AQULA
23
29
24
105
20
24
400
500
(d) Accuracy v.s. Transmitted Bits (c) Loss v.s. Transmitted Bits
(1) Transmitted Bits per epoch
100% 10
100%aCIAA 140
Thonamittos BRS EEoch p155
Thanomitte Bis MM50)
AOLLA
AQULA
Gabbl Erecc
Erach
Transmitted Bits per epoch
(h) Transmitted Bits per epoch
Figure 7: Comparison on 10 devices at three datasets in the Non-IID, homogeneous scenario..
17

---

Under review as a conference paper at ICLR 2023
100% S0%.S CHAN-LO
100% SPPESPAACIAA
100% 200-5525C1AA4100000
90-
LAD
LAD
LEGA
40JIA
A666
LAOWO
LOM
AQULA
Transmstted
8
LAG00
30-
Thtal Tanamklled Bix
Tit Tanamited Bix
Global
(a) Accuracy v.s. Transmitted Bits
(b) Loss v.s. Transmitted Bits
(c) Transmitted Bits per epoch
90.
Tranomitted Ditk tooch (ND)
L40
L4e30
LaM
0560
AQULA
160
12M6
25 286 325 35
175
200
06
25 381 325
25
172
200
90c
Titel Tenurbieed Bia (G8)
Total Tenurtieed Dix
Global Epoch
(d) Accuracy v.s. Transmitted Bits
(c) Loss v.s. Transmitted Bits
(f) Transmitted Bits per epoch
100%1-60% (ile--2-
100%6-50% www. 10
LAO
LAG
230
LACWO
MM No
Mi
AQUIA
AQULA
520
127
10'
Tansmitted
Tansmitted Bits
Global
(g) Perplexity v.s. Transmitted Bits
(h:) Loss v.s. Transmitted Bits
(i) Transmitted Bits per epoch
Thancrdtte Bios Feech (48)
300-
ACJIA
MARIA AQULA
Gren
AQUIA
100-
422
30-
330
100-
330
125 236
220
20
1003
Global Spach
Global Eprch
Global Epoch
(i) Transmitted Bits per epoch
(k) Transmitted Bits per epoch
(1) Transmitted Bits per epoch
Figure 8: Comparison on 10 devices at three datasets in the IID, heterogeneous scenario.
18

---

Under review as a conference paper at ICLR 2023
100% 10AAB-100 Now-iI
190% Non-l1
100%
1.2-
CCG3
0550
Adko
HARHHA
LAQ
530-
LPQ
LEVA
ACULA
90-
1,90
Thanemttedd Epoch
LCMS
85-
LAD
75-
70-
14
15s
Thtsl Tansmitted Bits (CR)
Thta Taansiitedd Bits (CB)
Global Eprch
(a) Accuracy v.s. Transmitted Bits
(b) Loss v.s. Transmitted Bits
(c) Transmitted Bits per epoch
130%-50%..C FAR-- Mon-il
20-
Trememittd fiis Eoorh (985)
5
leed
Loea0
1/0
0660
1.2-
AQULA
mell
Lice0
L256
20-
16
24
305
30
400
500
(d) Accuracy v.s. Transmitted Bits
(c) Loss v.s. Transmitted Bits
(f) Transmitted Bits per epoch
100%-5504 Dihondl
100% 102%-505-0000
Thonamizedd Bis Epoch (MB)
Thsnammmed MRt Eooch (MB)
-AG
x
15
Gibbal Epech
Globol Epoch
Transmitted Bits per epoch
(h) Transmitted Bits per epoch
Figure 9: Comparison on 10 devices at three datasets in the Non-IID, heterogeneous scenario.
CHAI-10 TD Difleeert
CRAA--102 Dif Diffreet
Wil: 1eet-2 d9 Different
20-
2e
beto=2.00
bcbo=3:03
37-
sie
0-
60c
Global spoch
Global Epoch
Global spoch
(a) Accuracy v.s. Global epach
(b) Accuracy v.s. Global epoch
(c) Perplexity v.s. Global epoch
CHARL110 @ Difieert
CIAA--102 Different beta
230
Wik: lust-2 @ Different beta
0ets000
32
Seta-2 25
seta-12
bebs-1 5
bebx-2.0
betb=2.00
beta=2.00
betb-5.3
bets-6.)
2.15
5.15
bets: 3.25
bete 0.25
bete: 2.5
bate 03
10
20
60
104
(d) Accuracy v.s. Transmitted Bits
(c) Loss v.s. Transmitted Bits
(f) Perplexity v.s. Transmitted Bits
Figure 10: Accuracy (Perplexity) comparison of AQUILA with various selections of the tuning factor 33 in three datasets.
19

---

Under review as a conference paper at ICLR 2023
B BASIC FACTS AND SOME LEMMAS
Bold fonts denote vectors (e.g., 0). Normal fonts denote scalars (e.g., a). Subscript m is used describe functions about local device m (e.g., fm (0)). function without subscript is used to describe an average among all devices (e.g., f(0)).
Notations:
Frequently used norm inequalities Suppose n E N+ and ||a denotes the l norm. For p in Rt 24 a, b E IR", there holds
1. Norm summation inequality.
Σ
2
x
(25)
1=1
2. Inner-product inequality.
1
(a, b)
(1lal1 1 + -161 - b11)
(26)
2
3. Young's Inequality.
la b12 < (1 p) [all2 + (1+ '0) 11b11
(27)
4. Minkowski's Inequality.
|a bl12 & ||a||| + -|1b112-
(28)
Assumption B.1. All devices' quantization errors eh will be constrained by the total error of the omitted devices., i.e., V = 0, o....... K. if M + Ø, 3 2 1, such that
e 11
1 PIIS M
Σ MEM
em
Σ
(29)
M
MEMs
2
where K denotes the termination time, and eth easy verify when Mk * bounded variable (here is e*) will always be bounded by part of itself ( Emem: ex) multiplied by a real number (7). Note that there is another nontrivial scenario that M # but e conflicts with our assumption. However, this situation only happens when all entries of e = 0, i.e., fm (0*)], " for all 0 i d.
(O') - Ag This lemma is
for all m MM which implies that y or not exists and
Lemma B.1. The summation of quantized gradient innovation and quantization error is bounded by the global model difference:
M
+
*
<
B7 a²
1
g
2
(30)
M
2
MEMS
2
20

---

Under review as a conference paper at ICLR 2023
Proof.
Σ
Amm
+
| 11
M
MEM:
1
Σ
Am
+7
Em
M
Ti MEM:
MEM
M
Σ
Ag
M
M
MEM
mEM
(31)
Σ
(I
+ + (1)
M
MEMÉ
(6)
Σ
(111 + 1||| || l12)
M
MEM
8y|MM
|
0h-1|
a²M²
87
0 kh-11
a²
where (a) follows Assumption B.I, (b) follows is larger than by definition, and (c) utilizes novel trigger condition 122
Lemma B.2. From Definition 3.1, we can derive that the relationship between quantized gradient innovation Ag and its quantization representation z which applies byt bits for each dimension:
Aq 2 Rk 3tth
Rd 1,
(32)
where 1 Rd denotes vector filled with scalar value 1.
Remark:We can utilize 32 to calculate the quantized gradient innovation in the experimental
implementation.
C MISSING PROOF OF LEMMA 3.1 AND THE DERIVATION OF b. m
With lazy aggregation, the actual aggregated model epoch i: is:
g++1_
a
Σ M
( k-1 + Ag
a
Σ
4m k-1
(33)
M
M
mEM!
Suppose Ak denotes the quantization loss of device epoch & and vh denotes the quantization representation of local gradient innovation as Definition 3.1, i.e.,
V Sm
(b))
k-1
1 R
2
1
(34)
2 Rk
2
21

---

Under review as a conference paper at ICLR 2023
With
33
and 34).
the model deviation | -0*113 caused by skipping gradients can be written
0
0
AT
M
mEM!
2n R 2bth
Riy
M
mEMÉ
a IM
Σ
27 Rij 2b
R
M
mEMÉ
a MM
Σ
(|
am
Ry
+ I' R A
R 112
M
mEM
2a²
Σ
(/
+ R2h ||2 + I 122
M
MEMC
(0)
20x² |
Σ
(i. - -thh
+
Tm li
+ dd)
M
2
ME.E
MM
Σ
+ || R 1,) +
M
MEM
2a?
2a
Σ
(1)
|| Rh || + F1
F 1112) 2 + +d)
M
MEMU
Σ
((]
- || 12 111)) + + 12th 11
d 2
- am
M
MEMB
4a2
MM
Σ
x-1 (()TFinCO)
- [12
|| R 1112) + (( ) )2 + d
M2
2
ME.M
(35)
where 1 E Rd denotes the vector filled with scalar value 1, (a) A E (-1, 0J. (b) R > + R
0.
Since R is independent of 7 we can formulate an optimization problem about Th for device m at communication round h as follows:
min oCT
(/V
ath 112 - -1|- -/1
R 111)
(36)
Therefore, the optimal solution of 7
36p is
(37)
m
Rl Vd
Then, the optimal adaptive quantization level (b%)) " is equal to
(b%))
logg(
1
+ 1)
(rk))
(38)
R vd
logz
+
V Fm (0*) - gm 1-1
Notice that (²*))²² >
is always true since (Trk)
&
22

---

Under review as a conference paper at ICLR 2023
D MISSING PROOF OF LEMMA 4.1, THEOREM 4.1 AND COROLLARY 4.1.
Proof. Suppose Assumptions 4.1, 4.2, and 4.3 are satisfied and M + Ø. For the simplicity of the convergence proof, we assume $² M Ememy Aqm First, we prove Lemma 4.1.
f ) f(0h)
Vf(0"), 0h+ 8*) I. | 8t
Vf(0"), (Vi(0)) - et vt))
L
k+
0+. 2
(S(O)) 1.- (VS(0)), E + $
0 1
gb+1
+ 2
VS(O") 11- (|7/(0)))
11² + +11E*
1
04113)
L
$*
0
0¹
+
a
2
((())))
//2 + 1 =
(
1
|
0²1
20
V
2 + a ||5 2 + |
2/2
L
1
|
0 06/12
20
(39)
Hence, we have
30
L
gatt1 gb 0u11 By 0
- ((0ht))-(C
+
(40)
2
2a
which gives us Theorem 4.1. Sum it up for k
1.2, ... K, we have
f(0k+1) f(0') <
Σ
K
(
L 1
|1
|
-0xl
20
(41)
K-1 1
87
|
8 gil12
97 +
|| - 101
+
+
2
2a
a
1
a
k=
Notice that inequality holds for both M + Ø and M = Ø. Therefore, for ( 2a O and all hyperparameters chosen properly, considering the minimum of || ((
81
<
min k=1,2..
(42)
41
2
[(0))) f((0))
+ By ||et 0
aK
For
1
1 Za
+
and all hyperparameters are chosen properly, we have that
| & ak (f())) - f(0)) )+ +
By ||@l 89112) < E
min
(43)
Rim I. 2, K
which demonstrates AQUILA requires K = 0 2wi
communication round with w1 = f(())
ac
f(0") + 81 |100 - -0013 to achieve min;=1,2,-..
V V |/(0+) E
23

---

Under review as a conference paper at ICLR 2023
E
MISSING PROOF OF COROLLARY 4.1 WHEN M = Ø.
Proof. Since the skipping subset of devices are the empty set, from (
we have
g 0¹
a
Σ
(Imh
+ Aq
a
Im
k-1
M
M
MEM*
MEM
a
Σ
(9th + Amm))
M
MEM
(44)
a
Σ (v - -Em)
M
MEM
a (Vi(0*)) -((
)
From
14 we have:
f(O
f(e))
2
a
2 +a
Σ
Aq
L 1
ghh+1 -g² 10 + ==11=1112
2
M
20
MEM
V )
(
|0+t1
001
+ a 1 1
+
2
2
2a/
a
V (
a
(
24 (1 p) (
1 + (1+pp
||{*1]]] 1==='' + + 1
2
2
1|-
(a²L a) (1+p) (5(00) 11;
+ (a (-a-) a) (1+p-1) || 12 + e
1
a ((LL (1 +p - 1) | | + a ((LL 1) (1 + +2) 2 2
2
(45)
If the factor of || in 45 is less than equal to 0, that is,
(aL 1) (1+p 2 0,
(46)
then the factor of (V)) | will be less than - which indicates that
f f(0*+1) f(())
Vf(0*)
(47)
Note that it not difficult to demonstrate that 466 and the same time. For instance, we can set p 0.1, a 0.1, 3 = 0.25, 7 = 2, I. = 2.5 that satisfies both of them.
2 2n + fx & can actually be satisfied at
F MISSING PROOF OF THEOREM 4.2.
Proof. Based on the intermediate result (40) of Theorem 4.1 and Assumption 4.4 (p- PE condition),
we have
s(0h) - |
11 + (5 2
| 0+
001/2
8y
0
0²
2
2
a
au(f(()) f(0))) +
L
11)
||
g&
By
l
2
+
2
2a
2
a
(48)
which is equivalent to
f(0h+l) - f(0)
19
(1 - (1) f(())) +
( L
1
|
gh
||2
+
3y
g²
g
2
2 2a
2
a
2
(49)
24

---

Under review as a conference paper at ICLR 2023
Suppose 87 < (1 aqd) (2. - 2), show that
(
1 4 | 0r 0²
)(0)t))-10 - 1(0")
2
2a
(50)
< (1 aa4)
((00) - 1(0))
L
||
0²
8
2
2a
2
2
Therefore, after multiply & 1.2,
K, we have
f(0kth)-5(09)
1
L
| - 0k
1
2a
2
2
(51)
< (1 au)) x (1()) -(00)
1
L
100 00[ <e,
((00)))(00)
+
2a
2
which demonstrates AQUILA requires K 0 (-
log 41
communication round with
W1 -((0') - -(00) + 2
5) 110 - 11 to achieve 1(0K+1)- - ((0") + (2 -- |10
0K113 & c.
25


Reviews:
[{"review_id": "vcQyPICiDb", "reviewer": "Reviewer_ogm4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper proposes a communication-efficient federated learning strategy, AQUILA, that combines lazily-aggregated quantization (LAQ) and adaptive quantization (AdaQuantFL). This strategy balances the communication frequency for each parameter and the quantization level adaptively. Experimental results show that AQUILA outperforms the baselines (including LAQ and AdaQuantFL individually) on CIFAR-10, CIFAR-100, and WikiText datasets. ", "summary_of_the_review": "Please see my comments above. ", "strength_and_weaknesses": "The paper is well-written. Overall, I enjoyed reading the paper. Even though the main ideas and the approaches in the proofs are mainly borrowed from existing works, I think the authors did a good job in combining the methods.\n\n- When averaging the local objective functions in (1), why isn't the local function weighted by the number of local samples $n_m$? \n\n- Page 4, first line: quantification -> quantization.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Lad-zhLtsr", "reviewer": "Reviewer_NDFY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "The paper proposes a new adaptive quantization strategy (and aggregation criteria), AQUILA, by adaptively determining the quantization bits per round per client in lazily aggreagated federated learning. The quantization level $b^*$ is chosen based on the $l_\\infty$ and $l_2$ norm of the difference between the current gradient and the previous quantized gradient. Convergence rates in non-convex and PL condition are provided. Experiments are conducted to show the advantages of the proposed method.", "summary_of_the_review": "I feel that the motivation of this paper is not very strong. I have some concerns about the design of the new adaptive quantization strategy. The theoretical analysis needs some seemingly meaningless assumption and does not consider stochastic gradients which is less practical. The experiments lacks ablation study and comparison with important methods. Thus, I think the paper is below the high bar of ICLR in its current version.", "strength_and_weaknesses": "Pros:\n1. The topic of federated learning (FL) is important and interesting to NeurIPS community.\n2. The paper provides both theoretical and empirical results.\n3. The writing and presentation, though can still be improved, is in general clear.\n\nCons:\n1. (i) The motivation is not very strong. While alternating the number of bits $b$ across training rounds might be effective, it is not guaranteed to always bring benefits (reduced communication). Specifically, in formula (10) when choosing $b^*$, it seems that the number of bits largely relies on the largest entry of the vector ($l_\\infty$ norm). What if the vector only has a few 'outliers'? This strategy would use a large $b$ to compromise those outliers. A more practical and possibly better strategy might be sending those large coordinates in full-precision, and quantize others using low bits. This may use much less communication than the proposed strategy. In my understanding, (10) basically says that if the largest magnitude of the vector is big, we use more bits. This does not look very exciting and promising to me.\n\n(ii) From Figure 2 and Figure 3, we see that the communication across training rounds of AQUILA is almost constant (a flat line). Then why not simply using a fixed number of bits? I think a figure with the evolution of the $b^*$ for the clients might help.\n\n(iii) The communication criteria (11) looks more like a byproduct for the convenience of proof (e.g., Lemma A.1). Could you please provide more intuition on it and its difference with (6)? Besides, I have two questions regarding (11). First, how do you know $\\theta^{k+1}$ at time $k$? Second, are both $\\gamma$ and $\\beta$ free hyperparameters? If so, the algorithm becomes much harder to tune which is also a potential drawback.\n\n2. The convergence analysis considers full gradient without noise, which is less practical since people use SGD in most applications. On page 6, the authors wrote 'we could still prove the correctness of Corollary 4.1 in this special condition without any extra assumptions'. Then why is Assumption 4.3 needed? \n\n3. Indeed, Assumption 4.3 seems a little bit strange. In (13), is the $\\gamma$ the same as that in (11)? Also, you can assume a very large $\\gamma$ for this condition to hold. However, I do not see this $\\gamma$ appearing in later theoretical results. So how does this assumption affect the analysis?\n\n4. The experiments uses $M=24$ clients which is rather small for FL. Also, there is no ablation study on the impact of $\\gamma$ and $\\beta$. Thus we do not know how robust this algorithm is to different choices of the hyperparameters. I think the authors should also compare with strategies with fixed-bit quantization like the popular QSGD method. This could help justify the importance of adaptive quantization and strengthen the motivation. Currently, given the above concerns, I think the motivation is not very strong.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BdkBog28KEu", "reviewer": "Reviewer_6iqd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "This paper proposes a framework for federated learning by adjusting the frequency of communication between agents and the server with an adaptive quantization scheme. Specifically, the authors combine two quantization schemes, namely, the adaptive quantization rule (AdaQuantFL) and lazily aggregated quantization (LAQ). ", "summary_of_the_review": "The paper falls short to highlight the main novelty compared to the previous works on the lazy aggregation of quantized gradients for federated learning as I detailed above. The theoretical results suggest no improvement compared to existing methods such as LAG and LAQ.", "strength_and_weaknesses": "Weaknesses:\n\n- My main concern is regarding the novelty of the proposed method and also, in improving the existing results. This paper seems to be significantly built on a prior work \"Lazily Aggregated Quantized Gradient Innovation for Communication-Efficient Federated Learning\". It is not clear how the performance of LAQ in the mentioned work is improved in theory. The authors only mention a comparison after Theorem 4.2: \" Theorem 4.2 informs us that AQUILA can achieve a linear convergence rate as in LAG (Chen et al., 2018) and LAQ when certain assumptions are satisfied.\" I wonder what would be the motivation to use the proposed AQUILA method if it achieves the same performance for already existing LAG and LAQ methods.\n\n- The paper considers a (not class) specific quantizer which limits the scope of the theoretical and simulation results. \n\n- Assumption 4.3 states that all devices’ quantization errors are constrained by the total error of the omitted devices. The justification for this assumption is presented as follows: This assumption is easy to verify when M_c≠∅ this a bounded variable will always be bounded by a part of itself multiplied by a real number. This statement is not accurate and should be: This assumption is easy to verify when M_c≠∅ this a bounded variable will always be bounded by a non-zero part of itself multiplied by a real number. So, how can we guarantee that the total error of the omitted devices is non-zero?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "B-QdEpOjGa", "reviewer": "Reviewer_qabV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper proposes a new communication efficient federated learning approach that combines adaptive quantization with lazy aggregation of gradients at each round to reduce the amount of data communicated as compared to prior work while providing comparable reduction in training loss. The approach is validated through theoretical analysis and experiments in both homogenous and heterogeneous federated learning settings.", "summary_of_the_review": "The paper proposes a novel principled approach for communication efficient federated learning approach that combines adaptive quantization with lazy aggregation of gradients and is backed by both theoretical analysis and experimental evaluation. However, some points need to be explained more clearly and some background information needs to be provided to make it fully accessible to readers.", "strength_and_weaknesses": "Strengths:\n\na) The main strength of the paper is that it combines adaptive quantization and lazy aggregation of gradients in a principled manner. Specifically, the quantization level at each round at a given node is clearly connected to the amount of new information (gradient innovation) being provided by the node instead of just depending on the loss value. \n\nb) The principled approach is then backed by analysis and experiments to show that it indeed reduces the amount of data being communicated while providing the same training performance in a variety of settings.\n\nWeaknesses:\n\na) The main weakness according to me is that the explanation of the algorithm is currently not very clear. I have provided some comments/suggestion on improving this in the following section. \n\nb) While the main selling point for AQUILA is the reduction in the amount of data being communicated, the current theoretical results only show that the training converges at the same rate as standard GD. Any analytical result characterizing the expected reduction in amount of data being communicated would significantly strengthen this work. Alternately can you provide some explanation for why such an analysis is difficult?\n\nc) Likewise, from Figure 3 (d-f) it appears that the variance in the amount of data being communicated is also significantly lower in AQUILA which is a point in its favour, especially if the network cannot handle large fluctuations in the amount of communication. Can you provide some analysis/intuition for why that may be the case?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject