DAdaQuant: Doubly-adaptive quantization for communication-efficient Federated Learning
Authors: Robert Hönig
Yiren Zhao
Robert D. Mullins
Venue: ICLR 2022 Submitted (2022)
Keywords: federated learning
gradient compression
quantization
communication efficiency

Abstract: Federated Learning (FL) is a powerful technique for training a model on a
server with data from several clients in a privacy-preserving manner. In FL,
a server sends the model to every client, who then train the model locally
and send it back to the server. The server aggregates the updated models and
repeats the process for several rounds. FL incurs significant communication
costs, in particular when transmitting the updated local models from the
clients back to the server. Recently proposed algorithms quantize the model
parameters to efficiently compress FL communication. These algorithms
typically have a quantization level that controls the compression factor. We
find that dynamic adaptations of the quantization level can boost
compression without sacrificing model quality. First, we introduce a
time-adaptive quantization algorithm that increases the quantization level
as training progresses. Second, we introduce a client-adaptive quantization
algorithm that assigns each individual client the optimal quantization level
at every round. Finally, we combine both algorithms into DAdaQuant, the
doubly-adaptive quantization algorithm. Our experiments show that DAdaQuant
consistently improves client$\rightarrow$server compression, outperforming
the strongest non-adaptive baselines by up to $2.8\times$.

Under review as a conference paper at ICLR 2022
DADAQUANT: DOUBLY-ADAPTIVE QUANTIZA- TION FOR COMMUNICATIO-EFFICIENT FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated Learning (FL.) is powerful technique for training a model on server with data from several clients in a privacy-preserving manner. In FL., a server sends the model to every client, who then train the model locally and send it back to the server. The server aggregates the updated models and repeats the process for several rounds. FL incurs significant communication costs, in particular when transmitting the updated local models from the clients back to the server. Recently proposed algorithms quantize the model parameters to efficiently compress FL communication. These algorithms typically have a quantization level that controls the compression factor. We find that dynamic adaptations of the quantization level can boost compression without sacrificing model quality. First, we introduce a time-adaptive quantization algorithm that increases the quantization level train- ing progresses. Second, we introduce a client-adaptive quantization algorithm that assigns each individual client the optimal quantization level at every round. Finally, we combine both algorithms into DAdaQuant, the doubly-adaptis quan- tization algorithm. Our experiments show that DAdaQuant consistently improves client compression, outperforming the strongest non-adaptive baselines by up to 2.8x.
INTRODUCTION
Edge devices such as smartphones, remote sensors and smart home appliances generate massive amounts of data (Wang et al.] 2018b; Cao al.) 2017 Shi & Dustdar (016). In recent years, Federated Learning (FL) has emerged as a technique to train models on this data while preserving privacy [McMahan et al., 2017 Li al. 2018).
In FL, we have a single server that is connected to many clients. Each client stores a local dataset that it does not want share with the server because of privacy concerns or law enforcement (Voigt & Von dem Bussche (017). The server wants to train a model on all local datasets. To this end, initializes the model and sends it to random subset of clients. Each client trains the model on its local dataset and sends the trained model back to the server. The server accumulates all trained models into an updated model for the next iteration and repeats the process for several rounds until some termination criterion is met. This procedure enables the server to train a model without accessing any local datasets.
Today's 's neural network models often have millions or even billions (Brown et al., 2020 of param- eters, which makes high communication costs a concern in FL. fact, Qiu al. (202)) suggest that communication between clients and server may account for over 70% of energy consumption FL.. Reducing communication requirements, energy consumption and training time.
is an attractive area of research because it lowers bandwidth
Communication in FL occurs in two phases: Sending parameters from the server to clients (down- link) and sending updated parameters from clients to the server (uplink). Uplink bandwidth usually imposes a tighter bottleneck than downlink bandwidth. This has several reasons. For one, the av- erage global mobile upload bandwidth is currently less than one fourth of the download bandwidth (Speedlest). For another, FL downlink communication sends the same parameters to each client. Broadcasting parameters is usually more efficient than the accumulation of parameters from differ-

---

Under review as a conference paper at ICLR 2022
ent clients that is required for uplink communication (Amiri al. 2020 Reisizadeh et al. For these reasons, we seek to compress uplink communication.
2019
A Client
Client
B
Client A
Client B
pí x [0,1]
ps x [0, 1
PA x [0,1]
ps x [0. 1]
8
Server
qB
8
4A
Server
qB
Q(pa)
Q Q
Q
Q(pn)
Q()) Epaig [Var (Q(p))] = 0.0018
Q(P) BPA.PD Var (R(p)) = 0.0017
(a) Static quantization.
(b) Client-adaptive quantization.
Figure 1: Static quantization vs. client-adaptive quantization when accumulating parameters P.1 and PB- (a): Static quantization uses the same quantization level for PA and pg. (b) Client-adaptive quantization uses slightly higher quantization level for pa because Pa is weighted more heavily. This allows us to use a significantly lower quantization level QA for pa while keeping the quanti- zation error measure Epg.pg [Var (Q())) roughly constant. Since communication is approximately proportional to Ч + qB, client-adaptive quantization communicates less data.
A large class of compression algorithms for FL apply some lossy quantizer Q, optionally fol- lowed by lossless compression stage. Q usu- ally provides "quantization level" hyperparam- eter g to control the coarseness of quantization (e.g. the number of bins for fixed-point quanti- zation). When q is kept constant during train- ing, we speak of static quantization. When changes, we speak of adaptive quantization. Adaptive quantization can exploit asymmetries in the FL framework to minimize communica- tion. One such asymmetry lies in FL's train- ing time, where Jhhujhhunwll et al., (2021) ob- served that early training rounds can use a lower q without affecting convergence. Figure il- lustrates how time-adaptive guantization lever- ages this phenomenon to minimize communi- cation. Another asymmetry lies in FL's client space, because most FL algorithms weight client contributions to the global model proportional to their local dataset sizes. Figure iillustrates how client-adaptiv quantization can minimize the quantization error. Intuitively, FL clients with greater weighting should have greater commu- nication budget and our proposed client-adaptive quantization achieves this in a principled way. To this end, introduce the expected variance of accumulation of quantized parameters, E[Var(> ( (pp)), as measure of the quantization error. Our client-adaptive quantization algorithm then assigns clients minimal quantization levels, subject a fixed [[Var( Q(p))]- This lowers the amount of data communicated from clients to the server, without increasing the quantization error.
Loss
q=1
adaptive q
4
2
Communication
Figure 2: Time-tdaptive quantization. A small quantization level (q) decreases the loss with less communication than a large but converges to higher loss. This motivates an adaptive quanti- zation strategy that uses a small as long as is large q. We
beneficial and then switches over generalize this idea into an algorithm that mono- tonically increases q based on the training loss.
DAdaQuant (Doubly Adaptive Quantization) combines time- and client-adaptive quantization with an adaptation of the QSGD fixed-point quantization algorithm to achieve state-of-the-an FL uplink compression. In this paper, we make the following contributions:
We introduce the concept of client-adaptive quantization and develop algorithms for time- and client-adaptive quantization that computationally efficient, empirically superior to existing algorithms, and compatible with arbitrary FL quantizers. Our client-adaptive quantization is prov- ably optimal for stochastic fixed-point quantizers.
2

---

Under review as a conference paper at ICLR 2022
We create Federated QSGD as an adaptation of the stochastic fixed-point quantizer QSGD that works with FL. Federated QSGD outperforms all other quantizers, establishing a strong baseline for FL compression with static quantization.
We combine time- and client-adaptive quantization into DAdaQuant. We demonstrate DAdaQuant's state-of-the-art compression by empirically comparing against several compet- itive FL compression algorithms.
RELATED WORK
FL research has explored several approaches to reduce communication. identify three general directions.
First, there a growing interest investigating FL. algorithms that can converge fewer rounds. FedAvg (McMahan et al. 2017) achieves this with prolonged local training, while FOLB (Nguyen ct al. 2020) speeds up convergence through a more principled client sampling. Since communication proportional to the number of training rounds, these algorithms effectively reduce communication.
Secondly, communication can be reduced by reducing the model size because the model size is proportional the amount of training communication. PruneFL (Jiang et al. 2019) progressively prunes the model over the course of training, while AFD (Bouacida et al. 2021) only trains sub- models on clients.
Thirdly, is possible to directly compress FL training communication. FL compression algorithms typically apply techniques like top-k sparsification (Malekijoo et al. 2021: Rothchild et al., (0200) or quantization (Reisizadeh et al. 2019; Shlezinger et al.) (020) to parameter updates, optionally followed by lossless compression. Our work applies quantization--asse
compression algorithms. It is partially based on QSGD (Alistarh et al., (017). which combines lossy fixed fixed-point quanti- zation with a lossless compression algorithm compress gradients communicated in distributed training. DAdaQuant adapts QSGD into Federated QSGD, which works with Federated Learning- DudaQuant also draws inspiration from FedPAQ (Reisizadeh al., 2019), the first FI. framework to use lossy compression based on model parameter update quantization. However, FedPAQ does not explore the advantages additional lossless compression or adaptive quantization. UVeQFed (Shlezinger et al.) 2020) is an FL compression algorithm that generalizes scalar quantization to vector quantization and subsequently employs lossless compression with arithmetic coding. Like FedPAQ, UVeQFed also limits itself to a single static quantization level.
Faster convergence, model size reduction and communication compression are orthogonal tech- niques, they be combined for further communication savings. For this paper, limit the scope of empirical comparisons to quantization -hased FL. compression algorithms.
For quantization- based compression for model training, prior works have demonstrated that DNNs can be successfully trained in low-precision (Banner et al., 2018 Gupta et al.) 2015 Sun et al., 2019). There also several adaptive quantization algorithms for training neural networks in non-distributed setting. [Shen et al. (2020) use different quantization levels for different parameters of neural network. FracTrain (Fu et al., 2020) introduced multi-dimension adaptive quantization by developing time-adaptive quantization and combining it with grrameter-adaptivv quantization. However, FracTrrain uses the current loss to decide on the quantization level. FL generally can only compute local client losses that are too noisy to be practical for FracTrain. AdaQuantFL. introduces time-adaptive quantization to FL, but requires the global loss (Jhunjhunwala et al. 2021). To com- pute the global loss, AdaQuantFL has to communicate with every client each round. We show in Section 4.2 that this quickly becomes impractical as the number of clients grows. DAdaQuant's time adaptiee quantization overcomes this issue without compromising on the underlying FL com- munication. In addition, to the best of our knowledge, DAdaQuant is the first algorithm to use client-adaptive quantization.
3

---

Under review as a conference paper at ICLR 2022
3
THE DADAQUANT METHOD
3.1 FEDERATED LEARNING
Federated Learning assumes a client-server topology with a set C = {cili [1,2..NN) of N clients that are connected to single server. Each client C₁ has local dataset D₁. from the local data distribution Dg. Given a model M with parameters p, a loss function fp(d E D2) and the local loss
F& (p)
D EAED, (d),, FL seeks minimize the global loss G(p) = Σ k=
D2.
D Px(p).
3.2 FEDERATED AVERAGING (FEDAVG)
DAdaQuant makes only minimal assumptions about the FL algorithm. Crucially, DAdaquant can complement FedAvg (McMahan et al. 2017), which representative of large class of FL algo- rithms.
FedAvg trains the model M over several rounds. In each round FedAvg sends the model param- eters Pt to a random subset St of K clients who then optimize their local objectives (Pt))) and send the updated model parameters p1+ back the server. The server accumulates all parameters |Dyl into the new global model Pr+1 ExEs, Σ, D př+1 and starts the next round. Algorithm lists FedAvg in detail. For our experiments, we use the FedProx (Li al. 2018) adaptation of FedAvg. FedProx improves the convergence of FedAvg by adding the proximal term 5 #1lp2+ p. to the local objective Fx (p(+1) Line 20 of Algorithm
3.3 QUANTIZATION WITH FEDERATED QSGD
While DAdaQuant be applied to any quantizer with configurable quantization level, it is op- timized for fixed-point quantization. We introduce Federated QSGD as competitive stochastic fixed-point quantizer top of which DAdaQuant applied.
In general, stochastic fixed-point quantization uses a quantizer Qg with quantization level that splits Rz0 and Rgo into q intervals each. 0, then returns the sign of p and |p] stochastically rounded to one of the endpoints of its encompassing interval. (p) quantizes the vector elementwise.
We design DAdaQuant's quantization stage based on QSGD, an efficient fixed-point quantizer for state-of-the siree-of-the-aa gradient compression. QSGD quantizes a vector in three steps:
p 1. Quantize as Q [||l| into bins in [0, 1]. storing signs and |p||z separately. (lossy)
2. Encode the resulting integers with O run-length encoding, (lossless)
3. Encode the resulting integers with Elias w coding. (lossless)
QSGD has been designed specifically for quantizing gradients. This makes it not directly applica- ble to parameter compression. To overcome this limitation, we apply difference coding to uplink compression, first introduced to FL by FedPAQ. Each client сą applies Q, the parameter updates pf+1 Pt (cf. Line of Algorithm I and sends them the server. The server keeps track of the previous parameters and accumulares the quantized parameter updates into the new parameters as [D2] P++1 = Pt + Σkes, Σ. L. o, (pi+ p.) (cf. Line 11 of Algorithm Ip. We find that QSGD works well with parameter updates, which can be regarded as an accumulation of gradients over several training steps. We call this adaptation of QSGD Federated QSGD.
3.4 TIME-ADAPTIVE QUANTIZATION
Time-adaptive quantization uses different quantization level de for each round of FL training. DAdaQuant chooses q: to minimize communication costs without sacrificing accuracy. To this end, we find that lower quantization levels suffice to initially reduce the loss, while partly trained models require higher quantization levels to further improve (as illustrated Figure 2). FracTrain built
on similar observations for non-distributed training. Therefore, design DAdaQuant to mimic FracTrain in monotonically increasing 9. as a function of t and using the training loss to inform increases in gt-
4

---

Under review as a conference paper at ICLR 2022
Round Samples
3
4
Round
2
3
Client
Quantization level
Client
Samples
Quantization level
A
1
8
A
4
B
2
8
B
2
2
4
3
8
3
8
2
(a) Static quantization.
(b) Time- Line-adaptive quantization.
Round
2
5
Round
Client
Samples
Quantization level
Client
Samples
Quantization level
A
1
6
A
B
2
7
9
2
C
3
9
2
D
D
9
(c) Client-adaptive quantization.
(d) Time-adaptinn and client-adaptive quantization.
Figure 3: Exemplary quantization level assignment for FL clients that train over 5 rounds. Each
round, two clients get sampled for training.
When q is too low, FL converges prematurely. Like FracTrain, DAdaQuant monitors the FL loss and increases when it converges. Unlike FracTraiin there is no single centralized loss function evaluate and unlike AdaQuantFL, we do assume availability of global training loss G(p.). [P_|
Instead, we estimate G(p.) as the average local loss G, = Ekes, Σ, [PIl Fk(Pt) where S, is the set of clients sampled at round t. Since S typically consists of only small fraction of all clients, G. is very noisy estimate of G(p:). This makes it unsuitable for convergence detection. Instead, DAdaQuant tracks a running average loss G. = v + - G..
Gmin E N. DAdaQuant determines training converge whenever G 2 Gi+1-6 for some & N that specifies the number of rounds across which we compare G. On convergence, DAdaQuant sets q: 2 and keeps the quantization level fixed for least rounds to enable reductions G to manifest in G. Eventually, the training loss converges regardless of the quantization level. To avoid unconstrained quantization increases on convergence, limit the quantization level to 9max-
We initialize Q1 Qmin for
The following equation summarizes DAdaQuant's adme-ada quantization:
Qmin
t = 0
> and G.-1 G. and and 29t-1 1 < Jmux and ft-1 9t-@
2q:-1
96-1
else
3.5 CLIENT-ADAPTIVE QUANTIZATION
FL algorithms typically accumulate each parameter P; all clients into weighted average p ΣK wip; (see Algorithm Ip. Quantized FL accumulates quantized parameters (,(p) ΣK (p,) where is the quantization level. We define the quantization error et = |p Q (p)l-
We observe in our experiments that communication cost per client is roughly linear function of Federated QSGD's quantization level q. This means that the communication cost per round is pro- portional Q Kg. We call Q the communication budget and use as a proxy measure of communication cost.
Client-adaptive quantization dynamically adjusts the quantization level of each client. This means that even within single round, each client can be assigned a different quantization level ga- The previous definitions then generalize to Ek 9k and Qn (p) ΣKK w,Q,, (px) and 9 (p)].
egt egl--OoK
Prior convergence results for distributed training and FL rely
upper bound
Var VQ az (p)) that determines the convergence speed Li et al. (2017); Horváth et al. (2019): Rei- sizadeh et al. 2019). This makes V(Q (p)) natural measure optimize for when choosing (k-
5

---

Under review as a conference paper at ICLR 2022
We optimize for the closely related measure Epi...px [Var(Q,) (p)]] that replaces the upper bound with an expectation over parameters P1... .....PK. Heuristically, we expect an this averaged measure to provide better estimate of practically observed quantization errors than upper bound. For a stochastic, unbiased fixed-point compressor like Federated QSGD, Epp... (Var(Qq..... (p)) equals E pp...p [Va(<()) and can be evaluated analytically.
We devise algorithm that chooses qs minimize Q subject to Epi...px (ar(ee (a)(e)))))))) Ep....pk [Var(eş)] for given q. Thus, our algorithm effectively minimizes communication costs while maintaining a quantization error similar to static quantization. Theorem | provides us with an analytical formula for quantization levels Q1 ... 9K-
Theorem 1. Given parameters ...... Pr [[-1,1 and quantization level q, miitgg---9 Ei= oi
subject to Ep....x [Var(eg = Ep....p [Va((e))] minimized by qi V h x w, where
K دj= w and Σ}=
DAdaQuant applies Theorem to lower communication costs while maintaining the same loss as static quantization does with fixed q. To ensure that quantization levels are natural numbers, DAdaQuant approximates the optimal real-valued solution as qi = max m / wx Appendix [ gives detailed proof of Theorem To the best of our knowledge, DAdaQuant the first algorithm to use client-adaptive quantization.
|
Algorithm 1: The FedAvg and DAdaQuant algorithms.
The uncolored lines list FedAvg. quantization, alient-adaptive
Adding the colored lines creates DAdaQuant. quantization, adaetiiee quantization.
1 Function RunServer () [D.
Initialize W/ = Σ, [D] for all i E (1,...,N) NN;
for O...., T do
Choose S C C with S
K, including each ex E C with uniform probability:
Omin
t t> 0 and Ś, 2 G.- and > ò and q: S 9max and 9:-1 Qr-6
21
9i-1
else
for cs E Sy do in parallel
d + V K -
2/3
Σx1 m²
Send(ck. ):. y; end
Receive(Cs, Ck2 p1+1,0())
10
P++1 - Eneo, W.Pt41i
G, - Exes, G/Gh
G. @G.-t + (1 (1
Go
t
else
14
end
15 end
Function RunClient (ck)
17
while Truc do
18
Receive (Server, Pr, ) P - G :x::::
20
F trained with SGD for E epochs with learning rate
Send(Server, 0gy (pi+1) Gt);
end
end

---

Under review as a conference paper at ICLR 2022
3.6 DOUBLY- QUANTIZATION (DADAQUANT)
DAdaQuant combines the time-adaptive and client- siiiett-daapive quantization algorithms described in the previous sections. At each round t, time-adaptive quantization determines preliminary quantization level q.- Client-adaptive quantization then finds the client quantization levels of k E {L..... ....K)
that minimize Σm= 9 subject to pp....xx [Var(ee)...x) )] = Ep...px px [Var(e])]. Algorithm lists DAdaQuant in detail. Figure gives an example of how time-adaptive, client-adaptive and doubly-adaptive quantization algorithms set quantization levels.
Reisizadeh al.) (2019) prove the convergence of FL with quantization for convex and non-convex cases as long as the quantizer Q is (1) unbiased and (2) has a bounded variance. These conver- gence results extend to DAdaQuant when combined with any quantizer that satisfies (I) and (2) for DAdaQuant's 's minimum quantization level 1. Crucially, this includes Federated QSGD.
We highlight DAdaQuant's low overhead and general applicability. The computational overhead is dominated by an additional evaluation epoch per round per client to compute G. which is negligible when training for many epochs per round. In our experiments, we observe computational overheads of ~ 1% (see Appendix A.2). DAdaQuant can compliment any FL algorithm that trains models over several rounds and accumulates weighted average of client parameters. Most FL algorithms, including FedAvg, follow this design.
EXPERIMENTS
4.1 EXPERIMENTAL DETAILS
Evaluation We use DAdaQuant with Federated QSGD to train different models with FedProx on different datasets for a fixed number of rounds. We monitor the test loss and accuracy at fixed intervals and measure uplink communication at every round across all devices.
Models & datasets We select a broad and diverse set of five models and datasets to demonstrate the general applicability of DAdaQuant. To this end, we use DAdaQuant to train a línear model, CNNs and LSTMs of varying complexity on federated synthetic dataset (Synthetic), as well as two federated image datasets (FEMNIST and CelebA) and two federated natural language datasets (Sent140 and Shakespeare) from the LEAF (Caldas et al. 2018) project for standardized FL re- search. We refer to Appendix A. for more information on the models, datasets, training objectives and implementation.
System heterogeneity In practice, FL has to cope with clients that have different compute capabil- ities. We follow Li et al. (2018) and simulate this system heterogeneity by randomly reducing the number of epochs to E" for a random subset S/ C S, of clients at each round f, where E' is sampled from [1. 1,.... E| and | 0.9K.
Baselines We compare DAdaQuant against competing quantization based algorithms for FL param- eter compression, namely Federated QSGD, FedPAQ (Reisizadeh al., 2019), GZip with fixed- point quantization (FxPQ + GZip), UVeQFed (Shlezinger et al. 2020) and FP8. Federated QSGD (see section 3.3) is our most important baseline because outperforms the other algorithms. Fed- PAQ only applies fixed-point quantization, which is equivalent to Federated QSGD without lossless compression. Similarly, FxPQ + GZip is equivalent to Federated QSGD with Gzip for its lossless compression stages. UVeQFed generalizes scalar quantization to vector quantization, followed by arithmetic coding. We apply UVeQFed with the optimal hyperparameters reported by its authors. FP8 (Wang et al. (a) is a floating-poin quantizer that uses an 8-bit floating-poii -ponn format de- signed for storing neural network gradients. We also evaluate all experiments without compression to establish accuracy benchmark.
Hyperparameters With the exception of CelebA, all our datasets and models are also used by Li et al.] We therefore adopt most of the hyperparameters from Li et al. and use LEAF's hyperparame- ters for CelebA Caldas et al. (018). For all experiments, we sample 10 clients each round. We train Synthetic, FEMNIST and CelebA for 500 rounds each. We train Sent140 for 1000 rounds due to slow convergence and Shakespeare for 50 rounds due to rapid convergence. We use batch size 10, learning rates 0.01, 0.003, 0.3, 0.8, 0.1 and jas (FedProx's 's proximal term coefficient) 1, 1, 1, 0.001,
7

---

Under review as a conference paper at ICLR 2022
Synthetic
FEMNIST
Sent140
Uncompressed
78.3 = 0.3
12.2MB
77.7 0.04
GB
69.7 0.5
GB
Federated QSGD
-0.1
17x
+..
2809x
0.5
90x
FP8
+0.1 = 0.4
4.0x (0.23x)
-0.1
4.0% (0.00%)
0..
4.0% (0.04x)
FedPAQ (FXPQ)
14x (0.82 (0.37x)
4.5
(0.00%)
0.5
(0.01x)
FxPQ + GZáp
0.11 1 0.1
+0.6.1.0.2
1557 (0.55
-..0
71X (0.79x)
UVeQFed
+:
(0.03%)
0.5
12x
(0.00 x)
4.2
(0.16
DAdaQuant
-0.2 0.4
48X (2.81 x))
+0.7
4772X (1.70
-0.1
108X (1.19
DAdaQuantuar
-0.1
37x (2. x)))
0.2
4518x (1.6
0.61
93x (1.03
DAdaQuantares
-0.0
(1.51x) x)
0.4
3017X
+..1
(1.16%)
Shakespeare
Uncompreseed
49.9 0.3
267.0MB
9..4
12.6GB
Federated QSGD
-0.5 = 0.6
9.5x
0..1
648X
0.1
FedPAQ (FxPQ)
-0.5 + 0.6
3.2x (0.34
-0.1
6.4x (0.01
FxPQ GZip
+
9.3x x0.97
-..1
494x (0.76x)
UVeQFed
-0.0 0.1
7.9x (0.83x)
0.3
31x (0.05 x)
DudaQuant
0.6 0.5
21X
-..1
775X (1.20 x)
DAdaQuantume
-0.5 0.5
(1.29x)
0.2
716x (1.10%)
DAdaQuantatens
-0.4 0.5
16x (1.67
-0.1 -..0
700x (1.08
Table 1: Top-1 test accuracies and total client-ssere communication of all baselines, DAdaQuant, DAdaQuantime and DAdaQuant<tient Entry x + y px (q x denotes an accuracy difference of x% the uncompressed accuracy with standard deviation of y%, compression factor of p w.r.t. the uncompressed communication and compression factor of w.r.t. Federated QSGD.
for Synthetic, FEMNIST, Sent140, Shakespeare, CelebA respectively. We randomly split the local datasets into 80% training set and 20% test set.
To select the quantization level q for static quantization with Federated QSGD, FedPAQ and FxPQ GZip, run gridsearch over q 1, 8, and choose for each dataset the lowest q for which Federated QSGD excceds uncompressed training in accuracy. We set UVeQFed's "coding rate" hyperparameter R 4, which is the lowest value for which UVeQFed achieves negligible accuracy differences compared to uncompressed training. We set the remaining hyperparameters of UVeQFed the optimal values reported by its authors. Appendix [A.4 shows further experiments that compare against UVeQFed with R chosen to maximize its compression factor.
For DAdaQuant's time-adaptive quantization, we set té to 0.9, é to 1/10"h of the number of rounds and 9max the quantization level q for each experiment. For Synthetic and FEMNIST, we set Qmin to 1. We find that Sent140, Shakespeare and CelebA require a high quantization level to achieve top accuracies and/or converge in few rounds. This prevents time-adaptive quantization from increasing the quantization level quickly enough, resulting in prolonged low-precision training that hurts model performance. To counter this effect, we set Jmin to 9max/2 2. This effectively results in binary time- adaptive quantization with an initial low-precision phase with 9max/ /2, followed by high- precision phase with Imax-
4.2 RESULTS
We repeat the main experiments three times and report average results and their standard deviation (where applicable). Table [ shows the highest accuracy and total communication for each experi- ment. Figure plots the maximum accuracy achieved for any given amount of communication.
Baselines Table shows that the accuracy of most experiments lies within the margin of error of the uncompressed experiments. This reiterates the viability of quantization-base compression algorithms for communication reduction in FL. For all experiments. Federated QSGD achieves a significantly higher compression factor than the other baselines. The authors of FedPAQ and UVe- QFed also compare their methods against QSGD and report them as superior. However, FedPAQ is compared against "unfederated" QSGD that communicates gradients after each local training step and UVeQFed is compared against QSGD without its lossless compression stages.
Time-adaptive quantization The purely time-adaptive version of DAdaQuant, DAdaQuantumee universally outperforms Federated QSGD and the other baselines in Table [ achieving comparable accuracies while lowering communication costs. DAdaQuantime performs particularly well on Syn-
8

---

Under review as a conference paper at ICLR 2022
Synthetic
FEMNIST
Sent 40
80
Accuracy in 1%%
Accuracy in
60
Accuracy in
60
40
25
20
50
0.4
0.6
0
200
400
Communication Megabytes
Communication in Megahytes
Communication Megabytes
Federated QSGD
DAdaQuant
Figure Communication-acccraag trade-off curves for training on FEMNIST with Federated QSGD and DAdaQuant. We plot the average highest accuracies achieved up to any given amount client- +servrr communication. Appendix A.3 shows curves for all datasets, as well as DAdaQuantime and DAdaQuantçiiesss with similar results.
thetic and FEMNIST, where it starts from the lowest possible quantization level = 1. However, binary time-adaptive quantization still measurably improves over QSGD for Sent140, Shakespeare and Celeba.
provides empirical evidence that AdaQuantFL's communication scales linearly with the number of clients. As a result. AdaQuantFL is prohibitively expensive for datasets with thousands of clients such Celeba and Sent140. DAdaQuant does not face this problem because its communication is unaffected by the number of clients.
Figure [ in Appendix A.5
Client-adaptive quantization The purely time-adaptive version of DAdaQuant, DAdaQuant,tiettss also universally outperforms Federated QSGD and the other baselines in Table T achieving similar accuracies while lowering communication costs. Unsurprisingly, the performance of DAdaQuantyiiess is correlated with the coefficient of variation = - of the numbers of samples in the local datasets with mean and standard deviation a:: Synthetic (c,, = 3.3) and Shakespeare
(c, = 1.7) achieve significantly higher compression factors than Sent140 (c,, = 0.3), FEMNIST (c, = 0.4) and Celeba (c,, = 0.3).
DAdaQuant DAdaQuant outperforms DAdaQuantame and DAdaQuanteieen: in communication while achieving similar accuracies. The compression factors of DAdaQuant are roughly multi- plicative in those of DAdaQuantgiiosss and DAdaQuantgime-- This demonstrates that we can effectively combine time- and client-adaptive quantization for maximal communication savings. Figur that DAdaQuant achieves higher accuracy than the strongest baseline, Federated QSGD, for any fixed amount of client- communication.
5 CONCLUSION
We introduced DAdaQuant as a computationally efficient and robust algorithm to boost the per- formance of quantization-base FL compression algorithms. We showed intuitively and mathe- matically how DAdaQuant's dynamic adjustment of the quantization level across time and clients minimize client-vserver communication while maintaining convergence speed. Our experiments establish DAdaQuant as nearly universally superior over static quantizers, achieving state-of-the of-the-art compression factors when applied to Federated QSGD. The communication savings of DAdaQuant effectively lower FL bandwidth usage, energy consumption and training time. Future work may apply and adapt DAdaQuant to new quantizers, further pushing the state the art in FL uplink compression.
REPRODUCIBILITY STATEMENT
Our submission includes repository with the source code for DAdaQuant and for the experiments presented in this paper. All the datasets used in our experiments are publicly available. Any post- processing steps of the datasets described in Appendix A.T. To facilitate the reproduction of

---

Under review as a conference paper at ICLR 2022
results, we have bundled all our source code, dependencies and datasets into Docker image. The repository submitted with this paper contains instructions on how to use this Docker image and reproduce all plots and tables in this paper.
ETHICS STATEMENT
FL trains models private client datasets in a privacy-preserving manner. However, FL does completely climinate privacy concerns, because the transmitted model updates and the learned model parameters may expose the private client data from which they are derived. Our work does not directly target privacy concerns in FL. With that said, it is worth noting that DAdaQuant does not expose any client data that not already exposed through standard FL training algorithms. fact, DAdaQuant reduces the amount of exposed data through lossy compression of the model updates. We therefore believe that DAdaQuant is free of ethical complications.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li. Ryota Tomioka, and Milan Vojnovic. QSGD:
Communication-efficeenn SGD via gradient quantization and encoding. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances Neural Information Processing Systems 30, pp. 1709-1720. Curran Associates, Inc., 2017. URL http:://pperr.nnps.c/ppprrr////p qsgd
httpp///ww.e007ooooooooooooooooa connunication
Mohammad Mohammadi Amiri, Deniz Gunduz, Sanjeev R. Kulkarni, and H. Vincent Poor. Feder- ated learning with quantized global model updates. arXiv:2006.1067,, 2020.
Ron Banner, Itay Hubara, Elad Hoffer, and Daniel Soudry. Scalable methods for 8-bit training of neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 5151-5155 2018.
Daniel J. Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Titouan Parcollet, and Nicholas D. Lane. Flower: A friendly Federated Learning research framework. arXiv:2007.14390 2020.
Nader Bouacida, Jiahui Hou, Hui Zang, and Xin Liu. Adaptive Federated Dropout: Improving communication efficiency and generalization for federated learning. In IEEE INFOCOM 2021- IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 1-6.
IEEE, 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Vosss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran As- sociates, Inc., 2020. URL httpppp:/pproceeeiigg....ee 745700888fc001777771111111111112
ps.cc/ pss.c//paper2222//111.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings.
arXiv:1812.01097, 2018
Bokai Cao, Lei Zheng, Chenwei Zhang, Philip S Yu, Andrea Piscitello, John Zulueta, Olu Ajilore, Kelly Ryan, and Alex D Leow. DeepMood: modeling mobile phone typing dynamics for mood detection. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 747-755, 2017.
Yonggan Fu, Haoran You, Yang Zhao, Yue Wang, Chaojian Li, Kailash Gopalakrishnan, Zhangyang Wang, and Yingyan Lin. FracTrain: Fractionally squeezing bit savings both temporally and
10

---

Under review as a conference paper at ICLR 2022
spatially for efficient DNN training. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 12127-12139. Curran Associates, Inc., 2020. http:tt:: http:///wwcccceeeeeeeeeeoe...o.e
Suyog Gupta, Ankur Agrawal. Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In International conference on machine learning, pp. 1737-1746.
PMLR, 2015.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint 1rXx:::904.00115. 2019.
Divyansh Jhunjhunwala, Advait Gadhikar, Gauri Joshi, and Yonina C Eldar. Adaptive quantization of model updates for communication-efficcenn federated learning. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3110-3114. IEEE, 2021.
Yuang Jiang, Shiqiang Wang, Bong Jun Ko, Wei-Han Lee, and Leandros Tassiulas. Model pruning enables efficient Federated Learning on edge devices. arXiv:1909, 19t.:199...2366,, 2019.
Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training quantized nets: A deeper understanding. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 5813-5823, 2017.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization heterogeneous networks. arXiv:1812.06111 2018.
Amirhossein Malekijoo, Mohammad Javad Fadaeieslam, Hanieh Malekijou, Morteza Homayounfar, and Reza Rawassizadeh. FEDZIP: A compression framework for communicationn-efiiicell Federated Learning. arXiv:2102.01599, 2021.
Farshid
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--fficcen learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Hung T Nguyen, Vikash Sehwag, Seyyedali Hosseinalipour, Christopher G Brinton, Mung Chiang, and Vincent Poor. Fast-convergent federated learning. IEEE Journal on Selected Areas in Communications, (9(1):001-218, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buce E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Cur- ran Associates, Inc., 2019. http:///////////peaeaaaa/a/e//a. aan-imperatin wwwppeeratiee-tttteee
Xinchi Qiu, Titouan Parcolle, Daniel Beutel, Taner Topa, Akhil Mathur, and Nicholas D Lane. A first look into the carbon footprint federated learning. arXiv preprint arXiv:2010.06537, 2020.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. FedPAQ: A communication-efficeenn Federated Learning method with periodic averaging and quantization. 1.Xiv:1909.130144 2019.
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica. Vladimir Braverman, Joseph Gonzalez, and Raman Arora. FetchSGD: Communication-efficienn federated learning with sketching. In International Conference Machine Learning, pp. 8253-8265. PMLR, 2020.
Jianghao Shen, Yue Wang, Pengfei Xu, Yonggan Fu, Zhangyang Wang, and Yingyan Lin. Fractional skipping: Towards finer-grained dynamic CNN inference. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 5700-5708, 2020.
11

---

Under review as a conference paper at ICLR 2022
Weisong Shi and Schahram Dustdar. The promise of edge computing. Computer, 49(5):78-81, 2016.
Nir Shlezinger, Mingzhe Chen, Yonina C Eldar, H Vincent Poor, and Shuguang Cui. UVeQFed: Universal vector quantization for federated learning. IEEE Transactions Signal Processing, 69:500-514, 2020.
Speedtest. Speedtest global index. httpgs//ww...aedd.sss.eee/...g.d cessed: 2021-05-12.
Ac-
Xiao Sun, Jungwook Choi, Chia- Yu Chen, Naigang Wang, Swagath Venkataramani, Vijayalakshmi Srinivasan, Xiaodong Cui, Wei Zhang, and Kailash Gopalakrishnan. Hybrid 8-bit floating point (HFP8) training and inference for deep neural networks. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pp- 4900 4909, 2019.
Paul Voigt and Axel Von dem Bussche. The EU general data protection regulation (GDPR). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10:3152676, 2017.
Naigang Wang, Jungwook Choi, Daniel Brand, Chia-Yu Chen, and Kailash Gopalakrish- nan. Training deep neural networks with 8-bit floating point numbers. In S. Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems 31, pp. 7675-7684. Curran Associates, Inc., 2018a. URL http:////pppccaacccce///e//ee/ee
Pan Wang, Feng Ye, and Xuejiao Chen. A smart home gateway platform for data collection and awareness. IEEE Communications magazine, 56(9):77-93, 2018b.
12

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL SIMULATION DETAILS AND EXPERIMENTS
A.1 ADDITIONAL SIMULATION DETAILS
Here, we give detailed information on the models, datasets, training objectives and implementation that we use for experiments. We set the five following FL tasks:
Multinomial logistic regression (MLR) on synthetic dataset called Synthetic that contains tors in IR:00 with a label of one out of 10 classes. We use the synthetic dataset generator in Li et al. (2018) to generate synthetic datasets. The generator samples Synthetic's local datasets and labels from MLR models with randomly initialized parameters. For this purpose, parameters and [ control different kinds of data heterogeneity. a controls the variation in the local models from which the local dataset labels are generated. / controls the variation in the local dataset samples. We set a and B 1 to simulate an FL setting with both kinds of data heterogeneity. This makes Synthetic useful testbed for FL.
Character classification into 62 classes of handwwitten characters from the FEMNIST dataset using CNN. FEMNIST groups samples from the same author into the same local dataset.
Smile detection in facial images from the CelebA dataset using CNN. CelebA groups samples of the same person into the same local dataset. We note that LEAF's CNN for CelebA uses BatchNorm layers. We replace them with LayerNorm layers because they are more amenable to quantization. This change does not affect the final accuracy.
Binary sentiment analysis of tweets from the Sent140 dataset using an LSTM. Sent140 groups tweets from the same user into the same local dataset. The majority of local datasets in the raw Sent140 dataset only have single sample. This impedes FL convergence. Therefore, we filter Sent140 to clients with at least 10 samples (i.e. one complete batch). Caldas al. (2018 (2018) similarly filter Sent140 for their FL. experiments.
al.
Next character prediction on text snippets from the Shakespeare dataset of Shakespeare's collected plays using an LSTM. Shakespeare groups lines from the same character into the same local dataset.
Table provides statistics of our models and datasets.
For experiments in Figure 8 AdaQuantFL requires hyperparameter that determines the initial quantization level. We set 8 to 2, the optimal value reported by the authors of AdaQuantFL.. The remaining hyperparameters are identical those used for the Synthetic dataset experiments in Table
We implement the models with PyTorch Paazke al. 2019) and use Flower (Beutel et al. 2020
simulate the FL server and clients.
Dataset
Model
Parameters
Clients
Samples
Samples per client
min
stddev
Synthetic
MLR
610
30
9,600
320.0
45
5,953
1051.6
FEMNIST
2-layer CNN
6.6 10
3,500
785,582
224.1
19
584
87.8
CelebA
4-layer CNN
6.3 x 10
9,343
200,288
21.4
35
7.6
Sent140
2-layer LSTM
1.1 x 10"
21,876
430,707
51.1
10
549
17.1
Shakespeare
2-layer LSTM
1.3 x 10
1,129
4,226,158
3743
66,903
6212
Table 2: Statistics of the models and datasets used for evaluation. Logistic Regression".
MLR stands for "Multinomial
A.2
COMPUTATIONAL OVERHEAD OF DADAQUANT
Training DAdaQuantime
DAdaQuantt
Federated QSGD
Total overhead 0.41 (1.14%)
36 s
<1 ms (0.00%) 0.17 s (0.47%)
0.24 (0.67%)
Table 3: Execution time measurements for different stages of FL training round on FEMNIST with DAdaQuant. Each entry contains the execution time in seconds and as a fraction the normal training time. The total overhead of DAdaQuant, including Federated QSGD, is =s 1%.
13

---

Under review as a conference paper at ICLR 2022
A.3
COMPLETE COMMUNICATION-ACCURAA TRADE-OFF CURVES
Synthetic
FEMNIST
Sent
Accuracy in 55.
Accuracy in %..
160
50
20
0.0
0.2
0.4
0.6
20
40
200
400
Communication in Megabytes Shakespeare
Communication in Megabytes
Communication in Megabytes
Celeha
Federated QSGD
Accuracy in S.
DAdaQuant
60
10
20
Communication Megabytes
Communication Megabytes
Figure 5: Communication accuraay trade-off curves for Federated QSGD and DAdaQuant. We plot the average highest accuracies achieved up any given amount of communication.
Synthetic
FEMNIST
Scnt140
80
Accuracy in f6.
60
50
Accuracy in
20
50
0.0
0.2
0.4
0.6
20
40
200
400
Communication in Megabytes
Communication in Megahytes
Communication in Megahytes
Shakespeare
Celeba
Federated QSGD
Accuracy in St.
40
DAdaQuanteiooe
Accuracy
20
60
10
20
10
20
Communication Megabyles
Communication
Megahyles
Figure 6: Communication- Communication-ccarayy accuracy trade-off curves for Federated QSGD and DAdaQuant;ime. We plot the average highest accuracies achieved up any given amount of communication.
14

---

Under review as a conference paper at ICLR 2022
Synthetic
FEMNIST
Sent140
80
Accuracy in f8.
Accuracy in %.
(60
50
20
50
0.0
0.2
0.44
0.6
20
40
0
200
400
Communication in Megabyles
Communicatton in Megahyles
Communication in Megahytes
Shakespeare
Celeba
Federated QSGD
Accuracy in S.
40
DAdaQuanteteens
Accuracy
20
80
10
20
10
201
Communication Megabytes
Commonicationn
Megabyles
Figure 7: Communication-accunaa trade-off curves for Federated QSGD and DAdaQuant We plot the average highest accuracies achieved up any given amount of communication.
A.4 ADDITIONAL UVEQFED EXPERIMENTS
To demonstrate that the choice of UVeQFed's "coding rate" hyperparameter R does not affect our findings on the superior compression factors DAdaQuant, we re-evaluate UVeQFed with 1, which maximizes UVeQFed's compression factor. Our results in Table show that with the exception of Shakespeare, DAdaQuant still achieves considerably higher compression factors than UVeQFed.
Synthetic
FEMNIST
Sent140 43
Shakespeare
Celeba
Uncompressed
1B
132.1 GB
267.0MB
12.6GR
QSGD
17x
2809
90x
9.5x
648x
UVeQFed (R=4)
0.6% (0.03
(0.00
15x (0.16 x)
7.9x (0.83
31x (0.05
UVeQFed (R=1)
13x (0.77 x)
34x (0.01 x))
41x (0.45
21x (2. (2:22 22 xx)
93x (0.14x)
DAdaQuant
(1.19x)
(1.20
Table 4: Comparison of the compression factors of DAdaQuant, UVeQFed with R (default value used for our experiments in Table [ and UVeQFed with R 1 (maximizes UVeQFed's compression factor). Entry x (q x) denotes a compression factor of p w.r.t. the uncompressed communication and compression factor of w.r.t. Federated QSGD.
15

---

Under review as a conference paper at ICLR 2022
A.5
ADDITIONAL ADAQUANTFL EXPERIMENTS
Communication Kilobytes
AdaQuantFL
20
DAdaQuant
0.6
Accuracy
AdaQuantFL
0.2
DAdaQuant
0-
10
100
200
400
200
400
Number of clients
Training round
(a) Comparison of the per-round-commumication for AdaQuantFL and DAdaQuant. We plot the average client sserver communication per round that re- quired to train MLR model on synthetic datasets with 10, 100, 200 and 400 clients. AdaQuantFL's communication incrcases linearly with the number of clients because trains the model on all clients at each round. In contrast, DAdaQuant's communica- tion does not change with the number of clients.
(b) Comparison of the convergence speed for AdaQuantFL DAdaQuant. We plot the test ac- curacy while training on a synthetic dataset with 100 clients. Although AdaQuantFL, has full client partic- ipation each round, it converges only slightly faster than DAdaQuant and achieves similar top accu- racy. This means that AdaQuantFL's linear increase in communication is not offset by proportional re- duction in training rounds.
Figure 8: Scalability of AdaQuantFL vs. DAdaQuant.
In principle, AdaQuantFL could be adapted to work with partial client participation by comput- ing an estimate of the global loss from the sampled subset of clients. While full evaluation of this approach is out of the scope of this paper, we conduct a brief feasibility study on FEMNIST. Concretely, we find that a single run of AdaQuantFL with partial client participation on FEMNIST achieved an accuracy of 78.7%. with total client->serve communication of 50.5 MB. In contrast, the same run with DAdaQuanteime similarly achieved an accuracy of 78.4 4%, while lowering the total client->ee server communication to 27.5 MB.
B PROOFS
Lemma 1. Take arbitrary quantization level 9s E and parameter P4 E [-t,t]. Then, au (pi) an unbiased estimator of Pt.
Proof. Let 8;
1. rem (pi, 81) and u; = 8; by Then, we have
"8-
E. Qq. (p:) pi]
Ui (pi b.) + by (p. + u.)
see Figure 9
8;
8;
Pi
Lemma 2. For arbitrary > O and parameter E [-t,t], let 8; = b, = rem (ps, 8;) and
u4 = ---b,. by. Then, Var (p.) u.b
Proof.
Var (Q,, (p:))
((.. [Q (p:)))
[(a,, (p.) pt)²
see Lemmal
b, a + Wi b2
Figure
si
st
16

---

Under review as a conference paper at ICLR 2022
4,by
(u: bi)
8j
ugb:
P(cs;)
Mi
P((c+ 1)8;)
C3
Pi (c 1)s;
Figure 9: Illustration of the Bernoulli random variable Qg (p:)- 8; is the length of the quantization interval. Ps rounded up to (c + 1)8; with a probability proportional to its distance from cS;-
Lemma 3. Assume that parameters P1 ... P.P sampled from U [1[-t, f) for arbitrary t 0. Then, Pp...PK (Var(e(...xx) 1² R
wi
2i=1
Proof.
Epi-.px Px [Var(ep)]
K
1
1
Var Σ wilgg (pi) -P) dpıdp2.... dpx
2t
2t
2t
1
1
Var
Σ wilgg (pi) -D) dpidp2...du ... .pk
symmetry of Qg. (pt) w.r.t. negation
J
J
K
Σ
Wi Var (qn, (p:))
dpk
mutual independence of Qg (p:) Vi
th
i=1
Σ
wi Var (qn, (pi)) dpıdp2 ... dpk
exchangeability of finite sums and integrals
ta
K
n-1
wf Var (Qg. (p:)) dp:
1
1=1
K
Var (Qy, (pi)) dps
1
Σ
u,b; dpi
Lemma
K
8: u,b; dpi
Σ
w
qi
s s--periodicity of u, and b;
t
K
9 qi
(s: pi) dp:
J0
W 9:87
2 K
Lemma 4. Let Q be a fixed-point quantizer. Assume that parameters Pt ... Px are sampled from
[[ for arbitrary > 0. Then, ming ax Ep px [Var(egh...9x )] subject to Q = _k qi is
K
2/8
minimized by qi 5 , w
17

---

Under review as a conference paper at ICLR 2022
Proof. Define
f(g) Ep....p [Var(e
n g(q) =
Σ 1=1
qi
I (q) f()) >g(g) (Lagrangian)
Any (local) minimum 9 satisfies
V9
( =0
K
AV
9: 0
Σ
q:
Q
Lemma 3
1=1
1=1
K
Vi
n2
9: = Q
-3 g
K
Vi 1.. n.
W
A
=
Q
33
i=1
2/3
w
Vi = n. = Q
2/3
1=
w
B.1 PROOF OF THEOREM 1
Proof.
Using Lemma is straightforward to show that for any V, ming ... ΣK q subject to
2/3 for the unique C E R that satisfies Epp...p (ar(cg...d ..x))))))) V is minimized by q: Cw
Ep....pi [Var(e]) Var(eet
.. V.
Then, taking V Epp...p (Vr (e])] and C = / (see Theorem 1 we indeed get
Epp Pk [Var(egi...9)) )]
w
Lemmal 3
(Cw, 2/3
f
K
2/3
w
プラ=1 j==
K
K
2/3
2/3
1=1
12 K
w²
q2
1=1
E
Epp..px [Vr(ee])
lemma 3
18


Reviews:
[{"review_id": "XdOtliekifK", "reviewer": "Reviewer_eicQ", "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": "Strength:\n\n(1) A novel double quantization design\n\n(2) Communication overhead saving is promising\n\n\nWeakness\n\n**(1)  Computational overhead in quantization**\n\nThis paper proposes a double quantization strategy for efficient FL.  While the saving in the communication overhead is promising, there is little discussion on the extra computational overhead introduced by the algorithm. For instance: i) what is the complexity of performing the time-adaptive and  client-adaptive quantization algorithm, ii) how does the overall training time being affected if we use the proposed algorithm, iii) what is the ratio between the communication time saving and the total training time\n\n**(2)  Comparison with other communication efficient algorithms**\n\nThis paper compares with quantization baselines. How does the double quantization algorithm perform when we compare it with sketching-based FL methods?\n\n", "summary_of_the_paper": "This paper studies the federated learning problem with a focus on communication efficiency. The major contribution of this paper can be summarized as:\n\n(1) Propose a time-adaptive quantization algorithm that adjusts the quantization level\nas training progresses\n\n(2) Propose a client-adaptive quantization algorithm that assigns quantization level to individual clients", "summary_of_the_review": "This paper is well-organized with a clear presentation. However,  there exist concerns regarding the efficiency of the proposed algorithm\n \nThe authors are strongly encouraged to address these shortcomings by:\n\n(1) Benchmarking the total training time and the computational overhead in quantization\n\n(2) Comparison with other  communication efficient  FL strategies such as sketching\n\n\n", "strength_and_weaknesses": "", "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": "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": {}}, {"review_id": "X9FL-hUIBfE", "reviewer": "Reviewer_2tGb", "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": "The strengths:\n\n1, The paper develops a new communication-efficient quantized FL, Particularly, the client-adaptive quantization is the first time to be considered for FL algorithms. \n\n2,  The paper has done extensive experiments to show the improvement of proposed methods. \n\nThe weaknesses:\n\n1,  Some math notations used in this paper miss definitions. For example, the definition of  $E_{p_1, ..., p_K}[Var(Q_q(p))]$ is missing.\n\n2, The quantization $Q_q(p)$ used in this paper based on section 3.3 QUANTIZATION WITH FEDERATED QSGD is \"$Q_q(p)$ then returns the sign of p and jpj rounded to one of the endpoints\". This quantization is not an unbiased estimator of $p$, which is conflict with the claim on page 14. \n\n3, The paper introduces the expected variance of an accumulation of quantized parameter $E[Var(\\sum Q(p))]$ as a measure of the performance of quantized FL algorithm and tries to minimize it in Thereom 1. The authors should explain more why it is a good measure.  Why not give the theoretical analysis in the following logic line: convergence guarantee -> get rounds T, given $epsilon$ -> get computational complexity and communication cost?\n\n4, In algorithm 1, RunClient($c_k$) is missing between line 8 and line 9. \n", "summary_of_the_paper": "The paper tries to reduce the communication cost of the Federated Learning (FL) algorithms.  They introduce the doubly-adaptive quantization algorithm (DAdaQuant), which adopts two quantization techniques: 1, time-adaptive quantization; 2, client-adaptive quantization.  The empirical studies also show that DAdaQuant can improve client sever compression. ", "summary_of_the_review": "The paper proposes an interesting communication-efficient FL algorithm. However, the theoretical analysis is not convincing and the commonly used analyses, like communication cost via communication rounds, are missing. ", "strength_and_weaknesses": "", "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": "WJk4Baw31LU", "reviewer": "Reviewer_CKYb", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "### Strengths\n1. The proposed two adaptive quantization strategies are simple and easy to implement in practice. In the experiments, they exhibit better performance than static quantization schemes.\n2. The client-level adaptive quantization scheme is new and has not appeared in literature. The idea itself makes sense and the authors proposed a theory-grounded approach to make it work.\n\n### Weaknesses\nI think the \"time-adaptivity\" part in the paper is a bit improper. And the authors tend to oversell their contribution. The contribution in this part is kind of trivial compared to previous works.\n\n- In the introduction, the authors mentioned that \"we observe that early training rounds can use a lower q without affecting convergence\". But in fact, this observation was first made by previous literature, such as (Jhunjhunwala et al. ICASSP 2021). More generally, the intuition that one need more communication towards the end of training already appeared in two years ago in (Wang & Joshi, MLSys 2019, \"Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD\"). The way the authors wrote this part can make people think this paper find this idea, which is not. The authors are supposed to make it clear in introduction that \"previous literature observed that.. and we further improve their algorithms by overcoming/addressing..\"\n- The comparison of time-adaptive quantization schemes with previous work (Jhunjhunwala et al. ICASSP 2021) is unfair. Basically, (Jhunjhunwala et al. ICASSP 2021) let all clients to participate into each round of training because they consider the full participation FL. But the algorithm itself can be easily extended to the case where we only sample few clients at each round. One can simply replace the global loss by the average loss within the current subset. Compared to this work, the authors should demonstrate (1) moving average of the loss help; (2) a step-increase strategy is better than the strategy used in (Jhunjhunwala et al. ICASSP 2021); (3) the proposed strategy converges faster than any other static quantization schemes, as predicted in Figure 2.\n- Related to the above point, I feel the authors failed to demonstrate the effectiveness of the time-adaptive quantization methods. There are still many remaining questions. In their experiments, the authors do not show whether the moving average of loss help. The authors do not compare the results with previous works AdaQuantFL. The authors do not show the proposed scheme is faster than any other static quantization schemes, as predicted in Figure 2. Instead, they just fix one quantization level and report the final accuracy.\n- In addition, the authors claim Pareto optimality in their experiments. I don't agree with this. Although the proposed algorithm is better, why is it the optimal one? \n", "summary_of_the_paper": "This paper studies how to compress the local model changes in federated learning to save uplink communication costs. In particular, the authors found (1) adaptively increasing the number of quantization levels (2) adaptively assigning different quantization levels on different clients, can effectively outperform previous static quantization schemes. They evaluated the proposed algorithm on multiple federated learning datasets.", "summary_of_the_review": "In general, I think the client-adaptive quantization part is quite interesting and novel. But the time-adaptive quantization part is incomplete. The authors fail to demonstrate the effectiveness of their proposed method.", "strength_and_weaknesses": "", "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": "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": {}}, {"review_id": "JEjNwnpZCyQ", "reviewer": "Reviewer_d8ve", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper provides clear intuition behind the double adaptive quantization approach. The work also presents solid empirical studies by comparing with a series of baseline algorithms over multiple classical datasets. The work overall is well presented.\n\nMajor concerns and questions:\n1. For Theorem 1, what is the definition of $e^{p_1\\cdots p_K}_q$? How is the agent-specific quantization level $q_i$'s relates to the given quantization level $q$?\n2. For Figure 4, the authors comment that for DAdaQuant, the communication cost does not scale with the number of clients. The reviewer thinks that despite per iteration the communication cost does not increase, the overall number of training rounds will increase, which causes the total communication cost to grow, especially in a data heterogeneous case. Can the author comments on this?\n\nMinor questions:\n1. In section 3.5, the authors comment \"We observe that Ep1...pK [Var(Qq(p))] is a useful statistic of the quantization error\nbecause...\". The reviewer does not doubt the intuition. But is there any rigorous justification for this observation?\n2. Have the authors tried other orthogonal techniques combining with quantization to further improve the communication cost empirically?", "summary_of_the_paper": "The paper proposes a communication-efficient federated learning framework named DAdaQuant. It is a quantization-based FL compression algorithm, which chooses both time-adaptive and client-adaptive quantization levels to improve the communication efficiency of FL algorithms over previous quantization works. The work provides math intuition behind choosing the client-adaptive quantization level. The authors also show solid empirical studies over FL datasets and validate the superiority of the proposed approach in communication efficiency.", "summary_of_the_review": "The paper is lean towards empirical studies. So the reviewer does not judge from the theoretical contribution perspective. Overall, the paper well presents the intuition and the logic of the data-adaptive quantization approach. The empirical study part is well-rounded and the results are relatively solid. ", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

I apologize to the authors for insufficient discussion in the discussion period. Thanks for carefully responding to reviewers. Nevertheless, I have read the paper as well, and the situation is clear to me (even without further discussion). I will not summarize what the paper is about, but will instead mention some of the key issues.

1) The proposed idea is simple, and in fact, it has been known to me for a number of years. I did not think it was worth publishing. This on its own is not a reason for rejection, but I wanted to mention this anyway to convey the idea that I consider this work very incremental. 
2) The idea is not supported by any convergence theory. Hence, it remains a heuristic, which the authors admit. In such a case, the paper should be judged by its practical performance, novelty and efficacy of ideas, and the strength of the empirical results, rather than on the theory. However, these parts of the paper remain lacking compared to the standard one would expect from an ICLR paper. 
3) Several elements of the ideas behind this work existed in the literature already (e.g., adaptive quantization, time-varying quantization, ...). Reviewers have noticed this.
4) The authors compare to fixed / non-adaptive quantization strategies which have already been surpassed in subsequent work. Indeed, QSGD was developed 4 years ago. The quantizers of Horvath et al in the natural compression/natural dithering family have exponentially better variance for any given number of levels. This baseline, which does not use any adaptivity, should be better, I believe, to what the author propose. If not, a comparison is needed. 
5) FedAvg is not the theoretical nor practical SOTA method for the problem the authors are solving. Faster and more communication efficient methods exist. For example, method based on error feedback (e.g., the works of Stich, Koloskova and others), MARINA method (Gorbunov et al), SCAFFOLD (Karimireddy et al) and so on. All can be combined with quantization. 
6) The reviewer who assigned this paper score 8 was least confident. I did not find any comments in the review of this reviewer that would sufficiently justify the high score. The review was brief and not very informative to me as the AC. All other reviewers were inclined to reject the paper. 
7) There are issues in the mathematics - although the mathematics is simple and not the key of the paper. This needs to be thoroughly revised. Some answers were given in author response.
8) Why should expected variance be a good measure? Did you try to break this measure? That is, did you try to construct problems for which this measure would work worse than the worst case variance? 

Because of the above, and additional reasons mentioned in the reviewers, I have no other option but to reject the paper.

Area Chair
Decision: Reject