Year: 2021

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→server compression, outperforming the strongest non-adaptive baselines by up to 2.8×.

heading: 1 INTRODUCTION
text: Edge devices such as smartphones, remote sensors and smart home appliances generate massive amounts of data (Wang et al., 2018b; Cao et al., 2017; Shi & Dustdar, 2016). 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 et 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 to share with the server because of privacy concerns or law enforcement (Voigt & Von dem Bussche, 2017). The server wants to train a model on all local datasets. To this end, it initializes the model and sends it to a 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 neural network models often have millions or even billions (Brown et al., 2020) of parameters, which makes high communication costs a concern in FL. In fact, Qiu et al. (2020) suggest that communication between clients and server may account for over 70% of energy consumption in FL. Reducing communication in FL is an attractive area of research because it lowers bandwidth requirements, energy consumption and training time.
Communication in FL occurs in two phases: Sending parameters from the server to clients (downlink) 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 average global mobile upload bandwidth is currently less than one fourth of the download bandwidth (Speedtest). 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-
ent clients that is required for uplink communication (Amiri et al., 2020; Reisizadeh et al., 2019). For these reasons, we seek to compress uplink communication.
A large class of compression algorithms for FL apply some lossy quantizer Q, optionally followed by a lossless compression stage. Q usually provides a “quantization level” hyperparameter q to control the coarseness of quantization (e.g. the number of bins for fixed-point quantization). When q is kept constant during training, we speak of static quantization. When q changes, we speak of adaptive quantization. Adaptive quantization can exploit asymmetries in the FL framework to minimize communication. One such asymmetry lies in FL’s training time, where Jhunjhunwala et al. (2021) observed that early training rounds can use a lower q without affecting convergence. Figure 2 illustrates how time-adaptive quantization leverages this phenomenon to minimize communication. 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 1 illustrates how client-adaptive quantization can minimize the quantization error. Intuitively, FL clients with greater weighting should have a greater commu-
nication budget and our proposed client-adaptive quantization achieves this in a principled way. To this end, we introduce the expected variance of an accumulation of quantized parameters, E[Var( ∑ Q(p))], as a measure of the quantization error. Our client-adaptive quantization algorithm
then assigns clients minimal quantization levels, subject to a fixed E[Var( ∑
Q(p))]. This lowers the amount of data communicated from clients to the server, without increasing the quantization error.
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-art 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 are computationally efficient, empirically superior to existing algorithms, and compatible with arbitrary FL quantizers. Our client-adaptive quantization is provably optimal for stochastic fixed-point quantizers.
• 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 it against several competitive FL compression algorithms.

heading: 2 RELATED WORK
text: FL research has explored several approaches to reduce communication. We identify three general directions.
First, there is a growing interest of investigating FL algorithms that can converge in fewer rounds. FedAvg (McMahan et al., 2017) achieves this with prolonged local training, while FOLB (Nguyen et al., 2020) speeds up convergence through a more principled client sampling. Since communication is 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 to 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 submodels on clients.
Thirdly, it 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., 2020) or quantization (Reisizadeh et al., 2019; Shlezinger et al., 2020) to parameter updates, optionally followed by lossless compression. Our work applies to quantization-based compression algorithms. It is partially based on QSGD (Alistarh et al., 2017), which combines lossy fixed-point quantization with a lossless compression algorithm to compress gradients communicated in distributed training. DAdaQuant adapts QSGD into Federated QSGD, which works with Federated Learning. DAdaQuant also draws inspiration from FedPAQ (Reisizadeh et al., 2019), the first FL framework to use lossy compression based on model parameter update quantization. However, FedPAQ does not explore the advantages of 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 techniques, so they can be combined for further communication savings. For this paper, we limit the scope of empirical comparisons to quantization-based 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 are also several adaptive quantization algorithms for training neural networks in a non-distributed setting. Shen et al. (2020) use different quantization levels for different parameters of a neural network. FracTrain (Fu et al., 2020) introduced multi-dimensional adaptive quantization by developing time-adaptive quantization and combining it with parameter-adaptive quantization. However, FracTrain 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 compute 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-adaptive quantization overcomes this issue without compromising on the underlying FL communication. In addition, to the best of our knowledge, DAdaQuant is the first algorithm to use client-adaptive quantization.

heading: 3 THE DADAQUANT METHOD

heading: 3.1 FEDERATED LEARNING
text: Federated Learning assumes a client-server topology with a set C = {ci|i ∈ {1, 2...N}} of N clients that are connected to a single server. Each client ck has a local dataset Dk from the local data distribution Dk. Given a model M with parameters p, a loss function fp(d ∈ Dk) and the local loss Fk(p) =
1 |Dk| ∑ d∈Dk fp(d), FL seeks to minimize the global loss G(p) = ∑N k=1 |Dk|∑ l |Dl| Fk(p).

heading: 3.2 FEDERATED AVERAGING (FEDAVG)
text: DAdaQuant makes only minimal assumptions about the FL algorithm. Crucially, DAdaquant can complement FedAvg (McMahan et al., 2017), which is representative of a large class of FL algorithms.
FedAvg trains the model M over several rounds. In each round t, FedAvg sends the model parameters pt to a random subset St of K clients who then optimize their local objectives Fk(pt) and send the updated model parameters pkt+1 back to the server. The server accumulates all parameters into the new global model pt+1 = ∑ k∈St |Dk|∑ j |Dj |
pkt+1 and starts the next round. Algorithm 1 lists FedAvg in detail. For our experiments, we use the FedProx (Li et al., 2018) adaptation of FedAvg. FedProx improves the convergence of FedAvg by adding the proximal term µ2 ‖p k t+1 − pt‖2 to the local objective Fk(pkt+1) in Line 20 of Algorithm 1.

heading: 3.3 QUANTIZATION WITH FEDERATED QSGD
text: While DAdaQuant can be applied to any quantizer with a configurable quantization level, it is optimized for fixed-point quantization. We introduce Federated QSGD as a competitive stochastic fixed-point quantizer on top of which DAdaQuant is applied.
In general, stochastic fixed-point quantization uses a quantizer Qq with quantization level q that splits R≥0 and R≤0 into q intervals each. Qq(p) then returns the sign of p and |p| stochastically rounded to one of the endpoints of its encompassing interval. Qq(p) quantizes the vector p elementwise.
We design DAdaQuant’s quantization stage based on QSGD, an efficient fixed-point quantizer for state-of-the-art gradient compression. QSGD quantizes a vector p in three steps:
1. Quantize p as Qq( p ||p||2 ) into q bins in [0, 1], storing signs and ||p||2 separately. (lossy) 2. Encode the resulting integers with 0 run-length encoding. (lossless) 3. Encode the resulting integers with Elias ω coding. (lossless)
QSGD has been designed specifically for quantizing gradients. This makes it not directly applicable to parameter compression. To overcome this limitation, we apply difference coding to uplink compression, first introduced to FL by FedPAQ. Each client ck applies Qq to the parameter updates pkt+1 − pt (cf. Line 21 of Algorithm 1) and sends them to the server. The server keeps track of the previous parameters pt and accumulates the quantized parameter updates into the new parameters as pt+1 = pt + ∑ k∈St |Dk|∑ l |Dl| Qq(p k t+1 − pt) (cf. Line 11 of Algorithm 1). 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.

heading: 3.4 TIME-ADAPTIVE QUANTIZATION
text: Time-adaptive quantization uses a different quantization level qt for each round t of FL training. DAdaQuant chooses qt 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 in Figure 2). FracTrain is built on similar observations for non-distributed training. Therefore, we design DAdaQuant to mimic FracTrain in monotonically increasing qt as a function of t and using the training loss to inform increases in qt.
When q is too low, FL converges prematurely. Like FracTrain, DAdaQuant monitors the FL loss and increases q when it converges. Unlike FracTrain, there is no single centralized loss function to evaluate and unlike AdaQuantFL, we do not assume availability of global training loss G(pt). Instead, we estimate G(pt) as the average local loss Ĝt = ∑ k∈St |Dk|∑ l |Dl|
Fk(pt) where St is the set of clients sampled at round t. Since St typically consists of only a small fraction of all clients, Ĝt is a very noisy estimate of G(pt). This makes it unsuitable for convergence detection. Instead, DAdaQuant tracks a running average loss Ĝt = ψĜt−1 + (1− ψ)Ĝt. We initialize q1 = qmin for some qmin ∈ N. DAdaQuant determines training to converge whenever Ĝt ≥ Ĝt+1−φ for some φ ∈ N that specifies the number of rounds across which we compare Ĝ. On convergence, DAdaQuant sets qt = 2qt−1 and keeps the quantization level fixed for at least φ rounds to enable reductions in G to manifest in Ĝ. Eventually, the training loss converges regardless of the quantization level. To avoid unconstrained quantization increases on convergence, we limit the quantization level to qmax.
The following equation summarizes DAdaQuant’s time-adaptive quantization:
qt ←−  qmin t = 0
2qt−1 t > 0 and Ĝt−1 ≥ Ĝt−φ and t > φ and 2qt−1 < qmax and qt−1 = qt−φ qt−1 else

heading: 3.5 CLIENT-ADAPTIVE QUANTIZATION
text: FL algorithms typically accumulate each parameter pi over all clients into a weighted average p = ∑K i=1 wipi (see Algorithm 1). Quantized FL accumulates quantized parameters Qq(p) =∑K
i=1 wiQq(pi) where q is the quantization level. We define the quantization error e q p = |p− Qq(p)|.
We observe in our experiments that communication cost per client is roughly a linear function of Federated QSGD’s quantization level q. This means that the communication cost per round is proportional to Q = Kq. We call Q the communication budget and use it as a proxy measure of communication cost.
Client-adaptive quantization dynamically adjusts the quantization level of each client. This means that even within a single round, each client ck can be assigned a different quantization level qk. The previous definitions then generalize to Q = ∑K k=1 qk and Qq1...qK (p) = ∑K i=1 wiQqi(pi) and eq1...qKp = |p− Qq1...qK (p)|. Prior convergence results for distributed training and FL rely on an upper bound b on Var(Qq1...qK (p)) that determines the convergence speed Li et al. (2017); Horváth et al. (2019); Reisizadeh et al. (2019). This makes V(Qq1...qK (p)) a natural measure to optimize for when choosing qk.
We optimize for the closely related measure Ep1...pK [Var(Qq1...qK (p))] that replaces the upper bound with an expectation over parameters p1 . . . pK . Heuristically, we expect an this averaged measure to provide a better estimate of practically observed quantization errors than an upper bound. For a stochastic, unbiased fixed-point compressor like Federated QSGD, Ep1...−pK [Var(Qq1...qK (p))] equals Ep1...pK [Var(eqp)] and can be evaluated analytically.
We devise an algorithm that chooses qk to minimize Q subject to Ep1...pK [Var(eq1...qKp )] = Ep1...pK [Var(eqp)] for a given q. Thus, our algorithm effectively minimizes communication costs while maintaining a quantization error similar to static quantization. Theorem 1 provides us with an analytical formula for quantization levels q1 . . . qK .
Theorem 1. Given parameters p1 . . . pk ∼ U[−t, t] and quantization level q, minq1...qK ∑K i=1 qi
subject to Ep1...pK [Var(eq1...qKp )] = Ep1...pK [Var(eqp)] is minimized by qi = √ a b × w 2/3 i where
a = ∑K j=1 w 2/3 j and b = ∑K j=1 w2j q2 .
DAdaQuant applies Theorem 1 to lower communication costs while maintaining the same loss as static quantization does with a fixed q. To ensure that quantization levels are natural numbers, DAdaQuant approximates the optimal real-valued solution as qi = max(1, round( √ a b × w 2/3 i )). Appendix B gives a detailed proof of Theorem 1. To the best of our knowledge, DAdaQuant is the first algorithm to use client-adaptive quantization.
Algorithm 1: The FedAvg and DAdaQuant algorithms. The uncolored lines list FedAvg. Adding the colored lines creates DAdaQuant. — quantization, — client-adaptive quantization, — time-adaptive quantization. 1 Function RunServer() 2 Initialize wi =
|Di|∑ j |Dj |
for all i ∈ [1, . . . , N ]; 3 for t = 0, . . . , T − 1 do 4 Choose St ⊂ C with |St| = K, including each ck ∈ C with uniform probability;
5 qt ←−  qmin t = 0
2qt−1 t > 0 and Ĝt−1 ≥ Ĝt−φ and t > φ and qt ≤ qmax and qt−1 = qt−φ qt−1 else ;
6 for ck ∈ St do in parallel 7 qkt ←− √∑K j=1 w 2/3 j / ∑K j=1 w2j q2 ; 8 Send(ck,pt,q k t ); 9 Receive(ck,p k t+1,Ĝ k t );
10 end 11 pt+1 ←− ∑ k∈St wkp k t+1;
12 Ĝt ←− ∑ k∈St wkĜ k t ;
13 Ĝt ←−
{ Ĝ0 t = 0
ψĜt−1 + (1− ψ)Ĝt else ;
14 end 15 end 16 Function RunClient(ck) 17 while True do 18 Receive(Server,pt, qkt );
19 Ĝkt ←− Fk(pt) ; 20 pkt+1 ←− Fk(pkt+1) trained with SGD for E epochs with learning rate η; 21 Send(Server, Qqkt (p k t+1) ,Ĝ k t ); 22 end 23 end

heading: 3.6 DOUBLY-ADAPTIVE QUANTIZATION (DADAQUANT)
text: DAdaQuant combines the time-adaptive and client-adaptive quantization algorithms described in the previous sections. At each round t, time-adaptive quantization determines a preliminary quantization level qt. Client-adaptive quantization then finds the client quantization levels qkt , k ∈ {1, . . . ,K} that minimize ∑K i=1 qi subject to Ep1...pK [Var(eq1...qKp )] = Ep1...pK [Var(eqp)]. Algorithm 1 lists DAdaQuant in detail. Figure 3 gives an example of how our time-adaptive, client-adaptive and doubly-adaptive quantization algorithms set quantization levels.
Reisizadeh et 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 convergence results extend to DAdaQuant when combined with any quantizer that satisfies (1) and (2) for DAdaQuant’s minimum quantization level q = 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̂t, 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 a weighted average of client parameters. Most FL algorithms, including FedAvg, follow this design.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL DETAILS
text: 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 linear model, CNNs and LSTMs of varying complexity on a 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 research. We refer to Appendix A.1 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 capabilities. 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′t ⊂ St of clients at each round t, where E′ is sampled from [1, . . . , E] and |S′t| = 0.9K. Baselines We compare DAdaQuant against competing quantization-based algorithms for FL parameter compression, namely Federated QSGD, FedPAQ (Reisizadeh et al., 2019), GZip with fixedpoint quantization (FxPQ + GZip), UVeQFed (Shlezinger et al., 2020) and FP8. Federated QSGD (see section 3.3) is our most important baseline because it outperforms the other algorithms. FedPAQ 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., 2018a) is a floating-point quantizer that uses an 8-bit floating-point format designed for storing neural network gradients. We also evaluate all experiments without compression to establish an 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 hyperparameters for CelebA Caldas et al. (2018). 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 µs (FedProx’s proximal term coefficient) 1, 1, 1, 0.001, 0
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, we run a gridsearch over q = 1, 2, 4, 8, . . . and choose for each dataset the lowest q for which Federated QSGD exceeds 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 to 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 ψ to 0.9, φ to 1/10th of the number of rounds and qmax to 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 qmin to qmax/2. This effectively results in binary timeadaptive quantization with an initial low-precision phase with q = qmax/2, followed by a highprecision phase with q = qmax.

heading: 4.2 RESULTS
text: We repeat the main experiments three times and report average results and their standard deviation (where applicable). Table 1 shows the highest accuracy and total communication for each experiment. Figure 4 plots the maximum accuracy achieved for any given amount of communication.
Baselines Table 1 shows that the accuracy of most experiments lies within the margin of error of the uncompressed experiments. This reiterates the viability of quantization-based 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 UVeQFed 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, DAdaQuanttime, universally outperforms Federated QSGD and the other baselines in Table 1, achieving comparable accuracies while lowering communication costs. DAdaQuanttime performs particularly well on Syn-
thetic and FEMNIST, where it starts from the lowest possible quantization level q = 1. However, binary time-adaptive quantization still measurably improves over QSGD for Sent140, Shakespeare and Celeba.
Figure 8 in Appendix A.5 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 as Celeba and Sent140. DAdaQuant does not face this problem because its communication is unaffected by the number of clients.
Client-adaptive quantization The purely time-adaptive version of DAdaQuant, DAdaQuantclients, also universally outperforms Federated QSGD and the other baselines in Table 1, achieving similar accuracies while lowering communication costs. Unsurprisingly, the performance of DAdaQuantclients is correlated with the coefficient of variation cv = σµ of the numbers of samples in the local datasets with mean µ and standard deviation σ: Synthetic (cv = 3.3) and Shakespeare (cv = 1.7) achieve significantly higher compression factors than Sent140 (cv = 0.3), FEMNIST (cv = 0.4) and Celeba (cv = 0.3).
DAdaQuant DAdaQuant outperforms DAdaQuanttime and DAdaQuantclients in communication while achieving similar accuracies. The compression factors of DAdaQuant are roughly multiplicative in those of DAdaQuantclients and DAdaQuanttime. This demonstrates that we can effectively combine time- and client-adaptive quantization for maximal communication savings. Figure 4 shows that DAdaQuant achieves a higher accuracy than the strongest baseline, Federated QSGD, for any fixed amount of client→server communication.

heading: 5 CONCLUSION
text: We introduced DAdaQuant as a computationally efficient and robust algorithm to boost the performance of quantization-based FL compression algorithms. We showed intuitively and mathematically how DAdaQuant’s dynamic adjustment of the quantization level across time and clients minimize client→server communication while maintaining convergence speed. Our experiments establish DAdaQuant as nearly universally superior over static quantizers, achieving state-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 of the art in FL uplink compression.

heading: 6 REPRODUCIBILITY STATEMENT
text: Our submission includes a 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 postprocessing steps of the datasets are described in Appendix A.1. To facilitate the reproduction of
our results, we have bundled all our source code, dependencies and datasets into a 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.

heading: 7 ETHICS STATEMENT
text: FL trains models on private client datasets in a privacy-preserving manner. However, FL does not completely eliminate 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 is not already exposed through standard FL training algorithms. In 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.

heading: A ADDITIONAL SIMULATION DETAILS AND EXPERIMENTS
text: A.1 ADDITIONAL SIMULATION DETAILS
Here, we give detailed information on the models, datasets, training objectives and implementation that we use for our experiments. We set the five following FL tasks:
• Multinomial logistic regression (MLR) on a synthetic dataset called Synthetic that contains vectors in R60 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. α 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 α = 1 and β = 1 to simulate an FL setting with both kinds of data heterogeneity. This makes Synthetic a useful testbed for FL. • Character classification into 62 classes of handwritten characters from the FEMNIST dataset using a CNN. FEMNIST groups samples from the same author into the same local dataset. • Smile detection in facial images from the CelebA dataset using a 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 a single sample. This impedes FL convergence. Therefore, we filter Sent140 to clients with at least 10 samples (i.e. one complete batch). Caldas et al. (2018); Li et al. (2018) similarly filter Sent140 for their FL experiments. • 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 2 provides statistics of our models and datasets.
For our experiments in Figure 8, AdaQuantFL requires a hyperparameter s that determines the initial quantization level. We set s to 2, the optimal value reported by the authors of AdaQuantFL. The remaining hyperparameters are identical to those used for the Synthetic dataset experiments in Table 1.
We implement the models with PyTorch (Paszke et al., 2019) and use Flower (Beutel et al., 2020) to simulate the FL server and clients.
A.2 COMPUTATIONAL OVERHEAD OF DADAQUANT
A.3 COMPLETE COMMUNICATION-ACCURACY TRADE-OFF CURVES
Synthetic
FEMNIST
Sent140
Synthetic
FEMNIST
Sent140
Synthetic
FEMNIST
Sent140
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 of DAdaQuant, we re-evaluate UVeQFed with R = 1, which maximizes UVeQFed’s compression factor. Our results in Table 4 show that with the exception of Shakespeare, DAdaQuant still achieves considerably higher compression factors than UVeQFed.
A.5 ADDITIONAL ADAQUANTFL EXPERIMENTS
In principle, AdaQuantFL could be adapted to work with partial client participation by computing an estimate of the global loss from the sampled subset of clients. While a 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 a total client→server communication of 50.5 MB. In contrast, the same run with DAdaQuanttime similarly achieved an accuracy of 78.4%, while lowering the total client→server communication to 27.5 MB.

heading: B PROOFS
text: Lemma 1. Take arbitrary quantization level qi ∈ N and parameter pi ∈ [−t, t]. Then, Qqi(pi) is an unbiased estimator of pi.
Proof. Let si = tqi , bi = rem (pi, si) and ui = si − bi. Then, we have E [ Qqi(pi)− pi ] =
ui si (pi − bi) + bi si (pi + ui) see Figure 9
= pi
Lemma 2. For arbitrary t > 0 and parameter pi ∈ [−t, t], let si = tqi , bi = rem (pi, si) and ui = si − bi. Then, Var ( Qqi(pi) ) = uibi.
Proof.
Var ( Qqi(pi) ) = E [( Qqi(pi)− E [ Qqi(pi)
])2] = E [( Qqi(pi)− pi )2] see Lemma 1
= bi si u2i + ui si b2i see Figure 9
Lemma 3. Assume that parameters p1 . . . pK are sampled from U[−t, t] for arbitrary t > 0. Then, Ep1...pK [Var(eq1...qKp )] = t 2
6 ∑K i=1 w2i q2i .
Proof. Ep1...pK [Var(ep)]
= 1
2t ∫ t −t 1 2t ∫ t −t . . . 1 2t ∫ t −t Var ( K∑ i=1 wiQqi(pi)− p ) dp1dp2 . . . dpK
= 1
t ∫ t 0 1 t ∫ t 0 . . . 1 t ∫ t 0 Var ( K∑ i=1 wiQqi(pi)− p ) dp1dp2 . . . dpK symmetry of Qqi(pi) w.r.t. negation
= 1
tn ∫ t 0 ∫ t 0 . . . ∫ t 0 K∑ i=1 w2iVar ( Qqi(pi) ) dp1dp2 . . . dpK mutual independence of
Qqi(pi) ∀i
= 1
tn K∑ i=1 ∫ t 0 ∫ t 0 . . . ∫ t 0 w2iVar ( Qqi(pi) ) dp1dp2 . . . dpK exchangeability of finite sums and integrals
= 1
tn K∑ i=1 tn−1 ∫ t 0 w2iVar ( Qqi(pi) ) dpi
= 1
t K∑ i=1 w2i ∫ t 0 Var ( Qqi(pi) ) dpi
= 1
t K∑ i=1 w2i ∫ t 0 uibi dpi Lemma 2
= 1
t K∑ i=1 w2i qi ∫ si 0 uibi dpi si-periodicity of ui and bi
= 1
t K∑ i=1 w2i qi ∫ si 0 (si − pi) pi dpi
= 1
6t K∑ i=1 w2i qis 3 i
= t2
6 K∑ i=1 w2i q2i
Lemma 4. Let Q be a fixed-point quantizer. Assume that parameters p1 . . . pK are sampled from U[−t, t] for arbitrary t > 0. Then, minq1...qK Ep1...pK [Var(eq1...qKp )] subject to Q = ∑K i=1 qi is
minimized by qi = Q w 2/3 i∑K
k=1 w 2/3 k
.
Proof. Define
f(q) = Ep1...pK [Var(eq1...qKp )]
g(q) = ( n∑ i=1 qi ) L(q) = f(q)− λg(q) (Lagrangian)
Any (local) minimum q̂ satisfies
∇L(q̂) = 0
⇐⇒ ∇ t 2
6 K∑ i=1 w2i q2i − λ∇ K∑ i=1 qi = 0 ∧ K∑ i=1 qi = Q Lemma 3
⇐⇒ ∀i = 1 . . . n. t 2 −3 w2i q3i = λ ∧ K∑ i=1 qi = Q
⇐⇒ ∀i = 1 . . . n. qi = 3 √ t2
−3λ w2i ∧ K∑ i=1 qi = Q
=⇒ ∀i = 1 . . . n. qi = Q w 2/3 i∑K
j=1 w 2/3 j
B.1 PROOF OF THEOREM 1 Proof. Using Lemma 4, it is straightforward to show that for any V , minq1...qK ∑K i=1 qi subject to Ep1...pK [Var(eq1...qKp )] = V is minimized by qi = Cw 2/3 i for the unique C ∈ R>0 that satisfies Ep1...pK [Var(eq1...qKp )] = V .
Then, taking V = Ep1...pK [Var(eqp)] and C = √ a b (see Theorem 1), we do indeed get
Ep1...pK [Var(eq1...qKp )]
= t2
6 K∑ i=1
w2i
(Cw 2/3 i )
2 Lemma 3
= 1 C2 t2 6 K∑ i=1 wi 2/3
=
∑K j=1
w2j q2∑K
j=1 w 2/3 j
t2
6 K∑ i=1 wi 2/3
= t2
6 K∑ j=1 w2j q2
= Ep1...pK [Var(eqp)] lemma 3

Review summaries:
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.

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.

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.