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. Two major challenges in this framework are privacy, since user data is often sensitive, and compression, since the user devices have low network bandwidth. Prior work has addressed these challenges separately by combining standard compression algorithms with known privacy mechanisms. In this work, we take a holistic look at the problem and design a family of privacy-aware compression mechanisms that work for any given communication budget. We first propose a mechanism for transmitting a single real number that has optimal variance under certain conditions. We then show how to extend it to metric differential privacy for location privacy use-cases, as well as vectors, for application to federated learning. Our experiments illustrate that our mechanism can lead to better utility vs. compression trade-offs for the same privacy loss in a number of settings.
Introduction
In Federated Data Analysis (FDA), a central server aggregates data from thousands or millions of user devices (clients) to compute statistics or train machine learning models. This decentralized approach is increasingly common as organizations seek to leverage edge data without centralizing raw, sensitive information. However, FDA faces two significant practical hurdles: privacy and communication bandwidth.
To protect user privacy, researchers typically employ Local Differential Privacy (LDP), where clients perturb their data with noise before transmission. To manage limited upload bandwidth, clients must compress this noisy data into a few bits. Traditionally, these two steps are handled sequentially: first, an LDP algorithm (like the Laplace mechanism) is applied, followed by a quantization step for compression.
This research identifies a critical flaw in the sequential approach: it often introduces bias. When noisy data is truncated or rounded to fit a specific bit budget, the resulting reports may not converge to the true value, even as the number of clients approaches infinity. This paper introduces the Minimum Variance Unbiased (MVU) mechanism, which co-designs privacy and compression to ensure "asymptotic consistency"—the property that the aggregate estimate remains unbiased regardless of the compression level.
The MVU Mechanism: Co-Designing Privacy and Compression
The core contribution of this work is the MVU framework. Rather than treating sanitization and compression as independent steps, MVU treats them as a single optimization problem. The goal is to minimize the variance of the client's output while strictly adhering to two constraints:
- LDP Constraint: The output must satisfy $\epsilon$-differential privacy.
- Unbiasedness Constraint: The expected value of the output must equal the input value.
The Strategy
The mechanism utilizes dithering, a randomized rounding technique that allows continuous values to be represented on a discrete grid without introducing systematic bias. By solving a mathematical optimization problem to determine a sampling probability matrix ($P$) and an output alphabet ($A$), the MVU mechanism identifies the most efficient way to represent noisy data within a fixed bit budget.
One of the most significant insights of this research is that privacy acts as a natural compressor. As the demand for privacy increases (lower $\epsilon$), the noise eventually dominates the signal. In these high-privacy regimes, adding more communication bits provides diminishing returns for accuracy, meaning very low-bit representations (even 1 or 2 bits) can be nearly as effective as infinite-precision reports.
Extensions to Vectors and Metric DP
The paper extends the MVU framework beyond simple scalar estimation to address more complex real-world applications:
- Metric Differential Privacy: This is particularly useful for location privacy, where the sensitivity of data is defined by physical distance. MVU can be adapted to provide guarantees that scale with the distance between points.
- High-Dimensional Vectors: For applications like Federated Learning (FL), where clients send gradient vectors to update a global model, the authors utilize Rényi Differential Privacy (RDP). This allows for tighter privacy accounting when composing the mechanism across multiple dimensions, ensuring that the high-dimensional noise does not destroy the utility of the gradients.
Experimental Results
The authors evaluated the MVU mechanism against several baselines using synthetic data and standard machine learning benchmarks (MNIST and CIFAR-10).
Scalar and Vector Estimation
In distributed mean estimation (DME) tasks, the MVU mechanism demonstrated superior efficiency. For scalar estimation, MVU using only 3 bits achieved lower variance than the standard Laplace mechanism (which requires high precision) at specific privacy levels. In high-dimensional vector spaces ($d=128$), MVU outperformed existing baselines like the Skellam mechanism and CLDP, often reducing Mean Squared Error (MSE) by an order of magnitude.
Federated Learning
When applied to training linear classifiers and convolutional neural networks, MVU showed significant advantages in the communication-constrained regime. Specifically, MVU with a 1-bit budget consistently outperformed stochastic signSGD, a popular specialized gradient compression method, across a wide range of privacy budgets. This suggests that the co-design of privacy and compression is more effective than applying state-of-the-art compression to a pre-existing privacy mechanism.
Conclusion and Future Work
The MVU mechanism represents a shift toward holistic design in federated systems. By prioritizing unbiasedness and optimizing for variance within a joint privacy-compression framework, it achieves a better trade-off between accuracy and bandwidth than traditional methods.
While highly effective, the approach currently faces computational challenges when scaling to very high-resolution quantization (large bit budgets). Additionally, while the scalar version is perfectly unbiased, the vector implementation introduces a small bias when attempting to preserve the vector norm. Future research may explore combining MVU with Secure Aggregation to transition from Local to Central Differential Privacy, potentially offering even greater utility for large-scale federated applications.
Summary updated