Source-linked AI summary
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation
Peter Kairouz, Ziyu Liu, Thomas Steinke
TL;DR
Federated learning must train on sensitive data distributed across devices while limiting what the server can learn from updates. The paper combines discretization, on-device discrete Gaussian noise, and secure aggregation, with privacy analysis for noisy sums and finite-precision effects. Experiments show accuracy essentially matching central differential privacy with 16 or fewer bits of precision per value, while performance depends on communication and privacy budget.
Problem
Training on distributed, sensitive device data requires stronger privacy than federated learning alone provides, while preserving service utility and handling secure aggregation's finite precision.
Method
The paper discretizes and flattens client updates, adds independent discrete Gaussian noise, and uses modular secure aggregation with server-side reconstruction.
Results
Accuracy essentially matches central differential privacy with 16 or fewer bits of precision per value.
Takeaways & Limitations
With sufficient communication and privacy budget, DDGauss achieves better utility and can match the continuous Gaussian mechanism.
Takeaways & Limitations
A slight EMNIST performance gap remains for ε = 3 and k = 4, likely from rounding, modular clipping, and generic privacy-amplification bounds.
Abstract
from arXiv · showhide
We consider training models on private data that are distributed across user devices. To ensure privacy, we add on-device noise and use secure aggregation so that only the noisy sum is revealed to the server. We present a comprehensive end-to-end system, which appropriately discretizes the data and adds discrete Gaussian noise before performing secure aggregation. We provide a novel privacy analysis for sums of discrete Gaussians and carefully analyze the effects of data quantization and modular summation arithmetic. Our theoretical guarantees highlight the complex tension between communication, privacy, and accuracy. Our extensive experimental results demonstrate that our solution is essentially able to match the accuracy to central differential privacy with less than 16 bits of precision per value.
1 Introduction
The paper develops an end-to-end federated learning system that combines discretization, distributed discrete Gaussian noise, and secure aggregation to provide quantifiable privacy under finite-precision communication. Its analysis and experiments address privacy, accuracy, modular arithmetic, and communication trade-offs.
- System and contribution: The system discretizes client updates, adds discrete Gaussian noise on-device, and uses modular secure aggregation to protect federated learning data.The server observes only the noisy aggregate rather than individual client updates.
- Privacy analysis: The privacy analysis carefully characterizes sums of independent discrete Gaussians, which are not themselves discrete Gaussian, and supports concentrated differential privacy guarantees.The guarantees also degrade gracefully with the fraction of malicious or dropped-out clients.
- Accuracy and communication: The protocol analyzes discretization, privacy noise, and modular wrap-around jointly, exposing a trade-off between communication bits, privacy, and accuracy.Communication is O(d log m), while larger m reduces wrap-around and permits finer discretization.
- Accuracy and communication: Theoretical accuracy is, up to constants, the error expected for differential privacy in the central model.The paper supplements this theoretical analysis with empirical evaluation.
- Motivation and gap: The paper targets a gap in combining federated learning, secure aggregation, and differential privacy while accounting for finite precision and modular summation.Prior work often treated these technologies separately or ignored secure aggregation arithmetic at low bit-widths.
2 Preliminaries
The paper introduces divergence-based privacy definitions and properties used to analyze user-level differential privacy. It adopts concentrated and Rényi differential privacy alongside standard pure and approximate differential privacy.
- Privacy definitions: Rényi divergence quantifies the difference between probability distributions on a common domain.The definition assumes absolute continuity so the Radon–Nikodym derivative is well-defined.
- Divergence properties: Key divergence properties include additive composition for product distributions and non-increase under postprocessing.The paper also states a triangle-inequality-style bound through an intermediate distribution and a quasiconvexity property.
- Privacy definitions: User-level privacy treats each input entry as all records associated with one person.The guarantee applies to adding or removing one user’s records.
- Privacy definitions: The analysis uses the zero-concentrated variant of concentrated differential privacy because it has cleaner mathematical properties.The paper notes that the two concentrated-DP versions are loosely equivalent.
- Privacy definitions: The paper defines concentrated differential privacy using a bound on max divergence for neighboring user-level datasets.The neighboring relation is addition or removal of a single user’s records.
- Privacy definitions: Rényi differential privacy bounds order-α Rényi divergence between outputs on datasets differing by one user’s records.It is presented as a more general relaxation of concentrated differential privacy.
- Privacy definitions: The framework also distinguishes pure differential privacy with δ = 0 from approximate differential privacy with δ > 0.The paper relates these standard definitions to concentrated and Rényi privacy through conversion results.
3 Distributed Discrete Gaussian
This section develops privacy and utility guarantees for discrete Gaussian noise, including how sums of independent discrete Gaussians behave and how the results extend to multiple dimensions.
- Discrete Gaussian: The discrete Gaussian is defined as an integer-supported probability distribution with scale parameter σ and location parameter µ.It is denoted N_Z(µ, σ^2).
- Convolution: Unlike continuous Gaussians, sums of independent discrete Gaussians are not discrete Gaussians, but can be very close under reasonable parameters.For σ^2 = τ^2 = 3, the max-divergence closeness bound is ≤ 10^-12.
- Convolution: The convolution result extends by induction to sums of more than two independent discrete Gaussians.The many-variable result is used to characterize the distribution of aggregated noise.
- Privacy: Adding a sum of discrete Gaussians to a sensitivity-∆ query yields a concentrated differential privacy guarantee.For σ = ∆ = 1 and n = 10^4, the stated bound gives ε < 0.02.
- Multidimensional privacy: The privacy analysis extends to multidimensional discrete Gaussians through composition across coordinates.The resulting bound incorporates the dimension d and the sensitivity norm through terms involving ∥∆∥1 and τ.
- Utility: A discrete Gaussian has mean zero, variance below σ^2, and a utility bound based on its moment-generating behavior.These properties support analyzing the accuracy cost of discrete Gaussian noise.
4 Theoretical Utility Analysis
The utility analysis decomposes error into randomized rounding, privacy noise, and modular clipping, then combines bounds for the overall mechanism. Flattening controls coordinate concentration, while discretization granularity, modulus, and rounding parameters create communication–accuracy tradeoffs.
- Error decomposition: The analysis accounts separately for discretization, privacy noise, and modular clipping before combining their effects.These are the three identified sources of error in the protocol.
- Randomized rounding: Randomized rounding maps vectors to the grid γZ^d by independently rounding each coordinate while preserving the input mean.For each coordinate, the rounded value is one of the two neighboring grid points with probabilities chosen to preserve its expectation.
- Randomized rounding: Conditional randomized rounding resamples until the output lies in a permitted set, replacing a small privacy-failure probability with controlled conditioning error.If the acceptance probability is 1−β, the expected number of trials is (1−β)^-1.
- Parameter choice: The theory suggests β ≈ 1/√n because this balances bias and variance, while choosing β much smaller needlessly increases sensitivity.The paper also notes that the bound is worst-case and practical error may be considerably lower.
- Communication and accuracy: Reducing granularity γ lowers discretization error but increases the likelihood of modular wrap-around, while larger modulus increases communication.Communication is O(d log m), so modulus and granularity jointly govern the communication–accuracy tradeoff.
- Flattening and padding: Flattening randomizes coordinate magnitudes before modular clipping, avoiding large errors from concentrated coordinates, but random unitary matrices require Θ(d^2) time and space.A small-entry matrix with randomized signs is proposed instead; Walsh–Hadamard constructions can reduce padding overhead, with one construction reducing the worst-case factor to 1.5.
- Combined guarantee: The main theoretical result combines the three error analyses and yields mean squared error O(c^2d/ε^2) under the stated parameter conditions.The theorem’s decomposition identifies randomized rounding and modular clipping as contributing a term dnγ^2.
5 Experiments
Experiments evaluate DDGauss on distributed mean estimation and three federated-learning benchmarks, showing how communication, privacy, quantization, and modular clipping affect utility. With sufficient communication, DDGauss matches the continuous Gaussian baseline, while larger quantization parameters reduce wrapping at the cost of low-bit performance.
- Experimental setup: DDGauss is evaluated on distributed mean estimation and three public federated-learning benchmarks: EMNIST, Stack Overflow Tag Prediction, and Stack Overflow Next Word Prediction.The experiments compare DDGauss with the centralized continuous Gaussian mechanism under varying privacy and communication budgets.
- Distributed mean estimation: 16 bits per coordinate are sufficient for DDGauss to nearly match the Gaussian baseline’s utility in distributed mean estimation.The mean-estimation experiments report mean squared error with confidence intervals over multiple random dataset initializations.
- Federated learning: Increasing communication bits B and privacy budget ε improves DDGauss utility, and sufficient B allows it to match the continuous Gaussian baseline.This pattern holds both relative to the baseline and in absolute performance across the federated-learning experiments.
- Quantization and clipping trade-off: Larger k reduces modular wrapping but increases quantization error, so it can match the Gaussian baseline while worsening performance at low bit-widths.At k = 2, modular clipping creates a visible gap; increasing k closes that gap but enlarges the discretization granularity γ.
- Limitations: EMNIST shows a slight DDGauss–Gaussian gap at ε = 3 and k = 4, which the authors attribute partly to generic privacy-amplification bounds.The mismatch is described as minor and occurs in an extreme experimental setting alongside rounding and modular-clipping errors.
- Additional results: With sufficient communication, positive β values have insignificant utility impact, whereas bounded norm growth from conditional rounding can matter when communication is tight.For sufficient budgets, β = e^-1/2 ≈0.607 and β = 1/√n = 0.1 have similar performance and convergence speed.
6 Concluding Remarks
The protocol provides an end-to-end approach for federated learning with distributed differential privacy and secure aggregation, while identifying several directions for improvement.
- The protocol flattens and discretizes client model updates, adds discrete Gaussian noise, and applies secure aggregation for federated learning.
- It allows an untrusted server to perform complex learning tasks on decentralized, privacy-sensitive data while achieving the accuracy of a trusted server.
- Open questions include tightening privacy-amplification analysis for subsampled distributed discrete Gaussians.
- Further directions include reducing transform padding, developing private self-tuning parameter selection, and seeking better mechanisms.