Universal Exact Compression of Differentially Private Mechanisms
Authors: Yanxiao Liu
Wei-Ning Chen
Ayfer Ozgur
Cheuk Ting Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Channel Simulation
Federated Learning
Communication
Poisson Process
Primary area: privacy
TL;DR: We provide the first mechanism that compresses and simulates any randomizer while preserving local differential privacy, achieving near-optimal compression sizes, and ensuring no distortion is introduced to the reproduced distribution.

Abstract: To reduce the communication cost of differential privacy mechanisms, we introduce a novel construction, called Poisson private representation (PPR), designed to compress and simulate any local randomizer while ensuring local differential privacy. Unlike previous simulation-based local differential privacy mechanisms, PPR exactly preserves the joint distribution of the data and the output of the original local randomizer. Hence, the PPR-compressed privacy mechanism retains all desirable statistical properties of the original privacy mechanism such as unbiasedness and Gaussianity. Moreover, PPR achieves a compression size within a logarithmic gap from the theoretical lower bound. Using the PPR, we give a new order-wise trade-off between communication, accuracy, central and local differential privacy for distributed mean estimation. Experiment results on distributed mean estimation show that PPR consistently gives a better trade-off between communication, accuracy and central differential privacy compared to the coordinate subsampled Gaussian mechanism, while also providing local differential privacy.

Universal Exact Compression of Differentially Private Mechanisms
Yanxiao Liu
Wei-Ning Chen Stanford University wmchen@stanfore www..aooooooooooooooooooooooo..d edu
The Chinese University of Hong Kong yanxiaoliu@link cuhk, edu.hk
Ayfer Özgür
Cheuk Ting
Stanford University
The Chinese University of Hong Kong ctli@ie. cuhk. edu.
aozgur@stanfore edu
Abstract
To reduce the communication cost of differential privacy mechanisms, we intro- duce novel construction, called Poisson private representation (PPR), designed to compress and simulate any local randomizer while ensuring local differential privacy. Unlike previous simulation-basee local differential privacy mechanisms, PPR exactly preserves the joint distribution of the data and the output the original local randomizer. Hence, the PPR-compressed privacy mechanism retains all desir- able statistical properties of the original privacy mechanism such as unbiasedness and Gaussianity. Moreover, PPR achieves compression size within logarithmic gap from the theoretical lower bound. Using the PPR, we give a new order-wise trade-off between communication, accuracy, central and local differential privacy for distributed mean estimation. Experiment results on distributed mean estima- tion show that PPR consistently gives better trade-off between communication, accuracy and central differential privacy compared to the coordinate subsampled Gaussian mechanism, while also providing local differential privacy.
1 Introduction
In modern data science, there is a growing dependence on large amounts of high-quality data, often generated by edge devices (e.g., photos and videos captured by smartphones, messages hosted by social networks). However, this data inherently contains personal information, making susceptible privacy breaches during acquisition, collection, utilization. For instance, despite the significant recent advancement in foundational models [9], studies have shown that these models can accidentally memorize their training data. This poses risk where malicious users, extract substantial portions of sensitive information [14 In recent years, differential privacy (DP) 28 has emerged powerful framework for safeguarding users' privacy by ensuring that local data is properly randomized before leaving users' devices. Apart from privacy concerns, communicating local data from edge devices to the central server often becomes bottleneck in the system pipeline, especially with high- dinenssinn data common in many machine learning scenarios. This leads to the following fundamental question: how can we efficiently communicate privatized data?
with just API access, can
Recent works have shown that a wide range of differential privacy mechanisms can be "simulated" and "compressedd" using shared randomness, resulting in "compressed mechanism" which has a smaller communication cost compared to the original mechanism, while retaining the (perhaps slightly weakened) privacy guarantee. This can be done via rejection sampling [31], importance
sampling [71] (78), or dithered quantization [56] 72 46 9 80 with each approach having its own
advantages and disadvantages. For example, importance-samping-
methods [7] 78 and the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

rejection-sann -aaplinng-mananna based method [3]] can simulate a wide range of privacy mechanisms; however, the output distribution of the induced mechanism does not perfectly match the original mechanism. This is limiting in scenarios where the original mechanism is designed to satisfy some desired statistical properties, e.g. it is often desirable for the local randomizer to he unbiased or be "summable" noise such as Gaussian or other infinitely divisible distributions. Since the induced mechanism is different from the original one, these statistical properties are not preserved. On the other hand, dithered- quantization-base
46 49 80) can ensure correct simulated distribution, but they can only simulate additive noise mechanisms. More importantly, dithered quantization relies on shared randomness between the user and the server, and the server needs to know the dither for decoding. This annuls the local privacy guarantee on the user data, unless we are willing to assume a trusted aggregator 46),, use additional secure aggregation step [49], or restrict attention to specific privacy mechanisms (e.g., one-dimensional Laplace (72).
approaches [48] (56] 72
Our contribution
In this paper, we introduce novel "DP mechanism compressor" called Poisson private representation (PPR), designed to compress and exactly simulate any local randomizer while ensuring local DP, through the use of shared randomness[] We elaborate on three main advantages of PPR, namely universality, exactness and communication efficiency.
approaches which can only simulate additive noise mechanisms, PPR can simulate any local or central DP mechanism with discrete or continuous input and output. Moreover, PPR is universal in the sense that the user and the server only need to agree on the output space and a proposal distribution, and the user can simulate any DP mechanism with the same output space. The user can choose a suitable DP mechanism and privacy budget according to their communication bandwidth and privacy requirement, without divulging their choice to the server.
Universality. Unlike fathherdd-qannizaaton------
Exactness. Unlike previous DP mechanism compressors such as Feldman and Talwar [31. Shah et al. 771, Triastcyn et al. 778.. PPR enables exact simulation, ensuring that the reproduced distribution perfectly matches the original one. Exact distribution recovery offers several advantages. Firstly, the compressed sample maintains the same statistical properties as the uncompressed one. the local randomizer is unbiased (a crucial requirement for many machine learning tasks like DP-SGD), the outcome of PPR remains unbiased. In contrast, reconstruction distributions in prior simulation- based compression methods 31 71]
are often biased unless specific debiasing steps performed (only possible for certain DP mechanisms (71). ). Secondly, when the goal is to compute the mean (e.g.. for private mean frequency estimation problems) and the local noise is "summable" (e.g., Gaussian noise or other infinitely divisible distributions (55] 42)), exact distribution recovery of the local noise enables precise privacy accounting for the final central DP guarantee, without relying on generic privacy amplification techniques like shufffing (30 32) PPR can compress a central DP mechanism (e.g.. the Gaussian mechanism 27 and simultaneously achieve weaker local DP (i.e., with larger élocal) and stronger central DP (i.e., with a smaller Scentral). while maintaining exactly the same privacy-utility trade-offs as the uncompressed Gaussian mechanism.
Communication efficiency. PPR compresses the output of any DP mechanism to a size close to the theoretical lower bound. For a mechanism on the data X with output Z, the compression size of PPR is T(X; Z) + log( (T:: Z) + 1) + O(1), with only a logarithmic gap from the mutual information lower bound [(X; 2 The "O(1)" constant can be given explicitly in terms of a tunable parameter a > which controls the trade-off between compression size, computational time and privacy.
The main technical tool we utilize for PPR is the Poisson functional representation 66 60), which provides precise control over the reconstructed joint distribution in channel simulation problems 10 21). Channel simulation aims to achieve the minimum communication for simulating a channel (i.c.. a specific conditional distribution). Typically, these methods rely on shared randomness between the user and server, and privacy is only preserved when the shared randomness is hidden from the adversary. This setup conflicts with local DP, where the server (which requires access shared randomness for decoding) is considered adversarial. To ensure local DP, we introduce a randomized encoder based on the Poisson functional representation, which stochastically maps
45 61
35 41
I 'Our code can be found inttpss://gtthhu htt.:t/pe/gggttt.....///ttuttete 2This is similar to channel simulation [45] and the strong functional representation lemma
61 though
45 61 do not concern privacy.

---

private local message to its representation. Hence. PPR achieves order- wise trade-off' between privacy, communication, and accuracy. while preserving the original distribution of local randomizers.
Entropy HX)), mutual information T(X;Y) Y), KL divergence D ((Pl)) and logarithm the same base, e.g., they can be all in bits (base 2), or all in nats (base e). For P, Q. dP())/QQ denotes the Radon-Nikodym derivative.
Notations.
2 Related Work
Generic compression of local DP mechanisms. In this work, we consider both central DP 22 and local DP [79 (53 Recent research has explored methods for compressing local DP randomizers when shared randomness is involved. For instance, when & S 1, Bassily and Smith [5] demonstrated that single bit can simulate any local DP randomizer with a small degradation of utility, as long as the output can be computed using only a subset of the users' data. Bun et al. [12 proposed another generic compression technique based on rejection sampling, which compresses c-DP mechanism into a 10=-DP mechanism. Feldman and Talwar [3 proposed a distributed simulation approach using rejection sampling with shared randomness, while Shah et al. [7]]. Triastcyn et al. [78] utilized importance sampling (or more specifically, minimum random coding (0 74, 47)). However, all these methods only approximate the original local DP mechanism, unlike scheme, which achieves an exact distribution recovery.
Distributed mean estimation under DP. Mean estimation is the canonical problems in distributed
learning and analytics. They have been widely studied under privacy [2 g 23 communication
has demonstrated that the optimal unbiased mean estimation scheme under local differential privacy is privUnit (8). mechanisms introduced by Feldman and Talwar BTI Shah et al. (71). Isik et al. [51] aimed to construct communication-effiiiee versions of privUnit, either through distributed simulation or discretization. However, these approaches only approximate the privUnit distribution, while our proposed method ensures exact distribution recovery.
40 I 75), or both constraints [88 31
19]. Among them, Asi
Subsequently, communication--ffiiee
Distributed channel simulation. Our approach relies on the notion of channel simulation 6 45 10
61 35
7 21 One-shot channel simulation is a lossy compression task, which aims to find the minimum amount of communications over a noiseless channel that is in need to "simulate" some channel P2|x (a specific conditional distribution). By Harsha et al. [45. Li and EI Gamal [61, the average communication cost is [(;; Z) + Olog [(X; 2))). In [45) algorithms based on rejection sampling are proposed, and is further generalized in 33 by introducing the greedy rejection coding. Dithered quantization [81 has also been used to simulate an additive noise channel in (2) for neural compression. As also shown (2), the time complexity of channel simulation protocols (e.g., in 61] is usually high, and [76] 35
41 try to improve the runtime under certain assumptions. Moreover, channel simulation tools have also been used in neural network compression [47), image compression via variational autoencoders (37,, diffusion models with perfect realism [77] and differentially private federated learning (7].
Poisson functional representation. The Poisson functional representation is channel simulation scheme studied in [61]. Also refer to (65] for related constructions for Monte Carlo simulations. Based on the Poisson functional representation, the Poisson matching lemma has been used in proving one-shot achievability results for various network information theory problems (60 64 Also see applications hiding (63, minimax learning [62) and secret key generation [50]. A variation called the importance matching lemma (69] has also used in distributed lossy compression. By (38), the Poisson functional
unequal message protection [54]. hypothesis testing [44] information
representation can be viewed as a certain variant of the A sampling [66] 65). and hence an optimized
version with better runtime for one-dimensional unimodal distribution has been proposed in 38
3 Preliminaries
We begin by reviewing the formal definitions of differential privacy (DP). We consider two models of DP data analysis. the central model, introduced in Dwork et al. (28. the data of the individuals
is stored in a database X e X' by the server. The server is then trusted to perform data analysis
3

---

whose output Z = A(X) E Z (where A is randomized algorithm), which is sent to an untrusted data analyst, does not reveal too much information about any particular individual's data. While this model requires a higher level of trust than the local model, it is possible to design significantly more accurate algorithms. We say that two databases X, X' E X' are neighhoring if they differ a single data point. More generally, we can consider symmetric neighbor relation N C X22 and regard X, X' as neighbors if (X, X') N.
On the other hand, in the local model, each individual (or client) randomizes their data before sending it the server, meaning that individuals are not required trust the server. local DP mechanism 53 is local randomizer A that maps the local data X E X' to the output Z = A(X) E Z. Note that here X the data at one user. unlike central- where X is the database with the data of all users. We now review the notion of (s, 5)-central and local DP.
Definition 3.1 (Differential privacy [28] 53). Given a mechanism A which induces the conditional distribution Pz|x of Z A(X). we say that it satisfies (s, ()-P) for any neighboring (z, x²) W and S C 2, it holds that
= S E x)) +
In particular, W = X²2 we say that the mechanism satisfies (e, 8)-ooaal DP 53
When mechanism satisfies (s, ceettraall/lcal DP, we will refer to it simply as e-Central/loca DP. c-DP can be generalized to metric privacy by considering a metric dx (z, x²) over X [6 3)
Definition 3.2 (s dx-privacy [6 3). Given a mechanism A with conditional distribution Pz|x, and a metric dxx over X, we say that A satisfies E dx-privacy for any x, x' E S C 2, we have
Pr(Z E S X r) eedx((.,a) Pr(Z E 8 x
This recovers the original e-central DP by considering dx to be the Hamming distance among databases, and recovers the original e-local DP by considering dxx to be the discrete metric [[6].
The reason we use X to refer to both the database in central DP and the user's data in local DP is that our proposed method can compress both central and local DP mechanisms in exactly the same manner. In the following sections, the mechanism A to be compressed (often written as conditional distribution Px x) can be either central or local DP mechanism, and the neighbor relation A can be any symmetric relation. The "encoder" refers to the server in central DP, or the user in local DP. The "decoder" refers to the data analyst central DP, or the server local DP.
Poisson Private Representation
Definition 4.1 (Poisson functional representation 60]60) Let (T)); be a Poisson process with rate 1
(i.e., Ti, T2 -Ti,Ts T3 T sid Exp(1)), independent of Z, sid Q for i = 1, 2, .... Then (Z,, T:); a Poisson process with intensity measure Q x A1o, (57) where > is the Lebesgue measure over [0, oc). Fix any distribution over Z that is absolutely continuous with respect to Q. Let
dP ( (z.(z))
f :=
(I)
Then (Z,.T.) is Poisson process with intensity measure P x oc) which is from the mapping theorem (57] The Poisson functional representation (PFR) 61 60 selects the point Z = Zx with
the smallest associated TK. i.e., let K := argmin, and Z : ZK
The PFR selects sample following the target distribution P using another distribution Q. It draws random sequence (Z,), from Q and a sequence of times (T:); according to a Poisson process. If we select the sample Z; with the smallest T,, then the selected sample follows Q. To obtain sample from P instead, we multiply the time by the factor (1p (2.)) -1 (I) give T,, so the Ze with the smallest 7; will follow P.
'quivalently, local DP can viewed as special case central DP with dataset size n "iice the Tt's 's are continuous, with probability 1, there do not exist two equal values among Tt's.

---

The Poisson functional representation guarantees that Z ~ P [6]] To simulate a DP mechanism with a conditional distribution Pz|x using the Poisson functional representation, we can use (Z)); as the shared randomness between the encoder and the decoder. Upon observing X, the encoder generates the Poisson process (T,),, computes T. and K using P = Pz and transmits K to the decoder. The decoder simply outputs ZK. which follows the conditional distribution Pz|x- The issue is that K is a function of X and the shared randomness (Z,. Ti);, and change of X may affect K in a deterministic manner, and hence this method cannot be directly used to protect the privacy of X.
Poisson private representation. To ensure privacy, we introduce randomness in the encoder by generalization of the Poisson functional representation, which we call Poisson private representation (PPR) with parameter E (1, oo], proposal distribution Q and the simulated mechanism Pz|x. Both X and Z can be discrete or continuous, though as a regularity condition, we require P to be absolutely continuous with respect to Q almost surely. The PPR-compressed mechanism is given as:
1. We use (Zi) Zi sid Q as the shared randomness between the encoder and the decoder.
Practically, the encoder and the decoder can share a random seed and generate Z, idd Q from it using a pseudorandom number generator [
2. The encoder knows (Z,),, X, P2|x and performs the following steps:
(a) Generates the Poisson process (T,), with rate 1.
(b) Computes T; == T; (dP (2:))= where P := Pz|x(1X) Take T; 0o if dP (Z,) = 0.
aq
(c) Generates E Z4 using local randomness with
T-a
Pr(K = k)) Eie 7:a0
(d) Compress K (e.g., using Elias delta coding (9 and sends K.
3. The decoder, which knows (Z:),, K, outputs Z = Zx.
Note that when a Do, we have K argmin,TT, and PPR reduces to the original Poisson functional representation 61 60]. PPR can simulate the privacy mechanism Pz|x precisely, as shown in the following proposition. The proof is in Appendix[A]
Proposition 4.2. The output of PPR follows the conditional distribution Pzzx exactly.
Due to the exactness of PPR, it guarantees unbiasedness for tasks such as DME. If the goal is only to design a stand-alone privacy mechanism, we can focus on the privacy and utility of the mechanism without studying the output distribution. However, if the output of the mechanism is used for downstream tasks (e.g., for DME, after receiving information from clients, the server sends information about the aggregated mean to data analysts, where central DP is crucial), having an exact characterization of the conditional distribution of the output given the input allows us to obtain precise (central) privacy and utility guarantees.
Notably, PPR universal in the sense that only the encoder needs to know the simulated mechanism Pz|x- The decoder can decode the index K as long as it has access to the shared randomness (Zz).. This allows the encoder to choose an arbitrary mechanism P2 x with the same Z, and adapt the choice of Px x to the communication and privacy constraints without explicitly informing the decoder which mechanism is chosen.
Practically, the algorithm cannot compute the whole infinite sequence (T.);- We can truncate the method and only compute T,..., T'y for a large N and select K E (I....,,N,, which incurs small distortion in the distribution of Z While this method is practically acceptable, it might defeat
'The original Poisson functional representation 61 60 uses the whole (Z,, T;), as the shared randomness. is clear that (T.); is not needed by the decoder, and hence we can use only (7,): as the shared randomness.
"We note that our analyses assume that the adversary knows both the index K and the shared randomness (Zt).. and prove that the mechanism is still private despite the shared randomness between the encoder and the decoder, since the privacy is provided by locally randomizing K in Step 2c
"To compare to the minimal random coding (MRC) [47 20 74 scheme in 71.. which also utilizes a finite
number N of samples (Zi)==1.....,, while truncating the number of samples to N in both PPR and MRC
5

---

the purpose of having an exact algorithm that ensures the correct conditional distribution Px x. In Appendix B we will present an exact algorithm for PPR that terminates in a finite amount of time, using& reparametrization that allows the encoder to know when the optimal point Zq has already been encountered (see Algorithm | in Appendix B
By the lower bound for channel simulation [6. 61.. we must have ((K) 2 [XX; 2). i.c. the compression size at least the mutual information between the data X and the output Z. The following result shows that the compression provided by PPR is "almost optimal", i.e. close to the theoretical lower bound I [x; Z). The proof is given in Appendix
Theorem 4.3 (Compression size of PPR). For PPR with parameter 1, when the encoder is given the input z, the message K given by PPR satisfies
1aaaa-1)/0 Eloo K] S D(PIIQ) + (log(3.56)) min((a-1)/2.11 1);
where P = (2)x(++)), As result, when the input X ~ Px random, taking Q Pz, we have
Ellog K] S (X; 2) + (l0g(3.56)) min - 13.
Note the running time complexity (which depends the number of samples Z; the algorithm must
examine before outputting the index K) can be quite high. Since [E[log K] x T(X; 2), K (and hence
the running time) is at least exponential in T(X; Z). See more discussions in Section 8
If a prefix-free encoding of K is required, then the number of bits needed is slightly larger than loga K. For example, if Elias delta code [29] is used, the expected compression size is S [B[log, K] + 2 (E[log, K| 1) + bits. If the Shannon code 73 (an almost-optimal prefix-free code) for the
Zipf distribution p(k) x k A with À 1 + 1/ // K] is used, the expected compression size is < E[log, K] + logg (B(log2 K]+1)+2 bits (see (61). Both codes yield an [(X; Z)+0 [(X; Z size, within a logarithmic gap from the lower bound T(X; Z). This similar to some other channel simulation schemes such as 45 10 61). though these schemes do not provide privacy guarantees.
Note that if PzIx is s-DP, then by definition, for any = E Z and x Do E X, it holds that
D P = EENPP2x== log ( [dPz|x=> (2) [
- e loge.
dP2 =ro
Setting the proposal distribution Q = P2 for an arbitrary Zo E X' gives the following bound. Corollary 4.4 (Compression size under e-IDP). Let P2|x satisfy e-differential privacy. Let To E X and Q- P Then for PPR with parameter
1, the expected compression size is at most ++ logz (E + 1) bits, where { == e log. + (30g2(3.56)) //minn {(a - 1)/2, 1}.
Next, we analyze the privacy guarantee of PPR. The PPR method induces a conditional distribution P(z))xKIx of the knowledge of the decoder ((Z:)., K), given the data X. To analyze the privacy guarantee, we study whether the randomized mapping P(z,),KK) x from X to ((Z,);, K) satisfies e-DP or (e, D)- This is similar the privacy condition in 771,, and is referred as decoder privacy in (72), which is stronger than database privacy which concerns the privacy of the randomized mapping from X to the final output Z 772 (which is simply the privacy of the original mechanism Pzzx to be compressed since PPR simulates Pz|x precisely). Since the decoder knows ((Z)), K). more than just the final output Z, we expect that the PPR-compeessed mechanism P(z,), K|x have a worse privacy guarantee than the original mechanism P2 x, which is the price of having smaller communication cost. The following result shows that, if the original mechanism P2|x is e-DP, then the PPR-compressed mechanism is guaranteed to be 2oc-DP.
results in distortion in the distribution of Z that tends to 0 as N + 0o, the difference is that log K (which is approximately the compression size) in MRC grows like log N. whereas log K does not grow as N + co in PPR. The size N in truncated PPR merely controls the tradeoff between accuracy of the distribution of Z and the running time the algorithm.
'Note that the encoder does not actually send ((Z:),, K); it only sends K. The common randomness (Z,); independent of the data X, and can be pre-generated using a common random seed in practice. While this seed must communicated between the client and server as a small overhead, the client and the server only ever need to communicate one seed to initialize a pseudorandom number generator, that can be used in all subsequent privacy mechanisms and communication tasks (to transmit high dimensional data or use DP mechanisms for many times). The conditional distribution P(z,). KI x only relevant for privacy analysis.

---

Theorem 4.5 (s-DP of PPR). If the mechanism P x is E-differentially private, then PPR Pizdaxix with parameter a > 1 is diffffrrrentllllyy private.
Similar results also apply to (e. and metric DP.
Theorem 4.6 ((e, 6)-DP of PPR). If the mechanism Pz is (e, (.)))differeeniallyy private, then PPR P(Z),,KIX with parameter a > 1 is (2ase, dif-fefferemtially private.
Theorem 4.7 (Metric privacy of PPR). If the mechanism Pzix satisfies -xx-privacy, then PPR
K(Z) with parameter a > 1 satisfies 20r dx-privacy.
Refer to Appendices C and D for the proofs. In Theorem 4.5 and Theorem 4.6 PPR imposes
multiplicative penalty 2a on the privacy parameter E. This penalty can be made arbitrarily close to 2 by taking a close 1, which increases the communication cost (see Theorem 4.3). Compared to minimal random coding which has a factor 2 penalty in the DP guarantee 47
71J, the 2a factor in
PPR is slightly larger, though PPR ensures exact simulation (unlike [47 71 which are approximate).
The method in [31] does not have a penalty on é, but the utility and compression size depends on computational hardness assumptions on the pseudorandom number generator, and there is no guarantee that the compression size is close to the optimum. In comparison, the compression and privacy guarantees of PPR are unconditional and does not rely on computational assumptions.
In order to make the penalty of PPR close to 1, we have to consider (e, 5) -differrnntall privacy, and allow small failure probability, i..., small increase in 8. The following result shows that PPR can compress any e-DP mechanism into a ( e, Rs O)-DP mechanism as long as a is close enough to (i.e., almost no inflation). More generally, PPR compress (e. 8)PDP mechanism into an ( E, x 25)-DP mechanism for a close to 1. The proof is in Appendix
Theorem 4.8 (Tighter (EP of PPR). If the mechanism P2 X is (e, deifereifre private, then PPR R(x with parameter a > is (aE + E, 2 + 8)) difffereentilll private, for every E (0, 1] and 8 (0, 1/3] that satisfy a S e -.28 1- 5n
Applications to Distributed Mean Estimation
We demonstrate the efficacy of PPR by applying it to distributed mean estimation (DME) 75 Note that private DME the core sub-routine various private and federated optimization algorithms, such as DP-SGD 1 or De-FedAvg [67]
Consider the following general distributed setting: each of clients holds local data point X; E X, and a central server aims to estimate function of all local data μ (X"), subject to privacy and local communication constraints. To this end, each client compresses X; into a message Z; Z,, via local encoder, and we require that each Z, can be encoded into bit string with an expected length of at most b bits. Upon receiving Z DP estimate a. Two DP criteria can be considered: the (s, o)-central DP of the randomized mapping from X to f., and the (e, 8) local DP of the randomized mapping from X, to Z, for each client
(Z,..... ., Zn). the central server decodes it and outputs a
In the distributed Le mean estimation problem, X (a(C)) == (v E Rd ||l|22 SC.. and the central server aims to estimate the sample mean ju( ((X")= = -m X, by minimizing the mean squared error (MSE) Eillu - Al It is recently proved that under e-local DP, privUnit 8 is the optimal mechanism. By simulating privUnit with PPR and applying Corollary 4.4 and Theorem 4.6 we immediately obtain the following corollary:
Corollary 5.1 (PPR simulating privUnit). Let be the density defined by E E-privUnit, Bhowmick et al. 18 Algorithm 1J. Let Q be the uniform density over the sphere gd-1 (1/m) where the radius 1 1/m is defined in Bhowmick el al. [ (15)). Let r* : e.. Then the outcome of PPR (see Algorithm
satisfies (1) 20s-local DP; and (2) (as E,, -DP for any a S -4.2822 log(1/5) + 1. In addition. the average compression size is most 8- (e+1)+2 bits where E := e+ (log, (3.56)) min((a- 1)/2,1} Moreover, PPR achieves the same MSE as E-privUnit,, which is O (d/ min (c,e²)).
Note that PPR can simulate arbitrary local DP mechanisms. However, we present only the result of privUnit, because it achieves the optimal privacy-accurae trade-off. Besides simulating local DP mechanisms, PPR can also compress central DP mechanisms while still preserving some (albeit weaker) local guarantees. We give corollary of Theorems 4.3 and 4.6 The proof is in Appendix H
7

---

Corollary 5.2 (PPR compressee Gaussian mechanism). Let E (0, 1). Consider the Gaussian
mechanism P (+1x)= Nax Ial,), and the proposal distribution Q = (0,, ( ( / n
)ll),, where
For each client i, let Z₁ be the output of PPR applied Pzxx (- (-Ix;). We have: CV 2211(1225/) 8
M(Z)) = = E, Z yields an unbiased estimator of p(X")) = - X, satisfying (s, 6)-
central DP and has MSE Billa --ll1 ddd/n??
As long as & < <1//n, PPR satisfies (2ax/ne, 26 -local DP
The average per-client communication cost at most + logg (1 + 1) + bits where
C²n
nE²
:== 2
log2
+1) T v log2
2d ln(.222)) + +1) + nl
do
where Taa = (1.8233)))) min - 1)/2, //, 1}.
few remarks are in order. First, notice that when a is fixed, for an O per-client communication cost is
cdd
log (1(()) MSE, the
Odd (log(11/)) + + +1),
ne²
which is at least good as the O(ne² log(1/0) /8) 1) bound in [75 19 and can be better than O(ne²/ (1/6) + 1) when n > d. Hence, the PPR-compressed Gaussian mechanism is order-wise optimal. Second, compared to other works that also compress the Gaussian mechanism, PPR is the only lossless compressor; schemes based on random sparsífication, projection, or minimum random coding (e.g., Triasteyn et al. (78), Chen al. (19) lossy, i.e., they introduce additional distortion on top of the DP noise. Finally, other DP mechanism compressors tailored to local randomizers [1] do provide the same level of central DP guarantees when applied local Gaussian noise since the reconstructed noise is no longer Gaussian. Refer to Section for experiments.
Applications to Metric Privacy
Metric privacy [16 3 (see Definition 3.2) allows users to send privatized version Z E IRd of their data vectors X E Rd to an untrusted server, so that the server can know X approximately but not exactly. R4), where d-dimensional Laplace noise is added to X. The conditional density function of Z given X is (=(rr) x e (2,x( where is the privacy parameter, and the metric dx 2) = | æ||2 is the Euclidean distance. The Laplace mechanism achieves E dx-privacy, and has been used, for example, in eeo-indisinnguusaabllyy to privatize the users' locations 3. and to privatize high-dimg sotb-dimensionl word embedding vectors 33 34)
A popular mechanism is the Laplace mechanism [16] 3 33
A problem is that the real vector Z cannot be encoded into finitely many bits. To this end, B studies a discrete Laplace mechanism where each coordinate of Z is quantized to a finite number of levels, introducing additional distortion to Z. PPR provides alternative compression method that preserves the statistical behavior of Z (e.g.. unbiasedness) exactly. We give a corollary of Theorems ! The proof is in Appendix [ Refer Appendix for an experiment
4.3 and 4.7
metric privacy.
Corollary 6.1 (PPR-col comppesedd Laplace mechanism). Consider PPR applied to the Laplace mechanism Pz x where X E (C( {x E IR || S C), with proposal distribution
Q = (0, C2 + d+1 (T)). It achieves an MSE d(d+1), 2ac dx-privacy, and a compression size
d
ct
at most + log (E + + bits, where
d
(2 (C
2 C28a
+ ++1+))
logg r(d + T(2 +1)
f = 2 c
log2
+ Ta.
where Na == (log2 (3.56)) min((a- 1)/2, 1).
9The restricted range < 1/vnis due to the simpler privacy accountant 25 By using the Rényi DP accountant instead, one can achieve tighter result that applies any We present the Rényi DP version of the corollary in Appendix G Moreover, in the context of federated learning. n refers to the number of clients in each round, which is typically much smaller than the total number of clients. For example, as observed in (52). the pou-round cohort size in Google's 's FL application typically ranges from 10 to 10ah significantly smaller than the number of trainable parameters E [10", 100] the number of available users N [10", 10
8

---

7 Empirical Results
We empirically evaluate our scheme on the DME problem (which is formally introduced in Section 5 examine the sampled Gaussian Mechanism (CSGM) [19] Algorithm 1], an order-optimal scheme for DME under central DP. In Chen et al. [9] each client only communicates partial information (via sampling a subset of the coordinates of the data vector) about its samples to amplify the privacy, and the compression is mainly from subsampling. Moreover, CSGM only guarantees central DP.
seccuracy-communicatton trade-off, and compare it with the Coordinate Sub-
We use the same setup that has been used in 19 consider n 500 clients, and the dimension of
local vectors is d 1000, each of which is generated according to Xz(i) iid. (2 Ber(0.8) 1), where (0.) is a Bernoulli random variable with parameter p = 0.8. We require (e, - DP with d 10 and E [0.05, 6) and apply the PPR with a = 2 to simulate the Gaussian mechanism, where the privacy budgets are accounted via Rényi DP.
We compare the MSE of PPR (a 2. using Theorem 4.3) and CSGM under various compression sizes in Figure (the y-axis in logarithmic scale) Note that the MSE of the (uncompressed)
Gaussian mechanism coincides with the CSGM with 1000 bits, and the PPR with only 400 bits. We see that PPR consistently achieves a smaller MSE compared to CSGM for all e's and compression sizes considered. For 1 and we compress d = 1000 to 50 bits, CSGM has an MSE 0.1231 while PPR has an MSE 0.08173, giving a 33.61% 61% reduction. For e = 0.5 and we compress d 1000 to 25 bits (the case of high compression and conservative privacy), CSGM has an MSE 0.3877, while PPR has an MSE 0.3011, giving a 22.33% reduction. These reductions are significant, since all considered mechanisms asymptotically close to optimal and large improvement compared to an (almost optimal) mechanism is unexpected. See Section L for more about MSE against the compression sizes.
We also emphasize that PPR provides both central and local DP guarantees according to Theorem 4.5 4.6 and 4.8 In contrast, CSGM only provides central DP guarantees. Another advantage of PPR under conservative privacy (small E) is that the trade-off between e and MSE of PPR exactly coincides with the trade-off of the Gaussian mechanism for small (see Figure D.. and CSGM is only close to (but strictly worse than) the Gaussian mechanism. This means that for small PPR provides compression without any drawback in terms of c-MSE trade-off compared to the Gaussian mechanism (which requires infinite size communication to exactly realize).
Moreover, although directly applying PPR on the d-dimensional vectors is impractical for large d. one can ensure an efficient (dd running time (see Section X for details) by breaking the vector with d = 1000 dimensions into small chunks of fixed lengths (we use debunk- = 50 dimensions for each chunk), and apply the PPR to each chunk. We call it the sliced PPR in Figure Though the sliced PPR has a small penalty on the MSE (as shown in Figure D it still outperforms the CSGM (400 bits) for the range of & in the plot. For the sliced PPR for one d = 1000 vector, when e = 0.05, the running time is 1.3348 seconds on average [1] For larger e's, we can choose smaller dehunk to have reasonable running time: For 6 and dehunk = 2 we have an average running time 0.0127 seconds and with dehunk = 4 we have an average running time 0.6343 seconds; for e = 10 and debunk = we have an average running time 0.0128 seconds and with dehunk we have an average running time 0.7301 seconds. See Appendix K for more experiments on the running time of the sliced PPR.
8 Limitations
While PPR is communication-efin effficient, having only logarithmic gap from the theoretical lower bound on the compression size as shown in Theorem 4.3 the running time complexity can be high. However, we note that an exponential complexity is also needed in sampling methods that do not
ensure privacy, such as 665 47 It has been proved in 2 that no polynomial time general sampling-
Experiments were executed on M1 Pro Machook, 8-core CPU (st 3.2 GH2) with 16GB memory. For PPR under a privacy budget and communication budget b, we find the largest e' S such that the communication cost bound in Theorem 4.3 (with Shannon code (73) for simulating the Gaussian mechanism with (e', ,, 6)-centaal DP is at most b, and use PPR simulate this Gaussian mechanism. Thus, MSE of PPR in Figure [ becomes flat for large e, PPR falls back to using a smaller e' instead of due to the communication budget.
10 Source code: htttt:://gttttteeee
'Thee running time is calculated by 1000 1000 trials. The estimate of the mean of Tahunk is 0.0667, whereas the standard deviation is 0.2038.
500 x Tamunk where each chunk's 's running time Taauk is averaged over

---

Mean estimation (n 500, d 1000, 1e 6)
10a
10a
MSE
CSGM (50 bits)
10
CSGM (100 bits)
(200
CSGM (400 bits)
CSGM (1000 bits)
PPR bits)
(100 bits)
10
PPR (200 bits)
PPR (400 bits)
Gaussian
sliced PPR (400 bits)
10-4
10"
Privacy (e)
Figure 1: MSE of distributed mean estimation for PPR and CSGM 19 for different e's.
based method exists (even without privacy constraint), if RP + NP. All existing polynomial time exact channel simulation methods can only simulate specific noisy channels Hence, polynomial time algorithm for exactly compressing a general DP mechanism is likely nonexistent.
Nevertheless, this is not obstacle for simulating local DP mechanisms, since the mutual information T(X; Z) for reasonable local DP mechanism must be small, or else the leakage of the data in Z would be too large. For an e-local DP mechanism, we have T(X; Z) S min Hence, the PPR algorithm can terminate quickly even has a running time exponential in [(X; Z).
E²} } (in nats) [22]
Another way to ensure a polynomial running time is to divide the data into small chunks and apply the mechanism to each chunk separately. For example, apply the Gaussian mechanism high-dimensional vector, we break it into several shorter vectors and apply the mechanism to each vector. Experiments in Section show that this greatly reduces the running time while having only small penalty on the compression size. See Appendix K for experiments on the running time of PPR.
9 Conclusion
We proposed novel scheme for compressing DP mechanisms, called Poisson private representation (PPR). Unlike previous schemes which are either constrained on special classes DP mechanisms or introducing additional distortions on the output, scheme compress and exactly simulate arbitrary mechanisms while protecting differential privacy, with a compression size that close to the theoretic lower bound. A future direction is to reduce the running time of PPR under certain restrictions on Pz|x. For example, the techniques in 38 35 may be useful when Pzix is unimodal.
Acknowledgment
YL was partially supported by the CUHK PhD International Mobility for Partnerships and Collabora- tions Award 2023-24. WC and AO were supported by the NSF grant CIF-22 13223.. CTL was partially supported by two grants from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No.s: CUHK 24205621 (ECS), CUHK 14209823 (GRF)).
For example, (36] and suthered-quantizznn based schemes 48
72
can only simulate additive noise
mechanisms. Among these existing works, only 722 ensures local DP.
10

---

References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-33 318, 2016.
[2] Eirikur Agustsson and Lucas Theis. Universally quantized neural compression. Advances in neural information processing systems, 33: 1336-77663 2020.
[3] Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. Seo-indistinguishabliy Differential privacy for location- systems. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 901-91-4 2013.
[4] Hilal Asi, Vitaly Feldman, and Kunal Talwar. Optimal algorithms for mean estimation under local differential privacy. In International Conference on Machine Learming, pages 1046-1056. PMLR, 2022.
[5] Raef Bassily and Adam Smith. Local, private, efficient protocols for succinct histograms. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 127-135, 2015.
[6] Charles H Bennett, Peter W Shor, John Smolin, and Ashish V Thapliyal. Entanglement-assine capacity of quantum channel and the reverse Shannon theorem. IEEE Trans. Inf. Theory, 48 (10))2637-2655. 2002.
[7] Charles H Bennett, Igor Devetak, Aram W Harrow, Peter W Shor, and Andreas Winter. The quantum reverse shannon theorem and resource tradeoffs for simulating quantum channels. 2014.
IEEE Transactions on Information Theory,
[8] Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Pro- tection against reconstruction and its applications in private federated learning. arXiv preprint arXiv:1812.00984, 2018.
[9] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108. 07258, 2021.
[10] Mark Braverman and Ankit Garg. Public vs private coin bounded-rout information. In International Colloquium on Automata, Languages, and Programming, pages 502-513. Springer, 2014.
[11] Mark Braverman, Ankit Garg, Tengyu Ma. Huy L Nguyen, and David P Woodruff. Communica- tion lower bounds for statistical estimation problems via distributed data processing inequality. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1011-1022 2016.
[12] Mark Bun, Jelani Nelson, and Uri Stemmer. Heavy hitters and the structure of local privacy. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGA Symposium on Principles of Database Systems, SIGMOD/PODS 18, page 435-447, New York, NY, USA, 2018. Association for Computing Machinery.
[13] Clément I. Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differen- tial privacy. Advances in Neural Information Processing Systems, 33:1 13:15676-1566 15688, 2020.
[14] Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagiclski, Ariel Herbert- Voss, Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, al. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pages 2633-2600 1633-2650., 2021.
[15] Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In 32nd USENIX Security Symposium (USENIX Security 23). pages 5253-5270, 2023.
[16] Konstantinos Chatzikokolakis, Miguel Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metries. In Privacy Enhancing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12 2013. Proceedings 13, pages 82-102. Springer, 2013.

---

[17]
Kamalika Chaudhuri, Chuan Guo, and Mike Rabbat. Privacy-aware compression for federated data analysis. In Uncertainty in Artificial Intelligence, pages 296-306 PMLR, 2022.
[18]
Wei-Ning Chen, Peter Kairouz, and Ayfer Özgür. Breaking the trilemma. Advances in Neural Information Processing Systems, 33:3312 2020.
[19] Wei-Ning Chen, Dan Song, Ayfer Özgüü, and Peter Kairouz. Privacy amplification via com- www-acccrrcc-communiiicce
trade-off in distributed mean estimation. Advances in Neural Information Processing Systems, 36, 2024.
pression: Achieving the optimal
[20] Paul Cuff. Communication requirements for generating correlated random variables. In 2008
IEEE International Symposium on Information Theory, pages 1393-1397. IEEE, 2008
[21] Paul Cuff. Distributed channel synthesis. IEEE Trans. Inf. Theory, 59(1 1):7071-77098 Nov 2013.
[22] Paul Cuff and Lanqing Yu. Differential privacy as mutual information constraint. In Proceed- ings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 43-54, 2016.
[23] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Conference on Learning T'heory, pages 1161-1191. PMLR, 2019.
[24] John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 JEEE 54th Annual Symposium on Foundations of Computer Science, pages 029-438 IEEE, 2013.
[25] Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pages 1-12. Springer, 2006.
[26] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(3-4):21 1--07, 2014.
[27] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology- EUROCRYPT 2006: 24th Anmual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pages 486-503. Springer, 2006.
[28] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[29] Peter Elias. Universal codeword sets and representations of the integers. IEEE transactions on information theory, 21(2):194-200 1975.
[30] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468 2439..479..28 SIAM, 2019.
[31] Vitaly Feldman and Kunal Talwar. Lossless compression of efficient private local randomizers. In International Conference on Machine Learning, pages
PMLR, 2021.
[32] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Anmual Symposium on Foundations of Computer Science (FOCS), pages 954-964. IEEE, 2022.
[33] Natasha Fernandes, Mark Dras, and Annabelle McIver. Generalised differential privacy for text document processing. In Principles of Security and Trust: 8th International Conference, POST 2019, pages 123-148. Springer International Publishing, 2019.
[34] Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe. Privacy-and utility- preserving textual analysis via calibrated multivariate perturbations. In Proceedings of the 13th international conference on web search and data mining, pages 178-186, 2020.
[35] Gergely Flamich. Greedy poisson rejection sampling. Advances in Neural Information Process- ing Systems, 36, 2024.
[36] Gergely Flamich and Lucas Theis. Adaptive greedy rejection sampling. 2023 IEEE Interna- tional Symposium on Information Theory (ISIT), pages 459-459. IEEE, 2023.
12

---

[37] Gergely Flamich, Marton Havasi, and José Miguel Hernández- Compressing images by encoding their latent representations with relative entropy coding. Advances in Neural Information Processing Systems, 33: 13:11631-11141, 2020.
[38] Gergely Flamich, Stratis Markou, and José Miguel Hernández-Lobato. Fast relative entropy coding with A* coding. In International Conference on Machine Learning, pages 6548-6577.
PMLR, 2022.
[39] Gergely Flamich, Stratis Markou, and José Miguel Hernández Lobato. Faster relative entropy coding with greedy rejection coding, arXiv preprint arXlv:2309.15746, 2023.
[40] Ankit Garg, Tengyu Ma, and Huy Nguyen. On communication cost of distributed statistical estimation and dimensionality, In Advances in Neural Information Processing Systems, pages 2734,,734, 2014.
[41] Daniel Goe and Gergely Flamich. On channel simulation with causal rejection samplers. arXiv preprint arXiv:2401. /6579, 2024.
[42] Slawomir Goryczka and Li Xiong. A comprehensive comparison of multiparty secure additions with differential privacy. IEEE transactions on dependable and secure computing, 14(5): 463-477, 2015.
[43] Chuan Guo, Kamalika Chaudhuri, Pierre Stock, and Michael Rabbat. Privacy-aware compres- sion for federated learning through numerical mechanism design. In International Conference on Machine Learning, pages 1 1188-11999 PMLR, 2023.
[44] Yuanxin Guo, Sadaf Salehkalaibar, Stark C. Draper, and Wei Yu. One-shot achievability region for hypothesis testing with communication constraint. In accepted the IEEE Information Theory Workshop. IEEE, 2024.
[45] Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan. The communica- tion complexity of correlation. IEEE Trans. Inf. Theory, 56(1):4335 449, Jan 2010.
[46] Burak Hasırcroğlu and Deniz Gündüz. Communication efficient private federated learning using dithering. In ICASSP 2024-2002200 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7575-7579 IEEE, 2024.
[47] Marton Havasi, Robert Peharz, and José Miguel Hernández-Lobato Minimal random code learning: Getting bits back from compressed model parameters. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
[48] Mahmoud Hegazy and Cheuk Ting Li. Randomized quantization with exact error distribution. In 2022 IEEE Information Theory Workshop (ITW), pages 350-355 IEEE, 2022.
[49] Mahmoud Hegazy, Rémi Leluc, Cheuk Ting Li, and Aymeric Dieuleveut. Compression with exact error distribution for federated learning. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 613-621, PMLR, 02-04 May 2024.
[50] Henri Hentilä, Yanina Y Shkel, and Visa Koivunen. Communication-consstaiii generation: Second-order bounds. IEEE Transactions on Information Theory, 2024.
secret key
[51] Berivan Isik, Wei-Ning Chen, Ayfer Özgür, Tsachy Weissman, and Albert No. Exact optimality of communication privacy- tradeoffs in distributed mean estimation. Advances in Neural Information Processing Systems, 36, 2024.
[52] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and trends@ in machine learning, 14(1-2): 1-200, 2021.
[53] Shiva Prasad Kusiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on 2omputinng44033)7793--38 40(3):793-
2011.
[54] Ashish Khisti, Arash Behboodi, Gabriele Cesa, and Pratik Kumar. Unequal message protection: One-shot analysis via poisson matching lemma. In 2024 IEEE International Symposium on Information Theory (ISFT). IEFF, 2024.
[55] Samuel Kotz, Tomasz Kozubowski, and Krzystof Podgorski. The Laplace distribution and generalizations: revisut with applications to communications, economics, engineering, and finance. Springer Science & Business Media, 2012.
13

---

[56] Natalie Lang, Elad Sofer, Tomer Shaked, and Nir Shlezinger. Joint privacy enhancement and quantization in federated learning. IEEE Transactions on Signal Processing. 71:295-310, 2023.
[57] Günter Last and Mathew Penrose. Lectures on the Poisson process, volume 7. Cambridge University Press, 2017.
[58] Cheuk Ting Li. Pointwise redundancy in one-shot lossy compression via Poisson functional representation. arXiv preprint. 2024.
[59] Cheuk Ting Li and Venkat Anantharam. Pairwise martinlarginall optimal transport and embed- ding for earth mover's distance. arXiv preprint arXiv: 1908001388. 2019.
[60] Cheuk Ting Li and Venkat Anantharam. A unified framework for one-shot achievability via the Poisson matching lemma. IEEE Transactions on Information Theory, 67(5):2624-26511 2021.
[61] Cheuk Ting Li and Abbas El Gamal. Strong functional representation lemma and applications to coding theorems. IEEE Transactions on Information Theory, 6A(11):6967-6978, Nov 2018.
[62] Cheuk Ting Li, Xiugang Wu, Ayfer Özgür, and Abbas EI Gamal. Minimax learning for remote prediction. In 2018 IEEE ISIT, pages 541-545, June 2018. doi: 10.1109/SST.2201884477 8.43738..
[63] Yanxiao Liu and Cheuk Ting Li. One-shot information hiding. In accepted the IEEE Information Theory Workshop. IEEE, 2024.
[64] Yanxiao Liu and Cheuk Ting Li. One-shot coding over general noisy networks. arXiv preprint 2xXiv:242206602 2024.
[65] Chris J Maddison. A Poisson process model for Monte Carlo. Perturbation, Optimization, and Statistics, pages 993-232,22 2016.
[66] Chris Maddison, Daniel Tarlow, and Tom Minka. A sampling. Advances in neural information processing systems, 27, 2014.
[67] Brendan McMaaan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication efficient learning of deep networks from decentralized data. In Artificial intelligence and statisticc, pages 1273 PMLR, 2017.
[68] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275 IEEÉ, 2017.
[69] Buu Phan, Ashish Khisti, and Christos Louizos. Importance matching lemma for lossy compres- sion with side information. In International Conference Artificial Intelligence and Statistics, pages 1387-1395. PMLR, 2024.
[70] John K Salmon, Mark A Moraes, Ron O Dror, and David E Shaw. Parallel random numbers: as easy 1, 2, 3. In Proceedings of 2011 international conference for high performance computing, networking, storage and analysis, pages 1-12, 2011.
[71] Abhin Shah, Wei-Ning Chen, Johannes Balle, Peter Kairouz, and Lucas Theis. Optimal compression of locally differentially private mechanisms. In International Conference Artificial Intelligence and Statistics, pages 7680-7723 PMLR, 2022.
[72] Ali Moradi Shahmiri, Chih Wei Ling, and Cheuk Ting Li. Communication-effiianee laplace mechanism for differential privacy via random quantization. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4550- 4554. IEEE, 2024.
[73] Claude E Shannon. A mathematical theory of communication. Bell system technical journal, 27(3):379-444 423, 1948.
[74] Eva Song, Paul Cuff, and H Vincent Poor. The likelihood encoder for lossy compression. IEEE Trans. Inf. Theory, (2(4))1836-1844 2016.
[75] Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International conference on machine learning, pages
PMLR, 2017.
[76] Lucas Theis and Noureldin Y Ahmed. Algorithms for the communication of samples. In International Conference on Machine Learning, pages 21308-211 21388- PMLR, 2022.
[77] Lucas Theis, Tim Salimans, Matthew D Hoffman, and Fabian Mentzer. Lossy compression with Gaussian diffusion. arXiv preprint arXiv:2206.0 08888, 2022.
14

---

[78] Aleksei Triastcyn, Matthias Reisser, and Christos Louizos. DP-REC; Private & communication- efficient federated learning. arXiv preprint arXiv:2111.05444, 2021.
[79] Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69, 1965.
[80] Guangfeng Yan, Tan Li, Tian Lan, Kui Wu, and Linqi Song. Layered randomized quantiza- tion for coammunicaiion-efficcen and peeeeecvigi distributed learning. arXiv preprint arXiv:2312.07060, 2023.
[81] Jacob Ziv. On universal quantization. IEEE Trunsactions on Information Theory, 31(3):344-347, 1985.
15

---

A Proof of Proposition 4.2
Write (X,); (P()) if the points (Xa); (as a multiset, ignoring the ordering) form Poisson point process with intensity measure μs. Similarly, for f [0, oo)" + [0, o0), we write PP(f) for the Poisson point process with intensity function (i.e., the intensity measure has Radon-Nikodym derivative f against the Lebesgue measure).
Let (T:); ~ (1(1) be Poisson process with rate independent of Z1, Zz,... sid Q. By the marking theorem 577. (Z, T:); ~ PP(Q x xe), where Q x0)) is the product measure between Q and the Lebesgues measure over [0, 20). Let P Pz|x (-Iz), and T; -T-- (2,)) (1))))11_ By the mapping theorem [57] (also [6] 60).. (Z,, Ti), PP(P x)), Note that the points (Z,, Te); may not be sorted in ascending order of T,. Therefore, we will sort them as follows. Let j1 be the j such that T is the smallest, ja be the j other than j1 such that T₁ is the smallest, and so on. Break ties arbitrarily. Then (T is an ascending sequence, and we still have (Z,, Ti ~ PP(P X A(o.cc) since we merely rearranging the points. Comparing (Z),, J PP(P )1o with the definition of (Z,, PP(Q )),,c)),, we can see that (T₂), PP(1) independent of Zj Zjz.... itd P. Recall that in PPR, we generate E Z4 with
7-a
Pr(K = k))
Σ
and the final output is Zg. Rearranging the points according to (1)) the distribution of the final output remains the same if we instead generate K' Z_ with
Pr(K = k))
E
and the final output Zjgr. Since (T₃:); PP(1) is independent of Z,z. rid independent of (Zj, )i and hence Zi ~ P follows the desired distribution.
P. we know that K" is
B Reparametrization and Detailed Algorithm of PPR
We now discuss the implementation of the Poisson private representation in Section 4 Practically, the algorithm cannot compute the whole infinite sequence (T)),- We now present an exact algorithm for PPR that terminates in finite amount of time using reparametrization.
In the proof of Theorem F11 we showed that, letting (Ti); PP(1), Z1 Zz.... ld Q. R
(dP) V1, V2.... Exp(1), PPR can be equivalently expressed
K argminTT R-
&
The problem of finding K is that there is stopping criteria for the argmin. For example, if we scan the points (2), R2, Vi), in increasing order of T, it is always possible that there is a future point with Vi so small that makes T. R. VV, smaller than the current minimum. If we scan the points in increasing order of V; instead, it is likewise possible that there is future point with very small T, We can scan the points in increasing order of U, == T V.. but we would not know the indices of the points in the original process where Ti < T2 S out the Z, corresponding to each point (recall that in PPR, the point with the smallest Tü corresponds Z, the second smallest T, corresponds to Zz, etc.).
is in increasing order, which is necessary find
Therefore, we will scan the points in increasing order of B, == T min V4, 13 instead. By the mapping theorem 577 (T PP(a PP(a-llt/o-1 1///o-1). By the marking theorem [57]
(T (T); ~ 1P((a-ll/a-1gp
By the mapping theorem,
(T.,T, Vi), ~ PP(a 26
16

---

Since B, = m . V again by the mapping theorem,
(B:): ~ PP
181/0-2 dv
+ a 1-1l//a-2 br dt
PP
1/11a1120 c- ta - a11-a-111)
-P a (e bl/a-1).
where 71 := 1= 1) and ((, Le e e 7 dr the lower incomplete gamma function.
Comparing the distribution of (B.), and (T i. we can generate (B,); by first generating (U1);
PP(1), and then taking B; = (U,0/(e (e- + 7));. The conditional distribution of (T;, Vi) given
B, = is described as follows:
With probability e-1((e + 771, ) we have TV = and 77V; b(Ep((1) + 1), and hence
= b1/a and V; Fx) +1.
With probability 7/(l + 71), have T7 V, b and
-11///222--0 - T 1 a 1)61/a-1*
Hence, for 0 <T
7(1 a TT
PP) b/T)
7(1 - a 1,1'
and V3 follows the truncated gamma distribution with shape within the interval [0, 1]. We then have T, = (b.
and scale 1, truncated
The algorithm is given in Algorithm [I The encoder and decoder require a shared random seed s. One way to generate is to have the encoder and decoder maintain two synchronized pseudorandom number generators (PRNGs) that are always at the same state, and invoke the PRNGs to generate 8, guaranteeing that the at the encoder is the same as the the decoder. The encoder maintains collection of points (T;, Vi, O2), stored in a heap to allow fast query and removal of the point with the smallest T; The value O E {0, }} indicates whether it possible that the point (T;, V,) attains the minimum of T. R Vv. The encoding algorithm repeats until there is possible points left in the heap, and it impossible for any future point to be better than the current minimum of T RØ Vk- The encoding time complexity is ((sup,(dl (dP/dQ) log(sup,ddP/OQ) (dP/dQ)=))), which is close to other sampling-based channel simulation schemes (45 36 The decoding algorithm simply outputs the k-th sample generated using the random seed which can be performed in O(1) time [4]
The PPR is implemented by Algorithm 1 We write +- (xp=(1) to mean that generate an exponential random variate æ with rate I using the pseudorandom number generator Y Write Expro (1) mean that is generated using a local pseudorandom number generator (not 9).
C Proofs of Theorem 4.5 and Theorem 4.7
First prove Theorem 4.5 Consider s-DP mechanism Pzxx. Consider neighbors ø 22, and let T dP (Z:)), and K, be the output of PPR applied on Pj. for j 1, 2. (a
P3 P2)x (-1x;), Ti
Since Pz|x is E-DP.
dP
(z)
It was shown in 33 that greedy rejection sampling 45 runs in O(sup, (dP/dQ)(=)) time. The PPR algorithm has additional log term due the of heap.
14 A counter-based PRNG (70) allows us to directly jump to the state after & uses of the PRNG, without the need of generating all & samples, greatly improving the decoding efficiency. This technique is applicable to greedy rejection sampling (45) and the original Poisson functional representation [6] 60 as well.
17

---

Algorithm Poisson private representation
Procedure PPRENCODE((, Q, 2rr,,", 8)
Input:
parameter a > 1, distribution Q, density r(z) == (dP/dQ)(=). bound y* 2 sup, r(z), random seed Output: index & E Σ>0
1: Initialize PRNG & using the seed
2: u 0, :" +- oc, t k* 0, n 0
3: 71 < >11 a 1) So e 7 dr
4: h (empty heap)
5: while true do
6:
+ + Exp ocal (1)
Generated using local randomness (not $
7:
b [ua/(e + n))
if and b( 9: return 1s*
8:
wn then
No possible points left and future points impossible
end
11: if Uniftocal (0, 1) < + 7)) then
> Run with prob. e / 71)
12:
1 t b2/a v Explocal (1) +1
13:
else
14:
repeat
15:
8 f- Gammajocal -a 111) until <
D Gamma distribution
16:
17:
t < (b/u) 1/a
18:
end if
19:
I 4- ((ttr"))' w²}
b Is it possible for this point to be optimal
20:
Push (f
21:
b Number of possible points in heap while h + 0 and min 1' < b2/a do Assign Zi to points in heap with small T; (t, v) +- arg (in t', and pop (t, 0) from h
+ 0
22:
23:
24:
n n 0
25:
++ +
26:
Generate 2 Q using y (t/r(2))
27:
28:
if w < w" then
w²
30:
ks -
end
32:
end while end while
Procedure PPRDECODE((,
Input: Q, index & E Zzo, seed Output: sample 2
1: Initialize PRNG 3 using the seed s
2: for i 1,2,...,k do
3: Generate z ~ Q using? y
D. See footnote
14
4: end for
5: return
18

---

for Q-almost every
18 and hence e eTx2,, S T2.5 S eT
For ls E Z+, we have, almost surely,
1,k
Pr(K1 = (Z,,
ii=
1,8
ae
T,
e-ae fro
i==
20
Pr(K2 k (7,, T:).).
For any measurable S S _ Z>o.
Pr (((()),, K1) E
Pr (((Z,);,
Ki) E ES (Z,, Ti):)]
=
Σ
Pr (Ki = k (2x,
k: (174)
S 22E E
Σ
Pr (K2 k (2)))
1: k))
2ae Pr (((Zi):; S).
Hence, K(x 2ne-DP.
For Theorem
4.7 consider a dx-private mechanism P2|x, and consider #1, 22 E X. We have
ce dP2 (2) dPi (z) s (x dP2 (z)
dQ
aQ
dQ
for Q-almost every By exactly the arguments in the proof of Theorem 4.5 Pr (((Z)), Ki) E 8) < (01 Pr (((Z));, K2) E S), and hence P(z,).KIx is 2ue dx- private.
D Proof of Theorem 4.6
Consider (s, 5)-DP mechanism Pzxx Consider neighbors F2, and let P, := (+1x)))))). and Ký be the output of PPR applied on P. for j = 1, By the definition of (e, -ddffcrreent privacy, we have
/ max (2)(2) e" p2(2), 0) Q(2z) <
(5)
/ max (p2(2) e (z)), 0) Q(dz) <
(6)
Let
(x) min {max (x), e p2(=)) e pz))) Note that e p2(2) S (2) < e pz(z). We then consider two cases:
Case 1: J ((z) < Let ps(2) be such that f (s(2)((d2) and
p(z) S pa(z) e p2(z).
We can always find such p3 by taking an appropriate convex combination of the lower bound above (which integrates to < 1) and the upper obund above (which integrates to 2 1). We then have
e e p2(()) S Ps(=) S ef p2(2).
15 DD only implies that (2) holds for Pi-almost every (or equivalently Pa-almost every since P1, Pz are
absolutely continuous with respect each other). We show that 2 holds for Q-almost every z. Apply
Lebesgue's decomposition theorem to find measures Q, Q such that Q = Q + Q Q < P. and Q 1 Pt. There
exists Z' C Z such that P1(Z")
and Q(Z')) = Since Pa & Q, we have P1 < Q. We have 2 for
Qlamost every 2. Also, we have
Qlammost every since z $ z' gives aQ (z) aQ (z) for
Q- D-almost every and also
dP de
(z) 0 for almmms every since H3 < P..
19

---

dp (z). If p2( -e < O, then p1(2)-Pa(z) - -1()))p(=) 0. 0. px p2(z) 0, then pz(z) =
p(z) = e² P2(2). Either way, we have max (pi(2) -2)))))))), 0} max (2) P2(2), 0}. By
5 we have
/ max ( pz(2), 0) Q(dz) - 8.
Let P3 = =2z be the probability measure with dP3/dQ = Ps. Then the total variation distance drv (V1, Ps) between P1 and P3 most 8, and by (
dl's dQ (z) - dQ
dl's
(2) S e-
(8)
dQ
Case 2: [=)=)((dz) > Let p=(=) be such that f (d))) and
p2(2)) pa(=) S p(z).
We can always find such Pa by taking appropriate convex combination of the lower bound
above (which integrates to I 1) and the upper obund above (which integrates to > 1). We again
have e p2(2) I pa(2) p2(2). If e ==(22) (1(2) 0, then Pz(z) - (2) I p(2)
Pi(2) S If e- e p2(2) (2)) > 0. then Pa(2) p(z) e p=(2). Either way, we have
max {ps(2) p1(2), 0} max fe p2(2)) P1(2), 0}. By 6 we have
/ max (ps(2)
-z (z). 0) Q(dz) sc
Let P3 P be the probability measure with dP3/dQ P3- Again, we have dTv(PI, P3) and (8). Therefore, regardless of whether Case 1 or Case 2 holds, we can construct P3 satisfying
dTv (1,, P3) < d and (8). Let K3 be the output of PPR applied on Ps.
In the proof of Theorem we see that PPR has the following equivalent formulation. Let (T;); ~ rid Q. Let R, == (d.).
(1) be Poisson process with rate independent of Z1, Zz,...
sid
and let its probability measure be PR. Let V1, V2,... Exp(1). PPR can be equivalently expressed as
T 1/a
K argmint Rr VV- argmin
Rg
&
Note that (T.VVl/a),
1 PP(T(1 - -- is a uniform Poisson process.
Therefore PPR is the same as the Poisson functional representation
applied on (T₃ V V. /o)) )a-
By the grand coupling property of Poisson functional representation 60 59 (see (59 Theorem 3)). we apply the Poisson functional representation on P1 and P3 to get K₁ and K3 respectively, then
Pr(Ki + K3) S 2drv (P1, Pa) s 25.
Therefore, for any measurable S _ 8 x Zzo.
Pr (((z),,,, E S) S Pr (((())))) K3) E S) +2
S e 20 Pr (((Z)); K2) E SS) + 25,
where the last inequality is by applying (2aE,28)-DD 2D)
3 on Pg, P2 instead of Pı, Ps. Hence, P(z,,. is
E Proof of Theorem 4.8
We present the proof of ()PD) of PPR (i.e., Theorem 4.8
Proof.
We assume
38
a
<
(9)
In 8'
20

---

where 3 == e 4.2 Using the Laplace functional of the Poisson process (Ti); [57 Theorem 3.9), for
> 0.
exp (- (-Jo 20
E
exp
1
Σ
7-a
(1 (opp-ww-")/0
(10)
(-wl/ar(1 - -a-))
exp
We first bound the left tail of Σ, T.-0
By Chernoff bound, for d 2 0,
Pr
TTa <d
S inf endR w20
exp w Σ T:a
inf exp
wd - w 1/T((1 a a-11)
exp
a
d-
T - a1
r(1-a-1)
ad
ad
(T(1 a ()=))=
a a- - aa ou.
exp
ad
(1 a 1
exp
(T(1 a11)aa
ad(( a 1)a
(1- a-1)
exp
(T(2 - a a-10=1))) 1))²
(a 1)d
exp
(T(2 - 1-
Therefore, to guarantee Pr E, 7:-0 < d) $ 5/3, we require
1(2 a 1) - In((83)) 1a
ds
a-1 1
where
I(2 a--)- (-In(8/3) -(a-1)
-a-11)
2 (exp (->(a - 1))) (-In(02)
35E2
A322
(-21n 5)
2 exp
-ya I
38
2e -13822
exp
8
2/y
BEa
exp
3 In
3e
2 exp (-0.81 (362)
2/22
since < 8 < 1/3,
e 4.2 and < S 1, where 7 is the Euler-Mascheroni constant.
Hence, we have
E/2
Pr Σ T. a
(1))
a
21

---

We then bound the right tail of Σ; T Unfortunately, the Laplace functional (TO) does not work since the integral diverges for small Therefore, we have to bound away from 0. Note that min; 7, Exp(1), and hence
Pr(min T, - 8/3) s 8/3.
(12)
Write 6/3. Using the Laplace functional again, for >> O,
Σ T; T
E
exp
(1 - exxp(ul ))d(
exp
exp
(oxp(ut - 1)dt -1)dt
(exp(wT -3 1) t- a
S exp
7 - dl
exp(wT 9)
--(-1)
exp
T T(exp(uT 9) -) 111)
a
exp
a-1
Therefore, by Chernoff bound, for d 2 0,
Pr
Σ f: 2d)
x,TT
(wud+ r(exp(ut-9) -
$ inf exp w>D
a a-
dr 1ldda((a-1)) (oxp(ln(d(a-1)ee - 1)aa-1)) -1)011))))))11111 -1)
S exp
a a-1
d(a 11--))
Indla 1) 11) +
exp
a-1
CT
Inc c-1 1
exp
a a-1
a-1
exp
a-1 (elnc c
T
7(2122 - 1)(c- 1)2
I exp
(13)
a a-1
where
c:= d(a a - 1)7a1
and the last inequality holds whenever E [1,2] since in this range,
chn-c++ (2 2 1)(c 1)2.
Substituting
2/2
a a-1
we have a By 13 to guarantee Pr( Pr: 1: 2 d) 5/3 require
r(2 2
- 1)2 >
a
22

---

aa - ()(())))
2/2 2/22a-12 2
+ 1.
(14)
7(2lm2 1)
Substituting 9 we have
R682 lnd
2 2/2
7
8
38
= exp
2
+
In
3
-n 8
2 8)
B
2 exp
+
2
-3 In 8
2,3
= exp
3
since 0 < 2 < 1/3. Note that this also guarantees
2 E [1,2] since 3 = - and
& S 1. We also have
(a - (a-1)(-In1)
-In
- InT)
121n2-1)
7(2 2 1)
352
In (-2 5)
(2/3) 1) 63E2
2ln
< 1633?
Hence,
(a - lnr)
+1 < 48 +1
7(21n2 1)
S exp (4EV
1
28
33
))
exp
$
3
S aa-
where (a) is by 3 = e422 Hence 14 is satisfied, and
2/2
Pr
Σ
3
Combining this with 11 and 122..
C EE/2
2/2
Σ
a a-1
a
C -2f2
< Pr
+ Pr(min T; S 8833)
2/2
+Pr
t-a
a
t1,28/3
8..
Consider an (s, -ddifferrettiall private mechanism Pzix Consider neighbors 2 22, and let P, Pz|x (112,), Tg T./(2f (Z.)), and K, be the output of PPR applied P,. for j = 1, 2. We
23

---

first consider the case ô = O, which gives
dQ (x)
dB
S cº aQ
for every 2. For any measurable
S 200 x Zzu.
Pr(( (z)) Ki) E)
= E Pr (((2));, K1) ES E (2,, T:).)
=E
Pr (K1 kb (21,
An k)s
T
E
Σ
Ei
A: R)
E/2
8/2
T
S
1
T
min
Σ
+8
Ei T
A: (:2()),
<
+
(-///(( 1)
As ((Z)).)EES
(Zx)) "
E
min
Σ
aQ
8
E 2-22/ 1)
As ((2.).))E
(e de (Zx) (2)
E
min
Σ
aQ
+
0-812/(0 - 11)
An: ((Z))
c 2/2 e
(e= (2z)))TT
<
E
1
T-a
min Σ
aQ
1
+ 28
a
e-2/2/
k: ((Z)))
dPs
Tx aQ
<
E
min
+ +.25
e- E, 12
c: ((Zi)aajes
t
<
E
Σ
+ +8
E. T-aa
A: kE)
c Pr (r((())) K2) () + 20.
(15)
Hence PPR is (or + ε, 20) differentially private.
For the case d > 0, by the definition of (e, oddffferrent privacy, we have
/
dP aQ
e: dP3 (=), 0f Q(d=) s 8.
max
(=)
aQ
Let P3 be probability measure that satisfies
dP
min
(2),
dQ
for every z. Such P3 can be constructed by taking an appropriate convex combination of the lower bound above (which integrates to < 1) and the upper bound above (which integrates to > 1) such that P3 integrates to 1. We have
dPP dQ
dP's dQ
(z), 0) Q(dz) <
max
(z)
and hence the total variation distance drv (P1, P3) between P1 and Pa most d. Let K3 be the output of PPR applied on Pa.
24

---

In the proof of Theorem F.1 we see that PPR has the following equivalent formulation. Let (Ti), (1(1) be a Poisson process with rate 1, independent of Z1, Z2, ~
vid
Q. Let R. :- (2))
and let its probability measure be PR. Let V2, V2,... sid Exp(1). PPR can be equivalently expressed
T&Ve //
K argminn Ry Vx argmin k
Rg
k
v-1/ae- Note that (T.V P
( is uniform Poisson process.
Therefore PPR is the same as the Poisson functional representation 6
60 applied on (T: //a)
By the grand coupling property of Poisson functional representation if we apply the Poisson functional representation on P1 and P3 to get K1 and K3 respectively, then
60 (see [59 Theorem 3)),
Pr(Ki + K3) S 2drv (P1, P3) s 26.
Therefore, for any measurable S n Z>0.
Pr (r((());; K1) ES
< Pr (((;);, K3) E 68)+24 2
I 05 Pr ((z,),. K2) E S) + +28 26,
where the last inequality is by applying 15
Ps, Pa instead of P1, Pz. This completes the proof.
F Proof of Theorem
We now bound the size of the index output by the Poisson private representation. The following is refined version of Theorem 4.3
Theorem F.1. For PPR with parameter a > when the encoder is given the input x, the message K given by PPR satisfies
Ellog K] D(PIIQ)
inf 1 (0.a.1)
T(1 ([1-nt1jn
n [(n + 11
log
(T(1 ) +
(16)
log(3.56)
D(P[I))
(17)
- min((a-1)/2.11
where P ;= P21x
Note that for a = xo, (66) with 7 gives Ellog K1 S D(PIIQ) + log 2, recovering the bound in (which strengthened (11).
58
Proof. Write (Xt); (p) if the points (X,), (as multiset, ignoring the ordering) form a Poisson
point process with intensity measure μ. Similarly, for f [0, oo)" - [0, oo), we write PP( (f) for the Poisson point process with intensity function (i.e., the intensity measure has Radon-Nikodym derivative f against the Lebesgue measure). Let (T)), ~ PP(1) be a Poisson process with rate 1,
independent of Z1, .z.... rtd Q. Let R, = (dP)dQ)(Z.), and its probability measure be Pn- We have T, T Rg Let V1, 12, iid Exp(1). By the property of exponential random variables. for any P1,P2, ... 2 0 with E; Pt < oo, we have Pr Pr(argmin, Ve/P: = k) pk/ Σ; Therefore, PPRF can be equivalently expressed as
K argminTe B VV.
&
By the marking theorem
57
(T;, Rr, V.); is Poisson process over [0, 00)3 with intensity measure (T,, R4 V.), PP (e- (P((r))
25

---

By the mapping theorem 57 letting W; := T,
T, R₂ Vi, we have
(T, R2 Wi)s ~ PP (10 -or" PR(r)).
(18)
Again by the mapping theorem,
ER~PA [/ Rtta a dt
(Wi), ~ PP
PP
E
R I a 1120)
PP
E
w 1/a-11100111 T(1 - -a )
PP
1o a -a
since E[R] 1 [dPP/a))s))((ds)
Recall that WK min; W; by the definition of K. We
have
Pr(Wx > w) = exp (-J²" a 10-// T(1 a '')dr)
exp
= exp (-w"/aT(1 - a a0)))
Hence the probability density function of WK
d dw
exp (- 1/1//T(11- - -1-
= - - -- exp (-w\/ar(1-aa))
(19)
By (8). and PR is
the Radon-Nikodym derivative between the conditional distribution Rx given WK = w
Pr(Rk E |r,r +r) Wx w)/Pn(dr)
So00 pat ----a-=""t"" t- df
En-Pa [Jo Rat-ag-
dt
a www//a [[ a -1)r
a a/'w//a-110 - a 11)
does not depend on w. Hence Rx is independent of WK. By 18). 0
E Rk r, Wx w] fo 11 --- wr t- dl
So par ae u dt
a (y(+t T(1 (n 1)a 1r
(20)
a1-a
Since Rx is independent of WK, using
20 and 19 for n E (0, 1),
ETT
RK r
[ 20
a (w T - (n + 1)a exp (-w2/aT(11 a a)1) dw
-r (1 1)a 1) f a w exp -wwl/ar1 a 1) dw
=,"T(1 (1 + 1)a (T - a -1)) -n 1n+1) + +1)
=: ".
(21)
26

---

where Ca.n T=1 - (n + ( - (T-1 [n + 1). Hence,
El + 1) Rx = r]
I ( + 1) Rx r]
Ein log (T + 1) Rx = r] 1) -1 log(Co..) " + 1).
(22)
Note that
-- T, < TKHl.
and hence the expecation of K - given Tkk should be around Tg. This is not exact since conditioning on Txx changes the distribution of the process (T;, Rg Vi).- To resolve this problem, we define a new process (T R, Vi), which includes all points in (T;, R₁, Vi), excluding the point (Tx, Rg. Vk). together with newly generated points according to (P(eE"PA(r)LA (P(()) < TR R Vx)).
Basically, (t"r=" < R is the "impossible region" where the points in (T,, R₁, Vi); cannot be located in, since K attains the minimum of Tg Rx The new process (T), R2 V(); removes the point (Tx, Rg. Vx), and then fills in the impossible region. straightforward to check that (T), R4, Vi); ~ PP(e- "P((r)) independent of (Tx, Rx, Vx). We have
E K
Tx]
E
[[i: Ti < TxH1
Tk +1
[ito: T < TKHl
< E
Tk -1
= Tk + 1.
Therefore, by
22
and Jensen's inequality.
E log K]
E [E[log K [Txc]]
< E [log(TK + +]]
E E [lg([TK + 1) Rxl I
S E (n log((co, R2 + +1]
y 'RZp [1og| caw
dP (2) )" +11
aQ
= - log
((8(2))
dP
(Z)
""]
+ 17 'B log Ca.n +
dP (G) -1)
aQ
E ([ (1) "1)
"I)')
< D(P[IQ) + n log Co.n +
< Q(P + -og(Caan + 1),
where the last line is due (d(
[(aP S 1 (this step 1).
appeared in [58). The bound (16) follows from minimizing over n) E
To show 17 substituting 7 mann(a- - 1)/2, 1J.
T(1 - (17 + ())
Ca."
- a((-==))))tt)
(1 (1-a² a -1ynt
0.885 (1 (1 + 1)a-1)
(1 a -1ynt1
0.8852. (1 - ((a - 1)/2 + 1)o-
2
(1 a 11y
0.885
< 2.56,
27

---

where (a) is because 0.885 2 xI(x)) = [(x + for < S 1. Hence,
Ellog K] < D(PIQ) + 1 log(Can 1), log(3.56)
S ((II)) + min (a 1)/2,
G Distributed Mean Estimation with Rényi DP
In many machine learning applications, privacy budgets are often accounted in the moment space, and one popular moment accountant is the Rényi DP accountant. For completeness, we provide Rényi DP version of Corollary 5.2 in this section. We begin with the following definition Rényi DP:
Definition G.1 (Rényi Differential privacy conditional distribution Pzix of Z = A(X), we say that it satisfies (y, Rényi DP if for any neighboring (z, x²) E N and S _ 2, it holds that
Given a mechanism which induces the
D, (Pzxx== P2|x=r)) || EE
where
Dy (PII))
7 - log BQ
(
is the Rényi divergence between P and Q. I X2, say that the mechanism satisfies (7, e)local DP.
The following conversion lemma from 13 relates Rényi DP to (
Lemma G.2. If satisfies (rr, Réényi DP for some 7 2 1, then, for any 0, satisfies O))D( where
(DP = - log (1/ (1/76) + log((1 - 1/7).
(23)
The following theorem states that, when simulating the Gaussian mechanism, PPR satisfies the following both central and local DP guarantee:
Corollary G.3 cPPR-compressed Gaussian mechanism). Let E 2 0 and Y 2 1. Consider the Gaussian mechanism (-1x(- Wax,, o" Ia), and the proposal distribution Q = NOO, (C,
- Ia), where o 2 V
Cr. For each client i, let Z; be output of PPR applied on (-)x(- 25
have:
p(Zz)= == 1 E, Zi yields unbiased estimator of =( X4 satisfying (r,E)-
(central) Rényí DP and (EDP(8), 8D.,, where (D) is defined in
-Pzi,, satisfies (()), 26) -local DP, where
log(1 1/7). log (1/78)
E () = Vn +
7-1
=i(Z") has MSE [lll ق| d2d/n².
The average per-client communication cost most log (l + 1) + bits where
C'n
ne²
+1) + 1/ - 2 2d11(11.5/8) + 1) + Mar
{:= 2
log2
loga
2
where Ta = (log, (3.56)) min - 1)/2, 1}.
The local DP guarantee follows from Lemma G.2 and Theorem 4.8 Finally, the communication bound can be obtained from the same analysis in Corollary 5.2
Proof. The central DP guarantee follows from 68 and Lemma G.2
28

---

H Proof of Corollary 5.2
Consider the PPR applied on the Gaussian mechanism Pzxx 221x(-1r)= = Wax L3²1)), with the proposal
distribution Q NO0 C e Ma). PPR ensures that Z follows the distribution (N To).
Therefore the MSE is
n =
E Il Al
Σ
(X: Z,)
0²
d
71
7
o²d
n²
For the compression size, for Rd with || S C, we have
(()2))(+=)11))
dP dP22x (7)
= -EZxPaxx(1))
log dQ
(2TO²) /n) d/2 exp( 2
= (12xP2|x(11)
log (2 C + )))
4/2 exp
1/001/11///( +
d
C² + a
d²
1
1| - x013
= (E2=Paix(1))
log
+ 2
2
02/n
C2 + d2
0²
C² + o² d'dnn
d'd/n
$
log
02/n
2
C2
d²
0²/n
C²n
= 2
log
d
+1 1
Hence, by Theorem 4.3 the compression size is at most l + logg(e + 1) + 2 bits, where
d
C
i =
log2
+ 1) + na
2
2
d
2d (125588) +1) +
ne²
log2
2
ne² log2 (e)
+ 17a,
4 4ln(1.25/0)
where 7a = (3.52)))5))) min((a- 1 1).
The central-DP guarantee follows from (c, 5)DP of Gaussian mechanism [26] Appendix A] since the output distribution of PPR exactly the same as the Gaussian mechanism, whereas the local-DP guarantee follows from Theorem 4.6 and [26 Appendix A].
I Proof of Corollary 6.1
Let || 2 RS where R E [0, 20) the magnitude of X Z, and ||S]|| As shown in 33
R follows the Gamma distribution with shape d and scale 1/e. Hence the MSE is
d
d(d + 1)
E
[|X
- =
=
+
22
2
29

---

The conditional differential entropy (in nats) of Z given X is
h(2(x) h(B)) + ((SRR)
= =d(In - (d- 1))(d) - In e + E I
= =d+In - 188-1177 ()) - Ii + Ind + In(Vol((a
+ (d 1) Rl
= -d+ II(I) - (d (d) - In + Ind ln Inl
2 +1
(d - In In 1d-11)e())
dln CV In r(g +1)
(d)
where & is the digamma function. Therefore, the KL divergence between (2)x(+|x) and Q (in nats)
((P21x(1=)112)
C
1+)))
d
4/2
1
In
2T
exp
2
C2
+ 4+1
h(21x)
d
C
d
d+1
E Ez-Pz x (1x)
|
eVTT In
(d)
In
2T
dln
2
6²
2( 7
[ +1
2
C
d+1
C + d(d+1)
eV
dd)
$
In
2T
dln
In
2
E²
2 7 +
4+1
[ + 1)
d
2
1(
d + 1
In
2
T(2 +1)
Hence, by Theorem 4.3 the compression size is at most E + log, (f+ 1) + 2 bits. The metric privacy guarantee follows from Theorem 4.7
J Experiments on Metric Privacy
We use PPR to simulate the Laplace mechanism 3
33 34
fz x (=|æx) x e -edx(zz,2) discussed
in Section 6 We consider X E Ba(C) where C 10000 and d 500. A large number of
dimensions is common, for example, in privatizing word embedding vectors 33 34 We compare 6.11 the performance of PPR-compressed Laplace mechanism (Corollary 6.1) with the discrete Laplace mechanism B]. The discrete Laplace mechanism is described as follows (slightly modified from K to work for the d-ball Ba(C))): 1) generate Laplace noise Y with probability density function fr( e=ellulla; 2) compute Ż X + Y; 3) truncate 2 to the closest point Z in Ba(C); and 4) quantize each coordinate of 2 by a quantizer with step size u > O. The number of bits required by the discrete Laplace mechanism is [logg (Vol(Ba(C))/ /un)] where Vol(Ba(C)) //v /ud is the number of quantization cells (hypercube of side length u) inside BB(C) The parameter u is selected to fit the number of bits allowed.
Figure shows the mean squared error of PPR- compressed Laplace mechanism (a = 2) and the discrete Laplace mechanism for different e's, when the number of bits is limited to 500, 1000 and 1500 16 We can see that PPR performs better for larger c or smaller MSE, whereas the discrete Laplace mechanism performs better for smaller or larger MSE. The performance of discrete Laplace mechanism for smaller e is due to the truncation step which limits Z to (C),),, which reduces the error the expense of introducing distortion to the distribution of Z, and making Z biased estimate of X. In comparison, PPR preserves the Laplace conditional distribution /z| exactly, and hence produces unbiased Z.
16The MSE of PPR is computed using the closed-form formula in Corollary 6.1 which is tractable since Z follows the Laplace conditional distribution f2|x exactly. The number of bits used by PPR is given by the bound Corollary 6.1 The MSE of the discrete Laplace mechanism is estimated using 5000 trials per data point. Although we do not plot the error bars, the largest coefficient of variation of the sample mean (i.c., standard error of the mean divided by the sample mean) is only 17, which would be unnoticeable even if the error bars were plotted.
30

---

Metric privacy, dimension = 500
10a
PPR (500 bits)
Discrete Laplore (500 bits)
PPR (1000 bits)
Discrete Laplace (1000 bits)
(1500 bits)
Discrete Laplace
10a
MSE
10A
10 10
109
10
Privacy (e)
Figure 2: MSE of PPR-compressed Laplace mechanism and discrete Laplace mechanism different e's.
S for
K
Running Time of PPR
K.1
As discussed in Section 7 we ensure (d) running time for the Gaussian mechanism by using the sliced PPR, where the d-dimensional vector X is divided into [d [d/dehunk] chunks, each with fixed dimension dehunk (possibly except the last chunk if dehunk is not a factor of d). The average total running time is [d//chunk Tehunk where Tehunk is the average running time of PPR applied on chunk Therefore, to study the running time of the sliced PPR, study how T Tebunk depend dehunk-
chunk with dimension debunk where dehmnk ranges from 40 to 110 18 With d 1000, n = 500, & 0.05 and 5 10 we require Gaussian mechanism with noise N(0, n where 1.0917 each user in order to ensure (c, c)-centa DP. We record the mean Tehmak and the standard error the mear of the running time of PPR applied simulate this Gaussian mechanism (averaged over 20000 trials..
In Figure 3 we show the rumning time T Tchank of PPR applied
Note that the chunks may be processed in parallel for improved efficiency. Experiments were executed on MI Macbook, 8-core CPU (+= GHz) with 16GB memory. 19 standard error of the mean is given by Otime /raiiats where is the standard deviation
of the running time among the Altrials 20000 trials.
31

---

running time (seconds)
20-4
chunk dimension detunk
Figure 3: Average rumning time of PPR applied to chunk of dimension dehunk. with error bars indicating the interval Tehunk 20 mean. where Tehunk the sample mean the running time, and menn is the standard error of the mean (see Footnote 19
K.2
We plot the average rumning time (over 20000 trials for each data point) against the values of E [0.06, 10), with dehunk always chosen to be 4. The average running time denoted as Tehunk- and the standard error of the mean given by meean Orime/ /ntrialss where Otime is the standard deviation the running time among the time = 20000 trials.
20a
running time (seconds)
10-1
10
10-1
Figure 4: Average running time (over 20000 trials), dehank and [0.06, 10), with error bars indicating the interval Tehunk + meann where Tehunk is the sample mean the running time, and Twean is the standard error of the mean.
L MSE against Compression Size
We plot the MSE against the compression size (ranging from 25 1000 bits) for (0.25, 0.5, 1.0, 2.0} in the following figure.
32

---

0.25
0.5
1,20
C5GM
CSGM
0.373
PPR
PPR
MSE
MSE
0.330
1.15
0.325
1.10
0.300
10a
10P
com pression size
com compression size
1.0
2.0
CSGM
0.100
CSGM
0.150
PPR
PPR
0.075
MSE
MSE
0.125
0.050
0.025
10
103
compression size
compression size
Figure 5: The MSE of PPR and CSGM against the compression size in bits, where E chosen from (0.25, 0.5, 1.0, 2.0) and compression sizes vary from 25 to 1000 bits. Note that parts of the curves for PPR are flat, because a lower compression size is already sufficient for PPR to exactly simulate the best Gaussian mechanism for that value of so higher compression size than necessary will affect the result.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have clearly stated paper's contributions and scope in both the abstract and introduction. We try to answer the fundamental question: how can we efficiently com- municate privatized data? The main contribution is novel "DP mechanism compressor", whose main advantages: universality, exactness and communication efficiency, have been elaborated in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The main limitation of the proposed method is that it has running time exponential with respect to the mutual information, though this not an obstacle for simulating local DP mechanism (where the mutual information must be small). This is elaborated in Section 8 Note that there is no limitation on the type of DP mechanism that can be compressed by PPR (it can compress any DP mechanism to almost the theoretically smallest size). See Section for details.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
34

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theorems are precise mathematical statements, with all necessary assump- tions included in either the theorem statement or the definition of PPR. Complete proofs included in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The detailed pseudocode of the PPR method given in Algorithm T in the appendix, and the implementation together with the codes and data for Section 7 have been submitted in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
35

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided detailed implementations of Algorithm | and data for Figure (the main experimental result) the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
popllccgguies/. htt////ooosossioonnniooo ciiiiooooolyll for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips wttp::cccccpccgdddceeeeeeeeee/ee htlili/c/gudde//ooeeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have specified all the experiment details in Section 7
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
36

---

Justification: For the PPR applied on the Gaussian mechanism in Section 7 the mean squared error is obtained by a closed-form. formula, and the compression size is bounded using the expression in Theorem 4.3 Therefore, the plot about PPR in in Figure i precise. For the running time of sliced PPR, we have reported the standard error of the mean of the running time via error bars in Figure For the experiments on the Laplace mechanism in Appendix J the standard error the mean has been recorded for the estimation of the MSE of the discrete Laplace mechanism, and the largest coefficient of variation of the sample mean is reported, which is very small and would be unnoticeable even if the error bars were plotted.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided all the necessary information on the experiments in Section 7 including the computer and CPU information. Figure plotted according to closed-form formulas and hence can be immediately derived.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We confirm that the research conducted in this paper conforms with the NeurlPS Code of Ethics.
37

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: We believe research on privacy preservation generally has a positive societal impact, and research on reducing the communication cost of privacy mechanisms (such as this paper) is beneficial. Nevertheless, we have not addressed this in the paper, since we believe our theoretical results has no specific societal impact outside of the general impacts of privacy and reduced communication cost.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This piece of research is theoretical. We do not release any new dataset or pretrained model.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
38

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have appropriately mentioned and cited the paper whenever compare with it.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: This paper is mainly for theoretical research. We have provided the codes for our algorithm (implemented by Python) in the supplementary material, which is well documented. We do not release any new dataset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This piece of research does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
39

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This piece of research does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "pTeadveXQP", "reviewer": "Reviewer_NbQx", "summary": "The paper designs Poisson private representation (PPR) to compress and simulate any local randomizer while ensuring local differential privacy. PPR exactly preserves the joint distribution of the data and the output of the original local randomizer, and also achieves a compression size within a logarithmic gap from the theoretical lower bound. The authors also a provides an order-wise trade-off between communication, accuracy, central and local differential privacy for distributed mean estimation. Numerical experiments are conducted to validate theoretical justifications.", "questions": "Why does the privacy analysis in Corollary 5.1 not relate to n?", "limitations": "Limitations are clearly stated in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper designs a compressor that can simulate any local or central DP mechanism and enables exact simulation\n* The trade-off between communication, accuracy, and privacy for distributed mean estimation are analyzed\n* The paper is well-organized and easy to follow\n* The comparisons with previous results and the limitations of the proposed PPR are discussed", "weaknesses": "The privacy analysis in Corollary 5.2 is only suitable for cases where n, the number of local clients, is small. However, in practical scenarios such as federated learning, n is typically very large. An analysis that addresses privacy for large n would be appreciated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer NbQx for the constructive feedback. \nWe are pleased to hear Reviewer NbQx thought our manuscript is well-organized and easy to follow. \nBelow, we clarify the weakness and address the question pointed out by the reviewer \n\n\n**Regarding small $n$:** Firstly, as noted in footnote 6, the restriction $\\\\varepsilon < 1/\\\\sqrt{n}$ (which may require a smaller $n$) is due to the simpler privacy accountant [24]. A tighter result that applies to any $n$ can be obtained by considering Rényi DP instead, as discussed in Corollary G.3 in Appendix G. \n\nMoreover, in the context of federated learning or analytics, $n$ refers to the cohort size, which is the number of clients *in each round*. This cohort size is typically much smaller than the total number of available clients. For example, as observed in [Kairouz et al., 2019], the per-round cohort size in Google's FL application typically ranges from $10^3$ to $10^5$, which is significantly smaller than the number of trainable parameters $d \\\\in [10^6, 10^9]$ or the number of available users $N \\\\in [10^6, 10^8]$.\n\nFurthermore, even in the context of traditional, non-FL training with a DP-SGD-type optimizer, $n$ refers to the *batch* size rather than the total number of samples, where privacy can be amplified via random batching.\n\n**Regarding the reason for which Corollary 5.1 does not relate to $n$:** Note that Corollary 5.1 (and also PrivUnit) considers local DP instead of central DP (see Definition 4.1). Therefore, the privacy analysis and guarantees do not depend on the total number of clients $n$.\n\n\n**References**\n\n[Kairouz et. al, 2019] \"Advances and open problems in federated learning.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wwoOQGK2tj", "reviewer": "Reviewer_VD1w", "summary": "The paper investigates the problem of compressing the output of differentially private algorithms, particularly focusing on the local model. Given a Local Differential Privacy (LDP) algorithm $ A $ that induces a conditional distribution $ p_{Z \\mid X} $ where $ Z = A(X) $, the objective is to generate a message using minimum bits, allowing the server to recreate a random variable following the distribution $ p_{Z \\mid X} $.\n\nThe paper introduces a novel compression algorithm leveraging shared randomness between the server and clients. Key points include:\n1. The compression algorithm applies universally to every local randomized algorithm, provided there is agreement on the output space.\n2. The size of the compressed output matches the mutual information lower bound $ I(X; Z) $, with an additive logarithmic term.\n3. Using the compressed outputs, the server can reconstruct random variables that exactly follow the distributions of the outputs of the local randomizers of the clients.\n\nA central component of this approach is the Poison functional representation, a channel simulation scheme. Initially not differentially private, the paper extends it to ensure differential privacy using a technique akin to the exponential mechanism.\n\nExperimental results demonstrate improved performance of the proposed algorithm compared to previous approaches.", "questions": "1. On page 2, line 75, \"lower bound I(X;Y)\" - - > \"lower bound I(X;Z)\".\n\n2. In the experiment section, the paper only mentions the running time for $ \\epsilon = 0.05 $ (line 335). It would be informative to include the running time for larger values of $ \\epsilon $ experimented in the paper, such as $ \\epsilon = 10 $. Specifically, it would be useful to know how does the running time scale with $ \\epsilon $.", "limitations": "1.\t1. The running time of the compression algorithm is exponential in the mutual information $ I(X; Z) $. While this aspect is crucial, it is currently mentioned in the limitation section rather than explicitly in the main theorem describing the properties of the compression algorithm.\n\n2.\t2. The proposed compression algorithm does not strictly preserve the privacy guarantee of the Local Differential Privacy (LDP) algorithm. Instead, it can inflate the privacy guarantee by a constant factor: an $ \\epsilon $-LDP algorithm, after compression, might become $ 2\\alpha \\epsilon $-LDP, where $ \\alpha > 1 $. This trade-off is acceptable when focusing on the asymptotic privacy-utility trade-off of LDP algorithms. However, for LDP algorithms that achieve optimal errors with optimal constants, applying the compression algorithm may result in algorithms with suboptimal constants.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Viewing the problem of compressing the output of Local Differential Privacy (LDP) algorithms as a channel simulation problem is inspiring, as it allows leveraging insights and results from the extensive study of channel simulation.\n\n2. The proposed algorithm is versatile and applicable to a wide range of LDP algorithms, effectively reducing their communication costs to nearly optimal levels. It can serve as a fundamental primitive: LDP algorithm designers can focus on the privacy-utility trade-off without significant concerns about communication costs.", "weaknesses": "See ``Limitations''", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer VD1w for the constructive feedback. We are pleased to hear that Reviewer VD1w find the idea of viewing the compression of the output of LDP algorithms as channel simulation inspiring, and our technique can serve as a fundamental primitive to DP algorithm designers. Please find our responses to the questions and comments below. \n\n \n**Regarding running time for larger $\\\\varepsilon$:** We have discussed the running time of case $\\\\varepsilon = 0.05$ in the paper. \nWe report the running time for some larger values of $\\\\varepsilon$'s as follows: \nFor $\\\\varepsilon = 6$ (which is the largest $\\\\varepsilon$ that is plotted in Figure 1 of the original manuscript), we can choose $d_{\\\\mathrm{chunk}}=2$ in the sliced PPR to have an average running time $0.0127$ seconds or choose $d_{\\\\mathrm{chunk}}=4$ to have an average running time $0.6343$ seconds, where we calculate the running time by averaging over $10000$ trails; \nfor $\\\\varepsilon = 10$ (as suggested by the reviewer),  we can choose $d_{\\\\mathrm{chunk}}=2$ to have an average running time $0.0128$ seconds or choose $d_{\\\\mathrm{chunk}}=4$ to have an average running time $0.7301$ seconds. \nIt shows the running time are acceptable even for large values of $\\\\varepsilon$.  \nWe plot the average running time (over $10000$ trials for each data point) against the values of $\\\\varepsilon\\\\in [0.06, 10]$, with $d_{\\\\mathrm{chunk}}$ always chosen to be $4$, in Figure A in the submitted pdf file. \n\n**Regarding exponential running time:** We agree with the reviewer that we can discuss more about the running time in main sections. \nWe will move the paragraph ``the running time complexity (which depends on the number of samples $Z_i$ the algorithm must examine before outputting the index $K$) can be quite high. Since $\\\\mathbb{E}[\\\\log K] \\\\approx I(X;Z)$, $K$ (and hence the running time) is at least exponential in the mutual information $I(X;Z)$'' from the limitation section to after Theorem 4.3.\n\n**Regarding privacy guarantee:** For $\\\\varepsilon$-DP, PPR may inflate the privacy budget $\\\\varepsilon$ by a factor of $2 \\\\alpha$ as shown in Theorem 4.5 (though we can make it arbitrarily close to $2$). However, if we instead consider $(\\\\varepsilon, \\\\delta)$-DP with a small $\\\\delta$, then Theorem 4.8 shows that the privacy budget $\\\\varepsilon$ of the compressed mechanism can be arbitrarily close to the $\\\\varepsilon$ of the original mechanism.\n\nMoreover, we would like to note again that another advantage of our exact simulation scheme is that PPR enables having both local and central DP guarantees at the same time.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ek5K9n35H5", "reviewer": "Reviewer_U6Tv", "summary": "The paper addresses the problem of reducing the communication cost of messages that are shared under differential privacy (DP) guarantees. This is an important problem in privacy preserving machine learning, where parties that share obfuscated large models could incur in significant communication overhead.  \n\nTechniques to reduce communication exist, but they (a) require to share randomness between the encoder (i.e., the data subject that obfuscates its data) and a (possibly adversarial) analyst (or decoder), (b) resort into approximate and biased distribution estimations or (c) only work for specific distributions. \n\nThe current paper proposes a compression technique that (i) achieves optimal and lossless compression rates without significant degradation of DP-guarantees, (ii) only requires a small amount of public information to be shared between encoder and decoder and (iii) are universal as they can be used for any DP-mechanism.", "questions": "Can de authors address weaknesses raised in my review? \n\nEspecially, two aspects that would clarify the advantages of the work are:\n\n- The disadvantages of shared randomness between encoder and decoder, which in the paper is discussed in two different contexts: At the end page 2 of the paper, shared randomness appear to break privacy guarantees if the decoder is an adversary. Then, at the beginning of page 3 under the compression of local DP mechanisms, shared randomness is also discussed, but disadvantages here are not clear (see the related point in the weaknesses I described in my review). \n\n- From Figure 1, I can only see the advantages of PPR in permissive privacy regimes. However, distributed mean estimation is a canonical task that in machine learning is used under composition, leading to further privacy degradation. Therefore it is important to understand the properties of the protocol under more conservative regimes (e.g. $\\epsilon < 1/2$). Could PPR perform better with respect to CSGM with further compression (e.g., 25 bits or 10 bits) under such regimes?", "limitations": "I don't see additional limitations other than the discussed by the authors.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "In terms of novelty, the paper proposes an original idea that leverages the Poisson functional representation to avoid shared randomness between the encoder and decoder, allowing the use of the compression technique in the local DP setting. \n\nThe work is of good quality as\n- it appropriately backs its claims with proofs \n- provides an extensive analysis of the compression and privacy properties of the proposed technique.\n\nFirst, it shows that it achieves optimal compression (up to a logarithmic factor) which yields to compression rates that are similar to non-private techniques. Next, it provides DP bounds of the compression technique, characterizing the trade-offs between compression and privacy and showing that significant compression can be achieved with acceptable privacy degradation. Finally, it shows how these guarantees boil down to distributed mean estimation (DME) and metric privacy. \n\nA strong point on the impact of the contribution is the universality property, which allows the simulation of any distribution. This makes the technique widely applicable, unlike previous solutions that are tailored to specific problems.", "weaknesses": "The main drawback of the contribution is in the lack of a more detailed comparison with other previous techniques. While the proposed technique successfully positions itself with respect to related work, it is not clear how the advantages (universality, exact simulation, lack of shared randomness between encoder and decoder) lead to significant improvements in machine learning. \n\nAs said before, it is clear that universality is a potentially interesting property. However, it is not completely clear the disadvantage of shared randomness when these randomness does not break the privacy guarantee (as it seems to be the case in [5,30]). It seems that this shared randomness would imply a larger communication cost, but the final compromises between compression, accuracy and privacy are not clear. \n\nThe advantages of an exact simulation are also not illustrated. It might be the case that the degradation of accuracy (or privacy) of approximate solutions is not significant. Since these aspects are not more accurately illustrated, I am not sure about the actual advantages of the current technique. \n\nFinally, empirical illustrations don't to show more than a marginal advantage with respect to GSGM [18], which only apply in permissive privacy regimes (e.g. $\\epsilon > 1$). Therefore, these illustrations do not help to clarify the advantages of the current contribution in practice. \n\nA minor comment is the lack of a more complete presentation of Poisson functional representation, which could be expanded for clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer U6Tv for the constructive and detailed feedback. We are pleased to hear that Reviewer U6Tv appreciate the universality of our proposed method. Please find our responses to the comments below.\n\n**Shared randomness and privacy:** Whether shared randomness weakens or prevents privacy depends on the design of the mechanism. Indeed, the 1-bit protocol [5] guarantees privacy in the presence of shared randomness. [30] is slightly different since its privacy-utility trade-off depends on computational assumptions, which is not the case for our work (and most related works cited by us). In some other algorithms, shared randomness can be detrimental to privacy, and additional steps or assumptions are needed to alleviate this problem (e.g., [43] requires a trusted aggregator; [46] requires secure aggregation).\n\nNote that our proposed PPR algorithm also requires shared randomness (see Section 4; it will be made clearer in the revised version), though it is designed to ensure privacy even when the adversary can access both the shared randomness and the compressed data. All privacy analyses (Theorems 4.5-4.8) in the paper assume that the adversary knows both the message $K$ and the shared randomness $(Z_i)_i$.\n\nTo clarify, using shared randomness is not an advantage or a disadvantage by itself. It only becomes a disadvantage if it harms the privacy, which may happen in dithered quantization schemes (unless with additional steps and/or assumptions [43,46]), but does not happen in [5,30,65] or our PPR algorithm. The purpose of mentioning shared randomness in the introduction and related work section is to highlight the challenges in ensuring privacy in the presence of shared randomness, though we understand that it could give an impression that we are claiming shared randomness to be an advantage of the proposed algorithm, which is not our intention. This will be clarified in the revised version. The advantages of our algorithm are universality, exactness (comparing to [5,30] which are approximate) and communication efficiency. \n\n**The presentation of Poisson functional representation:** We will have a more detailed explanation of the Poisson functional representation in the revised version. \n\n\n**Advantages of exact simulation:** \nThe advantages of exact simulation (refer to the ``Exactness'' paragraph in page 2) are:\n\n1. Exact simulation does not introduce any bias in compression, and hence it guarantees unbiasedness for tasks such as distributed mean estimation (DME). \n\n2. For the Gaussian mechanism for DME, guaranteeing that the resultant local noise of the compression is exactly Gaussian will result in an overall noise that is Gaussian as well. This provides the central DP of the PPR-simulated Gaussian mechanism, in addition to (and with a better $\\\\varepsilon$ than) the local DP. Otherwise, only a much looser central DP can be provided, since when the local noise is not \"summable\", one must rely on generic privacy amplification techniques, e.g. shuffling [Erlingsson et al., 2019], which suffers from highly sub-optimal constants and are only meaningful for limited privacy regimes where $\\\\varepsilon_{local} \\\\ll 1$, making it less practical for most FL applications. \n\nThis highlights an important advantage of exactness. If the goal is only to design a stand-alone privacy mechanism, then we can study the privacy and utility of the mechanism, without studying the output distribution. However, if the output of the mechanism is used for downstream tasks (e.g., for DME, after receiving information from clients, the server sends information about the aggregated mean to data analysts, where central DP is crucial), having an exact characterization of the conditional distribution of the output given the input will allow us to obtain precise (central) privacy and utility guarantees. Otherwise, we must fall back to the worst-case guarantee (for DME, the central DP guarantee can only be the same as the local DP, which is far from optimal), or use a sub-optimal generic privacy amplification technique.\n\n**Advantages of PPR under more conservative regimes or with further compression:** The y-axis of Figure 1 is in logarithmic scale, which may make the MSE's look closer than they actually are. For example, when $\\\\varepsilon=1$ and we compress $d=1000$ to $50$ bits, CSGM has an MSE $0.1231$, while PPR has an MSE $0.08173$, giving a 33.61% reduction. For a case with further compression under more conservative $\\\\varepsilon$, for example, when $\\\\varepsilon=0.5$ and we compress $d=1000$ to $25$ bits, CSGM has an MSE $0.3877$, while PPR has an MSE $0.3011$, giving a 22.33% reduction. Such reductions are significant, considering that all considered mechanisms are asymptotically close to optimal, so a large improvement compared to an (almost optimal) mechanism is unexpected. We plot the MSE against the compression size (ranging from 25 to 1000 bits) for $\\\\varepsilon\\\\in \\\\{0.25, 0.5, 1.0, 2.0\\\\}$ in Figure B in the submitted pdf file.\n\nMoreover, we note again that PPR achieves a better trade-off between MSE and central DP than CSGM, while also giving local DP guarantees that CSGM cannot provide. Another advantage of PPR under more conservative regimes (small $\\\\varepsilon$) is that the trade-off between $\\\\varepsilon$ and MSE of PPR exactly coincides with the trade-off of the Gaussian mechanism for small $\\\\varepsilon$, as seen in Figure 1. In contrast, CSGM is close to (but strictly worse than) the Gaussian mechanism. This means that for small $\\\\varepsilon$, PPR provides compression without any drawback in terms of $\\\\varepsilon$-MSE trade-off compared to the Gaussian mechanism (which requires an infinite size communication to exactly realize). This advantage is a consequence of exact simulation. \n\n\n**References**\n\n[Erlingsson, Úlfar, et al.] ``Amplification by shuffling: From local to central differential privacy via anonymity,'' SODA 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "L6KNXQ1bkc", "reviewer": "Reviewer_GP8R", "summary": "A new technique for compressing local differential privacy (LDP) reports is presented, based on Poisson functional representations, a tool from information theory that allows encoding a random variable in close to information-theoretically minimum number of bits (expected) in a \"universal\" manner that does not require the decoder to know about the distribution of the random variable. The paper presents a generalization called Poisson *private* representations (PPR) that preserves DP guarantees up to a multiplicative factor and has similar encoding efficiency (with a trade-off controlled by a parameter 𝛼). Unlike previous LDP compression techniques, PPR result in exactly the same distribution of decoded values as the original, uncompressed LDP protocol, so it preserves properties such as unbiasedness. The utility of PPR is investigated in a couple of case studies: distributed mean estimation and metric privacy.", "questions": "* Is it correctly understood that your method is private even to an adversary who knows the shared randomness?\n* Is there any way that clients can use the same shared randomness, or should this by per-client?\n* In line 166 it is not clear that argmin is well-defined, can you comment on this?\n* Can you achieve a bound on the worst-case encoding size, say, by reverting to a simpler encoding if K is too large?", "limitations": "The authors have adequately addressed limitations", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Originality: Interesting techniques from information theory that have not, to my knowledge, been used in differential privacy or federated learning before\n* Quality and clarity: The paper is very well-written (but also dense and assumes a lot from the reader).\n* Significance: A little hard to gauge, but the generality of the methods suggest that they may be of interest in many settings. The \"universality\" is particularly striking and may have important applications.", "weaknesses": "* I found the paper hard to read, in part because it uses math that I was not familiar with, in part because many details are hidden away in the appendices. Possibly, a more self-contained and accessible version could be achieved by focusing the exposition on a special case (e.g. simulating privUnit), and leaving the generalization for the appendices.\n* It is assumed that each client and the server share a common, random sequence. While this might be realized using a pseudorandom generator, communicating a short seed, this overhead may be significant in practice. (This weakness, it should be mentioned, is shared with several previous methods.)\n* PPR yields an overhead of more than a factor 2 in the privacy parameter\n* The running time is exponential in 𝜺 which may limit applications to the shuffle model, where amplification means that high values of epsilon may be used", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer GP8R for the constructive feedback. \nWe are pleased to hear Reviewer GP8R thought our PPR technique is interesting and the paper is very well-written. \nPlease find our responses to the questions and comments below.\n\n**Regarding a more self-contained and accessible version on a special case:** In the revised manuscript, we will explain the PPR algorithm using the Gaussian mechanism as an example, which will hopefully make the exposition more accessible.\n\n\n**Regarding the common random sequence:** In practice, the common random sequence is generated using a pseudorandom number generator (PRNG) initialized with a seed shared between the client and the server. While this seed must be communicated between the client and the server, and may lead to an increased communication cost, note that the client and the server only ever need to communicate one seed, which will be used to initialize a PRNG that will be used in all subsequent privacy mechanisms and communication tasks. This is similar to running a large-scale randomized simulation program on a computer, where we only need to initialize the random seed once when the simulation starts.\n\nPractically, the client and the server will share the seed when the connection is established as a small overhead, and can use the same PRNG throughout the whole connection. If the client is applying DP mechanisms to transmit a high-dimensional data, or is using DP mechanisms many times, the cost of communicating the seed will only contribute a small fraction of the total communication cost. On the other hand, if the client is only applying DP mechanisms a small number of times on some small data, then the cost of communicating the seed will be dominated by the overhead in TCP/IP handshaking. In any case, the cost of communicating the seed is insignificant.\n\n\n **Regarding running time for larger $\\\\varepsilon$:** We have discussed the running time of case $\\\\varepsilon = 0.05$ in the paper. \nWe report the running time for some larger values of $\\\\varepsilon$'s as follows: \nFor $\\\\varepsilon = 6$ (which is the largest $\\\\varepsilon$ that is plotted in Figure 1), we can choose $d_{\\\\mathrm{chunk}}=2$ in the sliced PPR to have an average running time $0.0127$ seconds or choose $d_{\\\\mathrm{chunk}}=4$ to have an average running time $0.6343$ seconds, where we calculate the running time by averaging over $10000$ trails. \nFor $\\\\varepsilon = 10$ (as suggested by the reviewer),  we can choose $d_{\\\\mathrm{chunk}}=2$ to have an average running time $0.0128$ seconds or choose $d_{\\\\mathrm{chunk}}=4$ to have an average running time $0.7301$ seconds. \nWe plot the average running time (over $10000$ trials for each data point) against $\\\\varepsilon\\\\in [0.06, 10]$, with $d_{\\\\mathrm{chunk}}$ fixed to $4$. \nPlease refer to Figure A in the attached pdf file, where we record the mean $T_{chunk}$ and the standard error of the mean. \nThe standard error of the mean is given by $\\\\sigma_{\\\\mathrm{mean}} = \\\\sigma_{\\\\mathrm{time}} / \\\\sqrt{n_{\\\\mathrm{trials}}}$, where $\\\\sigma_{\\\\mathrm{time}}$ is the standard deviation of the running time among the $n_{\\\\mathrm{trials}}=10000$ trials.\n\n\n**Regarding the overhead in the privacy parameter:** For $\\\\varepsilon$-DP, PPR may inflate the privacy budget $\\\\varepsilon$ by a factor of $2 \\\\alpha$ as shown in Theorem 4.5 (though we can make it arbitrarily close to $2$). However, if we instead consider $(\\\\varepsilon, \\\\delta)$-DP with a small $\\\\delta$, then Theorem 4.8 shows that the privacy budget $\\\\varepsilon$ of the compressed mechanism can be arbitrarily close to the $\\\\varepsilon$ of the original mechanism. \n\n\n**Regarding exponential running time:** We agree with the reviewer that we can discuss more about the running time in main sections. \nWe will move the paragraph \"the running time complexity (which depends on the number of samples $Z_i$ the algorithm must examine before outputting the index $K$) can be quite high. Since $\\\\mathbb{E}[\\\\log K] \\\\approx I(X;Z)$, $K$ (and hence the running time) is at least exponential in the mutual information $I(X;Z)$\" from the limitation section to after Theorem 4.3.\n\n\n**Regarding shared randomness and privacy:** All privacy analyses in the paper assumes that the adversary knows both the message $K$ and the shared randomness $(Z_i)_i$. The trade-off between communication cost and privacy are described in Theorem 4.3 and Theorems 4.5-4.8. \n\n\n**Regarding clients using the same shared randomness:** It is assumed that each client uses a different independent shared randomness. Otherwise, we can no longer ensure that the privacy-preserving noises at the clients are independent. Nevertheless, as mentioned earlier in this response, the cost of generating these shared randomness is insignificant. We will clarify this in the revised manuscript.\n\n\n**Regarding the argmin in line 166:** Since the $T_i$'s are continuous random variables, with probability one, there do not exist two equal values among $\\\\tilde{T}_i$'s. This will be clarified in the revised manuscript.\n\n\n**Regarding worst-case encoding size:** We can apply Markov inequality $\\\\mathrm{Pr}(\\\\log K > L) \\\\le \\\\mathrm{E}[\\\\log K] / L$ on the bound in Theorem 4.3 to show that $\\\\log K$ is most likely small. If the worst-case encoding length must be controlled, i.e., $\\\\log K \\\\le L$, we can modify the method to have the encoder output $0$ instead if the $K$ given by PPR exceeds $2^L$. After this modification, the method may not be exact, though the error probability is bounded by $\\\\mathrm{Pr}(\\\\log K > L)$, which is small due to Markov inequality and the bound in Theorem 4.3. We will explain this in the revised paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers and ACs,

We would like to thank all the reviewers for carefully reviewing our paper, their patience and also their valuable and constructive feedback. 
We observed that the feedback from all four reviewers is generally positive. 
Most reviewers mentioned the novelty of introducing a variant of the Poisson functional representation (as an elegant channel simulation technique) to compressing differentially private algorithms, our theoretic contributions with experimental validation and our organized structure among the strengths of our work. 

The reviewers also shared suggestions that are valuable to improve our manuscript's quality. 
We have responded to every question in our separate responses to each reviewer. 
We also found that some concerns are common and mentioned by multiple reviewers, including the inflated privacy guarantee, the shared randomness, the running time and the advantage of exact simulation. 
Hence we briefly summarize our replies to them here for a general clarification. 
More details can be found in separate responses to each reviewer. 

**Regarding shared randomness:** 
All our privacy analyses assumes that the adversary knows both the message and the shared randomness. 
In practice, shared randomness does not require a large communication cost. 
The client and the server can communicate a small random seed to initialize the pseudorandom number generator (PRNG) that produces all the shared randomness needed. 
Note that the client-server pair only ever need to communicate one seed for all subsequent privacy mechanisms and communication tasks.
In practice, the cost of communicating the seed is insignificant compared to both the cost of transmitting the compressed data (e.g., the $K$ in the proposed method), and the overhead of initializing the connection (e.g., TCP/IP handshaking).

**Regarding privacy guarantee:** 
For $\\varepsilon$-DP, the PPR may inflate the privacy budget $\\varepsilon$ by a factor of $2 \\alpha$ (that can be arbitrarily close to $2$). However, we can instead consider $(\\varepsilon, \\delta)$-DP with a small $\\delta$, and Theorem 4.8 guarantees that the privacy budget $\\varepsilon$ of the compressed mechanism can be arbitrarily close to the $\\varepsilon$ of the original mechanism (i.e., almost no inflation). 
We would like to note again that another advantage of PPR is the exact simulation, with advantages elaborated as follows. 

**Regarding the exact simulation:** 
Exact simulation (where the compression does not introduce any bias) enables us to guarantee 1) unbiasedness for tasks such as distributed mean estimation, where unbiasedness is crucial; 2) for the Gaussian mechanism for distributed mean estimation, the resultant local compression noise is exactly Gaussian, giving an overall noise that is also Gaussian so that we have both central DP and local DP. 
Otherwise, without exact simulation we can only rely on generic privacy amplification techniques, such as shuffling [Erlingsson et al., 2019] (known to suffer from highly sub-optimal constants and only meaningful for limited privacy regimes where $\\varepsilon_{local} \\ll 1$), giving a much looser central DP. 
Please see more discussions in our separate responses. 

**Regarding exponential running time for larger $\\varepsilon$:** 
We have discussed the running time of case $\\varepsilon = 0.05$ in the paper. 
We report the running time (averaging over $10000$ trails) for some larger $\\varepsilon$'s: 
For $\\varepsilon = 6$, by using sliced PPR with $d_{\\mathrm{chunk}}=2$ we have an average running time $0.0127$ seconds and with $d_{\\mathrm{chunk}}=4$ we have an average running time $0.6343$ seconds; 
for $\\varepsilon = 10$, with $d_{\\mathrm{chunk}}=2$ the average running time are $0.0128$ seconds and with $d_{\\mathrm{chunk}}=4$ the average running time are $0.7301$ seconds. 
More data on average running time against $\\varepsilon\\in [0.06, 10]$ with $d_{\\mathrm{chunk}}=4$ are plotted in Figure A in the submitted pdf file. 

In conclusion, we believe the reviews for our contributions are overall positive. 
We sincerely hope that we have adequately addressed the reviewers' concerns and questions. 
We have also submitted another file in pdf format to share additional figures. 
Any further feedback and discussion is gladly welcomed. 
If our rebuttal effectively addresses the reviewers' concerns, we kindly invite them to consider updating their scores. Thank you very much for your time and feedback. 

**References**

[Erlingsson, Úlfar, et al.] "Amplification by shuffling: From local to central differential privacy via anonymity," SODA 2019.

Meta-review: This submission provides a new method for compressing local differential private reports. It is based on Poisson functional representations, a tool from information theory that allows encoding a random variable in close to the information theoretic minimum expected number of bits in a universal manner that does not require the decoder to know the probability distribution of the random variable.
The paper presents a generalization called Poisson Private Representations (PPR) that preserves the differential privacy guarantee up to a multiplicative factor, and has similar encoding efficiency. Unlike previous local differential privacy compression techniques, PPR result in exactly the same distribution of decoded values as the original uncompressed local differentially private protocol, so it preserves properties such as unbiasedness. The paper investigates the utility of PPR in a couple of settings including metric privacy and distributed mean estimation.

There is agreement among the reviewers that the paper should be accepted. The authors are expected to implement in the final version the changes that were promised in the rebuttal.

Moreover, in the AC-reviewers discussion, the following point came up:

The authors seem to be missing part of the literature on shuffle DP. Specifically, the rebuttal said:

"without exact simulation we can only rely on generic privacy amplification techniques, such as shuffling [Erlingsson et al., 2019] (known to suffer from highly sub-optimal constants and only meaningful for limited privacy regimes where epsilon_local << 1), giving a much looser central DP."

This is incorrect the literature following up on Erlingsson et al., 2019 managed to get much tighter bounds that work for epsilon_local >> 1. In particular, please see the paper of Feldman et al. (FOCS 2021): https://vtaly.net/papers/FMT-Clones-0921.pdf

The authors should clarify this in the final version.
Decision: Accept (poster)