added a post

1 files changed, 752 insertions, 0 deletions

diff --git a/posts/2019-03-14-great-but-manageable-expectations.md b/posts/2019-03-14-great-but-manageable-expectations.md
new file mode 100644
index 0000000..6c4e04e
--- /dev/null
+++ b/posts/2019-03-14-great-but-manageable-expectations.md
@@ -0,0 +1,752 @@
+---
+title: 'Great, but Manageable Expectations'
+date: 2019-03-14
+template: post
+comments: true
+---
+
+Let us continue with the study of differential privacy from [Part 1 of this post](2019-03-13-a-tail-of-two-densities.html).
+
+Rényi divergence and differential privacy 
+-----------------------------------------
+
+Recall in the proof of Gaussian mechanism privacy guarantee (Claim 8) we
+used the Chernoff bound for the Gaussian noise. Why not use the Chernoff
+bound for the divergence variable / privacy loss directly, since the
+latter is closer to the core subject than the noise? This leads us to
+the study of Rényi divergence.
+
+So far we have seen several notions of divergence used in differential
+privacy: the max divergence which is $\epsilon$-ind in disguise:
+
+$$D_\infty(p || q) := \max_y \log {p(y) \over q(y)},$$
+
+the $\delta$-approximate max divergence that defines the
+$(\epsilon, \delta)$-ind:
+
+$$D_\infty^\delta(p || q) := \max_y \log{p(y) - \delta \over q(y)},$$
+
+and the KL-divergence which is the expectation of the divergence
+variable:
+
+$$D(p || q) = \mathbb E L(p || q) = \int \log {p(y) \over q(y)} p(y) dy.$$
+
+The Rényi divergence is an interpolation between the max divergence and
+the KL-divergence, defined as the log moment generating function /
+cumulants of the divergence variable:
+
+$$D_\lambda(p || q) = (\lambda - 1)^{-1} \log \mathbb E \exp((\lambda - 1) L(p || q)) = (\lambda - 1)^{-1} \log \int {p(y)^\lambda \over q(y)^{\lambda - 1}} dx.$$
+
+Indeed, when $\lambda \to \infty$ we recover the max divergence, and
+when $\lambda \to 1$, by recognising $D_\lambda$ as a derivative in
+$\lambda$ at $\lambda = 1$, we recover the KL divergence. In this post
+we only consider $\lambda > 1$.
+
+Using the Rényi divergence we may define:
+
+**Definition (Rényi
+differential privacy)** (Mironov 2017). An mechanism $M$ is
+$(\lambda, \rho)$*-Rényi differentially private* ($(\lambda, \rho)$-rdp)
+if for all $x$ and $x'$ with distance $1$,
+
+$$D_\lambda(M(x) || M(x')) \le \rho.$$
+
+For convenience we also define two related notions, $G_\lambda (f || g)$
+and $\kappa_{f, g} (t)$ for $\lambda > 1$, $t > 0$ and positive
+functions $f$ and $g$:
+
+$$G_\lambda(f || g) = \int f(y)^{\lambda} g(y)^{1 - \lambda} dy; \qquad \kappa_{f, g} (t) = \log G_{t + 1}(f || g).$$
+
+For probability densities $p$ and $q$, $G_{t + 1}(p || q)$ and
+$\kappa_{p, q}(t)$ are the $t$th moment generating function and cumulant
+of the divergence variable $L(p || q)$, and
+
+$$D_\lambda(p || q) = (\lambda - 1)^{-1} \kappa_{p, q}(\lambda - 1).$$
+
+In the following, whenever you see $t$, think of it as $\lambda - 1$.
+
+**Example 1 (RDP for Gaussian
+mechanism)**. Using the scaling and translation invariance of $L$ (6.1),
+we have that the divergence variable for two Gaussians with the same
+variance is
+
+$$L(N(\mu_1, \sigma^2) || N(\mu_2, \sigma^2)) \overset{d}{=} L(N(0, 1) || N((\mu_2 - \mu_1) / \sigma, 1)).$$
+
+With this we get
+
+$$D_\lambda(N(\mu_1, \sigma^2) || N(\mu_2, \sigma^2)) = {\lambda (\mu_2 - \mu_1)^2 \over 2 \sigma^2} = D_\lambda(N(\mu_2, \sigma^2) || N(\mu_1, \sigma^2)).$$
+
+Also due to the scaling invariance of $L$, we only need to consider $f$
+with sensitivity $1$, see the discussion under (6.1). The Gaussian
+mechanism on query $f$ is thus $(\lambda, \lambda / 2 \sigma^2)$-rdp for
+any $\lambda > 1$.
+
+From the example of Gaussian mechanism, we see that the relation between
+$\lambda$ and $\rho$ is like that between $\epsilon$ and $\delta$. Given
+$\lambda$ (resp. $\rho$) and parameters like variance of the noise and
+the sensitivity of the query, we can write $\rho = \rho(\lambda)$ (resp.
+$\lambda = \lambda(\rho)$).
+
+Using the Chernoff bound (6.7), we can bound the divergence variable:
+
+$$\mathbb P(L(p || q) \ge \epsilon) \le {\mathbb E \exp(t L(p || q)) \over \exp(t \epsilon))} =  \exp (\kappa_{p, q}(t) - \epsilon t). \qquad (7.7)$$
+
+For a function $f: I \to \mathbb R$, denote its Legendre transform by
+
+$$f^*(\epsilon) := \sup_{t \in I} (\epsilon t - f(t)).$$
+
+By taking infimum on the RHS of (7.7), we obtain
+
+**Claim 20**. Two probability densities $p$ and $q$ are
+$(\epsilon, \exp(-\kappa_{p, q}^*(\epsilon)))$-ind.
+
+Given a mechanism $M$, let $\kappa_M(t)$ denote an upper bound for the
+cumulant of its privacy loss:
+
+$$\log \mathbb E \exp(t L(M(x) || M(x'))) \le \kappa_M(t), \qquad \forall x, x'\text{ with } d(x, x') = 1.$$
+
+For example, we can set $\kappa_M(t) = t \rho(t + 1)$. Using the same
+argument we have the following:
+
+**Claim 21**.
+
+1.  If $M$ is $(\lambda, \rho)$-rdp, then it is also
+    $(\epsilon, \exp((\lambda - 1) (\rho - \epsilon)))$-dp for any
+    $\epsilon \ge \rho$.
+2.  Alternatively, $M$ is $(\epsilon, - \exp(\kappa_M^*(\epsilon)))$-dp
+    for any $\epsilon > 0$.
+3.  Alternatively, for any $0 < \delta \le 1$, $M$ is
+    $(\rho + (\lambda - 1)^{-1} \log \delta^{-1}, \delta)$-dp.
+
+**Example 2 (Gaussian mechanism)**.
+We can apply the above argument to the Gaussian mechanism on query $f$
+and get:
+
+$$\delta \le \inf_{\lambda > 1} \exp((\lambda - 1) ({\lambda \over 2 \sigma^2} - \epsilon))$$
+
+By assuming $\sigma^2 > (2 \epsilon)^{-1}$ we have that the infimum is
+achieved when $\lambda = (1 + 2 \epsilon / \sigma^2) / 2$ and
+
+$$\delta \le \exp(- ((2 \sigma)^{-1} - \epsilon \sigma)^2 / 2)$$
+
+which is the same result as (6.8), obtained using the Chernoff bound of
+the noise.
+
+However, as we will see later, compositions will yield different results
+from those obtained from methods in [Part 1](2019-03-13-a-tail-of-two-densities.html) when considering Rényi dp.
+
+**Claim 22 (Moment Composition
+Theorem)**. Let $M$ be the adaptive composition of $M_{1 : k}$. Suppose
+for any $y_{< i}$, $M_i(y_{< i})$ is $(\lambda, \rho)$-rdp. Then $M$ is
+$(\lambda, k\rho)$-rdp.
+
+**Proof**. Rather straightforward. As before let $p_i$ and
+$q_i$ be the conditional laws of adpative composition of $M_{1 : i}$ at
+$x$ and $x'$ respectively, and $p^i$ and $q^i$ be the joint laws of
+$M_{1 : i}$ at $x$ and $x'$ respectively. Denote
+
+$$D_i = \mathbb E \exp((\lambda - 1)\log {p^i(\xi_{1 : i}) \over q^i(\xi_{1 : i})})$$
+
+Then
+
+$$\begin{aligned}
+D_i &= \mathbb E\mathbb E \left(\exp((\lambda - 1)\log {p_i(\xi_i | \xi_{< i}) \over q_i(\xi_i | \xi_{< i})}) \exp((\lambda - 1)\log {p^{i - 1}(\xi_{< i}) \over q^{i - 1}(\xi_{< i})}) \big| \xi_{< i}\right) \\
+&= \mathbb E \mathbb E \left(\exp((\lambda - 1)\log {p_i(\xi_i | \xi_{< i}) \over q_i(\xi_i | \xi_{< i})}) | \xi_{< i}\right) \exp\left((\lambda - 1)\log {p^{i - 1}(\xi_{< i}) \over q^{i - 1}(\xi_{< i})}\right)\\
+&\le \mathbb E \exp((\lambda - 1) \rho) \exp\left((\lambda - 1)\log {p^{i - 1}(\xi_{< i}) \over q^{i - 1}(\xi_{< i})}\right)\\
+&= \exp((\lambda - 1) \rho) D_{i - 1}.
+\end{aligned}$$
+
+Applying this recursively we have
+
+$$D_k \le \exp(k(\lambda - 1) \rho),$$
+
+and so
+
+$$(\lambda - 1)^{-1} \log \mathbb E \exp((\lambda - 1)\log {p^k(\xi_{1 : i}) \over q^k(\xi_{1 : i})}) = (\lambda - 1)^{-1} \log D_k \le k \rho.$$
+
+Since this holds for all $x$ and $x'$, we are done. $\square$
+
+This, together with the scaling property of the legendre transformation:
+
+$$(k f)^*(x) = k f^*(x / k)$$
+
+yields
+
+**Claim 23**. The $k$-fold adaptive composition of
+$(\lambda, \rho(\lambda))$-rdp mechanisms is
+$(\epsilon, \exp(- k \kappa^*(\epsilon / k)))$-dp, where
+$\kappa(t) := t \rho(t + 1)$.
+
+**Example 3 (Gaussian mechanism)**.
+We can apply the above claim to Gaussian mechanism. Again, without loss
+of generality we assume $S_f = 1$. But let us do it manually to get the
+same results. If we apply the Moment Composition Theorem to the an
+adaptive composition of Gaussian mechanisms on the same query, then
+since each $M_i$ is $(\lambda, (2 \sigma^2)^{-1} \lambda)$-rdp, the
+composition $M$ is $(\lambda, (2 \sigma^2)^{-1} k \lambda)$-rdp.
+Processing this using the Chernoff bound as in the previous example, we
+have
+
+$$\delta = \exp(- ((2 \sigma / \sqrt k)^{-1} - \epsilon \sigma / \sqrt k)^2 / 2),$$
+
+Substituting $\sigma$ with $\sigma / \sqrt k$ in (6.81), we conclude
+that if
+
+$$\sigma > \sqrt k \left(\epsilon^{-1} \sqrt{2 \log \delta^{-1}} + (2 \epsilon)^{- {1 \over 2}}\right)$$
+
+then the composition $M$ is $(\epsilon, \delta)$-dp.
+
+As we will see in the discussions at the end of this post, this result
+is different from (and probably better than) the one obtained by using
+the Advanced Composition Theorem (Claim 18).
+
+We also have a subsampling theorem for the Rényi dp.
+
+**Claim 24**. Fix $r \in [0, 1]$. Let $m \le n$ be two
+nonnegative integers with $m = r n$. Let $N$ be a $(\lambda, \rho)$-rdp
+machanism on $X^m$. Let $\mathcal I := \{J \subset [n]: |J| = m\}$ be
+the set of subsets of $[n]$ of size $m$. Define mechanism $M$ on $X^n$
+by
+
+$$M(x) = N(x_\gamma)$$
+
+where $\gamma$ is sampled uniformly from $\mathcal I$. Then $M$ is
+$(\lambda, {1 \over \lambda - 1} \log (1 + r(e^{(\lambda - 1) \rho} - 1)))$-rdp.
+
+To prove Claim 24, we need a useful lemma:
+
+{#Claim 25}**Claim 25**. Let $p_{1 : n}$ and $q_{1 : n}$ be
+nonnegative integers, and $\lambda > 1$. Then
+
+$${(\sum p_i)^\lambda \over (\sum q_i)^{\lambda - 1}} \le \sum_i {p_i^\lambda \over q_i^{\lambda - 1}}. \qquad (8)$$
+
+**Proof**. Let
+
+$$r(i) := p_i / P, \qquad u(i) := q_i / Q$$
+
+where
+
+$$P := \sum p_i, \qquad Q := \sum q_i$$
+
+then $r$ and $u$ are probability mass functions. Plugging in
+$p_i = r(i) P$ and $q_i = u(i) Q$ into the objective (8), it suffices to
+show
+
+$$1 \le \sum_i {r(i)^\lambda \over u(i)^{\lambda - 1}} = \mathbb E_{\xi \sim u} \left({r(\xi) \over u(\xi)}\right)^\lambda$$
+
+This is true due to Jensen\'s Inequality:
+
+$$\mathbb E_{\xi \sim u} \left({r(\xi) \over u(\xi)}\right)^\lambda \ge \left(\mathbb E_{\xi \sim u} {r(\xi) \over u(\xi)} \right)^\lambda = 1.$$
+
+$\square$
+
+**Proof of Claim 24**. Define $\mathcal I$ as
+before.
+
+Let $p$ and $q$ be the laws of $M(x)$ and $M(x')$ respectively. For any
+$I \in \mathcal I$, let $p_I$ and $q_I$ be the laws of $N(x_I)$ and
+$N(x_I')$ respectively. Then we have
+
+$$\begin{aligned}
+p(y) &= n^{-1} \sum_{I \in \mathcal I} p_I(y) \\
+q(y) &= n^{-1} \sum_{I \in \mathcal I} q_I(y),
+\end{aligned}$$
+
+where $n = |\mathcal I|$.
+
+The MGF of $L(p || q)$ is thus
+
+$$\mathbb E((\lambda - 1) L(p || q)) = n^{-1} \int {(\sum_I p_I(y))^\lambda \over (\sum_I q_I(y))^{\lambda - 1}} dy \le n^{-1} \sum_I \int {p_I(y)^\lambda \over q_I(y)^{\lambda - 1}} dy \qquad (9)$$
+
+where in the last step we used Claim 25. As in the proof of Claim 19, we
+divide $\mathcal I$ into disjoint sets $\mathcal I_\in$ and
+$\mathcal I_\notin$. Furthermore we denote by $n_\in$ and $n_\notin$
+their cardinalities. Then the right hand side of (9) becomes
+
+$$n^{-1} \sum_{I \in \mathcal I_\in} \int {p_I(y)^\lambda \over q_I(y)^{\lambda - 1}} dy + n^{-1} \sum_{I \in \mathcal I_\notin} \int {p_I(y)^\lambda \over q_I(y)^{\lambda - 1}} dy$$
+
+The summands in the first are the MGF of $L(p_I || q_I)$, and the
+summands in the second term are $1$, so
+
+$$\begin{aligned}
+\mathbb E((\lambda - 1) L(p || q)) &\le n^{-1} \sum_{I \in \mathcal I_\in} \mathbb E \exp((\lambda - 1) L(p_I || q_I)) + (1 - r) \\
+&\le n^{-1} \sum_{I \in \mathcal I_\in} \exp((\lambda - 1) D_\lambda(p_I || q_I)) + (1 - r) \\
+&\le r \exp((\lambda - 1) \rho) + (1 - r).
+\end{aligned}$$
+
+Taking log and dividing by $(\lambda - 1)$ on both sides we have
+
+$$D_\lambda(p || q) \le (\lambda - 1)^{-1} \log (1 + r(\exp((\lambda - 1) \rho) - 1)).$$
+
+$\square$
+
+As before, we can rewrite the conclusion of Lemma 6 using
+$1 + z \le e^z$ and obtain
+$(\lambda, (\lambda - 1)^{-1} r (e^{(\lambda - 1) \rho} - 1))$-rdp,
+which further gives $(\lambda, \alpha^{-1} (e^\alpha - 1) r \rho)$-rdp
+(or $(\lambda, O(r \rho))$-rdp) if $(\lambda - 1) \rho < \alpha$ for
+some $\alpha$.
+
+It is not hard to see that the subsampling theorem in moment method,
+even though similar to the results of that in the usual method, does not
+help due to lack of an analogue of advanced composition theorem of the
+moments.
+
+**Example 4 (Gaussian mechanism)**.
+Applying the moment subsampling theorem to the Gaussian mechanism, we
+obtain $(\lambda, O(r \lambda / \sigma^2))$-rdp for a subsampled
+Gaussian mechanism with rate $r$.
+Abadi-Chu-Goodfellow-McMahan-Mironov-Talwar-Zhang 2016 (ACGMMTZ16 in the
+following), however, gains an extra $r$ in the bound given certain
+assumptions.
+
+ACGMMTZ16 
+---------
+
+What follows is my understanding of this result. I call it a hypothesis
+because there is a gap which I am not able to reproduce their proof or
+prove it myself. This does not mean the result is false. On the
+contrary, I am inclined to believe it is true.
+
+**Hypothesis 0**. For a subsampled Gaussian mechanism
+with ratio $r$, if $r = O(\sigma^{-1})$ and $\lambda = O(\sigma^2)$,
+then we have $(\lambda, O(r^2 \lambda / \sigma^2))$-rdp.
+
+Recall the definition of $G_\lambda$ under the definition of Rényi
+differential privacy. The following Claim will be useful.
+
+**Claim 26**. Let $\lambda$ be a positive integer, then
+
+$$G_\lambda(r p + (1 - r) q || q) = \sum_{k = 1 : \lambda} {\lambda \choose k} r^k (1 - r)^{\lambda - k} G_k(p || q).$$
+
+**Proof**. Quite straightforward, by expanding the numerator
+$(r p + (1 - r) q)^\lambda$ using binomial expansion. $\square$
+
+**Proof of Hypothesis 0
+(Incomplete)**. I will break the proof into two parts and discuss each
+one.
+
+1.  The MGF of the privacy loss is bounded by that of
+    $L(r \mu_1 + (1 - r) \mu_0 || \mu_0)$ where
+    $\mu_i = N(i, \sigma^2)$.
+2.  If $r \le c_1 \sigma^{-1}$ and $\lambda \le c_2 \sigma^2$, then
+    there exists $C = C(c_1, c_2)$ such that
+    $G_\lambda (r \mu_1 + (1 - r) \mu_0 || \mu_0) \le C$ (since
+    $O(r^2 \lambda^2 / \sigma^2) = O(1)$).
+
+**Remark in the proof**. Note that the choice of
+$c_1$, $c_2$ and the function $C(c_1, c_2)$ are important to the
+practicality and usefulness of Hypothesis 0.
+
+Item 1 can be deduced from the following hypothesis, which, as the only
+gap in the Proof of Hypothesis 0, is heuristically reasonable, hence why
+I am inclined to believe Hypothesis 0 is true.
+
+**Hypothesis 1**. Let $p_i$, $q_i$, $\mu_i$, $\nu_i$ be
+probability densities on the same space for $i = 1 : n$. If
+$D_\lambda(p_i || q_i) \le D_\lambda(\mu_i || \nu_i)$ for all $i$, then
+
+$$D_\lambda(n^{-1} \sum_i p_i || n^{-1} \sum_i q_i) \le D_\lambda(n^{-1} \sum_i \mu_i || n^{-1} \sum_i \nu_i).$$
+
+Basically, it is saying \"if for each $i$, $p_i$ and $q_i$ are closer to
+each other than $\mu_i$ and $\nu_i$, then so is their average over
+$i$\".
+
+To see how Hypothesis 1 implies Item 1, note that
+
+$$D_\lambda(q_I || p_I) = D_\lambda(p_I || q_I) 
+\begin{cases}
+\le D_\lambda(\mu_0 || \mu_1) = D_\lambda(\mu_1 || \mu_0), & I \in \mathcal I_\in\\
+= D_\lambda(\mu_0 || \mu_0) = D_\lambda(\mu_1 || \mu_1) = 0 & I \in \mathcal I_\notin
+\end{cases}$$
+
+and that $p = |\mathcal I|^{-1} \sum_{I \in \mathcal I} p_I$ and
+$q = |\mathcal I|^{-1} \sum_{I \in \mathcal I} q_I$ and
+$|\mathcal I_\in| = r |\mathcal I|$.
+
+Alternatively, one may try to prove a weaker version of Hypothesis 1, by
+specialising on mixture of Gaussians.
+
+One way one may try to prove Hypothesis 1 is to prove an equivalent
+statement:
+
+**Hypothesis 2**. Let $p_1$, $q_1$, $p_2$, $q_2$,
+$\mu_1$, $\mu_2$, $\nu_1$, $\nu_2$ be probability densities, and suppose
+
+$$\int {p_i^\lambda \over q_i^{\lambda - 1}} \le \int {\mu_i^\lambda \over \nu_i^{\lambda - 1}}, \qquad i = 1, 2$$
+
+then
+
+$$\int {(p_1 + p_2)^\lambda \over (q_1 + q_2)^{\lambda - 1}} \le \int {(\mu_1 + \mu_1)^\lambda \over (\nu_1 + \nu_2)^{\lambda - 1}}.$$
+
+Indeed, on one hand, Hypothesis 2 is a special case of Hypothesis 1 and
+on the other hand, given Hypothesis 2, Hypothesis 1 can be shown using
+induction by replacing one pair of densities a time.
+
+Now let us prove Item 2.
+
+Using Claim 26 and Example 1, we have
+
+$$\begin{aligned}
+G_\lambda(r \mu_1 + (1 - r) \mu_0 || \mu_0)) &= \sum_{j = 0 : \lambda} {\lambda \choose j} r^j (1 - r)^{\lambda - j} G_j(\mu_1 || \mu_0)\\
+&=\sum_{j = 0 : \lambda} {\lambda \choose j} r^j (1 - r)^{\lambda - j} \exp(j (j - 1) / 2 \sigma^2). \qquad (9.5)
+\end{aligned}$$
+
+Denote by $n = \lceil \sigma^2 \rceil$. It suffices to show
+
+$$\sum_{j = 0 : n} {n \choose j} (c_1 n^{- 1 / 2})^j (1 - c_1 n^{- 1 / 2})^{n - j} \exp(c_2 j (j - 1) / 2 n) \le C$$
+
+Note that we can discard the linear term $- c_2 j / \sigma^2$ in the
+exponential term since we want to bound the sum from above.
+
+We examine the asymptotics of this sum when $n$ is large, and treat the
+sum as an approximation to an integration of a function
+$\phi: [0, 1] \to \mathbb R$. For $j = x n$, where $x \in (0, 1)$,
+$\phi$ is thus defined as (note we multiply the summand with $n$ to
+compensate the uniform measure on $1, ..., n$:
+
+$$\begin{aligned}
+\phi_n(x) &:= n {n \choose j} (c_1 n^{- 1 / 2})^j (1 - c_1 n^{- 1 / 2})^{n - j} \exp(c_2 j^2 / 2 n) \\
+&= n {n \choose x n} (c_1 n^{- 1 / 2})^{x n} (1 - c_1 n^{- 1 / 2})^{(1 - x) n} \exp(c_2 x^2 n / 2)
+\end{aligned}$$
+
+Using Stirling\'s approximation
+
+$$n! \approx \sqrt{2 \pi n} n^n e^{- n},$$
+
+we can approach the binomial coefficient:
+
+$${n \choose x n} \approx (\sqrt{2 \pi x (1 - x)} x^{x n} (1 - x)^{(1 - x) n})^{-1}.$$
+
+We also approximate
+
+$$(1 - c_1 n^{- 1 / 2})^{(1 - x) n} \approx \exp(- c_1 \sqrt{n} (1 - x)).$$
+
+With these we have
+
+$$\phi_n(x) \approx {1 \over \sqrt{2 \pi x (1 - x)}} \exp\left(- {1 \over 2} x n \log n + (x \log c_1 - x \log x - (1 - x) \log (1 - x) + {1 \over 2} c_2 x^2) n + {1 \over 2} \log n\right).$$
+
+This vanishes as $n \to \infty$, and since $\phi_n(x)$ is bounded above
+by the integrable function ${1 \over \sqrt{2 \pi x (1 - x)}}$ (c.f. the
+arcsine law), and below by $0$, we may invoke the dominant convergence
+theorem and exchange the integral with the limit and get
+
+$$\begin{aligned}
+\lim_{n \to \infty} &G_n (r \mu_1 + (1 - r) \mu_0 || \mu_0)) \\
+&\le \lim_{n \to \infty} \int \phi_n(x) dx = \int \lim_{n \to \infty} \phi_n(x) dx = 0.
+\end{aligned}$$
+
+Thus we have that the generating function of the divergence variable
+$L(r \mu_1 + (1 - r) \mu_0 || \mu_0)$ is bounded.
+
+Can this be true for better orders
+
+$$r \le c_1 \sigma^{- d_r},\qquad \lambda \le c_2 \sigma^{d_\lambda}$$
+
+for some $d_r \in (0, 1]$ and $d_\lambda \in [2, \infty)$? If we follow
+the same approximation using these exponents, then letting
+$n = c_2 \sigma^{d_\lambda}$,
+
+$$\begin{aligned}
+{n \choose j} &r^j (1 - r)^{n - j} G_j(\mu_0 || \mu_1) \le \phi_n(x) \\
+&\approx {1 \over \sqrt{2 \pi x (1 - x)}} \exp\left({1 \over 2} c_2^{2 \over d_\lambda} x^2 n^{2 - {2 \over d_\lambda}} - {d_r \over 2} x n \log n + (x \log c_1 - x \log x - (1 - x) \log (1 - x)) n + {1 \over 2} \log n\right).
+\end{aligned}$$
+
+So we see that to keep the divergence moments bounded it is possible to
+have any $r = O(\sigma^{- d_r})$ for $d_r \in (0, 1)$, but relaxing
+$\lambda$ may not be safe.
+
+If we relax $r$, then we get
+
+$$G_\lambda(r \mu_1 + (1 - r) \mu_0 || \mu_0) = O(r^{2 / d_r} \lambda^2 \sigma^{-2}) = O(1).$$
+
+Note that now the constant $C$ depends on $d_r$ as well. Numerical
+experiments seem to suggest that $C$ can increase quite rapidly as $d_r$
+decreases from $1$. $\square$
+
+In the following for consistency we retain $k$ as the number of epochs,
+and use $T := k / r$ to denote the number of compositions / steps /
+minibatches. With Hypothesis 0 we have:
+
+**Hypothesis 3**. Let $\epsilon, c_1, c_2 > 0$,
+$r \le c_1 \sigma^{-1}$,
+$T = {c_2 \over 2 C(c_1, c_2)} \epsilon \sigma^2$. then the DP-SGD with
+subsampling rate $r$, and $T$ steps is $(\epsilon, \delta)$-dp for
+
+$$\delta = \exp(- {1 \over 2} c_2 \sigma^2 \epsilon).$$
+
+In other words, for
+
+$$\sigma \ge \sqrt{2 c_2^{-1}} \epsilon^{- {1 \over 2}} \sqrt{\log \delta^{-1}},$$
+
+we can achieve $(\epsilon, \delta)$-dp.
+
+**Proof**. By Hypothesis 0 and the Moment Composition Theorem
+(Claim 22), for $\lambda = c_2 \sigma^2$, substituting
+$T = {c_2 \over 2 C(c_1, c_2)} \epsilon \sigma^2$, we have
+
+$$\mathbb P(L(p || q) \ge \epsilon) \le \exp(k C(c_1, c_2) - \lambda \epsilon) = \exp\left(- {1 \over 2} c_2 \sigma^2 \epsilon\right).$$
+
+$\square$
+
+**Remark**. Hypothesis 3 is my understanding / version of
+Theorem 1 in \[ACGMMTZ16\], by using the same proof technique. Here I
+quote the original version of theorem with notions and notations altered
+for consistency with this post:
+
+> There exists constants $c_1', c_2' > 0$ so that for any
+> $\epsilon < c_1' r^2 T$, DP-SGD is $(\epsilon, \delta)$-differentially
+> private for any $\delta > 0$ if we choose
+
+$$\sigma \ge c_2' {r \sqrt{T \log (1 / \delta)} \over \epsilon}. \qquad (10)$$
+
+I am however unable to reproduce this version, assuming Hypothesis 0 is
+true, for the following reasons:
+
+1.  In the proof in the paper, we have $\epsilon = c_1' r^2 T$ instead
+    of \"less than\" in the statement of the Theorem. If we change it to
+    $\epsilon < c_1' r^2 T$ then the direction of the inequality becomes
+    opposite to the direction we want to prove:
+    $$\exp(k C(c_1, c_2) - \lambda \epsilon) \ge ...$$
+
+2.  The implicit condition $r = O(\sigma^{-1})$ of Hypothesis 0 whose
+    result is used in the proof of this theorem is not mentioned in the
+    statement of the proof. The implication is that (10) becomes an
+    ill-formed condition as the right hand side also depends on
+    $\sigma$.
+
+Tensorflow implementation 
+-------------------------
+
+The DP-SGD is implemented in [TensorFlow
+Privacy](https://github.com/tensorflow/privacy). In the following I
+discuss the package in the current state (2019-03-11). It is divided
+into two parts: `optimizers` which implements the actual differentially
+private algorithm, and `analysis` which computes the privacy guarantee.
+
+The `analysis` parts implements a privacy ledger that \"keeps a record
+of all queries executed over a given dataset for the purpose of
+computing privacy guarantees\". On the other hand, all the computation
+is done in `rdp_accountant.py`
+([link](https://github.com/tensorflow/privacy/blob/7e2d796bdee9b60dce21a82a397eefda35b0ac10/privacy/analysis/rdp_accountant.py).
+At this moment, `rdp_accountant.py` only implements the computation of
+the privacy guarantees for DP-SGD with Gaussian mechanism. In the
+following I will briefly explain the code in this file.
+
+Some notational correspondences: their `alpha` is our $\lambda$, their
+`q` is our $r$, their `A_alpha` (in the comments) is our
+$\kappa_{r N(1, \sigma^2) + (1 - r) N(0, \sigma^2)} (\lambda - 1)$, at
+least when $\lambda$ is an integer.
+
+-   The function `_compute_log_a` presumably computes the cumulants
+    $\kappa_{r N(1, \sigma^2) + (1 - r) N(0, \sigma^2), N(0, \sigma^2)}(\lambda - 1)$.
+    It calls `_compute_log_a_int` or `_compute_log_a_frac` depending on
+    whether $\lambda$ is an integer.
+-   The function `_compute_log_a_int` computes the cumulant using (9.5).
+-   When $\lambda$ is not an integer, we can\'t use (9.5). I have yet to
+    decode how `_compute_log_a_frac` computes the cumulant (or an upper
+    bound of it) in this case
+-   The function `_compute_delta` computes $\delta$s for a list of
+    $\lambda$s and $\kappa$s using Item 1 of Claim 3 and return the
+    smallest one, and the function `_compute_epsilon` computes epsilon
+    uses Item 3 in the same way.
+
+In `optimizers`, among other things, the DP-SGD with Gaussian mechanism
+is implemented in `dp_optimizer.py` and `gaussian_query.py`. See the
+definition of `DPGradientDescentGaussianOptimizer` in `dp_optimizer.py`
+and trace the calls therein.
+
+At this moment, the privacy guarantee computation part and the optimizer
+part are separated, with `rdp_accountant.py` called in
+`compute_dp_sgd_privacy.py` with user-supplied parameters. I think this
+is due to the lack of implementation in `rdp_accountant.py` of any
+non-DPSGD-with-Gaussian privacy guarantee computation. There is already
+[an issue on this](https://github.com/tensorflow/privacy/issues/23), so
+hopefully it won\'t be long before the privacy guarantees can be
+automatically computed given a DP-SGD instance.
+
+Comparison among different methods 
+----------------------------------
+
+So far we have seen three routes to compute the privacy guarantees for
+DP-SGD with the Gaussian mechanism:
+
+1.  Claim 9 (single Gaussian mechanism privacy guarantee) -\> Claim 19
+    (Subsampling theorem) -\> Claim 18 (Advanced Adaptive Composition
+    Theorem)
+2.  Example 1 (RDP for the Gaussian mechanism) -\> Claim 22 (Moment
+    Composition Theorem) -\> Example 3 (Moment composition applied to
+    the Gaussian mechanism)
+3.  Hypothesis 0 (RDP for Gaussian mechanism with specific magnitudes
+    for subsampling rate) -\> Hypothesis 3 (Moment Composition Theorem
+    and translation to conventional DP)
+
+Which one is the best?
+
+To make fair comparison, we may use one parameter as the metric and set
+all others to be the same. For example, we can
+
+1.  Given the same $\epsilon$, $r$ (in Route 1 and 3), $k$, $\sigma$,
+    compare the $\delta$s
+2.  Given the same $\epsilon$, $r$ (in Route 1 and 3), $k$, $\delta$,
+    compare the $\sigma$s
+3.  Given the same $\delta$, $r$ (in Route 1 and 3), $k$, $\sigma$,
+    compare the $\epsilon$s.
+
+I find that the first one, where $\delta$ is used as a metric, the best.
+This is because we have the tightest bounds and the cleanest formula
+when comparing the $\delta$. For example, the Azuma and Chernoff bounds
+are both expressed as a bound for $\delta$. On the other hand, the
+inversion of these bounds either requires a cost in the tightness (Claim
+9, bounds on $\sigma$) or in the complexity of the formula (Claim 16
+Advanced Adaptive Composition Theorem, bounds on $\epsilon$).
+
+So if we use $\sigma$ or $\epsilon$ as a metric, either we get a less
+fair comparison, or have to use a much more complicated formula as the
+bounds.
+
+Let us first compare Route 1 and Route 2 without specialising to the
+Gaussian mechanism.
+
+**Disclaimer**. What follows is my original research and
+has not been reviewed by anyone.
+
+Suppose each mechanism $N_i$ satisfies
+$(\epsilon', \delta(\epsilon'))$-dp. Let
+$\tilde \epsilon := \log (1 + r (e^{\epsilon'} - 1))$, then we have the
+subsampled mechanism $M_i(x) = N_i(x_\gamma)$ is
+$(\tilde \epsilon, r \tilde \delta(\tilde \epsilon))$-dp, where
+
+$$\tilde \delta(\tilde \epsilon) = \delta(\log (r^{-1} (\exp(\tilde \epsilon) - 1) + 1))$$
+
+Using the Azuma bound in the proof of Advanced Adaptive Composition
+Theorem (6.99):
+
+$$\mathbb P(L(p^k || q^k) \ge \epsilon) \le \exp(- {(\epsilon - r^{-1} k a(\tilde\epsilon))^2 \over 2 r^{-1} k (\tilde\epsilon + a(\tilde\epsilon))^2}).$$
+
+So we have the final bound for Route 1:
+
+$$\delta_1(\epsilon) = \min_{\tilde \epsilon: \epsilon > r^{-1} k a(\tilde \epsilon)} \exp(- {(\epsilon - r^{-1} k a(\tilde\epsilon))^2 \over 2 r^{-1} k (\tilde\epsilon + a(\tilde\epsilon))^2}) + k \tilde \delta(\tilde \epsilon).$$
+
+As for Route 2, since we do not gain anything from subsampling in RDP,
+we do not subsample at all.
+
+By Claim 23, we have the bound for Route 2:
+
+$$\delta_2(\epsilon) = \exp(- k \kappa^* (\epsilon / k)).$$
+
+On one hand, one can compare $\delta_1$ and $\delta_2$ with numerical
+experiments. On the other hand, if we further specify
+$\delta(\epsilon')$ in Route 1 as the Chernoff bound for the cumulants
+of divergence variable, i.e.
+
+$$\delta(\epsilon') = \exp(- \kappa^* (\epsilon')),$$
+
+we have
+
+$$\delta_1 (\epsilon) = \min_{\tilde \epsilon: a(\tilde \epsilon) < r k^{-1} \epsilon} \exp(- {(\epsilon - r^{-1} k a(\tilde\epsilon))^2 \over 2 r^{-1} k (\tilde\epsilon + a(\tilde\epsilon))^2}) + k \exp(- \kappa^* (b(\tilde\epsilon))),$$
+
+where
+
+$$b(\tilde \epsilon) := \log (r^{-1} (\exp(\tilde \epsilon) - 1) + 1) \le r^{-1} \tilde\epsilon.$$
+
+We note that since
+$a(\tilde \epsilon) = \tilde\epsilon(e^{\tilde \epsilon} - 1) 1_{\tilde\epsilon < \log 2} + \tilde\epsilon 1_{\tilde\epsilon \ge \log 2}$,
+we may compare the two cases separately.
+
+Note that we have $\kappa^*$ is a monotonously increasing function,
+therefore
+
+$$\kappa^* (b(\tilde\epsilon)) \le \kappa^*(r^{-1} \tilde\epsilon).$$
+
+So for $\tilde \epsilon \ge \log 2$, we have
+
+$$k \exp(- \kappa^*(b(\tilde\epsilon))) \ge k \exp(- \kappa^*(r^{-1} \tilde \epsilon)) \ge k \exp(- \kappa^*(k^{-1} \epsilon)) \ge \delta_2(\epsilon).$$
+
+For $\tilde\epsilon < \log 2$, it is harder to compare, as now
+
+$$k \exp(- \kappa^*(b(\tilde\epsilon))) \ge k \exp(- \kappa^*(\epsilon / \sqrt{r k})).$$
+
+It is tempting to believe that this should also be greater than
+$\delta_2(\epsilon)$. But I can not say for sure. At least in the
+special case of Gaussian, we have
+
+$$k \exp(- \kappa^*(\epsilon / \sqrt{r k})) = k \exp(- (\sigma \sqrt{\epsilon / k r} - (2 \sigma)^{-1})^2) \ge \exp(- k ({\sigma \epsilon \over k} - (2 \sigma)^{-1})^2) = \delta_2(\epsilon)$$
+
+when $\epsilon$ is sufficiently small. However we still need to consider
+the case where $\epsilon$ is not too small. But overall it seems most
+likely Route 2 is superior than Route 1.
+
+So let us compare Route 2 with Route 3:
+
+Given the condition to obtain the Chernoff bound
+
+$${\sigma \epsilon \over k} > (2 \sigma)^{-1}$$
+
+we have
+
+$$\delta_2(\epsilon) > \exp(- k (\sigma \epsilon / k)^2) = \exp(- \sigma^2 \epsilon^2 / k).$$
+
+For this to achieve the same bound
+
+$$\delta_3(\epsilon) = \exp\left(- {1 \over 2} c_2 \sigma^2 \epsilon\right)$$
+
+we need $k < {2 \epsilon \over c_2}$. This is only possible if $c_2$ is
+small or $\epsilon$ is large, since $k$ is a positive integer.
+
+So taking at face value, Route 3 seems to achieve the best results.
+However, it also has some similar implicit conditions that need to be
+satisfied: First $T$ needs to be at least $1$, meaning
+
+$${c_2 \over C(c_1, c_2)} \epsilon \sigma^2 \ge 1.$$
+
+Second, $k$ needs to be at least $1$ as well, i.e.
+
+$$k = r T \ge {c_1 c_2 \over C(c_1, c_2)} \epsilon \sigma \ge 1.$$
+
+Both conditions rely on the magnitudes of $\epsilon$, $\sigma$, $c_1$,
+$c_2$, and the rate of growth of $C(c_1, c_2)$. The biggest problem in
+this list is the last, because if we know how fast $C$ grows then we\'ll
+have a better idea what are the constraints for the parameters to
+achieve the result in Route 3.
+
+Further questions 
+-----------------
+
+Here is a list of what I think may be interesting topics or potential
+problems to look at, with no guarantee that they are all awesome
+untouched research problems:
+
+1.  Prove Hypothesis 2
+2.  Find a theoretically definitive answer whether the methods in Part 1
+    or Part 2 yield better privacy guarantees.
+3.  Study the non-Gaussian cases, general or specific. Let $p$ be some
+    probability density, what is the tail bound of
+    $L(p(y) || p(y + \alpha))$ for $|\alpha| \le 1$? Can you find
+    anything better than Gaussian? For a start, perhaps the nice tables
+    of Rényi divergence in Gil-Alajaji-Linder 2013 may be useful?
+4.  Find out how useful Hypothesis 0 is. Perhaps start with computing
+    the constant $C$ nemerically.
+5.  Help with [the aforementioned
+    issue](https://github.com/tensorflow/privacy/issues/23) in the
+    Tensorflow privacy package.
+
+References 
+----------
+
+-   Abadi, Martín, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya
+    Mironov, Kunal Talwar, and Li Zhang. "Deep Learning with
+    Differential Privacy." Proceedings of the 2016 ACM SIGSAC Conference
+    on Computer and Communications Security - CCS'16, 2016, 308--18.
+    <https://doi.org/10.1145/2976749.2978318>.
+-   Erven, Tim van, and Peter Harremoës. "R\\'enyi Divergence and
+    Kullback-Leibler Divergence." IEEE Transactions on Information
+    Theory 60, no. 7 (July 2014): 3797--3820.
+    <https://doi.org/10.1109/TIT.2014.2320500>.
+-   Gil, M., F. Alajaji, and T. Linder. "Rényi Divergence Measures for
+    Commonly Used Univariate Continuous Distributions." Information
+    Sciences 249 (November 2013): 124--31.
+    <https://doi.org/10.1016/j.ins.2013.06.018>.
+-   Mironov, Ilya. "Renyi Differential Privacy." 2017 IEEE 30th Computer
+    Security Foundations Symposium (CSF), August 2017, 263--75.
+    <https://doi.org/10.1109/CSF.2017.11>.