# Exact Optimality of Communication-Privacy-Utility Tradeoffs in Distributed Mean Estimation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 41 references that are in the map.
- First posted on arXiv 8 Jun 2023.

## Builds on (most cited first, 26 of 26)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [Protection Against Reconstruction and Its Applications in Private Federated Learning](https://mlsanity.com/paper/1812.00984/) (2018)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Breaking the Communication-Privacy-Accuracy Trilemma](https://mlsanity.com/paper/2007.11707/) (2020)
- [Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters](https://mlsanity.com/paper/1810.00440/) (2018)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Sparse Random Networks for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2209.15328/) (2022)
- [rTop-k: A Statistical Estimation Approach to Distributed SGD](https://mlsanity.com/paper/2005.10761/) (2020)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy](https://mlsanity.com/paper/1606.05053/) (2016)
- [An Information-Theoretic Justification for Model Pruning](https://mlsanity.com/paper/2102.08329/) (2021)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Correlated quantization for distributed mean estimation and optimization](https://mlsanity.com/paper/2203.04925/) (2022)
- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (2022)
- [Locally Differentially Private Data Collection and Analysis](https://mlsanity.com/paper/1906.01777/) (2019)
- [Lossy Compression of Noisy Data for Private and Data-Efficient Learning](https://mlsanity.com/paper/2202.02892/) (2022)

## Built on by (most cited first, 9 of 9)

- [Communication Efficient Private Federated Learning Using Dithering](https://mlsanity.com/paper/2309.07809/) (2023)
- [Universal Exact Compression of Differentially Private Mechanisms](https://mlsanity.com/paper/2405.20782/) (2024)
- [Adaptive Compression in Federated Learning via Side Information](https://mlsanity.com/paper/2306.12625/) (2023)
- [Exactly Minimax-Optimal Locally Differentially Private Sampling](https://mlsanity.com/paper/2410.22699/) (2024)
- [Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy](https://mlsanity.com/paper/2405.02341/) (2024)
- [Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation](https://mlsanity.com/paper/2407.03289/) (2024)
- [Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networks](https://mlsanity.com/paper/2406.03766/) (2024)
- [Beyond Statistical Estimation: Differentially Private Individual Computation via Shuffling](https://mlsanity.com/paper/2406.18145/) (2024)
- [Trading-off Accuracy and Communication Cost in Federated Learning](https://mlsanity.com/paper/2503.14246/) (2025)

## Abstract (arXiv)

We study the mean estimation problem under communication and local differential privacy constraints. While previous work has proposed order-optimal algorithms for the same problem (i.e., asymptotically optimal as we spend more bits), exact optimality (in the non-asymptotic setting) still has not been achieved. In this work, we take a step towards characterizing the exact-optimal approach in the presence of shared randomness (a random variable shared between the server and the user) and identify several conditions for exact optimality. We prove that one of the conditions is to utilize a rotationally symmetric shared random codebook. Based on this, we propose a randomization mechanism where the codebook is a randomly rotated simplex -- satisfying the properties of the exact-optimal codebook. The proposed mechanism is based on a k-closest encoding which we prove to be exact-optimal for the randomly rotated simplex codebook.