Source-linked AI summary
Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT
Antti Koskela, Joonas Jälkö, Lukas Prediger, Antti Honkela
TL;DR
Accurate privacy accounting is difficult for discrete mechanisms and complex compositions, especially when strict guarantees are required. The paper extends FFT-based privacy-loss-distribution accounting, analyzes its error through moment bounds, and applies it to subsampled Gaussian and binomial mechanisms. The resulting method provides strict bounds and supports substantially tighter accounting, including reduced noise variance at equal privacy in the binomial example.
Problem
Existing privacy accounting for complex and discrete mechanisms lacks a broadly applicable method with strict lower and upper (ε, δ)-privacy bounds.
Method
The paper combines privacy loss distributions with FFT-based accounting and analyzes approximation error using moment bounds.
Results
The method yields accurate strict lower and upper bounds for subsampled Gaussian mechanisms and tight accounting for discrete mechanisms including the binomial mechanism.
Takeaways & Limitations
The approach supports rigorous privacy accounting for discrete-output DP-SGD and can reduce binomial-mechanism noise variance by up to 75 percent at equal privacy.
Takeaways & Limitations
The error analysis is parameterized by L, and n may need to be increased when the resulting lower and upper δ(ε) bounds are too far apart.
Abstract
from arXiv · showhide
We propose a numerical accountant for evaluating the tight $(\varepsilon,δ)$-privacy loss for algorithms with discrete one dimensional output. The method is based on the privacy loss distribution formalism and it uses the recently introduced fast Fourier transform based accounting technique. We carry out an error analysis of the method in terms of moment bounds of the privacy loss distribution which leads to rigorous lower and upper bounds for the true $(\varepsilon,δ)$-values. As an application, we present a novel approach to accurate privacy accounting of the subsampled Gaussian mechanism. This completes the previously proposed analysis by giving strict lower and upper bounds for the privacy parameters. We demonstrate the performance of the accountant on the binomial mechanism and show that our approach allows decreasing noise variance up to 75 percent at equal privacy compared to existing bounds in the literature. We also illustrate how to compute tight bounds for the exponential mechanism applied to counting queries.
1 Introduction
The paper addresses accurate privacy accounting for increasingly complex and discrete mechanisms by extending FFT-based PLD accounting with rigorous error bounds. It applies this approach to subsampled Gaussian and binomial mechanisms, including strict lower and upper privacy guarantees.
- FFT-based PLD accounting is extended from prior Gaussian-mechanism analysis to discrete mechanisms, with strict lower and upper (ε, δ)-DP bounds.
- The work targets the open problem of composing binomial mechanisms, including the sign-approximation case relevant to communication-efficient cpSGD.
- The paper organizes its contribution around PLD definitions, an FFT algorithm, rigorous error analysis, and experiments on efficiency and accuracy.
- Accurate lower and upper bounds are provided for the subsampled Gaussian mechanism, completing earlier FFT-based analysis without strict bounds.
2 Differential Privacy
This section defines neighboring datasets and approximate differential privacy through protection of measurable output events. It also distinguishes tight privacy bounds from looser valid bounds.
- Datasets are neighbors under remove/add or substitute relations, depending on whether one element is removed, added, or replaced.
- A mechanism is (ε, δ, ∼)-DP when every neighboring pair and measurable event satisfy the stated approximate-privacy inequality.
- A mechanism is tightly (ε, δ, ∼)-DP when no smaller δ′ provides the same privacy guarantee under the chosen neighboring relation.
3 Privacy Loss Distribution
The PLD formalism represents privacy loss for discrete mechanisms and converts composition into convolution, enabling tight privacy accounting for varied mechanisms and subsampling. Randomised response illustrates how the formalism recovers an explicit tight bound.
- For discrete outputs, generalized densities use weighted Dirac delta functions, allowing discrete probability masses to be handled within the PLD framework.
- The privacy loss distribution ωX/Y represents the distribution of log probability ratios between mechanism outputs on neighboring datasets.
- The PLD definition omits an explicit ∞ symbol, while unequal supports can make its total mass less than one; the subsequent analysis includes this case.
- The formalism defines integration over generalized densities and uses it to express tight privacy bounds for discrete and continuous output mechanisms.
- Randomised response provides a concrete two-output example in which the worst neighboring inputs determine the tight δ(ε) bound.
- Tight (ε, δ)-bounds for non-adaptive compositions are obtained by convolving the component PLDs, and the approach also handles composite mechanisms with varying PLDs.
- For subsampling, Poisson sampling under remove/add adjacency produces mixture densities, while substitute-adjacency sampling is analyzed analogously.
4 Fourier Accountant for Discrete-Valued Mechanisms
The Fourier accountant places a discrete privacy loss distribution on a finite grid and uses FFT-based convolutions to evaluate tight privacy bounds efficiently. Grid approximation, truncation, and periodisation are paired with an iterative solver and stopping criterion for computing ε and δ.
- 4.1 Fast Fourier Transform: FFT reduces discrete convolution costs from O(n^2) to O(n log n), enabling efficient evaluation of repeated PLD convolutions.The convolution theorem turns periodic convolutions into elementwise products in the Fourier domain.
- 4.2 Grid Approximation: The method places the PLD on a finite grid, using left- and right-sided grid approximations to obtain computable privacy bounds.A moderate L often suffices because grid points represent log probability ratios; the supplement treats cases outside the interval.
- 4.3 Truncation and Periodisation: Truncating convolutions to [−L, L] and periodising the distribution makes the finite-range inputs compatible with FFT evaluation.For equidistant grids, the construction supports direct FFT evaluation of the resulting convolutions.
- 4.4 Fourier Accountant Algorithm: Algorithm 1 evaluates the convolutions on an even grid and computes the approximate integral formula for the tight δ-value.The implementation specifies Δx = 2L/n, evaluates convolutions with FFT, and determines the integral’s starting point.
- 4.4 Fourier Accountant Algorithm: The iterative ε solver converges more than twice as fast as binary search under the same stopping tolerance.The method can use Newton’s method for ε as a function of δ and stops when the prescribed tolerance is reached.
5 Error Analysis
The error analysis bounds approximation errors using moment-generating functions of the privacy loss distribution and Chernoff bounds. These bounds yield strict lower and upper δ(ε) guarantees for the FFT accountant, with grid resolution providing an additional practical control.
- 5.2 Tail Bound: The error analysis uses moment-generating-function bounds and Chernoff bounds to control periodisation and convolution-truncation errors.Independent PLDs compose through sums, whose moment-generating functions factor under independence.
- 5.1 Connection to RDP: The log moment-generating function of the privacy loss is exactly connected to Rényi divergence, allowing existing RDP estimates to bound it.This identifies α(λ) with the logarithm of the PLD moment-generating function.
- 5.3 Total Error: For a discrete-valued PLD, left and right grid approximations plus Theorem 10 produce strict lower and upper δ(ε)-DP bounds.The procedure subtracts the estimated error from the left approximation and adds it to the right approximation.
- 5.3 Total Error: The analysis is parameterized by L, while increasing n can tighten overly separated lower and upper δ(ε) bounds.The experiments evaluate the required moment-generating functions using λ = L/2.
6 Examples
The examples apply the FFT accountant to exponential, binomial, multivariate, DP-SGD, and subsampled Gaussian mechanisms, illustrating tight bounds and comparisons with existing analyses.
- Binomial mechanism: The multivariate binomial mechanism reduces to tight bounds for non-adaptive compositions of one-dimensional mechanisms.Theorem 11 applies when independent noise coordinates are added to neighboring function outputs.
- DP-SGD: The MNIST experiment applies Algorithm 1 to sign-approximated DP-SGD with binomial noise and subsampling amplification.The method is compared with cpSGD on Infinite MNIST using reported results from Agarwal et al. (2018).
- Subsampled Gaussian mechanism: For the subsampled Gaussian mechanism, Algorithm 1 computes δ(ε) bounds while varying discretisation points and records compute times.The displayed setting is ε = 1.0, q = 0.02, σ = 2.0, and L = 8.0; convergence is compared with TensorFlow’s moments accountant.
7 Conclusions
The paper concludes that its PLD- and FFT-based accountant provides strict privacy bounds for discrete mechanisms and accurate bounds for subsampled Gaussian mechanisms.
- Conclusions: The method provides strict lower and upper privacy bounds through rigorous error analysis of discrete PLD approximations.The analysis supports lower and upper bounds for δ(ε), including composed mechanisms.
- Conclusions: The framework computes accurate bounds for discrete-valued mechanisms, including subsampled binomial mechanisms with sign-approximated gradients.It also supports moments-accountant-like techniques for discrete-output DP-SGD.
- Privacy-loss composition: Non-adaptive composition combines privacy-loss distributions by convolution, yielding tight composition bounds.For consecutive applications, the PLD is convolved repeatedly.
- FFT accounting: The FFT implementation evaluates truncated convolutions on an equidistant grid using discrete Fourier transforms and elementwise powers.Algorithm 1 operates on a grid with n points and composition count k.
- Error analysis: The error analysis separates approximation errors and bounds them using moment-generating functions and Chernoff inequalities.The resulting bounds account for truncation, periodisation, and convolution-related errors.
C.2 Error Arising from the Periodisation
The periodisation analysis bounds the error introduced when repeated PLD convolutions are evaluated on a finite periodic grid.
- Periodisation error: Moment-generating-function bounds control the periodisation error for truncated convolutions of the PLD.The analysis defines α+(λ) and α−(λ) from the PLD moment-generating function.
- Periodisation error: The bound applies even when the PLD support extends outside the truncation interval [−L, L].The truncation error is bounded for all λ > 0.
- Periodisation error: The convolution error is handled recursively by comparing ordinary and truncated convolutions at successive composition levels.The recursion decomposes the difference into a one-step truncation term and a propagated previous error.
- Periodisation error: Combining Chernoff bounds with the convolution and truncation lemmas yields the final error estimate used by the accountant.The theorem uses α+(λ) and α−(λ) to control the total approximation error.
D Theorem 11: Tight Bound for Multidimensional Mechanisms via One Dimensional Distributions
The section shows that tight privacy bounds for certain multidimensional mechanisms reduce to one-dimensional distributions and their compositions. It then describes Fourier-accountant approximations and error controls for obtaining strict bounds.
- Tight (ε, δ)-bounds for a multidimensional mechanism can be obtained from one-dimensional distributions when the neighboring datasets yielding maximal δ(ε) are known.
- The multidimensional mechanism is equivalent, in privacy-loss distribution, to composing shifted one-dimensional variables Δ_i + Z_i with Z_i.
- The Fourier accountant represents multidimensional compositions through convolutions of one-dimensional density functions and combines mixture terms for subsampled mechanisms.
- Grid-based lower and upper approximations use truncated distributions ω_min and ω_max, with coefficients determined from local minima and maxima on grid intervals.
G Description of Learning Rate Cooling Used for Experiments of Figure 2b.
The Figure 2b feedforward-network experiments use an initial learning rate of 0.02 and linearly cool it to zero after specified epochs.
- The experiments start with learning rate η = 0.02 and linearly decrease it after each epoch until it reaches zero.Cooling starts at epoch 13 for n = 2400, |B| = 500, and at epoch 5 for n = 3000, |B| = 300.