Research map / Federated learning and privacy / Differential privacy
Universal Exact Compression of Differentially Private Mechanisms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Poisson private representation (PPR), a universal, exact channel-simulation compressor for any local or central DP mechanism that also provides DP guarantees, and applies it to distributed mean estimation and metric privacy with experiments versus CSGM.
Problem
Communication-efficient compression of differential privacy mechanisms that exactly preserves the mechanism's output distribution (e.g., unbiasedness, Gaussianity) while retaining local and central DP guarantees.
Approach
Adds encoder-side randomness to the Poisson functional representation (sampling the index K with probabilities proportional to T̃_k^{-α}) so the output exactly follows the target mechanism, the compressed message stays private (2α·ε DP), and the message size is within a log gap of I(X;Z).
Key results
- For epsilon=1 compressing d=1000 to 50 bits, PPR achieves MSE 0.08173 vs CSGM 0.1231 (33.61% reduction).
- For epsilon=0.5 with 25 bits, PPR MSE 0.3011 vs CSGM 0.3877 (22.33% reduction).
- PPR with 400 bits matches the uncompressed Gaussian mechanism MSE, while CSGM needs 1000 bits.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PPR (α=2) instead of CSGM at 50 bits | DME with d=1000 and ε=1 · DME, ε=1, d=1000, 50 bits | MSE: 0.1231 -> 0.08173; 33.61% reduction | Helped |
| use PPR (α=2) instead of CSGM at 25 bits | DME with d=1000 and ε=0.5 · DME, ε=0.5, d=1000, 25 bits | MSE: 0.3877 -> 0.3011; 22.33% reduction | Helped |
| apply PPR to fixed-length chunks of 50 dimensions (ablation) | PPR for DME with d=1000 · DME, d=1000, ε range in the plot | MSE | Hurt |
Surprising findings
- PPR achieves lower MSE than CSGM at all tested epsilon and compression sizes, even though both are near-optimal.
Limitations
- Exact encoding running time is exponential in the mutual information; no polynomial-time algorithm for general mechanisms is likely.
- Chunking high-dimensional vectors is needed for practical runtime, with a small MSE penalty.
- Privacy penalty factor 2α on epsilon for pure DP.
Experimental setup
Datasets: synthetic Rademacher-style vectors (2*Ber(0.8)-1), n=500 clients, d=1000
Benchmarks: distributed mean estimation MSE on synthetic data
Metrics: mean squared error compression size in bits running time
Baselines: CSGM uncompressed Gaussian mechanism privUnit
Builds on: Poisson functional representation minimal random coding privUnit Coordinate subsampled Gaussian mechanism
Closest papers by meaning
- Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy (NeurIPS 2023 · similarity 0.91)
- Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation (NeurIPS 2023 · similarity 0.90)
- Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy (ICML 2024 · similarity 0.90)
- Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation (NeurIPS 2023 · similarity 0.90)
- Lossless Compression of Efficient Private Local Randomizers (ICML 2021 · similarity 0.89)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.