PaperlayerView exact revision on arXiv

Source-linked AI summary

The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation

Peter Kairouz, Ziyu Liu, Thomas Steinke

arXiv:2102.06387v4cs.LGcs.DSstat.ML

TL;DR

Privacy-preserving learning on data distributed across user devices is difficult to combine with secure aggregation in a rigorous, principled system. The paper presents such a system using discretized updates and distributed discrete Gaussian noise, and reports matching central differential privacy accuracy with 16 or fewer bits of precision per value.

  • Problem

    Although privacy technologies for training on sensitive, device-distributed data have been studied extensively on their own, rigorous and principled understanding of how to combine them remains limited.

    Source: §1 · p. 2

  • Method

    The protocol discretizes and flattens client updates, adds independent discrete Gaussian noise on each device, and uses secure aggregation to reveal only their sum.

    Source: §1.1 · p. 3, §6 · p. 47

  • Results

    The solution essentially matches central differential privacy accuracy with 16 or fewer bits of precision per value.

    Source: §6 · p. 47

  • Takeaways & Limitations

    The protocol allows an untrusted server to perform complex learning on decentralized, privacy-sensitive data while achieving the accuracy of a trusted server.

    Source: §6 · p. 47

    On EMNIST, a slight performance gap from Gaussian remains at ε = 3 and k = 4; the authors believe generic privacy amplification bounds contribute to this mismatch alongside rounding and modular clipping errors.

    Source: §5.2.4 · p. 45

Abstract

from arXiv · show

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 presents an end-to-end federated learning system that discretizes client updates, adds discrete Gaussian noise, and uses secure aggregation to provide distributed differential privacy. Its analysis addresses privacy, accuracy, and modular arithmetic, while experiments assess the communication–utility tradeoff.

1 Introduction

  • Clients discretize updates, add discrete Gaussian noise, and send them for modular secure summation, combining federated learning, secure aggregation, and distributed differential privacy.The paper describes this as a first concrete step toward a communication-efficient FL system with distributed DP and SecAgg guarantees.Source: §1 · p. 2

1.1 Main Results

  • The sum of independent discrete Gaussians is not itself a discrete Gaussian, but is extremely close in the relevant regime, underpinning the differential privacy guarantee.The algorithm’s privacy theorem states a 2ε²-concentrated differential privacy guarantee under its secure-aggregation assumption.Source: §1.1 · pp. 3, 5, 6, Then Algorithm 1 satisfies 1 · p. 6
  • Client computation is nearly linear in dimension and communication costs O(d log m) bits, with larger modulus m trading increased communication for finer discretization and less wrap-around.The paper notes that choosing m also affects rounding error through the available discretization precision.Source: §1.1 · p. 4
  • The theoretical accuracy is, up to constants, the error expected under central-model differential privacy; the analysis accounts for discretization, privacy noise, and modular wrap-around.The paper identifies these as three interacting error sources and analyzes their effects.Source: §1.1 · p. 4, Then Algorithm 1 satisfies 1 · p. 7

Then Algorithm 1 satisfies 1

  • 16 bits per coordinate nearly match the Gaussian baseline’s utility for distributed mean estimation, while the method performs well under tight privacy budgets on Federated EMNIST and Stack Overflow.The FL comparison uses generic RDP amplification for this method and precise RDP analysis for the subsampled Gaussian mechanism.Source: Then Algorithm 1 satisfies 1 · p. 7

1.2 Related Work

  • Prior work often overlooks finite precision and modular summation in SecAgg; this paper contributes a strategy for mapping real-valued vectors to vectors over Z_m.Source: Federated Learning · pp. 8–9
  • Unlike cpSGD’s binomial mechanism, the discrete Gaussian approach provides concentrated differential privacy suitable for composition and subsampling analysis, and accounts for modular arithmetic.The paper says cpSGD does not consider modular arithmetic, complicating its combination with secure aggregation.Source: Federated Learning · p. 9
  • The paper carefully analyzes sums of discrete Gaussians and reports that its privacy guarantees degrade gracefully with malicious or dropped-out clients, avoiding reliance on a shared noise seed.A single honest-but-curious client could break privacy under the shared-seed approach described in prior work.Source: Federated Learning · pp. 9–10

2 Preliminaries

This section introduces Rényi divergence as a tool for quantifying privacy and defines user-level privacy notions used throughout. It also states how divergence-based and event-based privacy guarantees relate to the framework.

2 Preliminaries

  • Rényi divergence compares distributions on a common domain when the first is absolutely continuous with respect to the second, and is defined for orders α > 1.The paper also uses divergence between random variables to mean divergence between their distributions.Source: §2 · p. 10, We also define · p. 10

We also define

  • Rényi divergence adds across corresponding product distributions and does not increase under deterministic or independently randomized postprocessing.These properties support composition and subsequent processing of privacy-preserving outputs.Source: We also define · p. 11
  • Privacy is defined at the user level: neighboring inputs differ by adding or removing all records belonging to one person, rather than a single record.The paper uses add/remove adjacency rather than replacement; group privacy implies a replacement guarantee with a doubled privacy parameter.Source: We also define · p. 11
  • Concentrated differential privacy bounds order-∗ Rényi divergence, while (α, ε)-Rényi differential privacy requires order-α divergence at most ε for neighboring inputs.The paper adopts the Bun and Steinke version of concentrated differential privacy, also known as zCDP.Source: We also define · p. 12
  • The section defines (ε, δ)-differential privacy through event probabilities, distinguishing pure privacy when δ = 0 from approximate privacy when δ > 0.It identifies the original pure-DP definition with and approximate DP with.Source: We also define · p. 12

3 Distributed Discrete Gaussian

The section develops privacy guarantees for integer-supported discrete Gaussian noise, including sums of independent noises and their multidimensional extension, and gives a variance bound for utility. It also shows that convolution is close to a discrete Gaussian under stated parameter conditions.

3 Distributed Discrete Gaussian

  • The discrete Gaussian is supported on the integers, and Theorem 10 establishes a differential-privacy guarantee for shifts of its location parameter.The section identifies this distribution as the basis of its privacy guarantee.Source: §3 · p. 13
  • When σ² = τ² = 3, the sum of two independent discrete Gaussians is within 10^-12 in max divergence of a discrete Gaussian with variance σ² + τ².The theorem gives this closeness under the condition 1/σ² + 1/τ² ≤ 8; the authors describe max divergence as the strongest closeness measure they could hope for.Source: §3 · pp. 13, 16
  • The two-noise convolution result extends by induction to sums of more than two independent discrete Gaussians.The section states a many-noise convolution corollary for n independent variables.Source: §3 · p. 16
  • For n independent discrete Gaussians with σ = Δ = 1, adding their sum to a sensitivity-Δ query gives ε < 0.02 when n = 10^4.The section derives privacy guarantees for sums by combining the convolution result with the privacy guarantee for a single discrete Gaussian.Source: §3 · pp. 16–17
  • Proposition 14 extends the privacy guarantee for sums to d-dimensional discrete Gaussian vectors and queries with ℓp sensitivity, using composition across coordinates.The noise coordinates are independent across users and dimensions.Source: §3 · p. 17
  • A discrete Gaussian with scale σ has mean 0 and variance less than σ².The utility lemma also states a bound on its tail expectation, but the supplied passage truncates that expression.Source: §3 · p. 18

4 Theoretical Utility Analysis

This section analyzes utility error from discretization, privacy noise, and modular clipping, bounding randomized-rounding error and using an efficiently computable flattening transform to reduce clipping error. It gives a final mean squared error bound of O(c2d/ε2).

4.1 Randomized Rounding

  • Randomized rounding independently selects grid values with mean equal to each input coordinate, preserving the vector mean and expected L1 norm.The analysis also bounds increases in the Euclidean norm in expectation and with high probability.Source: §4.1 · p. 18
  • Resampling rounded outputs outside an allowed set trades a small probability of inaccuracy for avoiding a privacy-failure probability from excessive norm.Conditional randomized rounding repeats until the output lies in the set; its expected number of trials is the reciprocal of the acceptance probability.Source: §4.1 · pp. 20–21
  • The theory suggests setting β ≈ 1/√n to balance bias and variance; smaller β needlessly raises sensitivity, while larger values may improve practical accuracy.The error bound is worst-case, so the authors consider β = e^-1/2 in practice; reducing γ lowers discretization error but increases communication.Source: §4.1 · p. 24

4.2 Flattening

  • Flattening addresses large modular-clipping errors when inputs or their sum concentrate on one coordinate by applying a random-sign transform and then an invertible matrix.The transformation is undone by the server after aggregation.Source: §4.2 · pp. 25–26
  • After scaling appropriately, Walsh–Hadamard matrices attain optimal ρ = 1; their fast transform computes matrix-vector products in O(d log d) operations, but requires power-of-two d, so zero-padding may nearly double dimension.Source: §4.2 · p. 26
  • For arbitrary dimensions, the discrete cosine transform supports O(d log d) products with ρ = 2, while the complex discrete Fourier transform achieves ρ = 1 and requires padding at most one zero.The Fourier option encodes two real entries as one complex entry and requires an even dimension.Source: §4.2 · p. 27
  • O(d log d) operations suffice to compute the discrete Fourier transform for any d, not only powers of 2.The exact efficiency constants depend on d.Source: §4.2 · p. 31

4.3 Modular Clipping

  • Modular clipping leaves A(x) unchanged when it lies in the clipping interval; the analysis uses centered subgaussian coordinates to bound the chance of leaving that interval.The operation is homomorphic, so clipping a sum agrees with summing clipped values and clipping the result.Source: §4.3 · p. 31

4.4 Putting Everything Together

  • Under β ≤ 1/√n and the stated bound on σ̂²(x), the error bound separates privacy cost dnσ² ≈ d c²/ε² from rounding and clipping cost dnγ².The analysis assumes β and σ̂ are sufficiently small to avoid additional terms.Source: §4.4 · pp. 33, 35
  • The combined analysis yields mean squared error O(c2d/ε2).Source: §4.4 · p. 39

5 Experiments

Experiments evaluate DDGauss on distributed mean estimation and federated learning, testing utility against the continuous Gaussian mechanism under privacy guarantees and varying communication budgets.

5.1 Distributed Mean Estimation

  • DDGauss achieves a good communication-utility trade-off in mean estimation and matches Gaussian performance with sufficient bit-width; larger k reduces clipping but worsens low-bit performance through rounding.At k = 2, modular clipping creates a visible gap; increasing k reduces wrapping and closes the high-bit-width gap.Source: §5.1 · p. 40, Figure 2 · p. 41

5.2.1 Datasets

  • The FL evaluation covers Federated EMNIST, Stack Overflow Tag Prediction, and Stack Overflow Next Word Prediction, datasets with real-world user-level heterogeneity and imbalance.The benchmarks use user-level rather than example-level differential privacy.Source: §5.2 · p. 40, §5.2.1 · p. 41

5.2.2 Models

  • Models were a convolutional network for EMNIST, logistic regression for SO-TP, and an LSTM for SO-NWP, with respective sizes 1,018,174, 5,000,500, and 4,050,748 parameters.The SO-TP model uses bag-of-words sentence representations.Source: §5.2 · p. 40, §5.2.2 · p. 42

5.2.3 Setup

  • Training used standard dataset splits, FedAvg with uniformly weighted client updates, and 60–100 sampled clients per round; privacy amplification assumes sampled identities are hidden from analysts.The assumption does not hold for the server initiating client connections; DDGauss uses a generic amplification upper bound that may require more noise than the Gaussian baseline.Source: §5.2.3 · pp. 42–44

5.2.4 Results

  • With sufficient B, DDGauss matches the continuous Gaussian; more bits and privacy budget improve utility, though EMNIST retains a slight gap at ε = 3, k = 4.The paper attributes the EMNIST mismatch to the generic upper bound used for privacy amplification via subsampling.Source: Figure 3 · p. 43, Figure 4 · p. 43, Figure 5 · p. 44

5.3 Additional Results

  • At n = 1000 clients per round, z ≈ 0.07 targets about 25.2% test accuracy, while z ≈ 0.5 and z ≈ 0.3 yield ε around 10 and 234, respectively.The large-scale SO-NWP results indicate properly parameterized DDGauss can perform as well as the continuous Gaussian in settings with large models and heterogeneous clients.Source: §5.3 · pp. 45–46, Figure 7 · p. 45
  • Conditional rounding helps convergence when communication is tight, while its bias has little impact with sufficient bits; privacy degrades gracefully as clients drop out.With sufficient communication, β = e−1/2 and β = 1/√n yield similar performance and convergence speed.Source: §5.3 · pp. 46–47, Figure 8 · p. 46, Figure 9 · p. 46

6 Concluding Remarks

The paper presents an end-to-end federated learning protocol combining discretized client updates, discrete Gaussian noise, and secure aggregation; experiments show it essentially matches central differential privacy accuracy with 16 or fewer bits per value.

6 Concluding Remarks

  • With 16 or fewer bits of precision per value, the protocol essentially matches the accuracy of central differential privacy.It flattens and discretizes client updates before adding discrete Gaussian noise and applying secure aggregation, enabling an untrusted server to perform learning tasks on decentralized, privacy-sensitive data.Source: §6 · p. 47
  • Open questions include tighter RDP amplification or precise subsampled-mechanism analysis, alternatives to Walsh-Hadamard transforms, and private self-tuning of algorithm parameters.The transform alternatives aim to avoid padding by up to d −1 zeros; self-tuning would learn parameter settings on the fly.Source: §6 · p. 47
  • The authors also leave open proving a lower bound on m that could indicate whether a better mechanism exists.The passage says such a bound may confirm an existing result or suggest the existence of a better mechanism.Source: §6 · p. 47

Related papers

Loading 2102.06387v4…