Practical Locally Private Federated Learning with Communication Efficiency
Authors: Yan Feng
Tao Xiong
Ruofan Wu
Yuan Qi
Venue:  (2021)

Abstract: Federated learning (FL) is a technique that trains machine learning models from decentralized data sources. We study FL under local differential privacy constraints, which provides strong protection against sensitive data disclosures via obfuscating the data before leaving the client. We identify two major concerns in designing practical privacy-preserving FL algorithms: communication efficiency and high-dimensional compatibility. We then develop a gradient-based learning algorithm called \emph{sqSGD} (selective quantized stochastic gradient descent) that addresses both concerns. The proposed algorithm is based on a novel privacy-preserving quantization scheme that uses a constant number of bits per dimension per client. Then we improve the base algorithm in two ways: first, we apply a gradient subsampling strategy that offers simultaneously better training performance and smaller communication costs under a fixed privacy budget. Secondly, we utilize randomized rotation as a preprocessing step to reduce quantization error. We also initialize a discussion about the role of quantization and perturbation in FL algorithm design with privacy and communication constraints. Finally, the practicality of the proposed framework is demonstrated on benchmark datasets. Experiment results show that sqSGD successfully learns large models like LeNet and ResNet with local privacy constraints. In addition, with fixed privacy and communication level, the performance of sqSGD significantly dominates that of baseline algorithms.

Under review as a conference paper at ICLR 2021
PRACTICAL LOCALLY PRIVATE FEDERATED LEARN- ING WITH COMMUNICATION EFFICIENCY
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) is a technique that trains machine learning models from decentralized data sources. We study FL under local differential privacy constraints, which provides strong protection against sensitive data disclosures via obfuscating the data before leaving the client. We identify two major concerns in designing FL algorithms: communication efficiency and high- dimensional compatibility. We then develop a gradient-based learning algorithm called s4SGD (selective quantized stochastic gradient descent) that addresses both concerns. The proposed algorithm is based on novel privacy- privacy-preserving quantization scheme that uses a constant number bits per dimension per client, Then we improve the base algorithm in ways: first, we apply gradient subsampling strategy that offers simultaneously better training performance and smaller communication costs under fixed privacy budget. Secondly, we utilize randomized rotation as preprocessing step to reduce quantization error. We also initialize a discussion about the role of quantization and perturbation in FL algorithm design with privacy and communication constraints. Finally, the practicality of the proposed framework is demonstrated on benchmark datasets. Experiment results show that sqSGD successfully learns large models like LeNet and ResNet with local privacy constraints. In addition, with fixed privacy and communication level, the performance of sqSGD significantly dominates that of baseline algorithms.
practical
INTRODUCTION
1.1 BACKGROUND
Federated learning (FL) Kairouz al. (2019); Konečný et al. (2016) is rapidly evolving application of distributed optimization to large-scale learning or estimation scenarios where multiple entities. called clients, collaborate in solving machine learning problem, under the coordination of a central server. Each client's ' raw data is stored locally and not exchanged or transferred. To achieve the learning objective, the server collects minimal information from the clients for immediate aggregation. FL. is particularly suitable for mobile and edge device applications since the (sensitive) individual data never directly leave the device and has seen deployments in industries (?Hard al. 2019: Leroy et al.) 2019). While FL offers significant practical privacy improvements over centralizing all the training data, lacks a formal privacy guarantee. As discussed in Melis al. (2018), even if only model updates (i.e. gradient updates) are transmitted, it is easy to compromise the privacy of individual clients.
Differential privacy (DP) (Dwork et al. 2014) is the offte--f-thearrr approach to address informa- tion disclosure. Differentially private algorithms fuse participation of any individual via injecting algorithm-specific random noise. In FL. setting, DP is suitable for protecting against external adver- saries, i.e. a malicious analyst that tries to infer individual data via observing final or intermediate model results. However, DP paradigms typically assume a trusted curator, which corresponds to the server in the FL setting. This assumption often not satisfied in practical cases, under which users that act clients may not trust the service provider that acts as the server. Local differential privacy (LDP) (Kasiviswanathan et al., 201T Dwork et al., 2014) provides privacy protection on the individual level via applying randomized mechanisms that obfuscate the data before leaving the

---

Under review as a conference paper at ICLR 2021
client, and is more natural privacy model for distributed learning scenarios like FL, allowing easier compliance with regulatory strictures (Bhowmick et al. 2018
1.2 METHODOLOGY
We will be focusing on distributed learning procedures that aim to solve an empirical risk minimization problem in a decentralized fashion:
min L(O), L( DE0
Σ Lm (0)
(I)
N
where M denotes the number of clients. Let Y; denotes training data that belongs to the m-th client consisting Nm data points, and N Σm=1 Nm- The term (0) Eyey.. E(0, y) stands for locally aggregated loss evaluated at parameter 0, where é x
R+ is the loss function depending on the problem context and we use é and Y' to describe parameter and data domain respectively. We will seek to optimize (I via gradient- caasee methods. In what follows will use [n), E N to denote the set {1, (1, At round I, the procedure iterates as:
n...
1. Server distribute the current value 0, among a subset S of clients.
2. For each client E S, a local update computed A = g(0,, Y,) and transmitted to the server.
3. The server aggregates all {Ar)wess to obtain a global update A and updates the parameter 0.+1 0, A.
We distinguish 2 practical scenarios cross-silo FL and cross-device FL (Kairouz et al., 2019). In cross-silo FL, M is relatively small (i.e. M I 100 ) and usually each client has a moderate or large amount of data (i.e. minm Nm >> 1). As consequence, all the clients participate in the learning process (i.e. S = [M)- In each iteration a client computes locally a negative stochastic uniform random subsample RR C Y. of size R. cross-device FL S is a uniformly random subset of [M.] and g(Or, Y.) N. E yEY, Vi(d,. y) is the average negative gradient over Y, evaluated at 6, In this paper we will be focusing on the FedSgd aggregation rule corresponding to stochastic gradient step with N, learning rate 17. i... A = 17 E.es N g(0,, Y,). Generally speaking, there are two sources of data that need privacy protection: the parameter 0g and the updates {Ar) In this paper we will develop algorithms for protecting } against inference attack or reconstruction attack, which will be defined later. Note that the protection of 0&s could be done via applying standard central DP techniques as in inhohwwick et al. (2018). To begin our discussion suitably defined privacy models, we first review the local model of privacy.
gradient ((t,, Y,)
R yER, Ve(O,, y) of (0:)))/N,, based
Local differential privacy Kasiviswanathan et (2011) we say a randomized algorithm A that maps the private data X E X to some value Z = Al A()) E Z is e-locally differentially private, if the induced conditional probability measure P (.1X- x) satisfies that for any x,, x' E X and any Z 2:
P ( =
e
(Z =x) Se
In the FL setting, the private data X is typically not the raw data Y but the gradient of the loss function & evaluated at Y. Hereafter we will assume the private data to be a d dimensional euclidean vector, while d could be very large (i.e. to the order of millions). LDP is a very strong privacy protection model that protects individual data against inference attacks that aims at inferring the membership of arbitrary data from the data universe. According to the discussion in Bhowmick et al. (2018), allowing adversaries with such strength may be overly pessimistic: to conduct an effective inference attack the adversary shall come up with "the true data" and only use the privatized output to verify his/her belief about the membership. If the prior information is reasonably constrained for the adversary, we may adopt a weaker, but still elegant type of privacy protection paradigm that protects against reconstruction attacks. Heuristically, reconstruction attack aims at recovering individual data with respect to a well-defined criterion, given a prior over the data domain that is not too concentrated. Formally, adopt the definition in Bhowmick al. 20018:
2

---

Under review as a conference paper at ICLR 2021
Reconstruction attack Bhowmick et al. (2018) Let h be prior distribution over the data domain y that encodes the adversary's s prior belief. We describe the generation process of privatized user data Y - X + Z A(X) for some srrivacy-protecting
mechanism A. Additionally let
f: + Re be the target of reconstruction (i.e., the adversary wants to evaluate the value f(Y)) and Tree= R$ R& + 1 be the reconstruction loss serving as the criterion. Then estimator
{:X+ + R provides an P, (a, feeconsstrirtin breach for the loss Lrec if there exists some 2 E Z
such that:
PP (Lrec ([
= >
>
The existence of a reconstruction breach provides an attack that effectively breaks the privatized algorithm for some output Hence to provide protection against reconstruction attacks, we need the following to hold:
sup sup IP (f)) ((X) 2) p xE2
(4)
When 44) holds, the mechanism A is said to be (a, p. f) protteceee against reconstruction for the loss Trec. In (Bhowmick al., 2018 Lemma 2.2), the authors relates LDP mechanisms with protection against reconstruction attacks, and the result for several scenarios suggest that using LDP mechanisms with large may still provide decent protection against reconstruction. As a consequence, we identify two sorts of threats used in this paper:
Inference attacks by powerful adversaries this is the standard setup in LDP scenarios under which the adversary can observe the final learned model, as well as the information about potential partici- pants except for the precise membership list. For such cases, only low c LDP mechanisms provide sufficient protection against inference attacks.
Reconstruction attacks by curious onlookers in this relaxed scenario we assume the adversary is able to observe all model updates and individual communications to conduct reconstruction attacks that target the evaluation of some function f over private individual data. But knowledge about individual data is restricted some prior distribution xy. For such cases, we will discover mechanisms that are based upon LDP algorithms with large but provides decent protection against reconstruction.
Moreover, we assume the adversaries to be semi-honest (Lyu et al. 2020). i.c. they are curious about individual data but follow the FL protocol correctly.
In the seminal work (Duchi et al. 2018), the authors developed minimax optimal LDP mean estimators under i.i.d generative constraints. Bhowmick et al. (2018) used separate mechanisms to privatize both the direction and the scale of the individual gradients, and was shown to achieve comparable performance with respect to non- non-private counterparts using high es. Despite the effectiveness of the LDP approach, the communication cost is prohibitive. For models involving deep neural architectures, the number of parameters explodes to the order of millions. For each round, each client transmit (dd) bits to the server, where ö is the minimum number of bits to represent a real number with desired precision. The resulting communication cost is usually not affordable for mobile scenarios. In fact, the primary bottleneck for FL is usually communication, especially for deep neural architectures (Kairouz et al. 2019). It is thus of significant importance to reduce the communication cost to reasonable level. We identify two main challenges in building practical FL algorithms:
Communication Efficiency The algorithm shall be communication efficient, measured terms of bits transferred per client in single round.
High-dimensional compatibility It was shown in Duchi et al. (0018) that upon estimating a d- dimensional vector, the locally private constraint incurs multiplicative penalty of O(d/e²) in terms of minimax &2 risk. This linear dependence on the dimension of gradients may result in overly noisy gradient estimates that destroy the learning process. Hence the algorithm shall be able to handle models with high-dimensional inputs with tolerable performance degradation.
"In general, there are two sources of communication cost distributed learning scenario that requires sequential interactions between the server and the clients: downlink cost that happens during clients downloading the updated model from the central server, and uplink cost that happens when clients sending their updates to the server. In was previously noted in Konečný al. 2016) that uplink cost usually dominates downlink costs in FL settings. Hence in the scope of this work, we will refer communication cost as uplink communication cost.
3

---

Under review as a conference paper at ICLR 2021
Summary of contributions In this paper, we propose practical solution to locally private FL setting that addresses the above concerns which we term selective quantized stochastic gradient descent (sqSGD). Our contributions are summarized as follows:
1. We propose novel algorithm for locally private multivariate mean estimation. The proposed algorithm stochastically quantizes each dimension of each sample to K equally spaced levels and serves as the base algorithm for our gradient- learning framework.
2. We make several improvements to the basic algorithm under the gradient-based learning scenario. Specifically, we attribute the estimation error the base algorithm to perturbation enror caused by privacy constraints, and quantization error. Then utilize gradient subsampling strategy to simultancously reduce communication cost and improve private estimation utility. We also apply randomized rotation reduce quantization error.
3. We verify the performance of sqSGD on benchmark datasets using standard neural archi- tectures like NeNet (Lecun al. 1998) and ResNet (He et al.] (0166), and make systematic studies on the impact of both communication and privacy constraints. Specifically, under the same privacy and communication constraints, our model outperforms baseline algorithms that do not involve quantization by significant margin.
2 RELATED WORK
Communicatoon-efficeeet FL Since its introduction in (Konečný et al. 2016). communication efficiency has been one of the central topics of FL (Konečný et al. 2016 Kairouz et al.) 2019). Konečný et al.) (2016) described two kinds of general approaches for improving communication efficiency: structured updates like randomized masking, and sketched updates like quantization methods. The design of sqSGD could viewed as a combination the aforementioned approaches.
Privacy-preserving FL As optimization via stochastic gradient methods remains the most repre- sentative task federated learning, most privacy- prreecypreesriinggg FL. approaches are based on private SGD type algorithms like /Abadi et al. (2016). McMahan et al. (2018) used slightly tweaked central DP model to train large language models. Wei et al. (2020) derived federated aggregation schemes under the central DP model and discussed convergence properties. [howmick et al. (2018) justified using large privacy budgets in LDP settings, while still provide reasonable privacy guarantees against reconstruction attacks. However, most of the previous works privacy-preservine preserving FL did not address communication efficiency problems.
Gradient sparsification and quantization Gradient dropping methods threshold gradients based on either fixed single threshold (Aji & Heafield 2017) or adaptively chosen thresholds (Chen let al.] 2017) reported to greatly reduce communication overhead. DGC (Lin et al.) 2018) adopted more elegant refinements like accumulation correction and factor masking to achieve even higher compression ratios. FedSel (Liu al. (2020) performed privatized gradient sparsification via adopting randomized response techniques to select the most significant gradient dimension. Gradient quantization methods like QSGD (Alistarh al., (017)) or TernGrad (Wen al., (017) are able to achieve little performance degradation on large neural architectures using less than 4 quantization bits. Privatized versions of quantized SGD are recently proposed, epSGD> (Agarwal et al. 2018) adopts the central DP model and vqSGD (Gandikota et al., 2019) allows local DP model.
3
OUR MODEL
3.1 BASE MECHANISM
As starting point, we base our communication efficient mean estimation algorithm on the stochastic k-level quantization(Suress et al., (017)) scheme: We assume a uniform upper bound U on the &oo norm of any individual gradients over the whole course of the FL process. The quantization procedure is described as follows: Let 2 2 be the desired quantization level. We quantize the gradient to a
sequence of points -U B, B2 < .... < BK 1x U, where
2(k 1)U
B₁ = -U +
(5)
K -
4

---

Under review as a conference paper at ICLR 2021
The case for K = 2 corresponds to using only the endpoints (-U,U) for quantization. We will denote the quantization range as = [Bx hEr For each dimension j E [d] the individual gradient X we first locate X to one of the K bins via finding k3 such that X [ Bg-+1) 1) and round
X to the boundary of the bin as:
Bx++1 with probability 1'(Xi-Bp.) Bxx otherwise
20
(6)
Note that X is unbiased estimator of X). The quantization scheme reduces the communication cost to d logg bits per round per client.
Next we privatize X by constructing a locally private unbiased estimator of X (where we fix the randomness of the quantization step), thereby obtaining locally private estimator of X with its value resides in Bd. To describe the privatization scheme we introduce some new notations: for Vei, 1/ E Bd, define M(U1, 12) = # oi = = # oa # 2 where #C' stands for the number of elements in the set C. For a given positive integer &. E fo......d 1}, let (e;; (d : {u M(u. v) x} and S(v; B := fu MM,, v) < x}. The privatization procedure, which we termed PrivQuant is summarized in Algorithm | To state the privacy guarantee of PrivQuant,, we identify two setups which corresponds to protection against inference and reconstruction attacks. The later case requires additional specifications for the priors and evaluation function held by the adversary, which we state as follows: we assume the evaluation function f to be map from Y' to compact set C' C RR" For any absolutely continuous prior on V, we n to denote the induced prior on f. Let my be the uniform prior over C, we will be focusing on priors that belong to the following set:
Pp(P)) 11TT ( :uppupploy log di d S Po
dro(y)
where Po non-negative number. The set (p())) characterize prior beliefs that are "not much more certain than uniformly random guessing" over all possible outcomes that belong to the image of the evaluation function. We state the theorem under the orthogonal reconstruction attack that uses the evaluation function (z) = Az/ ||æ||| with A E Rx an orthonormal matrix, i.c., AAT = Ir. and the reconstruction criterion chosen the l2 error Liee x²) ||z// |>ll2 - x ||=21 Theorem 1. For any K 2 2, Consider PrivQuantx. oo as a mechanism parameterized by (n. p). Let d+++11 and let (v. p) be chosen such that the following relation holds:
P Σ ( - 1)(8-0) Se
1-P Σ Ei 1)(a-e)
then Z is an unbiased estimator of X, Lee. B(Z)= = with randommess jointly over the quantization step and sampling step. Moreover, we have the following privacy guarantees:
Inference attack protection PrivQuantx, p)P) is e-locally differentially private.
Reconstruction attack protection with k 2 4 and a E [0, PrivQuantxx.o (t, is
(V2 - 20, w(a), JA) prooected against reconstruction for
(- (r 1)a²
w(a) V8exp
exple + po)
2
The proof will be deferred to appendix A.I Theorem ! implies that, if the adversary aims at reconstructing a non-vanishing fraction of the private data with r = Od), for small that allows of smaller order than d ensure that any
coarse reconstruction, we only need 6 and Po reconstruction attack will not succeed with reasonable probability. Note for K levels and U 1. algorithm reducee to algorithm PrivUnit in (Bhowmick et al. 2018).
We may view the estimation error of Z (measured in terms of Ea risk) coming from two parties: one from the quantization step, and the other from the privatization step. In the following sections we will take closer looks at the two sources of error, and develop corresponding improvements. Indeed as verified by our empirical study (see section certain improvements are necessary to achieve digh-dimensional compatibility.
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Private K X-quantized &o Ball PrivQuantx,.o
Require: X E [-U,U], (0...., 1), 2 1.2 -= ]dtat11. [
1: Quantize each coordinate of to B using (6 to obtain X 14.
2: Sample random vector V as follows: with probability p. V is sampled uniformly at random
from S(X;B%) otherwise with probability p. V is sampled uniformly random from S(X:B*)
3:
Calculate normalizing factor
(+)) (K (K-1)0 1)0-
(= (K 1) EE (2) - 1)a-
= P Σ l= (K - 1)0-1
-1 - -11 - -p)
return 7= m
3.2 IMPROVING PRIVATIZATION UTILITY VIA SELECTIVE GRADIENT UPDATE
PrivQuant,, provides unbiased estimator of individual gradients, but the considerable amount of noise injected would hurt the training process. This defect is amplified in deep learning scenarios: empirically, [Lin et al. 2018) observed that for many representative deep architectures, most of the gradient dimensions are nearly sparse. Hence privatizing the whole gradient vector would result in a high privatization error that even orders of magnitude higher than the norm of the gradient itself.
The (almost) sparse structure of the gradients suggests a modification to the estimation scheme via privatizing and transmitting only fraction of the gradient dimensions, which could be regarded as significantly reducing variance at the cost of small amount of bias. Such techniques are closely related gradient compression that sends a few most significant gradient dimensions (Lin al.) 2018). Typically, gradient compression techniques require selecting top-k gradients measured in absolute magnitude (Lin al., [2018] Aji & Heahelld 2017). A straightforward extension the local private setting would be to perform private selection methods like exponential mechanism (Dwork) ctt al., 2014) or noisy top-k (Ding et al. 2019), for which we need to allocate a certain fraction of privacy budget. However, these solutions are either computationally expensive or "too noisy" for picking high dimensional gradients that are almost sparse. We defer a more detailed discussion to appendix A.2 A.2
Motivated by algorithm designs distributed learning like random masking (Konečný et al. 2016) and Hogwild! (Niu et al. 2011), we utilize simple strategy, gradient subsampling, by randomly sample d = |rd] dimensions, where is the sampling proportion of gradient dimensions. To further improve training efficiency, we applied local accumulation techniques like momentum correction and factor masking similar to (Lin et al.) 2018). It is worth noting that low sampling ratio do not necessarily improves model performance as the overall bias of the sparse approximation would become significant when only few dimensions are selected. more detailed study of this aspect provided in appendix A.3
3.3 IMPROVING QUANTIZATION PERFORMANCE VIA RANDOMIZED ROTATION
As shown in Agarwal et al. 2018 Suresh et al. 2017), for a d-dimensional vector X, the quantization error scales with (max;ej4 X minjej4 x To reduce quantization error, effective way is to preprocess the data via randomized rotation, as to make maxjejd X minje(4 X small in expectation. Note that we only need to rotate the fraction of gradient that are selected to get transmitted.
To perform randomized rotation we need to assume public randomness between the server and the clients, under which generate orthogonal random matrix R E d and apply the linear transform the individual gradients X RX on the client side, and apply inverse transform the server side Ż R Z. We adopt the method in (Agarwal et al. 2018 Suresh et al. 2017) to generate that support fast matrix multiplication with Od d') time and O(1) space. Specifically, generate R H. HA
A where A is random diagonal matrix with i.i.d. Rademacher entries (i.e.

---

Under review as a conference paper at ICLR 2021
P(AN 1 -1) = 0.5, Vi [d), and H is Walsh-Hadamard matrix
(Horadam 2012
defined recursively by the formula:
H(2))
1 -1 ((
(2 12 H22=11 (2
(10)
The randomized rotation operation is performed before quantization and privatization, therefore we project the vector X an & ball of radius U before rotation. This would ensure the vector obtained after rotation has for norm bounded by U as well.
The final selective SGD updating process is summarized in algorithm 2 and sparsification strategy have no effect on privacy level, hence the local update within a single round is e-LDP. At the same time, communication cost was further reduced from Ogg K) bits to O(d K) bits per client.
The randomized rotation
Algorithm 2 sqSGD: Selective Quantized SGD with local privacy guarantee
Require: Training data {Y:) gradient norm bound U, privacy budge c, sampling ratio r E (0, 1),
local correction factor a, 3,, learning rate batch size B.
1: Find a (Ke, P.) pair that satisfies relation (8)
2: Calculate the corresponding normalizing constant m, in algorithm
3: Set d (rdn), and using public randomness to generate random matrix R
according to the construction in (10)
4: Initialize model parameter Og and local residuals res.,o = 0, Vi 1I....;
5: for = o..... T .,T 1 do
6: Sample a batch indices S. E [N] with size B
7: for E 5 do
8:
//* Client Side Update *//
9:
Select a uniformly random subset of [d] with cardinality d, denoted as D., also let DC denote [d].
10:
11:
Calculate local (stochastic) gradient with respect to client data Nz,t = o(Y,,,,0)
12:
Clip the local gradient the la ball with radius U
13:
Accumulate and Apply rotation X,,: R (res.,, [P.] 8X.,, (Da)) Rotate and update local residual res.,141 (D.) = [D.] + (D and res., ,,t++ [D.] =
14:
15:
16:
Calculate Zz,t = PrivQuantx, (K.,e, Kic, Pc)
Upload (Z,,/m,,, D.) the server
18:
//* Server Side Update *//
Gradient update step 0.+1 02 R-1 R-1n Eges
Zense where Zdense the d dimensional
20:
zero vector with indices in D, replaced by Za.
return fg.
4 EXPERIMENTS
In this section, we apply SQGGD to simulated FL environments, constructed via standard datasets MNIST (Lecun al. 1998,, EMNSIT (Cohen al., 2017), and Fashion MNIST (Xiao al. 2017) which we abbreviate as FMNIST hereafter. All three datasets are of equal (training) sample size, therefore we randomly partition each dataset into 10 equally sized blocks to simulate cross-silo FL environment consisting of central server and 10 clients.
We train on MNIST and EMNIST datasets using the LeNet-5 architecture (Lecun et al. 1998) (119, 850 parameters). We also train a larger network under the ResNet- architecture (1, 722, 224 parameters) on the FMNIST dataset. Since the main goal the empirical study is not to achieve state-of-the-art performance, we adopt the following common strategies without further tuning across all experiments: in each round, we randomly sample a single batch with batch size 32 for each client and compute single gradient update step. Without gradient subsampling, this would be equivalent to a stochastic gradient descent update over the entire data with a batch size of 320. The training duration is measured via number of epochs (1 epoch 188 rounds). We use the same configuration
7

---

Under review as a conference paper at ICLR 2021
MNI5 1w0.55 a-60
ENNST 0.5% 4-400
Mashaac110 r.0.5% 2-2000
25 1 Epoches
Epoches
Epoches
Figure 1: Study impact of communication constraints
MNIS LeNet5 r.0.5% K-16
EHMST Lekiet Leliet r-0.5% K-16
FNNIST ResNett1S FNNISTResNetIIC K-16
Number Epoches
Tumber of Spaches
Number of EpEcches
Figure 2: Study on impact of privacy constraints
of learning rate rj = 0.001 and local correction factors a = 1.0, = 1.0 across all experiments. We set the Eg norm bound of the gradients U 10 as it works reasonably well. Note that could use more elegant distributed private estimation of the & norm bound via sending privatized magnitude evaluated at different points of the parameter space, i.e. via mechanisms like ScalarDP in Bhowmick jet al. (2018). Finally, for a given privacy budget e, we use the following method to determine the value of Pe): We set Ki to be the largest integer such that the value of the left hand side of (8) is 2.1c
smaller than or equal to 0.9c, and P.
14.0..1.
Choice of privacy budget across all the experiments we align the choice e O(Vd) with respect to the additional risk factor O(df²2 in private mean estimation (in comparison to non-private case). As the models used in our experiments are all of high dimension, the choice of high-epsilon will basically provide little protection against inference attacks. However, with respect to reconstruction attack specified in section 1.2 and the protection level 4 such choice still provide reasonable
protection against reconstruction attacks if the adversary's 's goal is to evaluate more than O(Vi) of the entries in the private data.
Impact of communication constraints We evaluate the performance of trained models using the test set accuracy. The privacy budget is chosen as 400 for LeNet models and 2000 for ResNet models. Sampling ratio is fixed at = 0.5%. We vary the quantization level in the range {2, 8, 32} which corresponds to using {1, 5} bits per client per dimension. The results plotted in figure The results indicate that a while 1-bit sqSGD is efficient in terms of communication cost, the quantization error results in significant degradation in model performance, both in the final accuracy after model convergence, and in the speed of convergence. A reasonable quantization level (i.e. larger than 3 bits) yields competitive performance.
Impact of privacy constraints Next we investigate the performance loss due to privacy constraints. We fix the sampling rate ture, we select from the set (200, 300, 400), for ResNet-1 10 architecture, we select from the set (1000, 2000, 3000). The results are plotted in figure 2 The results imply that with limited communication, we need high privacy budgets to ensure successful training on large models.
0.5% and quantization level at K 16. For LeNet-5 architec-
Baseline comparisons We compare sqSGD against two baselines:
Piecewise mechanism (PM) (Wang et al., 2019) PM is designed for mean estimation under local privacy model that improves accuracy upon the PrivUnit,c algorithm in Bhowmick al. (2018)
8

---

mean estimation algorithm. For large d settings, we choose perturbed gradients in |c/2.5| dimensions. Under review as a conference paper at ICLR 2021
Lafeu15 K-15
K-128
ACC
ext300 peiai
25
13
Epoches
Epoches
Epoches
Figure 3: Comparison of sqSGD against piecewise mechanism
Although PM communicates real values, the multi-dimensional version of PM (Wang et al. Algorithm 4) samples fraction of coordinates for perturbation hence may view PM practically as a limited-communicatie
2019
reasonably large values such that PM communicates
vqSGD Gandikota et al. (2099) vqSGD uses an communication-opinni distributed mean estima- tion algorithm that adopts vector quantization strategies. The per client communication cost of vgSGD is Olog d) for mean estimation task. The algorithm has trivial extensions to locally private settings using randomized response strategies (Gandikota et al. 2019). As discussed by the authors, for distributed optimization settings with high dimensional models. Variance reduction techniques are necessary, specifically one data point is communicated 6 times and server uses the average of b quantized gradients for aggregation. This makes the communication cost O6 log d). Note that in private settings this results in a caveat that privacy protection level is degraded under composition. In experiments will ignore this caveat and use variance reduction that the communication of vqSGD matches that of sqSGD and PM.
We compare the three approaches across all tasks mentioned above under the same privacy budget. For sqSGD we use K = 16 for LeNet architectures and K = 128 for ResNet architectures, and we adjust the sampling ratio in sqSGD such that communication costs remain equal among all methods. The comparisons are presented in figure 3 Figure shows that sqSGD consistently outperforms PM by significant margin across tasks under various privacy levels. vqSGD obtains comparable performance with sqSGD in relatively smaller models and high-privacy regime (Note that vqSGI approaches offer much worse privacy protections in this setting), but breaks down when models get larger. Overall, in high-dimensional settings, sqSGD provides much better optimization performance.
Additional experiments We present an experimental study on the effect of gradient subsampling in appendix[A.2 AA.] and another study on the trade-off between quantization and subsampling in [n.44] The results of additional experiments further justify the choice of sampling ratios and quantization levels in the above comparisons.
CONCLUSION
We studied achieve both communication efficiency and high-dimensional compatibility, we proposed a gradient- based learning framework sqSGD that is based on a novel private multivariate mean estimation scheme with controllable quantization levels. We applied gradient subsampling and randomized rotation to reduce estimation error of the base mechanism that exploits the specific structure of federated learning with large modern neural architectures. Finally, our designed algorithm was shown on standard datasets to be capable of training large models with random initializations, surpassing baseline algorithms by significant margin.
federated learning under the local differential privacy model. To
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '16, pp. 308-318, New York, NY,

---

Under review as a conference paper at ICLR 2021
USA. 2016. Association for Computing Machinery, ISBN 9781450341394, doi: 10. 10.1145/2976799. 2978318. httttp:://dii.org11...oo
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. epsgd: Communication-effiiinn and differentially-priee distributed sgd. In Advances Neural Information Processing Systems, pp. 7564-7575, 2018.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 440 445, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus. S. Vishwanathan, and Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1709-1720. Curran Associates, Inc., 2017.
Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protec- tion against reconstruction and its applications in private federated learning. arXiv preprint arXiv:1812.00094 2018.
Chia- Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, and Kailash Gopalakr- ishnan. Adacomp : Adaptive residual gradient compression for data- parallel distributed training, 2017.
data-parallel
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. Emnist: an extension of mnist to handwritten letters, 2017.
Zeyu Ding, Yuxin Wang, Danfeng Zhang, and Daniel Kifer. Free gap information from the differen- tially private sparse vector and noisy max mechanisms, 2019.
John C Duchi, Michael I Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-201 2018.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):21 1-407, 2014.
Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent, 2019.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Kathy J Horadam. Hadamard matrices and their applications. Princeton university press, 2012.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet. Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafacl G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage. Ramesh Raskar, Dawn Song. Weikang Song, Sebastian U. Stich. Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning, 2019.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What learn privately? SIAM Journal on Computing, 40(3):793-824 2011.
10

---

Under review as a conference paper at ICLR 2021
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492. 2016.
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency, 2016.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 66(11):2278-2324, 1998.
D. Leroy, A. Coucke, T. Lavril, T. Gisselbrecht, and J. Dureau. Federated learning for keyword spotting. In ICASSP 2019 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6341-6345, 2019.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations, 2018. URL httpstt/ppeerreeiieee http:/viwwwiwweefeeeeeeeeeee http:///ww......rro.ooooooaaaaaa
Ruixuan Liu, Yang Cao, Masatoshi Yoshikawa, and Hong Chen. Fedsel: Federated sgd under local differential privacy with top-k dimension selection, 2020.
Lingjuan Lyu, Han Yu, and Qiang Yang. Threats to federated learning: A survey. arXiv preprint arXiv:2003..0213,, 2020.
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018. URL
https://openrevier net. nwt./fruumttteeee (otorummdd=BOOF1111
Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Inference attacks
against collaborative learning. arXiv preprint arXiv: 1805. 04049, 13, 2018.
Feng Niu, Benjamin Recht, Christopher Re, and Stephen J. Wright. Hogwild! lock-free approach to parallelizing stochastic gradient descent. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS' 11, pp. 693-701, Red Hook, NY, USA, 2011. Curran Associates Inc. ISBN 9781618395993.
Ananda Theertha Suresh, Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International Conference Machine Learning, pp. 3329-3 303,,
Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, and Ge Yu. Collecting and analyzing multidimensional data with local differential privacy. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp.
IEEE, 2019.
K. Wei, J. Li, M. Ding, C. Ma, H. H. Yang, F. Farokhi, S. Jin, T. Q. S. Quek, and H. Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-3469, 2020.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients reduce communication in distributed deep learning. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30. pp. 1509-1519. Curran Associates, Inc., 2017.
Han Xiao, Kashif Rasul, and Roland Vollgraf. machine learning algorithms, 2017.
a novel image dataset for benchmarking
11

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 PROOFS
Proof of theorem I. Let u E Bd and U Unif(B The vector E Bd sampled as in algorithm | has p.m.f.
p(u u) [1/P(M(U, u) N) ife > 1/P((((U u) < <) ifM(r, K.
The event that M(U u) = x when dt6+1 E implies that U and u match in exactly den+1 coordinates; the number of such matches is ((4xx+1/22) Computing the binomial sum, have
2
2
( (K ()100(0-)) 1)(0-0)
P(M(U, x) Kd
Σ
(11)
P(M u) kk)
Σ
(K- (K (K-1)
Kd
Now show unbiasedness via showing V.V u u|
We have
EiV u u| pE(U M(U, u) > x| + E M(U, S ml
By rotational symmetry, it suffices to show:
E ul p M(U u) +(1 p) LEU! M(U, S
T₁
T2
For Y,, we have:
Ti
Σ
d (1) K 1)d-
u²
Σ wn
KMP(M(U, u) k)
1=
wEBlu
(K - (1)()((r)) 1)(-=))
(<P(M(U,u>>))
Where in the second equality we used the fact that EweB w = 0. Similar calculations yield:
d (-=1) (K ()
T2 KMP(M(U, u) kk)
Combining the preceding display with (II,, we have:
(-=1) 1)d-r
(K-)0- 1)a-5 En (g 1)a-1)
(d (d-) -
E[V' u -u= w]
= 1 Σ2 (9) 1)d-1 (1-p)
mu
Next we show privacy guarantee.
LDP guarantee As F(M(U,)) u) > k) is decreasing in for any u' E Bd and v E Bd we have
plu u) p
P P(M(U, 5
P
x EE ()) 1)(d-))
u') 1 T-p P(M(U, u) k) 1-P E () 1)(d-e)
The result follows by relation
g
Reconstruction protection guarantee the result follows by Bhowmick al. 20018 and the LDP guarantee.
Proposition 1)
12

---

Under review as a conference paper at ICLR 2021
FMNIST ResNet110 K=16 c=2000
ACC
10
20
30
50
Number of Epoches
Figure Study on the effect of gradient subsampling
A.2 ON THE PRACTICALITY PRIVACY-PRESERVVNG SELECTION METHODS
Performing top-k selection with local privacy constraints could be done via two approaches. The first take is iteratively running the exponential mechanism (Dwork et al. 2014) for k times, each time selecting single index with gumble noise. The bottleneck of this take is that it requires sampling from high dimensional distribution for k times, which is computationally heavy. Note that the privatization step is carried out on the client side device, which is usually assumed to be of limited computational power in FL settings (Kairouz et al. 2019), thus using iterative exponential mechanism is not practical for FL scenarios. The second take the noisy top-k algorithm (Ding et al., 2019). which generalizes the report noisy max mechanism in Dwork et al. (2014). The algorithm requires adding Laplacian noise of scale 2Uk/c to each dimension of the gradient vector. In practice, is typically chosen at the order of hundreds. Since most of the gradients are very small in magnitude,to ensure reasonable noise requires high budget allocate for the selection step. This would significantly affect the overall privacy level.
A.3 EXPERIMENTS ON THE EFFECT OF GRADIENT SUBSAMPLING
In this experiment, we investigate the effect of subsampling under the setup of training a ResNetl model on the FMNIST dataset. We fix the privacy level at 2000 and quantization level at K 16. We vary the subsampling ratio from the set {1, 5, 10, 50} x 10 The results are plotted in figure 4 It could be seen from the plot that using a high sampling ratio severely hurts the training performance, while also incurs more communication. is thus necessary to perform subsampling. However, using very low subsampling ratio also causes training failure. This phenomenon will be further explored in the next experiment.
A.4 EXPERIMENTS ON THE TRADE-OFF BETWEEN QUANTIZATION AND SAMPLING
In this experiment, we study the trade-off between quantization and sampling under the setup of training a LeNet-5 model on the MNIST dataset. We fix the privacy level at = 400, and fix the total communication cost per client, measured using the product log, K. We vary the quantization level in the range {2, 8, 32, 128} which corresponds to using {1, 3, 5, 7) bits per client per dimension, and the sampling rate are adjusted accordingly. The results are shown in figure The results suggest that increasing the quantization level may not monotonically increase training performance. This is mainly due to the random subsample scheme of sqSGD, under which the structure of gradients is not fully explored.
13

---

Under review as a conference paper at ICLR 2021
MNIST LeNet5 40400
POP privaee
K- 328
1.0
0.
20
Number of Epoches
Figure 5: Study on the trade-off' between quantization and sampling with fixed communication level
14


Reviews:
[{"review_id": "tC7dMDeRKV1", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies FL under local differential privacy constraints. They identify two major concerns in designing practical privacy-preserving FL algorithms: communication efficiency and high\u0002dimensional compatibility, and develop a gradient-based learning algorithm sqSGD that addresses both concerns. They improve the base algorithm in two ways: First, apply a gradient subsampling strategy that offers simultaneously better training performance and smaller communication costs. Secondly, utilize randomized rotation as a preprocessing step to reduce quantization error. \n\nThere are also some parts need to be improved. For example, putting the related work as Section 3 is not proper. For the experiments, the epsilon is too large for privacy protection as 400 and 2000,. For this level, the privacy is not well protected. For the baseline PM, which performs well when epsilon is small. But in this paper, the comparison is only about large epsilon.\n\nThey are some typos/errors here:\nAfter Eq(1), it needs a space before ‘M’\nDifferent fonts for “cross-silo”\nThe first sentence of the last paragraph on Page 2, capitalize the first letter.\nEq(4), it should be k^* rather than k\nIn Algorithm 1, parameter \\tau is not introduced", "extra_scores": {}, "extra_text": {}}, {"review_id": "g095W6xXt7", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Federated learning is a distributed learning paradigm where models are learned from decentralized data sources. The paper proposes to train machine learning models with communication-efficient differentially private approaches.\nI have several concerns about the work including the experimental setup.\n\nExperimental setup:\nExperiments use a privacy budget of epsilon = 400 for LeNet Models and 2000 for ResNet models. Note that differential privacy algorithms ensure that the probabilities differ by at most e^{epsilon} with high probability. This means that the probabilities can be off by  e^{400} ~ 10^170, which is higher than the number of particles in the observed universe.\nThe paper is very hard to accept with the current set of experimental results.\n\nOther:\na. R_s is not defined in Section 1.2.\nb. PrivQuant seems to be a very interesting algorithm, however very little intuition is provided. It would be good to describe why this algorithm is preferred over others. \nc. In Section 2.2, authors argue that one can get better results if the gradients are sparse. However note that for this to work, even the non-zero coordinates have to be relayed with differential privacy, which can add to the total privacy cost.\nd. Step 14 in the algorithm: the role of r is not clear and needs to be explained more.", "extra_scores": {}, "extra_text": {}}, {"review_id": "819q7DEAbn", "reviewer": "AnonReviewer5", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a differentially private training algorithm for federated learning. The target is to achieve communication reduction while keeping differential privacy during training. The proposed algorithm adds a few new components to SGD, including a privacy mechanism, a random rotation to reduce quantization error, a gradient coordinate selection mechanism to reduce communication/computation. Experiments with high \\epsilon local differentially privacy guarantees are conducted. The proposed algorithm outperforms a baseline algorithm.\n\nOverall the paper is well-organized and easy to follow. My main concern is that the paper seems incremental and the comparison with existing works is not sufficient. \n\n1. Out of the three components added to SGD, the random rotation scheme is from existing works and it is not the contribution of this paper. The gradient coordinate selection mechanism is just uniformly picking coordinates which quite straightforward. The main contribution seems to be the privacy mechanism which is an extension of the mechanism in Bhowmick et al., 2018 and it is not technically difficult to extend it. \n\n2. The experiments only compared with one baseline algorithm in literature. However, there are quite a few works on communication-efficient privacy-preserving distributed training. For example, cpSGD in Agarwal et al., 2018 is a closely related algorithm but it is not compared in experiments. If a comparison is not applicable, it is better to add more discussion on comparison with existing works to highlight the difference and contribution of this work.\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2H1XWBRVl-y", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==== Overview====\n\nThis paper studies a low communication algorithm for multivariate mean estimation in the federated learning setting with differentially private communication. The algorithm uses quantization and dimension subsampling (only reporting some coordinates of the vector) to lower communication and randomized rotation (essentially applying a random orthogonal matrix) to reduce quantization error. They then apply this algorithm to ERM, using it as a subroutine in SGD. They experimentally explore the behavior of their algorithm on a number of benchmark datasets. They consider how the performance changes as they vary epsilon, the discretization parameter and the number of epochs (in SGD). \n\n==== Comments ==\n\nI thought PrivQuant was an interesting algorithm. I thought the use of randomized rounding was nice, although it was also used in Bhowmick et. al ’18. It wasn’t clear to me to what degree this algorithm was an extension of the algorithm in that paper, but I thought it was clever. The series of improvements made seem to all have individually appeared in the literature before (I wasn’t familiar with the random rotation but the authors indicate that this is not new to this work), but the combination of them for solving this problem seems to be unique.\n\nThe paper does a good job of placing itself in the context of prior work. I would have liked more explanation of how vqSGD compares?\n\nThe experiments are well designed. Hyper-parameter tuning is often an issue for algorithms like this and the authors clearly state how they tune hyper-parameters heuristically. They compare their algorithm to an algorithm from the literature, which has low communication via performing dimension subsampling, at a variety of epoch and privacy levels. They always outperform the other algorithm. It wasn’t clear to me if the algorithm they compare against was the current state of the art. \n\nThe discussion of Bhowmick et. Al ’18 was bit confusing and didn’t seem very self-contained. The authors use this paper as justification for the large local epsilon values used in the experiments. They also say that they will develop algorithms that protect against inference and reconstruction attacks. This is fine, but I think the findings and caveats of Bhowmick ’18 should be discussed more explicitly if they are used to justify the statement that high local eps algorithms protect against reconstruction attacks.\n\nThis is mainly semantics but I occasionally found the granularity of the privacy confusing. PrivQuant seems to be a locally differentially private in that each data point is privatized before it is sent to a central server. However, sqSGD is not written as a purely local algorithm, instead each client holds several data points, which they aggregate into a gradient, which is then privatized. Since PrivQuant is DP, it seems like the privacy is at the client level, not the level of individual data points? Perhaps the language of multi-central DP (https://arxiv.org/pdf/2009.05401.pdf)\n would be more helpful than local DP in the cross-silo FL setting?\n\nJust a question for the authors: do you have any intuition for what’s happening with FMNIST? It seems much more sensitive than MNIST or EMIST\n\n==== Presentation =\n\nIt would have been nice to see the non-private performance on the Figures to compare. The non-private seems to approach around 90% in most cases, is this around the non-private error? The authors state in the “impact of communication constraints” section that their algorithm “yields competitive results”, competitive with what?\n\nThe statement of Theorem 1 was a bit confusing. Is condition (5) required for the privacy statement and the unbiased statement? Currently it reads as being required for the unbiasedness, and its not clear whether its required for privacy.\n\nSmall:\nLDP is typically attributed to Dwork, McSherry, Nissim, Smith ’07 or https://arxiv.org/pdf/0803.0924.pdf.\nIt might have been more intuitive to just state the definition of M(v_1,v_2) in terms of the Hamming distance. \nIt would be nice to have some intuition for the statement about the quantization error at the start of section 2.3 since that wasn’t obvious to me. \nAt one point the authors refer to “raw perturbed gradients”, is this unquantized?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies differentially private, communication-efficient training methods for federated learning. While the problem studied in this paper is well-motivated and interesting, the reviewers raised several concerns about the paper. Despite the authors' reconstruction protection explanation, the concern over large values of epsilon at the scale of 400 persists. There is not too much technical novelty since the main technique is given by prior work. 
Decision: Reject