aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--posts/2019-03-13-a-tail-of-two-densities.md6
1 files changed, 6 insertions, 0 deletions
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