aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorYuchen Pei <me@ypei.me>2019-03-20 14:11:36 +0100
committerYuchen Pei <me@ypei.me>2019-03-20 14:11:36 +0100
commit601309e8bc8162d29b8dd3ff4ef716805f17e506 (patch)
treebb6d699f78eb205ded47b7ab6334b61ae41994f8
parent31f1546d123eb571661f0e7373b7cae0d6b26dad (diff)
reddit peer review - wikipedia links to stuff
-rw-r--r--posts/2019-03-13-a-tail-of-two-densities.md12
1 files changed, 7 insertions, 5 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 a7a39cf..26f4ad5 100644
--- a/posts/2019-03-13-a-tail-of-two-densities.md
+++ b/posts/2019-03-13-a-tail-of-two-densities.md
@@ -6,9 +6,10 @@ comments: true
---
This is Part 1 of a two-part post where I give an introduction to
-differential privacy, which is a study of tail bounds of the divergence between
-two probability measures, with the end goal of applying it to stochastic
-gradient descent.
+differential privacy, a study of [tail bounds](https://en.wikipedia.org/wiki/Concentration_inequality)
+of the divergence between
+two probability measures, with the end goal of applying it to [stochastic
+gradient descent](https://en.wikipedia.org/wiki/Stochastic_gradient_descent).
I start with the definition of $\epsilon$-differential privacy
(corresponding to max divergence), followed by
@@ -223,7 +224,7 @@ One interesting and readily verifiable fact is
$$\mathbb E L(p || q) = D(p || q)$$
-where $D$ is the KL-divergence.
+where $D$ is the [KL-divergence](https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence).
**Claim 1**. If
@@ -964,7 +965,8 @@ $$\mathbb P(L(q || p) \le k a(\epsilon) + \sqrt{2 k \epsilon^2 \log \beta^{-1}})
By Claim 1 we arrive at the conclusion. $\square$
**Claim 15 (Azuma\'s Inequality)**.
-Let $X_{0 : k}$ be a supermartingale. If $|X_i - X_{i - 1}| \le b$, then
+Let $X_{0 : k}$ be a [supermartingale](https://en.wikipedia.org/wiki/Martingale_(probability_theory)).
+If $|X_i - X_{i - 1}| \le b$, then
$$\mathbb P(X_k - X_0 \ge t) \le \exp(- {t^2 \over 2 k b^2}).$$