Advanced adaptive composition for standard-Borel outputs

Fix neighboring databases $D,D^{\mathrm{\prime }}$. By [F2], every finite history space is standard Borel. To apply the infinite-sequence form of [F3], append after round $k$ a singleton output space and its unique probability kernel at every later round. The first $k$ coordinates of the resulting path law have exactly the desired finite transcript law; do this for $D$ and $D^{\mathrm{\prime }}$ to obtain $P$ and $Q$. Event evaluations of these laws are measurable in the database by [F1].

We first prove the one-sided estimate from $P$ to $Q$. Set $P_0^{\ast }=Q_0$ equal to the point mass on the empty history. Recursively, after constructing the modified $D$-transcript prefix law $P_{i-1}^{\ast }$, apply [F6] to the round-$i$ pair $K_i(D,h,\cdot ),K_i(D^{\mathrm{\prime }},h,\cdot )$ with base history law ${\lambda }_i=P_{i-1}^{\ast }$. This gives a probability kernel $K_i^{\ast }$ that is pure $\epsilon$ relative to $K_i(D^{\mathrm{\prime }},h,\cdot )$ in both event directions for ${\lambda }_i$-almost every $h$, with $\int \mathrm{TV}(K_i(D,h,\cdot ),K_i^{\ast }(h,\cdot ))P_{i-1}^{\ast }(dh)\le \delta$. Composing the finite modified sequence by [F3] gives a law $P^{\ast }$ and its prefix laws $P_i^{\ast }$.

The prefix laws $P_i^{\ast }$ and $Q_i$ are mutually absolutely continuous for each $i$. They agree at the empty history. If they are equivalent at $i-1$, then for a product-measurable event $B$ with $Q_i(B)=0$, the iterated integral formula [F3] gives $K_i(D^{\mathrm{\prime }},h,B_h)=0$ for $Q_{i-1}$-almost every $h$, hence for $P_{i-1}^{\ast }$-almost every $h$. The pure reverse inequality from step 1.2 gives $K_i^{\ast }(h,B_h)=0$, so $P_i^{\ast }(B)=0$. Reversing the two kernels proves the converse; induction gives prefix equivalence.

For each $i$, apply [F4] with base measure $P_{i-1}^{\ast }$ to obtain a jointly measurable density $r_i(h,y)$ of $K_i^{\ast }(h,\cdot )$ with respect to $K_i(D^{\mathrm{\prime }},h,\cdot )$ on one common conull history set. The pure event inequalities imply $e^{-\epsilon }\le r_i\le e^{\epsilon }$ almost surely there: if either bound failed on a positive-measure fiber set, some level set separated from that bound by $1\mathrm{/}n$ would contradict one event inequality. Clip $r_i$ everywhere to $[e^{-\epsilon },e^{\epsilon }]$; Borel composition preserves measurability, the density is unchanged on the conull set, and $X_i(h,y)=\ln r_i(h,y)$ is jointly measurable with $\mathrm{\mid }{X}_i\mathrm{\mid }\le \epsilon$.

We prove the density formula by induction on prefix length. At the first round, [F4] gives $d{P}_1^{\ast }\mathrm{/}d{Q}_1=r_1$. Suppose $R_{i-1}={\prod }_{j<i}{r}_j$ is the density on the first $i-1$ outputs. For a measurable event $A$ on the first $i$ outputs, [F3] gives $P_i^{\ast }(A)=\int P_{i-1}^{\ast }(dh)\int {\mathbf{1}}_A(h,y)K_i^{\ast }(h,dy)$. For almost every $h$, [F4] replaces the inner integral by $\int {\mathbf{1}}_A(h,y)r_i(h,y)K_i(D^{\mathrm{\prime }},h,dy)$. Applying [F11] to the outer prefix integral with density $R_{i-1}$ yields $P_i^{\ast }(A)=\int Q_{i-1}(dh)R_{i-1}(h)\int {\mathbf{1}}_A(h,y)r_i(h,y)K_i(D^{\mathrm{\prime }},h,dy)={\int }_A{R}_{i-1}(h)r_i(h,y)Q_i(dh,dy)$. This proves the induction and hence $d{P}^{\ast }\mathrm{/}dQ=R={\prod }_{i=1}^k{r}_i(H_{i-1},Y_i)$. Since every factor is positive and bounded, [F15] gives $\ln R={\sum }_{i=1}^k{X}_i(H_{i-1},Y_i)$ almost surely under both laws.

Put $m_i(h)=\int X_i(h,y)K_i^{\ast }(h,dy)$. By the density formula and KL definition, $m_i(h)=D(K_i^{\ast }(h,\cdot )\mathrm{\parallel }{K}_i(D^{\mathrm{\prime }},h,\cdot ))\le b$ for $P_{i-1}^{\ast }$-almost every $h$, using [F5]. It is measurable by [F7] and [F12]. For every measurable prefix event $C$, the iterated-prefix identity [F3] gives ${\int }_{\{H_{i-1}\in C\}}{X}_{i}d{P}^{\ast }={\int }_C{m}_i(h)P_{i-1}^{\ast }(dh)$. Thus [F8] identifies $m_i(H_{i-1})$ as the conditional expectation of $X_i$ given the previous transcript. By [F14], the variables are integrable, so $M_j={\sum }_{i\le j}(X_i-m_i(H_{i-1}))$ is a martingale. Each increment lies in the history-measurable interval $[-\epsilon -m_i,\epsilon -m_i]$, of length $2\epsilon$.

If $\epsilon =0$, every $X_i=0$, so $P^{\ast }=Q$ and the pure transcript has zero privacy loss. If $\epsilon >0$, apply [F9] to step 4.2 with $c_i=2\epsilon$ and $t=\epsilon \sqrt{2k\ln (1\mathrm{/}{\delta }^{\mathrm{\prime }})}$. It gives $P^{\ast }(M_k\ge t)\le {\delta }^{\mathrm{\prime }}$. Since ${\sum }_i{m}_i\le kb$ almost surely, the privacy loss exceeds ${\epsilon }^{\mathrm{\prime }}=kb+t$ with probability at most ${\delta }^{\mathrm{\prime }}$. For any event $A$, split it into $A\cap \{\ln R\le {\epsilon }^{\mathrm{\prime }}\}$ and $A\cap \{\ln R>{\epsilon }^{\mathrm{\prime }}\}$; the density formula in step 4.1 bounds the first probability by $e^{{\epsilon }^{\mathrm{\prime }}}Q(A)$ and the second by ${\delta }^{\mathrm{\prime }}$. Thus $P^{\ast }(A)\le e^{{\epsilon }^{\mathrm{\prime }}}Q(A)+{\delta }^{\mathrm{\prime }}$. Applying the same argument under $Q$ with the roles reversed gives $Q(A)\le e^{{\epsilon }^{\mathrm{\prime }}}{P}^{\ast }(A)+{\delta }^{\mathrm{\prime }}$, because the conditional kernels are pure in both directions and [F5] bounds both KL orientations.

We compare $P$ and $P^{\ast }$ in total variation. For $i=0,\dots ,k$, let $H_i$ be the transcript law that uses the modified $D$ kernels for rounds $1,\dots ,i$ and the original $D$ kernels for rounds $i+1,\dots ,k$. Consecutive laws share the modified prefix through round $i-1$, whose law is $P_{i-1}^{\ast }$, and differ only in the round-$i$ kernel; after that round they use the same continuation kernels. For any final event, integrating that common continuation gives a measurable conditional probability $g(h,y)$ in $[0,1]$ by [F12]. The two-sided test-function bound [F10] and the integrated TV bound in step 1.2 yield $\mathrm{TV}(H_{i-1},H_i)\le \delta$. The triangle inequality gives $\mathrm{TV}(P,P^{\ast })\le k\delta$, hence $P(A)\le P^{\ast }(A)+k\delta$. Combining with step 5.1 proves $P(A)\le e^{{\epsilon }^{\mathrm{\prime }}}Q(A)+k\delta +{\delta }^{\mathrm{\prime }}$.

Repeat steps 1.2–6.1 with $D^{\mathrm{\prime }}$ as the modified side and $D$ as the reference side. This gives $Q(A)\le e^{{\epsilon }^{\mathrm{\prime }}}P(A)+k\delta +{\delta }^{\mathrm{\prime }}$. The ordered pair and event were arbitrary, so [F1] proves the stated differential-privacy guarantee. The condition $k\delta +{\delta }^{\mathrm{\prime }}\le 1$ keeps the additive parameter in its declared nontrivial range; no step weakens the claimed epsilon.