Compressive Differentially-Private Federated Learning Through Universal Vector
Quantization
Saba Amiri1 * , Adam Belloum1 , Sander Klous2 , Leon Gommans3
1

Multiscale Networked Systems (MNS) Research Group, University of Amsterdam, 1098 XH Amsterdam, The Netherlands
2Complex Cyber Infrastructure (CCI) Research Group, University of Amsterdam, 1098 XH Amsterdam, The Netherlands
3
Air France KLM{s.amiri,a.s.z.belloum,s.klous,leon.gommans}@uva.nl
Abstract
Collaborative and federated machine learning is an essential
vehicle for achieving privacy preserving machine learning.
By not forcing participants to share their private datasets,
we can adhere to strict local as well as international privacy protection legal regimes. However, a federated learning mechanism is usually hindered by the overhead communication costs between the central server and participants
when communication channels have constrained capacities.
Furthermore, just refraining from sharing the data will notlead us to absolute privacy, e.g. in presence of privacy attacks
such as membership inference. Differential Privacy has provided a set of rigorous privacy standards to protect individual
records of a dataset being used by a randomized mechanism.
As differential privacy has been widely accepted as the defacto privacy standard in machine learning, it could potentially mitigate privacy concerns. However, addition of differential privacy usually costs even more communication overhead, putting more pressure on uplink and downlink channels. In this work, we present a novel algorithm for achieving
both differential privacy and reduced communication overhead through compression of client-server communication bymeans of quantization. Not only we show acceptable levels ofdifferential privacy, we also show significant gains in termsof communication efficiency by compressing the data on theconstrained uplink channel.

1

Introduction

Traditional machine learning paradigms usually require forall training data to be accumulated in one place. Nowadays, this practice poses several challenges, two of themost important instances of which being constrained capacity of communication channels for data transfer and privacy concerns. Collaborative and federated learning mechanisms solve this problem by instead bringing the computation to the data, making the learning process distributed.
This negates the privacy-violating process of transferring
private datasets from participants to a central authority, butdoesn’t solve the privacy challenges completely.
Aside from a more complicated risk model by introducing communication channels and usually a central authority to the machine learning pipeline, this collaborative learn* Corresponding author.

Copyright © 2021, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

ing scheme too suffers from the communication overheadsimilar to that of centralized learning. The difference is, instead of the overhead related to communicating big datasets
once, the extra communication load is due to performing numerous rounds of training over a distributed setting. Smaller
packets of model parameter are sent on the uplink and downlink channels between participants and the parameter server
numerous times, making accumulative communication overhead high.
Regarding privacy aspects of federated machine learning,it has been shown that they can still leak critical information about their training dataset as well as the model parameters despite not forcing the participants to share theirprivate data (Song, Ristenpart, and Shmatikov 2017; Nasr,
Shokri, and Houmansadr 2018). Thus, we need to take additional measures to ensure the privacy of the training data ispreserved. In recent years, the de facto standard of privacy
for data access mechanisms has been Differential Privacy(Dwork, Roth et al. 2014) and its applications have been rigorously researched in machine learning (Abadi et al. 2016;
Chamikara et al. 2019). Differential Privacy could theoretically be achieved via perturbation as long as the boundsof the introduced perturbation are calculable. The main idea
behind this work stems from the necessity of compressing
communications between participants and central authority
and considering the inevitable transformation of communicated data as a form of perturbation. Thus with regards tothe previously defined general problems of federated learning, namely communication overhead and privacy and considering that , one can pose the research question ”Is is possible to use the perturbation resulting from compression ofcommunication in a federated learning scenario to achieve
Differential Privacy?”.
In this work, we investigate the above research questionand present a method for differentially private compression of the communicated parameters between participants
and the parameter server through compression. Using thismethod we can achieve not only more efficient communication, but also an effective level of privacy in local domain,i.e. sample level privacy.

1.1

Our Contribution• We design a novel method to achieve differential privacy
through quantization of the federated communications.

The novelty of this mechanism is to translate the perturbation by the compression method, namely universal latticequantization, into measurable Gaussian noise independentof the source distribution using dithering mechanism. To
the best of our knowledge, this is the first time the perturbation introduced by quantization has been employed as asource of noise to achieve differential privacy.
• We provide analysis of the quantization noise in different quantization schemes and connect their respective
noise models to that of specific differentially-private noise
adding mechanisms, making the connection between thetwo paradigms.
• We provide algorithms for compressive differentially private federated learning both to achieve local differential
privacy. We design experiments and report preliminary results, proving the system can achieve compression while
maintaining an acceptable level of privacy and utility.

2

Preliminaries

This section provides preliminaries and background information on federated learning, differential privacy, selectnoise-adding mechanisms for differential privacy and universal lattice vector quantization as well as the noise modelsof the quantization techniques.

2.1

Horizontal Federated Learning

Federated learning (FL) (McMahan et al. 2017) is a collaborative learning scheme for distributed training of machinelearning systems on multiple participants without them having to share their respective private datasets. In FL, the private datasets are accessed and processed locally, after whicha central Parameter Server (PS), usually acting as orchestrator and aggregator, gathers and combines the local updates
and returns the updated parameter set to the learning parties.
In the basic fusion algorithm proposed by McMahan et al.,namely Federated Stochastic Gradient Descent (FedSGD),
one step of gradient descent is done per learning round. Supposing N participants in total, in the first round the PS randomly generates the parameter set θ0 and communicates it
to all learning parties. Then at the round r ≥ 1 the ith participant Pi will perform one round of the training, computeits local gradients gi,r and send them back to the PS. After
receiving the parameters sets from M ≤ N participants, themechanism F on parameters server attempts to compute the
new weights, θr+1 , using the M parameter sets asF (g1,r , ..., gM,r ) = θr − ηMX

wi gi,ri=1where η is the PS learning rate and wi is the weight assigned
to each participant, e.g. the percentage of the samples they
are hosting.

2.2

Differential Privacy

Differential Privacy (DP) is a set of mathematical conditions
to provide plausible deniability to every single member of
the training set in the context of machine learning. Considering adjacent datasets D and D0 which differ in only one

element and the randomized mechanism M mapping the domain X to the range R, M : X → R, the mechanism M is(, δ)-differentially private if for all possible outputs S ⊆ R
P r[M (D) ∈ S] ≤ e [P r[M (D0 ) ∈ S] + δ.  (privacy budget) controls the trade-off of utility-privacyand δ allows for a small probability of failure for the privacy
preservation mechanism. Simply put, DP caps the increase
in information learned by changing a single element in thedataset.

2.3

Making Mechanism M Differentially Private

Methods used to make randomized mechanisms private usually involve some form of perturbation, e.g. noise addition.
Noise addition mechanisms are usually applied to the output
of query q. The amount of noise is controlled by the sensitivity of the q, defined as maximum change in the output of
q for any adjacent datasets D and D0 :Sq = max kq(D) − q(D0 )k.
(0, δ)-Differential Privacy with Uniform Noise Since the
distribution of the ideal universal quantization noise is uniform, in this section we study DP in presence of uniform
noise. According to (Geng and Viswanath 2015), in case of(0, δ)-DP, the optimal noise mechanism for Sq = 1 has auniform probability distributionδP(x) =

Sq

0

S

S

− 2δq ≤ x ≤ 2δqotherwise(1)

This result has been iterated in (Geng et al. 2019) as a
special case of truncated Laplacian mechanism.
For  ≥ 0, 0 ≤ δ ≤ 12 and Sq ≥ 0, when  → 0, it
will
to a uniform distribution with the support ofih be reducedSS− 2δq , 2δq and probability density of Sδq .
Analytical Gaussian Mechanism The Gaussian noise
adding mechanism introduced in (Dwork, Roth et al. 2014)
has a limitation on , namely 0 ≤  ≤ 1. (Zhao et al. 2019)show how this mechanism has been misused with  > 1,
leading to a loss of privacy. Balle and Wang in (Balle andWang 2018) define analytical Gaussian noise adding mechanism Z ∼ N (0, σ 2 I) and show it to be (, δ)-DP for any
SS ≥ 0, δ ∈ [0, 1] if and only if Φ( 2σq − Sσq ) − eσ Φ(− 2σq −σSq ) ≤ σ, with Φ being the Gaussian Comulative Distribution Function (CDF). They also provide a numerical algorithm to compute the optimal value of σ, which we willleverage to fine tune out quantization parameters.

2.4

Differential Privacy Domains

In a FL setting, the DP aspect of the mechanism, i.e. themachine learning algorithm, can be defined as either Global
or Local. Local Differential Privacy (LDP) in a FL setting isapplied on participant level. According to the definition of
LDP provided by (Bebensee 2019; Kasiviswanathan et al.

2011), a randomized mechanism M : X → R adheres to
LDP if for any x, x0 ∈ X and set of y ∈ R
P r[M (x) = y] ≤ e [P r[M (x0 ) = y] + δHere the output value y is perturbed using a DP mechanism.
Global Differential Privacy (GDP) in FL is applied on aggregation level, e.g. on PS. For the purpose of this work, themechanism F defined in 2.1 needs to adhere to DP conditions defined in Section 2.2. This ensures that all participant
parameter sets will be protected under DP assumptions.

3

Proposed Method

In this section we propose a (, δ)-differentially private compressive federated learning model to preserve local differential privacy. First, we provide two quantization schemes withsubtractive and non-subtractive dither. We provide analysis
of quantization noise for these methods. Next, we describe
our differentially private federated lea

3.1

Lattice Quantization and Its Noise Model

One of the challenges introduced by the FL paradigm isthe communication overhead between the participants andthe PS, especially in the presence of constrained uplink anddownlink channels. In this work we assume a constrained
capacity for the uplink channel. Therefore, optimizing thecommunication component of the FL scheme is crucial. The
desired optimization could be achieved through compressionof the data packages being sent to PS by participants.
In the following section we will introduce Lattice Vector Quantization method as a way to achieve data compression. We define Subtractive Dithered and Non-Subtractive
Dithered Universal Vector Quantization (SDUVQ, NSDUVQ respectively) and formalize them as randomized
quantization methods.
Universal Lattice Vector Quantization Universal Lattice
Vector Quantization (LVQ)(Gersho 1979) which comprisesof Quantization followed by a lossless coding scheme is
the most efficient entropy coded vector quantization method
when the quantization rate goes to infinity(Gray and Neuhoff
1998). Introducing subtractive dither to the LVQ makes it
universal(Zamir and Feder 1992), i.e. the quantization noisemechanism will be independent of the source distribution.
This type of quantization noise is called a Pseudo Quantization Noise model (PQN). In case of non-subtractive dither,it has been shown that the Gaussian dither essentially canbe modelled as PQN with quantization noise independentof input distribution if σ ≥ ∆2 . The two SDUVQ and NSDUVQ defined in this section are based on the uniform vector quantization scheme of (Dragotti and Gastpar 2009) witha simple lattice code design and introduction of dither. Each
scheme will have an encoding and a decoding path. The encoding happens at source, i.e. participant, to compress the
input data while the decoding happens at the destination toreconstruct the data.
~ . We define theConsider the N -dimensional vector w
quantization step size ∆ and lattice dimension L. The quantization parameters are known by both source and destination.

~ first we breakIn the encoding path, to quantize w
N
it
down
into
v
=
smaller
vectorsof the size LL
w0..L−1~ , wL..2L−1~, ..., w(v−1)L..vL−1~. For the sake ofsimplicity we assume N
L is an integer, but the scheme caneasily be modified by taking the d N
L e instead if this condition doesn’t hold true. Next, we will generate the vdimensional dither vector ~d = [d1 , d2 , ..., dv ] by generating in an i.i.d fashionv uniform random variables with the∆support − ∆2 , 2 . We can also generate Gaussian ditherwith µ = 0 and σ ≥ ∆2 . Generating dither from uniform noise ensures source distribution-independent quantization error(Zamir and Feder 1996) in case of subtractive dither. For non-subtractive dither, it has been shownthat the Gaussian dither comes extremely close to the PQN
model, rendering the quantization noise independent of thesource distribution and identified by the same Gaussian distribution(Widrow and Kollár 2008) (Chapter 19, Section
6.5). Next step would be applying the uniform quantization method of (Dragotti and Gastpar 2009) but before that,
we need to randomize the source vector using our generated
dither to compute w~d . To this end, each element of the dither
vector ~d will be added to the corresponding lattice cell, e.g.
w~di = {wiL + di , wiL+1 + di , .., wiL−1 + di }. Then, weapply the uniform quantization to each dithered lattice cell~d iw~di as w~q i = ∆round( w∆). In the last stage of the encoding path, as per (Zamir and Feder 1992), we will use alossless entropy source encoder to compress w~q . There are
a number of lossless source coding algorithms introducedin the literature. For the purpose of this work we chose thebzip2(Seward 1996) which uses the Burrows-Wheeler transformation(Kruse and Mukherjee 1999). Applying the bzip2~e and codealgorithm on w~q , we will end up with vector w
book C~ 0 we needIn the decoding path, to reconstruct the vector w~e using codebook C, resulting in vector w~q .
to decode the w
This will be the end of the encoding path for the NSDUVQ
scheme.
The SDUVQ goes through additional steps of dither subtraction. First, the vector w~q is divided into v lattice cells.
Next, using the shared source of randomness the random
vector ~d is reconstructed. Finally, the corresponding dither
values of ~d are subtracted from vector w~q leading to the~ 0.
reconstructed input vector w
The probability distribution of the noise of SDUVQ
scheme is completely independent of the input distribution(Zamir and Feder 1992) and can be defined as 1−∆ ≤ x ≤ ∆P(x) = 2∆(2)0otherwise
As mentioned earlier, the quantization noise of NSDUVQ
with Gaussian dither can essentially behave as a PQN model
when σ ≥ ∆2 , and we end up with a Gaussian noise pdf.

3.2

NSDUVQ-based Differentially Private
Federated Learning Mechanism

Algorithm 1 and algorithm 2 provide the federated learning
steps on participant and PS respectively for P participants.

We consider the case where the uplink from participant to
the PS is constrained while the downlink has enough capacity to handle the traffic efficiently, thus we only need toincrease efficiency in the uplink. The server is consideredhonest but curious and we need to maintain local differential
privacy on sample level. Since uniform noise of the subtractive dither is inefficient for differential privacy without significant loss of utility, we use non-subtractive dither methodwith Gaussian noise adding mechanism. The value of σ is
fixed at ∆2.

quantization noise to be Gaussian.
Fixing the values of , δ and ∆ and clipping the gradientsso that Sq = 1, we can then calculate the optimal value ofσ according to the numeric algorithm of analytical Gaussian
method (Balle and Wang 2018). Finally with the calculatedσ, we can define the lattice parameters and the noise scale
N of Algorithm 1 so that the quantization noise would be∼ N (0, σ 2 I). We use advanced composition theorem andprivacy magnification through Poisson subsampling on our
privacy bounds while calculating the system parameters.

Algorithm 1: Compressive (, δ)-DP Federated
Learning - Participant i, Round t > 1
Input: Training samples DiP= {x1i , ..., xN i }, loss
function L(θ) = N1i j L(θ, xij )Parameters: gradient norm bound Sq , group size G,
lattice vector size L, quantization step
size ∆, noise scale N
1 Receive parameter set θt ;L
2 Take a random sample Lt with probability N ;i
3 Choose subset Dt = {xj∈Lt } from Di using Poisson
subsampling function S po (.);
4 Compute gradient gt (Dt , θt );kgt k
5 Clip gradient ḡt ← gt /max(1, S 2 );q
6 Create Gaussian dither vector ~d by drawing Ni i.i.d

Algorithm 2: Compressive (, δ)-DP Federated
Learning - Parameter server (PS), Round t
Input: Encoded gradients of P participants{Barget1 , ..., BargetP } and codebooks{CBt1 , ..., CBtP }Parameters: PS learning rate η
1 Decode gradient vectors {Bargqt1 , ..., BargqtP }using codebooks {CBt1 , ..., CBtP } for P clients;
2 Descend and calculate new model parametersPPθt+1 = θt − η j=1 ḡqt j ;3 Send updated model parameters θt+1 to P clients forround t+1;

L

samples from N (0, σ 2 C 2 I) with σ = N ∆;N
7 Split ḡt into Li lattice vectors {ḡt1 , ..., ḡtL };8 Randomize lattice vector ḡtj = ḡtj + ~d(j);9 Quantize each lattice vectorḡtq j = ∆round(ḡtq j /∆);
10 Encode the concatenated quantized gradient vectorḡtq using universal source coding method bzip;
11 Send encoded gradient vector ḡet i and codebook
CBti to PS;
In round t = 1 the PS randomly initializes parameters set
θ0 and sends it to participants. We applying the quantization
after the calculation of the gradients using the quantizationnoise to achieve a certain level of differential privacy. The
descent on noisy gradients is performed by the PS.
To calculate the accumulative privacy costs over a total of T steps, first we need to fix the parameters of ournoise mechanism. Consider the ideal quantization schemeof SDUVQ, in which the noise is independent of the source
distribution and can be modelled as uniform noise. This will
be equivalent of achieving (0, δ)-DP. This special case is notdesirable for us, since it will lead to very low levels of privacy, e.g. considering Sq = 1, setting ∆ = 1/128 willlead to δ = 64. In NSDUVQ scheme, although the quantization noise can not be proven to be independent of thesource distribution, it is shown that for σ ≥ ∆2 it essentiallyfollows a PQN model and behaves independent of the input distribution and can be modeled by the Gaussian dither.
Furthermore, it is shown by Gariby and Erez (Gariby and
Erez 2008) that the lattice quantization noise can approach adesired distribution, e.g. Gaussian distribution, with correct
design of the lattice itself. We use this principle to shape the4
4.1

Experiments

Dataset and Experiment Design

We evaluate our method on EMNIST dataset. We simulatea FL setup with 10 participants. We experiment in severe
and mild non-i.i.d data distribution cases. In severe non-i.i.d
distribution, each participant only holds data related to one
writer. In the mild non-i.i.d case, each client hold data related to 50 authors. To manage the trade-off between privacy and utility, we fix the privacy budget  ≤ 10 and set
the quantization system setting so that we would achieve thelowest σ value possible. This process has a trade-off in itself in form of quantization accuracy which directly affects
the quantization noise while having an inverse effect on utility of the system in a fixed number of iterations. This also
affects the compression level achieved through the quantization process.

4.2

Results

We applied the experiments above on a simple model witha dense layer of the size 10. For  = 9.94, δ = 0.001,∆ = 1/64, L = 32, η = 0.01, T = 1000, G = 20,
P = 10, N = 74, σ = 1.15625 and with 4650 samples
per client, we report a sparse categorical accuracy of 92.2%
after T = 1000 iterations without early stopping, with thealgorithm converging around T = 650. The achieved average compression ratio over the 1000 iterations for all participants is 2.97.
Based on the early results we have of non-concluded experiments, the privacy level, utility and compression ratio
can certainly be massively improved by fine tuning the lattice, the quantization accuracy and the target privacy budget.
Also, by experimenting with different architectures, we areable to see varying levels of success, depending on the architecture of the network and the training data.

5

Discussion

In this work, we explored the possibility of achieving differential privacy in a federated learning setting through quantization. We have presented an end to end compressive federated protocol and provided an analysis of the quantizationnoise. We integrated the quantization scheme with the federated learning setup and were able to achieve both compression and differential privacy in our collaborative setup.
Although our experiments are still ongoing, early reported
results support our claim of privacy and compression.

6

Acknowledgments

This research has been performed as part of the Enabling
Personalized Intervention (EPI) project. The EPI projectis funded by the Dutch Science Foundation in the Commit2Data program (Grant Number: 628.011.028).

References
Abadi, M.; Chu, A.; Goodfellow, I.; McMahan, H. B.;
Mironov, I.; Talwar, K.; and Zhang, L. 2016. Deep learningwith differential privacy. In Proceedings of the 2016 ACM
SIGSAC Conference on Computer and Communications Security, 308–318.
Balle, B.; and Wang, Y.-X. 2018. Improving the gaussianmechanism for differential privacy: Analytical calibrationand optimal denoising. arXiv preprint arXiv:1805.06530 .
Bebensee, B. 2019. Local differential privacy: a tutorial.
arXiv preprint arXiv:1907.11908 .
Chamikara, M. A. P.; Bertok, P.; Khalil, I.; Liu, D.; Camtepe,S.; and Atiquzzaman, M. 2019. Local differential privacy fordeep learning. arXiv preprint arXiv:1908.02997 .
Dragotti, P. L.; and Gastpar, M. 2009. Distributed source
coding: theory, algorithms and applications. Academic
Press.
Dwork, C.; Roth, A.; et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in
Theoretical Computer Science 9(3-4): 211–407.
Gariby, T.; and Erez, U. 2008. On general lattice quantization noise. In 2008 IEEE International Symposium on Information Theory, 2717–2721. IEEE.
Geng, Q.; Ding, W.; Guo, R.; and Kumar, S. 2019. Optimalnoise-adding mechanism in additive differential privacy. In
The 22nd International Conference on Artificial Intelligenceand Statistics, 11–20. PMLR.
Geng, Q.; and Viswanath, P. 2015. Optimal noise adding
mechanisms for approximate differential privacy. IEEE
Transactions on Information Theory 62(2): 952–969.
Gersho, A. 1979. Asymptotically optimal block quantization. IEEE Transactions on information theory 25(4): 373–
380.
Gray, R. M.; and Neuhoff, D. L. 1998. Quantization. IEEE
transactions on information theory 44(6): 2325–2383.
Kasiviswanathan, S. P.; Lee, H. K.; Nissim, K.; Raskhodnikova, S.; and Smith, A. 2011. What can we learn privately?
SIAM Journal on Computing 40(3): 793–826.

Kruse, H.; and Mukherjee, A. 1999. Improving text compression ratios with the Burrows-Wheeler transform. In Proceedings DCC’99 Data Compression Conference (Cat. No.
PR00096), 536. IEEE.
McMahan, B.; Moore, E.; Ramage, D.; Hampson, S.; andy Arcas, B. A. 2017. Communication-efficient learning ofdeep networks from decentralized data. In Artificial Intelligence and Statistics, 1273–1282. PMLR.
Nasr, M.; Shokri, R.; and Houmansadr, A. 2018. Comprehensive privacy analysis of deep learning: Stand-alone andfederated learning under passive and active white-box inference attacks. arXiv preprint arXiv:1812.00910 .
Seward, J. 1996.
bzip2 and libbzip2.
avaliable at
http://www. bzip. org .
Song, C.; Ristenpart, T.; and Shmatikov, V. 2017. Machinelearning models that remember too much. In Proceedings ofthe 2017 ACM SIGSAC Conference on Computer and Communications Security, 587–601.
Widrow, B.; and Kollár, I. 2008. Quantization noise. Cambridge University Press 2: 5.
Zamir, R.; and Feder, M. 1992. On universal quantization byrandomized uniform/lattice quantizers. IEEE Transactions
on Information Theory 38(2): 428–436.
Zamir, R.; and Feder, M. 1996. On lattice quantizationnoise. IEEE Transactions on Information Theory 42(4):1152–1159.
Zhao, J.; Wang, T.; Bai, T.; Lam, K.-Y.; Ren, X.; Yang, X.;
Shi, S.; Liu, Y.; and Yu, H. 2019. Reviewing and improving the Gaussian mechanism for differential privacy. arXiv
preprint arXiv:1911.12060 .