Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy
Authors: Richeng Jin
Zhonggen Su
Caijun Zhong
Zhaoyang Zhang
Tony Quek
Huaiyu Dai
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential privacy
federated data analytics
discrete valued-mechanism
distributed mean estimation
TL;DR: Analyze the $f$-differential privacy guarantees for discrete-valued mechanisms and propose a new differentially privacy compressor

Abstract: We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. The commonly adopted compression schemes introduce information loss into local data while improving communication efficiency, and it remains an open problem whether such discrete-valued mechanisms provide any privacy protection. In this paper, we study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP). More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms, including the binomial noise and the binomial mechanisms that are proposed for privacy preservation, and the sign-based methods that are proposed for data compression, in closed-form expressions. We further investigate the amplification in privacy by sparsification and propose a ternary stochastic compressor. By leveraging compression for privacy amplification, we improve the existing methods by removing the dependency of accuracy (in terms of mean square error) on communication cost in the popular use case of distributed mean estimation, therefore breaking the three-way tradeoff between privacy, communication, and accuracy.

Breaking the Conmuniction-Piivacy-cuaaaaa Tradeoff with S-DDifferential Privacy
Richeng Jin' Zhaoyang Zhang'
Zhonggen Su'
Caijun Zhong'
Tony Q.S. Quek² Huaiyu Dai
!Zhejiang University
Singapore University of Technology and Design North Carolina State University
Abstract
We consider federated data analytics problem in which server coordinates the collaborative data analysis multiple users with privacy concerns and limited communication capability. The commonly adopted compression schemes introduce information loss into local data while improving communication efficiency, and it remains an open problem whether such discrete-valued mechanisms provide any privacy protection. In this paper, we study the local differential privacy guaran- tees of discrete-valuee mechanisms with finite output space through the lens of f-differential privacy (DP). More specifically, we advance the existing literature by deriving tight f-DP guarantees for a variety of discrete-values mechanisms, includ- ing the binomial noise and the binomial mechanisms that are proposed for privacy preservation, and the sign-based methods that are proposed for data compression, in closed-form expressions. We further investigate the amplification in privacy by sparsification and propose a ternary stochastic compressor. By leveraging com- pression for privacy amplification, we improve the existing methods by removing the dependency of accuracy (in terms of mean square error) on communication cost in the popular use case of distributed mean estimation, therefore breaking the three-way tradeoff between privacy, communication, and accuracy.
Introduction
Nowadays, the massive data generated and collected for analysis, and consequently the prohibitive communication overhead for data transmission, are overwhelming the centralized data analytics paradigm. Federated data analytics is, therefore, proposed as
distributed computing paradigm that enables data analysis while keeping the raw data locally on the user devices [[] Similarly to its most notable use case, i.e., federated learning (FL.) 2 3, federated data analytics faces critical challenges: data privacy and communication efficiency. On one hand, the local data of users may contain sensitive information, and the user devices are usually equipped with limited communication capabilities, and compression mechanisms are often adopted improve communication efficiency.
mechanisms needed. On the other hand,
Differential privacy (DP) has become the gold standard for privacy measures due to its rigorous foundation and simple implementation. One classic technique to ensure DP is adding Gaussian or Laplacian noises to the data [4). However, they are prone to numerical errors on finite-precision computers (5) and may not be suitable for federated data analytics with communication constraints due to their continuous nature. With such consideration, various discrete noises with privacy guarantees have been proposed, e.g., the binomial noise [6], the discrete Gaussian mechanism [7], and the Skellam mechanism [8) Nonetheless, the additive noises in 77] and (8] assume infinite range, which renders them less communication-efficle without appropriate clipping. Unfortunately, clipping
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

usually ruins the unbiasedness of the mechanism. [9| develops a Poisson binomial mechanism (PBM) that does not rely on additive noise. In PBM, each user adopts a binomial mechanism, which takes a continuous input and encodes it into the success probability of a binomial distribution. The output of the binomial mechanism is shared with a central server which releases the aggregated result that follows the Poisson binomial distribution. However, [9] focuses on distributed DP in which the server only observes the output of the aggregated results instead of the data shared by each individual user, and therefore, requires a secure computation function (e.g., secure aggregation [3).
In addition to discrete DP mechanisms, existing works have investigated the fundamental tradeoff between communication, privacy, and accuracy under the classic (c. 6D framework (e.g.. [I 12 (3). Notably, the case of distributed mean estimation, [3] incorporates Kashin's 's representation and proposed Subsampled and Quantized Kashin's 's Response (SQKR), which achieves order-optimal mean square error (MSE) that has a linear dependency on the dimension of the private data d. SQKR first computes Kashin's 's representation of the private data and quantizes each coordinate into a 1-bit message. Then, & coordinates are randomly sampled and privatized by the 2* -a-nddn Response mechanism [14). SQKR achieves an order-optimal waree-way tradeoff between privacy, accuracy, and communication. Nonetheless, it does not account for the privacy introduced during sparsification.
Intuitively, as compression becomes more aggressive, less information will be shared by the users, which naturally leads to better privacy protection. However, formally quantifying the privacy guarantees of compression mechanisms remains an open problem. In this work, we close the gap by investigating the local DP guarantees of discrete-valued mechanisms, based on which a ternary stochastic compressor is proposed to leverage the privacy amplification by compression and advance tradeoff. More specifically, we
the literature by achieving better communication-pin wwtpnn-pp-aaaccrrraaaa focus on the emerging concept of f-DP [15] that can be readily converted to (c, 5)-DP and Rényi differential privacy [16] in a lossless way while enjoying better composition property (17].
Our contributions. In this work, we derive the closed-form expressions of the tradeoff function between type I and type II error rates in the hypothesis testing problem for a generic discrete-valued mechanism with finite output space, based on which f-DP guarantees of the binomial noise (c.f. Section 4.1 and the binomial mechanism (c.f. Section 4.2p that covers a variety of discrete differentially private mechanisms and compression mechanisms as special cases are obtained. Our analyses lead to tighter privacy guarantees for binomial noise than (6) and extend the results for the binomial mechanism in [ to local DP. To the best of our knowledge, this is the first work that investigates the f-DP guarantees of discrete-valuee mechanisms, and the results could possibly inspire the design of better differentially private compression mechanisms.
Inspired by the analytical results, we also leverage the privacy amplification of the sparsification scheme and propose a ternary stochastic compressor (c.f. Section 5) By accounting for the privacy amplification of compression, our analyses reveal that given a privacy budget G-GDP (which is a special case of f-DP) with μ < / //Arr(111 r) (in which is the ratio of non-zero coordinates in expectation for the sparsification scheme), the MSE of the ternary stochastic compressor only depends on μ in the use case of distributed mean estimation (which is the building block of FL). In this sense, we break the three-war way tradeoff between communication overhead, privacy. and accuracy by removing the dependency of accuracy on the communication overhead. Different from existing works which suggest that, in the high privacy regime, the error introduced by compression is dominated by the error introduced for privacy, we show that the error caused by compression could be translated into enhancement in privacy. Compared to SQKR [13. the proposed scheme yields better privacy guarantces given the same MSE and communication cost. For the scenario where each user i observes rr {-c, c) for some constant > O, the proposed scheme achieves the same privacy guarantee and MSE as those of the classic Gaussian mechanism in the large regime, which essentially means that the improvement in communication efficiency is achieved for free. We remark that the regime of large d is often of interest in practical FL in which d is the number of training parameters.
2 Related Work
Recently, there is a surge of interest in developing differentially private data analysis techniques, which can be divided into three categories: central differential privacy (CDP) that assumes a trusted central server to perturb the collected data [88, distributed differential privacy that relies on secure aggregation during data collection 3], and local differential privacy (LDP) that avoids the need for

---

the trusted server by perturbing the local data on the user side [9]. To overcome the drawbacks of the Gaussian and Laplacian mechanisms, several discrete mechanisms have been proposed. [T8] introduces the one-dimensional binomial noise, which is extended to the general d-dimensional case in [6] with more comprehensive analysis in terms of (c, 6)-DP. 20 analyzes the LDP guarantees of discrete Gaussian noise, while 77] further considers secure aggregation. [8] studies the Rényi DP guarantees of the Skellam mechanism. However, both the discrete Gaussian mechanism and the Skellam mechanism assume infinite ranges at the output, which makes them less communication efficient without appropriate clipping. Moreover, all the above three mechanisms achieve differential privacy at the cost of exploding variance for the additive noise in the high- high-privacy regimes.
Another line of studies jointly considers privacy preservation and compression. [10 [T] propose to achieve DP by quantizing, sampling, and perturbing each entry, while [12] proposes vector quantization scheme with local differential privacy. However, the MSE of these schemes grows watpuuniiiiiooiiivaagye aacuuracya tradeoff and incorporates
with d². [13 investigates the three-way Kashin's s representation to achieve order-optimal estimation error in mean estimation.
[2 proposes
to first sample a portion of coordinates, followed by the randomized response mechanism [22] [23
and [24] further incorporate shuffling for privacy amplification. [25] proposes to compress the LDP schemes using pseudorandom generator, while [26) utilizes minimal random coding. (27 proposes a privacy-award aware compression mechanism that accommodates DP requirement and unbiasedness simultaneously. However, they consider pure c-DP, which cannot be easily generalized to the relaxed variants. [9] proposes the Poisson binomial mechanism with Rényi DP guarantees. Nonetheless, Rényi DP lacks the favorable hypothesis testing interpretation and the conversion to 8).P) is lossy. Moreover, most of the existing works focus on privatizing the compressed data or vice versa, leaving the privacy guarantees of compression mechanisms largely unexplored. (28) proposes numerical accountant based on fast Fourier transform (2 to evaluate (c, DD of general discrete-valued
mechanisms. Recently, an independent work (30 studies privacy amplification by compression for central (e, 5D-DP and multi-message shuffling frameworks. In this work, we consider LDP through the lens of f-DP and eliminate the need for trusted server or shuffler.
Among the relaxations of differential privacy notions 31 16 32,. f-DP [5] is a variant of e-DP with hypothesis testing interpretation, which enjoys the property of lossless conversion to (c, 8DP and tight composition [33]. As a result, it leads to favorable performance in distributedffeddratee learning 34 B5). However, to the best of our knowledge, none of the existing works study the f-DP of discrete-valued mechanisms. In this work, we bridge the gap by deriving tight f-DP guarantees of various compression mechanisms in closed form, based on which ternary stochastic compressor is tradeoff than existing methods.
proposed to achieve a better caamuuniaaiionprvvcyaaacomo
3 Problem Setup and Preliminaries
3.1 Problem Setup
We consider a set of N users (denoted by N) with local data x; e Rd. The users aim to share x; 's and cmmmunication-effficce manner. More specifically, with central server in a peeecccpeeeeiinnggg mechanism M to obfuscate their data and share the perturbed the users adopt
results (1x)) 's with the central server. In the use case of distributeddfedderated learning, each user has a local dataset S. During each training step, it computes the local stochastic gradients and shares the obfuscated gradients with the server. In this sense, the overall gradient computation and obfuscation mechanism M takes the local dataset S as the input and outputs the obfuscated result MMSS). Upon receiving the shared M(S'ss, s, the server estimates the mean of the local gradients.
3.2 Differential Privacy
Formally, differential privacy is defined as follows.
Definition 1 5)-P [18). A randomized mechanism M is (c, -ddifferrenl private for all neighboring datasets and and all O O in the range of M, we have
P(M(S) E 0) < e e ((M(S') O) + 5.
(1)
in which S and S' are neighboring datasets that differ in only one record, and e, 2 0 are the parameters that characterize the level of differential privacy.
3

---

3.3 f-Differential Privacy
Assuming that there exist two neighboring datasets S and S', from the hypothesis testing perspective, we have the following two hypotheses
Ho the underlying dataset is S, H1 the underlying dataset is S
(2)
Let P and Q denote the probability distribution of M(S) and M(S"), respectively. 15 formulates the problem of distinguishing the two hypotheses the tradeoff between the achievable type and type II eπrоr rates. More precisely. consider a rejection rule 0 I Φ I 1 (which rejects Ho with probability of Φ). the type and type II error rates are defined as ag Ep [ő] and B& respectively. In this sense. f-DP characterizes the tradeoff between type I and type II error rates. The tradeoff function and f-DP are formally defined follows.
Eolo].
Definition 2 (tradeoff function (15)). For any two probability distributions and on the same space, the tradeoff function T(P. Q) [0, + [o, 1] is defined as T(P, Q) = =inf{ f as S a), where the infimum is taken over all (measurable) rejection rule é.
Definition (f-DP (5).. Let be a tradeoff function. With a slight abuse of notation, mechanism M is f-differentially private (MM() M((")) 2 f for all neighboring datasets S and S', which suggests that the attacker cannot achieve a type II error rate smaller than f(x)..
f-DP can be converted to (e, 6)-D as follows.
Lemma 1. [75] A mechanism is f(a) private if and only if it is ( diffffernenl private with
f(a) max 1 6-a (1-8, a))
Finally, we introduce a special case of fDDP with f(a) (0 a) 1)), which is denoted as μ-GDP. More specifically, j-GDP corresponds to the tradeoff function of two normal distributions with mean and Jr, respectively, and a variance of 1.
Tight f-DP Analysis for Existing Discrete-Valuu Valued Mechanisms
In this section, we derive the f-DP guarantees for variety of existing differentially private discrete- valued mechanisms in the scalar case (i.e., d = 1) to illustrate the main ideas. The vector case will be discussed in Section [6] More specifically, according to Definition [] the f-DP of a mechanism M is given by the infimum of the tradeoff function over all neighboring datasets S and S', i.e., [(a = s,s inf (Bp(a) as S a). Therefore, the analysis consists of two steps: 1) we obtain the closed-form expressions of the tradeoff functions, i.e., inf (Bp(a) as S a), for generic sescrete-valued mechanism (see Section A in the supplementary material); and 2) given the tradcoff functions, we derive the f-DP by identifying the mechanism-specifee infimums of the tradeoff functions over all possible neighboring datasets. We remark that the tradcoff functions for the discrete-ve valued mechanisms are essentially piece-wist functions with both the domain and range of each piece determined by both the mechanisms and the datasets, which renders the analysis for the second step highly non-trivial.
4.1 Binomial Noise
In this subsection, we consider the binomial noise (i.e., Algorithm I proposed in 6 which serves as a coammunication-effcieee alternative the classic Gaussian noise. More specifically, the output of stochastic quantization in 6 is perturbed by binomial random variable.
Algorithm 1 Binomial Noise 6
Input: E j0, 1, I. E N, number of trials M, success probability Privatization: Z, x4 + Binom(M, (M.
Theorem 1. Let 2 Binom (M (M, p). the binomial noise mechanism in Algorithm 1 is pmm (a)- differentially private with
f (a) min (. (3)nn(a)))
(4)

---

in which
P(Z 2 k +1)
P(Z r(z=ktt) P(Z=k) a,
P(Z=R)
(a))
for [P K), P(z = b)] k E M - 11,
0.
for a E [P(2 - M -1,
(5)
P(Z 1)- P(2 ((--8-0((22))
r(2=k-1) a: P(Z=k) p(2=k)
(a)
for [P(Z> > 1)), P(ž 2 k)). h E M,
(6)
0.
for E IP 2 1). 1].
D) -1)) can be readily shown that when p = 0.5, both (taue( and (ox) are maximized, and f(a)) = ( (..
Given that P(Z = k)
Fig. shows the impact of M when / = 8, which confirms the result in [6] that a larger M provides better privacy protection (recall that given the same a, a larger 3a indicates that the attacker makes mistakes the hypothesis testing more likely and therefore corresponds to better privacy protection). Note that the output of Algorithm [ Zi E {0, 1, ..., M + 1). which reqiures a communication overhead of log, [M (M+++) 1)+ bits. We can readily convert f (a)) to (c, 6)-DP by utilizing Lemma]
Remark 1. The results derived in this work improve 6 in
two aspects: (1) Theorem 1 in [6] requires Mp(1 p)
max(23 (ogg((/)))...m. 21 > max log 10), 21/s). in which
123
2-
1/& N is some scaling factor. When p = 12, requires M 212.
More specifically, for M = 500, (0 requires 5 >> 0.044, Our results imply that there exists some (c, 8) such that Algorithm 7 is (c, 5PP
04
0.2
as long M > I. For M 500, ô can be small as 4.61 x 10 136
(2) Our results are tight, in the sense that no relaxation is applied
20
05
244
0.5
0.8
20
Figure 1: Impact of M on Algo-
in our derivation. As example, when M = 500 and
0.5,
rithm 1 with = 8.
Theorem in (6] gives (3.18, 0.044)-DP while Theorem in this paper yields (1.67, D.P39)
4.2 Binomial Mechanism
Algorithm 2 Binomial Mechanism
9
Input: <> 0, 2 E [-c,c], M E N. (,,,) [rnnno Pmax]
Privatization: Z; A Binom (x.)).
In this subsection, we consider the binomial mechanism (i.e., Algorithm Different from Algo- rithm I that perturbs the data with noise following the binomial distribution with the same success probability, the binomial mechanism encodes the input x; into the success probability of the binomial distribution. We establish the privacy guarantee of Algorithm 2 as follows.
Theorem 2. The binomial mechanism in Algorithm 2 prm (ai-differettialll private with fbm (a) = m (a), B (..ne(a))
in which
P0.nn (a) = [1- < <k)+rP(Y = k)] = P(Y 2 k) + P(Y = k)P(P k) P(X K) for a E {P < k), P(X S k)] and k (0,1,2 ... ,,,,..,M, .M,, where X = Binoml M,Pmas) and
P(Y = k)
g+
P(X k)
Y = Binom Pomin) ) and
3 B7.nr (a)= = 1- I > k) + PP = k)] = P(Y <k) + P(Y = k)p(X> k)
P(Y = k)
P(X = k) O.
P(X = k)
for a E [P > P(X 2 b)] and E 1,, M), where X = BinoraMM (M.piia) and
Y Binom (M. ). When Pmax= = 1 Pmin. we have $ = (a).
Remark 2 (Comparison to (). The binomial mechanism part of the Poisson binomial mechanism proposed in (9). More specifically, in (9), each user i shares the output of the binomial mechanism
5

---

xx and 0 is some design parameter: It can be readily Pmi this case. The server then aggregates the result through MNO CEEN Z 2 (9 requires secure aggregation and considers the privacy leakage of releasing T. while we complement by showing the L.P,, i.e,, the privacy leakage of releasing 7. for each user. In addition, we eliminate the constraint 0 E [0, q).
Zi with the server. in which pz(2.) =
verified that Pmax MN
11, and the results hold for any selection of Pi (x.))) Moreover, the privacy guarantees in Theorem 2 are tight since no relaxation is involved. Fig. 2 shows the impact of M on the privacy guarantee. In contrast to binomial noise, the privacy of the binomial mechanisms improves as M (and equivalently communication overhead) decreases, which implies that it is more suitable for communication-consseeee constrained scenarios. We also derive the f-DP of in the supplementary material.
the Poisson binomial mechanism, which are presented in Section C
In the following, we present two existing compressors that are special cases of the binomial mechanism.
Example 1. We first consider the following stochastic sign compres- sor proposed in [36].
Definition 4 (Two-Level Stochastic Compressor given x E [-c, cl, the compressor sto-sign outputs
36
For any
1, with probability
A+z
24
24
2A
sto-sign(x, A) 1, with probability 2A
(8)
Figure 2: Impact of M on Algo- rithm
A-z
where A > the design parameter that controls the level of stochasticity.
With a slight modification (i.e., mapping the output space from {0, 1) 10 (-1,1}), sto-sign(z, A)
can be understood as special case of the binomial mechanism with M = and (x( Ats, In
24
this case, we have Pmaz=
2A
A+e. and Pmii A-C Applying the resulty in Theorem 2 vields
Atc for a E [0,
Ate
poto-sigm (a:) = = ( = Sa. (a) =
A-C
24
(9)
A-c a for a E 24 1 Ate 1].
1tc
Combining 9 with (3) suggests that the sto-sign compressor ensures (In( (
Example 2. The second sign-based compressor that we examine is CLDPx (.)
233
Definition 5 (CLDPs<() (23)). For any given x E [-c,c], the compressor CLDP outputs CLDP (c), which given by
+1, with probability 2
+ x 2c e1
CLDP
(10)
- with probability 2 2c el
x c²
CLDPx can be understood as special case of sto-sign(z, A) with A +1) according to we have
In this case,
e--1
1 1- for a E [0, Ate] 2A
CLDD (a) (1-1)a), for E [ [Atc,1]
(1I)
Combining the above result with (3) suggests that CLDPx ensures (c, ()-D), which recovers the result [23]. It is worth mentioning that CLDPx (c) can be understood as the composition of sto- sto-sign with A = followed by the randomized response mechanism [22], and is equivalent to the one dimeneiinnii case of the compressor in [13). Moreover, the one-immesioonal case of the schemes in 1O Tfy can also be understood as special cases of slo-sign.
5
The Proposed Ternary Compressor
The output of the binomial mechanism with M = 1 lies in the set (0, 1}, which coincides with the sign-based compressor. In this section, we extend the analysis to the ternary case, which can be understood as combination of sign-based quantization and sparsification (when the output takes value O, no transmission needed since it does not contain any information) and leads to improved communication efficiency. More specifically, we propose the following ternary compressor.

---

Definition 6 (Ternary Stochastic Compressor), For any given E [-c, c), the compressor ternary ouppus ternary(z, A. B). which is given by
1, with probability
A+z
2B
ternary(2, A. A)
0, with probability
(12)
B
1, with probability
A-z 2B
where > A> car the design parameters that control the level of sparsity.
For the ternary stochastic compressor in Definition 6
establish its privacy guarantee follows.
Theorem 3. The ternary stochastic compressor is sternar((a) differentially private with
1
Atc A-c a,
for a E [0, A-c]
tonury 2n77t, 3000PP
2B
pternary (o) 1 - B
c a, for a E
A-c
Atc
(13)
28
2B
A-c a for E
Atc
2B 1].
Remark 3 (Privacy amplification by sparsification). It can be
observed from ② and (13) that fternory (a) > fsto-sign when
Figure 3: Sparsification im-
1B Atc) and pernnry (a) fato-sign, otherwise. Fig.
proves privacy.
2B
3 3shows frernary (a) and fsto-sign for = 0.1, 0.25, 0.5,
and the shaded gray area corresponds to the improvement in privacy. It can be observed that commu- nication efficiency and privacy are improved simultaneously. is worth mentioning that, if we convert the privacy guarantees to (c,0) D)-P, we have c In(3) 3 for both compressors. However, the ternary compressor ensures (In(2), D.P (i.e., frernary (a) 2 max {0, 0.95 2ox, 0.5(0.95 a}}) while the sto-sign compressor does not. note that the same A, as increases (i.e., communication (which corresponds to perfect privacy).
cost decreases), plernary (a) approaches [(x) =
In the following, we present a special case of the proposed temarry stochastic compressor. Example 3. The ternayybassd compressor proposed in [37] is formally defined as follows.
Definition 7 (ternarize()) (37). For any given x E [-c, cl. the compressor ternarize(-) outputs ternorize(z; B) sign(x) with probability (xl/ B and ternarize(z, B) O otherwise, in which B > is the design parameter.
ternarize x. B) can be understood as a special case of ternary(a, A, B) with A = |z]. According Theorem 3 fternary
[0, g] and fiernary(a) for a Combining the above result with (3). we have ö = B and e 0, i.e ternarize(-) provides perfect privacy protection (e =0 0) with a violation probability of = B. Specifically, the attacker cannot distinguish x; from x if the output of ternarize((). differential privacy is provided if the output of ternarize(() + (violation of the privacy guarantee).
1- aor
c 1]. B
0 (perfect privacy protection), while no
Remark is worth mentioning that, (37], the users transmil scaled version of ternarize() and the scaling factor reveals the magnitude information of a.. Therefore, the compressor in (37] is not differentially private.
Breaking the CommunicttionPPrvvayy-ccuuu Tradeoff
In this section, we extend the results in Section 5 to the vector case in two different approaches, followed by discussions on the three-way tradeoff between communication, privacy, and accuracy. The results in Section Cean be extended similarly. Specifically, in the first approach, we derive the μ-GDP in closed form, while introducing some loss in privacy guarantees. In the second approach, a tight approximation is presented. Given the results in Section 5 we can readily convert f-DP in the scalar case to Gaussian differential privacy in the vector case as follows.
Theorem 4. Given a vector x; [Ii,11 Ti,2, ... , si.a) with |maي] S c, Vj. Applying the ternary compressor the j-th coordinate of x; independently yields p-GDP with μ --
1+1 A4ayy
Remark 5. Note that ||æi||2 E e sufficient condition for |æasl S e, Vj. In the proof of Theorem we first convert (arraar((a)-De to O)-DP for the scalar case, and then obtain (de, -)-
7

---

for the d-dimensional case. followed by the conversion to GDP. One may notice that some loss in privacy guarantee is introduced since the extreme case |وميع= j. actually violates the condition |a:ll2 S To address this issue, following a similar method in [13. 38 9 one may introduce Kashin's 's representation to transform the l2 geometry of the data into the I geometry. More specifically, [39] shows that for D > d, there exists a frame U such that for any x. E R one can always represent each x; with y: E 1-1o/vd, -70/ -70/Vdj for some 7/ and xi Uy:
In Theorem 4 some loss in privacy guarantees is introduced when we convert f-DP to H-GDP. In fact, since each coordinate of the vector is processed independently, the extension from the scalar case to the d-dimensional case may be understood as the d-fold composition of the mechanism in the scalar case. The composed result can be well approximated or numerically obtained via the central limit theorem for f-DP in [15] or the Edgeworth expansion in [33]. In the following, we present the result for the ternary compressor by utilizing the central limit theorem for fDPP.
Theorem 5. For vector 2; = [x 24.2 1M Fr,al with |و, I S c, Vj. the ternary compressor with B 2 A > is flernary (a) DD) with
Gyla 7) I (e) - G2 (a= 7) +
(14)
in which
de
0.56
A-c 2B
1
+
Atc 2B
1
+(1
4 B
B
y=
(15)
VAB - c²
0² d/
B B
Given the above results, we investigate the communication-piivcy---eee the proposed ternary stochastic compressor with the state-of-the-ar method SQKR in [13 and the classic Gaussian mechanism. According to the discussion in Remark [5] given the l2 norm constraint, Kashin's 's representation can be applied to transform it into the Loo geometry. Therefore, for ease of discussion, we consider the setting in which each user stores a vector I₁ = [Tt,1, 24,,, It,aa
tradeoff and compare
with |r, S < c= C va Vj. and ||0:||2 I C.
Ternary Stochastic Compressor: Let Zzj ternary(as.. A, B), then B[ Fij and Var (B2,)) AB - zi..- In this sense, applying the ternary stochastic compressor to each coordinate of z; independently yields unbiased estimator with variance of ABd || l|. The privacy guarantee is given by Theorem 5 and the communication overhead is (log2(d) 1) n d bits in expectation.
SQKR: In SQKR, each user first quantizes each coordinate of x; to {-c,e} with 1-bit stochastic quantization. Then, it samples & coordinates (with replacement) and privatizes the k bit message via the 2 Random response mechanism with e-LDP [14) The SQKR mechanism yields an unbiased estimator with a variance of { 42"
||= li. The privacy guarantee is c-LDP, and the corresponding communication overhead is (log2 (d) + 1)k bits.
Gaussian Mechanism: We apply the Gaussian mechanism (i.c., adding independent zero-mest f followed by a sparsification probability of A/ B as in Cernary(x... A, B), which gives Z Z,Gass B A (Ia,) + n4.5) with probability A/B B and
Gaussian noise ni, ~ (O, d²) to xi.)),
Z Gouss
otherwise. It can be observed that B|ZGauss] = zij and Var (2,) (Z(auss)= = 8 0² 8 1) 1) There-
fore, the Gaussian mechanism yields an unbiased estimator with variance of o + ( 1)||>, 2 By utilizing the post-processing property, it can be shown that the above Gaussian mechanism is 2v GDP [1], and the communication overhead is (log2(d) + 32) A d bits in expectation.
B
Discussion: It can be observed that for SQKR, with given privacy guarantee e-LDP, the variance (i.e., MSE) depends on k (i.e., the communication overhead). When e < 2 (which corresponds to the high privacy regime), the variance grows rapidly as increases. For the proposed ternary stochastic compressor, it can be observed that both the privacy guarantee (in terms of 4-GDP) and the variance depend on AB. Particularly, with given privacy guarantee μ < /4dr/(1 -r) for r r= A/B, the variance is given by (4d/)2² + 1)C - -|aa which remains the same regardless of the communication overhead. In this sense, we essentially remove the dependency of accuracy on the communication overhead and therefore break the three-wan way tradeoff between communication
8

---

10
Gissile Sparitty Radi 3.6
Goca Sparity Rade 0.6
2288---2
Brrtary Sponity Full
sary A
300
02
Spurity Futts
Figure 4: For the left figure, we set 10 and derive the corresponding variance for SQKR, based on which A and B for the temnrry stochastic compressor are computed such that they have the same communication overhead and MSE in expectation. The middle and right figures show the tradeoff between μ-GDP and MSE. For the middle figure, we set E C 2 3 1,2, 4. 6, 8, 10 for the Gaussian mechanism, given which A and B are computed such that AB = c² + o² and the sparsity ratio is A/B, For the right figure, we set A E {5c, 10c, 20c, 30c} and A/B E (0.2, 0.6, 0.8, 1.0). given which the corresponding o's are computed such that AB c² oz
overhead, privacy, and accuracy This is mainly realized by accounting for privacy amplification by sparsification. At a high level, when fewer coordinates are shared (which corresponds to larger privacy amplification and a larger MSE), the ternary stochastic compressor introduces less ambiguity to each coordinate (which corresponds to worse privacy protection and smaller MSE) such that both the privacy guarantee and the MSE remain the same. Since we use different differential privacy measures from 133 (i.e., 2t-GPP in this work and c-DP in [1]), we focus the comparison between the proposed ternary stochastic compressor and the Gaussian mechanism (which is order-optimal in most parameter regimes, (30]) in the following discussion and present the detailed comparison with SQKR in the experiments in Section 7
Let AB = c² + o², it can be observed that the f-DP guarantee of the ternary compressor ap- proaches that of the Gaussian mechanism as increases, and the corresponding variance is given by Var ()
c² 22.g. When A B, i..., sparsification is applied, we have (arr(B.,,)) Var (ar(ZZanu (ZGaus)) c² - Specifically, when æi, E (-c,c), V1 S S d, the ternary compressor demonstrates the same f-DP privacy guarantee and variance as that for the Gaus- sian mechanism, i.e., the improvement in communication efficiency obtained for free (in the large d regime). When B= > A, we have V Var(BBz - Var (ZGause) and there exists some such that the ternary compressor outperforms the Gaussian mechanism in terms of both variance and communication efficiency. It is worth mentioning that the privacy guarantee of the Gaussian mechanism is derived by utilizing the post-processing property. We believe that sparsification brings improvement in privacy for the Gaussian mechanism as well, which is, however, beyond the scope of this paper.
(1 2 )00² + c² 4x7,
Optimality: It has been shown that, for k-bit unbiased compression mechanisms, there is lower bound of (2(C2d/k) in MSE 40.. For the proposed ternary compressor, the MSE and the communica- tion cost are given by O(ABd) and A(log(d) + 1)d/ / B bits, respectively. Let k = A(log (d) + 1)dd/ B, it achieves an MSE of (log(()) + 1)/k). Since A > c C/ the MSE of the ternary compressor is given by O(C2d(log(d + 1)/k), which implics that it is order-optimal up to a factor of log(d), Note that the factor of log(d) is used to represent the indices of coordinates that are non-zero, which can be eliminated by allowing for shared randomness between the users and the server.
7 Experiments
In this section, examine the performance of the proposed ternary compressor in the case of distributed mean estimation. We follow the set-up of [9] and generate N = 1000 user vectors with dimension d = 250, i.c., 21, ...,, ZN E 250 Each local vector has bounded l2 and lac norms, i.c., ||æح||2 S C = and || le S c Va
Fig. 4 compares the proposed ternary stochastic compressor with SQKR and the Gaussian mechanism. More specifically, the left figure in Fig- 4 compares the privacy guarantees (in terms of the tradeoff between type and type II error rates) of the ternary stochastic compressor and SQKR given the
In practice, utilizing the closed-fore form expressions of the MSE and the privacy guarantee μ. one may readily obtain the corresponding A and B for any given privacy/MSE and communication cost specifications.

---

same communication overhead and MSE. It can be observed that the proposed ternary stochastic compressor outperforms SQKR in terms of privacy preservation, i.c., given the same type error rate the type II error rate B of the ternary stochastic compressor is significantly larger than that of SQKR, which implies better privacy protection. For example, for S with e 2. given type error rate a 0.5, the type II error rate of the attacker is around fSQKR (() = 0.068, while the ternary compressor attains flernery (a) 0.484. Given the same MSE and communication cost as that of SQKR with E {1,2. 2. 5]. if we translate the privacy guarantees of the ternary compressor from f-DP to EP via Lemma (we numerically test different e's such that flernery (()) 2 max(0,
5 - e 8 a)] holds for d 0), have Cternory {0.05, 0.2, 3.9} for the ternary compressor, which demonstrates its effectiveness. The middle and right figures in Fig. showw the tradeoff between MSE and DP guarantees for the Gaussian mechanism and the proposed ternary compressor. Particularly, in the middle figure, the tradeoff curves for the ternary compressor with all the examined sparsity ratios overlap with that of the Gaussian mechanism with A/B since they essentially have the same privacy guarantees, and the difference in MSE is negligible. For the Gaussian mechanism with 4 1, the MSE is larger due to sparsification, which validates our discussion in Section 6 In the right figure, we examine the MSEs of the proposed ternary compressor with various A's and B's. It can be observed that the corresponding tradcoff between MSE and privacy guarantee matches that of the Gaussian mechanism well, which validates that the improvement in communication efficiency for the proposed ternary compressor obtained for free.
8 Limitation
The main results derived in this paper are for the scalar case, which are extended to the vector case by invoking the central limit theorem. this case, the privacy guarantees derived in Theorem 5 are tight only in the large d regime. Fortunately, in applications like distributed learning, d corresponds to the model size (usually in the orders of millions for modern neural networks). Moreover, despite that the privacy-accuragy tradeoff of the proposed ternary compressor matches that of the Gaussian mechanism which is order-optimal (e, dDD the optimality of the proposed ternary compressor in the fDD regime needs to be further established.
9 Conclusion
In this paper, we derived the privacy guarantees of discrete- mechanisms with finite output space in the lens of f-differential privacy, which covered various differentially private mechanisms and compression mechanisms as special cases. Through leveraging the privacy amplification by sparsification, ternary compressor that achieves better eecuracy-privacyy drivacy-communicatiio tradeoff than existing methods is proposed. It is expected that the proposed methods can find broader applications in the design of communication efficient and differentially private federated data analysis techniques.
Acknowledgments and Disclosure of Funding
Richeng Jin was supported in part by the National Natural Science Foundation of China under Grant No. 62301487, in part by the Zhejiang Provincial Natural Science Foundation of China under Grant No. LQ23F010021, and in part by the Ng Teng Fong Charitable Foundation in the form of ZJU- SUTD IDEA Grant No. 188170-11 11-1111 102. Zhonggen Su was supported by the Fundamental Research Funds for the Central Universities Grants. Zhaoyang Zhang was supported in part by the National Natural Science Foundation of China under Grant No. U20A20158, in part by the National Key R&D Program of China under Grant No. 2020YFB 1007101, and in part by the Zhejiang Provincial Key R&D Program under Grant No. 2023C01021. Huaiyu Dai was supported by the US National Science Foundation under Grant No. ECCS-220322 The views expressed in this publication are those of the authors and do not necessarily reflect the views of the National Science Foundation.
References
[1] D. Wang, S. Shi, Y. Zhu, and Z. Han, "Federated analytics: Opportunities and challenges." IEFE Network, vol. 36, no. 1, pp. 151-158, 2021.
10

---

[2] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, "Communication-effiicei learning of deep networks from decentralized data," " in Artificial Intelligence and Statistics. PMLR, 2017, pp. 1273-1282.
[3] 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, vol. 14, no. 1, 2021.
[4] C. Dwork, F. McSherry, K. Nissim, and A. Smith, "Calibrating noise to sensitivity in private data analysis." in Theory of cryptography conference. Springer, 2006, pp. 265-284.
[5] I. Mironov, "On significance of the least significant bits for differential privacy," in Proceedings of the 2012 ACM conference on Computer and communications security, 2012, pp. 650-661.
[6] N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMahan, "cpSGD: Communication- efficient and infferentially-privatte distributed SGD," " in Advances in Neural Information Pro- cessing Systems, 2018, pp. 7564-7575.
[7] P. Kairouz, Z. Liu, and T. Steinke, "The distributed discrete gaussian mechanism for federated learning with secure aggregation," " in International Conference on Machine Learning. PMLR, 2021, pp. 5201-5212
[8] N. Agarwal, P. Kairouz, and Z. Liu, "The skellam mechanism for differentially private federated learning," Advances in Neural Information Processing Systems, vol. 34, pp. 5052-5064 2021.
[9] 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. PMLR, 2022, pp. 3490-3506.
[10] 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," arXiv preprint arXiv:1606.0500 05055, 2016.
[11] T. Wang, J. Zhao, X. Yang, and X. Ren, "Locally differentially private data collection and analysis," arXiv preprint arXiv: 1906.01777, 2019.
[12] V. Gandikota, D. Kane, R. K. Maity, and A. Mazumdar, "vqsgd: Vector quantized stochastic gradient descent," in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 2197-2205.
[13] W.-N. Chen, P. Kairouz, and A. Ozgur, "Breaking the trilemma," Advances in Neural Information Processing Systems, vol. 33, pp. 3312-3324, 2020.
[14] A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan, "Distributed mean estimation with limited communication," in International conference machine learning. PMLR, 2017, pp- 1329-3337.
[15] J. Dong, A. Roth, and W. Su, "Gaussian differential privacy." Journal of the Royal Statistical Society, 2021.
[16] I. Mironov, "Rényi differential privacy," in IEEE Computer Security Foundations Symposium (CSF). IEEE, 2017, pp. 263-275.
[17] A. El Ouadrhiri and A. Abdelhadi, "Differential privacy for deep and federated learning: A survey." IEEE Access, vol. 10, pp. 22 1235-222222 380, 2022.
[18] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, "Our data, ourselves: Pri- vacy via distributed noise generation," " in Annual international conference on the theory and applications of cryptographic techniques. Springer, 2006, pp. 486-503.
[19] P. Kasiviswanathan, H. K. Lee, K. Nissim, Raskhodnikova, and A. Smith, "What can we learn privately?" SIAM Journal on Computing. vol. 40, no. 3, pp. 793-826, 2011.
[20] C. L. Canonne, G. Kamath, and T. Steinke, "The discrete gaussian for differential privacy," Advances in Neural Information Processing Systems, vol. 33, pp. 15 676-15 688, 2020.
[21] G. Cormode and I. L. Markov, "Bit-efficient numerical aggregation and stronger privacy for trust in federated analyties." arXiv preprint orXiv:2108.0152) 2021.
[22] Kairouz, Oh, and P. Viswanath, "Extremal mechanisms for local differential privacy," The Journal of Machine Learning Research, vol. 17, no. 1, pp. 492-542,2016

---

[23] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. T. Suresh, "Shuffled model of differential pri- vacy in federated learning," in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 2521-2529.
[24] A. M. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. T. Suresh, "Shuffled model of federated learning: Privacy, aceuracy and communication trade-offs," IEEE journal selected areas in information theory, vol. 2, no. 1, pp. 464-478, 2021.
[25] V. Feldman and K. Talwar, "Lossless compression of efficient private local randomizers," in International Conference on Machine Learning. PMLR, 2021, pp. 3208-3219.
[26] A. Shah, W.-N. Chen, J. Balle, P. Kairouz, and L. Theis, "Optimal compression of locally differentially private mechanisms." in International Conference on Artificial Intelligence and Statistics. PMLR, 2022. pp. 7680-7723
[27] K. Chaudhuri, C. Guo, and M. Rabbat, "Privacy-aware compression for federated data analysis." in The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
[28] A. Koskela, J. Jälkö, L. Prediger, and A. Honkela, "Tight differential privacy for snscrete-valued mechanisms and for the subsampled gaussian mechanism using fft," in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 3358-3366
[29] A. Koskela, J. Jälkö, and A. Honkela, "Computing tight differential privacy guarantees using fit," in International Conference on Artificial Intelligence and Statistics. PMLR, 2020, pp. 1560-2569.
[30] W.-N. Chen, D. Song, A. Ozgur, and P. Kairouz, "Privacy amplification via compression: Achieving the optimal wur.o--acccrrrcoommunniiiiiooooi trade-off in distributed mean estima- tion," arXiv preprint 2rXiv:2304.01541 2023.
[31] C. Dwork and G. N. Rothblum, "Concentrated differential privacy." arXiv preprint
1603.008 2016.
[32] M. Bun, C. Dwork, G. N. Rothblum, and T. Steinke, "Composable and versatile privacy via truncated cdp." in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 74-86.
[33] Q. Zheng, J. Dong, Q. Long, and W. Su, "Sharp composition bounds for gaussian differential privacy via edgeworth expansion," " in International Conference on Machine Learning. PMLR, 2020, pp. 11 420-11 435.
[34] Z. Bu, J. Dong, Q. Long, and W. J. Su, "Deep learning with gaussian differential privacy." Harvard data science review, vol. 2020, no. 23, 2020.
[35] Q. Zheng, S. Chen, Q. Long, and W. Su, "Federated f-differential privacy," in International Conference Artificial Intelligence and Statistics. PMLR, 2021, pp. 2251-2259.
[36] R. Jin, Y. Huang, X. He, H. Dai, and T. Wu, "Stochastic-Sign SGD for federated learning with theoretical guarantees," " arXiv preprint arXiv:2002.10940, 2020.
[37] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li, "TernGrad: Ternary gradients
to reduce communication distributed deep learning," " in Advances in Neural Information Processing Systems, 2017, pp. 1509-1519.
[38] M. Safaryan, E. Shulgin, and P. Richtárik, "Uncertainty principle for communication compres- sion in distributed and federated learning and the search for optimal compressor," arXiv preprint 20Xi:2002.089555 2020.
[39] Y. Lyubarskii and R. Vershynin, "Uncertainty principles and vector quantization." IEEE Trans- actions on Information Theory, vol. 56, no. 7, pp. 3491-3501, 2010.
[40] W.-N. Chen, C. 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. PMLR, 2022, pp. 3056-3089.
[41] E. L. Lehmann, J. P. Romano, and G. Casella, Testing statistical hypotheses. Springer, 2005,
vol. 3.
[42] J. Lee, M. Kim, S. W. Kwak, and S. Jung, "Differentially private multivariate statistics with an application to contingency table analysis," arXiv preprint arXiv:2211.15012 2022.
[43] Y. Liu, K. Sun, L. Kong, and B. Jiang, "Identification, amplification and measurement: bridge to gaussian differential privacy," arXiv preprint arXiv:22100092269, 2022.
12

---

Breaking the Communcation-Piivcy-Akuuuua Tradeoff with f-Differential Privacy: Supplementary Material
A Tradeoff Functions for a Generic Discrete-Values Mechanism
We consider a general randomization protocol M(.) with discrete and finite output space. In this case, we can always find a one-to-one mapping between the range of MM.) and a subset of Z. With such consideration, we assume that the output of the randomization protocol is integer, i..., M(S) E 2M C Z, YS, without loss of generality, Given the randomization protocol and the hypothesis testing problem in ( we derive its tradeoff function function of the type error rate in the following lemma.
Lemma 2. For two neighboring datasets S and S' suppose that the range of the randomized mechanism R(M(S) ((M(())) = Z 12,,..., 21] C Z and ( 2 C z. Les = M(S) and Y = -(S"). Then,
Z/M- =
Case (1) If M(S) E 12/, 2 +1,, +1....,2y M(S) E [2% 24 + +1,... 2k), and P(Y=k) P(X=k) is
decreasing function of l for & E Σ' the tradeoff function in Definition 2 is given by
P(Y 2 +)+ P(Y=))((X
P(Y=k) P(X=k) -( a,
3
ifa (P(X < P(X S k)). k E [2 1/1.
(16)
if E (P(X < 2/ + 1),1]
Case (2) If MSS E [2) 2í, + + Z11. .MS') [2], 2/. 1,... 2%,, and P(Y=k)
p(X=k) is
increasing function of for k E E the tradeoff function funcetioo in Defimition 2 iivenv by
P(Y < k) + -(
p(Y=k)
P(X=
P(X=R) 02
(a(a)=
ifa (P(X > b), P(X 2 k)), ls E |2 2/1-
(17)
0,
if E (P(X > 1),11.
Remark 6. It is assumed in Lemma that P(Y=k) P(X= is a decreasing function (for part (I)) or an increasing function (for part (2)) of l E Z/M- without loss of generality. In practice, thanks to the post-processing property of DP (15), one can relabel the output of the mechanism to ensure that this condition holds and Lemma 2 can be adapted accordingly.
We note that in Lemma 2 both X and Y depend on both the randomized mechanism M(- and the neighboring datasets S and S' Therefore, the infinums of the tradeoff functions in (T) and (77) are mechanism-speciffe which should be analyzed individually. After identifying the neighboring datasets S and S that minimize 35 (ax) and B7 (a) for a mechanism M(.) (which is highly non-trivial), we can obtain the distributions of X and Y in (66) and 17) and derive the corresponding f-DP guarantees.
Remark 7.
Remark 8. Since 3 (a) is piecewise function with decreasing slopes w.r.t k (see, e.g., Fig. 1 it can P(Y=k)
be readily shown that 3 (a) 2 max{P(Y 2 k)
P(Y=k) P(X= P(X < k) PIX=R) 0}, wk Z'Me-
As a result, utilizing Lemmal 7 we may obtain different pairs of (e, 8) given different k's.
Remark 9. Although we assume a finite output space, similar method can be applied to the mechanisms with an infinite range, Taking the discrete Gaussian noise (20) as an example, M(x) = -202
x V V with P(V = v) Evez e yoat. One may easily verify that P(M(a.)=k) is decreasing P(M({)=K))
function of k if > x: (and increasing otherwise). Then we can find some threshold v for the rejection rule @ such that as. P(M(x.) S 50 = a, and the corresponding (0) = 1 P(M(())) S v).
The key to proving Lemma 2 is finding the rejection rule & such that (a(a)) is minimized for pre-determined a [0, 1]. To this end, we utilize the Seyman-Pearson Lemma [41), which states that for a given a, the most powerful rejection rule is threshold-based, i.e., if the likelihood ratio P(Y=)) P[ is larger than/equal to/smaller than threshold h, Ho is rejected with probability 1//00. More specifically, since and may have different ranges, we divide the discussion into two cases (i.e., Case (1) and Case (2) in Lemma 2 The Neyman- Pearsson Lemma 41 is given as follows.
13

---

Lemma 3. (Neyman-Peares Pearson Lemma (4T) Let P and Q be probability distributions on 22 with
densities p and q, respectively. For the hypothesis testing problem Ho P vs H1 Q, a test Φ: Φ: Ω + [0. 1] is the most powerfud test at level a if and only if there are two constants h E [0, + and 7 E (0, 1] such that & has the form
1, if 9(a)
> h,
plx)
(xx)
=
7: if p(a)
h,
(18)
0, if g(m) < h, p(x) and [p = a. The rejection rule suggests that Ho is rejected with probability of ((x) given the observation I.
Given Lemma 3 the problem is then reduced to finding the corresponding h and y such that the type error rate Os = a. For part (1) (the results for part (2) can be shown similarly), we divide the range of a (i.e.. [0, 1)) into multiple segments, as shown in Fig. 5 To achieve
0. we set h = oo
and y 1, which suggests that the hypothesis Ho is always rejected when k < 2 and accepted
otherwise. To achieve a E (P(X k), P(X k)], for k [Z) Z/1. we set P(X R)
P(Y=k) and
a-P(X<k) In this case, it can be shown that as = a E (P(X < k), P(X & k)]- To achieve P(
(P(X 2 + 1). 1], we set h O, and y a- P0 x> In this case, it can be shown that P(X>2k)
ag a E (P(X 2 + 1), The corresponding 3g can be derived accordingly, which is given by (6.. The complete proof is given below.
Proof. Given Lemma 3 the problem is reduced to finding the parameters h and in 18 such that Eylø] = a, which can be proved as follows.
Case (1) We divide E [0. 1] into z 3 + 1 segments: [P(X < ) P(X < U <
2)), P(X s u.. ... (P(X < k), P(X s U... u (P(X < P(X < 21 as shown
in Fig.
(P(x axf PCX #]]]
Figure 5: Dividing into multiple segments for part (1).
When a= = P(X < 2 = P(x < 2 = O, we set h = +o0. In this case, noticing that
=kY=k) = h for l 2 and P(Y=k) h otherwise, we have P(==))
P(==))
Ep(o) = - < z 0= a,
(19)
and
(0)
Fo - 7P(V < 2)).
(20)
The infimum is attained when 1, which yields 835 P(Y > 2/))
When E (P(X' < P(X < k)) for k E [2 2/), we set h P(Y=k)
P(Y=k)) P(X= In this case, P(X=K)
for K' k. and P(Y=k) P(X=K)
> h for k' k, and therefore
Ep = P(X < k) + 7PXX= = k).
(21)
We adjust y such that pp = a, which yields
a P(X <k)
(22)
P(X = =k)
and
8 (t( = 1- (P(Y k) + +P( = =k]]
0
= =PYY 2 k) - P(Y = k) a- P(X < k)
P(X = k)
(23)
= P(Y 2 k) + P(Y = 1) P(X <k)
P(Y k)) P(X k) a
P(X = k)
14

---

When E (P(X < k), < k)] for k (Z 2 set h 0. In this case, P(X=k)
P(Y=k))
h for
k 2/c, and P(==k) P(==))
for K' & 1/2 As a result,
Er P(X - 3/1 + 7P( > Z/d,
(24)
and
5t = |P - 2// + P > 2/1l =0 0
(25)
Similarly, we can prove the second part of Lemma 2 as follows.
Case (2) We also divide E 10 into 2 2/ + segments: [P(X > 2 P(X
2 21 U
...U (P(X > R), P(X 2 k)] U U (P(X > 2k P(X 2 2/)1, as shown in Fig. 6
3039
(PET 2
(0.
*b)1
Figure 6: Dividing in to multiple segments for part (2).
When E (P(X > 8), P(X 2 k)] for & Z(), set h = 0. In this case,
Br P(X 2/) + PPX < 2
(26)
and
(a)a) = 1 - |P(Y 2 z + + < 21 =0
(27)
When a E (P(X > k), P(X 2 k)] for & | k/4, we set h P(Y=k) In this case, P(X=k)
Eplø] = P(X > k) + 7P = k).
(28)
Setting Bp|ø] yields
a a- P(X > k)
=
(29)
P(X = k)
and
(a)
1 -1 [P(P > k) +TP(Y = x]]
= P(Y kk P(Y = k)) a- - P(X
(30)
P(X = k)
= P(Y 1k)+ + P(Y = P > k)
P(Y =k) P(X k) a
P(X = k)
When a = P(X> > 2//) = 0, we set h = +00. In this case,
Ep(0) [0) = -P > 2//3= = 0 = a,
(31)
and
8 (0) 1 - RQ[0] -1- > 2/2²
(32)
The infimum is attained when = 1, which yields 35 P(Y S 2
B Proofs of Theoretical Results
B.1 Proof of Theorem 1
Theorem 1. Let 2 Binom p). the binomial noise mechanism in Algorithm 1 is pmm (a)-
differentially private with
fmm (a) min inf (0),3
(33)
in which
P(ž 1 k+)
P(Z=k+))((<h)
p((=k+1)
P(2=k)
P(2=k) a,
(t)
for IP(Z < K), P(Z < k)), k E [0, - [J,
0,
for a E [P(2 < M 1).
(34)
15

---

1) P(Z=k-1)P(2Sh) p(2=k-1) P(Z=k) p(2=k) a,
(a)
a [P(Z > K), P( 2 k)), E M,,
(35)
0,
for E IP(2 2 1).
Given that P(Z k) = (1) p) it can be readily shown that when p = 0.5, both
3 (a)n and 5 (a) maximized, and f(a) in P (n))
Before proving Theorem | we first show the following lemma.
Lemma 4. Let X = x; + Binom(M (, p) and = x + Finom(M,2) p). Then, if xz > x'p
P( P(Y 2 k) + (( -(Y==))
P(X=A)
(a(a)=
ifa [P(X < k), P(X S k)], k E [1a, x. + M).
(36)
ifa (P(X x M + 1).1].
If d
P(Y k) + P(Y=RP((SE) P(
P(X=E) P(X=) a
5%(a) (a)
f k), P(X 2 k)), k E [,,, M).
(37)
0,
ifa (P(X x - 1),1
Proof of Lemma 4 When > 24, it can be easily verified that P(X k) > 0 only for & E [2 24
1, ..... 24 + +M,
P(Y = k)) > 0 only for lo E [x] x5 + 1,................. x + MI. For E [z,, .. , + M,,
have
(k- p m p) MM -kt2/
P(Y = k)
P(X = k)
k- pp k x p) k+zz
M
(38)
(N + x + 1) 1) - k: + x4 2) ... (N 16 xi) 1 1
P Pyol-a.
(k- Ia + 1)
+ 2) ... (k- x²1)
be observed that P(Y=k) decreasing function of k:. P(X=k)
When x; < ax can be easily verified that P(X k) > only for [ra, 22 + 1,... x. M).
P(Y = k) > 0 only for k
E
[r ot 1,... x + MJ. For & E [x,, .. 2 + M). we have
M
p) M M-
P(Y k)
P(X = k:)
(K-m:) p f- (1 p) M M-++z k.z
(39)
(k x () x + ... (K x;)
1 1-
P
(N + Fi + I) 1: + .. 2)... (N + x.)
p
It can be observed that proof.
P(Y=k) is an increasing function of k. and invoking Lemma P(X=k)
completes the
Given Lemma we are ready to prove Theorem
Proof of Theorem Let Ž = Binom p). X = I; + 7 and = x + Z. Two cases are considered:
Case 1: v; x//-
In this case, according to Lemma 4 we have
P(Y 2 k) +
(()=))((Xe))) P(Y=k) P(X=k)
P(X=T
8t (ar)
for E P(X < K), P(X < {)), |0,, + M).
(40)
0.
for E [P(X < o M),1],
16

---

In the following, we show the infimum of 3 (a). For the ease of presentation, let k = k - 2, and
T x A. Then, we have
P(Y 2 k) P(x + 22 P(2 2 + A),
P(Y = k) = P(Z k
(41)
P(X < k) = P(.: + < k) = p(ž <k),
P(X k) P(a; +Ō= -k)
40 can be rewritten as
P( A)
P(2=k+2)P(2<M)
P(Z=k+b) P(Z=k) a, for (P(Z < k)) P(2 < kb), i. E [0, M - A]]
k(Z-k)
(a)
0,
for a E [P(Z < M - 1].
(42)
Let J(A,)) = P (1= r(2=k+b)
r(2=6) a, we have
p(2=k)
J(A+1, - ((A J(A =
- A + 1) - P(ž = A)
(43)
[P <k) a].
P( =k=
Since a E [P(ž < P(2 < k)) we have P(ž < k) a E I-p(2 = =k),0). 0]. If P(ž
k ++A ++A+11 P( = k- A) 0, J(A + 1, - J(A,k) < - -P(2 k A) < 0. If
P(ž = k + P( k+ A) < 0, J(A + +1, - J(A, < -P k A + 1) < O.
As result, the infimum of (g) is attained when A A= 1,,,ie, I; = 1 and x 0. which yields
(a)
P(ž 2 k +) ((2=k)) p(2=k+1) P(Z=k)
p(2=k) a,
0t =
for E [P < 1), P(Z S }), k E M - I3, for E [P S M - 1).
(44)
0,
Case 2: x2 < x//.
In this case, according to Lemma 4 we have
P(Y s k) + (( P(Y=k) P(X=k) P(X=R) a,
(a))=
for E [P(X k), P(X 2 k)), k E [, + M).
(45)
for a E [P(X 2 2)), 1], In the following, we show the infimum of 3(a). For the ease of presentation, let k = k x4 and x 23 = A. Then, we have
0,
P(Y S k) P(a + 2 و k) = P(ž < k A),
P(Y = k) P(ž 1 k-
(46)
P(X > k) = P(., + > k) = p(Z> > it),
P(X = k) = P(x: + 2 = k) = p(ž = kk)
45
can be rewritten
P(ž < k - A)+ M2=k-A)P(2
P(2=k-2) P(Z=k) a
M[2=6]
(a)=
for E IP(2 > k), P(2 > k)), k E M],
(47)
0.
for IP A) 1].
Let J(A, k) = P - 12=1--))(221 ((2=k-1) a, we have m(=k)
P(Z=k)
J(A + 1,4) - = P(ž = =
-- -)
Piž=k = k A - - -tž = k - A)
(48)
P( 1 -c
P(Z = k))
17

---

Since a E [P(Z > P( 2 k)], we have P(ž > k) - E [-P(ž = k). If P(ž = -- k > 0, then J + 1, J(A, < - <0 If < -
-1) --4) 0, then -
As result, the infimum of // (a) is attained when A = i,i., = 0 and 2 = which yields
P(Z k -1
1(2=k-1) a.
P(Z- k)
P(
8 (a)
for a E P( > k) P(Z 2 k)] k E [1, M), for a E [P(Z 2 1).
(49)
0,
Combining and (49) completes the first part of the proof. When p 0.5, it can be found that both 3 iul (a) and 3 iiint (a) are maximized, and f(a) = (e) = ()iur(a).
B.2 Proof of Theorem 2
Theorem 2. The binomial mechanism in Algorithm 2 is f'm (a))((((aifeeetttiia private with
fmo (a) = m inint (1),3%.. (m)))
(50)
in which
(t.nr(a)= = 1- [PY < +Pp = k)] P(Y 2 k) P(Y = h)P(X < K) P(X k) for a E IP(X < k), P(X S k)] and (0,1, .. .M3, where X = Binom [M, Pemas) and
P(Y = k)
P(X = k)
Y = Binooo.,
and
B7. ( (a) = =1 [P(Y > +PPY = k)] P(Y kk)+ P(Y = -k)P(X> k)
P(Y = k))
P(X =k) k) for a E (P(X > k), P(X b)] and E 1,, M}, where X = Biinoaa (M, M,imi)) and Y Binom ( [M, P.nas). When Pmaz
P(X - k)
Pmiin we have Dt = (a)
Proof. Observing that the output space of the binomial mechanism remains the same for different data Fs i.e., 3/. 2/: = 0 and 2/2 = 2 M in Lemma Moreover, let X Binom (M.p)
k) and Y = Binom M, 4). we have P(X=)) (1)=*1-p)---
(1-0))
(
M a0l pl &. Similarly, we
consider the following two cases.
Case 1: q < p.
p(Y=k) In this case, can find that P(X=k) is decreasing function of k. Therefore, according Lemma we have
Bt = 1- - [P(Y < k) + +PY = k]]
P(Y 2 k) P(Y k) P(X < k)
P(X = k)
(51)
P(Y N k) P(Y = k( < k)
P(Y k) P(X k)
P(
In the following, we show that the infimum attained when p = Pmaz and q = Pmin- For Binomial
distribution Y, we have @P <k)
and aP(Y<K) < 0, Vk.
By
dq
0 ④ (a)
AP(Y <k) AP(Y = =k)
dq
0q
dq
OP(Y k)
AP(Y S k)
(52)
= -1 (1 7)
0g
0q
0.
Therefore, the infimum is attained when Pminn
Suppose X = Binom(M, p) and X = (in, Without loss of generality, assume p > p. Suppose that E [P(X- < k), P(X < k)] and a E [P(} < k), P(X < k)] for some k and satisfied simultancously, it can be readily shown that k k. In addition, [max{P(XX <
18

---

k), P(X < mi)) s), 3 k)Hl Let
(a) = P(Y 2 k) + P(Y = 1P -k) -
(53)
P(X =k)
and
P(Y = 1)((8 <k) -o
B (1) = P(Y 2 k))
(54)
P(X =k)
(a) -
P(Y [)( <b) a)
P(Y k)( < k) a
= P(Y 2 k) - P(Y 2 k)
P(X = k)
P(X = K)
(55)
P(Y P)( 5k) a)
P(Y P(( S K)) a
= P > k) - P(Y > k)
P(X = k)
P(X = k))
Obviously, P(Y 2 kk- 2 k) S 0 and P(Y > k)) P(Y > k) S 0 for k. Observing that 0.p (a) - 55 (a) is a linear function of a E [max < k), P(X min S
k), P(X < b)]l given Y, X, 8, le and ic, we consider the following four possible cases:
1) P(X < k) S P(X k) and a =Px < k): In this case, P(Y (((=)((((<))--) <k)
P(X=R)
P(Y -
< 0. As result, (a) _t s.
P(X=R)
2) P(X < k) > P(X < <k) and P(X < k): In this case,
8 (a) (a) - (a)
P(Y = k)[P(X <k) - al P(Y = =\) < <k) -a]
= P(Y 2 k) - P(Y R)
P(X k)
P( k)
(56)
P(Y = k)(P(X < <k) < < <b)]
= P(Y 2 k)) - P(Y 2 k)
P(X =k)
When h: ki since > é. we have P( < b) - PP(X < k)) > 0, which violates the condition that
P(X- <k) P(x < k).
When & > k we have P(Y 2 k) P(Y 2 1)) < -P(Y = k)). Therefore,
(a) (a) S -PYY k) P(Y = [P( h) - P(X k)]
P(X = k)
P(Y = P(( < k) P(X < k)]
(57)
P(X = k))
S..
3) P(X < k) < P(} < k) and a P(X < k): In this case,
P(Y P(( < k) - al
P(Y 1)(P({ <k) - a)
P(X = k)
P(X = k)
(58)
P(Y PP( < k)) P(X S <k)] 50
P(X =k)
As result, _t. (a) - (a)
(a) < P(Y > k) -PY k) 00.
4)
> P(X < 1)) and a = p( < i)): this case, when = k, P(X & <h) - P( s
i:) > 0, which violates the condition that P(X < k) > P(X < R).
19

---

When k> k
8 (1) (
P(Y = x)p((X <h) P = k)]
= P(Y 2 k) P(Y h)+
P(X = k)
P(Y = P) < -k)-P(X 1b)
(59)
P(X =k)
P(Y 2 k) - P(Y > k) P(Y = 1)[((X < - S [A]]
P(X = =k)
Since k > h, P(Y k) - -PYY= > 1) $ 0. In addition, P(X < k)) -P)x 1 k)) - 0 since
P(
a E [max P(( < k), P(X P(X,
P(X v R).. As a result, o.p (a) - (t,p(a) S P(Y >
k) P(Y > k) 5.
Now that /0.p( (0: - B (a) is linear function of a [max{P(XX < <)), P(X < k)), min s P(X < H. which is non non- non-positive in the extreme points (i.e., the boundaries), we conclude that B (T)(a)) $ < 0 for any a E [max{P(X k), P(X k)), min (P k), P(X s
}) Therefore, the infimum of 3 (a) is attained when p Pmax-
Case 2: 9
P( is an increasing function of k. As a result, according to Lemma In this case, we can find that P(X
we have
- k) P(Y = k)P(X k)
P(Y = k) P(X = k) a.
(60)
k(
Similarly, it can be shown that the infimum is attained when q = Pmaax and p = Pmin- As result, we have
T)P.Q)(a) = min B (a))
(61)
B.3 Proof of Theorem 3
Theorem 3. The ternary stochastic compressor is flermarv(a
private with
Atc
for a E [0, A-c)
A-o a,
2B
prornary (a)
1 - B - a, for a E A 1- 2B
Ate
(62)
28
A-c a for [1- Atc
Atc
.1..
2B
We provide the f-D analysis for a generic ternary stochastic compressor defined follows.
Definition 8 (Generic Ternary Stochastic Compressor). For any given E [-c, c). the generic compressor ternary outputs ternary (x, P1. Po. p-1). which given by
1, with probability pı (I:),
ternory PI.
(2, Po, P-1)
O. with probability po:
(63)
-1, with probability p-1(x),
where Po is the design parameter that controls the level sparsity and (1(z),p-11 E [pmin Pmaaw A+a
It can be readily verified that p1 = 2B -Po = 1- B. p-1
A-r (and therefore pmin 28
A_c and
28
Pmaz= Ate for the ternary stochastic compressor in Definition 6
In the following, we show the f-DP of the generic ternary stochastic compressor, and the corre- sponding f-D guarantee for the compressor in Definition 6 can be obtained with Puvin
A-c
2
A+c and Pa 1 4
Pmaz
20

---

(1() Lemma 5. Suppose that is independent of x, Pmaz + Pmiin = 1 - po, and p1 p1
The ternary compressor is fternery ( differentiall private with
Pmoz a,
for a E [0, Pmin]:
Pmin
flernary
Po + 2pmin a, for a E [pmin:: Pmnaa]:
(64)
Prasn
Pmit at,
for a E [1 Pmaz: 1]:
Pmuux
Pmux
Proof. Similar to the binomial mechanism, the output space of the ternary mechanism remains the same for different inputs. Let Y ternary(s4, Po. p-1) and X ternary(2;, Pi, Po, P-1), we have
P(Y = - p- p-1(2)) (2/)
P(X -1) p=1(
P(Y = 0)
P(X = =0) -1
(65)
P(Y = 1)
P(X =) (I;);)
When ny x4, it can be observed that we have
P(Y is decreasing function of k. According to Lemma 2 -[X=k)
1 p-1(z²)
p-1(2;) a,
for [-, (x:)];
(T(a)=
pa pippl1 (x() + p- (x;) a, for E (x:), p (4:)];
(66)
(x()
pi(e))
for E [1 Pı (3x4), 1].
pi(z.)
When 2; < x/, it can be observed that
P(Y is an increasing function of k. According to Lemma P(X k
2 we have
Pı (ai) 0t,
pı (m')
for [0, P1 (x:)):
87(a)
Po p-(()()) + p1 (I:)) a, for (p) (x:), p-1 1 (2:)];
(67)
p-)(x() p-1(e²)
for a E [1-p-1(z;;. 1].
P-1(z(] p-1(z.)
The infimum 3 (a) is attained when p- (2/) = Pmar and p-1 = Pmin, while the infimum of B (a) is attained when pl (ixx)) Pmax and pı (I,)) Pmin As result, we have for a E [0, Pmin): po + 2pmin for a E [pmin: Pmnaz]:
Pmoz O Pinin
glernary (a)
(68)
Punin Pmuz
for E [1 Pmaax; 1].
Pmax
which completes the proof.
B.4 Proof of Theorem
Theorem 4. Given a vector H;
Ti,,,, ;I.,, with [2ae] S c, Vj. Applying the ternary
compressor the j-th coordinate of x; independently yields p-GDP with μ -2 1+1
Before proving Theorem 4 we first introduce the following lemma.
Lemma 6. 442 43) Any (c, DD algorithm is also p-GDP for -20---1 ((12)) in which ((-)
is the cumulative function of normal distribution.
Proof. According to Theorem in the scalar case, the ternary stochastic compressor i flernory (a))- differentially private with
1 Atc A-ca a,
for E [0,
A-c 2F
flernary
1 - - a, for a
A Ate 2Ø
(69)
2B
A-c A-c for [1
Atc 2B 1].
Atc A+c
21

---

It can be easily verified that (tornary(a) 2 ma 1 1 - suggests that is (log( A A+ O). Extending it the d-dimensional case yields (d Atc) M DP. As a result, according to Lemma it is -24 1 1+14 )
(1- a)}..
Invoking Lemma
B.5 Proof of Theorem 5
Theorem 5. For vector 2; = [+t,] Ti,2, :. Fi,a] with |نi S c, Vj. the ternary compressor with
B 2 A i plernry
(ernory(a)--DF (a)-DP with
Gy(a + 7) 7 pternary (a) S G2 (a= ?) + 7-
(70)
in which
dede
0.56
A-c
2B
A+C 2B
+ (1 1
11 VAB
(71)
33/2
Before proving Theorem 5
we first define the following functions as in 15
kl(s) =
log (x:))dd,
(72)
(f) [ log" (ff(x))
(73)
ka(f) = S. |log If (z)
(74)
Ri (f( [-' +
(75)
The central limit theorem for f-DP is formally introduced as follows.
Lemma 7 ((15).. Let fi,.., fn be symmetric trade-off functions such that ka(fi) < oo for all
1 1 Kis d. Denote
2 ||
0.56 Ri 11
and 7 (112211 ||1]
VIKaa| - |
and assume 7 4. Then, for all l7, 7.. we have
Gy(a S J1 @ fa 8 ... @ Sa(a) < G, -7) 7
(76)
Given Lemma we ready prove Theorem
Proof. Given fa in 622
we have
A
C
A+c
(A-c)
kl())
log
+
log
2B
A -
2B
(A+c)
A+c
A
log
2B
2B
A c
(A+C)
log
B
A -
(2)
2B
-
log? 2
A A+ c
A
+
Atc c
2B
log (A-c)
(A+c)
(78)
A
+C
log
B
A
A + c
A c
(A-c)
ka()) =
log
+
log
2B
1
2B
A+c)
(79)
A+
|
log
B
A
C
A
A
C 3 B
A
c 37
A
+
c
3
Ra(f)=
1
+
+
log
(80)
2B
B
2B
B
B
A
22

---

The corresponding and are given as follows
2d
c B
dv
(81)
VAB - c²
B2d
0.56
A-c 2B
1
+
3
+
Ate
+
+
1 3
B
28
(82)
[
8/2
B
which completes the proof.
C f-DP of the Poisson Binomial Mechanism
The Poisson binomial mechanism g is presented in Algorithm
3
In the following, we show the
Algorithm 3 Poisson Binomial Mechanism
Input: ps E [min Pmazly Vi E
Privatization: 7pb - PB(pI.P2." .PN) = EiEN Binom M, P:).
[-DP guarantee of the Poisson binomial mechanism with M 1. The extension the proof for M > 1 is straightforward by following a similar technique.
Theorem 6. The Poisson binomial mechanism with M = 1 in Algorithm 3 is (a))aaafffeeenti)) private with
1 Pminn 0, Pmin (1 -1- aa)
(a) min
max
0,1
Pinar
Pmax
(83)
max 0,
Pmax
1 -
Pmax (1 - at)
Prrén
Pmnin
Proof. For Poisson Binomial, let
X PB(p1,
,PN);
Y = PB P2. ... PP- Pi+1, .PN),
(84)
(B P2. ... PP- Pi+1, ... .PN);
in which PB stands for Poisson Binomial. In this case,
P(Y + 1) P(Z t 1)(1 14, + P(Z k))p
(85)
P(X = k 11 P(Z = k 1) p:) + P(Z k)pp
In addition,
P(Y = k 1)P(X k) P(Y k)P(X k
(86)
[P(Z k 1) k k- -)-((= (P(Z= k)) -
Since P k 1P(() = -k))² for Poisson Binomial distribution, we have
O, if ps p/.
= - k) k <0,
(87)
if p/.
That being said, P(Y is an increasing function of A if < p/: and decreasing function of k if P(X=
Ps > p/. Following the same analysis that the proof of Theorem for P: p/, we have 5 (a) [P(Y < + +P k)]
= P(Y 2 k) P(Y = k) a P(X < k)
P(X = k)
(88)
P(Y 2 k) + P(Y P < k)
P(Y = k)
P(X = k) a,
P(X = k)
for a E [P(X < P(X < k)) and (0. 1,2. N).
In the following, show that the infimum of $5 (a) is attained when pl Pmax and pt Pmin-
23

---

Case 1: h = 0. In this case,
P(Y 2 0) 1,
P(Y =0) P(Z - ()(1 p(),
(89)
P(X <0) = 0,
P(X 0) P(z 0)(1 pi).
Plugging
89 into 88
yields
1- P/
(a) = 1 Pi a.
(90)
It is obvious that the infimum is attained when p; Pmax and p.z Pmin-
Case 2: 0. In this case.
P(Y 2 k) = P(Z 2 k) + P(Z= 1)p's
P(Y = k) = P(Z = 10(11pp] p1) + P(Z = 1)p/s
(91)
P(X k) P(Z P(Z = -- -1)ppt
P(X = k) = P[Z = =1)(1 (()- + P(Z = =k 1)p:-
Plugging (91 into (88)
yields
P(Z = k) - [P(Z 1P(Z=No k) P(Z = k
1)p
8 (a) p(Z > k)) + P(Z = k)ps + IP(X < k) a]
P(X k)
(92)
The pl related term is given by
P(X k) [P(Z= - - = 5k) - -k) a1
1/4
(93)
P(X=h)
p(
Observing that (93) is linear function of a, we only need to examine [P(X < P(X k)). More specifically, when a = P(X S k)., it is reduced to P(z = k)pf; when a = P(X < k), it
reduced to P(Z = 1 1)p'. In both cases, the infimum is attained when p/: Pmin-
Given that p/ Pmin- the same technique as in the proof of Theorem can be applied to show that the infimum is attained when Pmar.
p(Y=k) is decreasing function of k when p; > P'. we have P(X=
Since
Pmnén
P(X = k) S Pmin
P(Y k)
(94)
Pmaz
Pmar
Given that 3 (a) is a decreasing function of a with 3 (0) 1 and (+) 0. we can readily
conclude that 8 (ax) 2 max
1- Pmin o}} and 8 (ax) 2
Puii
(1 a). That being said,
I- Pmax
Pmar
(a) 2 max (0, 1 1-Pmin
I-pmar a
Punin
a)}.
Pmaz
Similarly, for < p/c we have
3 (a) = 1 [P(P > k) +TP(Y = k]]
=P(Y k) - P(Y =k) a- P(X > k)
P(X= kk)
(95)
P(Y <) + P(Y P(X
P(Y =
P(X k)) for a E [P(X > B), P(X 2)) k)) and E (0,1,2, ... .N. The infimum is attained when p; = Pmin+
p/_ Pmaz-
Since
pk)=k) P(X=k) an increasing function of when p; < p/, we have
1 - Pmox
P(Y = k) < Pmax
<
(96)
1 - Pmin
P(X k)
Pmin
Given that 37 (a) is an increasing function of with 37 (0) = 1 and 37 (1) 0, we can easily
conclude that 356 (ax 2 max(0,
Piaax a)) and 3 (a) 2 I- Pmin Pmnn
Pouz
ax. That being said,
37(a) 2 max (0, 1 Prazz Or, I-Pmen a)).
Poncz
Prax
24


Reviews:
[{"review_id": "Bok99hWZCv", "reviewer": "Reviewer_191s", "summary": "In a federated setting where a server coordinates the collaborative analysis of multiple users with local data, communication efficiency and data privacy are two major issues of consideration. Classical DP mechanisms such as Laplace or Gaussian mechanisms add noises as real numbers -- at the same time, to save communication cost it is preferred to have discrete noises with limited range (resolution). This paper considers all three aspects: communication efficiency, privacy, and accuracy. Specifically, the authors would like to study privacy guarantee of data compression schemes, which intuitively introduces information loss and thus is good for protecting privacy.\n \nThe authors use f-DP, and considers binomial mechanisms. Binomial mechanisms have been considered in [6] and [9], this paper provides tighter bounds. In addition, the authors also consider a compression scheme that optimizes for communication efficiency. This is a combination of a sign based quantization and sparsification.", "questions": "Are there any lower bounds on the tradeoff of the three considerations? Any discussion here would be useful.\n\nWriting: it would be good to summarize somewhere in the paper the best recommendation for practitioners, what parameters to choose etc.\n\nIs there general improvement (amplification of privacy) using compression/sparsification? Can the authors elaborate/discuss this?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the motivation of the paper and the consideration of all three objectives, communication efficiency, privacy and accuracy together. The tighter analysis and mechanisms for communication efficiency is of use in practice. \n\nAlthough the work builds on prior work the improvement by considering compression for privacy amplification is nice. The paper is generally well written. ", "weaknesses": "A few minor issues, see below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 191s,\n\nWe appreciate your time and effort in reviewing and providing a positive evaluation of our work. Please find the point-by-point response to the comments below.\n\n**Comment:** Are there any lower bounds on the tradeoff of the three considerations? \n\n**Response:** We fully agree that deriving the lower bounds is of critical importance to evaluate the optimality of the mechanism. For the lower bounds without privacy constraints, Theorem 5.3 in [R1] shows a lower bound of $\\Omega(\\frac{C^{2}d}{nb})$ for $b$-bit unbiased compression mechanisms, in which $n$ is the number of users. In our case, the MSE for a single user is $O(ABd)$ and the communication cost is $(\\log(d)+1)\\frac{A}{B}d$ bits. Let $b = (\\log(d)+1)\\frac{A}{B}d$, we have an MSE of $O(\\frac{A^{2}d^{2}(\\log(d)+1)}{b})$. Since $A > c = \\frac{C}{\\sqrt{d}}$, the MSE for $n$ users is therefore given by $O(\\frac{C^{2}d(\\log(d)+1)}{nb})$, which implies that the proposed mechanism is order-optimal up to a factor of $\\log(d)$. Note that the factor of $\\log(d)$ is used to represent the index of coordinates that are non-zero, which can be eliminated by allowing for shared randomness.\n\nFor the lower bounds given the privacy constraint, unfortunately, different from $(\\epsilon,\\delta)$-DP for which numerous existing works have derived the lower bounds in mean estimation, there is no such lower bound for $f$-DP in the existing literature. We believe that the analyses are highly non-trivial and deserve independent work. \n\nHowever, it can be shown that the proposed ternary compressor is order-optimal in terms of $(\\epsilon,\\delta)$-DP. Particularly, Corollary 2.13 in [R2] shows that a mechanism is $\\mu$-GDP if and only if it is $(\\epsilon,\\delta(\\epsilon))$-DP for any $\\epsilon \\geq 0$ with $\\delta(\\epsilon) = \\Phi(-\\frac{\\epsilon}{\\mu}+\\frac{\\mu}{2}) - e^{\\epsilon}\\Phi(-\\frac{\\epsilon}{\\mu}-\\frac{\\mu}{2})$. In terms of $(\\epsilon,\\delta)$-DP, the Gaussian mechanism achieves an MSE of $O(\\frac{C^{2}d\\log(1/\\delta)}{n^{2}\\epsilon^{2}})$ for central DP (and there will be a loss of factor $n$ for local DP), which is order-optimal (see, e.g., Theorem 3.1 of [R3]). Note that, in terms of $\\mu$-GDP, the proposed ternary compressor induces an MSE of $4dC^{2}/\\mu^{2} + C^{2} -||x||_{2}^{2}$ \n\nwhile the Gaussian mechanism has an MSE of $4dC^{2}/\\mu^{2}$. Notice that the difference $C^{2}-||x||_{2}^{2}$ is a constant and becomes zero when the distribution of $x$ is supported on $[-c,c]^{d}$ (which is adopted in the derivation of the lower bound in [R3]). Since the Gaussian mechanism is order-optimal, the proposed ternary compressor is also order-optimal.\n\n[R1] Chen, Wei-Ning, Christopher A. Choquette Choo, Peter Kairouz, and Ananda Theertha Suresh. \"The fundamental price of secure aggregation in differentially private federated learning.\" In International Conference on Machine Learning, pp. 3056-3089. PMLR, 2022.\n\n[R2] Dong, Jinshuo, Aaron Roth, and Weijie J. Su. \"Gaussian differential privacy.\" Journal of the Royal Statistical Society Series B: Statistical Methodology 84, no. 1 (2022): 3-37.\n\n[R3] Cai, T. Tony, Yichen Wang, and Linjun Zhang. \"The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.\" The Annals of Statistics 49, no. 5 (2021): 2825-2850.\n\n**Comment:** It would be good to summarize somewhere in the paper the best recommendation for practitioners, what parameters to choose etc.\n\n**Response:** Thanks for the constructive comment. There are two parameters (i.e., $A$ and $B$) to choose for our proposed ternary compressor. $AB$ determines the $f$-DP guarantees and the MSE while $A/B$ determines the communication cost (in expectation). Utilizing the closed-form expressions that we derive, the corresponding $A$ and $B$ can be readily obtained for any given privacy/MSE and communication cost specifications. We will add more discussions in the discussion part of Section 6.\n\n**Comment:** Is there general improvement (amplification of privacy) using compression/sparsification? \n\n**Response:** This is a great question that our work endeavors to answer. Intuitively, compression and sparsification introduce noise into the system and less useful information is transmitted, which would lead to privacy improvement. However, in terms of DP, compression itself does not necessarily provide privacy guarantees since DP considers the worst-case scenario. Here is a toy example. Suppose that there is a scalar $x\\in [-1,1]$, and the user shares $sign(x)$ with the central server. Then, the central server can distinguish any $x > 0$ from $x < 0$ given $sign(x)$, which corresponds to $\\epsilon = \\infty$ since $\\frac{P(sign(x) = +1|x > 0)}{P(sign(x)=+1|x<0)} = \\frac{1}{0}$, i.e., no differential privacy is preserved. \n\nNonetheless, it is likely that sparsification does bring privacy amplification to DP mechanisms. For example, suppose that random sparsification is adopted and a user shares 0 with the server with a probability of $1-\\delta$ regardless of its local data $x$. Then the random sparsification scheme itself is $(0,\\delta)$-DP, i.e., perfect privacy (when the central server receives 0) with a violation probability of $\\delta$ (when the user shares $x$). If the shared $x$ is itself differentially private, we believe the random sparsification scheme will further enhance it. \n\nHowever, mathematically measuring the amplification in privacy may be difficult. In fact, this work constitutes the first step towards this goal by analyzing the tradeoff function between type I and type II error rates in $f$-DP (please see Lemma 2 in Appendix A) for a generic discrete-valued mechanism. Unfortunately, quantifying the $f$-DP guarantees without explicit expression for the compression/sparsification scheme is still infeasible, and we conduct analyses on several popular compression and differentially private mechanisms in this work. We will consider extending the analyses to more general cases in our future work.\n"}, {"review_id": "vs2MI9N1pC", "reviewer": "Reviewer_Mzdj", "summary": "This paper analyses the privacy that is provided by stochastic rounding methods when doing distributed mean estimation with local differential privacy. It finds that they can contribute to the privacy guarantee thus achieving a better tradeoff.\n\nIt then \"breaks\" the privacy communication utility trade-off in the sense of pointing out that for the high privacy regime extra communication won't buy you any more accuracy.", "questions": "Fixing two of privacy/communication/utility how much does taking advantage of the randomness in the compression actually help the other one?\n\nAm I missing something with the breaking of the trade-off?", "limitations": "They don't really talk about the limitations, indeed the limitations aren't really clear from the presentation.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Previous naive means of implementing DP aggregation with randomised rounding have failed to take advantage of the privacy provided by stochastic compression. This should be utilised if possible which they attempt to do.", "weaknesses": "The presentation fails to show a decent comparison showing hwo much is really gained by taking advantage of this randomness. It isn't clear the gain isn't negligible. There is a graph comparing ternary and binary quantisation but it isn't clear whether the parameters actually correspond to low communication, which would require sufficient sparsity.\n\nThe supposed break of the three way trade off is really just the observation that in the high privacy regime there is no gain to lots of communication. This is not what break means, the title is overselling.\n\nWhat is more this observation is very far from new. The idea that O(epsilon) communication suffices goes back a long way for various problems. This was proven with complete generality in https://arxiv.org/pdf/2102.12099.pdf.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Mzdj,\n\nWe appreciate your time in reviewing our paper and providing constructive comments. We believe that the concerns are mainly due to misunderstanding, please find our response below.\n\n**Our contribution**: We would like to clarify that, as we discussed in the global response, our contribution is more than analyzing the privacy guarantees of stochastic rounding methods in distributed mean estimation with local DP, but advancing the literature by deriving tight privacy guarantees for various DP and compression mechanisms (we believe showing their $f$-DP guarantees is important on its own since it enjoys better composition property than other variants, see e.g., Fig.6 in [R1]), and proposing ternary compressor that exploits privacy amplification in compression.\n\n[R1] El Ouadrhiri, Ahmed, and Ahmed Abdelhadi. \"Differential privacy for deep and federated learning: A survey.\" IEEE Access, 2022.\n\n**Comment:** It isn't clear whether the gain is negligible and the parameters correspond to low communication.\n\n**Response:** We are afraid that this concern is due to a misunderstanding. A larger gain in privacy always corresponds to a larger improvement in communication. We believe that the graph you mention is Fig. 3 in the manuscript. As we discussed in Remark 3, we set $A=0.25$ and $B=0.5$ to generate the figure, which means that the sparsity ratio is 0.5. In addition, the parameters of $A$ and $B$ in Fig. 3 are selected for the purpose of illustration. For the proposed ternary compressor, more aggressive compression (i.e., lower communication) leads to larger privacy amplification. Specifically, the gray area in Fig. 3 corresponds to the privacy improvement (in which $\\alpha \\in [(A-c)/2B, 1-(A+c)/2B]$ and $f(\\alpha) = 1-c/B-\\alpha$ in Eq.(13)). For any $A$, increasing $B$ makes the output sparser, and $f(\\alpha) = 1-c/B-\\alpha$ approaches $f(\\alpha) = 1-\\alpha$ (which corresponds to perfect privacy). In this sense, as the communication cost decreases to zero (i.e., the output is always 0), the privacy guarantee improves and approaches perfect privacy. \n\nMoreover, as we discussed in our global response, the gain in privacy is not negligible. \n\n**Comment:** The supposed break of the three way trade off is just the observation that in the high privacy regime there is no gain to lots of communication. The title is overselling. \n\n**Response:** We acknowledge that there is rich literature showing that $O(\\epsilon)$ communication is sufficient, and this work is partially inspired by [13] which breaks the communication-privacy-accuracy trilemma by proposing SQKR. However, as we discussed in our global response, the message that this paper delivers is not ``communicating less will not hurt the utility much under privacy constraints``, but instead ``the loss in utility caused by communicating less is translated to enhancement in privacy``. Therefore, the results that we present are different from the existing literature, and we do not think the title is overselling. More specifically, existing methods either apply differentially private mechanisms to the compressed output (e.g., SQKR in [13]) or compress the output of differentially private mechanisms (e.g., [R1] mentioned by the reviewer). These mechanisms do not utilize privacy enhancement by compression (which is the focus of this paper). Particularly, the utility of the methods in [R1] depends on the quality of the pseudorandom generator while the utility of SQKR depends on the communication cost $k$. On the contrary, the proposed ternary compressor utilizes privacy amplification in compression, and the tradeoff is essentially only between privacy and accuracy. Since we further improve the results in [13], we also use the word ``break\". If the reviewer has better suggestions on the title, we will consider revising it seriously.\n\nMoreover, despite the condition $\\mu < \\sqrt{4dr/(1-r)}$, our results are not constrained in the high privacy or low privacy regimes. As $r = A/B$ increases and approaches 1 (i.e., no sparsification), the right-hand side of the inequality goes to infinity.\n\n[R1] Feldman, Vitaly, and Kunal Talwar. \"Lossless compression of efficient private local randomizers.\" In International Conference on Machine Learning, 2021.\n\n**Question:** Fixing two of privacy/communication/utility how much does taking advantage of the randomness in the compression actually help the other one?\n\n**Response:** We compare the proposed ternary compressor with SQKR in the left figure of Fig. 4 in the manuscript. As we discussed in our global response, given the same MSE and communication cost as those of SQKR with $\\epsilon_{SQKR} = \\\\{1,2,5\\\\}$, the proposed ternary compressor attains privacy guarantees of $\\epsilon_{ternary} = \\\\{0.05,0.2,3.9\\\\}$ by exploiting the privacy amplification in compression. We also compare the proposed ternary compressor with the Gaussian mechanism given the same privacy and utility requirements in the right figure in Fig. 4. It is shown that despite the improvement in communication efficiency (at least 32x if we use 32 bits to represent a float), the tradeoff between privacy and utility for the ternary mechanism matches that of the Gaussian mechanism (i.e., privacy for free).\n\n**Limitations:** We did not add a section to explicitly discuss the limitations due to space constraints, which we will add in our revised manuscript. As we briefly discussed in our discussion below Fig. 4, the improvement in communication efficiency is obtained for free only in the large $d$ regime. Fortunately, in applications like distributed learning, $d$ corresponds to the model size (usually in the orders of millions for modern neural networks). Moreover, despite that the privacy-accuracy tradeoff of the proposed ternary compressor matches that of the Gaussian mechanism which is order-optimal in $(\\epsilon,\\delta)$-DP, we do not show its optimality by deriving lower bounds in the $f$-DP regime. We will investigate it in future work."}, {"review_id": "YbXk3GGItt", "reviewer": "Reviewer_VYNX", "summary": "This paper investigates the f-DP guarantee of several discrete-valued mechanisms in the local-DP model. In particular, closed-form expressions for binomial noise mechanism and Binomial mechanics are derived. \n\nThen, the paper considers the popular problem of aggregating d-dimensional vectors from local users subject to privacy communication constraints. Under the f-DP framework, this paper presents a new \"ternary\" mechanism and analyzes its f-DP privacy guarantee. Roughly, the ternary mechanism allows each local user to sparsify their vectors by keeping each coordinate with only a small probability and adding noises to the alive coordinates. The hope is that by sparsification and randomization, one can optimize communication (i.e., minimizing the messages from each user to the server) and privacy cost (e.g., each user has its signal \"somewhat hidden\" in the noises).\n\nThe paper's main claim is that, by working with f-DP and the ternary mechanism, we can benefit in **both** privacy and communication by the sparsification process in the ternary mechanism. Intuitively, if the sparsifying threshold is high (i.e., we only keep very few coordinates), we can hope to add less noise to achieve privacy, as the sparsification has already introduced some uncertainty in the data. The paper claims that this is something that prior works cannot offer. The reviewer, unfortunately, did not have a chance to verify the claim.", "questions": "* Your algorithm sends **in expection** O(d * A/B) bits. Is there a way to improve this to a worst-case guarantee? How about, say, randomly selecting (A/B * d) coordinates? Is it possible to work out the f-DP (or any other reasonable DP notion) property of this variant?", "limitations": "Some future directions are mentioned in the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Working with f-DP **and** in the local model seems like a new approach.\n* The proposed algorithm is natural and simple to implement, it is backed by the theory and performs favorably in the experiments.", "weaknesses": "* It's a bit hard to interpret/digest the closed-form f-DP guarantee of all these mechanisms. Have some plot/converting to Renyi-DP or (eps,delta)-DP might help.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer VYNX,\n\nWe appreciate your time and effort in reviewing and providing a positive evaluation of our work. Please find the point-by-point response to the comments below.\n\n**Comment**: It's a bit hard to interpret/digest the closed-form f-DP guarantee of all these mechanisms. Have some plot/converting to Renyi-DP or $(\\epsilon,\\delta)$-DP might help.\n\n**Response:** Thanks for the valuable suggestion. We agree that the closed-form expressions characterizing the tradeoff between the two types of error rates are not easy to digest for readers not familiar with $f$-DP, and will add some figures converting it to RDP or $(\\epsilon,\\delta)$-DP for better illustration. We would like to mention that $f$-DP can be readily converted to $(\\epsilon,\\delta)$-DP through Lemma 1 in the manuscript by finding $(\\epsilon,\\delta)$'s such that $f(\\alpha) \\geq \\max\\\\{0,1-\\delta-e^{\\epsilon}\\alpha,e^{-\\epsilon}(1-\\delta-\\alpha)\\\\}$. For the privacy guarantees of the binomial noise in Fig. 1, we convert it to $(\\epsilon,\\delta)$-DP in Remark 1. For the privacy guarantees of the proposed ternary compressor in Fig. 3, we convert it to  $(\\epsilon,\\delta)$-DP in Remark 3. In our comparison with SQKR in Fig.4 of the manuscript, as we discussed in our global response, given the same MSE and communication cost as that of SQKR with $\\epsilon_{SQKR} = \\\\{1,2,5\\\\}$, if we translate the privacy guarantees of the ternary compressor from $f$-DP to $\\epsilon$-DP via Lemma 1, the proposed ternary compressor yields $\\epsilon_{ternary} = \\\\{0.05,0.2,3.9\\\\}$. We will add the corresponding discussion in the revised manuscript.\n\n**Question:** Your algorithm sends in expection O(d * A/B) bits. Is there a way to improve this to a worst-case guarantee? How about, say, randomly selecting (A/B * d) coordinates? Is it possible to work out the f-DP (or any other reasonable DP notion) property of this variant?\n\n**Response:** Thanks for the valuable comment. We agree that exploring the worst-case guarantee is crucial. We would like to mention that in the proof of the privacy guarantees, we first consider the scalar case and then extend the results to the multi-dimensional case by invoking the composition theorem to account for the composition. In this case, each coordinate is processed independently. Randomly selecting a fixed number of coordinates may ruin the independence across coordinates and makes the composition more complicated. \n\nThat being said, it is also possible that we directly analyze the privacy guarantees in the vector case by invoking Lemma 2 (which characterizes the tradeoff between type I and type II error rates for generic discrete-valued mechanisms) in Appendix A of the manuscript. However, in this case, the range of the randomized mechanism will grow exponentially as the number of selected coordinates increases, and may finally become computationally infeasible. We deem it an interesting direction for extension and will work on it in our future work.\n\nAnother straightforward way to avoid the extreme case where too many coordinates remain non-zero and thus little saving in communication is achieved (if this is the concern in the Reviewer's mind) is by incorporating another mechanism that randomly samples a subset of them (with a fixed number of coordinates) before transmission. The privacy guarantee remains the same thanks to the post-processing property of DP. In this case, we lose the privacy amplification introduced by the second sparsification scheme (since we utilize the post-processing property instead of accounting for the privacy amplification). However, for the proposed ternary compressor, the number of coordinates that remain non-zero follows the binomial distribution with a mean of $d\\times A/B$ and a variance of $d \\times (A/B) \\times (1-A/B)$. For the applications like federated learning, $d$ is the size of gradients, which would be in the order of millions for modern neural networks. The central limit theorem tells us that the probabilities of these extreme cases in which too many coordinates remain non-zero are very low. "}, {"review_id": "1pmfzFqnof", "reviewer": "Reviewer_mVNo", "summary": "This paper studies distributed mean estimation under privacy and communication constraints. This paper focuses on characterizing the recently defined notion of $f$-DP for communication-efficient mechanisms, where $f$-DP can be converted to the standard $(\\epsilon,\\delta)$-DP. The paper analyzed the $f$-DP of different known mechanisms in the literature. Furthermore, a new algorithm named ternary compression is proposed.", "questions": "* It is mentioned in the abstract and also in the introduction that *it remains an open problem whether such discrete-valued mechanisms provide any privacy protection.* \nI don't know which open problem the authors referring to. If it is the distributed mean estimation under jointly local differential privacy and communication constraints, then this problem is already solved in the literature.\n\n* In line 51, *SQKR doesn't account for the privacy introduced during sparsification.* I don't understand this part. AFAIK, SQKR is order optimal, and hence, it doesn't lose privacy analysis. \n\n* In lines 259-261, what do these numbers of $\\epsilon$ refer to, and from where it comes?\n\n* In lines 331-333, *we essentially remove the dependency of accuracy on the communication overhead.* Could you please explain more? In general, it is supposed that there is a trade-off between communication and accuracy, so the accuracy depends on the communication budget.", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The distributed mean estimation is an important topic and has lots of applications in federated learning under privacy and communication constraints. The presentation is well written.", "weaknesses": "Although the topic is interesting, my main concerns are about the contributions of this paper. \n\n * The first part of the paper is to analyze the $f$-DP of well-known discrete mechanisms. While analyzing the $f$-DP is useful, it is not hard to compute it. I don't know what are the major challenges in this analysis and if this analysis provides any new insights into analyzing the $f$-DP. Hence, in my opinion, this part isn't novel enough as a main contribution of this paper.\n* The expressions of the $f$-DP are not in a closed form; the expressions are functions of a set of probabilities that might be computationally expensive to compute for large system parameters.\n* The proposed mechanism of ternary compression is not novel. There are lots of similar schemes that don't send some coordinates with some probability from sampling the coordinates for example [13] and [23]. Actually, the Ternary mechanism can be seen as a combination of CLDP for a set of coordinates that are chosen i.i.d. with probability $B/A$. \n* In general, this ternary mechanism has higher privacy because it has lower accuracy, since with some non-zero probability (when $B>A$), the client will not send anything. \n\n*  The optimal trade-offs between privacy, communication, and accuracy have already been characterized for LDP in different works in the literature, and hence, I don't understand what is the major difference in this paper in comparison with the existing work.\n\n* Typos: please define the abbreviation of GDP (Gaussian differential privacy) for using it. In Algorithm 1, $x_i\\in\\lbrace 0,1,\\ldots,l \\rbrace$ instead of square brackets. Figure 4 is small and the lines are close enough so that it is hard to distinguish the different mechanisms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer mVNo,\n\nWe appreciate your time in reviewing our paper and providing helpful comments. We believe that your concerns are due to misunderstandings. Different from existing methods (e.g., SQKR) which ignore the privacy amplification in compression, the proposed ternary compressor achieves much better privacy guarantees. For example, as we discussed in our global response, the ternary compressor improves the privacy guarantees for SQKR from $\\epsilon_{SQKR} = \\\\{1,2,5\\\\}$ to $\\epsilon_{ternary} = \\\\{0.05,0.2,3.9\\\\}$ **given the same communication cost and MSE**. Please find our detailed response below.\n\n**Comment 1**: The main challenge of the analyses lies in the fact that the tradeoff functions are piece-wise functions with both the domain and the range of each piece determined by both the mechanism and the datasets, and finding the infimums analytically is highly non-trivial. Generally, since the piece-wise tradeoff functions are mechanism-dependent, the analyses are also mechanism specific. We adopt completely different strategies in finding the infimums for the binomial noise and the Poisson binomial mechanism.\n\nOur analyses advance the literature by deriving tighter privacy guarantees for the binomial noise and deriving local DP guarantees for the binomial mechanism in $f$-DP, which is of vital importance in their practical use. More importantly, based on our analyses, we propose the ternary compressor that utilizes compression for privacy amplification (to the best of our knowledge, this is the first work that achieves it), which outperforms the existing methods and delivers almost identical privacy-accuracy performance to the classic Gaussian mechanism while improving communication efficiency. This is of significant importance in applications like federated learning when communication and privacy are the major bottlenecks.  \n\n**Comment 2:** The probabilities are not expensive to compute. All the random variables in Theorem 1 and Theorem 2 follow a binomial distribution with known parameters (i.e., $M$ and $p$). Both their pdfs and cdfs are known analytically and easy to compute numerically. Therefore, we consider the corresponding $f$-DP guarantees are in closed-form expressions. In fact, the tradeoff functions are piecewise linear functions with fixed slopes for each piece. We only need to compute the boundary points for each piece, i.e., at most $O(M)$ cdfs values of the binomial distribution are needed to obtain Eq. (5) and Eq. (6) (similarly for Theorem 2), which is computationally affordable. We believe the concern is due to different interpretations of \"closed-form\" and will revise carefully. \n\n**Comment 3, 4, 5, Question 2:** There are indeed several schemes that simultaneously consider compression and DP. The major difference is that they fail to account for the privacy amplification by sparsification, by exploiting which the proposed ternary mechanism provides significantly better privacy guarantees. For CLDP in [23], as we discussed in Example 2, it is a special case of sto-sign, and the proposed ternary compressor obtains an amplification in privacy (see Fig. 3 in the manuscript). For SQKR in [13], given a $d$-dimensional data $x$, SQKR with $\\epsilon$-LDP first samples $k$ out of $d$ coordinates (denote the output by $y$) and applies the $\\epsilon$-LDP randomized response mechanism to $y$ (denote the output by $z$). It accounts for the privacy in the process of generating $z$ from $y$, but ignores the privacy in the process of generating $y$ from $x$ (i.e., sparsification). Therefore, these existing methods are only order-optimal (rather than optimal) in characterizing the tradeoff between privacy, communication, and accuracy. \n\nCompared to existing methods, the proposed ternary compressor does not obtain higher privacy by sacrificing accuracy. Instead, we exploit privacy amplification brought by compression (which reduces communication costs) to improve the privacy-accuracy tradeoff. As we discussed in our global response, our experimental results imply that the proposed ternary compressor significantly outperforms SQKR in [13]. We also compare the ternary compressor with the Gaussian mechanism given the same privacy and MSE in the right figure of Fig. 4. Despite the improvement in communication efficiency (at least 32x), the tradeoff between privacy and accuracy for the proposed ternary mechanism matches that of the Gaussian mechanism. \n\n**Question 1:** By open problem, we refer to quantifying the DP guarantees of the compression mechanisms. \n\n**Question 3:** The numbers of $\\epsilon$'s refer to the privacy levels in $(\\epsilon,\\delta)$-DP. In Theorem 3, we derived the $f$-DP guarantee, and the corresponding $\\epsilon$ and $\\delta$ are obtained by invoking Lemma 1 (line 153).\n\n**Question 4:** Indeed, accuracy depends on the communication budget, and our argument holds under fixed privacy requirements. Since the ternary compressor accounts for privacy amplification in sparsification, the privacy guarantee $\\mu$ is closely related to the communication overhead, i.e., the loss in accuracy introduced by communicating less is translated to enhancement in privacy (please see our global response for a detailed discussion). There are two sources of privacy in the ternary compressor: 1) privacy introduced by randomly mapping each coordinate to +1 or -1, and 2) privacy amplification by sparsification. More aggressive sparsification (i.e., a larger $B$) leads to a larger MSE while bringing a larger privacy amplification. Meanwhile, for a target privacy $\\mu$, a larger privacy amplification allows us to introduce less randomness (i.e., a smaller $A$) in the random mapping for each coordinate, which results in a smaller MSE. Overall, given the same privacy $\\mu$, the MSE remains the same regardless of communication overhead if $\\mu < \\sqrt{4dr/(1-r)}$. For the existing methods like SQKR, reducing communication leads to degradation in MSE without enhancing privacy.\n\n"}]

Author rebuttal:
Dear Chairs and Reviewers,

The authors would like to thank you for your time in handling our paper and providing insightful comments and suggestions. We are happy to know that the reviewers find our study is of practical use (reviewer 191s), our proposed method is natural and simple to implement while backed by both theory and experiments (reviewer VYNX), the privacy in compression that we study should be utilized if possible (reviewer Mzdj), and the paper is generally well-written (reviewers 191s, reviewer mVNo). 

In this work, we investigate the amplification in privacy brought by compression. To this end, we derive the expressions of the tradeoff function between the two types of error rates in the hypothesis testing problem for generic discrete-valued mechanisms, based on which we advance the literature by deriving tighter privacy guarantees for binomial noise and analyzing the local differential privacy guarantees for the Poisson binomial mechanism as well as a variety of discrete-valued differentially private and compression mechanisms. Utilizing the proposed analytical results, we further propose a ternary compressor that exploits privacy amplification in sparsification and show that the loss in accuracy introduced by compression can be translated to enhancement in privacy. Our analyses focus on the recently emerging and promising concept of $f$-DP that enjoys a better composition property than $(\epsilon,\delta)$-DP and Renyi DP, which we believe is valuable to the community on its own. 

We find that most of the concerns are due to misunderstandings and believe that we have addressed them adequately. In this global response, we would like to address the following two common concerns. 

**The difference from existing methods**: In this work, different from existing methods that combine compression and differentially private mechanisms, we endeavor to exploit the privacy amplification brought by compression. Therefore, what we observe and present is not ``communicating less will not hurt the utility much under privacy constraints``, but instead ``the loss in utility caused by communicating less is translated to enhancement in privacy``. More specifically, the state-of-the-art method SQKR in [R1] yields a variance of $\frac{d}{k}(\frac{e^{\epsilon}+2^{k}-1}{e^{\epsilon}-1})^{2}C^{2}-||x||_{2}^{2}$ 

for the transmitted signal $x$. While for finite $\epsilon$ and $k$, the MSE may be dominated by error introduced by the privacy requirement $\epsilon$, the error introduced by compression is non-zero and further degrades the MSE, i.e., *the variance is still a function of $k$, and decreasing $k$ leads to an increased MSE without affecting the privacy guarantee $\epsilon$*. On the contrary, for the proposed ternary compressor, the privacy guarantee is given by $\mu = \frac{2\sqrt{d}c}{\sqrt{AB-c^{2}}}$ (line 301 in the revised manuscript), the communication cost is determined by $\frac{A}{B}d$, and the MSE is given by $ABd-||x||_{2}^{2}$. 

When the communication cost is reduced with more aggressive sparsification (i.e., $B$ increases for a fixed $A$), there is an increase in MSE, but also a corresponding amplification in privacy, i.e., $\mu$ decreases. In this sense, given a fixed target privacy guarantee $\mu_{target}$, we may decrease $A$ when $B$ increases such that $AB$ (and therefore both $\mu$ and the MSE) remains the same. In this sense, *the MSE is solely determined by the privacy $\mu$ since the error introduced by compression is translated into enhancement in privacy.* With some simple algebra, the MSE of the ternary compressor is given by $(4d/\mu^{2}+1)C^{2}-||x||_{2}^{2}$ when $\mu < \sqrt{4dr/(1-r)}$, which remains the same regardless of the communication cost $r$. In this case, the tradeoff is essentially only between privacy and accuracy, and neither increasing nor decreasing the communication cost affects the tradeoff.

**The gain in privacy compared to SQKR**: The gain in privacy by utilizing the privacy amplification brought by compression is significant. The left figure in Fig. 4 compares the privacy guarantees of the proposed ternary compressor with SQKR given the same communication cost (only 10 out of 250 coordinates are transmitted) and MSE. Note that we transform the $\epsilon$-LDP guarantee of SQKR and the $f$-DP guarantee of the ternary compressor to the tradeoff between type I error rate and type II error rate in hypothesis testing for the ease of a direct comparison. Given the same type I error rate, a larger type II error rate means that the adversary is more likely to make a mistake in the hypothesis testing (i.e., better privacy). It can be observed from the left figure in Fig. 4 that the ternary compressor significantly outperforms SQKR. For example, for SQKR with $\epsilon = 2$, given type I error rate $\alpha = 0.5$, the type II error rate of the attacker is around $f(\alpha) = 0.068$. Meanwhile, given the same MSE and communication cost, the proposed ternary compressor attains a type II error rate of $f(\alpha) = 0.484$ when $\alpha = 0.5$. Given the same MSE and communication cost as that of SQKR with $\epsilon_{SQKR} = \\{1,2,5\\}$, if we translate the privacy guarantees of the ternary compressor from $f$-DP to $\epsilon$-DP via Lemma 1 (we numerically test different $\epsilon$'s such that $f(\alpha) \geq \max\\{0,1-\delta-e^{\epsilon}\alpha,e^{-\epsilon}(1-\delta-\alpha)\\}$ holds for $\delta = 0$), they are approximately $\epsilon_{ternary} = \\{0.05,0.2,3.9\\}$ for the proposed ternary compressor (please see the attached file for the figure). Note that in the high privacy regime, the error introduced by privacy requirements dominates for SQKR, and it becomes more important to exploit the privacy amplification by compression. As a result, a larger gap is observed. 

[R1] Chen, Wei-Ning, Peter Kairouz, and Ayfer Ozgur. "Breaking the communication-privacy-accuracy trilemma." Advances in Neural Information Processing Systems 33 (2020): 3312-3324.

Meta-review: The reviewers commend the paper's approach to addressing communication, privacy, and accuracy trade-offs using f-differential privacy. Notably, the focus on improved communication efficiency is appreciated. However, concerns arise regarding the clarity of comparative analysis on the tangible gains. The meta-reviewer recommends acceptance as a poster while urging the author(s) to enhance their comparative demonstrations for better impact.
Decision: Accept (poster)