mlsanityData to 14 Oct 2026

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

arXiv 2306.04924 ↗First posted 8 Jun 2023cs.LG cs.CR cs.DCcited by 9

Not on the map. Why?

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.

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

26 of 41 references.

References · 26

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  5. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 478
  6. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 256
  7. 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 158
  8. 2016Distributed Mean Estimation with Limited Communicationcited by 136
  9. 2018Protection Against Reconstruction and Its Applications in Private Federated Learningcited by 130
  10. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 107
  11. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
  12. 2018Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameterscited by 58
14 more
  1. 2021EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learningcited by 55
  2. 2021DRIVE: One-bit Distributed Mean Estimationcited by 52
  3. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  4. 2022Optimal Algorithms for Mean Estimation under Local Differential Privacycited by 36
  5. 2022Sparse Random Networks for Communication-Efficient Federated Learningcited by 32
  6. 2020rTop-k: A Statistical Estimation Approach to Distributed SGDcited by 27
  7. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  8. 2016Collecting and Analyzing Data from Smart Device Users with Local Differential Privacycited by 25
  9. 2021An Information-Theoretic Justification for Model Pruningcited by 25
  10. 2021Optimal Compression of Locally Differentially Private Mechanismscited by 22
  11. 2022Correlated quantization for distributed mean estimation and optimizationcited by 14
  12. 2022Private Frequency Estimation via Projective Geometrycited by 9
  13. 2019Locally Differentially Private Data Collection and Analysiscited by 5
  14. 2022Lossy Compression of Noisy Data for Private and Data-Efficient Learningcited by 1

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 6; 2025: 1.

9 papers.

  1. 2023Communication Efficient Private Federated Learning Using Ditheringcited by 9
  2. 2024Universal Exact Compression of Differentially Private Mechanismscited by 8
  3. 2023Adaptive Compression in Federated Learning via Side Informationcited by 6
  4. 2024Exactly Minimax-Optimal Locally Differentially Private Samplingcited by 5
  5. 2024Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacycited by 4
  6. 2024Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimationcited by 4
  7. 2024Privacy Preserving Semi-Decentralized Mean Estimation over Intermittently-Connected Networkscited by 2
  8. 2024Beyond Statistical Estimation: Differentially Private Individual Computation via Shufflingcited by 1
  9. 2025Trading-off Accuracy and Communication Cost in Federated Learningcited by 0