Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Design

Chuan Guo, Kamalika Chaudhuri, Pierre Stock, Michael Rabbat

Overview

In Federated Learning (FL), a central server trains a machine learning model by aggregating updates from thousands of edge devices, such as smartphones. This setup faces a challenging "trilemma" of competing needs:

  1. Privacy: Updates must be obfuscated (typically via Differential Privacy) so the server cannot reconstruct a user's private data.
  2. Accuracy: The noise added to ensure privacy should not destroy the model's predictive performance.
  3. Communication: Updates for modern AI models are massive. Sending them over mobile networks requires heavy compression.

Researchers have developed Interpolated MVU (I-MVU), a new privacy-preserving compression mechanism for FL that tackles this trilemma. By relaxing the strict requirement for "unbiased" updates and interpolating in the natural parameter space of probability distributions, I-MVU achieves the accuracy of uncompressed models while using as little as one bit per parameter.

The Bottleneck of Strict Unbiasedness

Existing solutions, like the Minimum Variance Unbiased (MVU) mechanism, work well for small-scale problems but break down in high-dimensional settings. MVU insists on being strictly "unbiased"—meaning the expected average of the compressed updates perfectly equals the original value.

To achieve this, MVU uses a technique called "randomized dithering." Unfortunately, in high-dimensional spaces, this dithering causes the magnitude (or "norm") of the vectors to explode. This leads to highly pessimistic privacy accounting: to guarantee privacy for these exploded vectors, the system must add so much noise that the resulting model becomes practically useless.

Methods: The I-MVU Approach

The authors propose I-MVU based on a key insight: strict unbiasedness is a luxury. While mathematically convenient, it isn't strictly necessary for successfully training deep learning models.

Instead of dithering between discrete points to force unbiasedness, I-MVU views the compression process through the lens of Exponential Families:

  • Natural Parameter Interpolation: Rather than interpolating the probabilities of choosing a specific bit, I-MVU interpolates the natural parameters ($\eta = \log p$) of the underlying categorical distribution. This allows the mechanism to behave more like the standard Gaussian mechanism—the gold standard for Differential Privacy—while still outputting compressed bits.
  • Fisher Information Analysis: To prove the privacy of this new method, the authors utilized Fisher Information to measure how much "information" a single sample reveals. This sophisticated approach allowed them to create a much tighter privacy analysis for $L_2$-bounded vectors, providing a more honest look at privacy leakage in high dimensions.
  • Computational Scalability: Because it avoids the expensive rejection sampling required by previous dithering methods, I-MVU is computationally efficient enough to be used on massive foundation models.
Expectation and variance of MVU vs. I-MVU across different bitrates

Key Results and Performance

The authors evaluated I-MVU across several benchmarks, including standard image classification (MNIST, CIFAR-10), realistic non-IID federated datasets (FEMNIST), and high-dimensional fine-tuning tasks (ImageNet-pretrained WideResNet-28-10).

  • Matching the Gold Standard: I-MVU achieved nearly the exact same accuracy as uncompressed Gaussian and Laplace mechanisms, despite using only 1 bit per parameter.
  • Beating the Competition: It consistently outperformed other popular baselines like SignSGD (which is simple but often too biased) and Skellam (which is unbiased but requires up to 16x more bandwidth in the authors' experiments).
  • Unlocking Scale: On the WideResNet-28-10 model, I-MVU easily matched the performance of the non-compressed Gaussian mechanism. In contrast, previous MVU methods were too computationally expensive to even run on a model of this size.

Limitations and Future Work

While I-MVU represents a significant step forward for communication-efficient private FL, the authors note a few areas for future exploration:

  • Local vs. Central DP: Currently, the mechanism operates under Local Differential Privacy (LDP). It does not yet leverage "Secure Aggregation," a technique that could further reduce the privacy cost if the server is trusted to only see the sum of the updates.
  • The 1-Bit Floor: The current scalar-to-vector extension hits a compression floor at 1 bit per parameter. For massive models, researchers might want to achieve sub-1-bit compression (e.g., 0.1 bits per parameter). The authors suggest combining I-MVU with "sketching" or sparsification techniques to break this barrier.
  • Grid Point Selection: The choice of grid points for discretization in the current study was kept simple. Optimizing these points based on the actual data distribution could yield even better privacy-utility trade-offs in the future.

Summary updated

Abstract

In private federated learning (FL), a server aggregates differentially private updates from a large number of clients in order to train a machine learning model. The main challenge in this setting is balancing privacy with both classification accuracy of the learnt model as well as the number of bits communicated between the clients and server. Prior work has achieved a good trade-off by designing a privacy-aware compression mechanism, called the minimum variance unbiased (MVU) mechanism, that numerically solves an optimization problem to determine the parameters of the mechanism. This paper builds upon it by introducing a new interpolation procedure in the numerical design process that allows for a far more efficient privacy analysis. The result is the new Interpolated MVU mechanism that is more scalable, has a better privacy-utility trade-off, and provides SOTA results on communication-efficient private FL on a variety of datasets.
BibTeX
@inproceedings{guo2023privacy,
  author = {Chuan Guo and Kamalika Chaudhuri and Pierre Stock and Michael Rabbat},
  title = {{Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Design}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=Otdp5SGQMr},
}
Figure