Basic and advanced adaptive composition

Let databases be finite-support record-count functions, with neighbors differing by one added or removed record occurrence. For $k\ge 1$, let round $i$ be a probability kernel $K_i(D,h,\cdot )$ on the $i$th arbitrary measurable output space, conditional on every prior transcript $h$. Suppose that for every ordered neighboring pair $D\sim D^{\mathrm{\prime }}$, every $h$, and every measurable round-$i$ event $A$,

$$K_i(D,h,A)\le e^{{\epsilon }_i}{K}_i(D^{\mathrm{\prime }},h,A)+{\delta }_i,$$

where ${\epsilon }_i\ge 0$ and ${\delta }_i\ge 0$. If ${\sum }_i{\delta }_i\le 1$, the full transcript on the finite product sigma-algebra is $({\sum }_i{\epsilon }_i,{\sum }_i{\delta }_i)$-differentially private. Also, assuming AC, if every conditional round has the same parameters $(\epsilon ,\delta )$ with $\epsilon \ge 0$ and $0\le \delta \le 1$, then for any $0<{\delta }^{\mathrm{\prime }}<1$ with $k\delta +{\delta }^{\mathrm{\prime }}\le 1$, advanced composition on arbitrary measurable output spaces gives parameters $({\epsilon }^{\mathrm{\prime }},k\delta +{\delta }^{\mathrm{\prime }})$, where

$${\epsilon }^{\mathrm{\prime }}=\sqrt{2k\ln (1\mathrm{/}{\delta }^{\mathrm{\prime }})}\epsilon +k\epsilon (e^{\epsilon }-1)\mathrm{.}$$

Basic adaptive composition on arbitrary measurable output spaces

Advanced composition on arbitrary measurable output spaces

Dwork and Roth, The Algorithmic Foundations of Differential Privacy, §3.5, Theorems 3.16 and 3.20, printed pp. 43–51.

Vadhan, The Complexity of Differential Privacy, §2.2, Lemmas 2.3–2.4 and their proofs.