From 0878be3e6e99f3016caba0ad881c499607549901 Mon Sep 17 00:00:00 2001 From: Yuchen Pei Date: Mon, 25 Mar 2019 23:14:42 +0100 Subject: added reference for the composition thm --- posts/2019-03-13-a-tail-of-two-densities.md | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'posts') diff --git a/posts/2019-03-13-a-tail-of-two-densities.md b/posts/2019-03-13-a-tail-of-two-densities.md index 41a3b57..d3cdeb2 100644 --- a/posts/2019-03-13-a-tail-of-two-densities.md +++ b/posts/2019-03-13-a-tail-of-two-densities.md @@ -1085,6 +1085,12 @@ $i$ and $y_{1 : i}$, $M_i(y_{1 : i})$ is $(\epsilon, \delta)$-dp. Then the adpative composition of $M_{1 : k}$ is $(k a(\epsilon) + \sqrt{2 k \log \beta^{-1}} (\epsilon + a(\epsilon)), \beta + k \delta)$-dp. +**Remark**. +This theorem appeared in Dwork-Rothblum-Vadhan 2010, but I could not find a proof there. +A proof can be found in Dwork-Roth 2013 (See Theorem 3.20 there). +Here I prove it in a similar way, except that I use the conditional probability results +as in Claim 5 instead of use of an intermediate random variable. + **Proof**. By Claim 5, there exist events $E_{1 : k}$ and $F_{1 : k}$ such that -- cgit v1.2.3