diff options
| -rw-r--r-- | posts/2019-03-13-a-tail-of-two-densities.md | 1224 |
1 files changed, 1224 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 new file mode 100644 index 0000000..1dbc573 --- /dev/null +++ b/posts/2019-03-13-a-tail-of-two-densities.md @@ -0,0 +1,1224 @@ +--- +date: 2019-02-13 +title: A Tail of Two Densities +template: post +comments: true +--- + +This is Part 1 of a two-part post where I give an introduction to +differential privacy, a study of tail bounds of the divergence between +probability measures, with the end goal of applying it to stochastic +gradient descent. + +I start with the definition of $\epsilon$-differential privacy +(corresponding to max divergence), followed by +$(\epsilon, \delta)$-differential privacy (a.k.a. approximate +differential privacy, corresponding to the $\delta$-approximate max +divergence). I show the $\epsilon$-dp for Laplace mechanism and, using +some tail bounds, the approximate dp for the Gaussian mechanism. + +Then I continue to state and prove the composition theorems for +approximate differential privacy, as well as the subsampling theorem +(a.k.a. amplification theorem). + +In Part 2, I discuss the Rényi differential privacy, corresponding to +the Rényi divergence. Like in Part 1, I prove a composition theorem and +a subsampling theorem. + +I also attempt to reproduce a seemingly better moment bound for the +Gaussian mechanism with subsampling, with one intermediate step which I +am not able to prove. + +Finally I explain the Tensorflow implementation of differential privacy, +and using the results from both Part 1 and Part 2 to obtain some privacy +guarantees for the differentially private stochastic gradient descent +algorithm (DP-SGD). I also compare these privacy guarantees. + +**Acknowledgement**. I would like to thank +[Stockholm AI](https://stockholm.ai) for introducing me to the subject +of differential privacy. Thanks to (in chronological order) Reynaldo +Boulogne, Martin Abedi, Ilya Mironov, Kurt Johansson, Mark Bun, Salil +Vadhan, Jonathan Ullman, Yuanyuan Xu and Yiting Li for communication and +discussions. The research was done while working at KTH Department of +Mathematics. + +The gist of differential privacy +-------------------------------- + +If you only have one minute, here is what differential privacy is about: + +Let $p$ and $q$ be two probability densities, we define the *divergence +variable* of $(p, q)$ to be + +$$L(p || q) := \log {p(\xi) \over q(\xi)}$$ + +where $\xi$ is a random variable distributed according to $p$. + +Roughly speaking, differential privacy is the study of the tail bound of +$L(p || q)$ and of $L(q || p)$: for certain $p$s and $q$s, and for +$\epsilon > 0$, find $\delta(\epsilon)$ such that + +$$\mathbb P(L(p || q) > \epsilon) < \delta(\epsilon) > \mathbb P(L(q || p) > \epsilon),$$ + +where $p$ and $q$ are the laws of the outputs of a randomised functions +on two very similar inputs. + +In application, the inputs are databases and the randomised functions +are queries with an added noise, and the tail bound gives privacy +guarantee. When it comes to gradient descent, the input is the training +dataset, and the query updates the parameters, and privacy is achieved +by adding noise to the gradients. + +Now if you have an hour\... + +$\epsilon$-dp +------------- + +**Definition (Mechanisms)**. Let $X$ be a +space with a metric $d: X \times X \to \mathbb N$. A *mechanism* $M$ is +a function that takes $x \in X$ as input and outputs a random variable +on $Y$. + +In this post, $X = Z^m$ is the space of datasets of $m$ rows for some +integer $m$, where each item resides in $Z$. In this case the distance +$d(x, x') := \#\{i: x_i \neq x'_i\}$ is the number of rows that differ +between $x$ and $x'$. + +Normally we have a query $f: X \to Y$, and construct the mechanism $M$ +from $f$ by adding a noise: + +$$M(x) := f(x) + \text{noise}.$$ + +Later, we will also consider mechanisms constructed by composition of +other mechanisms. + +In this post $Y = \mathbb R^d$ for some $d$. + +**Definition (Sensitivity)**. Let +$f: X \to \mathbb R^d$ be a function. The *sensitivity* $S_f$ of $f$ is +defined as + +$$S_f := \sup_{x, x' \in X: d(x, x') = 1} \|f(x) - f(x')\|_2,$$ + +where $\|y\|_2 = \sqrt{y_1^2 + ... + y_d^2}$ is the $\ell^2$-norm. + +**Definition (Differential +Privacy)**. A mechanism $M$ is called $\epsilon$*-differential privacy* +($\epsilon$-dp) if it satisfies the following condition: for all +$x, x' \in X$ with $d(x, x') = 1$, and for all measureable set +$S \subset \mathbb R^n$, + +$$\mathbb P(M(x) \in S) \le e^\epsilon P(M(x') \in S). \qquad (1)$$ + +An example of $\epsilon$-dp mechanism is the Laplace mechanism. + +**Definition**. The Laplace distribution over $\mathbb R$ +with parameter $b > 0$ has probability density function + +$$f_{\text{Lap}(b)}(x) = {1 \over 2 b} e^{- {|x| \over b}}.$$ + +**Definition**. Let $d = 1$. The Laplace mechanism is +defined by + +$$M(x) = f(x) + \text{Lap}(b).$$ + +**Claim**. The Laplace mechanism with + +$$b \ge \epsilon^{-1} S_f \qquad (1.5)$$ + +is $\epsilon$-dp. + +**Proof**. Quite straightforward. Let $p$ and $q$ be the laws +of $M(x)$ and $M(x')$ respectively. + +$${p (y) \over q (y)} = {f_{\text{Lap}(b)} (y - f(x)) \over f_{\text{Lap}(b)} (y - f(x'))} = \exp(b^{-1} (|y - f(x')| - |y - f(x)|))$$ + +Using triangular inequality $|A| - |B| \le |A - B|$ on the right hand +side, we have + +$${p (y) \over q (y)} \le \exp(b^{-1} (|f(x) - f(x')|)) \le \exp(\epsilon)$$ + +where in the last step we use the condition (1.5). $\square$ + +Approximate differential privacy +-------------------------------- + +Unfortunately, $\epsilon$-dp does not apply to the most commonly used +noise, the Gaussian noise. To fix this, we need to relax the definition +a bit. + +**Definition**. A mechanism $M$ is said to be +$(\epsilon, \delta)$*-differentially private* if for all $x, x' \in X$ +with $d(x, x') = 1$ and for all measureable $S \subset \mathbb R^d$ + +$$\mathbb P(M(x) \in S) \le e^\epsilon P(M(x') \in S) + \delta. \qquad (2)$$ + +Immediately we see that the $(\epsilon, \delta)$-dp is meaningful only +if $\delta < 1$. + +### Indistinguishability + +To understand $(\epsilon, \delta)$-dp, it is helpful to study +$(\epsilon, \delta)$-indistinguishability. + +**Definition**. Two probability measures $p$ and $q$ on +the same space are called $(\epsilon, \delta)$*-ind(istinguishable)* if +for all measureable sets $S$: + +$$\begin{aligned} +p(S) \le e^\epsilon q(S) + \delta, \qquad (3) \\ +q(S) \le e^\epsilon p(S) + \delta. \qquad (4) +\end{aligned}$$ + +As before, we also call random variables $\xi$ and $\eta$ to be +$(\epsilon, \delta)$-ind if their laws are $(\epsilon, \delta)$-ind. +When $\delta = 0$, we call it $\epsilon$-ind. + +Immediately we have + +**Claim 0**. $M$ is $(\epsilon, \delta)$-dp (resp. +$\epsilon$-dp) iff $M(x)$ and $M(x')$ are $(\epsilon, \delta)$-ind +(resp. $\epsilon$-ind) for all $x$ and $x'$ with distance $1$. + +**Definition (Divergence +Variable)**. Let $p$ and $q$ be two probability measures. Let $\xi$ be a +random variable distributed according to $p$, we define a random +variable $L(p || q)$ by + +$$L(p || q) := \log {p(\xi) \over q(\xi)},$$ + +and call it the *divergence variable* of $(p, q)$. + +One interesting and readily verifiable fact is + +$$\mathbb E L(p || q) = D(p || q)$$ + +where $D$ is the KL-divergence. + +**Claim 1**. If + +$$\begin{aligned} +\mathbb P(L(p || q) \le \epsilon) &\ge 1 - \delta, \qquad(5) \\ +\mathbb P(L(q || p) \le \epsilon) &\ge 1 - \delta +\end{aligned}$$ + +then $p$ and $q$ are $(\epsilon, \delta)$-ind. + +**Proof**. We verify (3), and (4) can be shown in the same +way. Let $A := \{y \in Y: \log {p(y) \over q(y)} > \epsilon\}$, then by +(5) we have + +$$p(A) < \delta.$$ + +So + +$$p(S) = p(S \cap A) + p(S \setminus A) \le \delta + e^\epsilon q(S \setminus A) \le \delta + e^\epsilon q(S).$$ + +$\square$ + +This Claim translates differential privacy to the tail bound of +divergence variables, and for the rest of this post all dp results are +obtained by estimating this tail bound. + +In the following we discuss the contrary of Claim 1. The discussions are +rather technical, and readers can skip to the next subsection on first +reading. + +The contrary of Claim 1 is not true. + +**Claim 2**. There exists $\epsilon, \delta > 0$, and $p$ +and $q$ that are $(\epsilon, \delta)$-ind, such that + +$$\begin{aligned} +\mathbb P(L(p || q) \le \epsilon) &< 1 - \delta, \\ +\mathbb P(L(q || p) \le \epsilon) &< 1 - \delta +\end{aligned}$$ + +$, and +$p(0) = q(1) = 2 / 5$ and $p(1) = q(0) = 3 / 5$. Then it is not hard to +verify that $p$ and $q$ are $(\log {4 \over 3}, {1 \over 3})$-ind: just +check (3) for all four possible $S \subset Y$ and (4) holds by symmetry. +On the other hand, + +$$\mathbb P(L(p || q) \le \log {4 \over 3}) = \mathbb P(L(q || p) \le \log {4 \over 3}) = {2 \over 5} < {2 \over 3}.$$ + +$\square$ + +A weaker version of the contrary of Claim 1 is true +(Kasiviswanathan-Smith 2015), though: + +**Claim 3**. Let $\alpha > 1$. If $p$ and $q$ are +$(\epsilon, \delta)$-ind, then + +$$\mathbb P(L(p || q) > \alpha \epsilon) < {1 \over 1 - \exp((1 - \alpha) \epsilon)} \delta.$$ + +**Proof**. Define + +$$S = \{y: p(y) > e^{\alpha \epsilon} q(y)\}.$$ + +Then we have + +$$e^{\alpha \epsilon} q(S) < p(S) \le e^\epsilon q(S) + \delta,$$ + +where the first inequality is due to the definition of $S$, and the +second due to the $(\epsilon, \delta)$-ind. Therefore + +$$q(S) \le {\delta \over e^{\alpha \epsilon} - e^\epsilon}.$$ + +Using the $(\epsilon, \delta)$-ind again we have + +$$p(S) \le e^\epsilon q(S) + \delta = {1 \over 1 - e^{(1 - \alpha) \epsilon}} \delta.$$ + +$\square$ + +This can be quite bad if $\epsilon$ is small. + +To prove the composition theorems in the next section, we need a +condition better than that in Claim 1 so that we can go back and forth +between indistinguishability and such condition. In other words, we need +a *characterisation* of indistinguishability. + +Let us take a careful look at the condition in Claim 1 and call it +**C1**: + +**C1**. $\mathbb P(L(p || q) \le \epsilon) \ge 1 - \delta$ and +$\mathbb P(L(q || p) \le \epsilon) \ge 1 - \delta$ + +It is equivalent to + +**C2**. there exist events $A, B \subset Y$ with probabilities +$p(A)$ and $q(B)$ at least $1 - \delta$ such that +$\log p(y) - \log q(y) \le \epsilon$ for all $y \in A$ and +$\log q(y) - \log p(y) \le \epsilon$ for all $y \in B$. + +A similar-looking condition to **C2** is the following: + +**C3**. Let $\Omega$ be the [underlying probability +space](https://en.wikipedia.org/wiki/Probability_space#Definition). +There exist two events $E, F \subset \Omega$ with +$\mathbb P(E), \mathbb P(F) \ge 1 - \delta$, such that +$|\log p_{|E}(y) - \log q_{|F}(y)| \le \epsilon$ for all $y \in Y$. + +Here $p_{|E}$ (resp. $q_{|F}$) is $p$ (resp. $q$) conditioned on event +$E$ (resp. $F$). + +**C2** and +**C3** are in different spaces, and therefore we can not write +$p_{|E}(S)$ as $p(S | E)$ or $q_{|F}(S)$ as $q(S | F)$. In fact, if we +let $E$ and $F$ in **C3** be subsets of $Y$ with +$p(E), q(F) \ge 1 - \delta$ and assume $p$ and $q$ have the same +supports, then **C3** degenerates to a stronger condition than +$ and +$q_F(y) = q(y) 1_{y \in F}$, and so $p_E(y) \le e^\epsilon q_F(y)$ +forces $E \subset F$. We also obtain $F \subset E$ in the same way. This +gives us $E = F$, and **C2** with +$A = B = E = F$. + +As it turns out, **C3** is the condition we need. + +**Claim 4**. Two probability measures $p$ and $q$ are +$(\epsilon, \delta)$-ind if and only if **C3** holds. + +**Proof**(Murtagh-Vadhan 2018). The \"if\" direction is proved +in the same way as Lemma 1. Without loss of generality we may assume +$\mathbb P(E) = \mathbb P(F) \ge 1 - \delta$. To see this, suppose $F$ +has higher probability than $E$, then we can substitute $F$ with a +subset of $F$ that has the same probability as $E$ (with possible +enlargement of the probability space). + +Let $\xi \sim p$ and $\eta \sim q$ be two independent random variables, +then + +$$\begin{aligned} +p(S) &= \mathbb P(\xi \in S | E) \mathbb P(E) + \mathbb P(\xi \in S; E^c) \\ +&\le e^\epsilon \mathbb P(\eta \in S | F) \mathbb P(E) + \delta \\ +&= e^\epsilon \mathbb P(\eta \in S | F) \mathbb P(F) + \delta\\ +&\le e^\epsilon q(S) + \delta. +\end{aligned}$$ + +The \"only-if\" direction is more involved. + +We construct events $E$ and $F$ by constructing functions +$e, f: Y \to [0, \infty)$ satisfying the following conditions: + +1. $0 \le e(y) \le p(y)$ and $0 \le f(y) \le q(y)$ for all $y \in Y$. +2. $|\log e(y) - \log f(y)| \le \epsilon$ for all $y \in Y$. +3. $e(Y), f(Y) \ge 1 - \delta$. +4. $e(Y) = f(Y)$. + +Here for a set $S \subset Y$, $e(S) := \int_S e(y) dy$, and the same +goes for $f(S)$. + +Let $\xi \sim p$ and $\eta \sim q$. Then we define $E$ and $F$ by + +$$\mathbb P(E | \xi = y) = e(y) / p(y) \\ +\mathbb P(F | \eta = y) = f(y) / q(y).$$ + +**Remark inside proof**. This can seem a bit +confusing. Intuitively, we can think of it this way when $Y$ is finite: +Recall a random variable on $Y$ is a function from the probability space +$\Omega$ to $Y$. Let event $G_y \subset \Omega$ be defined as +$G_y = \xi^{-1} (y)$. We cut $G_y$ into the disjoint union of $E_y$ and +$G_y \setminus E_y$ such that $\mathbb P(E_y) = e(y)$. Then +$E = \bigcup_{y \in Y} E_y$. So $e(y)$ can be seen as the \"density\" of +$E$. + +Indeed, given $E$ and $F$ defined this way, we have + +$$p_E(y) = {e(y) \over e(Y)} \le {\exp(\epsilon) f(y) \over e(Y)} = {\exp(\epsilon) f(y) \over f(Y)} = \exp(\epsilon) q_F(y).$$ + +and + +$$\mathbb P(E) = \int \mathbb P(E | \xi = y) p(y) dy = e(Y) \ge 1 - \delta,$$ + +and the same goes for $\mathbb P(F)$. + +What remains is to construct $e(y)$ and $f(y)$ satisfying the four +conditions. + +Like in the proof of Claim 1, let $S, T \subset Y$ be defined as + +$$\begin{aligned} +S := \{y: p(y) > \exp(\epsilon) q(y)\},\\ +T := \{y: q(y) > \exp(\epsilon) p(y)\}. +\end{aligned}$$ + +Let + +$$\begin{aligned} +e(y) &:= \exp(\epsilon) q(y) 1_{y \in S} + p(y) 1_{y \notin S}\\ +f(y) &:= \exp(\epsilon) p(y) 1_{y \in T} + q(y) 1_{y \notin T}. \qquad (6) +\end{aligned}$$ + +By checking them on the three disjoint subsets $S$, $T$, $(S \cup T)^c$, +it is not hard to verify that the $e(y)$ and $f(y)$ constructed this way +satisfy the first two conditions. They also satisfy the third condition: + +$$\begin{aligned} +e(Y) &= 1 - (p(S) - \exp(\epsilon) q(S)) \ge 1 - \delta, \\ +f(Y) &= 1 - (q(T) - \exp(\epsilon) p(T)) \ge 1 - \delta. +\end{aligned}$$ + +If $e(Y) = f(Y)$ then we are done. Otherwise, without loss of +generality, assume $e(Y) < f(Y)$, then all it remains to do is to reduce +the value of $f(y)$ while preserving Condition 1, 2 and 3, until +$f(Y) = e(Y)$. + +As it turns out, this can be achieved by reducing $f(y)$ on the set +$\{y \in Y: q(y) > p(y)\}$. To see this, let us rename the $f(y)$ +defined in (6) $f_+(y)$, and construct $f_-(y)$ by + +$$f_-(y) := p(y) 1_{y \in T} + (q(y) \wedge p(y)) 1_{y \notin T}.$$ + +It is not hard to show that not only $e(y)$ and $f_-(y)$ also satisfy +conditions 1-3, but + +$$e(y) \ge f_-(y), \forall y \in Y,$$ + +and thus $e(Y) \ge f_-(Y)$. Therefore there exists an $f$ that +interpolates between $f_-$ and $f_+$ with $f(Y) = e(Y)$. $\square$ + +To prove the adaptive composition theorem for approximate differential +privacy, we need a similar claim (We use index shorthand +$\xi_{< i} = \xi_{1 : i - 1}$ and similarly for other notations): + +$ be random +variables. Let + +$$\begin{aligned} +p_i(S | y_{1 : i - 1}) := \mathbb P(\xi_i \in S | \xi_{1 : i - 1} = y_{1 : i - 1})\\ +q_i(S | y_{1 : i - 1}) := \mathbb P(\eta_i \in S | \eta_{1 : i - 1} = y_{1 : i - 1}) +\end{aligned}$$ + +be the conditional laws of $\xi_i | \xi_{< i}$ and $\eta_i | \eta_{< i}$ +respectively. Then the following are equivalent: + +1. For any $y_{< i} \in Y^{i - 1}$, $p_i(\cdot | y_{< i})$ and + $q_i(\cdot | y_{< i})$ are $(\epsilon, \delta)$-ind +2. There exists events $E_i, F_i \subset \Omega$ with + $\mathbb P(E_i | \xi_{<i} = y_{<i}) = \mathbb P(F_i | \eta_{<i} = y_{< i}) \ge 1 - \delta$ + for any $y_{< i}$, such that $p_{i | E_i}(\cdot | y_{< i})$ and + $q_{i | E_i} (\cdot | y_{< i})$ are $\epsilon$-ind for any + $y_{< i}$, where + $$\begin{aligned} + p_{i | E_i}(S | y_{1 : i - 1}) := \mathbb P(\xi_i \in S | E_i, \xi_{1 : i - 1} = y_{1 : i - 1})\\ + q_{i | F_i}(S | y_{1 : i - 1}) := \mathbb P(\eta_i \in S | F_i, \eta_{1 : i - 1} = y_{1 : i - 1}) + \end{aligned}$$ + + are $p_i$ and $q_i$ conditioned on $E_i$ and $F_i$ respectively. + +**Proof**. Item 2 =\> Item 1: as in the Proof of Claim 4, + +$$\begin{aligned} +p_i(S | y_{< i}) &= p_{i | E_i} (S | y_{< i}) \mathbb P(E_i | \xi_{< i} = y_{< i}) + p_{i | E_i^c}(S | y_{< i}) \mathbb P(E_i^c | \xi_{< i} = y_{< i}) \\ +&\le p_{i | E_i} (S | y_{< i}) \mathbb P(E_i | \xi_{< i} = y_{< i}) + \delta \\ +&= p_{i | E_i} (S | y_{< i}) \mathbb P(F_i | \xi_{< i} = y_{< i}) + \delta \\ +&\le e^\epsilon q_{i | F_i} (S | y_{< i}) \mathbb P(F_i | \xi_{< i} = y_{< i}) + \delta \\ +&= e^\epsilon q_i (S | y_{< i}) + \delta. +\end{aligned}$$ + +The direction from +$q_i(S | y_{< i}) \le e^\epsilon p_i(S | y_{< i}) + \delta$ can be shown +in the same way. + +Item 1 =\> Item 2: as in the Proof of Claim 4 we construct +$e(y_{1 : i})$ and $f(y_{1 : i})$ as \"densities\" of events $E_i$ and +$F_i$. + +Let + +$$\begin{aligned} +e(y_{1 : i}) &:= e^\epsilon q_i(y_i | y_{< i}) 1_{y_i \in S_i(y_{< i})} + p_i(y_i | y_{< i}) 1_{y_i \notin S_i(y_{< i})}\\ +f(y_{1 : i}) &:= e^\epsilon p_i(y_i | y_{< i}) 1_{y_i \in T_i(y_{< i})} + q_i(y_i | y_{< i}) 1_{y_i \notin T_i(y_{< i})}\\ +\end{aligned}$$ + +where + +$$\begin{aligned} +S_i(y_{< i}) = \{y_i \in Y: p_i(y_i | y_{< i}) > e^\epsilon q_i(y_i | y_{< i})\}\\ +T_i(y_{< i}) = \{y_i \in Y: q_i(y_i | y_{< i}) > e^\epsilon p_i(y_i | y_{< i})\}. +\end{aligned}$$ + +Then $E_i$ and $F_i$ are defined as + +$$\begin{aligned} +\mathbb P(E_i | \xi_{\le i} = y_{\le i}) &= {e(y_{\le i}) \over p_i(y_{\le i})},\\ +\mathbb P(F_i | \xi_{\le i} = y_{\le i}) &= {f(y_{\le i}) \over q_i(y_{\le i})}. +\end{aligned}$$ + +The rest of the proof is almost the same as the proof of Lemma 2. +$\square$ + +### Back to approximate differential privacy + +By Claim 0 and 1 we have + +**Claim 6**. If for all $x, x' \in X$ with distance $1$ + +$$\mathbb P(L(M(x) || M(x')) \le \epsilon) \ge 1 - \delta,$$ + +then $M$ is $(\epsilon, \delta)$-dp. + +Note that in the literature the divergence variable $L(M(x) || M(x'))$ +is also called the *privacy loss*. + +By Claim 0 and Claim 4 we have + +**Claim 7**. $M$ is $(\epsilon, \delta)$-dp if and only if +for every $x, x' \in X$ with distance $1$, there exist events +$E, F \subset \Omega$ with $\mathbb P(E) = \mathbb P(F) \ge 1 - \delta$, +$M(x) | E$ and $M(x') | F$ are $\epsilon$-ind. + +We can further simplify the privacy loss $L(M(x) || M(x'))$, by +observing the translation and scaling invariance of $L(\cdot||\cdot)$: + +$$\begin{aligned} +L(\xi || \eta) &\overset{d}{=} L(\alpha \xi + \beta || \alpha \eta + \beta), \qquad \alpha \neq 0. \qquad (6.1) +\end{aligned}$$ + +With this and the definition + +$$M(x) = f(x) + \zeta$$ + +for some random variable $\zeta$, we have + +$$L(M(x) || M(x')) \overset{d}{=} L(\zeta || \zeta + f(x') - f(x)).$$ + +Without loss of generality, we can consider $f$ with sensitivity $1$, +for + +$$L(f(x) + S_f \zeta || f(x') + S_f \zeta) \overset{d}{=} L(S_f^{-1} f(x) + \zeta || S_f^{-1} f(x') + \zeta)$$ + +so for any noise $\zeta$ that achieves $(\epsilon, \delta)$-dp for a +function with sensitivity $1$, we have the same privacy guarantee by for +an arbitrary function with sensitivity $S_f$ by adding a noise +$S_f \zeta$. + +With Claim 6 we can show that the Gaussian mechanism is approximately +differentially private. But first we need to define it. + +**Definition (Gaussian mechanism)**. +Given a query $f: X \to Y$, the *Gaussian mechanism* $M$ adds a Gaussian +noise to the query: + +$$M(x) = f(x) + N(0, \sigma^2 I).$$ + +Some tail bounds for the Gaussian distribution will be useful. + +**Claim 8 (Gaussian tail bounds)**. +Let $\xi \sim N(0, 1)$ be a standard normal distribution. Then for +$t > 0$ + +$$\mathbb P(\xi > t) < {1 \over \sqrt{2 \pi} t} e^{- {t^2 \over 2}}, \qquad (6.3)$$ + +and + +$$\mathbb P(\xi > t) < e^{- {t^2 \over 2}}. \qquad (6.5)$$ + +**Proof**. Both bounds are well known. The first can be proved +using + +$$\int_t^\infty e^{- {y^2 \over 2}} dy < \int_t^\infty {y \over t} e^{- {y^2 \over 2}} dy.$$ + +The second is shown using Chernoff bound. For any random variable $\xi$, + +$$\mathbb P(\xi > t) < {\mathbb E \exp(\lambda \xi) \over \exp(\lambda t)} = \exp(\kappa_\xi(\lambda) - \lambda t), \qquad (6.7)$$ + +where $\kappa_\xi(\lambda) = \log \mathbb E \exp(\lambda \xi)$ is the +cumulant of $\xi$. Since (6.7) holds for any $\lambda$, we can get the +best bound by minimising $\kappa_\xi(\lambda) - \lambda t$ (a.k.a. the +Legendre transformation). When $\xi$ is standard normal, we get (6.5). +$\square$ + +**Remark**. We will use the Chernoff bound extensively in the +second part of this post when considering Renyi differential privacy. + +**Claim 9**. The Gaussian mechanism on a query $f$ is +$(\epsilon, \delta)$-dp, where + +$$\delta = \exp(- (\epsilon S_f \sigma - (2 S_f \sigma)^{-1})^2 / 2). \qquad (6.8)$$ + +Contrarily, to achieve give $(\epsilon, \delta)$-dp, we may set + +$$\sigma > \left(\epsilon^{-1} \sqrt{2 \log \delta^{-1}} + (2 \epsilon)^{- {1 \over 2}}\right) S_f \qquad (6.81)$$ + +or + +$$\sigma > (\epsilon^{-1} (1 \vee \sqrt{(\log (2 \pi)^{-1} \delta^{-2})_+}) + (2 \epsilon)^{- {1 \over 2}}) S_f \qquad (6.82)$$ + +or + +$$\sigma > \epsilon^{-1} \sqrt{\log e^\epsilon \delta^{-2}} S_f \qquad (6.83)$$ + +or + +$$\sigma > \epsilon^{-1} (\sqrt{1 + \epsilon} \vee \sqrt{(\log e^\epsilon (2 \pi)^{-1} \delta^{-2})_+}) S_f. \qquad (6.84)$$ + +**Proof**. As discussed before we only need to consider the +case where $S_f = 1$. Fix arbitrary $x, x' \in X$ with $d(x, x') = 1$. +Let $\zeta = (\zeta_1, ..., \zeta_d) \sim N(0, I_d)$. + +By Claim 6 it suffices to bound + +$$\mathbb P(L(M(x) || M(x')) > \epsilon)$$ + +We have by the linear invariance of $L$, + +$$L(M(x) || M(x')) = L(f(x) + \sigma \zeta || f(x') + \sigma \zeta) \overset{d}{=} L(\zeta|| \zeta + \Delta / \sigma),$$ + +where $\Delta := f(x') - f(x)$. + +Plugging in the Gaussian density, we have + +$$L(M(x) || M(x')) \overset{d}{=} \sum_i {\Delta_i \over \sigma} \zeta_i + \sum_i {\Delta_i^2 \over 2 \sigma^2} \overset{d}{=} {\|\Delta\|_2 \over \sigma} \xi + {\|\Delta\|_2^2 \over 2 \sigma^2}.$$ + +where $\xi \sim N(0, 1)$. + +Hence + +$$\mathbb P(L(M(x) || M(x')) > \epsilon) = \mathbb P(\zeta > {\sigma \over \|\Delta\|_2} \epsilon - {\|\Delta\|_2 \over 2 \sigma}).$$ + +Since $\|\Delta\|_2 \le S_f = 1$, we have + +$$\mathbb P(L(M(x) || M(x')) > \epsilon) \le \mathbb P(\xi > \sigma \epsilon - (2 \sigma)^{-1}).$$ + +Thus the problem is reduced to the tail bound of a standard normal +distribution, so we can use Claim 8. Note that we implicitly require +$\sigma > (2 \epsilon)^{- 1 / 2}$ here so that +$\sigma \epsilon - (2 \sigma)^{-1} > 0$ and we can use the tail bounds. + +Using (6.3) we have + +$$\mathbb P(L(M(x) || M(x')) > \epsilon) < \exp(- (\epsilon \sigma - (2 \sigma)^{-1})^2 / 2).$$ + +This gives us (6.8). + +To bound the right hand by $\delta$, we require + +$$\epsilon \sigma - {1 \over 2 \sigma} > \sqrt{2 \log \delta^{-1}}. \qquad (6.91)$$ + +Solving this inequality we have + +$$\sigma > {\sqrt{2 \log \delta^{-1}} + \sqrt{2 \log \delta^{-1} + 2 \epsilon} \over 2 \epsilon}.$$ + +Using +$\sqrt{2 \log \delta^{-1} + 2 \epsilon} \le \sqrt{2 \log \delta^{-1}} + \sqrt{2 \epsilon}$, +we can achieve the above inequality by having + +$$\sigma > \epsilon^{-1} \sqrt{2 \log \delta^{-1}} + (2 \epsilon)^{-{1 \over 2}}.$$ + +This gives us (6.81). + +Alternatively, we can use the concavity of $\sqrt{\cdot}$: + +$$(2 \epsilon)^{-1} (\sqrt{2 \log \delta^{-1}} + \sqrt{2 \log \delta^{-1} + 2 \epsilon}) \le \epsilon^{-1} \sqrt{\log e^\epsilon \delta^{-2}},$$ + +which gives us (6.83) + +Back to (6.9), if we use (6.5) instead, we need + +$$\log t + {t^2 \over 2} > \log {(2 \pi)^{- 1 / 2} \delta^{-1}}$$ + +where $t = \epsilon \sigma - (2 \sigma)^{-1}$. This can be satisfied if + +$$\begin{aligned} +t &> 1 \qquad (6.93)\\ +t &> \sqrt{\log (2 \pi)^{-1} \delta^{-2}}. \qquad (6.95) +\end{aligned}$$ + +We can solve both inequalities as before and obtain + +$$\sigma > \epsilon^{-1} (1 \vee \sqrt{(\log (2 \pi)^{-1} \delta^{-2})_+}) + (2 \epsilon)^{- {1 \over 2}},$$ + +or + +$$\sigma > \epsilon^{-1}(\sqrt{1 + \epsilon} \vee \sqrt{(\log e^\epsilon (2 \pi)^{-1} \delta^{-2})_+}).$$ + +This gives us (6.82)(6.84). $\square$ + +When $\epsilon \le \alpha$ is bounded, by (6.83) (6.84) we can require +either + +$$\sigma > \epsilon^{-1} (\sqrt{\log e^\alpha \delta^{-2}}) S_f$$ + +or + +$$\sigma > \epsilon^{-1} (\sqrt{1 + \alpha} \vee \sqrt{(\log (2 \pi)^{-1} e^\alpha \delta^{-2})_+}).$$ + +The second bound is similar to and slightly better than the one in +Theorem A.1 of Dwork-Roth 2013, where $\alpha = 1$: + +$$\sigma > \epsilon^{-1} \left({3 \over 2} \vee \sqrt{(2 \log {5 \over 4} \delta^{-1})_+}\right) S_f.$$ + +Note that the lower bound of ${3 \over 2}$ is implicitly required in the +proof of Theorem A.1. + +Composition theorems +-------------------- + +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 +the privacy when composing several mechanisms, combinatorially or +sequentially. Let us first define the combinatorial case: + +**Definition (Independent +composition)**. Let $M_1, ..., M_k$ be $k$ mechanisms with independent +noises. The mechanism $M = (M_1, ..., M_k)$ is called the *independent +composition* of $M_{1 : k}$. + +To define the adaptive composition, let us motivate it with an example +of gradient descent. Consider a neural network $h_\theta(x)$, where +$\theta$ is the parameter and $x$ the input, gradient descent updates +its parameter $\theta$ at each time $t$: + +$$\theta_{t} = \theta_{t - 1} - \alpha m^{-1} \sum_{i = 1 : m} \nabla_\theta h_\theta(x_i) |_{\theta = \theta_{t - 1}}.$$ + +We may add privacy by adding noise $\zeta_t$ at each step: + +$$\theta_{t} = \theta_{t - 1} - \alpha m^{-1} \sum_{i = 1 : m} \nabla_\theta h_\theta(x_i) |_{\theta = \theta_{t - 1}} + \zeta_t. \qquad (6.97)$$ + +Viewed as a sequence of mechanism, we have that at each time $t$, the +mechanism $M_t$ takes input $x$, and outputs $\theta_t$. But $M_t$ also +depends on the output of the previous mechanism $M_{t - 1}$. To this +end, we define the adaptive composition. + +**Definition (Adaptive +composition)**. Let $({M_i(y_{1 : i - 1})})_{i = 1 : k}$ be $k$ +mechanisms with independent noises, where $M_1$ has no parameter, $M_2$ +has one parameter in $Y$, $M_3$ has two parameters in $Y$ and so on. For +$x \in X$, define $\xi_i$ recursively by + +$$\begin{aligned} +\xi_1 &:= M_1(x)\\ +\xi_i &:= M_i(\xi_1, \xi_2, ..., \xi_{i - 1}) (x). +\end{aligned}$$ + +The *adaptive composition* of $M_{1 : k}$ is defined by +$M(x) := (\xi_1, \xi_2, ..., \xi_k)$. + +The definition of adaptive composition may look a bit complicated, but +the point is to describe $k$ mechanisms such that for each $i$, the +output of the first, second, \..., $i - 1$th mechanisms determine the +$i$th mechanism, like in the case of gradient descent. + +In Dwork-Rothblum-Vadhan 2010 (see also Dwork-Roth 2013) the adaptive +composition is defined in a more general way, but the definition is +based on the same principle, and proofs in this post on adaptive +compositions carry over. + +It is not hard to see that the adaptive composition degenerates to +independent composition when each $M_i(y_{1 : i})$ evaluates to the same +mechanism regardless of $y_{1 : i}$, in which case the $\xi_i$s are +independent. + +In the following when discussing adaptive compositions we sometimes omit +the parameters for convenience without risk of ambiguity, and write +$M_i(y_{1 : i})$ as $M_i$, but keep in mind of the dependence on the +parameters. + +It is time to state and prove the composition theorems. In this section +we consider $2 \times 2 \times 2 = 8$ of them, i.e. theorems of three +dimensions, where there are two choices in each dimension: + +1. Composition of $\epsilon$-dp or more generally + $(\epsilon, \delta)$-dp mechanisms +2. Composition of independent or more generally adaptive mechanisms +3. Basic or advanced compositions + +Note that in the first two dimensions the second choice is more general +than the first. + +The relation between proofs of these composition theorems is as follows: + +1. Claim 10 - Basic composition theorem for $(\epsilon, \delta)$-dp + with adaptive mechanisms: by a direct proof with an induction + argument +2. Claim 14 - Advanced composition theorem for $\epsilon$-dp with + independent mechanisms: by factorising privacy loss and using + Hoeffding\'s Inequality +3. Claim 16 - Advanced composition theorem for $\epsilon$-dp with + adaptive mechanisms: by factorising privacy loss and using Azuma\'s + Inequality +4. Claims 17 and 18 - Advanced composition theorem for + $(\epsilon, \delta)$-dp with independent / adaptive mechanisms: by + using characterisations of $(\epsilon, \delta)$-dp in Claims 4 and 5 + as an approximation of $\epsilon$-dp and then using Proofs in Item 2 + or 3. + +**Claim 10 (Basic composition +theorem).** Let $M_{1 : k}$ be $k$ mechanisms with independent noises +such that for each $i$ and $y_{1 : i - 1}$, $M_i(y_{1 : i - 1})$ is +$(\epsilon_i, \delta_i)$-dp. Then the adpative composition of +$M_{1 : k}$ is $(\sum_i \epsilon_i, \sum_i \delta_i)$-dp. + +**Proof +(Dwork-Lei 2009, see also Dwork-Roth 2013 Appendix B.1)**. Let $x$ and +$x'$ be neighbouring points in $X$. Let $M$ be the adaptive composition +of $M_{1 : k}$. Define + +$$\xi_{1 : k} := M(x), \qquad \eta_{1 : k} := M(x').$$ + +Let $p^i$ and $q^i$ be the laws of $(\xi_{1 : i})$ and $(\eta_{1 : i})$ +respectively. + +Let $S_1, ..., S_k \subset Y$ and $T_i := \prod_{j = 1 : i} S_j$. We use +two tricks. + +1. Since $\xi_i | \xi_{< i} = y_{< i}$ and + $\eta_i | \eta_{< i} = y_{< i}$ are $(\epsilon_i, \delta_i)$-ind, + and a probability is no greater than $1$, + $$\begin{aligned} + \mathbb P(\xi_i \in S_i | \xi_{< i} = y_{< i}) &\le (e^{\epsilon_i} \mathbb P(\eta_i \in S_i | \eta_{< i} = y_{< i}) + \delta_i) \wedge 1 \\ + &\le (e^{\epsilon_i} \mathbb P(\eta_i \in S_i | \eta_{< i} = y_{< i}) + \delta_i) \wedge (1 + \delta_i) \\ + &= (e^{\epsilon_i} \mathbb P(\eta_i \in S_i | \eta_{< i} = y_{< i}) \wedge 1) + \delta_i + \end{aligned}$$ + +2. Given $p$ and $q$ that are $(\epsilon, \delta)$-ind, define + $$\mu(x) = (p(x) - e^\epsilon q(x))_+.$$ + + We have + $$\mu(S) \le \delta, \forall S$$ + + In the following we define + $\mu^{i - 1} = (p^{i - 1} - e^\epsilon q^{i - 1})_+$ for the same + purpose. + +We use an inductive argument to prove the theorem: + +$$\begin{aligned} +\mathbb P(\xi_{\le i} \in T_i) &= \int_{T_{i - 1}} \mathbb P(\xi_i \in S_i | \xi_{< i} = y_{< i}) p^{i - 1} (y_{< i}) dy_{< i} \\ +&\le \int_{T_{i - 1}} (e^{\epsilon_i} \mathbb P(\eta_i \in S_i | \eta_{< i} = y_{< i}) \wedge 1) p^{i - 1}(y_{< i}) dy_{< i} + \delta_i\\ +&\le \int_{T_{i - 1}} (e^{\epsilon_i} \mathbb P(\eta_i \in S_i | \eta_{< i} = y_{< i}) \wedge 1) (e^{\epsilon_1 + ... + \epsilon_{i - 1}} q^{i - 1}(y_{< i}) + \mu^{i - 1} (y_{< i})) dy_{< i} + \delta_i\\ +&\le \int_{T_{i - 1}} e^{\epsilon_i} \mathbb P(\eta_i \in S_i | \eta_{< i} = y_{< i}) e^{\epsilon_1 + ... + \epsilon_{i - 1}} q^{i - 1}(y_{< i}) dy_{< i} + \mu_{i - 1}(T_{i - 1}) + \delta_i\\ +&\le e^{\epsilon_1 + ... + \epsilon_i} \mathbb P(\eta_{\le i} \in T_i) + \delta_1 + ... + \delta_{i - 1} + \delta_i.\\ +\end{aligned}$$ + +In the second line we use Trick 1; in the third line we use the +induction assumption; in the fourth line we multiply the first term in +the first braket with first term in the second braket, and the second +term (i.e. $1$) in the first braket with the second term in the second +braket (i.e. the $\mu$ term); in the last line we use Trick 2. + +The base case $i = 1$ is true since $M_1$ is +$(\epsilon_1, \delta_1)$-dp. $\square$ + +To prove the advanced composition theorem, we start with some lemmas. + +**Claim 11**. If $p$ and $q$ are $\epsilon$-ind, then + +$$D(p || q) + D(q || p) \le \epsilon(e^\epsilon - 1).$$ + +**Proof**. Since $p$ and $q$ are $\epsilon$-ind, we have +$|\log p(x) - \log q(x)| \le \epsilon$ for all $x$. Let +$S := \{x: p(x) > q(x)\}$. Then we have on + +$$\begin{aligned} +D(p || q) + D(q || p) &= \int (p(x) - q(x)) (\log p(x) - \log q(x)) dx\\ +&= \int_S (p(x) - q(x)) (\log p(x) - \log q(x)) dx + \int_{S^c} (q(x) - p(x)) (\log q(x) - \log p(x)) dx\\ +&\le \epsilon(\int_S p(x) - q(x) dx + \int_{S^c} q(x) - p(x) dx) +\end{aligned}$$ + +Since on $S$ we have $q(x) \le p(x) \le e^\epsilon q(x)$, and on $S^c$ +we have $p(x) \le q(x) \le e^\epsilon p(x)$, we obtain + +$$D(p || q) + D(q || p) \le \epsilon \int_S (1 - e^{-\epsilon}) p(x) dx + \epsilon \int_{S^c} (e^{\epsilon} - 1) p(x) dx \le \epsilon (e^{\epsilon} - 1),$$ + +where in the last step we use $e^\epsilon - 1 \ge 1 - e^{- \epsilon}$ +and $p(S) + p(S^c) = 1$. $\square$ + +**Claim 12**. If $p$ and $q$ are $\epsilon$-ind, then + +$$D(p || q) \le a(\epsilon) \ge D(q || p),$$ + +where + +$$a(\epsilon) = \epsilon (e^\epsilon - 1) 1_{\epsilon \le \log 2} + \epsilon 1_{\epsilon > \log 2} \le (\log 2)^{-1} \epsilon^2 1_{\epsilon \le \log 2} + \epsilon 1_{\epsilon > \log 2}. \qquad (6.98)$$ + +**Proof**. Since $p$ and $q$ are $\epsilon$-ind, we have + +$$D(p || q) = \mathbb E_{\xi \sim p} \log {p(\xi) \over q(\xi)} \le \max_y {\log p(y) \over \log q(y)} \le \epsilon.$$ + +Comparing the quantity in Claim 11 ($\epsilon(e^\epsilon - 1)$) with the +quantity above ($\epsilon$), we arrive at the conclusion. $\square$ + +**Claim 13 (Hoeffding\'s +Inequality)**. Let $L_i$ be independent random variables with +$|L_i| \le b$, and let $L = L_1 + ... + L_k$, then for $t > 0$, + +$$\mathbb P(L - \mathbb E L \ge t) \le \exp(- {t^2 \over 2 k b^2}).$$ + +**Claim 14 +(Advanced Independent Composition Theorem)** ($\delta = 0$). Fix +$0 < \beta < 1$. Let $M_1, ..., M_k$ be $\epsilon$-dp, then the +independent composition $M$ of $M_{1 : k}$ is +$(k a(\epsilon) + \sqrt{2 k \log \beta^{-1}} \epsilon, \beta)$-dp. + +**Remark**. By (6.98) we know that +$k a(\epsilon) + \sqrt{2 k \log \beta^{-1}} \epsilon = \sqrt{2 k \log \beta^{-1}} \epsilon + k O(\epsilon^2)$ +when $\epsilon$ is sufficiently small. + +**Proof**. Let $p_i$, $q_i$, $p$ and $q$ be the laws of +$M_i(x)$, $M_i(x')$, $M(x)$ and $M(x')$ respectively. + +$$\mathbb E L_i = D(p_i || q_i) \le a(\epsilon),$$ + +where $L_i := L(p_i || q_i)$. Due to $\epsilon$-ind also have + +$$|L_i| \le \epsilon.$$ + +Therefore, by Hoeffding\'s Inequality, + +$$\mathbb P(L - k a(\epsilon) \ge t) \le \mathbb P(L - \mathbb E L \ge t) \le \exp(- t^2 / 2 k \epsilon^2),$$ + +where $L := \sum_i L_i = L(p || q)$. + +Plugging in $t = \sqrt{2 k \epsilon^2 \log \beta^{-1}}$, we have + +$$\mathbb P(L(p || q) \le k a(\epsilon) + \sqrt{2 k \epsilon^2 \log \beta^{-1}}) \ge 1 - \beta.$$ + +Similarly we also have + +$$\mathbb P(L(q || p) \le k a(\epsilon) + \sqrt{2 k \epsilon^2 \log \beta^{-1}}) \ge 1 - \beta.$$ + +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 + +$$\mathbb P(X_k - X_0 \ge t) \le \exp(- {t^2 \over 2 k b^2}).$$ + +Azuma\'s Inequality implies a slightly weaker version of Hoeffding\'s +Inequality. To see this, let $L_{1 : k}$ be independent variables with +$|L_i| \le b$. Let $X_i = \sum_{j = 1 : i} L_j - \mathbb E L_j$. Then +$X_{0 : k}$ is a martingale, and + +$$| X_i - X_{i - 1} | = | L_i - \mathbb E L_i | \le 2 b,$$ + +since $\|L_i\|_1 \le \|L_i\|_\infty$. Hence by Azuma\'s Inequality, + +$$\mathbb P(L - \mathbb E L \ge t) \le \exp(- {t^2 \over 8 k b^2}).$$ + +Of course here we have made no assumption on $\mathbb E L_i$. If instead +we have some bound for the expectation, say $|\mathbb E L_i| \le a$, +then by the same derivation we have + +$$\mathbb P(L - \mathbb E L \ge t) \le \exp(- {t^2 \over 2 k (a + b)^2}).$$ + +It is not hard to see what Azuma is to Hoeffding is like adaptive +composition to independent composition. Indeed, we can use Azuma\'s +Inequality to prove the Advanced Adaptive Composition Theorem for +$\delta = 0$. + +**Claim 16 +(Advanced Adaptive Composition Theorem)** ($\delta = 0$). Let +$\beta > 0$. Let $M_{1 : k}$ be $k$ mechanisms with independent noises +such that for each $i$ and $y_{1 : i}$, $M_i(y_{1 : i})$ is +$(\epsilon, 0)$-dp. Then the adpative composition of $M_{1 : k}$ is +$(k a(\epsilon) + \sqrt{2 k \log \beta^{-1}} (\epsilon + a(\epsilon)), \beta)$-dp. + + M(x)$ +and $\eta_{1 : k} \overset{d}{=} M(x')$, where $M$ is the adaptive +composition of $M_{1 : k}$. Let $p_i$ (resp. $q_i$) be the law of +$\xi_i | \xi_{< i}$ (resp. $\eta_i | \eta_{< i}$). Let $p^i$ (resp. +$q^i$) be the law of $\xi_{\le i}$ (resp. $\eta_{\le i}$). We want to +construct supermartingale $X$. To this end, let + +$$X_i = \log {p^i(\xi_{\le i}) \over q^i(\xi_{\le i})} - i a(\epsilon) $$ + +We show that $(X_i)$ is a supermartingale: + +$$\begin{aligned} +\mathbb E(X_i - X_{i - 1} | X_{i - 1}) &= \mathbb E \left(\log {p_i (\xi_i | \xi_{< i}) \over q_i (\xi_i | \xi_{< i})} - a(\epsilon) | \log {p^{i - 1} (\xi_{< i}) \over q^{i - 1} (\xi_{< i})}\right) \\ +&= \mathbb E \left( \mathbb E \left(\log {p_i (\xi_i | \xi_{< i}) \over q_i (\xi_i | \xi_{< i})} | \xi_{< i}\right) | \log {p^{i - 1} (\xi_{< i}) \over q^{i - 1} (\xi_{< i})}\right) - a(\epsilon) \\ +&= \mathbb E \left( D(p_i (\cdot | \xi_{< i}) || q_i (\cdot | \xi_{< i})) | \log {p^{i - 1} (\xi_{< i}) \over q^{i - 1} (\xi_{< i})}\right) - a(\epsilon) \\ +&\le 0, +\end{aligned}$$ + +since by Claim 12 +$D(p_i(\cdot | y_{< i}) || q_i(\cdot | y_{< i})) \le a(\epsilon)$ for +all $y_{< i}$. + +Since + +$$| X_i - X_{i - 1} | = | \log {p_i(\xi_i | \xi_{< i}) \over q_i(\xi_i | \xi_{< i})} - a(\epsilon) | \le \epsilon + a(\epsilon),$$ + +by Azuma\'s Inequality, + +$$\prob(\log {p^k(\xi_{1 : k}) \over q^k(\xi_{1 : k})} \ge k a(\epsilon) + t) \le \exp(- {t^2 \over 2 k (\epsilon + a(\epsilon))^2}). \qquad(6.99)$$ + +Let $t = \sqrt{2 k \log \beta^{-1}} (\epsilon + a(\epsilon))$ we are +done. $\square$ + +**Claim 17 +(Advanced Independent Composition Theorem)**. Fix $0 < \beta < 1$. Let +$M_1, ..., M_k$ be $(\epsilon, \delta)$-dp, then the independent +composition $M$ of $M_{1 : k}$ is +$(k a(\epsilon) + \sqrt{2 k \log \beta^{-1}} \epsilon, k \delta + \beta)$-dp. + +$ and +$F_{1 : k}$ such that + +1. The laws $p_{i | E_i}$ and $q_{i | F_i}$ are $\epsilon$-ind. +2. $\mathbb P(E_i), \mathbb P(F_i) \ge 1 - \delta$. + +Let $E := \bigcap E_i$ and $F := \bigcap F_i$, then they both have +probability at least $1 - k \delta$, and $p_{i | E}$ and $q_{i | F}$ are +$\epsilon$-ind. + +By Claim 14, $p_{|E}$ and $q_{|F}$ are +$(\epsilon' := k a(\epsilon) + \sqrt{2 k \epsilon^2 \log \beta^{-1}}, \beta)$-ind. +Let us shrink the bigger event between $E$ and $F$ so that they have +equal probabilities. Then + +$$\begin{aligned} +p (S) &\le p_{|E}(S) \mathbb P(E) + \mathbb P(E^c) \\ +&\le (e^{\epsilon'} q_{|F}(S) + \beta) \mathbb P(F) + k \delta\\ +&\le e^{\epsilon'} q(S) + \beta + k \delta. +\end{aligned}$$ + +$\square$ + +**Claim 18 +(Advanced Adaptive Composition Theorem)**. Fix $0 < \beta < 1$. Let +$M_{1 : k}$ be $k$ mechanisms with independent noises such that for each +$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. + +$ and +$F_{1 : k}$ such that + +1. The laws $p_{i | E_i}(\cdot | y_{< i})$ and + $q_{i | F_i}(\cdot | y_{< i})$ are $\epsilon$-ind for all $y_{< i}$. +2. $\mathbb P(E_i | y_{< i}), \mathbb P(F_i | y_{< i}) \ge 1 - \delta$ + for all $y_{< i}$. + +Let $E := \bigcap E_i$ and $F := \bigcap F_i$, then they both have +probability at least $1 - k \delta$, and $p_{i | E}(\cdot | y_{< i}$ and +$q_{i | F}(\cdot | y_{< i})$ are $\epsilon$-ind. + +By Advanced Adaptive Composition Theorem ($\delta = 0$), $p_{|E}$ and +$q_{|F}$ are +$(\epsilon' := k a(\epsilon) + \sqrt{2 k \log \beta^{-1}} (\epsilon + a(\epsilon)), \beta)$-ind. + +The rest is the same as in the proof of Claim 17. $\square$ + +Subsampling +----------- + +Stochastic gradient descent is like gradient descent, but with random +subsampling. + +Recall we have been considering databases in the space $Z^m$. Let +$n < m$ be a positive integer, +$\mathcal I := \{I \subset [m]: |I| = n\}$ be the set of subsets of +$[m]$ of size $n$, and $\gamma$ a random subset sampled uniformly from +$\mathcal I$. Let $r = {n \over m}$ which we call the subsampling rate. +Then we may add a subsampling module to the noisy gradient descent +algorithm (6.97) considered before + +$$\theta_{t} = \theta_{t - 1} - \alpha n^{-1} \sum_{i \in \gamma} \nabla_\theta h_\theta(x_i) |_{\theta = \theta_{t - 1}} + \zeta_t. \qquad (7)$$ + +It turns out subsampling has an amplification effect on privacy. + +**Claim 19 (Ullman 2017)**. Fix +$r \in [0, 1]$. Let $n \le m$ be two nonnegative integers with +$n = r m$. Let $N$ be an $(\epsilon, \delta)$-dp machanism on $X^n$. +Define mechanism $M$ on $X^m$ by + +$$M(x) = N(x_\gamma)$$ + +Then $M$ is $(\log (1 + r(e^\epsilon - 1)), r \delta)$-dp. + +**Remark**. Some seem to cite +Kasiviswanathan-Lee-Nissim-Raskhodnikova-Smith 2005 for this result, but +it is not clear to me how it appears there. + +**Proof**. Let $x, x' \in X^n$ such that they differ by one +row $x_i \neq x_i'$. Naturally we would like to consider the cases where +the index $i$ is picked and the ones where it is not separately. Let +$\mathcal I_\in$ and $\mathcal I_\notin$ be these two cases: + +$$\begin{aligned} +\mathcal I_\in = \{J \subset \mathcal I: i \in J\}\\ +\mathcal I_\notin = \{J \subset \mathcal I: i \notin J\}\\ +\end{aligned}$$ + +We will use these notations later. Let $A$ be the event +$\{\gamma \ni i\}$. + +Let $p$ and $q$ be the laws of $M(x)$ and $M(x')$ respectively. We +collect some useful facts about them. First due to $N$ being +$(\epsilon, \delta)$-dp, + +$$p_{|A}(S) \le e^\epsilon q_{|A}(S) + \delta.$$ + +Also, + +$$p_{|A}(S) \le e^\epsilon p_{|A^c}(S) + \delta.$$ + +To see this, note that being conditional laws, $p_A$ and $p_{A^c}$ are +averages of laws over $\mathcal I_\in$ and $\mathcal I_\notin$ +respectively: + +$$\begin{aligned} +p_{|A}(S) = |\mathcal I_\in|^{-1} \sum_{I \in \mathcal I_\in} \mathbb P(N(x_I) \in S)\\ +p_{|A^c}(S) = |\mathcal I_\notin|^{-1} \sum_{J \in \mathcal I_\notin} \mathbb P(N(x_J) \in S). +\end{aligned}$$ + +Now we want to pair the $I$\'s in $\mathcal I_\in$ and $J$\'s in +$\mathcal I_\notin$ so that they differ by one index only, which means +$d(x_I, x_J) = 1$. Formally, this means we want to consider the set: + +$$\mathcal D := \{(I, J) \in \mathcal I_\in \times \mathcal I_\notin: |I \cap J| = n - 1\}.$$ + +We may observe by trying out some simple cases that every +$I \in \mathcal I_\in$ is paired with $n$ elements in +$\mathcal I_\notin$, and every $J \in \mathcal I_\notin$ is paired with +$m - n$ elements in $\mathcal I_\in$. Therefore + +$$p_{|A}(S) = |\mathcal D|^{-1} \sum_{(I, J) \in \mathcal D} \mathbb P(N(x_I \in S)) \le |\mathcal D|^{-1} \sum_{(I, J) \in \mathcal D} (e^\epsilon \mathbb P(N(x_J \in S)) + \delta) = e^\epsilon p_{|A^c} (S) + \delta.$$ + +Since each of the $m$ indices is picked independently with probability +$r$, we have + +$$\mathbb P(A) = r.$$ + +Let $t \in [0, 1]$ to be determined. We may write + +$$\begin{aligned} +p(S) &= r p_{|A} (S) + (1 - r) p_{|A^c} (S)\\ +&\le r(t e^\epsilon q_{|A}(S) + (1 - t) e^\epsilon q_{|A^c}(S) + \delta) + (1 - r) q_{|A^c} (S)\\ +&= rte^\epsilon q_{|A}(S) + (r(1 - t) e^\epsilon + (1 - r)) q_{|A^c} (S) + r \delta\\ +&= te^\epsilon r q_{|A}(S) + \left({r \over 1 - r}(1 - t) e^\epsilon + 1\right) (1 - r) q_{|A^c} (S) + r \delta \\ +&\le \left(t e^\epsilon \wedge \left({r \over 1 - r} (1 - t) e^\epsilon + 1\right)\right) q(S) + r \delta. \qquad (7.5) +\end{aligned}$$ + +We can see from the last line that the best bound we can get is when + +$$t e^\epsilon = {r \over 1 - r} (1 - t) e^\epsilon + 1.$$ + +Solving this equation we obtain + +$$t = r + e^{- \epsilon} - r e^{- \epsilon}$$ + +and plugging this in (7.5) we have + +$$p(S) \le (1 + r(e^\epsilon - 1)) q(S) + r \delta.$$ + +$\square$ + +Since $\log (1 + x) < x$ for $x > 0$, we can rewrite the conclusion of +the Claim to $(r(e^\epsilon - 1), r \delta)$-dp. Further more, if +$\epsilon < \alpha$ for some $\alpha$, we can rewrite it as +$(r \alpha^{-1} (e^\alpha - 1) \epsilon, r \delta)$-dp or +$(O(r \epsilon), r \delta)$-dp. + +Let $\epsilon < 1$. We see that if the mechanism $N$ is +$(\epsilon, \delta)$-dp on $Z^n$, then $M$ is +$(2 r \epsilon, r \delta)$-dp, and if we run it over $k / r$ +minibatches, by Advanced Adaptive Composition theorem, we have +$(\sqrt{2 k r \log \beta^{-1}} \epsilon + 2 k r \epsilon^2, k \delta + \beta)$-dp. + +This is better than the privacy guarantee without subsampling, where we +run over $k$ iterations and obtain +$(\sqrt{2 k \log \beta^{-1}} \epsilon + 2 k \epsilon^2, k \delta + \beta)$-dp. +So with subsampling we gain an extra $\sqrt r$ in the $\epsilon$-part of +the privacy guarantee. But, smaller subsampling rate means smaller +minibatch size, which would result in bigger variance, so there is a +trade-off here. + +Finally we define the differentially private stochastic gradient descent +(DP-SGD) with the Gaussian mechanism +(Abadi-Chu-Goodfellow-McMahan-Mironov-Talwar-Zhang 2016), which is (7) +with the noise specialised to Gaussian and an added clipping operation +to bound to sensitivity of the query to a chosen $C$: + +$$\theta_{t} = \theta_{t - 1} - \alpha \left(n^{-1} \sum_{i \in \gamma} \nabla_\theta h_\theta(x_i) |_{\theta = \theta_{t - 1}}\right)_{\text{Clipped at }C / 2} + N(0, \sigma^2 C^2 I),$$ + +where + +$$y_{\text{Clipped at } \alpha} := y / (1 \vee {\|y\|_2 \over \alpha})$$ + +is $y$ clipped to have norm at most $\alpha$. + +Note that the clipping in DP-SGD is much stronger than making the query +have sensitivity $C$. It makes the difference between the query results +of two *arbitrary* inputs bounded by $C$, rather than *neighbouring* +inputs. + +In Part 2 we will use the tools developed above to discuss the privacy +guarantee for DP-SGD, among other things. + +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>. +- Dwork, Cynthia, and Aaron Roth. "The Algorithmic Foundations of + Differential Privacy." Foundations and Trends® in Theoretical + Computer Science 9, no. 3--4 (2013): 211--407. + <https://doi.org/10.1561/0400000042>. +- Dwork, Cynthia, Guy N. Rothblum, and Salil Vadhan. "Boosting and + Differential Privacy." In 2010 IEEE 51st Annual Symposium on + Foundations of Computer Science, 51--60. Las Vegas, NV, USA: + IEEE, 2010. <https://doi.org/10.1109/FOCS.2010.12>. +- Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya + Raskhodnikova, and Adam Smith. "What Can We Learn Privately?" In + 46th Annual IEEE Symposium on Foundations of Computer Science + (FOCS'05). Pittsburgh, PA, USA: IEEE, 2005. + <https://doi.org/10.1109/SFCS.2005.1>. +- Murtagh, Jack, and Salil Vadhan. "The Complexity of Computing the + Optimal Composition of Differential Privacy." In Theory of + Cryptography, edited by Eyal Kushilevitz and Tal Malkin, + 9562:157--75. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016. + <https://doi.org/10.1007/978-3-662-49096-9_7>. +- Ullman, Jonathan. "Solution to CS7880 Homework 1.", 2017. + <http://www.ccs.neu.edu/home/jullman/cs7880s17/HW1sol.pdf> +- Vadhan, Salil. "The Complexity of Differential Privacy." In + Tutorials on the Foundations of Cryptography, edited by Yehuda + Lindell, 347--450. Cham: Springer International Publishing, 2017. + <https://doi.org/10.1007/978-3-319-57048-8_7>. |