mlsanityData to 14 Oct 2026

Breaking the Communication-Privacy-Accuracy Tradeoff with f-Differential Privacy

arXiv 2302.09624 ↗First posted 19 Feb 2023cs.CR cs.IT cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. The commonly adopted compression schemes introduce information loss into local data while improving communication efficiency, and it remains an open problem whether such discrete-valued mechanisms provide any privacy protection. In this paper, we study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of f-differential privacy (DP). More specifically, we advance the existing literature by deriving tight f-DP guarantees for a variety of discrete-valued mechanisms, including the binomial noise and the binomial mechanisms that are proposed for privacy preservation, and the sign-based methods that are proposed for data compression, in closed-form expressions. We further investigate the amplification in privacy by sparsification and propose a ternary stochastic compressor. By leveraging compression for privacy amplification, we improve the existing methods by removing the dependency of accuracy (in terms of mean square error) on communication cost in the popular use case of distributed mean estimation, therefore breaking the three-way tradeoff between privacy, communication, and accuracy. Finally, we discuss the Byzantine resilience of the proposed mechanism and its application in federated learning.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 30 of its 47 references that are in the map. First posted on arXiv 19 Feb 2023.

Builds on

30 of 47 references.

References · 30

  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. 2017Renyi Differential Privacycited by 650
  4. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 571
  5. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 256
  6. 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 158
  7. 2016Concentrated Differential Privacycited by 144
  8. 2016Distributed Mean Estimation with Limited Communicationcited by 136
  9. 2020The Discrete Gaussian for Differential Privacycited by 135
  10. 2021The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregationcited by 128
  11. 2019Deep Learning with Gaussian Differential Privacycited by 114
  12. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
18 more
  1. 2021The Skellam Mechanism for Differentially Private Federated Learningcited by 68
  2. 2019Stochastic Sign Descent Methods: New Algorithms and Better Theorycited by 49
  3. 2020Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressorcited by 45
  4. 2020Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFTcited by 43
  5. 2022The Fundamental Price of Secure Aggregation in Differentially Private Federated Learningcited by 39
  6. 2020Stochastic-Sign SGD for Federated Learning with Theoretical Guaranteescited by 35
  7. 2019Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithmscited by 29
  8. 2021Federated f-Differential Privacycited by 29
  9. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  10. 2016Collecting and Analyzing Data from Smart Device Users with Local Differential Privacycited by 25
  11. 2021Optimal Compression of Locally Differentially Private Mechanismscited by 22
  12. 2022Privacy-Aware Compression for Federated Data Analysiscited by 17
  13. 2020Sharp Composition Bounds for Gaussian Differential Privacy via Edgeworth Expansioncited by 13
  14. 2018signSGD with Majority Vote is Communication Efficient And Fault Tolerantcited by 11
  15. 2022Identification, Amplification and Measurement: A bridge to Gaussian Differential Privacycited by 7
  16. 2019Locally Differentially Private Data Collection and Analysiscited by 5
  17. 2021Bit-efficient Numerical Aggregation and Stronger Privacy for Trust in Federated Analyticscited by 4
  18. 2022Differentially Private Multivariate Statistics with an Application to Contingency Table Analysiscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 1.

3 papers.

  1. 2024Attack-Aware Noise Calibration for Differential Privacycited by 8
  2. 2024TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Datacited by 2
  3. 2026ERIS: Enhancing the Privacy-Utility-Scalability Trade-Off in Federated Learning via Federated Shard Aggregationcited by 1