Privacy-aware compression for federated data analysis

Kamalika Chaudhuri, Chuan Guo, Mike Rabbat

Abstract

Federated data analytics is a framework for distributed data analysis where a server compiles noisy responses from a group of distributed low-bandwidth user devices to estimate aggregate statistics. This paper addresses the fundamental tension in these systems: how to collect useful data without invading user privacy or exceeding network bandwidth limits.

Introduction

In Federated Data Analysis (FDA), a central server aggregates data from thousands or millions of user devices to perform tasks such as traffic prediction or training speech-to-text models. This process faces two major hurdles: protecting sensitive user data via Local Differential Privacy (LDP) and managing slow upload speeds through data compression (quantization).

Traditionally, researchers treated these as separate problems—applying a privacy mechanism first and then compressing the result. However, this "two-step" approach is often inefficient and can introduce bias, preventing the server's estimate from ever converging to the true value. This paper, presented at UAI 2022, introduces the Minimum Variance Unbiased (MVU) mechanism, a framework that jointly optimizes for privacy and compression to achieve "asymptotic consistency."

The MVU Framework: Joint Optimization

The core contribution of this work is framing the co-design of privacy and compression as a mathematical optimization problem. The MVU mechanism seeks to minimize the variance of transmitted data while strictly satisfying LDP constraints and ensuring the client's mechanism remains unbiased.

MVU sampling matrices and output alphabets for varying privacy levels.

As illustrated in the figure above, the mechanism dynamically adjusts its sampling probability matrix ($P$) and output alphabet ($A$) based on the privacy parameter $\epsilon$. By designing these components together, the noise added for privacy effectively "doubles" as the quantization error, leading to much higher utility for the same "bit budget." The authors utilize "dithering" (a randomized rounding technique) to map continuous values to a discrete grid without introducing systematic bias.

Performance Evaluation

The authors evaluated the MVU mechanism against established benchmarks, including Randomized Response (RR) variants and the Laplace mechanism, using synthetic data for mean estimation and real-world datasets (MNIST, CIFAR-10) for federated learning tasks.

Variance comparison between MVU and baseline mechanisms across privacy budgets.

In scalar estimation tasks, MVU consistently achieved lower variance than existing methods like CLDP and Skellam. As shown in the comparison above, MVU (particularly with $b=3$ bits) approaches the performance of the uncompressed Laplace mechanism, even under strict privacy requirements (low $\epsilon$). In high-dimensional vector settings ($d=128$), MVU maintained high accuracy while using a fraction of the bandwidth required by competitors. Furthermore, when training models on MNIST and CIFAR-10, MVU outperformed specialized gradient compression algorithms like stochastic signSGD across nearly all privacy budgets.

Key Insights and Future Directions

A central insight of this research is that bias is the primary enemy in large-scale federated systems. While variance eventually washes out as more users join, bias remains constant. MVU prioritizes unbiasedness to ensure the server eventually learns the ground truth. Additionally, the authors observed a "privacy-compression coupling": as privacy requirements get stricter, the marginal benefit of high-resolution communication decreases, making joint optimization essential.

While the current MVU implementation faces computational complexity challenges for high-resolution quantization, it establishes a new standard for utility in privacy-preserving distributed analytics. Future work will focus on more efficient optimization solvers and extending these compressed mechanisms to Central Differential Privacy via secure aggregation.

Summary updated

Abstract

Federated data analytics is a framework for distributed data analysis where a server compiles noisy responses from a group of distributed low-bandwidth user devices to estimate aggregate statistics...
BibTeX
@inproceedings{chaudhuri2022privacy,
  author = {Kamalika Chaudhuri and Chuan Guo and Mike Rabbat},
  title = {{Privacy-aware compression for federated data analysis}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=IgD8aahFeVU},
}
Figure