diff options
Diffstat (limited to 'posts/2019-03-13-a-tail-of-two-densities.org')
| -rw-r--r-- | posts/2019-03-13-a-tail-of-two-densities.org | 8 |
1 files changed, 8 insertions, 0 deletions
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 |