The Skellam Mechanism for Differentially Private Federated Learning

Naman Agarwal; Peter Kairouz; Ziyu Liu

Source-linked AI summary

The Skellam Mechanism for Differentially Private Federated Learning

Naman Agarwal, Peter Kairouz, Ziyu Liu

arXiv:2110.04995v2Oct 11, 2021cs.LGcs.CRcs.DSmath.PRstat.ML

TL;DR

The paper addresses the need for a discrete privacy mechanism suitable for federated learning with secure aggregation and communication constraints. It introduces and analyzes the multi-dimensional Skellam mechanism, then shows that its privacy-accuracy trade-offs match the continuous Gaussian mechanism while retaining practical discrete-mechanism advantages.

Problem
Continuous Gaussian mechanisms create numerical and distributed-computation challenges, motivating a discrete alternative for privacy-preserving learning.
Method
The paper introduces multi-dimensional Skellam noise as the difference of two independent Poisson random variables and analyzes its privacy through privacy-loss evaluation and Rényi divergence.
Results
The Skellam mechanism matches the continuous Gaussian mechanism's privacy-accuracy trade-offs, with RDP guarantees at most 1 + O(1/µ) times worse theoretically.
Takeaways & Limitations
Skellam is a practical alternative to distributed discrete Gaussian because it is closed under summation, uses widely available Poisson samplers, and fits cryptographic protocols.
Takeaways & Limitations
The multi-dimensional analysis has room for improvement, and the main theoretical restriction that α be an integer is technical.

Abstract

from arXiv · show

We introduce the multi-dimensional Skellam mechanism, a discrete differential privacy mechanism based on the difference of two independent Poisson random variables. To quantify its privacy guarantees, we analyze the privacy loss distribution via a numerical evaluation and provide a sharp bound on the Rényi divergence between two shifted Skellam distributions. While useful in both centralized and distributed privacy applications, we investigate how it can be applied in the context of federated learning with secure aggregation under communication constraints. Our theoretical findings and extensive experimental evaluations demonstrate that the Skellam mechanism provides the same privacy-accuracy trade-offs as the continuous Gaussian mechanism, even when the precision is low. More importantly, Skellam is closed under summation and sampling from it only requires sampling from a Poisson distribution -- an efficient routine that ships with all machine learning and data analysis software packages. These features, along with its discrete nature and competitive privacy-accuracy trade-offs, make it an attractive practical alternative to the newly introduced discrete Gaussian mechanism.

1 Introduction

The paper motivates a discrete alternative to Gaussian mechanisms by addressing numerical, distributed-computation, and sampling limitations. It introduces Skellam noise, analyzes its privacy, and evaluates it in communication-constrained federated learning.

Motivation: The continuous Gaussian mechanism is difficult to represent exactly and cannot directly support secure aggregation based on modular arithmetic.These issues motivate discrete mechanisms for distributed privacy applications.
Motivation: The binomial mechanism can have infinite privacy loss, while the discrete Gaussian is not closed under summation and lacks widely available samplers.These drawbacks complicate distributed analysis and production use.
Contribution: Skellam noise is the difference of two independent Poisson random variables, is closed under summation, and can be sampled using widely available Poisson routines.Its discrete representation also fits cryptographic protocols and may reduce communication.
Privacy analysis: The analysis numerically evaluates privacy loss and proves a sharp Rényi-divergence bound for shifted multi-dimensional Skellam distributions.For sensitivities ∆1 and ∆2, the mechanism achieves an RDP guarantee parameterized by its variance µ.
Privacy analysis: The RDP guarantees are at most 1 + O(1/µ) times worse than those of the Gaussian mechanism.This provides the paper's principal theoretical comparison with the continuous Gaussian mechanism.
Experiments: In communication-constrained federated learning, the method matches the continuous Gaussian baseline under tight privacy and communication budgets.The evaluation covers distributed mean estimation and Federated EMNIST and Stack Overflow.

2 Preliminaries

This section defines differential privacy and related accounting frameworks, then specifies user-level neighboring datasets and sensitivity for the paper's comparisons. It also states the discrete Gaussian mechanism's RDP guarantee.

Differential privacy: Differential privacy requires neighboring datasets to produce similar output probabilities for every measurable set, subject to ε and δ.The neighboring relation used in the formal definition is based on adding or removing one user's records.
Privacy model: The experiments use user-level privacy, where neighboring datasets differ by adding or removing all records associated with one user.This is stronger than item-level privacy when users contribute multiple records.
Privacy accounting: Rényi differential privacy bounds Rényi divergence between mechanism outputs on neighboring datasets and supports tight privacy accounting.RDP can be converted to (ε, δ)-DP through the stated conversion lemma.
Sensitivity: For a query function f, ∆p sensitivity is the maximum ℓp distance between outputs on neighboring datasets.The paper uses these sensitivities when comparing Skellam and discrete Gaussian mechanisms.
Discrete Gaussian comparison: The discrete Gaussian mechanism with integer-valued queries and noise variance µ achieves (α, α∆2^2/(2µ))-Rényi differential privacy.The paper uses these guarantees as a comparison point for Skellam.

3 The Skellam Mechanism

The Skellam mechanism extends discrete noise to multidimensional integer-valued queries, supports tight privacy accounting through privacy loss distributions and Rényi differential privacy, and retains Gaussian-like guarantees up to lower-order terms.

Definition: The multidimensional Skellam distribution is defined over Z^d with independent coordinates, and each Skellam variable is the difference of two independent Poisson variables.Its summation closure follows from adding the means and variances of the component Skellam variables.
Definition: The Skellam mechanism adds Skellam noise to integer-valued queries, with its total ℓ2 error bounded in terms of the mechanism variance.The supplied passage introduces the error bound but does not include its complete displayed expression.
Tight Numerical Accounting via Privacy Loss Distributions: Privacy loss distributions characterize (ε, δ)-DP and compose through convolution, enabling numerical accounting for repeated applications of the Skellam mechanism.For scalar queries, the privacy-loss distribution can be characterized from the discrete symmetric Skellam distribution and used for tight accounting.
Tight Numerical Accounting via Privacy Loss Distributions: The direct scalar analysis compares Skellam with Gaussian and discrete Gaussian accounting, while multidimensional queries require an RDP bound because direct extensions can depend prohibitively on ℓ1 sensitivity.The supplied passages identify composition and high-dimensional sensitivity as central challenges for learning applications.
Tight Accounting via Rényi Differential Privacy: Theorem 3.5 establishes a sharp RDP guarantee for the Skellam mechanism, and the multidimensional corollary depends on both ℓ1 and ℓ2 sensitivities.The proof uses bounds on ratios of modified Bessel functions and follows the broad structure of the Gaussian RDP proof.
Tight Accounting via Rényi Differential Privacy: The Skellam RDP bound is at most 1 + O(1/µ) worse than the Gaussian bound, while the authors note that the integer-order restriction on α has negligible practical effect.The analysis contrasts this lower-order gap with looser bounds that introduce a constant multiplicative factor over Gaussian RDP.

4 Applying the Skellam Mechanism to Federated Learning

The paper applies Skellam noise to privacy-preserving federated learning under communication constraints, using discretization, scaling, secure aggregation, and distributed local noise. The approach exploits Skellam’s summation closure and practical sampling advantages while targeting privacy, error, and communication trade-offs.

Federated learning requires balancing differential privacy, expected ℓ2 error, and average communication bits per coordinate.
Client updates are discretized by scaling and stochastic rounding before private aggregation and conversion back to real values.The scaled variance is re-parameterized as s^2µ.
Larger scaling s reduces rounding-induced norm inflation and the extra noise required for the same privacy level.The paper uses conditional rounding to obtain a bounded norm for the scaled integer vector.
Distributed Skellam adds noise locally with variance µ/n, then securely sums noisy updates using SecAgg so only the noisy aggregate is revealed.Modulo operations are treated as post-processing of an already private query.
Skellam remains attractive under tight communication constraints because it is closed under summation and can be sampled using widely available Poisson routines.These properties avoid the distributed-sum divergence and software-access barriers associated with DDGauss.

5 Empirical Evaluation

The empirical evaluation studies distributed mean estimation and federated learning with distributed Skellam under privacy and communication constraints. Across the reported experiments, Skellam matches Gaussian performance and performs consistently with DDGauss in realistic regimes.

Experimental setup: Experiments evaluate distributed mean estimation and federated learning using RDP accounting, random orthogonal transformations, quantization, and secure aggregation.
Distributed mean estimation: The distributed mean-estimation experiment compares private Skellam estimates with a tightly accounted analytic Gaussian baseline across bit-width, dimension, and client-count settings.
Distributed mean estimation: Skellam matches Gaussian in mean-estimation error across the evaluated bit-width, dimension, and client-count settings.The reported metric is MSE, ∥b̂x − x̄∥2^2/d, with 95% confidence intervals over 10 dataset initializations.
Federated learning: The federated-learning evaluation covers Federated EMNIST, Shakespeare, and Stack Overflow next-word prediction with different privacy and bit-width values.
Federated learning: Skellam performs as well as Gaussian and consistently matches DDGauss in the reported federated-learning regimes.EMNIST and Shakespeare use average test accuracy over the last 100 rounds; Stack Overflow uses top-1 test accuracy.

6 Conclusion

The paper concludes that its sharp privacy analysis and experiments establish Skellam as a practical alternative to Gaussian and distributed discrete Gaussian mechanisms. It also identifies analytical improvements and implementation misuse as important boundaries.

The paper derives a sharp RDP bound and reports that Skellam matches Gaussian and discrete Gaussian in practical settings.
Skellam’s summation closure and widely available efficient samplers support extension from central to distributed differential privacy.
The discrete mechanism may provide communication savings and reduce susceptibility to attacks exploiting floating-point arithmetic.The passage states these as potential benefits rather than established outcomes.
Future work includes complete privacy-loss-distribution characterization and targeted analysis of RDP amplification by sampling.
Incorrect noise sampling or an extremely small scaling factor could produce nonexistent privacy guarantees for users’ data.

A Proof of Lemma 3.7

The proof of Lemma 3.7 handles shifted Skellam cases by splitting the analysis according to the sign and range of X, then applying bounds on inverse hyperbolic sine and modified Bessel terms. The argument establishes the lemma for Δ≥0, with the negative case obtained by switching X to −X.

Conclusion: The proof establishes the statement for Δ ≥ 0 and notes that an analogous argument for Δ ≤ 0 follows by replacing X with −X.This symmetry handles the remaining sign of the shift.
Case analysis: The proof divides the analysis into cases based on X, including X ≥ αΔ, X ≤ 0, and X ∈ [0, Δ/2].The case split is needed to handle different signs and ranges of the shifted variable.
Analytic bounds: The argument repeatedly applies arcsinh(y) − arcsinh(x) ≤ y − x for 0 ≤ x ≤ y, together with arcsinh(x) ≤ x.These inequalities simplify terms arising in the case-specific bounds.
Auxiliary lemmas: Lemma A.2 is applied to intermediate expressions, including terms involving Δ2 + 2νΔ, before collecting and simplifying them.Several case calculations use this lemma to control the resulting sums.
Auxiliary lemmas: Lemma A.1 supplies upper and lower bounds on δ2 and δ0 used to simplify the expressions in the case analysis.The proof explicitly invokes Lemma A.1 after deriving intermediate inequalities.

B Additional Results

Additional experiments evaluate the mechanisms on Shakespeare and Federated EMNIST under varied privacy, precision, and training settings. On Shakespeare, Skellam matches DDGauss across settings, while a small gap from Gaussian is attributed to modular clipping error from secure aggregation.

Shakespeare: Shakespeare uses 715 clients, predicts the next word, and trains for 1200 rounds with 100 clients per round.Because the dataset is small, privacy is also reported using a hypothetical population size N = 10^6.
Shakespeare: Skellam matches DDGauss across Shakespeare settings, while both show a slight gap from Gaussian likely caused by modular clipping error from SecAgg.The optimal clipping value is c = 0.5 for ε = 7.5 and c = 0.25 otherwise.
Shakespeare: Figure 6 summarizes Shakespeare test accuracies averaged over the last 100 rounds across different ε and b values for k = 3 and k = 4.The experiments use δ = 10^-6 and a hypothetical population size N = 10^6.
Federated EMNIST: Increasing k reduces scaling error while increasing quantization error, closing the Gaussian gap observed for Skellam and DDGauss at k = 3.Figure 11 additionally reports validation accuracy over 1600 rounds for k = 4.

C.2 Datasets

The additional dataset materials describe the public federated datasets, their standard splits, and the reporting conventions used for test and validation performance. They also identify the mechanisms represented in the supplementary comparisons.

Datasets: The experiments use public Federated EMNIST, Stack Overflow Next Word Prediction, and Shakespeare datasets available through TensorFlow Federated.The datasets are described as appropriately anonymized and without personally identifiable information.
Dataset splits: Federated EMNIST and Shakespeare use training and test splits, while Stack Overflow NWP uses training, validation, and test splits.Performance is reported on the test set for EMNIST and Shakespeare and on validation or test sets as specified for Stack Overflow NWP.
Mechanism comparisons: The supplementary comparison labels include DDGauss at b = 12, 14, and 16, Skellam at b = 12, 14, and 16, and Gaussian.These labels identify the mechanisms and precision settings compared in the plots.
Reporting conventions: Figure 7 reports Shakespeare test accuracy over 1200 training rounds, averaging results every 100 rounds with k = 3.The figure uses a hypothetical population size N = 10^6 and δ = 10^-6.

C.3 Other Implementation Details

The implementation details cover privacy amplification assumptions, model architecture, precision trade-offs, and Federated EMNIST reporting. Privacy amplification relies on client subsampling, while the choice of k balances modular clipping and quantization errors.

Privacy amplification: Privacy amplification assumes clients can be sampled uniformly and their identities hidden from the sampler, conditions that may not hold in federated learning.The guarantees remain applicable to external analysts requesting the trained model from the central aggregator.
Experimental protocol: The experiments fix client-data and parameter-initialization seeds, without repeating federated learning experiments across multiple seeds.Reported accuracies are still averaged over the last 100 rounds for the specified evaluation sets.
Federated EMNIST: Figure 8 summarizes Federated EMNIST test accuracies averaged over the last 100 rounds across ε and b for k = 3 and k = 4.The figure uses δ = 1/N.
Precision trade-offs: Increasing k trades reduced modular clipping error for increased quantization error in the implementation.This trade-off is examined through the effect of k on accuracy.

D.1 Ease of Sampling

Skellam is practical to sample because it relies on Poisson sampling routines already available in mainstream numerical and machine-learning software. The experiments compare Skellam with discrete Gaussian and Gaussian mechanisms across federated-learning settings.

Ease of Sampling: Poisson samplers for Skellam are widely available in NumPy, TensorFlow, and PyTorch.This availability is presented as a practical advantage for DP and machine-learning practitioners.
Ease of Sampling: The experiments evaluate test accuracies on Federated EMNIST over 1500 training rounds with k = 3.The figure reports δ = 1/N and averages accuracy every 100 rounds.
Ease of Sampling: Skellam sampling was up to 1000× faster than one discrete Gaussian implementation and up to 40% faster than another in TensorFlow eager execution.The first discrete Gaussian implementation was not vectorized, while the second remained slower in the reported comparison.

D.2 Closure Under Summation

Closure under summation simplifies distributed privacy accounting and avoids divergence terms that can grow with the number of clients. In a large-client example, Skellam closely matches Gaussian RDP while DDGauss incurs a much larger divergence and may require communication-costly scaling.

Closure Under Summation: The discrete Gaussian’s divergence errors grow with client count, whereas Skellam has no such dependence in the cited comparison.This matters particularly for massively distributed settings such as federated analytics.
Closure Under Summation: For n = 10000, σc = 50, and α = 2, Gaussian and Skellam RDP are 4 × 10−4 and 4.0036 × 10−4, respectively.The corresponding DDGauss RDP is > 723, a factor of > 10^6 larger, due to the sum divergence term τ.
Closure Under Summation: Scaling raw values and noise variances can alleviate DDGauss’s divergence issue but introduces additional communication costs.The trade-off arises in the large-client distributed setting.
Closure Under Summation: Skellam privacy accounting requires tracking only variance, simplifying switches between central and distributed DP implementations.Discrete Gaussian accounting additionally tracks client number, client dimensions, variance, and a divergence term.