Source-linked AI summary
Numerical Composition of Differential Privacy
Sivakanth Gopi, Yin Tat Lee, Lukas Wutschitz
TL;DR
The paper addresses the difficulty of obtaining tight, accurate privacy guarantees for large compositions of DP algorithms. It uses privacy loss random variables and numerical composition to approximate privacy curves efficiently, including under adaptive composition. The resulting method improves state-of-the-art runtime and memory for repeated composition while providing close privacy-curve bounds, with applications to DP-SGD.
Problem
Large compositions such as DP-SGD require accurate privacy curves, but existing accountants may provide only upper bounds, fail for unbounded PRV moments, or misestimate ε.
Method
The method reparameterizes privacy curves with privacy loss random variables, whose sums represent adaptive composition, and numerically approximates their convolutions using discretization.
Results
The algorithm improves the state of the art by at least a factor of k in running time and also reduces memory by a factor of k, while producing closely matching upper and lower bounds.
Takeaways & Limitations
The approach enables accurate and efficient privacy accounting for large repeated compositions, including practical DP-SGD analyses.
Takeaways & Limitations
The implementation only allows δ values greater than 10^-10 because floating-point inaccuracies affect computations at smaller δ values.
Abstract
from arXiv · showhide
We give a fast algorithm to optimally compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of privacy loss random variables to quantify the privacy loss of DP algorithms. The running time and memory needed for our algorithm to approximate the privacy curve of a DP algorithm composed with itself $k$ times is $\tilde{O}(\sqrt{k})$. This improves over the best prior method by Koskela et al. (2020) which requires $\tildeΩ(k^{1.5})$ running time. We demonstrate the utility of our algorithm by accurately computing the privacy loss of DP-SGD algorithm of Abadi et al. (2016) and showing that our algorithm speeds up the privacy computations by a few orders of magnitude compared to prior work, while maintaining similar accuracy.
1 Introduction
Differential privacy composition seeks tighter guarantees than naive accumulation, especially for repeated mechanisms such as DP-SGD. The paper develops a PRV-based algorithm that improves the efficiency and accuracy of numerical privacy-curve composition.
- Differential privacy provides quantifiable privacy guarantees for algorithms whose outputs are released from private data.
- Naive composition gives M^∘k the guarantee (kε, kδ)-DP, while advanced composition provides substantially better guarantees.
- Exact guarantees for composing different DP algorithms are #P-complete, motivating approximation methods for privacy curves.
- Privacy loss random variables add under adaptive composition, so composing privacy curves can be reduced to summing or convolving their distributions.
- Existing accountants have important limitations: Moments Accountant and RDP provide upper bounds but not arbitrary-accuracy curves, while GDP can underreport ε.
- The paper introduces a new algorithm for large compositions, with improved runtime and memory, and extends numerical composition analysis to adaptive composition.
- For repeated composition of one mechanism, the method improves prior runtime by at least a factor of k and produces closely matching privacy-curve bounds.
2 DP Preliminaries
Privacy curves represent all (ε, δ)-guarantees of a DP algorithm, and their composition captures adaptive composition through an operation on privacy curves.
- A privacy curve δ_M(ε) records the δ guarantee associated with every ε ≥ 0 for algorithm M.
- The privacy curve δ(X||Y) characterizes the privacy relationship between two random variables and determines whether an algorithm is (ε, δ)-DP.
- Privacy-curve composition δ1 ⊗ δ2 is defined using independently sampled pairs of random variables representing the two curves.
- The composition operation is well-defined even though multiple random-variable pairs can represent the same privacy curve.
- For adaptive composition, the privacy curve of M_k ◦ ··· ◦ M_1 equals δ1 ⊗ δ2 ⊗ ··· ⊗ δk.
3 Privacy Loss Random Variables (PRVs)
Privacy loss random variables reparameterize privacy curves so that composing privacy guarantees becomes adding the corresponding random variables, or equivalently convolving their distributions.
- PRVs provide an equivalent reparameterization of privacy curves in which composition becomes convolution.
- PRVs for a curve δ(P||Q) are given by the log-likelihood random variables of P and Q.
- The privacy curve can be computed from PRVs through δ(ε) = Pr[Y > ε] − e^ε Pr[X > ε] = E_Y[(1 − e^(ε−Y))_+].
- For privacy curves represented by PRV pairs (X1, Y1) and (X2, Y2), composition uses the pair (X1 + X2, Y1 + Y2).
- The framework also supports computing PRVs for subsampled mechanisms, which are used to calculate PRVs for DP-SGD.
4 Numerical composition of privacy curves
ComposePRV approximates PRVs by truncation and discretization, then uses FFT-based convolution to efficiently compute the privacy curve of a composition.
- ComposePRV is an efficient numerical method for composing privacy guarantees through privacy loss random variables.
- The algorithm truncates and discretizes each PRV, then convolves the resulting probability distributions using FFT.
- FFT convolution of distributions supported on hZ ∩ [−L, L] implicitly computes circular convolution modulo 2L.
- DiscretizePRV shifts each discretized variable so its expected value matches the original PRV, reducing discretization error.
- The corrected approximation permits a coarser mesh h ≈ 1/√k instead of h ≈ 1/k.
- The method handles PRVs with mass at infinity by separating that mass and approximating the finite component's sum.
5 Error analysis
The error analysis controls truncation, discretization, and composition errors using coupling approximations, yielding explicit privacy-curve bounds and efficient complexity for repeated composition.
- 5 Error analysis: A coupling approximation requires a coupling under which two random variables differ by more than h with probability at most η.
- 5 Error analysis: Coupling approximations keep the privacy curves of the original and approximate PRVs close, with additive and ε-shift errors.
- 5 Error analysis: Mean-preserving independent coupling approximations accumulate more favorably than the triangle inequality predicts.
- 5 Error analysis: For a DP algorithm, truncating at L = Θ(1) introduces only an additive δ error when the composed guarantee has ε = O(1) for sufficiently small δ.
- 5 Error analysis: For repeated composition, the analysis yields a k-dependent algorithm whose runtime and memory improve by a factor of k relative to prior approaches.
- 5 Error analysis: Theorem 5.5 bounds the true privacy curve between shifted approximate curves: δ_eY(ε + εerror) − δerror ≤ δ_M(ε) ≤ δ_eY(ε − εerror) + δerror.
6 Experiments
The experiments evaluate the composition method on DP-SGD and compare its accuracy and runtime with prior FFT-based methods and analytical solutions. The method produces close privacy bounds while requiring substantially fewer discretization points and reducing runtime.
- DP-SGD evaluation: DP-SGD performs k noisy gradient steps, sampling a p fraction of examples and adding Gaussian noise with variance proportional to σ^2.The privacy loss composes the privacy curve of one iteration k times, and the iteration PRVs have a closed form depending on p and σ.
- Comparison with prior work: Under the same mesh size, our algorithm computes a much closer upper and lower privacy bound than [KJPH21].The comparison uses bounds derived according to (8).
- Validation: For p = 1, the computed bounds sandwich the analytical privacy curve with vertical distance 2εerror and negligible δerror of 10^-10.Figure 2 compares the computed bounds with the analytical solution.
- Comparison with prior work: A few orders of magnitude fewer discretization points are needed for our algorithm to converge compared with [KJPH21].For large numbers of compositions, [KJPH21]'s error bounds worsen quickly.
- Implementation: The runtime and memory requirements are dominated by the number of discretization points in the PRV discretization.The experiments ran on an Intel Xeon W-2155 CPU with 128GB of memory.
- Runtime: Aligned-accuracy runtime experiments show a significant reduction in runtime using our algorithms as the number of DP-SGD steps varies.The comparison varies the number of DP-SGD steps after selecting numerical parameters that produce similarly accurate bounds.
A Effect of floating point arithmetic
The appendix examines floating-point inaccuracies by comparing computed privacy bounds with an analytical solution for very small δ. These inaccuracies become dominant below the range supported by the implementation.
- Floating-point effects: Floating-point inaccuracies become dominant around δ = 10^-11 with roughly 10^4 discretization points and 10^-15 floating-point resolution.Figure 6 compares lower and upper bounds with the analytical solution.
- Floating-point effects: For δ < 2 × 10^-11, the computed lower and upper bounds fail to produce meaningful results.The failure occurs in the regime beyond expected floating-point accuracy.
B Privacy Loss Random Variables
This section formalizes privacy loss random variables and their relationship to privacy curves. It derives PRVs for standard mechanisms and subsampled mechanisms, providing the representations used for composition.
- PRVs and privacy curves: The PRVs associated with a privacy curve satisfy the density relation Y(t) = e^t X(t).This relation underlies the converse construction between privacy curves and PRV densities.
- PRVs and privacy curves: The privacy curve δ can be expressed from PRVs (X, Y) as Pr[Y > ε] − e^ε Pr[X > ε].Equivalent forms are EY[(1 − e^(ε−Y))+] and Pr[Y ≥ ε + Z], where Z is exponential.
- Standard mechanisms: The section states PRVs for Gaussian, Laplace, and (ε, δ)-DP mechanisms, including symmetry conditions for several examples.For the Laplace mechanism, the PRVs are represented using a Laplace random variable Z.
- Subsampled mechanisms: For subsampling probability p, the transformed PRVs use log(1 + p(e^Y − 1)) and log(1 + p(e^X − 1)) in their mixture components.The section also gives the corresponding CDFs and the mixture interpretation p·P + (1−p)·Q.
C Missing Proofs in Error Analysis
The missing proofs establish coupling tools used in the error analysis. They show how coupling errors combine and how total variation distance yields a coupling approximation.
- Coupling inequalities: Coupling approximations satisfy a triangle inequality: errors η1 and η2 combine with bounds h1 and h2 into η1+η2 and h1+h2.The proof constructs a coupling by sampling X, then Y conditioned on X, and finally Z conditioned on Y.
- Coupling inequalities: The combined coupling obeys Pr[|X − Z| ≥ h1 + h2] ≤ Pr[|X − Y| ≥ h1] + Pr[|Y − Z| ≥ h2].This follows from the triangle inequality and a union bound.
- Total variation coupling: If dTV(X, Y) ≤ η, there exists a coupling with Pr[X ≠ Y] ≤ η.The result follows from the standard coupling characterization of total variation distance.
C.2 Bounding the error using tail bounds of PRVs
The error analysis bounds ComposePRV's approximation by combining truncation, discretization, and circular-convolution errors, using tail bounds of the underlying privacy-loss random variables. A key tail estimate relates an (ε, δ)-DP guarantee to the probability that a PRV exceeds ε plus a slack term.
- ComposePRV's error analysis is formulated in terms of tail bounds for the underlying privacy-loss random variables.The section explicitly targets bounding ComposePRV's error through PRV tails.
- DiscretizePRV preserves the truncated PRV's mean while coupling it within mesh-size error and truncation probability η.For truncation threshold L, η is the probability that the PRV lies outside [−L, L].
- The approximation error is assembled by applying coupling and triangle-inequality bounds across truncation, discretization, and composition steps.Corollary C.8 and Theorem C.3 combine the component bounds into the final ComposePRV guarantee.
- Circular convolution approximates the sum of discretized PRVs when the cumulative sum remains within [−L, L] with high probability.The analysis separates this wrapping error from the individual discretization and truncation errors.
- For an (ε, δ)-DP algorithm, the PRV tail satisfies roughly Pr(|Y| ≥ ε + 2) ≤ 2δ.Lemma 5.4 generalizes this relationship to a slack parameter t ≥ 0.
C.4 Proof of Theorem 5.5
Theorem 5.5 bounds the privacy curve of an adaptive composition between shifted privacy curves of the ComposePRV approximation, with additive error terms. The proof obtains this result by combining the discretization and composition error bounds, while FFT-based convolution determines the runtime.
- Theorem 5.5 applies to adaptive compositions of DP algorithms with specified privacy curves and fixed approximation errors εerror and δerror.The truncation parameter L is chosen sufficiently large relative to εerror.
- δeY(ε + εerror) − δerror ≤ δY(ε) = δM(ε) ≤ δeY(ε − εerror) + δerror.The composed mechanism's privacy curve is therefore bracketed by shifted bounds from the ComposePRV approximation.
- FFT-based convolution is the runtime bottleneck, costing O(bL/h log(L/h)) for b distinct algorithms.The total includes b forward transforms and one inverse transform.