summaries: This paper studies FL under local differential privacy constraints. They identify two major concerns in designing practical privacy-preserving FL algorithms: communication efficiency and highdimensional 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.  This 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).  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.
abstractText: 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 highdimensional compatibility. We then develop a gradient-based learning algorithm called 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.
references.authors: Martin Abadi Andy Chu Ian Goodfellow H. Brendan McMahan Ilya Mironov Kunal Talwar Li Zhang
references.title: Deep learning with differential privacy
references.venue: In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS
references.authors: Naman Agarwal Ananda Theertha Suresh Felix Xinnan X Yu Sanjiv Kumar Brendan McMahan
references.title: cpsgd: Communication-efficient and differentially-private distributed sgd
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Alham Fikri Aji Kenneth Heafield
references.title: Sparse communication for distributed gradient descent
references.venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,
references.authors: Dan Alistarh Demjan Grubic Jerry Li Ryota Tomioka Milan Vojnovic
references.title: Qsgd: Communicationefficient sgd via gradient quantization and encoding
references.venue: Advances in Neural Information Processing Systems
references.authors: Abhishek Bhowmick John Duchi Julien Freudiger Gaurav Kapoor Ryan Rogers
references.title: Protection against reconstruction and its applications in private federated learning
references.venue: arXiv preprint arXiv:1812.00984,
references.authors: Chia-Yu Chen Jungwook Choi Daniel Brand Ankur Agrawal Wei Zhang Kailash Gopalakrishnan
references.title: Adacomp : Adaptive residual gradient compression for data-parallel distributed training, 2017
references.authors: Gregory Cohen Saeed Afshar Jonathan Tapson André van Schaik
references.title: Emnist: an extension of mnist to handwritten letters, 2017
references.authors: Zeyu Ding Yuxin Wang Danfeng Zhang Daniel Kifer
references.title: Free gap information from the differentially private sparse vector and noisy max mechanisms, 2019
references.authors: John C Duchi Michael I Jordan Martin J Wainwright
references.title: Minimax optimal procedures for locally private estimation
references.venue: Journal of the American Statistical Association,
references.authors: Cynthia Dwork Aaron Roth
references.title: The algorithmic foundations of differential privacy
references.venue: Foundations and Trends in Theoretical Computer Science,
references.authors: Venkata Gandikota Daniel Kane Raj Kumar Maity Arya Mazumdar
references.title: vqsgd: Vector quantized stochastic gradient descent, 2019
references.authors: Andrew Hard Kanishka Rao Rajiv Mathews Swaroop Ramaswamy Françoise Beaufays Sean Augenstein Hubert Eichner Chloé Kiddon Daniel Ramage
references.title: Federated learning for mobile keyboard prediction, 2019
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Kathy J Horadam
references.title: Hadamard matrices and their applications
references.venue: Princeton university press,
references.authors: Shiva Prasad Kasiviswanathan Homin K Lee Kobbi Nissim Sofya Raskhodnikova Adam Smith
references.title: What can we learn privately
references.venue: SIAM Journal on Computing,
references.authors: Jakub Konečnỳ H Brendan McMahan Felix X Yu Peter Richtárik Ananda Theertha Suresh Dave Bacon
references.title: Federated learning: Strategies for improving communication efficiency
references.venue: arXiv preprint arXiv:1610.05492,
references.authors: Jakub Konečný H. Brendan McMahan Felix X. Yu Peter Richtárik Ananda Theertha Suresh Dave Bacon
references.title: Federated learning: Strategies for improving communication efficiency, 2016
references.authors: Y. Lecun L. Bottou Y. Bengio P. Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: D. Leroy A. Coucke T. Lavril T. Gisselbrecht J. Dureau
references.title: Federated learning for keyword spotting
references.venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),
references.authors: Yujun Lin Song Han Huizi Mao Yu Wang Bill Dally
references.title: Deep gradient compression: Reducing the communication bandwidth for distributed training
references.venue: In International Conference on Learning Representations,
references.authors: Ruixuan Liu Yang Cao Masatoshi Yoshikawa Hong Chen
references.title: Fedsel: Federated sgd under local differential privacy with top-k dimension selection, 2020
references.authors: Lingjuan Lyu Han Yu Qiang Yang
references.title: Threats to federated learning: A survey
references.venue: arXiv preprint arXiv:2003.02133,
references.authors: H. Brendan McMahan Daniel Ramage Kunal Talwar Li Zhang
references.title: Learning differentially private recurrent language models
references.venue: In International Conference on Learning Representations,
references.authors: Luca Melis Congzheng Song Emiliano De Cristofaro Vitaly Shmatikov
references.title: Inference attacks against collaborative learning
references.venue: arXiv preprint arXiv:1805.04049,
references.authors: Feng Niu Benjamin Recht Christopher Re Stephen J. Wright
references.title: Hogwild! a lock-free approach to parallelizing stochastic gradient descent
references.venue: In Proceedings of the 24th International Conference on Neural Information Processing Systems,
references.authors: Ananda Theertha Suresh X Yu Felix Sanjiv Kumar H Brendan McMahan
references.title: Distributed mean estimation with limited communication
references.venue: In International Conference on Machine Learning,
references.authors: Ning Wang Xiaokui Xiao Yin Yang Jun Zhao Siu Cheung Hui Hyejin Shin Junbum Shin Ge Yu
references.title: Collecting and analyzing multidimensional data with local differential privacy
references.venue: IEEE 35th International Conference on Data Engineering (ICDE),
references.authors: K. Wei J. Li M. Ding C. Ma H.H. Yang F. Farokhi S. Jin T.Q.S. Quek H. Vincent Poor
references.title: Federated learning with differential privacy: Algorithms and performance analysis
references.venue: IEEE Transactions on Information Forensics and Security,
references.authors: Wei Wen Cong Xu Feng Yan Chunpeng Wu Yandan Wang Yiran Chen Hai Li
references.title: Terngrad: Ternary gradients to reduce communication in distributed deep learning
references.venue: Advances in Neural Information Processing Systems
references.authors: Han Xiao Kashif Rasul Roland Vollgraf
references.title: Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017
references.authors: Dwork
references.title: The algorithm requires adding Laplacian noise of scale 2Uk/ to each dimension of the gradient vector. In practice, k is typically chosen at the order of hundreds. Since most of the gradients are very small in magnitude,to ensure reasonable noise requires a high budget to allocate for the selection
sections.heading: 1 INTRODUCTION
sections.heading: 1.1 BACKGROUND
sections.text: Federated learning (FL) Kairouz et al. (2019); Konečnỳ et al. (2016) is a rapidly evolving application of distributed optimization to large-scale learning or estimation scenarios where multiple entities. called clients, collaborate in solving a 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 et al., 2019; Leroy et al., 2019). While FL offers significant practical privacy improvements over centralizing all the training data, it lacks a formal privacy guarantee. As discussed in Melis et 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 state-of-the-art approach to address information 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 adversaries, 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 is often not satisfied in practical cases, under which users that act as clients may not trust the service provider that acts as the server. Local differential privacy (LDP) (Kasiviswanathan et al., 2011; Dwork et al., 2014) provides privacy protection on the individual level via applying randomized mechanisms that obfuscate the data before leaving the
  client, and is a more natural privacy model for distributed learning scenarios like FL, allowing easier compliance with regulatory strictures (Bhowmick et al., 2018).
sections.heading: 1.2 METHODOLOGY
sections.text: We will be focusing on distributed learning procedures that aim to solve an empirical risk minimization problem in a decentralized fashion:
  min θ∈Θ
  L(θ), L(θ) = 1
  N M∑ m=1 Lm(θ) (1)
  where M denotes the number of clients. Let Yi denotes training data that belongs to the m-th client consisting Nm data points, and N = ∑M m=1Nm. The term Lm(θ) = ∑ y∈Ym `(θ, y) stands for locally aggregated loss evaluated at parameter θ, where ` : Θ × Y 7→ 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 (1) via gradient-based methods. In what follows we will use [n], n ∈ N+ to denote the set {1, 2, . . . , n}. At round t, the procedure iterates as:
  1. Server distribute the current value θt among a subset S of clients.
  2. For each client s ∈ S, a local update is computed ∆s = g(θt, Ys) and transmitted to the server.
  3. The server aggregates all {∆s}s∈Ss to obtain a global update ∆ and updates the parameter as θt+1 = θt + ∆.
  We distinguish 2 practical scenarios as cross-silo FL and cross-device FL (Kairouz et al., 2019). In cross-silo FL, M is relatively small (i.e. M ≤ 100 ) and usually each client has a moderate or large amount of data (i.e. minmNm 1). As a consequence, all the clients participate in the learning process (i.e. S = [M ]). In each iteration a client computes locally a negative stochastic gradient g(θt, Ys) = − 1R ∑ y∈Rs ∇`(θt, y) of Ls(θt)/Ns, based on a uniform random subsample Rs ⊂ Ys of size R. In cross-device FL S is a uniformly random subset of [M ], and g(θt, Ys) = − 1Ns ∑ y∈Ys ∇`(θt, y) is the average negative gradient over Ys evaluated at θt. In this paper we will be focusing on the FedSgd aggregation rule corresponding to a stochastic gradient step with learning rate η, i.e., ∆ = η ∑ s∈S Ns N g(θt, Ys). Generally speaking, there are two sources of data that need privacy protection: the parameter θt and the updates {∆s}s∈S . In this paper we will develop algorithms for protecting {∆s}s∈S against inference attack or reconstruction attack, which will be defined later. Note that the protection of θts could be done via applying standard central DP techniques as in Bhowmick et al. (2018). To begin our discussion on suitably defined privacy models, we first review the local model of privacy.
  Local differential privacy Kasiviswanathan et al. (2011) we say a randomized algorithm A that maps the private data X ∈ X to some value Z = A(X) ∈ Z is -locally differentially private, if the induced conditional probability measure P (·|X = x) satisfies that for any x, x′ ∈ X and any Z ∈ Z:
  e− ≤ P (Z|X = x) P (Z|X = x′) ≤ e (2)
  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, we adopt the definition in Bhowmick et al. (2018):
  Reconstruction attack Bhowmick et al. (2018) Let π be a prior distribution over the data domain Y that encodes the adversary’s prior belief. We describe the generation process of privatized user data as Y → X → Z = A(X) for some (privacy-protecting) mechanism A. Additionally let f : Y 7→ Rk be the target of reconstruction (i.e., the adversary wants to evaluate the value f(Y )) and Lrec : Rk × Rk 7→ R+ be the reconstruction loss serving as the criterion. Then an estimator ζ : X 7→ Rk provides an (α, p, f)-reconstruction breach for the loss Lrec if there exists some z ∈ Z such that:
  P (Lrec(f(X), ζ(z))|A(X) = z) > p (3)
  The existence of a reconstruction breach provides an attack that effectively breaks the privatized algorithm for some output z. Hence to provide protection against reconstruction attacks, we need the following to hold:
  sup ζ sup z∈Z
  P (Lrec(f(X), ζ(z))|A(X) = z) ≤ p (4)
  When (4) holds, the mechanism A is said to be (α, p, f)-protected against reconstruction for the loss Lrec. In (Bhowmick et 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 participants except for the precise membership list. For such cases, only low 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 πf . 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.e. 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-private counterparts using high s. Despite the effectiveness of the LDP approach, the communication cost 1 is prohibitive. For models involving deep neural architectures, the number of parameters explodes to the order of millions. For each round, each client transmit O(dδ) 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 a reasonable level. We identify two main challenges in building practical privacy-preserving FL algorithms:
  Communication Efficiency The algorithm shall be communication efficient, measured in terms of bits transferred per client in a single round. High-dimensional compatibility It was shown in Duchi et al. (2018) that upon estimating a ddimensional vector, the locally private constraint incurs a multiplicative penalty of O(d/ 2) 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.
  1In general, there are two sources of communication cost in a 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 Konečnỳ et al. (2016) that uplink cost usually dominates downlink costs in FL settings. Hence in the scope of this work, we will refer to communication cost as uplink communication cost.
  Summary of contributions In this paper, we propose a 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 a 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-based learning framework.
  2. We make several improvements to the basic algorithm under the gradient-based learning scenario. Specifically, we attribute the estimation error of the base algorithm to perturbation error caused by privacy constraints, and quantization error. Then we utilize a gradient subsampling strategy to simultaneously reduce communication cost and improve private estimation utility. We also apply randomized rotation to reduce quantization error.
  3. We verify the performance of sqSGD on benchmark datasets using standard neural architectures like LeNet (Lecun et al., 1998) and ResNet (He et al., 2016), 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 a significant margin.
sections.heading: 2 RELATED WORK
sections.text: Communication-efficient FL Since its introduction in (Konečný et al., 2016), communication efficiency has been one of the central topics of FL (Konečnỳ et al., 2016; Kairouz et al., 2019). Konečnỳ 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 be viewed as a combination of the aforementioned approaches.
  Privacy-preserving FL As optimization via stochastic gradient methods remains the most representative task in federated learning, most privacy-preserving FL approaches are based on private SGD type algorithms like Abadi et al. (2016). McMahan et al. (2018) used a 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. Bhowmick 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 on privacy-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 et al., 2017) are 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 et al., 2020) performed privatized gradient sparsification via adopting randomized response techniques to select the most significant gradient dimension. Gradient quantization methods like QSGD (Alistarh et al., 2017) or TernGrad (Wen et al., 2017) 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, cpSGD (Agarwal et al., 2018) adopts the central DP model and vqSGD (Gandikota et al., 2019) allows local DP model.
sections.heading: 3 OUR MODEL
sections.heading: 3.1 BASE MECHANISM
sections.text: As a starting point, we base our communication efficient mean estimation algorithm on the stochastic k-level quantization(Suresh et al., 2017) scheme: We assume a uniform upper bound U on the `∞ norm of any individual gradients over the whole course of the FL process. The quantization procedure is described as follows: Let K ≥ 2 be the desired quantization level. We quantize the gradient to a sequence of points −U = B1 < B2 < . . . , < BK−1 < BK = U , where
  Bk = −U + 2(k − 1)U K − 1
  (5)
  The case for K = 2 corresponds to using only the endpoints {−U,U} for quantization. We will denote the quantization range as B = {Bk}Kk=1. For each dimension j ∈ [d] of the individual gradient Xj , we first locate Xj to one of the K bins via finding a k∗ such that Xj ∈ [Bk∗ , Bk∗+1) and round Xj to the boundary of the bin as:
  X̂j =
  { Bk∗+1 with probability k∗(Xj−Bk∗ ) 2U
  Bk∗ otherwise (6)
  Note that X̂j is an unbiased estimator of Xj . The quantization scheme reduces the communication cost to d log2K bits per round per client.
  Next we privatize X̂j by constructing a locally private unbiased estimator of X̂j (where we fix the randomness of the quantization step), thereby obtaining a locally private estimator of X with its value resides in Bd. To describe the privatization scheme we introduce some new notations: for ∀v1, v2 ∈ Bd, define M(v1, v2) = #{j : vj1 = v j 2} − #{j : v j 1 6= v j 2} where #C stands for the number of elements in the set C. For a given positive integer κ ∈ {0, . . . , d − 1}, let S(v;Bd) := {u :M(u, v) > κ} and S(v;Bd) := {u :M(u, v) ≤ κ}. The privatization procedure, which we termed PrivQuantK,∞, is summarized in Algorithm1. To state the privacy guarantee of PrivQuantK,∞, 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 a map from Y to a compact set C ⊂ Rr. For any absolutely continuous prior π on Y , we use πf to denote the induced prior on f . Let π0 be the uniform prior over C, we will be focusing on priors that belong to the following set:
  Pf (ρ0) = { π : sup
  y∈C log
  dπf (y) dπ0(y) ≤ ρ0
  } (7)
  where ρ0 is a non-negative number. The set Pf (ρ0) 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 fA(x) = Ax/ ‖x‖2 with A ∈ Rr×d an orthonormal matrix, i.e., AAT = Ir, and the reconstruction criterion is chosen as the `2 error Lrec(x, x′) = ‖x/ ‖x‖2 − x′/ ‖x′‖2‖ 2 2 . Theorem 1. For any K ≥ 2, Consider PrivQuantK,∞ as a mechanism parameterized by (κ, p). Let τ := dd+κ+12 e, and let (κ, p) be chosen such that the following relation holds:
  p 1− p × ∑τ−1 `=0 ( d ` ) (K − 1)(d−`)∑d
  `=τ ( d ` ) (K − 1)(d−`) ≤ e (8)
  then Z is an unbiased estimator of X , i.e. E(Z) = X , with randomness jointly over the quantization step and sampling step. Moreover, we have the following privacy guarantees:
  Inference attack protection PrivQuantK,∞(·, κ, p) is -locally differentially private.
  Reconstruction attack protection with k ≥ 4 and a ∈ [0, 1], PrivQuantK,∞(·, κ, p) is ( √ 2− 2a, ω(a), fA)-protected against reconstruction for
  ω(a) = √ 8 exp ( − (r − 1)a 2
  2
  ) exp( + ρ0) (9)
  The proof will be deferred to appendix A.1. Theorem 1 implies that, if the adversary aims at reconstructing a non-vanishing fraction of the private data with r = O(d), for small a that allows coarse reconstruction, we only need and ρ0 to be of smaller order than d to ensure that any reconstruction attack will not succeed with reasonable probability. Note for K = 2 levels and U = 1, algorithm 1 reduces to algorithm PrivUnit∞ in (Bhowmick et al., 2018).
  We may view the estimation error of Z (measured in terms of `2 risk) as 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 4), certain improvements are necessary to achieve high-dimensional compatibility.
  Algorithm 1 Private K-quantized `∞ Ball PrivQuantK,∞
  Require: X ∈ [−U,U ]d, κ ∈ {0, · · · , d− 1}, p ≥ 12 , τ = d d+κ+1 2 e. 1: Quantize each coordinate of X to B using (6) to obtain X̂ ∈ Bd. 2: Sample a random vector V as follows: with probability p, V is sampled uniformly at random
  from S(X̂;Bd); otherwise with probability 1 − p, V is sampled uniformly at random from S(X̂;Bd).
  3: Calculate normalizing factor
  m = p ( d−1 τ−1 ) (K − 1)d−τ∑d
  `=τ ( d ` ) (K − 1)d−l
  − (1− p) ( d−1 τ−1 ) (K − 1)d−τ∑τ−1
  `=0 ( d ` ) (K − 1)d−l
  return Z = 1m · V
sections.heading: 3.2 IMPROVING PRIVATIZATION UTILITY VIA SELECTIVE GRADIENT UPDATE
sections.text: PrivQuantK,∞ provides an 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 is 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 a fraction of the gradient dimensions, which could be regarded as significantly reducing variance at the cost of a small amount of bias. Such techniques are closely related to gradient compression that sends a few most significant gradient dimensions (Lin et al., 2018). Typically, gradient compression techniques require selecting top-k gradients measured in absolute magnitude (Lin et al., 2018; Aji & Heafield, 2017). A straightforward extension to the local private setting would be to perform private selection methods like exponential mechanism (Dwork et 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.
  Motivated by algorithm designs in distributed learning like random masking (Konečnỳ et al., 2016) and Hogwild! (Niu et al., 2011), we utilize a simple strategy, gradient subsampling, by randomly sample d̃ = brdc dimensions, where r 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 a few dimensions are selected. A more detailed study of this aspect is provided in appendix A.3.
sections.heading: 3.3 IMPROVING QUANTIZATION PERFORMANCE VIA RANDOMIZED ROTATION
sections.text: As shown in (Agarwal et al., 2018; Suresh et al., 2017), for a d-dimensional vectorX , the quantization error scales with ( maxj∈[d]X j −minj∈[d]Xj )2
  . To reduce quantization error, an effective way is to preprocess the data via randomized rotation, so as to make maxj∈[d]Xj − minj∈[d]Xj 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 we generate an orthogonal random matrix R ∈ Rd̃×d̃ and apply the linear transform to the individual gradients X̃ = RX on the client side, and apply inverse transform on the server side Z̃ = R−1Z. We adopt the method in (Agarwal et al., 2018; Suresh et al., 2017) to generate R that support fast matrix multiplication with O(d log d) time and O(1) space. Specifically, we generate R = 1
  d̃ HA where A is a random diagonal matrix with i.i.d. Rademacher entries (i.e.
  P(Aii = 1) = P(Aii = −1) = 0.5,∀i ∈ [d̃]), and H is a Walsh-Hadamard matrix (Horadam, 2012), defined recursively by the formula:
  H(21) = [ 1 1 1 −1 ] , H(2m) = [ H(2m−1) H(2m−1) H(2m−1) −H(2m−1) ] , (10)
  The randomized rotation operation is performed before quantization and privatization, therefore we project the vector X to an `2 ball of radius U before rotation. This would ensure the vector obtained after rotation has `∞ norm bounded by U as well.
  The final selective SGD updating process is summarized in algorithm 2. The randomized rotation and sparsification strategy have no effect on privacy level, hence the local update within a single round is -LDP. At the same time, communication cost was further reduced from O(d log2K) bits to O(d̃ log2K) bits per client.
  Algorithm 2 sqSGD: Selective Quantized SGD with local privacy guarantee
  Require: Training data {Yi}Mi=1, gradient norm bound U , privacy budge , sampling ratio r ∈ (0, 1), local correction factor α, β, learning rate η, batch size B.
  1: Find a (κ , p ) pair that satisfies relation (8) 2: Calculate the corresponding normalizing constant m as in algorithm 1 3: Set d̃ = 2blog2(rd)c, and using public randomness to generate a random matrix R ∈ Rd̃×d̃,
  according to the construction in (10) 4: Initialize model parameter θ0 and local residuals resi,0 = 0,∀i = 1, . . . , N 5: for t = 0, . . . , T − 1 do 6: Sample a batch of indices St ∈ [N ] with size B 7: for s ∈ S do 8: //* Client Side Update *// 9: Select a uniformly random subset of [d] with cardinality d̃, denoted as Ds,
  10: also let DCs denote [d]\D. 11: Calculate local (stochastic) gradient with respect to client data Xs,t = g(Ys,t, θt) 12: Clip the local gradient to the `2 ball with radius U 13: Accumulate and Apply rotation X̃s,t = R (resi,t[Ds] + βXs,t[Ds]) 14: Rotate and update local residual ress,t+1[DCs ] = ress,t[DCs ] + αXs,t[DCs ] 15: and ress,t+1[Ds] = 0 16: Calculate Zs,t = PrivQuantK,∞(X̃s,t, κ , p ) 17: Upload (Zs,t/m ,Ds) to the server 18: //* Server Side Update *// 19: Gradient update step θt+1 = θt −R−1 ηB ∑ s∈S Z dense s,t , where Z dense s,t is the d− dimensional 20: zero vector with indices in Ds replaced by Zs,t. return θT
sections.heading: 4 EXPERIMENTS
sections.text: In this section, we apply sqSGD to simulated FL environments, constructed via standard datasets MNIST (Lecun et al., 1998), EMNSIT (Cohen et al., 2017), and Fashion MNIST (Xiao et 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 a cross-silo FL environment consisting of a 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-110 architecture (1, 722, 224 parameters) on the FMNIST dataset. Since the main goal of 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 a 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
  of learning rate η = 0.001 and local correction factors α = 1.0, β = 1.0 across all experiments. We set the `2 norm bound of the gradients U = 10 as it works reasonably well. Note that we could use a more elegant distributed private estimation of the `2 norm bound via sending privatized magnitude evaluated at different points of the parameter space, i.e. via mechanisms like ScalarDP in Bhowmick et al. (2018). Finally, for a given privacy budget , we use the following method to determine the value of (κ , p ): We set κ to be the largest integer such that the value of the left hand side of (8) is smaller than or equal to e0.9 , and p = e 0.1
  1+e0.1 .
  Choice of privacy budget across all the experiments we align the choice = O( √ d) with respect to the additional risk factor O(d/ 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 goal is to evaluate more than O( √ d) 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 r = 0.5%. We vary the quantization level in the range {2, 8, 32} which corresponds to using {1, 3, 5} bits per client per dimension. The results are plotted in figure 1. 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 at r = 0.5% and quantization level at K = 16. For LeNet-5 architecture, we select from the set {200, 300, 400}, for ResNet-110 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.
  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∞ algorithm in Bhowmick et al. (2018)
  κ = 0. Although PM communicates real values, the multi-dimensional version of PM (Wang et al., 2019, Algorithm 4) samples a fraction of coordinates for perturbation hence we may view PM practically as a limited-communication mean estimation algorithm. For large d settings, we choose reasonably large values such that PM communicates raw perturbed gradients in b /2.5c dimensions. vqSGD Gandikota et al. (2019) vqSGD uses an communication-optimal distributed mean estimation algorithm that adopts vector quantization strategies. The per client communication cost of vqSGD is O(log 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 b times and server uses the average of b quantized gradients for aggregation. This makes the communication cost O(b log d). Note that in private settings this results in a caveat that privacy protection level is degraded under composition. In our experiments we will ignore this caveat and use variance reduction so 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 3 shows that sqSGD consistently outperforms PM by a significant margin across all tasks under various privacy levels. vqSGD obtains comparable performance with sqSGD in relatively smaller models and high-privacy regime (Note that vqSGD 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.3, and another study on the trade-off between quantization and subsampling in A.4. The results of additional experiments further justify the choice of sampling ratios and quantization levels in the above comparisons.
sections.heading: 5 CONCLUSION
sections.text: We studied privacy-preserving federated learning under the local differential privacy model. To achieve both communication efficiency and high-dimensional compatibility, we proposed a gradientbased 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 a significant margin.
sections.heading: A APPENDIX
sections.text: A.1 PROOFS
  Proof of theorem 1. Let u ∈ Bd and U ∼ Unif(Bd). The vector V ∈ Bd sampled as in algorithm 1, has p.m.f.
  p(v | u) ∝ {
  1/P(M(U, u) > κ) ifM(v, u) > κ 1/P(M(U, u) < κ) ifM(v, u) ≤ κ.
  The event that M(U, u) = κ when d+κ+12 ∈ Z implies that U and u match in exactly d+κ+1 2 coordinates; the number of such matches is (
  d (d+κ+1)/2
  ) . Computing the binomial sum, we have
  P(M(U, u) > κ) = 1 Kd d∑ `=d d+κ+12 e ( d ` ) (K − 1)(d−`)
  P(M(U, u) ≤ κ) = 1 Kd d d+κ+12 e−1∑ `=0 ( d ` ) (K − 1)(d−`)
  (11)
  Now we show unbiasedness via showing E[V | u = u] = m · u. We have
  E[V | u = u] = pE[U | M(U, u) > κ] + (1− p)E[U | M(U, u) ≤ κ]
  By rotational symmetry, it suffices to show:
  E[V 1 | u = u] = pE[U1 | M(U, u) > κ]︸ ︷︷ ︸ Υ1 +(1− p)E[U1 | M(U, u) ≤ κ]︸ ︷︷ ︸ Υ2
  For Υ1, we have:
  Υ1 = 1
  KdP(M(U, u) > κ) × d∑ `=τ u1(d ` ) (K − 1)d−` − ∑ w∈B\u1 w ( d ` ) (K − 1)d−`−1  = u1 KdP(M(U, u) > κ) × ( d− 1 τ − 1 ) (K − 1)(d−τ)
  Where in the second equality we used the fact that ∑ w∈B w = 0. Similar calculations yield:
  Υ2 = − u1 KdP(M(U, u) ≤ κ) × ( d− 1 τ − 1 ) (K − 1)(d−τ)
  Combining the preceding display with (11), we have:
  E[V 1 | u = u] = ( p ( d−1 τ−1 ) (K − 1)d−τ∑d
  `=τ ( d ` ) (K − 1)d−l
  − (1− p) ( d−1 dτ−1 ) (K − 1)d−τ∑τ−1
  `=0 ( d ` ) (K − 1)d−l
  ) × u1
  = mu1
  Next we show privacy guarantee.
  LDP guarantee As P(M(U, u) > κ) is decreasing in κ for any u, u′ ∈ Bd and v ∈ Bd we have
  p(v | u) p(v | u′) ≤ p 1− p · P(M(U, u ′) ≤ κ) P(M(U, u) > κ) = p 1− p × ∑τ−1 `=0 ( d ` ) (K − 1)(d−`)∑d
  `=τ ( d ` ) (K − 1)(d−`)
  The result follows by relation (8)
  Reconstruction protection guarantee the result follows by Bhowmick et al. (2018, Proposition 1) and the LDP guarantee.
  A.2 ON THE PRACTICALITY OF PRIVACY-PRESERVING 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 a single index with gumble noise. The bottleneck of this take is that it requires sampling from a 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 is 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/ to each dimension of the gradient vector. In practice, k is typically chosen at the order of hundreds. Since most of the gradients are very small in magnitude,to ensure reasonable noise requires a high budget to 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 ResNet110 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} × 10−3. 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. It is thus necessary to perform subsampling. However, using a 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 r log2K. 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 5. 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.