The Poisson binomial mechanism for secure and private federated learning

Wei-Ning Chen, Ayfer Özgür, Peter KairouzarXiv 2022 · DOI · arXiv

Introduction

In the landscape of private federated learning (FL), researchers and practitioners often grapple with a "trilemma" involving three competing priorities: privacy, utility, and communication efficiency. While Differential Privacy (DP) provides a rigorous framework for privacy, its standard implementation—adding continuous Gaussian or Laplace noise—presents significant challenges in distributed settings.

Specifically, most practical FL systems rely on Secure Aggregation (SecAgg) protocols to ensure that the central server only sees the aggregate update, not individual client data. However, SecAgg operates on finite groups using modular arithmetic, making it incompatible with continuous noise. Simply rounding or clipping continuous noise to fit these discrete structures introduces statistical bias, which can severely degrade the convergence of training algorithms like Stochastic Gradient Descent (SGD). Furthermore, traditional discrete DP schemes often suffer from a "privacy-bandwidth paradox," where increasing privacy (reducing $\epsilon$) requires adding more noise, which in turn consumes more communication bandwidth.

The Poisson Binomial Mechanism (PBM)

The Poisson Binomial Mechanism (PBM) is a novel discrete DP framework designed to solve these issues. Rather than the conventional "Value + Noise" paradigm, PBM treats the data values as parameters of a distribution. The mechanism follows a two-step process:

  1. Kashin’s Representation: High-dimensional local gradients are first transformed into a representation where information is spread evenly across coordinates. This transformation allows the mechanism to treat high-dimensional vectors as a series of 1D tasks without a significant loss in accuracy.
  2. Binomial Parameter Encoding: For each coordinate, a client maps their data value to the probability $p$ of a binomial distribution $Binom(m, p)$. The client then sends a sample from this distribution to the server.

Because the sum of independent binomial variables is a Poisson binomial variable, the server can aggregate these discrete samples via SecAgg and compute an unbiased estimate of the mean. This approach ensures native compatibility with cryptographic protocols while maintaining the statistical integrity of the updates.

Comparison of PBM with other discrete mechanisms across communication, MSE, and bias.

Key Advantages and Insights

Unbiasedness and Convergence

As shown in the comparison table above, PBM is uniquely positioned among discrete mechanisms for being natively unbiased. Most other discrete schemes require "modular clipping" to remain within SecAgg bounds, which introduces persistent bias. By remaining unbiased, PBM allows for convergence rates in private SGD (DDP-SGD) that match the best-known theoretical limits for non-private or continuous-noise settings.

Flipping the Privacy-Bandwidth Paradox

One of the most striking features of PBM is that communication costs actually decrease as privacy requirements become stricter. In high-privacy regimes (small $\epsilon$), the "support" or range of possible output values of the mechanism shrinks. This means that higher privacy levels require fewer bits to communicate, effectively turning a traditional disadvantage into a benefit for bandwidth-constrained environments.

Convergence to Gaussian Performance

A critical theoretical result of this work is that PBM achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism, which is considered the gold standard for utility in DP. As the communication budget (number of bits $m$) increases, the variance of the PBM estimator converges to that of the Gaussian mechanism.

Privacy-variance trade-offs for PBM compared to the Gaussian mechanism across different bit budgets.

Empirical Results and Future Work

In evaluations using synthetic Distributed Mean Estimation (DME), PBM demonstrated optimal trade-offs and significant communication efficiency. The per-client communication cost is $O(d \log n)$, outperforming previous discrete DP schemes like cpSGD or Skellam noise in high-privacy scenarios.

While the theoretical foundations are robust, future work remains to evaluate PBM on large-scale real-world federated learning datasets such as EMNIST or StackOverflow. Additionally, the authors note that establishing a formal lower bound on communication costs for DP-DME with SecAgg remains an open research question. Nonetheless, PBM represents a significant step forward in making secure, private, and efficient federated learning a practical reality.

Summary updated

Abstract

We introduce the Poisson Binomial mechanism (PBM), a discrete differential privacy mechanism for distributed mean estimation (DME) with applications to federated learning and analytics. We provide a tight analysis of its privacy guarantees, showing that it achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism. Our analysis is based on a novel bound on the R\'enyi divergence of two Poisson binomial distributions that may be of independent interest. Unlike previous discrete DP schemes based on additive noise, our mechanism encodes local information into a parameter of the binomial distribution, and hence the output distribution is discrete with bounded support. Moreover, the support does not increase as the privacy budget $\varepsilon \rightarrow 0$ as in the case of additive schemes which require the addition of more noise to achieve higher privacy; on the contrary, the support becomes smaller as $\varepsilon \rightarrow 0$. The bounded support enables us to combine our mechanism with secure aggregation (SecAgg), a multi-party cryptographic protocol, without the need of performing modular clipping which results in an unbiased estimator of the sum of the local vectors. This in turn allows us to apply it in the private FL setting and provide an upper bound on the convergence rate of the SGD algorithm. Moreover, since the support of the output distribution becomes smaller as $\varepsilon \rightarrow 0$, the communication cost of our scheme decreases with the privacy constraint $\varepsilon$, outperforming all previous distributed DP schemes based on additive noise in the high privacy or low communication regimes.
BibTeX
@misc{chen2022poisson,
  author = {Wei-Ning Chen and Ayfer Özgür and Peter Kairouz},
  title = {{The Poisson binomial mechanism for secure and private federated learning}},
  year = {2022},
  eprint = {2207.09916},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.09916},
}
Figure