Universal Exact Compression of Differentially Private Mechanisms

Authors: yanxiao  liu
wei-ning  chen
ayfer  özgür
ting  cheuk
  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:04:11

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.

Main paper: 
 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, or messages hosted by social networks). However, this data inherently contains personal information, making it susceptible to privacy breaches during acquisition, collection, or 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 a risk where malicious users, even with just API access, can extract substantial portions of sensitive information [14, 15] . In recent years, differential privacy (DP) [28] has emerged as a 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 a bottleneck in the system pipeline, especially with high-dimensional data common in many machine learning scenarios. This leads to the following fundamental question: how can we efficiently communicate privatized data?Recent works have shown that a wide range of differential privacy mechanisms can be "simulated" and "compressed" using shared randomness, resulting in a "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, 49, 80] with each approach having its own advantages and disadvantages. For example, importance-sampling-based methods [71, 78] and the rejection-sampling-based method [31] 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 be unbiased or to 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, ditheredquantization-based approaches [48, 56, 72, 46, 49, 80] can ensure a 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 an additional secure aggregation step [49] , or restrict attention to specific privacy mechanisms (e.g., one-dimensional Laplace [72] ).In this paper, we introduce a 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. 1 We elaborate on three main advantages of PPR, namely universality, exactness and communication efficiency.Universality. Unlike dithered-quantization-based 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.Exactness. Unlike previous DP mechanism compressors such as Feldman and Talwar [31] , Shah et al. [71] , Triastcyn et al. [78] , 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. If 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 are performed (only possible for certain DP mechanisms [71] ). Secondly, when the goal is to compute the mean (e.g., for private mean or 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 shuffling [30, 32] . PPR can compress a central DP mechanism (e.g., the Gaussian mechanism [27] ) and simultaneously achieve weaker local DP (i.e., with a larger ε local ) and stronger central DP (i.e., with a smaller ε central ), 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 I(X; Z) + log(I(X; Z) + 1) + O(1), with only a logarithmic gap from the mutual information lower bound I(X; Z). 2 The "O(1)" constant can be given explicitly in terms of a tunable parameter α > 1 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 [61, 60] , which provides precise control over the reconstructed joint distribution in channel simulation problems [6, 45, 61, 35, 41, 10, 7, 21] . Channel simulation aims to achieve the minimum communication for simulating a channel (i.e., 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 to 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 a private local message to its representation. Hence, PPR achieves order-wise trade-offs between privacy, communication, and accuracy, while preserving the original distribution of local randomizers.Notations. Entropy H(X), mutual information I(X; Y ), KL divergence D(P ∥Q) and logarithm are to the same base, e.g., they can be all in bits (base 2), or all in nats (base e). For P, Q, dP (•)/dQ denotes the Radon-Nikodym derivative. 
related work: 
 Generic compression of local DP mechanisms. In this work, we consider both central DP [28] and local DP [79, 53] . Recent research has explored methods for compressing local DP randomizers when shared randomness is involved. For instance, when ε ≤ 1, Bassily and Smith [5] demonstrated that a 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 a ε-DP mechanism into a 10ε-DP mechanism. Feldman and Talwar [31] proposed a distributed simulation approach using rejection sampling with shared randomness, while Shah et al. [71] , Triastcyn et al. [78] utilized importance sampling (or more specifically, minimum random coding [20, 74, 47] ). However, all these methods only approximate the original local DP mechanism, unlike our 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 [24, 8, 23, 4] , communication [40, 11, 75] , or both constraints [18, 31, 71, 43, 17, 19 ]. Among them, Asi et al. [4] has demonstrated that the optimal unbiased mean estimation scheme under local differential privacy is privUnit [8] . Subsequently, communication-efficient mechanisms introduced by Feldman and Talwar [31] , Shah et al. [71] , Isik et al. [51] aimed to construct communication-efficient 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.Distributed channel simulation. Our approach relies on the notion of channel simulation [6, 45, 61, 35, 41, 10, 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 P Z|X (a specific conditional distribution). By Harsha et al. [45] , Li and El Gamal [61] , the average communication cost is I(X; Z) + O(log(I(X; Z))). In [45] , algorithms based on rejection sampling are proposed, and it is further generalized in [39] 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 in [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 [71] .Poisson functional representation. The Poisson functional representation is a 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 on unequal message protection [54] , hypothesis testing [44] , information 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 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] .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 a running time exponential with respect to the mutual information, though this is 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 8 for details. Guidelines:• The answer NA means that the paper has no 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 a 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 on the scope of the claims made, e.g., if the approach was 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 We begin by reviewing the formal definitions of differential privacy (DP). We consider two models of DP data analysis. In the central model, introduced in Dwork et al. [28] , the data of the individuals is stored in a database X ∈ X by the server. The server is then trusted to perform data analysis whose output Z = A(X) ∈ Z (where A is a 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 ′ ∈ X are neighboring if they differ in a single data point. More generally, we can consider a symmetric neighbor relation N ⊆ X 2 , 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 to the server, meaning that individuals are not required to trust the server. A local DP mechanism [53] is a local randomizer A that maps the local data X ∈ X to the output Z = A(X) ∈ Z. Note that here X is the data at one user, unlike central-DP where X is the database with the data of all users. We now review the notion of (ε, δ)-central and local DP. Definition 3.1 (Differential privacy [28, 53] ). Given a mechanism A which induces the conditional distribution P Z|X of Z = A(X), we say that it satisfies (ε, δ)-DP if for any neighboring (x, x ′ ) ∈ N and S ⊆ Z, it holds thatPr(Z ∈ S | X = x) ≤ e ε Pr(Z ∈ S | X = x ′ ) + δ.In particular, if N = X 2 , we say that the mechanism satisfies (ε, δ)-local DP [53] . 3When a mechanism satisfies (ε, 0)-central/local DP, we will refer to it simply as ε-central/local DP. ε-DP can be generalized to metric privacy by considering a metric d X (x, x ′ ) over X [16, 3] . [16, 3] ). Given a mechanism A with conditional distribution P Z|X , and a metric d X over X , we say that A satisfies ε • d X -privacy if for any x, x ′ ∈ X , S ⊆ Z, we haveDefinition 3.2 (ε • d X -privacyPr(Z ∈ S | X = x) ≤ e ε•d X (x,x ′ ) Pr(Z ∈ S | X = x ′ ).This recovers the original ε-central DP by considering d X to be the Hamming distance among databases, and recovers the original ε-local DP by considering d X to be the discrete metric [16] .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 a conditional distribution P Z|X ) can be either a central or local DP mechanism, and the neighbor relation N 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 in central DP, or the server in local DP.(Z i ) i , K, outputs Z = Z K .Note that when α = ∞, we have K = argmin i Ti , and PPR reduces to the original Poisson functional representation [61, 60] . PPR can simulate the privacy mechanism P Z|X precisely, as shown in the following proposition. The proof is in Appendix A. Proposition 4.2. The output Z of PPR follows the conditional distribution P Z|X 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 is universal in the sense that only the encoder needs to know the simulated mechanism P Z|X . The decoder can decode the index K as long as it has access to the shared randomness (Z i ) i . This allows the encoder to choose an arbitrary mechanism P Z|X with the same Z, and adapt the choice of P Z|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 ( Ti ) i . We can truncate the method and only compute Ti , . . . , TN for a large N and select K ∈ {1, . . . , N }, which incurs a small distortion in the distribution of Z. 7 While this method is practically acceptable, it might defeat 5 The original Poisson functional representation [61, 60] uses the whole (Zi, Ti)i as the shared randomness. It is clear that (Ti)i is not needed by the decoder, and hence we can use only (Zi)i as the shared randomness. 6 We note that our analyses assume that the adversary knows both the index K and the shared randomness (Zi)i, and we 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. 7 To compare to the minimal random coding (MRC) [47, 20, 74] scheme in [71] , which also utilizes a finite number N of samples (Zi)i=1,...,N , while truncating the number of samples to N in both PPR and MRC the purpose of having an exact algorithm that ensures the correct conditional distribution P Z|X . In Appendix B, we will present an exact algorithm for PPR that terminates in a finite amount of time, using a reparametrization that allows the encoder to know when the optimal point Z i has already been encountered (see Algorithm 1 in Appendix B).By the lower bound for channel simulation [6, 61] , we must have H(K) ≥ I(X; Z), i.e., the compression size is 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 F. Theorem 4.3 (Compression size of PPR). For PPR with parameter α > 1, when the encoder is given the input x, the message K given by PPR satisfiesE[log K] ≤ D(P ∥Q) + (log(3.56))/ min{(α -1)/2, 1},where P := P Z|X (•|x). As a result, when the input X ∼ P X is random, taking Q = P Z , we haveE[log K] ≤ I(X; Z) + (log(3.56))/ min{(α -1)/2, 1}.Note 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 E[log K] ≈ I(X; Z), K (and hence the running time) is at least exponential in I(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 log 2 K. For example, if Elias delta code [29] is used, the expected compression size is [61] ). Both codes yield an I(X; Z)+O(log I(X; Z)) size, within a logarithmic gap from the lower bound I(X; Z). This is similar to some other channel simulation schemes such as [45, 10, 61] , though these schemes do not provide privacy guarantees.≤ E[log 2 K] + 2 log 2 (E[log 2 K] + 1) + 1 bits. If the Shannon code [73] (an almost-optimal prefix-free code) for the Zipf distribution p(k) ∝ k -λ with λ = 1 + 1/E[log 2 K] is used, the expected compression size is ≤ E[log 2 K]+log 2 (E[log 2 K]+1)+2 bits (seeNote that if P Z|X is ε-DP, then by definition, for any z ∈ Z and x, x 0 ∈ X , it holds thatD P Z|X=x P Z|X=x0 = E Z∼P Z|X=x log dP Z|X=x dP Z|X=x0 (Z) ≤ ε log e.Setting the proposal distribution Q = P Z|X=x0 for an arbitrary x 0 ∈ X gives the following bound. Corollary 4.4 (Compression size under ε-LDP). Let P Z|X satisfy ε-differential privacy. Let x 0 ∈ X and Q = P Z|X=x0 . Then for PPR with parameter α > 1, the expected compression size is at most ℓ + log 2 (ℓ + 1) + 2 bits, where ℓ := ε log 2 e + (log 2 (3.56))/min {(α -1)/2, 1}.Next, we analyze the privacy guarantee of PPR. The PPR method induces a conditional distribution P (Zi)i,K|X of the knowledge of the decoder ((Z i ) i , K), given the data X. To analyze the privacy guarantee, we study whether the randomized mapping 8 This is similar to the privacy condition in [71] , 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 [72] (which is simply the privacy of the original mechanism P Z|X to be compressed since PPR simulates P Z|X precisely). Since the decoder knows ((Z i ) i , K), more than just the final output Z, we expect that the PPR-compressed mechanism P (Zi)i,K|X to have a worse privacy guarantee than the original mechanism P Z|X , which is the price of having a smaller communication cost. The following result shows that, if the original mechanism P Z|X is ε-DP, then the PPR-compressed mechanism is guaranteed to be 2αε-DP.P (Zi)i,K|X from X to ((Z i ) i , K) satisfies ε-DP or (ε, δ)-DP.results in a distortion in the distribution of Z that tends to 0 as N → ∞, 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 → ∞ in PPR. The size N in truncated PPR merely controls the tradeoff between accuracy of the distribution of Z and the running time of the algorithm.Theorem 4.5 (ε-DP of PPR). If the mechanism P Z|X is ε-differentially private, then PPR P (Zi)i,K|X with parameter α > 1 is 2αε-differentially private.Similar results also apply to (ε, δ)-DP and metric DP. Theorem 4.6 ((ε, δ)-DP of PPR). If the mechanism P Z|X is (ε, δ)-differentially private, then PPR P (Zi)i,K|X with parameter α > 1 is (2αε, 2δ)-differentially private. Theorem 4.7 (Metric privacy of PPR). If the mechanism P Z|X satisfies ε • d X -privacy, then PPR P (Zi)i,K|X with parameter α > 1 satisfies 2αε • d X -privacy.Refer to Appendices C and D for the proofs. In Theorem 4.5 and Theorem 4.6, PPR imposes a multiplicative penalty 2α on the privacy parameter ε. This penalty can be made arbitrarily close to 2 by taking α close to 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, 71] , the 2α 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 (ε, δ)-differential privacy, and allow a small failure probability, i.e., a small increase in δ. The following result shows that PPR can compress any ε-DP mechanism into a (≈ ε, ≈ 0)-DP mechanism as long as α is close enough to 1 (i.e., almost no inflation). More generally, PPR can compress an (ε, δ)-DP mechanism into an(≈ ε, ≈ 2δ)-DP mechanism for α close to 1. The proof is in Appendix E. Theorem 4.8 (Tighter (ε, δ)-DP of PPR). If the mechanism P Z|X is (ε, δ)-differentially private, then PPR P (Zi)i,K|X with parameter α > 1 is (αε + ε, 2(δ + δ))-differentially private, for every ε ∈ (0, 1] and δ ∈ (0, 1/3] that satisfy α ≤ e -4.2 δ ε2 /(-ln δ) + 1.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 assumptions included in either the theorem statement or the definition of PPR. Complete proofs are 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
poisson private representation: 
 Definition 4.1 (Poisson functional representation [61, 60] ). Let (T i ) i be a Poisson process with rate 1 [57] , where λ [0,∞) is the Lebesgue measure over [0, ∞). Fix any distribution P over Z that is absolutely continuous with respect to Q. Let(i.e., T 1 , T 2 -T 1 , T 3 -T 2 , . . . iid ∼ Exp(1)), independent of Z i iid ∼ Q for i = 1, 2, . . .. Then (Z i , T i ) i is a Poisson process with intensity measure Q × λ [0,∞)EQUATIONThen (Z i , Ti ) is a Poisson process with intensity measure P × λ [0,∞) , which is from the mapping theorem [57] . The Poisson functional representation (PFR) [61, 60] selects the point Z = Z K with the smallest associated TK , i.e., let K := argmin i Ti and Z := Z K . 4The PFR selects a sample following the target distribution P using another distribution Q. It draws a random sequence (Z i ) i from Q and a sequence of times (T i ) i according to a Poisson process. If we select the sample Z i with the smallest T i , then the selected sample follows Q. To obtain a sample from P instead, we multiply the time by the factor ( dP dQ (Z i )) -1 in (1) to give Ti , so the Z i with the smallest Ti will follow P .The Poisson functional representation guarantees that Z ∼ P [61] . To simulate a DP mechanism with a conditional distribution P Z|X using the Poisson functional representation, we can use (Z i ) i as the shared randomness between the encoder and the decoder. 5 Upon observing X, the encoder generates the Poisson process (T i ) i , computes Ti and K using P = P Z|X , and transmits K to the decoder. The decoder simply outputs Z K , which follows the conditional distribution P Z|X . The issue is that K is a function of X and the shared randomness (Z i , T i ) i , and a 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 a generalization of the Poisson functional representation, which we call Poisson private representation (PPR) with parameter α ∈ (1, ∞], proposal distribution Q and the simulated mechanism P Z|X . Both X and Z can be discrete or continuous, though as a regularity condition, we require P Z|X (•|X) to be absolutely continuous with respect to Q almost surely. The PPR-compressed mechanism is given as:1. We use (Z i ) i=1,2,... , Z i iid ∼ 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 i iid ∼ Q from it using a pseudorandom number generator. 6 2. The encoder knows (Z i ) i , X, P Z|X and performs the following steps:(a) Generates the Poisson process(T i ) i with rate 1. (b) Computes Ti := T i • ( dP dQ (Z i )) -1, whereP := P Z|X (•|X). Take Ti = ∞ if dP dQ (Z i ) = 0. (c) Generates K ∈ Z + using local randomness with Pr(K = k) = T -α k ∞ i=1 T -α i .(d) Compress K (e.g., using Elias delta coding [29] ) and sends K.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: The detailed pseudocode of the PPR method is given in Algorithm 1 in the appendix, and the implementation together with the codes and data for Section 7 have been submitted in the supplementary material. 
applications to distributed mean estimation: 
 We demonstrate the efficacy of PPR by applying it to distributed mean estimation (DME) [75] . Note that private DME is the core sub-routine in various private and federated optimization algorithms, such as DP-SGD [1] or DP-FedAvg [67] .Consider the following general distributed setting: each of n clients holds a local data point X i ∈ X , and a central server aims to estimate a function of all local data µ (X n ), subject to privacy and local communication constraints. To this end, each client i compresses X i into a message Z i ∈ Z n via a local encoder, and we require that each Z i can be encoded into a bit string with an expected length of at most b bits. Upon receiving Z n := (Z 1 , . . . , Z n ), the central server decodes it and outputs a DP estimate μ. Two DP criteria can be considered: the (ε, δ)-central DP of the randomized mapping from X n to μ, and the (ε, δ)-local DP of the randomized mapping from X i to Z i for each client i. [8, 4] 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 P be the density defined by ε-privUnit 2 Bhowmick et al. [8, Algorithm 1] . Let Q be the uniform density over the sphere S d-1 (1/m) where the radius 1/m is defined in Bhowmick et al. [8, (15) ]. Let r * := e ε . Then the outcome of PPR (see Algorithm 1) satisfies (1) 2αε-local DP; and (2) (αε + ε, 2 δ)-DP for any α ≤ e -4.2 δ ε2 / log(1/ δ) + 1. In addition, the average compression size is at most ℓ+log 2 (ℓ+1)+2 bits where ℓ := ε+(log 2 (3.56))/ min{(α-1)/2, 1}. Moreover, PPR achieves the same MSE as ε-privUnit 2 , which is O d/ min ε, ε 2 .In the distributed L 2 mean estimation problem, X = B d (C) := v ∈ R d ∥v∥ 2 ≤ C ,) := 1 n n i=1 X i by minimizing the mean squared error (MSE) E[∥µ -μ∥ 2 2 ]. It is recently proved that under ε-local DP, privUnitNote that PPR can simulate arbitrary local DP mechanisms. However, we present only the result of privUnit 2 because it achieves the optimal privacy-accuracy trade-off. Besides simulating local DP mechanisms, PPR can also compress central DP mechanisms while still preserving some (albeit weaker) local guarantees. We give a corollary of Theorems 4.3 and 4.6. The proof is in Appendix H. . For each client i, let Z i be the output of PPR applied on P Z|X (•|X i ). We have:• μ(Z n ) := 1 n i Z i yields an unbiased estimator of µ(X n ) = 1 n n i=1 X i satisfying (ε, δ)- central DP and has MSE E[∥µ -μ∥ 2 2 ] = σ 2 d/n 2 . • As long as ε < 1/ √ n, PPR satisfies (2α √ nε, 2δ)-local DP. 9• The average per-client communication cost is at most ℓ + log 2 (ℓ + 1) + 2 bits whereℓ := d 2 log 2 C 2 n dσ 2 + 1 + η α ≤ d 2 log 2 nε 2 2d ln(1.25/δ) + 1 + η α ,where η α := (log 2 (3.56))/ min{(α -1)/2, 1}.A few remarks are in order. First, notice that when α is fixed, for an O(C 2 d n 2 ε 2 log(1/δ)) MSE, the per-client communication cost is O d log nε 2 d log(1/δ) + 1 + 1 ,which is at least as good as the O(nε 2 / log(1/δ) + 1) bound in [75, 19] , and can be better than O(nε 2 / log(1/δ) + 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 sparsification, projection, or minimum random coding (e.g., Triastcyn et al. [78] , Chen et al. [19] ) are lossy, i.e., they introduce additional distortion on top of the DP noise. Finally, other DP mechanism compressors tailored to local randomizers [31, 71] do not provide the same level of central DP guarantees when applied to local Gaussian noise since the reconstructed noise is no longer Gaussian. Refer to Section 7 for experiments. 
applications to metric privacy: 
 Metric privacy [16, 3] (see Definition 3.2) allows users to send privatized version Z ∈ R d of their data vectors X ∈ R d to an untrusted server, so that the server can know X approximately but not exactly. A popular mechanism is the Laplace mechanism [16, 3, 33, 34] , where a d-dimensional Laplace noise is added to X. The conditional density function of Z given X is f Z|X (z|x) ∝ e -εd X (x,z) , where ε is the privacy parameter, and the metric d X (x, z) = ∥x -z∥ 2 is the Euclidean distance. The Laplace mechanism achieves ε • d X -privacy, and has been used, for example, in geo-indistinguishability to privatize the users' locations [3] , and to privatize high-dimensional word embedding vectors [33, 34] .A problem is that the real vector Z cannot be encoded into finitely many bits. To this end, [3] 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 an alternative compression method that preserves the statistical behavior of Z (e.g., unbiasedness) exactly. We give a corollary of Theorems 4.3 and 4.7.The proof is in Appendix I. Refer to Appendix J for an experiment on metric privacy. Corollary 6.1 (PPR-compressed Laplace mechanism). Consider PPR applied to the Laplace mechanismP Z|X where X ∈ B d (C) = {x ∈ R d | ∥x∥ 2 ≤ C}, with a proposal distribution Q = N (0, ( C 2 d + d+1 ε 2 )I d ). It achieves an MSE d(d+1) ε 2 , a 2αϵ • d X -privacy, and a compression size at most ℓ + log 2 (ℓ + 1) + 2 bits, whereℓ := d 2 log 2 2 e C 2 ε 2 d + d + 1 -log 2 Γ(d + 1) Γ( d 2 + 1) + η α ,where η α := (log 2 (3.56))/ min{(α -1)/2, 1}. 9 The restricted range on ε < 1/ √ n is due to the simpler privacy accountant [25] . By using the Rényi DP accountant instead, one can achieve a tighter result that applies to any n. 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 per-round cohort size in Google's FL application typically ranges from 10 3 to 10 5 , significantly smaller than the number of trainable parameters d ∈ [10 6 , 10 9 ] or the number of available users N ∈ [10 6 , 10 8 ]. 
empirical results: 
 We empirically evaluate our scheme on the DME problem (which is formally introduced in Section 5), examine the privacy-accuracy-communication trade-off, and compare it with the Coordinate Subsampled Gaussian Mechanism (CSGM) [19, Algorithm 1], an order-optimal scheme for DME under central DP. In Chen et al. [19] , 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.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 X i (j)i.i.d. ∼ (2 • Ber(0.8) -1),where Ber(0.8) is a Bernoulli random variable with parameter p = 0.8. We require (ε, δ)-central DP with δ = 10 -6 and ε ∈ [0.05, 6] and apply the PPR with α = 2 to simulate the Gaussian mechanism, where the privacy budgets are accounted via Rényi DP.We compare the MSE of PPR (α = 2, using Theorem 4.3) and CSGM under various compression sizes in Figure 1 (the y-axis is in logarithmic scale). 10 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 ε'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% reduction. For ϵ = 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 are asymptotically close to optimal and a 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 ϵ) is that the trade-off between ϵ and MSE of PPR exactly coincides with the trade-off of the Gaussian mechanism for small ϵ (see Figure 1 ), 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 ϵ-MSE trade-off compared to the Gaussian mechanism (which requires an infinite size communication to exactly realize).Moreover, although directly applying PPR on the d-dimensional vectors is impractical for a large d, one can ensure an efficient O(d) running time (see Section 8 for details) by breaking the vector with d = 1000 dimensions into small chunks of fixed lengths (we use d chunk = 50 dimensions for each chunk), and apply the PPR to each chunk. We call it the sliced PPR in Figure 1 . Though the sliced PPR has a small penalty on the MSE (as shown in Figure 1 ), it still outperforms the CSGM (400 bits) for the range of ε in the plot. For the sliced PPR for one d = 1000 vector, when ϵ = 0.05, the running time is 1.3348 seconds on average. 11 For larger ϵ's, we can choose smaller d chunk 's to have reasonable running time: For ϵ = 6 and d chunk = 2 we have an average running time 0.0127 seconds and with d chunk = 4 we have an average running time 0.6343 seconds; for ϵ = 10 and d chunk = 2 we have an average running time 0.0128 seconds and with d chunk = 4 we have an average running time 0.7301 seconds. See Appendix K for more experiments on the running time of the sliced PPR. 
limitations: 
 While PPR is communication-efficient, having only a 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 [65, 47] . It has been proved in [2] that no polynomial time general sampling- 10 Source code: https://github.com/cheuktingli/PoissonPrivateRepr. Experiments were executed on M1 Pro Macbook, 8-core CPU (≈ 3.2 GHz) with 16GB memory. For PPR under a privacy budget ε and communication budget b, we find the largest ε ′ ≤ ε such that the communication cost bound in Theorem 4.3 (with Shannon code [73] ) for simulating the Gaussian mechanism with (ε ′ , δ)-central DP is at most b, and use PPR to simulate this Gaussian mechanism. Thus, MSE of PPR in Figure 1 becomes flat for large ε, as PPR falls back to using a smaller ε ′ instead of ε due to the communication budget. 11 The running time is calculated by 1000 50 × T chunk , where each chunk's running time T chunk is averaged over 1000 trials. The estimate of the mean of T chunk is 0.0667, whereas the standard deviation is 0.2038. based method exists (even without privacy constraint), if RP ̸ = N P . All existing polynomial time exact channel simulation methods can only simulate specific noisy channels. 12 Hence, a polynomial time algorithm for exactly compressing a general DP mechanism is likely nonexistent. Nevertheless, this is not an obstacle for simulating local DP mechanisms, since the mutual information I(X; Z) for a reasonable local DP mechanism must be small, or else the leakage of the data X in Z would be too large. For an ε-local DP mechanism, we have I(X; Z) ≤ min{ε, ε 2 } (in nats) [22] . Hence, the PPR algorithm can terminate quickly even if has a running time exponential in I(X; Z).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, to apply the Gaussian mechanism to a high-dimensional vector, we break it into several shorter vectors and apply the mechanism to each vector. Experiments in Section 7 show that this greatly reduces the running time while having only a small penalty on the compression size. See Appendix K for experiments on the running time of PPR. 
conclusion: 
 We proposed a novel scheme for compressing DP mechanisms, called Poisson private representation (PPR). Unlike previous schemes which are either constrained on special classes of DP mechanisms or introducing additional distortions on the output, our scheme can compress and exactly simulate arbitrary mechanisms while protecting differential privacy, with a compression size that is close to the theoretic lower bound. A future direction is to reduce the running time of PPR under certain restrictions on P Z|X . For example, the techniques in [38, 35] may be useful when P Z|X is unimodal.A Proof of Proposition 4.2 Write (X i ) i ∼ PP(µ) if the points (X i ) i (as a multiset, ignoring the ordering) form a Poisson point process with intensity measure µ. Similarly, for f : [0, ∞) n → [0, ∞), we write PP(f ) for the Poisson point process with intensity function f (i.e., the intensity measure has a Radon-Nikodym derivative f against the Lebesgue measure). Let (T i ) i ∼ PP(1) be a Poisson process with rate 1, independent of Z 1 , Z 2 , . . . iid ∼ Q. By the marking theorem [57] , ) is the product measure between Q and the Lebesgues measure over [0, ∞). Let P = P Z|X (•|x), and Ti = T i • ( dP dQ (Z i )) -1 . By the mapping theorem [57] (also see [61, 60] ), (Z i , Ti ) i ∼ PP(P × λ [0,∞) ). Note that the points (Z i , Ti ) i may not be sorted in ascending order of Ti . Therefore, we will sort them as follows. Let j 1 be the j such that Tj is the smallest, j 2 be the j other than j 1 such that Tj is the smallest, and so on. Break ties arbitrarily.(Z i , T i ) i ∼ PP(Q × λ [0,∞) ), where Q × λ [0,∞Then ( Tji ) i is an ascending sequence, and we still have (Z ji , Tji ) i ∼ PP(P × λ [0,∞) ) since we are merely rearranging the points. Comparing (Z ji , Tji ) i ∼ PP(P × λ [0,∞) ) with the definition of(Z i , T i ) i ∼ PP(Q × λ [0,∞) ), we can see that ( Tji ) i ∼ PP(1) is independent of Z j1 , Z j2 , . . . iid ∼ P .Recall that in PPR, we generate K ∈ Z + withPr(K = k) = T -α k ∞ i=1 T -α i ,and the final output is Z K . Rearranging the points according to (j i ) i , the distribution of the final output remains the same if we instead generateK ′ ∈ Z + with Pr(K ′ = k) = T -α j k ∞ i=1 T -α ji ,and the final output is Z j K ′ . Since ( Tji ) i ∼ PP(1) is independent of Z ji iid ∼ P , we know that K ′ is independent of (Z ji ) i , and hence Z j K ′ ∼ P follows the desired distribution. 
 
 Appendix: We now discuss the implementation of the Poisson private representation in Section 4. Practically, the algorithm cannot compute the whole infinite sequence ( Ti ) i . We now present an exact algorithm for PPR that terminates in a finite amount of time using a reparametrization.In the proof of Theorem F.1, we showed that, letting 1), PPR can be equivalently expressed as(T i ) i ∼ PP(1), Z 1 , Z 2 , . . . iid ∼ Q, R i := (dP/dQ)(Z i ), V 1 , V 2 , . . . iid ∼ Exp(K = argmin k T α k R -α k V k .The problem of finding K is that there is no stopping criteria for the argmin. For example, if we scan the points (T i , R i , V i ) i in increasing order of T i , it is always possible that there is a future point with V i so small that it makes T α i R -α i V i smaller than the current minimum. If we scan the points in increasing order of V i instead, it is likewise possible that there is a future point with a very small T i . We can scan the points in increasing order of U i := T α i V i , but we would not know the indices of the points in the original process where T 1 ≤ T 2 ≤ • • • is in increasing order, which is necessary to find out the Z i corresponding to each point (recall that in PPR, the point with the smallest T i corresponds to Z 1 , the second smallest T i corresponds to Z 2 , etc.). Therefore, we will scan the points in increasing order of B i := T α i min{V i , 1} instead. By the mapping theorem [57] , (T α i ) i ∼ PP(α -1 t 1/α-1 ). By the marking theorem [57] ,(T α i , V i ) i ∼ PP(α -1 t 1/α-1 e -v ). By the mapping theorem,(T α i , T α i V i ) i ∼ PP(α -1 t 1/α-2 e -vt -1).Since B i = min{T α i , T α i V i }, again by the mapping theorem,(B i ) i ∼ PP ∞ b α -1 b 1/α-2 e -vb -1 dv + ∞ b α -1 t 1/α-2 e -bt -1 dt = PP α -1 b 1/α-1 e -1 + α -1 b 1/α-1 γ(1 -α -1 , 1) = PP α -1 e -1 + γ 1 b 1/α-1 ,where γ 1 := γ(1 -α -1 , 1) and γ(β, x) =x 0 e -τ τ β-1 dτ is the lower incomplete gamma function. Comparing the distribution of (B i ) i and (T α i ) i , we can generate (B i ) i by first generating (U i ) i ∼ PP(1), and then taking B i = (U i α/(e -1 + γ 1 )) α . The conditional distribution of (T i , V i ) given B i = b is described as follows:• With probability e -1 /(e -1 + γ 1 ), we have T α i = b and T α i V i ∼ b(Exp(1) + 1), and henceT i = b 1/α and V i ∼ Exp(1) + 1.• With probability γ 1 /(e -1 + γ 1 ), we have T α i V i = b andT α i ∼ α -1 t 1/α-2 e -bt -1 α -1 γ(1 -α -1 , 1)b 1/α-1 . Hence, for 0 < τ ≤ 1, Pr(V i ≤ τ ) = Pr(T α i ≥ b/τ ) = γ(1 -α -1 , τ ) γ(1 -α -1 , 1) ,and V i follows the truncated gamma distribution with shape 1 -α -1 and scale 1, truncated within the interval [0, 1]. We then haveT i = (b/V i ) 1/α .The algorithm is given in Algorithm 1. The encoder and decoder require a shared random seed s.One way to generate s 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 s, guaranteeing that the s at the encoder is the same as the s at the decoder. The encoder maintains a collection of points (T i , V i , Θ i ), stored in a heap to allow fast query and removal of the point with the smallest T i . The value Θ i ∈ {0, 1} indicates whether it is possible that the point (T i , V i ) attains the minimum of T α k R -α k V k . The encoding algorithm repeats until there is no possible points left in the heap, and it is impossible for any future point to be better than the current minimum of T α k R -α k V k . The encoding time complexity is O(sup z (dP/dQ)(z) log(sup z (dP/dQ)(z))), which is close to other sampling-based channel simulation schemes [45, 36] . 13 The decoding algorithm simply outputs the k-th sample generated using the random seed s, which can be performed in O(1) time. 14The PPR is implemented by Algorithm 1. We write x ← Exp G (1) to mean that we generate an exponential random variate x with rate 1 using the pseudorandom number generator G . Write x ← Exp local (1) to mean that x is generated using a local pseudorandom number generator (not G ).First prove Theorem 4.5. Consider a ε-DP mechanism P Z|X . Consider neighbors x 1 , x 2 , and let P j := P Z|X (•|x j ), Tj,i := T i /( dPj dQ (Z i )), and K j be the output of PPR applied on P j , for j = 1, 2.EQUATIONAlgorithm 1 Poisson private representation Procedure PPRENCODE(α, Q, r, r * , s) :Input: parameter α > 1, distribution Q, density r(z) := (dP/dQ)(z), bound r * ≥ sup z r(z), random seed s Output: index k ∈ Z >0 1: Initialize PRNG G using the seed s 2: u ← 0, w * ← ∞, k ← 0, k * ← 0, n ← 0 3: γ 1 ← γ(1 -α -1 , 1) = 1 0 e -τ τ -α -1 dτ 4: h ← ∅ (empty heap) 5: while true do 6: u ← u + Exp local (1)▷ Generated using local randomness (not G ) if Unif local (0, 1) < e -1 /(e -1 + γ 1 ) then ▷ Run with prob. e -1 /(e -1 + γ 1 ) while h ̸ = ∅ and min (t ′ ,v ′ ,θ ′ )∈h t ′ ≤ b 1/α do ▷ Assign Z i 's to points in heap with small T i 23:12: t ← b 1/α , v ← Exp local (1) + 1 13: else 14: repeat 15: v ← Gamma local (1 -α -1 , 1) ▷ Gamma distribution 16: until v ≤ 1 17: t ← (b/v)(t, v, θ) ← arg min (t ′ ,v ′ ,θ ′ )∈h t ′ , and pop (t, v, θ) from hn ← n -θ 25:k ← k + 1 Generate z ∼ Q using G ▷ See footnote 14 4: end for 5: return z for Q-almost every z, 15 and hence e -ε T2,i ≤ T1,i ≤ e ε T2,i . For k ∈ Z + , we have, almost surely,EQUATIONHence, P (Zi)i,K|X is 2αε-DP.For Theorem 4.7, consider a ε • d X -private mechanism P Z|X , and consider x 1 , x 2 ∈ X . We haveEQUATIONfor Q-almost every z. By exactly the same arguments as in the proof of Theorem 4.5, Pr (((Z i ) i , K 1 ) ∈ S) ≤ e 2αε•d X (x1,x2) Pr (((Z i ) i , K 2 ) ∈ S), and henceP (Zi)i,K|X is 2αε • d X - private.Consider a (ε, δ)-DP mechanism P Z|X . Consider neighbors x 1 , x 2 , and let P j := P Z|X (•|x j ), and K j be the output of PPR applied on P j , for j = 1, 2. By the definition of (ε, δ)-differential privacy, we haveEQUATIONEQUATIONLet ρ(z) := min max ρ 1 (z), e -ε ρ 2 (z) , e ε ρ 2 (z) .Note that e -ε ρ 2 (z) ≤ ρ(z) ≤ e ε ρ 2 (z). We then consider two cases:Case 1: ρ(z)Q(dz) ≤ 1. Let ρ 3 (z) be such that ρ 3 (z)Q(dz) = 1 and ρ(z) ≤ ρ 3 (z) ≤ e ε ρ 2 (z).We can always find such ρ 3 by taking an appropriate convex combination of the lower bound above (which integrates to ≤ 1) and the upper obund above (which integrates to ≥ 1). We then haveEQUATION)15 ε-DP only implies that (2) holds for P1-almost every z (or equivalently P2-almost every z since P1, P2 are absolutely continuous with respect to each other). We now show that (2) holds for Q-almost every z. Apply Lebesgue's decomposition theorem to find measuresQ, Q such that Q = Q + Q, Q ≪ P1 and Q ⊥ P1. There exists Z ′ ⊆ Z such that P1(Z ′ ) = 1 and Q(Z ′ ) = 0. Since P1 ≪ Q, we have P1 ≪ Q. We have (2) for Q-almost every z. Also, we have (2) for Q-almost every z since z / ∈ Z ′ gives dP 1 dQ (z) = dP 1 d Q (z) = 0 for Q-almost every z, and also dP 2 dQ (z) = 0 for Q-almost every z since P2 ≪ P1. If ρ 1 (z)-e ε ρ 2 (z) ≤ 0, then ρ 1 (z)-ρ 3 (z) ≤ ρ 1 (z)-ρ(z) ≤ 0. If ρ 1 (z)-e ε ρ 2 (z) > 0, then ρ 3 (z) = ρ(z) = e ε ρ 2 (z).Either way, we have max {ρ 1 (z) -ρ 3 (z), 0} = max {ρ 1 (z) -e ε ρ 2 (z), 0}. By (5), we havemax {ρ 1 (z) -ρ 3 (z), 0} Q(dz) ≤ δ.Let P 3 = ρ 3 Q be the probability measure with dP 3 /dQ = ρ 3 . Then the total variation distance d TV (P 1 , P 3 ) between P 1 and P 3 is at most δ, and by ( 7),EQUATIONCase 2:ρ(z)Q(dz) > 1. Let ρ 3 (z) be such that ρ 3 (z)Q(dz) = 1 and e -ε ρ 2 (z) ≤ ρ 3 (z) ≤ ρ(z).We can always find such ρ 3 by taking an appropriate convex combination of the lower bound above (which integrates to ≤ 1) and the upper obund above (which integrates to > 1). We again have e -ε ρ 2 (z)≤ ρ 3 (z) ≤ e ε ρ 2 (z). If e -ε ρ 2 (z) -ρ 1 (z) ≤ 0, then ρ 3 (z) -ρ 1 (z) ≤ ρ(z) - ρ 1 (z) ≤ 0. If e -ε ρ 2 (z) -ρ 1 (z) > 0, then ρ 3 (z) = ρ(z) = e -ε ρ 2 (z).Either way, we havemax {ρ 3 (z) -ρ 1 (z), 0} = max {e -ε ρ 2 (z) -ρ 1 (z), 0}. By ( 6), we havemax {ρ 3 (z) -ρ 1 (z), 0} Q(dz) ≤ e -ε δ ≤ δ.Let P 3 = ρ 3 Q be the probability measure with dP 3 /dQ = ρ 3 . Again, we have d TV (P 1 , P 3 ) ≤ δ and ( 8). Therefore, regardless of whether Case 1 or Case 2 holds, we can construct P 3 satisfying d TV (P 1 , P 3 ) ≤ δ and (8). Let K 3 be the output of PPR applied on P 3 .In the proof of Theorem F.1, we see that PPR has the following equivalent formulation. Let (T i ) i ∼ PP(1) be a Poisson process with rate 1, independent of Z 1 , Z 2 , . . .iid ∼ Q. Let R i := (dP/dQ)(Z i ),and let its probability measure be PR . Let V 1 , V 2 , . . . iid ∼ Exp(1). PPR can be equivalently expressed asK = argmin k T α k R -α k V k = argmin k T k V 1/α k R k .Note that(T i V 1/α i ) i ∼ PP( ∞ 0 v -1/α e -v dv) = PP(Γ(1 -α -1)) is a uniform Poisson process. Therefore PPR is the same as the Poisson functional representation [61, 60] applied on(T i V 1/α i ) i .By the grand coupling property of Poisson functional representation [60, 59] (see [59, Theorem 3] ), if we apply the Poisson functional representation on P 1 and P 3 to get K 1 and K 3 respectively, thenPr(K 1 ̸ = K 3 ) ≤ 2d TV (P 1 , P 3 ) ≤ 2δ. Therefore, for any measurable S ⊆ Z ∞ × Z >0 , Pr (((Z i ) i , K 1 ) ∈ S) ≤ Pr (((Z i ) i , K 3 ) ∈ S) + 2δ ≤ e 2αε Pr (((Z i ) i , K 2 ) ∈ S) + 2δ,where the last inequality is by applying (3) on P 3 , P 2 instead of P 1 , P 2 . Hence, P (Zi)i,K|X is (2αε, 2δ)-DP.We present the proof of (ε, δ)-DP of PPR (i.e., Theorem 4.8).Proof. We assumeEQUATIONwhere β := e -4.2 . Using the Laplace functional of the Poisson process ( Ti ) i [57, Theorem 3.9], for w > 0,E exp -w i T -α i = exp - ∞ 0 (1 -exp(-wt -α ))dt (10) = exp -w 1/α Γ(1 -α -1 ) .We first bound the left tail of i T -α i. By Chernoff bound, for d ≥ 0,Pr i T -α i ≤ d ≤ inf w>0 e wd E exp -w i T -α i = inf w>0 exp wd -w 1/α Γ(1 -α -1 ) ≤ exp Γ(1 -α -1 ) αd α α-1 d - Γ(1 -α -1 ) αd 1 α-1 Γ(1 -α -1 ) = exp Γ(1 -α -1 ) α α-1 d -1 α-1 α -α α-1 -α -1 α-1 = exp - αd (Γ(1 -α -1 )) α -1 α-1 1 -α -1 = exp - αd(1 -α -1 ) α (Γ(2 -α -1 )) α -1 α-1 1 -α -1 = exp - (α -1)d (Γ(2 -α -1 )) α -1 α-1 . Therefore, to guarantee Pr( i T -α i ≤ d) ≤ δ/3, we require d ≤ Γ(2 -α -1 ) α -ln( δ/3) -(α-1) α -1 ,whereΓ(2 -α -1 ) α -ln( δ/3) -(α-1) ≥ (exp (-γ(α -1))) α -ln( δ2 ) -(α-1) ≥ exp -γα β δ ε2 -ln δ -2 ln δ -β δ ε2 -ln δ ≥ exp -2γ β δ ε2 -ln δ -2e -1 β δ ε2 ≥ exp - 2γ 3 ln 2 + 2 3e β ε2 ≥ exp -0.81 • β ε2 ≥ e -ε/2 , since 1 < α ≤ 2, 0 < δ ≤ 1/3, β = e -4.2 and 0 < ε ≤ 1, where γ is the Euler-Mascheroni constant. Hence, we haveEQUATION)We then bound the right tail of i T -α i . Unfortunately, the Laplace functional (10) does not work since the integral diverges for small t. Therefore, we have to bound t away from 0. Note that min i Ti ∼ Exp(1), and hence Pr(minEQUATION)Write τ = δ/3. Using the Laplace functional again, for w > 0,E   exp w i: Ti>τ T -α i   = exp - ∞ τ (1 -exp(wt -α ))dt = exp ∞ τ (exp(wt -α ) -1)dt ≤ exp ∞ τ (exp(wτ -α ) -1) t -α τ -α dt = exp exp(wτ -α ) -1 τ -α • τ -(α-1) α -1 = exp τ (exp(wτ -α ) -1) α -1 .Therefore, by Chernoff bound, for d ≥ 0,EQUATIONwherec := d(α -1)τ α-1 ,and the last inequality holds whenever c ∈ [1, 2] since in this range,c ln c -c + 1 ≥ (2 ln 2 -1)(c -1) 2 . Substituting d = e ε/2 α -1 ,we have c = e ε/2 τ α-1 . By ( 13), to guarantee Pr( i:EQUATIONSubstituting ( 9), we havee ε/2 τ α-1 ≥ e ε/2 τ β δ ε2 -ln δ = exp ε 2 + ln δ 3 β δ ε2 -ln δ ≥ exp ε 2 + 2 ln δ β ε -3 ln δ = exp ε 1 2 - 2β 3 , since 0 < δ ≤ 1/3. Note that this also guarantees c = e ε/2 τ α-1 ∈ [1, 2] since β = e -4.2 and 0 < ε ≤ 1. We also haveEQUATION≤ e ε/2 τ α-1 ,where (a) is by β = e -4.2 . Hence ( 14) is satisfied, andPr i: Ti>τ T -α i ≥ e ε/2 α -1 ≤ δ 3 .Combining this with ( 11) and ( 12),Pr i T -α i / ∈ e -ε/2 α -1 , e ε/2 α -1 ≤ Pr i T -α i ≤ e -ε/2 α -1 + Pr(min i Ti ≤ δ/3) + Pr i: Ti> δ/3 T -α i ≥ e ε/2 α -1 ≤ δ.Consider an (ε, δ)-differentially private mechanism P Z|X . Consider neighbors x 1 , x 2 , and let P j := P Z|X (•|x j ), Tj,i := T i /( dPj dQ (Z i )), and K j be the output of PPR applied on P j , for j = 1, 2. We first consider the case δ = 0, which gives dP1 dQ (z) ≤ e ε dP2 dQ (z) for every z. For any measurableEQUATIONHence PPR is (αε + ε, 2 δ)-differentially private.For the case δ > 0, by the definition of (ε, δ)-differential privacy, we havemax dP 1 dQ (z) -e ε dP 2 dQ (z), 0 Q(dz) ≤ δ.Let P 3 be a probability measure that satisfiesmin dP 1 dQ (z), e ε dP 2 dQ (z) ≤ dP 3 dQ (z) ≤ e ε dP 2 dQ (z),for every z. Such P 3 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 P 3 integrates to 1. We havemax dP 1 dQ (z) - dP 3 dQ (z), 0 Q(dz) ≤ δ,and hence the total variation distance d TV (P 1 , P 3 ) between P 1 and P 3 is at most δ. Let K 3 be the output of PPR applied on P 3 .In the proof of Theorem F.1, we see that PPR has the following equivalent formulation. Let (T i ) i ∼ PP(1) be a Poisson process with rate 1, independent of Z 1 , Z 2 , . . .iid ∼ Q. Let R i := (dP/dQ)(Z i ),and let its probability measure be PR . Let V 1 , V 2 , . . . iid ∼ Exp(1). PPR can be equivalently expressed asK = argmin k T α k R -α k V k = argmin k T k V 1/α k R k .Note that(T i V 1/α i ) i ∼ PP( ∞ 0 v -1/α e -v dv) = PP(Γ(1 -α -1)) is a uniform Poisson process. Therefore PPR is the same as the Poisson functional representation [61, 60] applied on(T i V 1/α i ) i .By the grand coupling property of Poisson functional representation [60, 59] (see [59, Theorem 3] ), if we apply the Poisson functional representation on P 1 and P 3 to get K 1 and K 3 respectively, thenPr(K 1 ̸ = K 3 ) ≤ 2d TV (P 1 , P 3 ) ≤ 2δ. Therefore, for any measurable S ⊆ Z ∞ × Z >0 , Pr (((Z i ) i , K 1 ) ∈ S) ≤ Pr (((Z i ) i , K 3 ) ∈ S) + 2δ ≤ e αε+ε Pr (((Z i ) i , K 2 ) ∈ S) + 2 δ + 2δ,where the last inequality is by applying (15) on P 3 , P 2 instead of P 1 , P 2 . This completes the proof.We now bound the size of the index output by the Poisson private representation. The following is a refined version of Theorem 4.3.Theorem F.1. For PPR with parameter α > 1, when the encoder is given the input x, the message K given by PPR satisfiesEQUATIONEQUATIONwhere P := P Z|X (•|x).Note that for α = ∞, (16) with η = 1 gives E[log K] ≤ D(P ∥Q) + log 2, recovering the bound in [58] (which strengthened [61] ).Proof. Write (X i ) i ∼ PP(µ) if the points (X i ) i (as a multiset, ignoring the ordering) form a Poisson point process with intensity measure µ. Similarly, for f : [0, ∞) n → [0, ∞), we write PP(f ) for the Poisson point process with intensity function f (i.e., the intensity measure has a Radon-Nikodym derivative f against the Lebesgue measure). Let (T i ) i ∼ PP(1) be a Poisson process with rate 1,independent of Z 1 , Z 2 , . . . iid ∼ Q. Let R i := (dP/dQ)(Z i ), and let its probability measure be P R .We have Ti =T i /R i . Let V 1 , V 2 , . . . iid ∼ Exp(1). By the property of exponential random variables, for any p 1 , p 2 , . . . ≥ 0 with i p i < ∞, we have Pr(argmin k V k /p k = k) = p k / i p i . Therefore, PPRF can be equivalently expressed asK = argmin k T α k R -α k V k .By the marking theorem [57] , (T i , R i , V i ) i is a Poisson process over [0, ∞) 3 with intensity measure(T i , R i , V i ) i ∼ PP e -v P R (r) .By the mapping theorem [57] , lettingEQUATIONAgain by the mapping theorem,(W i ) i ∼ PP E R∼P R ∞ 0 R α t -α e -wR α t -α dt = PP E α -1 (wR α ) 1/α-1 Γ(1 -α -1 )R α = PP E α -1 w 1/α-1 Γ(1 -α -1 )R = PP α -1 w 1/α-1 Γ(1 -α -1 ) since E[R] = (dP/dQ)(z)Q(dz) = 1. Recall that W K = min i W i by the definition of K.We havePr(W K > w) = exp - w 0 α -1 v 1/α-1 Γ(1 -α -1 )dv = exp -w 1/α Γ(1 -α -1 ) .Hence the probability density function ofEQUATIONBy ( 18), the Radon-Nikodym derivative between the conditional distribution of R K given W K = w and P R isPr(R K ∈ [r, r + dr) | W K = w)/P R (dr) = ∞ 0 r α t -α e -wr α t -α dt E R∼P R ∞ 0 R α t -α e -wR α t -α dt = α -1 w 1/α-1 Γ(1 -α -1 )r α -1 w 1/α-1 Γ(1 -α -1 ) = rdoes not depend on w. Hence R K is independent of W K . By (18) , for 0 ≤ η < α -1,EQUATION)Since R K is independent of W K , using ( 20) and ( 19), for η ∈ (0, 1] ∩ (0, α -1),EQUATIONwhere c α,η := Γ(1EQUATIONNote that K -1 = |{i : T i < T K }| , and hence the expecation of K -1 given T K should be around T K . This is not exact since conditioning on T K changes the distribution of the process (T i , R i , V i ) i . To resolve this problem, we define a new process(T ′ i , R ′ i , V ′ i ) i which includes all points in (T i , R i , V i ) i excluding the point (T K , R K , V K ), together with newly generated points according to PP e -v P R (r)1{t α r -α v < T α K R -α K V K } . Basically, {t α r -α v < T α K R -α K V K } is the "impossible region" where the points in (T i , R i , V i ) i cannot be located in, since K attains the minimum of T α K R -α K V K . The new process (T ′ i , R ′ i , V ′ i ) i removes the point (T K , R K , V K ), and then fills in the impossible region. It is straightforward to check that(T ′ i , R ′ i , V ′ i ) i ∼ PP(e -v P R (r)), independent of (T K , R K , V K ). We have E[K | T K ] = E |{i : T i < T K }| T K + 1 ≤ E |{i : T ′ i < T K }| T K + 1 = T K + 1.Therefore, by (22) and Jensen's inequality,E[log K] = E [E[log K | T K ]] ≤ E [log(T K + 1)] = E E log(T K + 1) R K ≤ E η -1 log(c α,η R η K + 1) = η -1 E Z∼P log c α,η dP dQ (Z) η + 1 = η -1 E log dP dQ (Z) η + η -1 E log c α,η + dP dQ (Z) -η ≤ D(P ∥Q) + η -1 log c α,η + E dP dQ (Z) -1 η ≤ D(P ∥Q) + η -1 log(c α,η + 1),where the last line is due to E[((dP/dQ)(Z)) -1 ] = ((dP/dQ)(Z)) -1 P (dz) ≤ 1 (this step appeared in [58] ). The bound (16) follows from minimizing over η ∈ (0, 1] ∩ (0, α -1).To show (17) , substituting η = min{(α -1)/2, 1}, c α,η = Γ(1 -(η + 1)α -1 )Γ(η + 1) (Γ(1 -α -1 )) η+1 (a) ≤ (1 -α -1 ) η+1 0.885 η+1 • (1 -(η + 1)α -1 ) ≤ (1 -α -1 ) η+1 0.885 2 • (1 -((α -1)/2 + 1)α -1 ) = 2 0.885 2 (1 -α -1 ) η ≤ 2.56,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 a Rényi DP version of Corollary 5.2 in this section. We begin with the following definition of Rényi DP: Definition G.1 (Rényi Differential privacy [1, 68] ). Given a mechanism A which induces the conditional distribution P Z|X of Z = A(X), we say that it satisfies (γ, ε)-Rényi DP if for any neighboring (x, x ′ ) ∈ N and S ⊆ Z, it holds thatD γ P Z|X=x P Z|X=x ′ ≤ ε,whereD γ (P ∥Q) := 1 γ -1 log E Q P Q γis the Rényi divergence between P and Q. If N = X 2 , we say that the mechanism satisfies (γ, ε)-local DP.The following conversion lemma from [13] relates Rényi DP to (ε DP (δ), δ)-DP. Lemma G.2. If A satisfies (γ, ε)-Rényi DP for some γ ≥ 1, then, for any δ > 0, A satisfies (ε DP (δ), δ)-DP, whereEQUATIONThe following theorem states that, when simulating the Gaussian mechanism, PPR satisfies the following both central and local DP guarantee: Corollary G.3 (PPR-compressed Gaussian mechanism). Let ε ≥ 0 and γ ≥ 1. Consider the Gaussian mechanism P Z|X (•|x) = N (x, σ 2 n I d ), and the proposal distributionQ = N (0, ( C 2 d + σ 2 n )I d ), where σ ≥ Cγ 2ε . For each client i, let Z i be the output of PPR applied on P Z|X (•|X i ). We have:• μ(Z n ) := 1 n i Z i yields an unbiased estimator of µ(X n ) = 1 n n i=1 X i satisfying (γ, ε)- (central)Rényi DP and (ε DP (δ), δ)-DP, where ε DP (δ) is defined in (23) .• P Z|Xi satisfies (2αε DP (δ), 2δ)-local DP, where εDP (δ) := √ nε + log (1/γδ) γ -1 + log(1 -1/γ). • μ(Z n ) has MSE E[∥µ -μ∥ 2 2 ] = σ 2 d/n 2Q = N (0, ( C 2 d + σ 2 n )I d ). PPR ensures that Z i follows the distribution N (X i , σ 2 n I d ). Therefore the MSE is E ∥µ -μ∥ 2 2 = E   1 n n i=1 (X i -Z i ) 2 2   = 1 n • d • σ 2 n = σ 2 d n 2 .For the compression size, for x ∈ R d with ∥x∥ 2 ≤ C, we haveD(P Z|X (•|x)∥Q) = E Z∼P Z|X (•|x) log dP Z|X (•|x) dQ (Z) = E Z∼P Z|X (•|x) log (2πσ 2 /n) -d/2 exp(-1 2 ∥Z -x∥ 2 2 /(σ 2 /n)) (2π( C 2 d + σ 2 n )) -d/2 exp(-1 2 ∥Z∥ 2 2 /( C 2 d + σ 2 n )) = E Z∼P Z|X (•|x) d 2 log C 2 d + σ 2 n σ 2 /n + 1 2 ∥Z∥ 2 2 C 2 d + σ 2 n - ∥Z -x∥ 2 2 σ 2 /n ≤ d 2 log C 2 d + σ 2 n σ 2 /n + 1 2 C 2 + σ 2 d/n C 2 d + σ 2 n - σ 2 d/n σ 2 /n = d 2 log C 2 n dσ 2 + 1 .Hence, by Theorem 4.3, the compression size is at most ℓ + log 2 (ℓ + 1) + 2 bits, where I Proof of Corollary 6.1EQUATIONLet ∥X -Z∥ 2 = RS where R ∈ [0, ∞) is the magnitude of X -Z, and ∥S∥ 2 = 1. As shown in [33] , R follows the Gamma distribution with shape d and scale 1/ε. Hence the MSE isE ∥X -Z∥ 2 2 = E R 2 = d ε 2 + d ε 2 = d(d + 1) ε 2 .The conditional differential entropy (in nats) of Z given X is h(Z|X) = h(R) + h(S|R)= d + ln Γ(d) -(d -1)ψ(d) -ln ε + E ln(nR d-1 Vol(B d (1))) = d + ln Γ(d) -(d -1)ψ(d) -ln ε + ln d + ln(Vol(B d (1))) + (d -1)E [ln R] = d + ln Γ(d) -(d -1)ψ(d) -ln ε + ln d + d 2 ln π -ln Γ d 2 + 1 -(d -1) ln ϵ + (d -1)ψ(d) = d ln e √ π ε + ln dΓ(d) Γ( d 2 + 1), where ψ is the digamma function. Therefore, the KL divergence between P Z|X (•|x) and Q (in nats) isD(P Z|X (•|x)∥Q) = -E Z∼P Z|X (•|x) ln 2π C 2 d + d + 1 ε 2 -d/2 exp - ∥Z∥ 2 2 2( C 2 d + d+1 ε 2 ) -h(Z|X) = d 2 ln 2π C 2 d + d + 1 ε 2 + E Z∼P Z|X (•|x) ∥Z∥ 2 2 2( C 2 d + d+1 ε 2 ) -d ln e √ π ε -ln dΓ(d) Γ( d 2 + 1) ≤ d 2 ln 2π C 2 d + d + 1 ε 2 + C 2 + d(d+1) ε 2 2( C 2 d + d+1 ε 2 ) -d ln e √ π ε -ln dΓ(d) Γ( d 2 + 1) = d 2 ln 2 e C 2 ε 2 d + d + 1 -ln Γ(d + 1) Γ( d 2 + 1).Hence, by Theorem 4.3, the compression size is at most ℓ + log 2 (ℓ + 1) + 2 bits. The metric privacy guarantee follows from Theorem 4.7.We use PPR to simulate the Laplace mechanism [3, 33, 34] f Z|X (z|x) ∝ e -εd X (x,z) discussed in Section 6. We consider X ∈ B d (C) where C = 10000 and d = 500. A large number of dimensions d is common, for example, in privatizing word embedding vectors [33, 34] . We compare the performance of PPR-compressed Laplace mechanism (Corollary 6.1) with the discrete Laplace mechanism [3] . The discrete Laplace mechanism is described as follows (slightly modified from [3] to Figure 2 shows the mean squared error of PPR-compressed Laplace mechanism (α = 2) and the discrete Laplace mechanism for different ε's, when the number of bits is limited to 500, 1000 and 1500. 16 We can see that PPR performs better for larger ϵ or smaller MSE, whereas the discrete Laplace mechanism performs better for smaller ϵ or larger MSE. The performance of discrete Laplace mechanism for smaller ϵ is due to the truncation step which limits Z to B d (C), which reduces the error at the expense of introducing distortion to the distribution of Z, and making Z a biased estimate of X. In comparison, PPR preserves the Laplace conditional distribution f Z|X exactly, and hence produces an unbiased Z. 16 The MSE of PPR is computed using the closed-form formula in Corollary 6.1, which is tractable since Z follows the Laplace conditional distribution f Z|X exactly. The number of bits used by PPR is given by the bound in 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.e., standard error of the mean divided by the sample mean) is only 0.00117, which would be unnoticeable even if the error bars were plotted. As discussed in Section 7, we can ensure an O(d) running time for the Gaussian mechanism by using the sliced PPR, where the d-dimensional vector X is divided into ⌈d/d chunk ⌉ chunks, each with a fixed dimension d chunk (possibly except the last chunk if d chunk is not a factor of d). The average total running time is ⌈d/d chunk ⌉T chunk , where T chunk is the average running time of PPR applied on one chunk. 17 Therefore, to study the running time of the sliced PPR, we study how T chunk depend on d chunk .In Figure 3 we show the running time T chunk of PPR applied on one chunk with dimension d chunk , where d chunk ranges from 40 to 110. 18 With d = 1000, n = 500, ε = 0.05 and δ = 10 -6 , we require a Gaussian mechanism with noise N (0, nσ 2 I d chunk ) where σ = 1.0917 at each user in order to ensure (ε, δ)-central DP. We record the mean T chunk and the standard error of the mean 19 of the running time of PPR applied to simulate this Gaussian mechanism (averaged over 20000 trials). We plot the MSE against the compression size (ranging from 25 to 1000 bits) for ϵ ∈ {0.25, 0.5, 1.0, 2.0} in the following figure.Figure 5 : The MSE of PPR and CSGM against the compression size in bits, where ε is 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 a higher compression size than necessary will not affect the result.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 our paper's contributions and scope in both the abstract and introduction. We try to answer the fundamental question: how can we efficiently communicate privatized data? The main contribution is our 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.• 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 are provided or not. • If the contribution is a 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 is a specific model and empirical evaluation, it may 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 to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions 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) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main 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.Our code can be found in https://github.com/cheuktingli/PoissonPrivateReprThis is similar to channel simulation[45] and the strong functional representation lemma[61], though[45,61] do not concern privacy.Equivalently, local DP can be viewed as a special case of central DP with dataset size n = 1.Since the Ti's are continuous, with probability 1, there do not exist two equal values among Ti's.Note that the encoder does not actually send ((Zi)i, K); it only sends K. The common randomness (Zi)i is independent of the data X, and can be pre-generated using a common random seed in practice. While this seed must be communicated between the client and the 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 i ) i ,K|X is only relevant for privacy analysis.For example,[36] and dithered-quantization-based schemes[48,72] can only simulate additive noise mechanisms. Among these existing works, only[72] ensures local DP.It was shown in[36] that greedy rejection sampling[45] runs in O(sup z (dP/dQ)(z)) time. The PPR algorithm has an additional log term due to the use of heap.A counter-based PRNG[70] allows us to directly jump to the state after k uses of the PRNG, without the need of generating all k samples, greatly improving the decoding efficiency. This technique is applicable to greedy rejection sampling[45] and the original Poisson functional representation[61,60] as well.Note that the chunks may be processed in parallel for improved efficiency.Experiments were executed on M1 Pro Macbook, 8-core CPU (≈ 3.2 GHz) with 16GB memory.The standard error of the mean is given by σmean = σtime/ √ n trials , where σtime is the standard deviation of the running time among the n trials =trials. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: Why does the privacy analysis in Corollary 5.1 not relate to n?
limitations: limitations: Limitations are clearly stated in the paper.
paper_summary: paper_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} $.

The paper introduces a novel compression algorithm leveraging shared randomness between the server and clients. Key points include:
1. The compression algorithm applies universally to every local randomized algorithm, provided there is agreement on the output space.
2. The size of the compressed output matches the mutual information lower bound $ I(X; Z) $, with an additive logarithmic term.
3. 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.

A 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.

Experimental results demonstrate improved performance of the proposed algorithm compared to previous approaches.
strength_weakness: strength_weakness: See ``Limitations''
questions: questions: 1. On page 2, line 75, "lower bound I(X;Y)" - - > "lower bound I(X;Z)".

2. 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: limitations: 1.	1. 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.

2.	2. 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.
paper_summary: paper_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.  

Techniques 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. 

The 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.
strength_weakness: strength_weakness: 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. 

As 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. 

The 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. 

Finally, 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. 

A minor comment is the lack of a more complete presentation of Poisson functional representation, which could be expanded for clarity.
questions: questions: Can de authors address weaknesses raised in my review? 

Especially, two aspects that would clarify the advantages of the work are:

- 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). 

- 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: limitations: I don't see additional limitations other than the discussed by the authors.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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.)
* PPR yields an overhead of more than a factor 2 in the privacy parameter
* 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
questions: questions: * Is it correctly understood that your method is private even to an adversary who knows the shared randomness?
* Is there any way that clients can use the same shared randomness, or should this by per-client?
* In line 166 it is not clear that argmin is well-defined, can you comment on this?
* Can you achieve a bound on the worst-case encoding size, say, by reverting to a simpler encoding if K is too large?
limitations: limitations: The authors have adequately addressed limitations

Comments: title: Thank you for your response to our rebuttal.
Thank you for your response to our rebuttal.
Thank you for your response to our rebuttal.
Thanks for the rebuttal
comment: We thank the reviewer for the time reading our paper and rebuttal.
We thank the reviewer for the time reading our rebuttal and providing constructive feedbacks.
We thank the reviewer for the time evaluating our manuscript.
Dear authors,

Thank you for your reply. I highly appreciate your efforts in clarifying concerns. I am leaning to increase my score, but in that case I will do it after discussing with the other reviewers.
We thank Reviewer U6Tv for the thoughtful comments. Please find our responses below.

**1. The reason for comparing to CSGM [18]**

We chose to compare to CSGM [18] since [18] is asymptotically optimal and compares favorably to several previous algorithms, as demonstrated in the experiments in [18]. By showing that our proposed scheme compares favorably to [18], we show that our scheme compares favorably to those previous works as well.

**2. Regarding comparison to other techniques**

Regarding Feldman and Talwar [30]: [30] mentioned applying [30, Theorem 3.4] to Gaussian mechanism. The main obstacle in comparing [30, Theorem 3.4] to our result is that [30] relies on a computational hardness assumption on the pseudorandom number generator, and it is unclear how many bits of random seed (communication) are necessary to guarantee computational indistinguishability. Also, [30] does not prove that their scheme has a communication cost close to the theoretical minimum.

Regarding Bassily and Smith [5]: [5] does not exactly preserves the distribution of the simulated mechanism (there is a 50% chance that the data is dropped). Additional (likely non-trivial) analyses are necessary to characterize its central-DP guarantee for mean estimation, to be compared to our scheme in Figure 1.

[65] is also non-exact, making their central-DP guarantees unclear.

**3. About whether "approximate simulation would imply biased estimates"**

We emphasize that unbiasedness is a mathematical property that requires proof. If an approximate method cannot be proved to be unbiased, then it should not be considered to be unbiased, regardless of how close to zero the bias appears to be in experiments (the bias might become large outside of the cases experimented). For some specific approximate methods, it may be possible to add a debiasing step with a proof of unbiasedness (e.g., [65]), though the feasibility of such a step depends on the specific task and the mathematical tractability of the output distribution. The advantage of exactness is that it can readily imply unbiasedness, and no additional steps are necessary.

In sum, approximate method does not necessarily imply biasedness (e.g., [65]), but an approximate method without a proof of unbiasedness should not be considered to be unbiased. Therefore, unbiasedness is an advantage of our exact method over other approximate methods without proofs of unbiasedness. This is a theoretical advantage that does not require experiments to show.

**4. Regarding distortion for a fixed $(\\varepsilon, \\delta)$ and approximate techniques**

Indeed, if $(\\varepsilon, \\delta)$ is fixed, then we have to reduce the $\\varepsilon, \\delta$ of the simulated mechanism. However, this reduction can be small according to Theorem 4.8. Also, the distortion introduced by lowering $\\varepsilon, \\delta$ is considerably different from the distortion introduced by the methods in [30,65,71]. If we exactly simulate the Gaussian mechanism with a lower $\\varepsilon, \\delta$, the noise is still exactly Gaussian (with a larger variance), and can be added to other Gaussian noises nicely. This "summable" noise is the key to providing central DP guarantees (in addition to local DP). However, if we simulate the Gaussian mechanism using the approximate techniques in [30,65,71], the noise introduced has a mathematically intractable distribution, which will be an obstacle in obtaining theoretic guarantees for downstream tasks (e.g., for distributed mean estimation, we do not know the overall noise distribution and its central-DP properties after summing all the data). The main benefits of exactness are mathematical tractability and ease of proving guarantees for downstream tasks.

**5. The benefits of simple theoretical guarantees**

Also, we believe that the theoretical contributions of our work, namely the privacy-communication trade-off given in Theorems 4.3-4.8 given in simple and clean expressions, with exact preservation of the output distribution, is noteworthy in itself. To the best of our knowledge, our work is the first method for compressing DP mechanisms that has a bound on its compression size universally close to the I(X;Z) lower bound (i.e., the bound depends on the simulated mechanism only through I(X;Z) as in Theorem 4.3, and hence is always almost-optimal regardless of the situation). Even though we agree that more experiments can be beneficial, experiments are not strictly necessary to demonstrate the almost-optimality of our method, when we have a mathematical proof of its universal almost-optimality for the compression size.

We believe these simple guarantees (in terms of simple quantities like I(X;Z)) and exact distribution preservation can make the proposed method a useful general technique for designing more specific DP mechanisms in the future.


We hope that we have adequately addressed the concerns and questions, and kindly invite the reviewer to consider updating the score.
Thank you for your rebuttal and your efforts for clarifying concerns.  

I appreciate the clarifications on the use of shared randomness and the advantages with respect to CSGM [18]. You have addressed these points successfully.

However, I still feel that the proposed technique should be further compared with related work. It is not clear to me why [18] is the only work for which you should compare concrete trade-offs. Even if you have been clear about the conceptual advantages of exact simulation (i.e., unbiased distributions, "summable" noise), it does not seem clear why approximate simulation would imply biased estimates. Therefore, I don't fully understand why other techniques mentioned in "Generic compression of local DP mechanisms" and "DME under DP" paragraphs of Section 2 are excluded from more concrete comparisons made in Section 7. 

In particular (and as already raised in the discussion), the proposed protocol inflates the privacy budget. Therefore if we want to obtain a compressed mechanisms with the exact same $(\epsilon, \delta)$ parameters as the original, your protocol should simulate a distribution that provides privacy with lower privacy budget, modifying (even if probably slightly) the distribution parameters. I don't see why this is not a distortion of the original distribution as claimed for other techniques. Therefore, my impression is that the work should either compare with a more extensive number of techniques, putting more illustrations of concrete privacy-accuracy-communication trade-offs on the table or better clarify why these comparisons are not relevant.
I appreciate the authors' thorough responses to my questions. I will keep my positive score.
I have no further questions