Basic and advanced privacy composition

Basic composition adds the epsilons; advanced composition gives \(\sqrt{2k\log(1/\delta')}\,\epsilon + k\epsilon(e^\epsilon - 1)\) at the cost of a delta.

Usage

morie_basic_composition(epsilons, delta_prime = NULL, deltas = NULL)

Arguments

epsilons

per-mechanism epsilons.

delta_prime

the delta advanced composition spends; NULL to report basic composition only.

deltas

optional per-mechanism deltas.

Value

list with basic_epsilon, advanced_epsilon, total_delta, recommended, epsilon.

Details

Advanced composition is not uniformly better and reaching for it by reflex is a common error. Its \(\sqrt k\) term only overtakes the linear one when k is large AND epsilon is small; for a handful of queries, or for loose per-query budgets, the second term dominates and basic composition wins. This function computes both and says which.

References

Dwork, C., Rothblum, G. N. and Vadhan, S. (2010). Boosting and differential privacy. FOCS, 51-60.

Examples

morie_basic_composition(rep(0.1, 50), delta_prime = 1e-6)$recommended
#> [1] "advanced"