From e9795c6b134eed858ddb73c036ff5c941d7e9838 Mon Sep 17 00:00:00 2001
From: Yuchen Pei <me@ypei.me>
Date: Fri, 18 Jun 2021 17:47:12 +1000
Subject: Updated.

---
 posts/2019-03-13-a-tail-of-two-densities.org | 8 ++++++++
 1 file changed, 8 insertions(+)

(limited to 'posts/2019-03-13-a-tail-of-two-densities.org')

diff --git a/posts/2019-03-13-a-tail-of-two-densities.org b/posts/2019-03-13-a-tail-of-two-densities.org
index 783e0c5..f1b6b15 100644
--- a/posts/2019-03-13-a-tail-of-two-densities.org
+++ b/posts/2019-03-13-a-tail-of-two-densities.org
@@ -80,6 +80,7 @@ BY-SA]] and [[https://www.gnu.org/licenses/fdl.html][GNU FDL]]./
 ** The gist of differential privacy
    :PROPERTIES:
    :CUSTOM_ID: the-gist-of-differential-privacy
+   :ID:       91bf2eb5-8509-4180-b471-939280dc1438
    :END:
 If you only have one minute, here is what differential privacy is about:
 
@@ -118,6 +119,7 @@ Now if you have an hour...
 ** \(\epsilon\)-dp
    :PROPERTIES:
    :CUSTOM_ID: epsilon-dp
+   :ID:       d29da3db-8b9a-4bad-811e-4af1cd9f856d
    :END:
 *Definition (Mechanisms)*. Let \(X\) be a space with a metric
 \(d: X \times X \to \mathbb N\). A /mechanism/ \(M\) is a function that
@@ -188,6 +190,7 @@ where in the last step we use the condition (1.5). \(\square\)
 ** Approximate differential privacy
    :PROPERTIES:
    :CUSTOM_ID: approximate-differential-privacy
+   :ID:       c48c68f8-d749-47f8-b5de-c92cc53f8cea
    :END:
 Unfortunately, \(\epsilon\)-dp does not apply to the most commonly used
 noise, the Gaussian noise. To fix this, we need to relax the definition
@@ -205,6 +208,7 @@ if \(\delta < 1\).
 *** Indistinguishability
     :PROPERTIES:
     :CUSTOM_ID: indistinguishability
+    :ID:       7875ad81-326b-4eaa-a3ae-9e09df96ea1b
     :END:
 To understand \((\epsilon, \delta)\)-dp, it is helpful to study
 \((\epsilon, \delta)\)-indistinguishability.
@@ -535,6 +539,7 @@ The rest of the proof is almost the same as the proof of Claim 4.
 *** Back to approximate differential privacy
     :PROPERTIES:
     :CUSTOM_ID: back-to-approximate-differential-privacy
+    :ID:       706c037d-ea44-4ade-8007-7f1f41d394e8
     :END:
 By Claim 0 and 1 we have
 
@@ -741,6 +746,7 @@ proof of Theorem A.1.
 ** Composition theorems
    :PROPERTIES:
    :CUSTOM_ID: composition-theorems
+   :ID:       b672a060-d886-4f07-92d2-1d92f5f4c0c8
    :END:
 So far we have seen how a mechanism made of a single query plus a noise
 can be proved to be differentially private. But we need to understand
@@ -1108,6 +1114,7 @@ The rest is the same as in the proof of Claim 17. \(\square\)
 ** Subsampling
    :PROPERTIES:
    :CUSTOM_ID: subsampling
+   :ID:       eeda51d4-9370-49c6-9710-9c9ab88f91e2
    :END:
 Stochastic gradient descent is like gradient descent, but with random
 subsampling.
@@ -1257,6 +1264,7 @@ guarantee for DP-SGD, among other things.
 ** References
    :PROPERTIES:
    :CUSTOM_ID: references
+   :ID:       65686625-6bd1-4e42-b00d-5f1744945884
    :END:
 
 - Abadi, Martín, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya
-- 
cgit v1.2.3