PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Accounting of Differential Privacy via Characteristic Function

Yuqing Zhu, Jinshuo Dong, Yu-Xiang Wang

arXiv:2106.08567v3cs.LGcs.CR

TL;DR

Privacy accounting needs tight guarantees over compositions, but RDP conversion can lose tightness and PLD’s pair-specific formulation leaves worst-case distributions unresolved. The paper uses dominating pairs and characteristic functions to unify privacy representations and enable composition and conversion. Experiments report tighter guarantees than RDP across basic and subsampled mechanisms, with AFA offering flexible computation.

  • Problem

    RDP conversion can fail to recover optimal (ε, δ)-DP guarantees, while PLD lacks a general way to identify worst-case distributions for composition.

    Source: §3 · pp. 5–6

  • Method

    The paper represents privacy loss through characteristic functions of dominating pairs, enabling lossless conversion among privacy descriptions and symbolic composition with an analytical Fourier accountant.

    Source: §4.2 · p. 9, §4.3 · p. 10, §6 · p. 13

  • Results

    Experiments show substantially tighter privacy guarantees over compositions than RDP on basic mechanisms and their subsampled counterparts, and suggest AFA can flexibly and efficiently fit DP applications.

    Source: §1 · p. 2, §6 · p. 13

  • Takeaways & Limitations

    Dominating pairs provide a broader foundation for PLD worst-case guarantees, including adaptive composition and amplification by sampling.

    Source: §6 · p. 13

    Some composed characteristic functions require many Gaussian quadrature points when their tails remain large.

    Source: §6 · p. 13

Abstract

from arXiv · show

Characterizing the privacy degradation over compositions, i.e., privacy accounting, is a fundamental topic in differential privacy (DP) with many applications to differentially private machine learning and federated learning. We propose a unification of recent advances (Renyi DP, privacy profiles, $f$-DP and the PLD formalism) via the \emph{characteristic function} ($\phi$-function) of a certain \emph{dominating} privacy loss random variable. We show that our approach allows \emph{natural} adaptive composition like Renyi DP, provides \emph{exactly tight} privacy accounting like PLD, and can be (often \emph{losslessly}) converted to privacy profile and $f$-DP, thus providing $(\epsilon,\delta)$-DP guarantees and interpretable tradeoff functions. Algorithmically, we propose an \emph{analytical Fourier accountant} that represents the \emph{complex} logarithm of $\phi$-functions symbolically and uses Gaussian quadrature for numerical computation. On several popular DP mechanisms and their subsampled counterparts, we demonstrate the flexibility and tightness of our approach in theory and experiments.

1 Introduction

The introduction motivates finer-grained privacy accounting by the limitations of existing functional representations, including unresolved worst-case issues in PLD. It presents dominating pairs and characteristic functions as a unified approach to tighter accounting and conversion across privacy descriptions.

1 Introduction

  • No single functional representation dominates all dimensions: RDP may be undefined or lose tightness, while privacy profiles and f-DP are unwieldy under composition.Existing Fourier-accountant methods also have restrictions on output distributions, and deriving functional descriptions manually can limit researchers and practitioners.Source: §1 · p. 2
  • The PLD formalism leaves unresolved how to identify worst-case neighboring datasets, which may not exist or be consistently ordered.This issue also complicates use of PLD for worst-case bounds under composition.Source: §1 · p. 2
  • Dominating pairs formalize worst-case distributions and support adaptive composition and amplification by sampling.The paper proves basic properties and recipes for constructing such pairs, broadening PLD's use for worst-case DP guarantees.Source: §1 · p. 2
  • The characteristic function losslessly represents privacy loss and converts to privacy profiles, tradeoff functions, moment-generating functions, and privacy-loss distributions.The paper also derives optimal conversion rules to and from these representations.Source: §1 · p. 2
  • The approach provides substantially tighter privacy guarantees over compositions than RDP on basic mechanisms and their subsampled counterparts.Its results essentially match those of Dong et al. [2021] and Koskela et al. [2021], without relying on a central-limit-theorem approximation or preset discretization.Source: §1 · p. 2
  • The analytical Fourier accountant represents the complex logarithm of φ-functions symbolically, enabling modular numerical integration.It supports black-box integration tools such as Gaussian quadrature, with error bounds chosen on the fly, unlike the initialization-time parameter choices of FFT accountants.Source: §1 · p. 3

2 Notations and preliminary

The section sets out equivalent ways to express differential privacy and introduces mechanism-specific functional descriptions. It also reviews RDP and its appeal for composition and privacy accounting.

Differential privacy and its equivalent definitions

  • Differential privacy can be expressed through hockey-stick divergence, hypothesis-testing tradeoff functions, or privacy-loss probabilities.The definitions require guarantees to cover every neighboring dataset pair.Source: §2 · p. 4

Mechanism-specific analysis / Functional representation of DP guarantee

  • A mechanism-specific functional representation can describe its privacy guarantee through a privacy profile, f-DP tradeoff function, or privacy-loss distribution.The privacy profile upper-bounds hockey-stick divergence, while f-DP lower-bounds the tradeoff function.Source: §2 · p. 4

Renyi Differential Privacy and Moments Accountant

  • RDP describes privacy using Rényi divergence and can be converted to (ε, δ)-DP by optimizing over its order.Tighter conversion formulas have also been proposed.Source: §2 · p. 4
  • RDP composes naturally across adaptively chosen mechanisms by adding their privacy parameters, and supports privacy accounting in private deep learning.The section relates the moments accountant to tracking the moment-generating function of the privacy-loss random variable.Source: §2 · pp. 4–5
  • Randomized response and a Gaussian mechanism can share the same RDP function while differing in their f-DP and privacy-profile guarantees.Figure 1 compares both mechanisms and the f-DP implied by conversion from RDP.Source: Figure 1 · p. 5, §2 · p. 5

3 Motivation of our research

The section argues that RDP is not a lossless route to optimal (ε, δ)-DP guarantees and that PLD lacks a general treatment of worst-case distributions. These limitations motivate the paper’s approach to mechanism-specific accounting.

The limits of RDP

  • Even when RDP parameters exist everywhere, converting RDP to (ε, δ)-DP need not match the optimal accounting available through privacy profiles or f-DP.The Gaussian mechanism illustrates this loss: randomized response can satisfy the same RDP while having a different tradeoff function.Source: §3 · pp. 5–6
  • At δ = 0.3, the Gaussian mechanism obeys (0.277, 0.3)-DP, while randomized response does not satisfy (ε, 0.3)-DP for ε < 0.471.The example shows that even the Gaussian mechanism’s RDP can be a lossy representation.Source: §3 · p. 6

Trouble with Worst-Cases in the PLD formalism

  • PLD is specified separately for each input pair, but analysts are expected to provide the worst-case distributions.Prior work derived such pairs for some basic mechanisms, including Gaussian and Laplace mechanisms.Source: §3 · p. 6
  • Worst-case pairs may vary across privacy-profile regions, may not exist, and do not generally compose into the composed mechanism’s worst-case PLD.This leaves PLD without a generic route to worst-case composition bounds outside specialized cases such as Gaussian mechanisms.Source: §3 · p. 6

4 Main results

The section builds a broader PLD accounting framework from dominating distribution pairs, then uses characteristic functions and an analytical accountant for composition and conversion.

4.1 Dominating pair of distributions, composition and subsampling

  • Every mechanism has a tightly dominating pair, and privacy-profile constructions can yield univariate pairs even for mechanisms with complex outputs.This broadens PLD beyond mechanisms with univariate or discrete outputs.Source: §4.1 · p. 7
  • Under the stated uniform bound on each adaptive next mechanism, products of dominating pairs dominate the adaptive composition.By induction, the resulting composed PLD gives a valid worst-case DP guarantee.Source: §4.1 · p. 7
  • For Poisson sampling and fixed-size subset sampling, the paper gives dominating pairs for add and remove neighbors, extending PLD to sampled mechanisms generically.The subset result assumes a replacing-neighbor dominating pair for the base mechanism.Source: §4.1 · p. 8

4.2 Characteristic function representation

  • Characteristic functions multiply under composition, making adaptive composition over heterogeneous mechanisms as straightforward as in RDP.The composition rule applies to the φ-functions of the mechanisms.Source: §4.2 · p. 9
  • The characteristic function is a lossless representation of the privacy-loss distribution, with conversions to privacy profiles, tradeoff functions, moment-generating functions, and distribution functions.Unlike the moment-generating function, it always exists and characterizes the privacy-loss distribution.Source: §4.2 · p. 9

4.3 Analytical Fourier Accountant and numerical algorithms

  • The Analytical Fourier Accountant symbolically tracks log characteristic functions, constructs privacy-loss CDFs for queries, and uses bisection to solve for ϵ given δ.It converts to (ϵ, δ)-DP using the lossless conversion rules.Source: §4.3 · p. 10
  • AFA avoids approximation while tracking mechanisms and avoids choosing FFT discretization parameters in advance; Gaussian quadrature computes CDFs with reported error often O(10^-13).The reported error is for CDFs in the experiments, using a few hundred sample points.Source: §4.3 · p. 10

5 Experiments

Across Gaussian, heterogeneous, and subsampled compositions, the experiments show AFA matching analytical or Fourier-accountant results while outperforming RDP in the reported comparisons. Its runtime and approximation behavior depend on whether analytical φ-functions are available and on what each accountant computes.

Exp. 1 (Gaussian mechanism)

  • AFA exactly matches the analytical Gaussian mechanism and strictly outperforms the RDP accountant across the evaluated privacy regimes.The comparison evaluates ε at fixed δ = 10^-4 for σ ∈ {50, 100}.Source: §5 · p. 11

Exp. 2 (Compositions of discrete and continuous mechanisms)

  • For discrete and continuous compositions, AFA analytically composes mechanisms without sampling discretization points over the privacy loss distribution.The reported numerical result matches the Fourier Accountant using 10^5 discretization points.Source: §5 · p. 11

Exp. 3 (Compositions over Poisson Subsample mechanisms)

  • For Poisson subsampled Gaussian compositions, “Double quadrature” matches the Fourier Accountant, and all Fourier-accountant approaches improve over the RDP-based accountant.At γ = 0.01, σ = 2.0, and δ = 10^-5, the method unevenly samples 700 points for each φ-function; its reported bounds include discretization and tail-integral error.Source: §5 · p. 12

Runtime and space analysis of AFA

  • For analytical φ-functions, each mechanism uses O(1) memory and evaluation time, with memory scaling as O(number of unique mechanisms).The runtime discussion separates composition from conversion to δ(ε).Source: §5 · p. 12
  • AFA adapts integration to φ-function structure and achieves a faster convergence rate in the approximation-error comparison.The runtime comparison is not like-for-like: FFT computes the entire discretized composed PLD, while AFA computes one point.Source: §5 · p. 12
  • Without analytical φ-functions, AFA must approximate φ as well and is slower than the compared FFT-based methods.The space and time complexity of adaptive discretization via double quadrature is unclear, though it is described as very fast in practice.Source: §5 · p. 12

6 Conclusion

The conclusion presents dominating pairs and a symbolic characteristic-function accountant as tools for tight mechanism-specific privacy accounting, with natural composition and numerical conversion. The accompanying limits discussion shows why RDP may fail on some privacy-loss distributions, while the paper identifies unresolved construction and integration challenges.

6 Conclusion

  • The paper introduces dominating pairs with adaptive composition and sampling amplification, and an analytical Fourier accountant that symbolically represents characteristic functions for natural composition.Experiments are reported to demonstrate AFA's merits and suggest flexible, efficient application across DP.Source: §6 · p. 13
  • High-dimensional discrete Gaussian mechanisms remain a difficult open problem when trade-off functions are not clear enough to construct dominating pairs.The paper says this construction is severely constrained in that setting.Source: §6 · p. 13
  • When composed φ-functions have large values in the integration tail, AFA may require substantially more Gaussian quadrature points.The authors identify numerical tools as a possible future way to address this issue.Source: §6 · p. 13

A Limits of RDP and the PLD formalism

  • RDP can be infinite for the Distance-to-Instability mechanism despite its stated (ε, δ)-DP guarantee, because its privacy-loss distribution has mass at +∞.The paper also notes that RDP may not exist for most orders in mechanisms with heavier-tailed privacy-loss distributions.Source: A Limits of RDP and the PLD formalism · p. 17
  • The privacy profile remains defined in the cited examples, while the characteristic function exists for heavy-tailed privacy-loss distributions; a +∞ mass is handled separately.The text also describes a mechanism whose privacy-profile maximizer varies by input parameter, so no single neighboring pair attains it throughout.Source: A Limits of RDP and the PLD formalism · pp. 17–18

B Conversion rules between functional representations

This section distinguishes conversions among representations of a privacy-loss random variable from conversions that establish DP guarantees. It outlines representation-to-representation links and notes that DP conversion can be lossy even when divergence conversion is generally lossless under regularity conditions.

B Conversion rules between functional representations

  • The conversion rules relate representations of the privacy-loss random variable under the same (ε, δ)-DP definition, rather than converting between DP definitions.The section focuses on conversions assuming a dominating pair is available.Source: B Conversion rules between functional… · pp. 18–19
  • Divergence conversion for privacy requires a dominating pair, which may not be tight; DP conversion instead seeks a bound on hockey-stick divergence across neighboring datasets.The section distinguishes this upper-bound task from converting divergences for a given pair of distributions.Source: B Conversion rules between functional… · p. 18
  • DP conversion is lossy, whereas divergence conversion is generically lossless under regularity conditions, though inverse Laplace transforms can pose numerical issues.The text illustrates the DP-conversion loss with standard randomized response being 1-zCDP.Source: B Conversion rules between functional… · p. 19
  • The section describes routes from characteristic functions to CDFs via Levy’s formula and between paired trade-off functions by inversion.The table identifies φ and φ′ as characteristic functions, F and G as PLD CDFs, f as the trade-off function, and Hα and Dα as divergences.Source: Table 4 · p. 19, B Conversion rules between functional… · p. 20

C.1 Characterization of privacy profiles

The section characterizes privacy profiles through convex-conjugacy relationships and shows how an upper bound can be tightened to one that admits a dominating pair. It then establishes that dominating pairs compose, including under the stated adaptive-composition condition.

C.1 Characterization of privacy profiles

  • Convex conjugacy gives a bijection between the stated classes F and G, yielding a characterization of the corresponding hockey-stick-divergence functions.The section relates h ∈ H to trade-off functions by h(α) = 1 + f*(−α).Source: §C.1 · pp. 21–22
  • A privacy-profile upper bound h can be tightened to HS(h), the greatest lower bound of h that is itself a valid privacy profile, and HS(h) admits a dominating pair.HS(h) can be significantly smaller than the original bound.Source: §C.1 · p. 23

C.2 Composition theorem of dominating pairs

  • The product of dominating pairs for two mechanisms is a dominating pair for their composition.The theorem permits adaptive choice of the second mechanism when its hockey-stick divergence is bounded uniformly over first-mechanism outputs.Source: §C.2 · p. 23

C.3 Privacy-amplification for dominating pairs

Theorem 11 gives dominating pairs for Poisson and fixed-size subset sampling by treating add and remove neighbors separately. Under mild regularity conditions, its bounds can be exactly optimal, and the resulting moments accountant closes a constant gap for subsampled mechanisms.

C.3 Privacy-amplification for dominating pairs

  • Poisson sampling preserves domination with (P, (1 −γ)P + γQ) for add neighbors and ((1 −γ)Q + γP, Q) for removal neighbors.The theorem applies when (P, Q) dominates the base mechanism for add neighbors.Source: §C.3 · p. 24
  • Subset sampling preserves domination with (P, (1−γ)P +γQ) for add neighbors and ((1 −γ)P + γQ, P) for removal neighbors.The base pair must dominate the mechanism for replacing neighbors.Source: §C.3 · p. 24
  • Under mild regularity conditions, tightly dominating pairs yield exact bounds for both add and removal relations, realized by concrete datasets.For Gaussian or Laplace mechanisms releasing the count of ones, the described neighboring datasets attain the upper bound for all α > 0.Source: §C.3 · p. 28
  • The moments accountant for subsampled mechanisms closes the constant gap with Poisson-sampled mechanisms, although its pairs need not attain the Renyi-DP bounds.The passages distinguish computing (ϵ, δ)-DP from attaining Renyi-DP bounds.Source: §C.3 · p. 28

C.4 Other schemes in privacy-amplification for dominating pairs

This section extends dominating-pair results to alternative sampling and neighbor schemes, describes φ-functions for basic mechanisms, and handles privacy loss with mass at infinity. The alternative-scheme bounds can be complex, while the paper identifies separate add/remove accounting as sufficient for practical use.

C.4 Other schemes in privacy-amplification for dominating pairs

  • Separate add/remove accounting suffices in practice; alternative sampling schemes also admit explicit dominating pairs, but their expressions can be complex.The alternative bounds characterize the tight privacy profile with two ordered pairs, which do not individually dominate across the full α range.Source: §C.4 · pp. 29, 31

D.1 φ-function of basic mechanisms

  • When worst-case distributions are known, the φ-function approach extends composition to exponential mechanisms, Report-noisy-max, and post-processed continuous-output mechanisms such as NoisyScreening.Mechanisms with discrete outputs admit an analytical φ-function representation whose space and time scale linearly with output-space size.Source: §D.1 · p. 33

D.2 Handling probability mass at ∞

  • Privacy loss mass at infinity can be handled separately, composing the characteristic function of the sub-probability measure that excludes infinity.The motivation includes propose-test-release-style algorithms, where the privacy-loss random variable may have nonzero mass at infinity.Source: §D.2 · pp. 33–34

E φ-function with discretization and experimental details

For continuous mechanisms without closed-form φ-functions, the section approximates privacy loss over a truncated output domain and develops error bounds. It also introduces double quadrature as a faster approximation method when closed forms are unavailable.

E φ-function with discretization and experimental details

  • The discretization approach grids the truncated output domain [−S, S] because bounding φ-functions alone need not bound privacy costs, and discrete outputs matter for communication-efficient private learning.The authors note that a one-dimensional tightly dominating pair exists for any mechanism.Source: E φ-function with discretization and… · pp. 34–35
  • Under monotone privacy loss as a function of output, Riemann-sum approximations bound the privacy profile and yield upper and lower bounds on composition costs.The section states the continuous-mechanism profile bound and extends the approach to simple composition.Source: E φ-function with discretization and… · pp. 35–36
  • Double quadrature applies Gaussian quadrature both to approximate unavailable φ-functions and to compute CDFs, improving on Algorithm 2’s linear time in the grid size.The experiments report a match with the Fourier Accountant while sampling hundreds of points for Poisson subsample mechanisms.Source: E φ-function with discretization and… · p. 36

E.1 Error analysis

  • The error analysis separates φ-function approximation, Riemann-sum approximation, and CDF quadrature error, with the last term often negligible.Truncation error is bounded through the tail integral, then multiplied by the number of compositions when accounting for outputs outside the truncated range.Source: §E.1 · pp. 36–37
  • For closed-form φ-functions, numerical error comes from quadrature used to convert φ-functions to CDFs, with classical quadrature error estimates available under smoothness assumptions.The passage describes asymptotic scaling of about O(1/n^α) for functions with α derivatives, and faster scaling for more advanced rules.Source: §E.1 · p. 37
  • The double-quadrature error bounds lack an asymptotic analysis, although scipy.integrate.dblquad provides valid bounds and the authors recommend this approach in practice.The discretization method instead uses an equispaced grid over the support of the dominating pairs.Source: §E.1 · p. 37

E.2 Experimental details in Exp 3

The experiments bound truncation error for Poisson subsampled Gaussian mechanisms and compare approximation approaches. The appendix also describes converting mechanism-specific RDP guarantees into f-DP and then (ϵ, δ)-DP.

E.2 Experimental details in Exp 3

  • For Poisson subsampling, the authors use a one-dimensional worst-case neighboring pair and discretization because its privacy-loss random variables do not yield a closed-form φ-function naively.The Gaussian experiment uses γ = 0.01, σ = 2.0, S = 100, N = 10^5, and up to 1500 compositions.Source: §E.2 · p. 38
  • For Poisson subsampled Gaussian experiments with S = 100, k = 1500, and σ = 2.0, k · δtail is bounded by e^-1000 and is negligible in the δ term.The discretization experiment plots valid lower and upper bounds using Algorithm 2.Source: §E.2 · p. 38
  • The double-quadrature algorithm exactly matches Koskela et al. [2021] and takes around 0.2 seconds per δ(ϵ) query, though its error analysis is not included.Source: §E.2 · p. 38

F An “optimal” Renyi DP to DP conversion?

  • The proposed RDP-to-f-DP conversion takes the pointwise maximum of the f-functions implied by a mechanism’s RDP bounds and includes 0 < α < 1, which has a nontrivial effect on the resulting tradeoff function.The resulting f-DP can then be converted to (ϵ, δ)-DP using the paper’s formula.Source: F An “optimal” Renyi DP to DP… · p. 39

F.1 RDP to f-DP

  • The f-DP tradeoff implied by a family of RDP bounds is the pointwise maximum of the resulting f-functions across α.The section derives the relation through hypothesis testing and closure to post-processing.Source: §F.1 · pp. 39–40

F.2 f-DP to (ϵ, δ)-DP

  • For f-DP, the paper gives a family of (ϵ, δ)-DP guarantees and describes numerically stable conversion using subgradients and logarithmic-scale computations.For differentiable f, the conversion can be computed through a nonlinear equation involving f′.Source: §F.2 · p. 40

F.3 Optimality of this conversion rule?

The section tests whether the RDP-to-DP conversion is optimal and finds different evidence for randomized response and the Gaussian mechanism. It leaves strong optimality unresolved.

F.3 Optimality of this conversion rule?

  • For randomized response, the converted result matches exactly the exact (ϵ, δ)-DP obtained from the privacy profile.Source: §F.3 · p. 41
  • For the Gaussian mechanism, the converted f-function touches that of randomized response when both satisfy the same RDP bound for all α > 0, ruling out a strict improvement at every Type I error input.Source: §F.3 · p. 41
  • The Gaussian example does not rule out improvements at some inputs, and the conjecture of optimality for all RDP functions and inputs is not formally proved.Source: §F.3 · p. 41

G Omitted proofs in Appendix B

The appendix proofs relate tradeoff functions to likelihood-ratio tests, hockey-stick divergence, privacy-loss distributions, and characteristic functions. They use these identities to connect f-DP descriptions with φ-functions.

G Omitted proofs in Appendix B

  • The appendix invokes the inverse-derivative relation between a convex function and its convex conjugate to connect derivatives in its identities.Source: G Omitted proofs in Appendix B · p. 42
  • The tradeoff function identifies Type I and Type II errors for a likelihood-ratio test, linking its distribution identities to the test’s error rates.Source: G Omitted proofs in Appendix B · p. 42
  • The tradeoff function determines the hockey-stick divergence and the distributions of log likelihood ratios under P and Q, so it also determines φ and φ′.The proof constructs a pair P′, Q′ realizing the tradeoff function to express φ.Source: G Omitted proofs in Appendix B · pp. 42–43
Loading 2106.08567v3…