Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation
Authors: Wei-Ning Chen
Dan Song
Ayfer Ozgur
Peter Kairouz
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential Privacy
Federated Learning
Communication

Abstract: Privacy and communication constraints are two major bottlenecks in federated learning (FL) and analytics (FA). We study the optimal accuracy of mean and frequency estimation (canonical models for FL and FA respectively) under joint communication and $(\varepsilon, \delta)$-differential privacy (DP) constraints. We consider both the central and the multi-message shuffled DP models. We show that in order to achieve the optimal $\ell_2$ error under $(\varepsilon, \delta)$-DP, it is sufficient for each client to send $\Theta\left( n \min\left(\varepsilon, \varepsilon^2\right)\right)$ bits for FL %{\color{blue}(assuming the dimension $d \gg n \min\left(\varepsilon, \varepsilon^2\right)$)} 
and $\Theta\left(\log\left( n\min\left(\varepsilon, \varepsilon^2\right) \right)\right)$ bits for FA to the server, where $n$ is the number of participating clients.  Without compression, each client needs $O(d)$ bits and $O\left(\log d\right)$ bits for the mean and frequency estimation problems respectively (where $d$ corresponds to the number of trainable parameters in FL or the domain size in FA), meaning that we can get significant savings in the regime $ n \min\left(\varepsilon, \varepsilon^2\right)  = o(d)$, which is often the relevant regime in practice. 

We propose two different ways to leverage compression for privacy amplification and achieve the optimal privacy-communication-accuracy trade-offs. In both cases, each client communicates only partial information about its sample and we show that privacy is amplified by randomly selecting the part contributed by each client. In the first method, the random selection is revealed to the server, which results in a central DP guarantee with optimal privacy-communication-accuracy trade-offs.  In the second method, the random data parts from the clients are  shuffled by a secure shuffler resulting in a multi-message shuffling scheme with the same optimal trade-offs. As a result, we establish the optimal three-way trade-offs between privacy, communication, and accuracy for both the central DP and multi-message shuffling frameworks.

Privacy Amplification via Compression: Achieving the Optimal Privac--Acuraay-Commmiaaa Trade-offs in Distributed Mean Estimation
Wei-Ning Chen Stanford University wnchen@stant ord. edu
Dan Song Stanford University songdan@stanford edu
Ayfer Özgür Stanford University aozgurøstanf ord edu
Peter Kairouz Google Research kair kairouz@google.co com
Abstract
Privacy and communication constraints two major bottlenecks in federated learning (FL) and analytics (FA). We study the optimal accuracy of mean and frequency estimation (canonical models for FL and FA respectively) under joint communication and (c, 5) ddifferreet privacy (DP) constraints. We consider both the central and the multi-message shuffled DP models. We show that in order achieve the optimal & error under (e, 8)-DP, it is sufficient for each client to send θ (n min (c, {²)) bits for FL and (log (n min (s,=")) bits for FA to the server, where the number of participating clients. Without compression, each client needs (d) bits and O (log d) bits for the mean and frequency estimation problems respectively (where d corresponds to the number of trainable parameters in FL the domain size in FA), meaning that we can get significant savings in the regime n min (e, o(d). which often the relevant regime in practice.
We propose two different ways to leverage compression for privacy amplification and achieve the optimal privacy- conruncccommniitiioooooooa each client communicates only partial information about its sample and we show that privacy is amplified by randomly selecting the part contributed by each client. In the first method, the random selection is revealed to the server, which results in a central DP guarantee with optimal privacy communictimiiiitionnnn cuamuuicatioonaaccuaayyy trade-offs. In the second method, the random data parts from the clients are shuffled by a secure shuffler resulting in multi-message shuffling scheme with the optimal trade- offs. As a result, we establish the optimal three-way trade-offs between privacy, communication, and accuracy for both the central DP and multi-messee mallliiessa shuffling frameworks.
trade-offs. In both cases,
Introduction
In the basic setting of federated learning (FL) 68 64, 61 and analytics (FA), server wants to execute specific learning or analyties task on raw data that kept on clients' devices. Consider, for example, model updates in FL. or histogram estimation in FA, both of which can be modeled as distributed mean estimation problem. Clients communicate targeted messages the server and the privacy of the users' data is ensured (in terms of explicit differential privacy (DP) (38] guarantees) by adding carefully calibrated noise the computed mean at the server before releasing to downstream modules (e.g., the server computes the average model update and corrupts it with the addition of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

noise). This is called the trusted server or central DP model, as it entrusts the central server with privatization and is one of the most common ways in which federated learning and analytics are implemented today |
In this paper, we ask the following question: given that the server needs to privatize the mean, can the clients communicate "less information" to the server? More precisely, can we leverage the fact that the server only needs to output a noisy (approximate) estimate of the mean reduce the communication load without sacrificing accuracy? In recent years, there has been significant interest in the central DP model [ as well as communication efficiency and privacy for FL and FA under
different models, including local DP 78 63 58
80
17
6 16 [2], shuffle 40 43
and distributed
DP [9 59 & 33 34;; however, this basic question has remained open.
One natural way to reduce communication is to have clients communicate only partial information about their samples. For example, in the case of model updates, each client can update only a subset of the model coefficients. In histogram estimation, information about a client's sample can be "split" into multiple parts, and the client can communicate only one part. However, this results in less information at the server, or effectively fewer samples to estimate the target quantity, e.g., each model coefficient is now updated only by subset of the clients. A quick calculation reveals that this increases the sensitivity of the estimate to each user's sample and therefore requires the addition of larger noise at the server to achieve the same privacy level. Hence, reducing communication reduces accuracy for the same privacy guarantee.
We circumvent this challenge with simple but insightful observation: when each client communicates only partial information about its sample, we can amplify privacy by randomly selecting the part contributed by each client. This random selection is hidden from downstream module which has only access to the estimate revealed by the server, which leads to privacy amplification. Privacy amplification by subsampling has been studied in [66] [4] but usually refers the selection of random subset of the clients (from a larger pool of available clients). In our case, it is the "piece of information" " that is randomly selected at each client. We call this gain privacy amplification via compression as it emerges from the fact that each client does not fully communicate its sample. We use establish the optimal communication- privacy-accures this same type of gain cannot be leveraged in the local DP model where the server is untrusted. The server needs to know the random selection at each client to construct an estimate. Indeed, in the local DP model, the privacy-accuracy trade-off is known to be significantly worse than the central DP model (see Table
trade-off for central DP. Note that
This naturally leads to follow-up question: can we leverage privacy amplification via compression and achieve the same three-way trade-off by using secure aggregation (33 and shuffling 44) type models which hide information from the server? For secure aggregation, the three-way trade-off has been studied in 3I] and the communication cost is significantly larger than the communication cost for central DP proved in this paper (see Table [I) For shuffling. the optimal communication cost has been posed as an open problem in (31]. We resolve this problem by showing that the optimal central DP trade-off can also be achieved with
shuffling scheme, establishing the optimal communication cost. (We note that a similar result has been concurrently and independently proved in [54] under the shuffle DP setting.) As before, our scheme leverages a privacy amplification gain. Each client communicates partial information about its sample; the identity of the message is erased by the secure shuffler, and hence the untrusted server does not know which part is contributed by each client. We show that to achieve the optimal trade-off, it is critical for each client to split its information into multiple messages and employ multiple shuffling rounds by carefully splitting the privacy budget across different rounds. In contrast, the linearity of secure aggregation requires all participating clients to communicate consistent information (same parts), hence precluding privacy amplification by compression. See Tablc[] for a detailed comparison.
Our contributions. We study distributed mean and frequency estimation as canonical building blocks for FL and FA. We consider both the central DP and the multi-message shuffling models. We characterize the order-optimal estimation and provide an achievable scheme for frequency estimation (in Appendix (A] under the central DP model. Our results reveal that privacy and communication efficiency can be achieved simultaneously with no additional penalty for accuracy. In particular, we show that Ô (n min (c,e²)
trade-offs for distributed mean
We assume a trusted service provider who applies the DP mechanism faithfully. This can be enforced by implementing the DP mechanism inside of remotely attestable trusted execution environment [II]

---

Communication (bits)
Eg error
Local DP
32
(
min(=*, .))
Distributed DP (with SecAgg
33
Ô (n² min (e,=²))
n min(s* ,6)
Central DP (Theorem 4.4
Ô (n (e,
0
d log of n min(c" (,aiu(c"",))
Shuffle DP (Theorem 5.3
(54]
Ô (n log(d) min (c,
0
13 min(e".e)
Table 1:
Comparison of the communication costs of & mean estimation under local, distributed, central, and shuffle DP (with 5 terms hidden). Compared to local DP, we see that error under central DP decays much faster (e.g., 1/n2 as opposed to 1/n); compared distributed DP with secure aggregation, our schemes achieve similar accuracy but saves the communication cost by a factor of n.
and Ô (log (n min (e) bits of (per-client) communication are sufficient to achieve the order- optimal error under (e, 6p-rivacy for mean and frequency estimation respectively, where is the number of participating clients. Without compression, each client needs ((d) bits and log d bits for the mean and frequency estimation problems respectively (where d is the number of trainable parameters in FL or the domain size in FA), which means that we can get significant savings in the regime nE? = o( d)) (assuming = = ((1). We note that this is often the relevant regime not only for cross-silo but also for cross-device FL/FA. For instance. in practical FL, d usually ranges from 10 to 10 and the per-epoch sample size, is usually much smaller (e.g.. of the order of 103 to 109). For distributed mean estimation, we show that the central DP trade-off can also achieved with a multi-message shuffling scheme (within a log d factor in communication cost). Hence our paper establishes the three-way trade-off between privacy, communication, and accuracy for both the central DP and multi-message shuffling frameworks, both of which were open problems in the prior literature. Compared with local DP where bit is sufficient when e O(1), this shows that central/shuftling DP has larger communication cost but achieve much smaller error (by factor of n) and hence is usually preferable in practical applications. Compared with distributed DP where the server aggregates local (encoded) messages with secure multi-party computation (c.g., [23 g 34]), we can improve the communication cost by a factor of n. therefore showing that the communication cost can be reduced with trusted server shuffler. We summarize the comparisons of our main results to local and distributed DP in Table
Notation. Throughout this paper, use [m]] denote the set of {1, .... m } for any E N. Random variables (vectors) (X,, are denoted as X We also make use of Bachmann-Landau asymptotic notation, i.e., O, Ωt w, and O.
2 Problem Formulation
We first present the distributed mean estimation (DME) 74 problem under differential privacy. Note that DME is closely related to federated learning with SGD (or similar stochastic optimization methods, such as FedAvg (68). where in each iteration, the server updates the global model by noisy mean of the local model updates. This noisy estimate is typically obtained by using DME scheme, and thus one can easily build distributed DP-SGD scheme (and hence a private FL scheme) from differentially private DME scheme. Moreover, shown in 49], as long as we have an unbiased estimate the gradient at each round, the convergence rates of SGD (or DP-SGD) depend on the lg estimation eиror.
Distributed mean estimation. Consider n clients each with local data x; Rdd that satisfies |æxl|| S C for some constant C > 0 (one can think of x; as a clipped local gradient). A server wants to learn an estimate ji of the mean su(=") A 1 Σ, x; from x² = (aI,.... rn) after communicating with the n clients. Toward this end, each client locally compresses 2; into a b-bit message Y, enc; (z+) E y through local encoder enc; X' + y (where | s 2 and sends it to the central server, which upon receiving y (YI..... Yn) computes an estimate = dec (Y*) that satisties the following differential privacy:
3

---

Definition 2.1 (Differential Privacy). The mechanism ji is (5. private for any neighboring datasets x" == (2,, "y,, F.). x == (II,... Typ Fn), and measurable S y. Pr E " Pr E S S|x" 6
where the probability is taken over the randomness of jt.
Our goal is to design schemes that minimize the lg estimation error:
min (ence (-)...,,ncs enc,, de)dec)))) max E || (enc: (21). ..., enc,,,,,,)),,,.)))))) m(x"))1]
subject to b-bit communication and (c, 5)- constraints.
Distributed frequency estimation. Similarly, frequency estimation can also be formulated as mean estimation problem but with sparse (one-hot) vectors. Let each user i hold item xy in a size d domain X. The server aims to estimate the histogram of the n items. Without loss of generality, we can assume that X' := {Ei, .... }d} E {0, 11 (where ej is the j-th standard basis vector in R²), i... each item is expressed as a one-hot vector. Then, the histogram of the n items can be expressed as (x*)= = >ie[n] Ti. Similar to the mean estimation problem, clients locally compute and then send Y; = enc; (xz) E y (for some y' such that | < 22). and the central server computes the estimate ft dec (y") Our goal is to design schemes that minimize the &2 or l erro
(ency min (-))ec()))
max E [|] (enc) (21), ...., enc, (Ix)) - x [I]
subject communication and DP constraints (where ||-|| can be e or (
3 Related Works
Federated learning and distributed mean estimation. Federated learning 64 68 60 emerges as decentralized machine learning framework that provides data confidentiality by retaining clients' raw data on edge devices. In FL, communication between clients and the central server can quickly become a bottleneck [68] so previous works have focused compressing local model updates via gradient quantization 668 10. 48, 74,
79 77 (24), sparsification 18 56 41 To further enhance
data security, FL. is often combined with differential privacy [38 9. Among these works, ?? ] also employs gradient sparsification (or gradient subsampling) to reduce the problem dimensionality. However, the sparsification takes place after the aggregation of local gradients, so the randomness introduced during sparsification cannot be leveraged to amplify the differential privacy guarantee. As a result, this approach leads suboptimal trade-off between privacy and communication compared to our scheme.
Note that in this work, we consider FL (or more specifically, the distributed mean estimation) under a central- DP setting where the server is trusted, which is different from the local DP model
63
37
70 76 22 32 and the distributed DP model with secure aggregation 23 21 59
key step in our mean estimation scheme pre-processing the local data via Kashin's 's representation [67]. While various compression schemes, based on quantization, sparsification, and dithering have been proposed in the recent literature, Kashin's 's representation has also been explored in a few works for communication efficiency [47 73 29 71 and for LDP [42) and is particularly powerful in the case of joint communication and privacy constraints as it helps spread the information in a vector evenly in every dimension.
Distributed frequency estimation and heavy hitters. Distributed frequency estimation (a.k.a. histogram estimation) is another canonical task that has been heavily studied under a distributed setting with DP. Prior works either focus on 1) the local DP model with or without communication
constraints, e.g., 20
19
25
26
57 (under an for loss for heavy hitter estimation) and [58] 80) 76
6. 32 constraints 38,
46
72
45
(under an f or Eg loss), or 2) the central DP model without communication
36) As suggested in (37 3 2 4 16), compared to central DP, local DP models usually incur much larger estimation errors and can significantly decrease the utility. In this work, we consider central DP but with explicit communication constraints.
52
65
27
3
Note that the & error corresponds to the total variation distance between the true and estimated frequency vectors.

---

Local DP with shuffling. A recent line of works 40 35 showing that one can significantly boost the central DP guarantees by randomly shufiling local (privatized) messages. In this work, we show that the same shuffling technique can be used to achieve the optimal central DP error with nearly optimal communication cost. Therefore, we can obtain the same level of central DP with small communication costs while weakening the security assumption: achieving the optimal communication cost (under central DP) only requires a secure shuffler (as opposed to a fully trusted central server).
12
51 considers shuffle-DP. 45 50
4 Distributed Mean Estimation
In this section, we present mean estimation scheme that achieves the optimal Ög under (e, 6)- while only using Ö(n=²) bits of per-client communication.
C2d n=
error
We first consider a slightly simpler, discrete setting with foo geometry (as opposed to the la mean estimation stated in Section 2 assume each client observes I; E ( cf where >> 0 ís a constant, and a central server aims to estimate the mean 1 (x*) == n -i=1 d; by minimizing the &y error subject to the privacy and communication constraints. We argue later that solutions to the above foo problem can be used for lg mean estimation by applying Kashin's 's representation.
To solve the aforementioned &oo mean estimation problem, first observe that each client's local data can be expressed in d bits since each coordinate of x; can only take values in (c,-c). To reduce the communication load to o(d) bits, each client adopts the following subsampling strategy: for each coordinate j E [d]. client chooses to send (j( to the server with probability y We assume that this subsampling step is performed with a seed shared by the client and the serve [ hence the server knows which coordinates are communicated by each client. Therefore upon receiving the client messages, it can compute the mean of each coordinate and privatize it by adding Gaussian noise. The key observation we leverage is that the randomness in the compression algorithm can be used to amplify privacy or equivalently reduce the magnitude of the Gaussian noise that is needed for privatization. Note that such randomness needs to be kept private from an adversary as the privacy guarantee of the scheme relies on it.
We summarize the scheme Algorithm I and state its privacy and utility guarantees in the following theorem.
Algorithm 1 Coordinate Subsampled Gaussian Mechanism (CSGM)
Theorem 4.1 (lxc, mean estimation.). Let
Input: users' data Ii, In. sampling parame- ters y == b/d, DP parameters (c.
T1 In E [-c,e] e)d and e, > O. There exists
a
Output: mean estimator p.
2 (olog(L/0) n=ng
(dllog(d/) + +e) log(d/6) n²=²
for user [r|] do
d =
for coordinate j E [d] do Lid.
(1)
Draw Zi, ~ Bern(7). if Zz.j Send (j) to the server. end if end for
such that Algorithm is (c, DDD and the Ez
1hen
estimation error of ja is most
de²
E |l
m12]
+ do²
ny
end for
o (de de
+ d lo (d/( nb
for coordinate j E [d] do
(2)
nb2
Server computes the average A ny En xx( + NN, o2), where o² is
2 (log(()) + + log(d/0)
1
n²
computed according to (I) in Theorem 4.1 end for Return: fa == (ix, fu2, ..., Pa).
In addition, the (average) per-client communica- tion cost yd = b bits, and Algorithm Algorithmnyields an unbiased estimator of p.
Remark 4.2 (Unbiasedness). Note that for mean estimation, we usually want the final mean estimator to be unbiased since standard con- vergence analyses of SGD [49] require an unbiased estimate of the true gradient in each optimization
'I practice such randomness can be agreed by both sides ahead of time, or it can be generated by the server and communicated to each client.
5

---

round. Given that our proposed mean estimation schemes (Algorithm and Algorithm ii the next section) are all unbiased, we can combine them with SGD/federated averaging and readity apply 49 to obtain a convergence guarantee for the resulting communication-effiei DP-SGD.
For the l mean estimation task formulated in Section we pre- pre-procsss local vectors by first computing their Kashin's 's representations and then performing randomized rounding 62 75 42
Specifically, if v; has '2 norm bounded by C, then its Kashin's representation (with respect to a tight
frame K E dd D where D = ((d)) h; has bounded &oc norm: || S c== (fa) and satisfies
T; Kē. This allows us convert the l2 geometry an Loo geometry. Furthermore, by randomly rounding each coordinate of ē; to {-c, c} (see for example (32)). , we can readily apply Algorithm and obtain the following result for l2 mean estimation as a corollary:
Corollary 4.3 (&2 mean cstimation). Let T1,..., E (C( (i.e., | S C for all i E [n]) Then for any 6 > O, Algorithm conitthm@cmmbiin combined with Kashin's representation and randomized rounding yields an (D unbiased estimator for with lg estimation error bounded by
dC² nb
C2d log(1/0) (d(log(d//)) + log(d/o) n2g2
(4)
n2
(a)
(1)
The first term (a) in the estimation error in Corollary 4.3 is the error due to compression, and the second term (3) is the error due to privatization (which order-optimal under (c, 6)DD up to
an additional log(d/6) factor as we discuss Section 4.2 In particular, we ignore the poly-
logarithmic terms and assume & = 0(1), the privatization error (3) can simplified to Ô dCa
which dominates the total Eg error when áig max (n=", vdz) i.c. in this regime the total &g error is order-wiid equal to the optimal centralized DP error (3). This implies that no more than b Ω mmax nne?, vde) bits per client are needed to achieve the order-optimal & error.
In the next section, we introduce a modification to Algorithm 1, which allows the removal of the Ω Vdee term in the communication cost.
4.1 Himension-free communication cost
In order to remove the dependence on the dimension d in the communication cost Ôs (max (ne², Vdd)) from the previous section, we need improve the performance of scheme in the small- regime ne² = o(vde.. Equivalently, we want to be able to achieve the centralized DP performance by using only b = f2, (ns") bits per client when ns = o(v Assuming E Rs 1, note that this implics that the total communication bandwidth of the system nó = o(d). i.c. the server receive information about at most nà n² o(d) coordinates. We show that in this regime the performance of the scheme can be improved by a priori restricting the server's attention to subset of the coordinates.
We make the following modification to Algorithm 1 before performing Algorithm I the server randomly selects d' x O (min(d, n)²²)) coordinates and only requires clients to run Algorithm 1 on them. We present the modified scheme in Algorithm and summarize its performance in Theorem 4.4
Similarly, we can obtain the following & mean estimation via Kashin's 's representations:
Theorem 4.4 (&2 mean estimation.). Let II,,.,, (C(C) (i.e., ||æi||2 I C for all E [m]).
e, 8 > O, and d' min dd, nb, [log( log(o/7)))))))) Then there exists
n,2a
o² = (
C2 1og(1/5) (C)log(1/0) C2d'(log(1/0) +e log(d' (6)
(5)
d'n2n²
dn?=²
such that Algorithm 2 (e, 8)-DP. In addition, the (average) per-client communication cost yd bits, and the lg estimation error is at most
(Codlog(d/8) nb
('dlog(d/))(oo((/// +&)
max
n²g2
(6)

---

Corollary 4.5, As long as b l
ng² ToR(1/6)+5 ) the lg error of mean estimation
C C'dlog(d/O)(log(//// +
o
n²=²
As suggested by Corollary
4.5 we see that when bits per client are suf-
& O(1), b = 52 (ne²)
Algorithm 2 CSGM with Coordinate Pre-selection
ficient to achieve the order-optimal Ōş ctd
Input: users' data 31, ... Tn. coordinate selec- tion d' S d, sampling parameters == b/d', . DP parameters (s,
error (even in the small sample regime n S d). i.e. the communication cost of the scheme is in- dependent of the dimension d.
Output: mean estimator j..
Randomly select d' coordinates J [j. C [d].
4.2 Lower bounds
for user [n]] do
Pre-procsd Pre-processing z; by restricting it on J: 2,(J) = (.,
In this section, we argue that the estimation er-
ror in Theorem 4.4 is optimal up to an log (d/5) factor. Specifically, Theorem 5.3 of [31 shows that any b-bit unbiased compression scheme will Cad
end for
Apply CSGM (Algorithm) 1 on (T), [n]:
As <- CSGM (za(J), [n]).
incur Ω problem (even when privacy is not required). This matches the first term in (6) up to loga-
error for the & mean estimation
for j E [d] do
nb
if j E J then
P Az(j).
rithmic factor.
else
P 0. end if
On the other hand, the centralized Gaussian mechanism (under central (E,8)-DP) achieves
end for Return: == (g f1, o P22.... .... Pa).
O
(1d) MSE 15 (which is order- n"
d
optimal in most parameter regimes; see the
lower bounds in Theorem 3.1 of (28) or Propo-
sition 23 of [30). Hence, we can conclude that the total communication received by the server has to be at least ?(n==?) bits in order to achieve the same error as the Gaussian mechanism. Therefore, the (average) per-elient communication cost has to be least (nn=²) bits. Hence we conclude that Algorithm 2 is optimal (up a logarithmic factor).
For completeness, we state the communication lower bound the following theorem:
Theorem 4.6 (Communication lower bound for mean estimation under central DP). Let æ1, In (C)))). Let Yi.... Y, be any b-bit local reports generated from a (possibly interactive) compres-
sor and be unbiased in the sense that E. 1 Yi = Σ, F.. Then if E || Σ, Y, + + x. 11 $
O (Caloe(y/0)) it holds that b = ne
n²e2
[og(1/5)
Finally, we remark that the logarithmic gap between the upper and lower bounds may be due to the specific composition theorem (Theorem III.3 of (9) we use in proof, which is simpler to work with but possibly slightly weaker. However, in our experiments, we compute and account for all privacy budgets with Rényi DP theoretical analysis.
69 82
and hence can obtain better constants compared to
5 Achieving the Optimal Trade-off via Shuffling
In Section and Section A we see that the communication cost can be reduced (Ō (ne?) for mean estimation and Ô (log ([n=²1)) for frequency estimation) while still achieving the order-wise optimal error, long as the server trusted. On the other hand, when the server untrusted, B3 S1
show that optimal error under (s, 8D- can be achieved with secure aggregation. However, the communication cost of these schemes is Ô (n= bits per client for mean estimation and Ô (ns) bits per client for frequency estimation. This corresponds to factor of n increase for mean estimation and exponential increase for frequency estimation. In this section, we investigate whether the
7

---

optimal communication cummmuiiatto-acccuraayy -privacy trade-off from the previous sections can be achieved when the server is not fully trusted.
In this section, we show that if there exists a secure shuffler that randomly permutes clients' locally privatized messages and releases them to the server, can achieve the nearly optimal (within log d factor) central-DP error in mean estimation with Ô (ne?) bits of communication. We note that similar result has been proven in a concurrent work (54). Specifically, we present a mean estimation scheme that combines a local-DP mechanism with privacy amplification via shuffling by building on the following recent result [40 43]:
43 Let M, be independent (Eo. 0)-LDP mechanism for each E [n] with Eo S 1 and π. be random permutation of [n). Then for any ò E [0, 1] such that S log Tolog(270] ) the M, M,, (F(x()))))) is (E, for some such that mechanism S (Z1....,, Fn) ++ (M1 (Ix(1))
Lemma 5.1
==0 ((0 10 (log(1/6) vn
Privacy analysis. With the above amplification lemma, we only need to design the local randomiz- ers M; that satisfy LD-LDP. Note that the above lemma is only tight when O(), thus restricting the (amplified) central = O(1/ VT), i.c. to be very small. To accommodate larger E, users can send different portions of their messages the server in separate shuffling rounds. Equivalently, repeat the shuffled LDP mechanism for T = O ([n=²]) rounds while ensuring that in each round, clients communicate an independent piece of information about their sample to the server. More precisely, within each round, each client applies the local randomizers M; with per-round local privacy budget Eq (1) and sends an independent message to the server. This results in (amplified) central O(1/
per round, which after composition over T = O ([ng? rounds leads to e-DP for the overall scheme as suggested by the composition theorem 58 We detail the algorithm in Algorithm 4 in Appendix F
(n1/vn)-Dn -n)-DnDDD
Communication costs. The communication cost of the above 7-round scheme can be computed as follows. As shown in (32), the optimal communication cost of an LD-LDP mean estimation is O ([Eol) bits. In addition, the (private-coin) SQKR scheme proposed in [32] uses O ([éo] log d) bits of communication (we state the formal performance guarantee for this scheme in Lemma 5.2 where compression is done by subsampling coordinates and privatization is performed with Randomized Response. Therefore, since the per-round Eo O(1), the total per-client communication cost is O (ne² log d), matching the optimal communication bounds in Section 4 within a log d factor.
Lemma 5.2 (SQKR (32). For all Eo > 0, bo > 0, there exists a (Eo. LDP mechanism using by log(d) bits such that j unbiased and satisfies E [Il) P (x") (x") )1 =
edd
minin (cā-ro.5o)
Finally, we summarize the performance guarantee for the overall scheme (Algorithm 4) in the following theorem.
Theorem 5.3 (62 mean estimation). Let I1, E B2(CC) (i.e., || S C for all i E [n]). For all & > 0,b > O, > 30, and 8 E (6min: 1] where 8eni = =0 log(d) ). Algorithm combined with Kashin's 's representation and randomized rounding is 5E,5)-DP, uses more than b bits of communication, and achieves
(o (log(d) log(b/ (logg/))))(( + +0)) ())
E - (=*)) =0
<bb Remark 5.4. As opposed to previous schemes Algorithm the shuffled SOKR requires some condition on ö, i.e., d E [8min 1] due to the specific shuffling lemma we used. In practice, however, 8min small due to the exponential dependence on n. The order-wise optimal error of O min(E",))
n²=²
C²d
achieved, up to logarithmic factors, when b = 26 log(d) min (s²,=)).
Remark 5.5. We note that similar ideas of private mean estimation based on shuffling have been studied before, see, for instance, [53]. However, these papers do not use the above privacy budget splitting trick over multiple rounds, so their result is only optimal when & is very small. The above scheme can be viewed as multi-message shuffling scheme [35 STV, and in particular, can be regarded as a generalization of the scalar mean estimation scheme
135 to d-dim mean estimation.
8

---

CSGM (n 500, d 500, 5 1e 6)
estimation 500, d 1000,
0.1 bia
10"
(200
2252
101
2000 c80
10 180)
10"
MSE
MSE
2074
C00
10-1
5009
10"
10"1
10-3
Privacy (E)
2.0
0.25
Privacy (E)
1.00
Figure 1: MSEs of CSGM (Algorithm 1 and shuffle LDP schemes.
6 Experiments
In this section, we empirically evaluate our mean estimation scheme (CSGM) from Section examine its wtt.-accrrccccommmnaattt trade-off, and compare with other DP mechanisms (including the shuffling-basee based mechanism introduced in Section 5).
Setup. For given dimension d, and number of samples n, we generate local vectors X, R Lid. 1 (2- Ber(0.8) 1) where Ber(0.8) is Bernoulli random variable with ~ va
as follows: let Xj)
bias = 0.8. This ensures >x S 1/vd and |Xill2 S 1, and in addition, the empirical mean (X*) == Σ; X; does not converge to O. Note that as our goal is to construct an unbiased estimator, we did not project our final estimator back to the foo or l2 space as the projection step may introduce bias. Therefore, the &g estimation error can be greater than 1. We account for the privacy budget with Rényi DP (69) and the privac--mplliicatiie by subsampling lemma [2
and convert
Rényi DP to (e, 0)D via 30
trade-off' of CSGM. In the first experiment (left of Figure D we apply [anrrithh[[iiht different sampling rates y, which leads to different communication budgets (b 00=1 yd). Note that when y = 1, the scheme reduces to the central Gaussian mechanism without compression. In Figure]] we see that with a fixed communication budget, CSGM approximates the central (uncompressed) Gaussian mechanism in the high privacy regime (small E) and starts deviating from it when exceeds a certain value. In addition, that value of depends only sample size n and the communication budget and not the dimension as predicted by our theory: recall that the compression error dominates the total error, and hence the performance starts to deviate from the (uncompressed) Gaussian mechanism when b = o(ne?), a condition that is independent of d. Observe, for example, that when b 50 bits, the Gaussian mechanism starts outperforming CSGM at 2 0.5 for both d 500 and = 5000. Hence, for E se 0.5 CSGM is able to provide 10X compression when d = 500, but 100X compression when d 5000 without impacting MSE.
shvaay-accuracy-ccommiii
Comparison with local and shuffle DP. Next, we compare the CSGM with local and shuffled
DP for d = 30 and n = 500. For local DP, we consider the private-coin SQKR scheme introduced in Section 5 which uses (flo d] + 1) = 11T bits for T shuffling rounds and DJW [37] which is known to be order-optimal when apply the amplification lemma in 43 to find the corresponding local Eo (see Section S for more details) and simulate both SQKR and DJW as the local randomizers.
((1) (but is not communication-effcccnnn))) For shuffle-DP, we
The MSES of all mechanisms are reported the right of Figure ! communication budget (say, 10 bits), the practical performance of CSGM significantly outperforms shuffled-DP mechanisms, including the shuffled SQKR and DJW, eventhough they have the same order-wise guarantees theoretically. In addition, the amplification gain of single-round shuffling diminishes fast as & increases. Indeed, when 0.8, we observe no amplification gain compared to the pure local DP.
Our results suggest that for fixed

---

7 Limitations and Future Work
While we have characterized the (nearly) orderwise optimal trade-offs under central and shuffled DP, it remains unclear whether the pre-constants can be further sharpened, potentially enhancing the practical applicabiliity of these approaches. Furthermore, our analysis is based on a classical privacy amplification technique. By employing more advanced accounting methods, it might be possible to shave off the logarithmic factors.
Acknowledgements
This work supported in part by NSF Award # CCF-2213223.
10

---

References
[1] M. Abadi, A. Chu, I. Goodfellow, H. McMahan, Mironov, K. Talwar, and Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pages 308-318, 2016.
[2] Acharya, C. Canonne, and H. Tyagi. Inference under information constraints II: Communi- cation constraints and shared randomness. arXiv preprint PrXiv:190S.08302 2019.
[3] J. Acharya, C. L. Canonne, and H. Tyagi. Inference under information constraints: Lower bounds from chi-square contraction. In Conference on Learning Theory, pages 3-17. PMLR, 2019.
[4] J. Acharya, C. L. Canonne, and H. Tyagi. General lower bounds for interactive high-dimensional estimation under information constraints. arXiv preprint arXiv:2010.0656; 2020.
[5] J. Acharya and Z. Sun. Communication complexity in locally private distribution estimation and heavy hitters. In International Conference on Machine Learning, pages 51-60, 2019.
[6] Acharya, Z. Sun, and H. Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1120-1129, 2019.
[7] Acharya, Z. Sun, and H. Zhang. Differentially private Assouad, Fano, and Le Cam. In Algorithmic Learning Theory, pages 48-78. PMLR, 2021.
[8] N. Agarwal, P. Kairouz, and Z. Liu. The Skellam mechanism for differentially private federated learning. Advances in Neural Information Processing Systems, 34:5052-5064, 2021.
[9] N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan. cpSGD: Communication- efficient and lfffeerentiaall-priiattt distributed sgd. In Advances in Neural Information Processing Systems, pages 7564-7575. 2018.
[10] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-effciennt sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems 30, pages 1709-1720, 2017.
[11] J. Allen, B. Ding, J. Kulkarni, H. Nori, O. Ohrimenko, and S. Yekhanin. An algorithmic framework for differentially private data analysis on trusted processors. Advances in Neural Information Processing Systems, 32, 2019.
[12] V. Balcer and A. Cheu. Separating local & shuffled differential privacy via histograms. arXiv preprint arXiv: 1911.06879, 2019.
[13] V. Balcer and S. Vadhan. Differential privacy on finite computers. arXiv preprint 17X1v:1009.05330 2017.
[14] B. Balle, G. Barthe, and M. Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
[15] B. Balle and Y.-X. Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 394-403. PMLR, 2018.
[16] L. P. Barnes, W.-N. Chen, and A. Ozgur. Fisher information under local differential privacy. arXiv preprint arXiv:2005.10783 2020.
[17] L. P. Barnes, Y. Han, and A. Ozgur. Lower bounds for learning distributions under communica- tion constraints via fisher information, 2019.
[18] L. P. Barnes, H. A. Inan, B. Isik, and A. Ozgur. rTop-k: A statistical estimation approach to distributed SGD, 2020.
[19] R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta. Practical locally private heavy hitters. In Proceedings of the 31 International Conference on Neural Information Processing Systems, NIPS' 17, page 2285-2292 Red Hook, NY, USA, 2017. Curran Associates Inc
11

---

[20] R. Bassily and A. Smith. Local, private, efficient protocols for succinct histograms. In Proceedings of the Porty-Seventh Annual ACM Symposium on Theory of Computing, STOC 11, page 127-135, New York, NY, USA, 2015. Association for Computing Machinery.
[21] J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1253-1269, 2020.
[22] A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers. Protection against recon- struction and its applications in private federated learning. arXiv preprint 2018.
[23] K. Bonawitz, Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. Practical secure aggregation for federated learning on user-held data. arXiv preprint 1rXiv:161.00444 2016.
[24] M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. P. Woodruff. Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1011- 1020, 2016.
[25] M. Bun, J. Nelson, and U. Stemmer. Heavy hitters and the structure of local privacy. In Proceedings of the 37th ACM SIGMOD-SIGAA SISASIAAAT-SIAI Symposium on Principles of Database Systems, SIGMOD/PODS '18, page 435 447, New York, NY, USA, 2018. Association for Computing Machinery.
[26] M. Bun, J. Nelson, and U. Stemmer. Heavy hitters and the structure of local privacy. ACM Transactions on Algorithms (TALG), 15(4):1-40, 2019.
[27] M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658 Springer, 2016.
[28] T. T. Cai, Y. Wang, and L. Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825-2850, 2021.
[29] S. Caldas, Konečny, H. B. McMahan, and Talwalkar. Expanding the reach of federated learning by reducing client resource requirements. arXiv preprint 1rXiv:1812.07210. 2018.
[30] C. L. Canonne, G. Kamath, and T. Steinke. The discrete gaussian for differential privacy. arXiv preprint 20Xiv:2004.000100 2020.
[31] W.-N. Chen, A. C. Choo. P. Kairouz, and A. T. Suresh. The fundamental price of secure aggregation in differentially private federated learning. In International Conference on Machine Learning, pages 3056-3089. PMLR, 2022.
[32] W.-N. Chen, P. Kairouz, and A. Ozgur. Breaking the commuiiation-rivayyycaaaaa trilemma. Advances in Neural Information Processing Systems, 33, 2020.
[33] W.-N. Chen, A. Ozgur, G. Cormode, and A. Bharadwaj. The communication cost of security and privacy in federated frequency estimation. In F. Ruiz, J. Dy, and J.-W. van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statisties, volume 206 of Proceedings of Machine Learning Research, pages 4247-4217 PMLR, 25-27 Apr 2023.
[34] W.-N. Chen, A. Ozgur, and P. Kairouz. The Poisson binomial mechanism for unbiased federated learning with secure aggregation. In International Conference on Machine Learning, pages 3490-3506. PMLR, 2022.
[35] A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In Anmual International Conference on the Theory and Applications of Cryptographic Techniques, pages 375 473-403. Springer, 2019.
[36] G. Cormode and A. Bharadwaj. Sample-and -nt-eeessoo-ddld differential privacy: Histograms and applications. In International Conference on Artificial Intelligence and Statistics, pages 1420- 1.31. PMLR, 2022.
12

---

[37] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429-438. IEEE, 2013.
[38] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[39] C. Dwork, G. N. Rothblum, and Vadhan. Boosting and differential privacy. In 2010 IEEE 5 Ist Annual Symposium on Foundations of Computer Science, pages 51-60. IEFE, 2010.
[40] U. Brlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta. Amplifi- cation by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2019.
SIAM,
[41] F. Farokhi. Gradient sparsification can improve performance of differentially-privee convex machine learning. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 1695-1700. IEEE, 2021.
[42] V. Feldman, C. Guzman, and S. Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1265-1277. SIAM, 2017.
[43] V. Feldman, A. McMillan, and K. Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Anmual Symposium on Foundations of Computer Science (FOCS), pages 954 964. IEEE, 2022.
[44] V. Feldman, A. McMillan, and K. Talwar. Stronger privacy amplification by shuffling for Rényi and approximate differential privacy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4966-4981. SIAM, 2023.
[45] V. Feldman, J. Nelson, H. Nguyen, and K. Talwar. Private frequency estimation via projective geometry. In International Conference on Machine Learning, pages 6418-6433. PMLR, 2022.
[46] V. Feldman and K. Talwar. Lossless compression of efficient private local randomizers. arXiv preprint 1.X.v::212./2099 2021.
[47] J.-J. Fuchs. Spread representations. In 2011 Conference Record of the Forty Fifth Asilomar Conference on Signals, Systems and Computers (ASILOMAR), pages 814-817. IEEE, 2011.
[48] V. Gandikota, D. Kane, R. K. Maity, and A. Mazumdar. vqSGD: Vector quantized stochastic gradient descent, 2019.
[49] S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2366 2013.
[50] B. Ghazi, N. Golowich, R. Kumar, R. Pagh, and A. Velingker. On the power of multiple anonymous messages. arXiv preprint arXiv: PrXii:1908. 1908. 1158,, 2019.
[51] B. Ghazi, R. Kumar, Manurangsi, and R. Pagh. Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead. In International Conference on Machine Learning, pages 3505-3514, PMLR, 2020.
[52] A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-mxximziing privacy mechanisms. SIAM Journal on Computing, 41 41(6):1633-166 2012.
[53] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. T. Suresh. Shuffled model of differential privacy in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 2521-2529 PMLR, 2021.
[54] A. M. Girgis and S. Diggavi. Multi-message shuffled privacy in federated learning. arXiv preprint 11122, 2023.
13

---

[55] Y. Han, A. Özgür, and T. Weissman. Geometric lower bounds for distributed parameter estimation under communication constraints. In Conference On Learning Theory, pages 3163- 3188. PMLR, 2018.
[56] R. Hu, Y. Gong, and Y. Guo. Federated learning with ctwpafficaatinnaapliiiiii privacy and adaptive optimization. In Z.-H. Zhou, editor. Proceedings of the Thirtieth International Joins Conference on Artificial Intelligence, IJCA1-21, pages 1463-1469, International Joint Confer- ences on Artificial Intelligence Organization, 8 2021. Main Track.
[57] Z. Huang, Y. Qiu, K. Yi, and G. Cormode. Frequency estimation under multiparty differential privacy: One-shot and streaming. Proc. VLDB Endow., 15(10):2058-20)) jun 2022.
[58] P. Kairouz, K. Bonawitz, and D. Ramage. Discrete distribution estimation under local privacy. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, pages 2436-2444, New York, New York, USA, 20-22 Jun 2016.
[59] P. Kairouz, Z. Liu, and T. Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. arXiv preprini urXiv:2102.06380 2021.
[60] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. arXiv preprint 1912:x:112.04999 2019
[61] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1 12:0,,10,, 2021.
[62] B. Kashin. Section of some finite- dimensional sets and classes of smooth functions (in russian) izv. Acad. Nauk. SSSR, 41 41:334-35.. 351, 1977.
[63] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
[64] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint 160.05466, 2016.
[65] A. Korolova, K. Kenthapadi, N. Mishra, and A. Ntoulas. Releasing search queries and clicks privately. In Proceedings of the 18th international conference on World wide web, pages 171-180, 2009.
[66] N. Li, W. Qardaji, and D. Su. On sampling, anonymization, and differential privacy or, k- anonymization meets differential privacy. In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pages 32-33, 2012.
[67] Y. Lyubarskii and R. Vershynin. Uncertainty principles and vector quantization. IEEE Transac- tions on Information Theory, ((47):3491-3501, 2010.
[68] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Arcas. Communication-effiiiennt learning of deep networks from decentralized data (2016). arXiv preprint arXiv: 160.00560 2016.
[69] I. Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IRRE, 2017
[70] T. T. Nguyên, x. Xiao, Y. Yang. S. C. Hui, H. Shin, and J. Shin. Collecting and analyzing data from smart device users with local differential privacy, 2016.
[71] M. Safaryan, E. Shulgin, and P. Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. arXiv preprint UrXiv:2002.08953 2020.
[72] A. Shah, W.-N. Chen, J. Balle, P. Kairouz, and L. Theis. Optimal compression of locally differentially private mechanisms. International Conference on Artificial Intelligence and Statistics, pages 7680-7723 PMLR, 2022.
14

---

[73] C. Studer, W. Yin, and R. G. Baraniuk. Signal representations with minimum norm. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). pages 1270-1277. IEEE, 2012.
[74] A. T. Suresh, F. X. Yu, S. Kumar, and H. B. McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, page 3329-3337. JMLR.org. 2017.
[75] R. Vershynin. High--dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[76] Т. Wang, J. Zhao, X. Yang, and X. Ren. Locally differentially private data collection and analysis. arXiv preprint
2019.
[77] Wangni, J. Wang. J. Liu, and Zhang. Gradient sparsification for coammuunicationefffiiieeee distributed optimization. In Advances in Neural Information Processing Systems, pages 1299- 1309, 2018
[78] S. L. Warner. Randomized response: survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-00 69, 1965.
[79] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in neural information processing systems, pages 1509-1519, 2017. 2017..
[80] M. Ye and A. Barg. Optimal schemes for discrete distribution estimation under local differential privacy. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 759-763, June 2017.
[81] W. Zhu, P. Kairouz, B. McMahan, H. Sun, and W. Li. Federated heavy hitters discovery with differential privacy. In International Conference on Artificial Intelligence and Statistics, pages 3837-3847. PMLR, 2020.
[82] Y. Zhu and Y.-.. Wang. Poission subsampled Rényi differential privacy. In International Conference Machine Learning, pages 7634-7642. PMLR, 2019.
15

---

A Distributed Frequency Estimation
In this section, consider the frequency estimation problem for federated analytics. Recall that for the frequency estimation task, each client's 's private data æ, E {0, satisfies | ll = 1. and the goal is to estimate π == 1 a E; 24 by minimizing the E2 (or L,, kgo) error || - 2 (x | subject to communication and (e. 6)-DP constraints. When the context clear, we sometimes use Ji to denote, by abuse of notation, the index of the item, i.e., E [d].
To fully make use of the Eo structure of the problem, standard technique is applying Hadamard transform to convert the to geometry to an loo one and then leveraging the recursive structure of Hadamard matrices efficiently compress local messages.
Specifically, for given b-bit constraint, we partition each local item I, into 2 chunks 1. (1) 11) 1), where = d/22~1 and n. x; r; (j 1) B j -- 1]. Note
that since 23 is one-hot, only one chunk of (1) is non-zero. Then, client i performs the following
(e) HB
(6)
Hadamard transform for each chunk:
y;
I; where H8 is defined recursively as follows:
H2 1
H H2 Hgn-1 and Ho [1]-
V2
H2n-1,
- -2
Each client then generates a sampling vector Zij ~
Lid
Bern (+) via shared randomness that (2
(j)) as its local report. Since (u, (1) (u)"() "......,.. (2) (j)) only contains a single non-zero entry that can be VB or VBB the local y report be represented in b bits (b bits for the location of the non-zero entry and 1 bit for its sign).
(1) is also known by the server, and commits (v) (),
From the local reports, the server can compute unbiased estimator by summing them together (with proper normalization) and performing an inverse Hadamard transform. Moreover, with an adequate injection of Gaussian noise, the frequency estimator satisfies (c, 6)-DP.
The idea has been used in previous literature under local DP 19 order-optimal trade-off under central-DP, one has to combine Hadamard transform with a random subsampling step and incorporate the privacy amplification due to random compression in the analysis. In Algorithm 3 we provide summary of the resultant scheme which builds on the Recursive Hadamard Response (RHR) mechanism from [32, which was originally designed for communication-efficces frequency estimation under local DP.
32 but in order obtain the
In the following theorem, we control the foo error of Algorithm
Theorem A.1. Let it (x") be the output of Algorithm 3 Then it holds that for all j E [d].
Σ3
o²
E [[x(i) (0)1)
n2
B
and the lg and & errors are bounded by
B do²
IE
112
< +
and
(8)
n
B
dB
d²oo
E |||
#
+
B
Theorem A.2. For any 8, 8 > 0, Algorithm
3
is (e, 8DP if
2 12 log B/
B(og 1/5) + E) log (B/8)
n
n?e²
By combining Theorem A. and Theorem with & emro
A.2
we conclude that Algorithm achieves (s, OSP
BBB
dB Log(B/U
d(oog(1/)) + eog (B/))
0
n²
n²e²
d2 log(d/))
d(Iog ((log(1/)) + e) log log(d/o)
=0
+
n2h
22b
?
16

---

Algorithm 3 Subsampled Recursive Hadamard Response
Input: user data 2n {0. 13dh (where d power of two), DP parameters (s, 6). commu- nication budget b.
Output: frequency estimate f
Set B = d/2b-1 and partition each one-hot vector z; into 2 chunks: x! ..... 2 (2- {0, 1) for user i E [n]] do
Compute the Hadamard transform of cach chunk: y, ( for coordinate j [B] do
HB x.
(0)
Draw Z.g Lid. Bern (#)
if Zi.j = then
Send (vi (1) (5) Vi
(2 12--1) ( (j))
to the server.
end if
end for
end for Server computes the average: ve (2b-1), (B].
T0 =
Σ ::21y
yi (i) + N(0,00),
where o² is computed according to Theorem A.2 Server performs the inverse Hadamard transform
a HB -0) for l = 1,... B.
Return: = ((+())
(#(*1))
Notice that when n (d). the error can be simplified to
0 n25 +
d(log(1/6) + 8) log (d/0) n²
which matches the order-optimal estimation error (up to a log d factor) subject b-bit constraint 55 3 [2] and (c, 8DP constraint [15 7).
17

---

B Proof of Theorem 4.1
It is trivial see that the average communication cost is d y bits. To compute the &g estimation error, observe that
E
|1iaon
2
27
1
Σ
x4(5) Zzd N(0,0²) - Σ ms((1)
E
1oy
1 E
1
Σ 2i(i) Zz,
+ do²
n²
7
, Σ mi(i)- Zi.) 91-
27
2
Σ n
1 E
1
1
Σ 21(0) [x((0)
+ do²
n²
Σ 270) 23,
+ 77
Σ
x((ixxv (i) Zid
Σ 21( [
+ do
7,2
n2
1 Σ o
7
mi())) + E0.()aa0(1)
- n²
1
Σ ar(())
+ do²
7 (1-1) ) Σ 22(60)
+ do²
n
==1
d
+ 2o²
which yields the inequality of (2). Next, we analyze the privacy of Algorithm |
We first the following
two lemmas for subsampling and the Gaussian mechanism:
Lemma B.1 ( (66 82 ). If M is (e, 8)-P, then M' that applies M PoissonSample satisfies (c', -DDP with log (1 + y (ef - 1)) and 8' 778
Lemma B.2 (115). For any E,8 E (0, 1). the Gaussian output perturbation mechanism with A22log(125/8) satisfies (5, 6DDP, where A is the Eg sensitivity of the fargetfunction
o2
Now, we use the above two lemmas to analyze the per-coordinate privacy leakage of Algorithm 1 For simplicity, we analyze the sum of (j'ss instead (and normalized it in the last step). Let S, (xx*) = (+x(()) then clearly the sensitivity of (y(")) is 2c, so Lemma B.2 implies S,(x") + (0, satisfies (:), if we set of 20 before computing the sum, i.e.,
(assuming 8 < 1). Next, if applying subsampling
$1
Sj PoissonSample,
Σ z;(i)Za.j.
where Zi, lid. Bern(7) as defined in Algorithm then by Lemma B.1
Sy PoissonSamplee,a"" + (
satisfies (E2, DD with == log (1 + + (eft - -1) = Ciyes (since we assume < 1) and
52 = - Equivalently, we have
1 = C1
(10)
61 -
Now, since we have established the per-coordinate privacy leakage we apply the following composi- tion theorem to account for the total privacy budgets.
18

---

Theorem B.3 ((391). For any > O, E [0, and å E (0, 11, the class of (E, 6DD mechanisms satisfies (Ez, dō + 8) -DP under d-fold adaptive composition, for
ē = de (ef + 2
According Theorem B.3
Algorithm
CaaiiimSSsttttii satisfies (s, DDD for 8 d 1) 22 2d log(1/8),
(11)
and 8 = dō + â (where 8 is free parameter that we can optimize).
Consequently, for pre-specified (total) privacy budget (e, (), set parameters follows. Let
ō / and 02 zØ7 Let 52 1 so that e S 282 holds. Then (II) implies Algorithm
is
= 2de + e2 2d (og((18))) 2 de2 1) + V 2d /8).
Solving the above quadratic (in-)equality for E2, it suffices that
2 min (1, (dd=o2dl)22/))) + /2d log (2/0) + 8ed =0 min (1 1,
6 / (log(1/6) + ))
4d
Consequently, we set G = 0 min
(note that we require E = O(1)
that 110 holds).
Plugging (e1, 51) into of, we need to choose
of 2c² log((125//0)) Ω max (olog(d/0)) (logg())) + +c) log(d/)) )
of
g²
Finally, as interested in estimating the (subsampled) mean instead of the sum, will normalize the private sum by
-
Ar(+") ny
(Sj PoissonSample, (z0)+N((,)))))
o²),
nn
where
c log(d/8) cdd(og(1/0) + +3) log log(d/6)
0² = max
n2a22
n²g²
Plugging in o² above and 7 b/d yields the desired accuracy in Theorem 4.1
Since we will reuse the above result, we summarize into the following lemma: Lemma B.4. Let Ji Rdxmm + RD for i 1, ..., be n functions with sensitivity bounded by (where the number of inputs can be random variable). Then
(J1 PoissonSample, (x*) O(O, In PoissonSample,(fte (x") N(O,0²))
satisfies (e, ().8)-DP, if
o² max loggg(B/)), ((lgg(() +s) Bog(
C Omitted details of dimension-free communication cost
C.1 Proof of Theorem 4.4
To prove Theorem 4.4 it suffices to prove the following loo version:
19

---

Theorem C.1. Let Let P1,,, In E (-c,c]", d' min nb,
n²=²
(o and
log(1/0) ( n2y²
édd (lloold//00 log(d' (o( /6)
o² o==
(12)
n22²2
Then Algorithm 2 is (e, 0)-DP and yields an unbiased estimator on μ.. In addition, the (average)
per-client communication cost is ydd = b bits, and the &g estimation error is at most
o (e log ( max
(log(1/8) (660)++)) + ))
(13)
nb""
n²=²
With slight abuse of notation, we let pJ E Rd be such that
0,
I
du dr
else.
Note that jy an unbiased estimate of μ if J selected uniformly at random. Then the lz error can be controlled by
|
212
E
||
1J112
+
|
Al12
(b)
E
|| Mr
[2]
d²
0
max
d²
da (ogld/())) (loglog(1/0 + +)) log(d/0)
d2
nb
n²b²
n²=²
de
Pdd'Alog(d//0
e'd cldg(lo (og (d/6)
E
||
pall2
+0
max
nb
n²6²
n²=²
19 d²
dea d'd' log(d/0) edd (log(1 1/8) + + log(d/6)
+0 max
d'
nb
n²b²
n²e²
where (a) holds since lrr is an unbiased estimate of and conditioned on J, j is an unbiased
estimate of Juz; ; (b) follows from Theorem 4.1 (c) holds due the following fact:
do. d' + de S d'
2d2
E [1 1ia--M3113
S Σ2sli
ΣE jEId
JEJ
Therefore, by setting d' = min nbb smaller than the second term, and the second term can be simplified as follows:
we ensure the first term (c) is always
o 2 d max
d' log(d//) (log(1/6) + ++) log(d/o)
nbb
n²
n²e²
1 nbllg(d/5) (log(1/6) + +E) log (oogg/////) d/6)
< 0
Ld max
nbb
n262
n²
(1
(log(1/0) +
0
?d &dd log((dd))) max
nb² n2g²
Finally, applying the same trick of Kashin's 's representation, we can transform the foo geometry to & (similar Corollary 4.3). hence proving Theorem 4.4
D
D Proof of Theorem A.1
Let == 1 D xg and (0) be defined the same way as a! for & E [B). Then our goal bound (0) - + (i),, for all & E [24-1] and E [B].
To this end, let (() = HB (6) (so it holds that - (6) = H (0). Then we have
E
n (
(a) S
(0) =()()))
27
| Ml (y(0) (100 (10) (i)
E
(14)
20

---

Next, observe that due to the subsampling step, for all E [2"-1] and j E [B],
B (HB) (0) Ze + N(
T
where recall that z, Lid. Ber(1/B). Therefore, (f) an unbiased estimator ()) In addition, since we choose Ziz independently in Algorithm g(0) (j)'s are independent for different j j's, so we have
(100 -10 2) = Var (1)
B
0² +
(HB)j. ( (Zis)
n
0 +
B
(H
(0)22
B
0²
+
chunk)
(15)
n
and for all j j
[[[ [[ (1 (110))) (0 ()) -
0.
(16)
Therefore, continue bounding (14
follows:
1 (H HD (v(0) ((9) (1)
E
(1H
B
1
E
HB))}* (1)) v10
B
11
1 E
(g()(k) (B))
B
(b)
Ce
x2
+
n
B
o²
B
where (a) holds since each entry of Hy takes value in {-1, 1} and by (16), (b) holds due to 15 and (c) holds because C₁ S for all
Finally, to bound the & error, observe that the above analysis ensures that
(
Cet) n²
d²
E
<
B
where {(j) E [20-1] is the index of the chuck containing j. Therefore, summing over j E [d]. we must have
E
|
#10
2
Cit n
do²
B
dg²
n B
since
2--1
21-1
Σ
Σ
Σ
Σ
fiet-un th chunk)
= B
1 fiet 8-tth-hhhe chunk) = B n.
8=1 E'E--th chunk 1=1
E=1
1=1
21

---

E Proof of Theorem A.2
Let fy(=") = (j), n (2 (j)), for =,,... B. Then the & sensitivity of fj is A Set
the sampling rate y B and the proof is complete by Lemma B.4
Algorithm of Shuffled SQKR
Algorithm 4 Shuffled SQKR
Input: users' data ....... local-DP parameter communication parameters bo, T Output: mean estimator f for round & E [T'] do
for user E [n] do
Sample s(1, ..,, si, bp)
lid Unif[d]
Sample Z Bern
eta -20+200-1)
Z= then
Set (i,,),..... (i, zi(ss(,, .))...., 2; bo))
else
Sample
(i, bo) iid Unif {-c,c}
end if
Send (i, 1),...,................ (i,, bo) and s(i, 1).......(... end for
s(i, bo) to shuffler
Shuffler samples permutation Unif (f [n] + [n] bijective]
for E [bo] do
Shuffler sends Y (())))))..,,,((((()).))). and ((=((),)) ... ((T()), server
end for ((k)
600 nbg e-0
Σ Ei=1 Σ bo 1= (TT())
end for
Return f = ET=1 (k)
G Proof of Theorem 5.3
Each round xm + (k) of Algorithm 4 implements the private-coin SQKR scheme of 32 achieving the communication cost and еттог as stated in Lemma 5.2
Lemma G.1 (SQKR 32 For all eo s(i..,,(;i,b)) bo)
0, the random mapping in Algorithm is (eo,0)-LDP and has
0,
Ty Y(i,1),..., (i, ((, output that can be communicated in bo log(d) bits, and the ju(k) computed from (i, (i,1)..... (i, bo), s(i, 1)....,ff. s(i, bo) is an unbiased estimator of μ. satisfyyng
max E [I(a")) (*) (x
=0
(n (e S0, b)) )
Cad
(17)
2
We now characterize the error performance of Algorithm 4 for general choices of parameters that satisfy privacy and communication constraints.
Proposition G.2. For all 0,b 0, O, with any arbitrary choice of
61 (c nn16/ 16e 1
(18)
82 (0,
(19)
there exists a choice of parameters Ea, bo. T such that Algorithm 4is (c, T5, + 52)-DP, uses no more than bits of communication, and produces ji such that
|| 2112] =0 -0 ((max (C'dlog(d)bo nb
Oddlog(1/6,) (log(1/62) +5) )
max 2'
(20)
n?g2
22

---

Proof. For arbitrary choice of
bo < log
(21)
16 16
it suffices to choose
T (log2 (d) + 1)b0
(22)
EV
80 O min 1, TToooo (61) (log(1 (1/6)) + +
(23)
The fact that Algorithm 4 uses less than b bits is immediate from the choice of T.
Applying Lemma G.1 by construction the mapping from each x; (i, 1),... Y (i, bo) (en, 0)-
LDP. By assumption
81 > nn/1ee
(24)
the inequality
1 < log 161og(2/81)
(25)
is satisfied. Then the choice of
S 1
(26)
also satisfies en log (2 by Lemma 5.1 the mapping x² + fz(0) is where
Eov (1/(1/
E1 =
(27)
Vn
Since the output of Algorithm is a function of (ji(")...,, by B.3 it suffices to have
E1 0 min (log((1/d))
(28)
for Algorithm be T8, + 32)- The first inequality follows from the assumption of 8, nn/10e and choice of Eo = 0(1), and the second from choice of
>
E
5o = 0
(29)
'T (og()/))) (10g(1 + +
Since Ep I $ b, we have min(Ez: En, b) = =/-- Applying Lemma G.I
max 2791
|| - A1(2] =
max E g
| a (1)
(30)
T
2
0
(31)
T
d d (log(1/5,) (log(1/52) +
0
max
T'n
n²
(32)
Substituting the choice of gives the desired result.
L
To show Theorem
5.3 it suffices choose
bp
(33)
5
6 2T
(34)
8 6, 2
(35)
which requires n > 16e x 30.14 due to
(1 and apply the previous proposition.
23

---

H
Using Kashin's Representation
We first introduce the idea of a tight frame in Kashin's 's representation. A tight frame is of vectors {uz)ş= C IR that satisfy Parseval's identity, i.e. || Ee= x),, for all æ E R2
frame can be viewed as a generalization of the notion of an orthogonal basis in R4 for D > d. To increase robustness, wish the information to be spread evenly across different coefficients, which motivates the following definition of a Kashin's 's representation:
Definition H.1. For a set of vectors {uy m we say the expansion
K
Σ agu with max layl
|
vD
j-1
a Kashin's representation of the vector x at level K.
By Theorem 3.5 and Theorem 4.1 in 677, we have the following lemma:
Lemma H.2. There exists light frame U [W1...., uD] with (7) D = ((d) and (2) level K = O(1).
The above lemma implies that for each z; I& such that ||æ:||2 1, one always represent each Fy with coefficients yi E [-ro/vd, / /d for some No: 71 and 24 Uy..
I Rényi-DP for Shuffled SQKR
In this section we restate some results for RDP which are useful for privacy accounting in experiments. Following the proof of Corollary 4.3 in 44 applying Theorem 4.1 in the same paper yields the following.
Lemma L1. Let M, be an independent (Ev, DD- mechanism for each i E [n] with Eg S 1 and π be a random permutation of [n]. Then any 165o exp(eu)) the mechanism
S: (TI,..,, In). (Mi (z=(1)) ...., Mn (Iz(n))
is (ei(a),8)-RDD with
Ea(a) = log (2att + e
(36)
1
where
8 ecD
(37)
8min Bre 1)
(38)
For small Eg, the result below is useful.
Lemma 1.2 (40)) Under the same assumptions as Lemma I.1 S is (s(a),0)-RDP
Ei(a) = 2E0 (e 1)² /n.
(39)
Applying Lemma G.1
by construction the mapping from each x; y(i, 1), 1)....,,............... v(i, bu) is (Eu. 0)-
LDP. By Lemma L.I
respectively Lemma I.2 the mapping x" + (k()) is (a) RDD where
Eι (a) is given by (36). respectively (39.. By composition, Algorithm i (Te(a), RDP.
We can convert this bound back to (c, using Proposition 12 from 30
Proposition I.3. For all Algorithm is (e, D)DP where
log(1/6 + (a 1) log(1 - 1/a) log(a)
inf (ei(a)+ aE(1,00)
(40)
--1
where
log (2a20" + 4
(1(0) min
20c seu (0 1) /n.
(41)
and 8min are given by
38 respectively.

---

Additional Experiments
Here experiments are done with the same setup as in Section with local vectors X1(i) Ltd. va (2 Ber(0.8) 1). We set 5 10-6.
Mean Estimation, 2000, E
Shuflled SOKR [T= round)
SQKR (T rounds)
Shuffled SQOR (T= 10 rounds)
Shuffled SOKR (T 20 rounds)
10a
rounds;
Shuffled SOKR (T= 100 rounds)
MSE
164
10a
10a
Figure 2: Comparison of MSE vs. number clients n for LDP scheme (SQKR) and shuffled SQKR. For shuffled SQKR, set by 1 and choose Eg using results in Section Communication cost is [(000))000) + 1)1 = 12 bits per round.
Figure illustraate separation between Algorithm and L.P schemes. Algorithm achieves error decreasing quadratically with n as guaranteed by Theorem 5.3 With only one round of shuffling, there is separation from the LDP scheme only when n is sufficiently large, and thus order-optimal error performance only occurs for large n (or equivalently small e). This problem is avoided with multiple rounds of shuffling.
Mean estimation, n= =05
Without, 3600
Without 4900
Without,
106
With, =500
With, 36000
With,
With. -400
10a
MSE
10a
102
102
10a
Communication constraint [bits]
Figure 3: CSGM with and without coordinate pre-selection using d' 833.
compares the performance of CSGM with and without coordinate pre-selection. In this regime coordinate pre-selection improves performance for b. As predicted by Corollary 4.3 an3 and
Figure
Corollary 4.5 the MSE decreases with 5 but is effectively constant for sufficiently high b where the
25

---

privacy term dominates. We can determine the communication cost needed for order-optimal central DP error performance to be the at which the MSE is within some fixed constant factor away from the limiting value. We see that the communication cost increases with dimension d with the vanilla CSGM scheme, but dimension-free communication cost is achieved with coordinate pre-selection.
26


Reviews:
[{"review_id": "bFOulf9HRe", "reviewer": "Reviewer_B1Jv", "summary": "This paper studies the federated learning problem within the central differential privacy model, where a trusted central server gathers information from local clients. The primary focus is on minimizing communication costs while ensuring privacy and maintaining accuracy guarantees. To address this challenge, the paper introduces a novel privacy amplification framework. The framework operates by having each local client transmit only a random subsample of its full parameters to the central server, effectively reducing the communication overhead. Simultaneously, the randomness introduced in the subsampling process amplifies the privacy guarantee. Notably, in the specific case of distributed mean estimation, this framework significantly reduces the communication cost from an order of $O(d)$ to $\\tilde O(n\\min\\\\{\\epsilon, \\epsilon^2\\\\})$, showing a significant improvement over state-of-art result.", "questions": "N/A", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper provides a novel privacy amplification method in central DP setting that optimizes the communication-privacy-accuracy three-way trade-off. Furthermore, the proposed distributed mean estimation also has significant implications. For example, upon setting $x_i$ to be local gradients, this algorithm immediately implies a private distributed SGD algorithm with reduced communication cost.", "weaknesses": "The privacy amplification method is restricted to the central DP model and does not apply to LDP model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's recognition of the novelty and significance of our techniques in private SGD and federated learning. As the reviwer notes, our schemes do not amplify local DP since the randomness used for amplification (i.e., random seeds for compression/subsampling) must be known by both the client and the server. We note that this is also true for other  amplification technologies, such as privacy amplification by shuffling or subsampling, which are primarily designed for central DP."}, {"review_id": "NxgFQNkEZJ", "reviewer": "Reviewer_rG5G", "summary": "The paper proposes a new randomization scheme for differentially private mean estimation. It is based on each user choosing randomly the coordinates to be sent in their messages. Similar scheme has been proposed in reference paper [55] (Hu et al., 2020), however Hu et al. do not sparsify the individual data-element-wise vectors, only mini-batch gradients.\n\nIn the proposed scheme, data-element-wise vectors are sparsified randomly and the server averages these sparse vectors and adds normally distributed noise. A classical differential privacy analysis (meaning it uses some classical (eps,delta)-amplification results) is carried out resulting in optimal communication - privacy - accuracy tradeoffs (solving also an open problem in the untrusted server - setting) when these quantities are measured asymptotically.\n\nAlgorithms both in trusted server setting and untrusted server (via multimessage shuffling) are given.\n\nThe privacy analysis is essentially for the $\\ell_\\infty$-mean estimation, and the $\\ell_2$-mean estimation bounds are obtained using the so called Kashin's representation which turns $\\ell_2$-constraints into $\\ell_\\infty$-constraints in an optimal way. \n\n", "questions": "-  You mention that the privacy analysis could possibly be improved, and the log factors shaved off. Somehow I get the impression that you could elaborate on this more... Looking at the trusted server setting, I get the impression that the $\\ell_\\infty$-mean estimation algorithm one could perhaps analyse tightly (with RDP or directly with approximative DP). In a sense I think you do that in the experimental example. However, again with the $\\ell_\\infty$-constraints, how would you go about involving the Kashin's representations in the analysis? I get the impression that, e.g., in reference [34], the privacy bounds are simply big-O bounds as there are some universal constant involved when transforming between the constraints. Do you think it would be possible to analyse $\\ell_2$-mean estimation algorithm using this coordinate subsampling tightly?\n\n- How would this fit to federated learning? I mean wouldn't the sparsity be lost quickly in case each device/user has model updates constructed using several data-elements? Wouldn't sparsification similar to the that of [55] be then required to reduce the communication?\n\nMinor comments:\n- Shouldn't \"$\\ell_2$ error\" in Table 1 be actually \"$\\ell_2^2$ error ?\n- In bibliography, please use the Arxiv reference for the reference [33] instead of \"in submission\" \n- The reference paper [55] (which is quite central here) has been published in IJCAI, you only mention the Arxiv reference.", "limitations": "Yes, I think the limitations with the analysis are adequately discussed in Section 7.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- solves an open problem and given optimal tradeoffs between privacy, accuracy and communication both in trusted and untrusted setting\n- Generally well written\n- extensive list of references and a comprehensive 'related works' section. I think the paper serves even as a good starting point for diving into this topic.", "weaknesses": "- I think some parts are too densely written. The Kashin's representation is not introduced properly I think, those lines 208 to 214 give simply to little information. Like what is that tight frame $K$? I think there is some (still quite short) introduction in reference [34]. I think it would help a lot to have some more material on Kashin's representation, e.g. in the appendix. You use it repeatedly to get the $\\ell_2$ mean estimation bounds anyways.\n\n- Related to the above comment, and for further improving writing: in lines 645-646 in the appendix you write \"applying the same trick of Kashin's representation\"... what are you referring to with 'the same' ? Here also would help expanding / elaborating a bit.\n\n- I think the paper is not entirely explicit about the difficulty of accurate privacy accounting in case of $\\ell_2$-mean estimation (see the question comment below in the Questions - section)\n\n- It is not entirely clear how well the method fits to reducing communication in FL training of ML models if one would need to randomly sparsify individual gradients (see comment in the Questions - section)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's comprehensive summary of our work. We would like to clarify the differences between our techniques and those presented in [Hu et al.]. One of the main distinctions is that Hu et al. consider a mini-batch setting, where sparsification, a form of dimensionality reduction, is performed *after* locally perturbing the mini-batch gradients. Although the $\\ell_2$ norm of the noise might appear reduced due to the projection step, constructing an unbiased estimator requires multiplying the sampled gradient by a factor of $1/p$, where $p$ is the sampling rate. Consequently, the $\\ell_2$ norm of the noise in the unbiased estimator indeed increases by a factor of $1/\\sqrt{p}$, resulting in a suboptimal privacy-communication-accuracy trade-off.\n\nIn contrast, our techniques independently apply the sampling step to different clients, and the noise is added to the mean of the decompressed gradients, rather than the original (local) uncompressed gradients. Most significantly, the randomness of local sampling is leveraged in our privacy analysis, enabling a tighter trade-off. As the title of our paper suggests we believe the key observation that our paper brings is that the randomness in the local compression can be leveraged for privacy amplification in central DP. It is important to note that the randomness of the sampling/projection in [Hu et al.] is not taken into account in their analysis.\n\nAdditionally, we present a communication-efficient scheme that achieves (nearly) optimal communication cost and MSE under a shuffle DP guarantee.\n\nResponse to Weaknesses:\n- Regarding Kashin's representation, roughly speaking, a tight frame can be interpreted as a \"basis\" (i.e., a collection of $D$ vectors in $\\mathbb{R}^d$ with $D > d$) with redundancy, and under this \"basis\", one can find a representation of any $x \\in \\mathbb{R}^d$ with small $\\ell_\\infty$ norm. \n\n    We have kept the overview of Kashin's representation brief in our submission as we felt like this has become a standard tool for DME in the literature, see for example [Chen et al. 2020], but following reviewers' suggestions we will provide a detailed discussion of Kashin's representation and how it can be used to transform the $\\ell_2$ problem to an $\\ell_\\infty$ one in an appendix. Below we provide those details for reviewers' reference.\n\nWe first introduce the idea of a tight frame in Kashin's representation. A tight frame is a set of vectors $\\\\{u_j\\\\}^D_{j=1} \\in \\mathbb{R}^d$ that satisfy Parseval's identity, i.e. $ \\| x \\|^2_2 = \\sum_{j=1}^D \\left\\langle u_j, x \\right\\rangle^2$ for all $x \\in \\mathbb{R}^d.$\n\nA frame can be viewed as a generalization of the notion of an orthogonal basis in $\\mathbb{R}^d$ for $D>d$. \nTo increase robustness, we wish the information to be spread evenly across different coefficients, which motivates the following definition of a Kashin's representation:\n\n**Definition.**\n    For a set of vectors $\\\\{u_j\\\\}^D_{j=1}$, we say the expansion  $ x = \\sum_{j=1}^D a_j u_j $,  with $\\max_j | a_j | \\leq \\frac{K}{\\sqrt{D}}\\| x \\|_2 $ is a Kashin's representation of the vector $x$ at level $K$ . \n\n[Chen et al. 2020] Breaking the communication-privacy-accuracy trilemma\n\n- Here, we refer to the same technique in the proof of Corollary 4.3 (which extends the $\\ell_\\infty$ mean estimation problem to $\\ell_2$ mean estimation). Again, this is based on Kashin's representation and the details stated in the beginning of our general response can be easily provided in an appendix. We will  also elaborate more in the proof to avoid any confusion.\n\n- For the remaining two points, see our responses to the questions below.\n\nResponse to Questions:\n\n- Regarding the theoretical analysis of privacy guarantees, we utilized the strong composition theorem in [Dwork et al. 2010], which is only tight up to some logarithmic factors. We acknowledge that employing more advanced accounting techniques such as the strong composition [Kairouz et al. 2016], moment accountants [Abadi et al. 2016], or Renyi DP accountant [Mironov et al. 2017] may yield slightly better bounds on $\\varepsilon$. Indeed, in our experiments, we accounted for the privacy budgets via Renyi DP, which we believe offers a tighter bound than our theoretical (order-wise optimal) bounds.\n    \n    Regarding the $\\ell_2$ mean estimation in practice, we opted not to use Kashin's representation and instead perform random rotation with $\\ell_\\infty$ clipping. Although the $\\ell_\\infty$ clipping step introduces a small amount of bias, we believe it offers a better privacy-MSE trade-off in practice. One may be able to directly analyze the privacy of $\\ell_2$ mean estimation  with coordinate-sampling (without the Kashin's representation step), but currently it remains unclear.\n\n    [Dwork et al. 2010] Boosting and differential privacy\n\n    [Kairouz et al. 2016] The composition theorem for differential privacy\n\n     [Abadi et al. 2016] Deep learning with differential privacy\n    \n    [Mironov et al. 2017]  Rényi differential privacy\n\n-  Note that in the context of standard FL, it is not guaranteed that each local gradient or model update exhibits sparsity. As a result, additional sparsification procedures must be explicitly introduced to effectively mitigate communication costs. In the work of [55], this sparsification process involves the random selection of $k$ coordinates from a set of $d$ coordinates. Our scheme, the Coordinate Subsampled Gaussian Mechanism, on the other hand, can also be viewed as sparsification (as mentioned earlier). However, our primary contribution lies in demonstrating how this sparsification can be used to \"amplify\" central DP. In comparison to [Hu et al.], our scheme injects isotropic Gaussian noise after local sparsification and aggregation, which enables us to apply the amplification lemma via subsampling.\n\nLastly, we appreciate the reviewer's attention to the typos and citation inconsistency, and we will promptly address those issues."}, {"review_id": "pA0HKhrLbe", "reviewer": "Reviewer_WRY9", "summary": "This paper studied the optimal rates of the tradeoff among privacy (central DP), utility ($\\ell_2$ estimation error), and communication cost (in bits) for the distributed mean and frequency estimation settings. The authors used Kashin's representation and Coordinate Subsampled Gaussian Mechanism to achieve the optimal rates. They also propose a many-round procedure with a shuffling mechanism to achieve the optimal rate if there is a secure shuffler instead of a secure central server. Simulation results are provided to supper the theoretical results of the distributed mean estimation setting.", "questions": "1. Line 212. What does the dot product in $x_i = K \\cdot \\tilde x_i$ mean? Is it a matrix multiplied by a vector? \n2. Are the notations of $(\\alpha)$ and $(\\beta)$ in Equation (4) in Line 217 misplaced? I think $(\\alpha)$ is only the first part of Equation (4) and $(\\beta)$ is the remaining two parts. Nevertheless, this seems not to affect the analysis in Section 4.1.\n3. Line 354. For the statement of $d=5000$, is it from the previous claim based on the theoretical results '$b$ is independent of $d$'? Or is the result of $d=5000$ missing in this manuscript?\n4. Line 622 in Section B. Should the sensitivity of $S_j(x^n)$ be $2c$? Should $Z_{i,j}$ be i.i.d. from $\\mathrm{Bern}(\\gamma)$ instead of $\\mathrm{Bern}(1/\\gamma)$?\n5. Line 630. Should $\\log(d/\\delta)$ be $\\log(d\\gamma/\\delta)$? Is $\\gamma$ missing here (and elsewhere) intentionally?", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides the optimal rates for the distributed mean estimation given specific privacy and communication constraints, which is a fundamental problem in distributed learning (with a central server).\n2. The authors proposed the Coordinate Subsampled Gaussian Mechanism and used it to realize the optimal rates.\n3. The theoretical results are supported by the simulation results.", "weaknesses": "1. In Theorem 5.3, the rate is $O(C^2 d \\ldots)$ while in the appendix Lemma G.1 and Proposition G.2, the rates are $O(c^2 d)$. As Theorem 5.3 is also using Kashin's representation, I think it should be $c=O(\\frac{C}{\\sqrt{d}})$ as in Line 211. Therefore, there could be something incorrect in the result of Theorem 5.3. However, removing $d$ from the current result also seems to be strange to me.\n2. The authors derived the theoretical results for the histogram estimation while not showing corresponding simulation results. They claimed these results in the abstract and introduction as contributions while only showing them in the appendix, which may not be very appropriate.\n3. This paper uses the name 'federated learning' many times while the problem being solved is more restricted to the distributed learning  (with a central server).\n\n\nMinor weaknesses:\n1. Citation issues: [33] is cited as 'in submission' while it is already published in AISTATS 2023. [59] and [60] are duplicates.\n2. Line 91. $10^6-10^9$ -> $10^6$ to $10^9$.\n3. In Theorem 4.1, $\\sigma$ should use $\\Omega$ notation since we need it large enough to guarantee privacy. Similar misuses are in other results. This can be seen in the transition from $\\sigma_1^2$ to $\\sigma^2$ in Line 630 where the former used $\\Omega$ while the latter used $O$.\n4. Line 358. $\\lceil \\log d\\rceil + 1)T$ should be $(\\lceil \\log d\\rceil + 1)T$\n5. Line 361. The period is missing in the end of this line.\n6. The citation of Theorem B.3 is missing.\n7. Line 628. $e_2^\\epsilon$ should be $e^{\\epsilon_2}$.\n8. Line 642. The second term in this equality is random which must be incorrect. Nevertheless, the final result is unaffected. \n\n---\nI have read the rebuttal which addressed my questions and the weakness concerns.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's careful reading, valuable questions, and constructive feedback.\n\n**Response to Weaknesses.**\n\n- We apologize for the inconsistency in notation; the rates in Lemma G.1 and Proposition G.2 should be $O(C^2 d ...)$ instead of $O(c^2 d ...)$, and our main results (Theorem 5.3) are indeed correct as stated. We want to clarify that the results stated in Lemma G.1 and Proposition G.2 are already for the $\\ell_2$ geometry, not the $\\ell_\\infty$ one.\n\n- We chose to move our results on histogram estimation (for federated analytics) to the appendix due to the strict page limit, but if this paper is accepted and we are granted an additional page for the full version, we will definitely include the result for histogram estimation together with simmulation results in the main body of the paper.\n      It is important to note that our scheme is unbiased, so the estimation error is not directly comparable with other frequency estimation schemes (which involve thresholding to reduce estimation error and, hence, are typically biased).\n\n- We believe our setting is indeed well-aligned with standard federated learning settings [Mcmahan et al. 2016, Kairouz et al. 2019]. As described in [Kairouz et al. 2019], \n*\"Federated learning (FL) is a machine learning setting where many clients (e.g. mobile devices or whole organizations) collaboratively train a model under the orchestration of a central server (e.g. service provider), while keeping the training data decentralized.\"*\nTo this end, our work focuses on optimizing communication efficiency under central DP or shuffle DP, which are two of the most prominent privacy frameworks for federated learning (another one is local DP which we do not consider in this paper). We characterize the fundamental limits and algorithms to achieve (nearly) optimal communication cost while still achieving the same order of estimation error. Our simulations further support the theoretical results.\n\n[Mcmahan et al. 2016] Communication-efficient learning of deep networks from decentralized data\n\n[Kairouz et al. 2019] Advances and open problems in federated learning\n\n- Lastly, we appreciate the reviewers detailed input about typos and minor issues; we will promptly fix them in the revision.\n\n\n**Response to Questions.**\n\n- Yes, here $K\\in\\mathbb{R}^\\{d\\times D\\}$ is the matrix representing the tight frame, and $K\\cdot \\tilde{x}\\_i$ is a matrix multiplication. Regarding Kashin's representation and its use in transforming an $\\ell_2$ problem to an $\\ell_\\infty$ one, we will include a section in the appendix that elaborates on this topic. See also our response to Reviewer rG5G. for more details on Kashin's representation.\n\n- We agree with the reviewer's point that the middle term $O\\left(\\frac{C^2d^2\\log(1/\\delta)}{n^2b^2}\\right)$ can also be viewed as part of the impact of privatization, as it comes from the DP noise (as stated in Theorem 4.1). However, it becomes significant only when local vectors are drastically compressed (i.e., when the sampling rate $\\gamma$ is sufficiently small). We will further clarify this aspect in the revision to avoid any ambiguity.\n\n- We apologize for the confusion regarding the experimental results for $d=5000$. We acknowledge that the previous version had these results but was removed due to space constraints. We will add it back in the appendix for a more comprehensive presentation.\n\n- Thank you for bringing the typos to our attention. We will fix them in the revision. The sensitivity in Section B should be $2c$ (due to our adoption of a replacement notion of DP instead of a removal version), and $Z_{ij} \\sim \\text{Bern}(\\gamma)$. That being said, the final results remain unaffected.\n\n- In line 630, we opt to use an upper bound on $\\sigma_1^2$ in order to simplify notation. Also note that we are mainly interested in the regime where $\\gamma = \\Omega( 1/\\sqrt{d})$ (which will be used to achieve the dimension-free communication cost as in Theorem 4.4), so asymptotically $\\log(d\\gamma/\\delta) \\asymp \\log(\\sqrt{d}/\\delta) \\asymp \\log(d/\\delta)$. We will clarify it in the proof of Theorem 4.1."}, {"review_id": "9ySiAZtTfC", "reviewer": "Reviewer_mo9D", "summary": "This paper studies the distributed mean estimation problem with communication constraints and central DP. Communication constraints are met by subsampling a Kashin representation of the target vector, and \\eps-DP is achieved by adding Gaussian noise. Privacy in the absence of a trusted server can be achieved using a LDP mechanism along with a secure shuffler.\n\nAfter discussions with the authors, I have increased my score. ", "questions": "The results are intuitively correct and are technically sound. ", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The work claims to be the first to study the communication-privacy-accuracy tradeoff for DME problem with central DP. It provides a simple scheme that achieves order-optimal error bounds. ", "weaknesses": "While this is the first work to study the problem, the solution was well-known. Unlike the LDP constraints, there is no tension between the communication cost and privacy in this case.  Therefore, in my opinion, the novelty of this work is limited. The results are a straightforward amalgamation of well-known techniques that are independently known to be optimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's acknowledgment of the correctness and technical soundness of our results. However, we kindly disagree with the statement that *\"Unlike the LDP constraints, there is no tension between the communication cost and privacy in this case.\"* Indeed, we believe the situation is exactly analogous to the local DP case, and showing this is part of the contribution of our paper. For local DP, one may a priori expect a tension between privacy and communication cost, e.g.,  privatizing the local messages can increase their entropy and hence make them more difficult to compress. However [Chen et al. 2020] and others have shown that these two constraints can be aligned in a way such that the optimal accuracy is only dictated by one of the two constraints and the less stringent constraint can be satisfied for free. Similarly for central DP, one may a priori expect that compression will increase the sensitivity of the mean and therefore require the addition of larger noise at the central server, and hence lower accuracy, for the same privatization level. \n\nThe main contribution of our paper is to show that this does not need to be the case when compression is done randomly and privacy amplification due to random compression is taken into account. We believe this idea of using random compression for privacy amplification is novel and does not appear in the prior literature. In addition, we also characterize the optimal three way trade-off for the shuffling model. While previous research has explored communication efficiency under local DP or secure aggregation, our work stands out as the first to comprehensively characterize the communication-privacy-accuracy trade-off for both the central DP and shuffling models.\n\n[Chen et al. 2020] Breaking the communication-privacy-accuracy trilemma"}]

Author rebuttal:
We thank all reviewers for their valuable questions, insightful suggestions, and constructive feedback. We will fix all typos/minor issues in the revision and have provided responses to concerns raised by each reviewer below. We would greatly appreciate if the reviewers could consider updating the scores if the concerns are addressed in our response.

Meta-review: This paper proposes an algorithm for distributed high-dimensional mean estimation in L_2 that reduces communication to at most $O(n \min{\epsilon,\epsilon^2\})$. For sufficiently large $d$ this improves on the naive algorithm communicating $d$ bits. The algorithm requires either an appropriate aggregator or just a multi-message shuffler. The analysis relies on privacy amplification achieved via randomly selecting which indices of the input data to send. This is a neat and novel technique that might find additional applications.
Decision: Accept (poster)