# Breaking the Communication-Privacy-Accuracy Trilemma

arXiv: https://arxiv.org/abs/2007.11707 · HTML: https://mlsanity.com/paper/2007.11707/

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2020.

## Built on by (most cited first, 30 of 68)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Algorithms for the Communication of Samples](https://mlsanity.com/paper/2110.12805/) (2021)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Trading Off Privacy, Utility and Efficiency in Federated Learning](https://mlsanity.com/paper/2209.00230/) (2022)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Machine Unlearning of Federated Clusters](https://mlsanity.com/paper/2210.16424/) (2022)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Breaking the Trilemma of Privacy, Utility, Efficiency via Controllable Machine Unlearning](https://mlsanity.com/paper/2310.18574/) (2023)
- [Privacy-Aware Compression for Federated Data Analysis](https://mlsanity.com/paper/2203.08134/) (2022)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [Correlated quantization for distributed mean estimation and optimization](https://mlsanity.com/paper/2203.04925/) (2022)
- [Fast Optimal Locally Private Mean Estimation via Random Projections](https://mlsanity.com/paper/2306.04444/) (2023)
- [DP-REC: Private & Communication-Efficient Federated Learning](https://mlsanity.com/paper/2111.05454/) (2021)
- [FedMM: Saddle Point Optimization for Federated Adversarial Domain Adaptation](https://mlsanity.com/paper/2110.08477/) (2021)
- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (2022)
- [Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation](https://mlsanity.com/paper/2306.04924/) (2023)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Mean Estimation with User-level Privacy under Data Heterogeneity](https://mlsanity.com/paper/2307.15835/) (2023)
- [Universal Exact Compression of Differentially Private Mechanisms](https://mlsanity.com/paper/2405.20782/) (2024)
- [Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation](https://mlsanity.com/paper/2110.07751/) (2021)
- [QUIC-FL: Quick Unbiased Compression for Federated Learning](https://mlsanity.com/paper/2205.13341/) (2022)
- [Network Shuffling: Privacy Amplification via Random Walks](https://mlsanity.com/paper/2204.03919/) (2022)
- [Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Design](https://mlsanity.com/paper/2211.03942/) (2022)

## Abstract (arXiv)

Two major challenges in distributed learning and estimation are 1) preserving the privacy of the local samples; and 2) communicating them efficiently to a central server, while achieving high accuracy for the end-to-end task. While there has been significant interest in addressing each of these challenges separately in the recent literature, treatments that simultaneously address both challenges are still largely missing. In this paper, we develop novel encoding and decoding mechanisms that simultaneously achieve optimal privacy and communication efficiency in various canonical settings. In particular, we consider the problems of mean estimation and frequency estimation under varepsilon-local differential privacy and b-bit communication constraints. For mean estimation, we propose a scheme based on Kashin's representation and random sampling, with order-optimal estimation error under both constraints. For frequency estimation, we present a mechanism that leverages the recursive structure of Walsh-Hadamard matrices and achieves order-optimal estimation error for all privacy levels and communication budgets. As a by-product, we also construct a distribution estimation mechanism that is rate-optimal for all privacy regimes and communication constraints, extending recent work that is limited to b=1 and varepsilon=O(1). Our results demonstrate that intelligent encoding under joint privacy and communication constraints can yield a performance that matches the optimal accuracy achievable under either constraint alone.