[CCS 2016] Deep Learning with DP - (4)

논문 제목: Deep Learning with Differential Privacy

출처: https://arxiv.org/abs/1607.00133

 

 지난 포스트에서 Moments Accountant의 작동 원리를 확인하였습니다. (이전 글 보기) 이번 포스트에서는 step마다 bound하는 방법에 관한 이야기를 해보겠습니다.

 

5. $\mathcal{M}_i$를 bound하기

 

주의사항: 해당 논문은 Gaussian Noise를 사용한다는 가정 하에 작성되었습니다.

 

$\text{Lemma 3}$

 함수 $f: D \rightarrow \mathbb{R}^p$가 존재하여 $||f(\cdot)||_2 \leq 1$을 만족한다고 가정하자. 그리고 $\sigma \geq 1$에 대하여 $q < \frac {1} {16\sigma}$의 확률로 독립적으로 sampling된 $i \in [n]$의 집합 $J$를 정의하자. 이때, 임의의 양의 정수 $\lambda \leq \sigma^2 log \frac {1} {q \sigma}$에 대하여, $\mathcal{M} (d) = \sum_{i \in J} f(d_i) + \mathcal{N} (0, \sigma^2 \textbf{I})$는 다음을 만족한다.

$$\alpha_{\mathcal{M}} (\lambda) \leq \frac {q^2 \lambda (\lambda + 1)} {(1 - q) \sigma^2} + O \left( \frac {q^3 \lambda^3} {\sigma^3} \right)$$

 

$\text{Proof}$

 어떠한 $d'$가 존재한다고 가정하고, $d := d' \cup \{d_n\}$으로 정의하자. (즉, $d$와 $d'$는 adjacent하다.) 이때, 일반성을 잃지 않고, $f(d_n) = \textbf{e}_1$,  $\sum_{i \in J \setminus [n]} f(d_i) = \textbf{0}$이라고 가정하자. 그러면 첫 번째 coordinate에서만 $\mathcal{M} (d)$와  $\mathcal{M} (d')$가 차이를 보이고, 이 부분만 제외하면 둘은 identically distributed되어 있으므로, 우리는 차이가 보이는 해당 한 차원에 대해서만 확인하면 충분하다.

 

 $\mathcal{N} (0, \sigma^2)$의 pdf를 $\mu_0$,  $\mathcal{N} (1, \sigma^2)$의 pdf를 $\mu_1$로 표기하자. 그러면 $\mathcal{M} (d') \sim \mu_0$이고, 가정에 의하여 $d_n$를 sampling할 확률이 $q$이므로 $\mathcal{M} (d) \sim \mu := (1 - q) \mu_0 + q \mu_1$이다. 이때, $\mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu(z)} {\mu_0(z)} \right) ^\lambda \right]$와 $\mathbb{E}_{z \sim \mu_0} \left[ \left( \frac {\mu_0(z)} {\mu(z)} \right) ^\lambda \right]$를 모두 bound할 것인데, 두 case를 동시에 살펴보기 위하여, 임의의 두 분포 $\nu_0$, $\nu_1$에 대하여 $\mathbb{E}_{z \sim \nu_0} \left[ \left( \frac {\nu_0(z)} {\nu_1(z)} \right) ^\lambda \right]$를 대신 bound하고자 한다. 이때, 다음 식이 성립한다.

$$\begin{align*} \mathbb{E}_{z \sim \nu_0} \left[ \left( \frac {\nu_0(z)} {\nu_1(z)} \right) ^\lambda \right] &= \mathbb{E}_{z \sim \nu_1} \left[ \left( \frac {\nu_0(z)} {\nu_1(z)} \right) ^{\lambda + 1} \right] \\&= \mathbb{E}_{z \sim \nu_1} \left[ \left( 1 + \frac {\nu_0(z) - \nu_1(z)} {\nu_1(z)} \right) ^{\lambda + 1} \right] \\&= \underbrace{\sum_{t=0}^{\lambda + 1} {\lambda + 1 \choose t} \mathbb{E}_{z \sim \nu_1} \left[ \left( \frac {\nu_0(z) - \nu_1(z)} {\nu_1(z)} \right) ^t \right]}_{(*)} \; (\because \text{Binomial Theorem}) \end{align*}$$

 

$(*)$의 첫 번째 term($t = 0$)은 $1$이고, $(*)$의 두 번째 term($t = 1$)은 다음과 같이 $0$이다.

$$\begin{align*} {\lambda + 1 \choose 1} \mathbb{E}_{z \sim \nu_1} \left[ \frac {\nu_0 (z) - \nu_1 (z)} {\nu_1 (z)} \right] &= (\lambda + 1) \int_{-\infty}^{\infty} \nu_1(z) \times \frac {\nu_0 (z) - \nu_1 (z)} {\nu_1 (z)} dz \\&= (\lambda + 1) \left( \int_{-\infty}^{\infty} \nu_0(z) dz - \int_{-\infty}^{\infty} \nu_1(z) dz \right) \\&= (\lambda + 1) (1 - 1) = 0 \end{align*}$$

 

여기에서, 우리는 $(*)$의 세 번째 term($t = 2$)과 네 번째 term($t = 3$)의 bound가 나머지 모든 term들의 합을 dominate한다는 것을 보일 것이다. 편의 상 $\nu_0 = \mu_0$,  $\nu_1 = \mu$인 경우만 설명하는데, $\nu_0 = \mu$,  $\nu_1 = \mu_0$인 경우도 동일한 방식으로 증명할 수 있다. 우선, $t = 2$일 때를 살펴보면,

$$\begin{align*} \mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^2 \right] &= \mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu_0(z) - \left( (1 - q) \mu_0(z) + q \mu_1(z) \right) } {\mu(z)} \right) ^2 \right] \; (\because \mu = (1 - q) \mu_0 + q \mu_1) \\&= \mathbb{E}_{z \sim \mu} \left[ \left( \frac {q \mu_0(z) - q \mu_1(z) } {\mu(z)} \right) ^2 \right] \\&= q^2 \mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu_0(z) - \mu_1(z) } {\mu(z)} \right) ^2 \right] \\&= q^2 \int_{-\infty}^{\infty} \mu(z) \times \left( \frac {\mu_0(z) - \mu_1(z) } {\mu(z)} \right) ^2 dz  \\&= q^2 \int_{-\infty}^{\infty} \frac {( \mu_0(z) - \mu_1(z))^2} {\mu(z)} dz \\&\leq \frac {q^2} {1 - q} \int_{-\infty}^{\infty} \frac {( \mu_0(z) - \mu_1(z))^2} {\mu_0(z)} dz \; (\because \mu = (1 - q) \mu_0 + q \mu_1) \\&= \frac {q^2} {1 - q}  \mathbb{E}_{z \sim \mu_0} \left[ \left( \frac {\mu_0(z) - \mu_1(z) } {\mu_0(z)} \right) ^2 \right] \end{align*}$$

에서, $\mathbb{E}_{z \sim \mu_0} \left[ \left( \frac {\mu_0(z) - \mu_1(z) } {\mu_0(z)} \right) ^2 \right]$은 다음과 같이 정리된다.

$$\begin{align*} \mathbb{E}_{z \sim \mu_0} \left[ \left( \frac {\mu_0(z) - \mu_1(z) } {\mu_0(z)} \right) ^2 \right] &= \mathbb{E}_{z \sim \mu_0} \left[ \left( 1 - \frac {\mu_1(z)} {\mu_0(z)} \right) ^2 \right] \\&= \mathbb{E}_{z \sim \mu_0} \left[ \left( 1 - \frac {\frac{1} {\sqrt{2\pi}\sigma} e^{- \frac {(z - 1)^2} {2 \sigma^2}}} {\frac{1} {\sqrt{2\pi}\sigma} e^{- \frac {z^2} {2 \sigma^2}}} \right) ^2 \right] \\&= \mathbb{E}_{z \sim \mu_0} \left[ \left( 1 - e^{\frac {z^2} {2 \sigma^2} - \frac {(z - 1)^2} {2 \sigma^2}} \right) ^2 \right] \\&= \mathbb{E}_{z \sim \mu_0} \left[ \left( 1 - e^{\frac {2z - 1} {2 \sigma^2}} \right) ^2 \right] \\&= \mathbb{E}_{z \sim \mu_0} \left[ 1 - 2e^{\frac {2z - 1} {2 \sigma^2}} + e ^{\frac {4z - 2} {2\sigma^2}} \right] \\&= \mathbb{E}_{z \sim \mu_0} \left[ 1 \right] - 2 \mathbb{E}_{z \sim \mu_0} \left[ e^{\frac {2z - 1} {2 \sigma^2}} \right] + \mathbb{E}_{z \sim \mu_0} \left[ e ^{\frac {4z - 2} {2\sigma^2}} \right] \end{align*}$$

 이때, 임의의 $a \in \mathbb{R}$에 대하여,

$$\begin{align*} \mathbb{E}_{z \sim \mu_0} \left[ e^{\frac {2az^2} {2\sigma^2}} \right] &= \int_{-\infty}^{\infty} \mu_0(z) \times e^{\frac {2az^2} {2\sigma^2}} dz = \int_{-\infty}^{\infty} \frac {1} {\sqrt{2\pi}\sigma} e^{- \frac {z^2} {2\sigma^2} + \frac {2az^2} {2\sigma^2}} dz = \int_{-\infty}^{\infty} \frac {1} {\sqrt{2\pi}\sigma} e^{- \frac {(z - a)^2} {2\sigma^2} + \frac {a^2} {2\sigma^2}} dz \\&= e^{\frac {a^2} {2\sigma^2}} \times \int_{-\infty}^{\infty} \frac {1} {\sqrt{2\pi}\sigma} e^{- \frac {(z - a)^2} {2\sigma^2}} dz = e^{\frac {a^2} {2\sigma^2}} \end{align*}$$

이므로, 위 식은 다시 다음과 같이 정리된다. $(1)$

$$\begin{align*} \mathbb{E}_{z \sim \mu_0} \left[ \left( \frac {\mu_0(z) - \mu_1(z) } {\mu_0(z)} \right) ^2 \right] &= \mathbb{E}_{z \sim \mu_0} \left[ 1 \right] - 2 \mathbb{E}_{z \sim \mu_0} \left[ e^{\frac {2z - 1} {2 \sigma^2}} \right] + \mathbb{E}_{z \sim \mu_0} \left[ e ^{\frac {4z - 2} {2\sigma^2}} \right] \\&= 1 - 2 e^{- \frac {1} {2\sigma^2}} \times \mathbb{E}_{z \sim \mu_0} \left[ e^{\frac {2z} {2 \sigma^2}} \right] + e^{- \frac {2} {2\sigma^2}} \times \mathbb{E}_{z \sim \mu_0} \left[ e ^{\frac {4z} {2\sigma^2}} \right] \\&= 1 - 2 \times e^{\frac {1} {2\sigma^2}} \times e ^ {- \frac {1} {2\sigma^2}} + e^{\frac {4} {2\sigma^2}} \times e^{\frac {-2} {2\sigma^2}} \; (\because (1)) \\&= 1 - 2 + e^{\frac {1} {\sigma^2}} =  e^{\frac {1} {\sigma^2}} - 1 \end{align*}$$

---

$\text{Claim}$: 임의의 $\sigma \geq 1$, $k > 0$에 대하여, $e < \left( \left( 1 + \frac {k} {\sigma^2} \right)^{\frac {\sigma^2} {k}} \right)^2 \leq e^2$이다. $(2)$

 

$\text{Proof}$

$e$의 정의 상 자명하다. $\square$

 

---

 그러므로, 우리가 bound하고자 하는 $(*)$의 세 번째 term($t = 2$)은 다음과 같이 bound된다.

$$\begin{align*} {\lambda + 1 \choose 2} \mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu_0(z) - \mu_(z) } {\mu(z)} \right) ^2 \right] &= \frac {\lambda(\lambda + 1)} {2} \mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu_0(z) - \mu_1(z) } {\mu_0(z)} \right) ^2 \right] \\&\leq \frac {\lambda(\lambda + 1)} {2} \times \frac {q^2} {1 - q} \mathbb{E}_{z \sim \mu_0} \left[ \left( \frac {\mu_0(z) - \mu_1(z) } {\mu_0(z)} \right) ^2 \right] \\&= \frac {\lambda(\lambda + 1)} {2} \times \frac {q^2} {1 - q} \times \left( e^{\frac {1} {\sigma^2}} - 1 \right) \\&< \frac {\lambda(\lambda + 1)} {2} \times \frac {q^2} {1 - q} \times \frac {2} {\sigma^2} \; (\because (2) \text{ with } k = 2) \\&= \frac {\lambda (\lambda + 1) q^2} {(1 - q) \sigma^2} \end{align*}$$

 이제, $(*)$의 나머지 term들에 관해서 확인하기 위하여, $z < 0$, $0 \leq z \leq 1$, $z > 1$, 이렇게 세 개의 구간으로 $z$를 구분하자. 이때,

$$\begin{align*} \left| \mu_0(z) - \mu_1(z) \right| &= \left| \frac {1} {\sqrt{2\pi}\sigma} e^{-\frac {z^2} {2\sigma^2}} - \frac {1} {\sqrt{2\pi}\sigma} e^{-\frac {(z - 1)^2} {2\sigma^2}} \right| = \frac {1} {\sqrt{2\pi}\sigma} \left| e^{-\frac {z^2} {2\sigma^2}} - e^{-\frac {z^2 - 2z + 1} {2\sigma^2}} \right| \\&= \frac {1} {\sqrt{2\pi}\sigma} e^{-\frac {z^2} {2\sigma^2}} \left| 1 - e^{-\frac {- 2z + 1} {2\sigma^2}} \right| = \mu_0(z) \left| 1 - e^{-\frac {- 2z + 1} {2\sigma^2}} \right|  \end{align*}$$

이므로, $0 \leq z \leq 1$일 때에는 $\left| \mu_0(z) - \mu_1(z) \right| = \mu_0(z) \left| 1 - e^{-\frac {- 2z + 1} {2\sigma^2}} \right| \leq \mu_0 \left( e^{\frac {1} {2\sigma^2}} - 1\right) < \frac {1} {\sigma^2} \mu_0(z)$이다. (여기에서, 마지막 부등식은 $k = 1$일 때 $(2)$를 이용한 것이다.) 또한, $z < 0$일 때에는 $\left| 1 - e^{-\frac {- 2z + 1} {2\sigma^2}} \right| = 1 - e^{-\frac {- 2z + 1} {2\sigma^2}}$이므로, 임의의 $x \in \mathbb{R}$에 대하여 $1 + x \leq e^x$임을 이용하여 $\left| \mu_0(z) - \mu_1(z) \right| = \mu_0(z) \left( 1 - e^{-\frac {- 2z + 1} {2\sigma^2}} \right) \leq \mu_0(z) \times \frac {-2z + 1} {2 \sigma^2} < - \frac {(z - 1)} {\sigma^2} \mu_0(z)$임을 알 수 있다. 한편, 동일한 방식으로 $z > 1$인 경우를 계산해보면,

$$\begin{align*} \left| \mu_0(z) - \mu_1(z) \right| &= \left| \frac {1} {\sqrt{2\pi}\sigma} e^{-\frac {z^2} {2\sigma^2}} - \frac {1} {\sqrt{2\pi}\sigma} e^{-\frac {(z - 1)^2} {2\sigma^2}} \right| = \frac {1} {\sqrt{2\pi}\sigma} \left| e^{-\frac {z^2} {2\sigma^2}} - e^{-\frac {(z - 1)^2} {2\sigma^2}} \right| \\&= \frac {1} {\sqrt{2\pi}\sigma} \left| e^{-\frac {(z - 1)^2} {2\sigma^2} - \frac {2z - 1} {2\sigma^2}} - e^{-\frac {(z - 1)^2} {2\sigma^2}} \right| = \frac {1} {\sqrt{2\pi}\sigma} e^{-\frac {(z - 1)^2} {2\sigma^2}} \left| e^{- \frac {2z - 1} {2\sigma^2}} - 1 \right| \\&= \mu_1(z) \left| e^{- \frac {2z - 1} {2\sigma^2}} - 1 \right| = \mu_1(z) \left( 1 - e^{- \frac {2z - 1} {2\sigma^2}} \right) \\&\leq \mu_1(z) \times \frac {2z - 1} {2\sigma^2} \; (\because 1 + x \leq e^x \text{ for all } x \in \mathbb{E}) \\&< \frac {z} {\sigma^2} \mu_1(z) \end{align*}$$

이다. 이상을 정리하면 다음과 같다. $(3)$

$$\begin{align*} \forall z < 0 &: |\mu_0(z) - \mu_1(z)| \leq - \frac {(z - 1)} {\sigma^2} \mu_0(z) \\ \forall z > 1 &: |\mu_0(z) - \mu_1(z)| \leq \frac {z} {\sigma^2} \mu_1(z) \\ \forall 0 \leq z \leq 1 &: |\mu_0(z) - \mu_1(z)| \leq \frac {1} {\sigma^2} \mu_0(z) \end{align*}$$

 

 이제, 이 세 구간에 맞추어 $\mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^t \right]$를 다음과 같이 분할하자. 우리는 $A, B, C$를 각각 bound할 것이다.

$$\begin{align*} \mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^t \right] &\leq \underbrace{\int_{-\infty}^0 \mu(z) \left| \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^t \right| dz}_{A} \\&\quad + \underbrace{\int_0^1 \mu(z) \left| \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^t \right| dz}_{B} \\&\quad + \underbrace{\int_1^{\infty} \mu(z) \left| \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^t \right| dz}_{C} \end{align*}$$

이때, 정의 상 $\mu = (1 - q)\mu_0 + q\mu_1$이므로, $\mu_0 - \mu = q(\mu_0 - \mu_1)$, $\mu \leq (1 - q)\mu_0$임을 알고 있다. $(4)$ 또한, $\sqrt{\frac {2} {\pi}} < 1$이므로, $\mathbb{E}_{z \sim \mu_0} [|z|^t] = \int_{-\infty}^{\infty} \mu_0(z)|z|^t dt \leq \sigma^t (t - 1)!!$이다. $(5)$ 따라서, $A$ term은 다음과 같이 정리된다.

$$\begin{align*} \int_{-\infty}^0 \mu(z) \left| \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^t \right| dz &= \int_{-\infty}^0 \frac { \left| \mu_0(z) - \mu(z) \right|^t } {(\mu(z))^{t - 1}} dz \\&\leq \int_{-\infty}^0 \frac { \left| q (\mu_0(z) - \mu_1(z)) \right|^t } {( (1 - q) \mu_0(z) )^{t - 1}} dz \; (\because (4)) \\&= \frac {q^t} {(1 - q)^{t - 1}} \int_{-\infty}^0 \frac { \left| \mu_0(z) - \mu_1(z) \right|^t } {( \mu_0(z) )^{t - 1}} dz \\&\leq \frac {q^t} {(1 - q)^{t - 1}} \int_{-\infty}^0 \frac { \frac {|z - 1| ^ t} {\sigma^{2t}} \times (\mu_0(z))^t } {( \mu_0(z) )^{t - 1}} dz \; (\because (3))  \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_{-\infty}^0 \mu_0(z) |z - 1| ^ t dz  \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_{\infty}^0 \mu_0(- z) |- z - 1| ^ t \times (-1) dz \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_0^{\infty} \mu_0(z) |z + 1| ^ t dz  \\&\leq \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \times \frac {1} {2} \int_{-\infty}^{\infty} \mu_0(z) |z + 1| ^ t dz \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \times \frac {1} {2} \mathbb{E}_{z \sim \mu_0} [|z + 1|^t] \\&\leq \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \times \frac {1} {2}  \times 2^t \sigma^t (t - 1)!! \; (\because (5)) \\&= \frac {(2q)^t (t - 1)!!} {2(1 - q)^{t - 1} \sigma^{2t}} \end{align*}$$

 

한편, $B$ term은 다음과 같이 정리된다.

$$\begin{align*} \int_{0}^1 \mu(z) \left| \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^t \right| dz &\leq \int_0^1 \mu(z)  \left| \left( \frac { q (\mu_0(z) - \mu_1(z))} { (1 - q) \mu_0(z) } \right)^t \right| dz \; (\because (4)) \\&= \frac {q^t} {(1 - q)^t} \int_0^1 \mu(z)  \left| \left( \frac {\mu_0(z) - \mu_1(z)} { \mu_0(z) } \right)^t \right| dz \\&\leq \frac {q^t} {(1 - q)^t} \int_0^1 \mu(z) \frac {(\frac {1} {\sigma^2} (\mu_0(z))^t} {(\mu_0(z))^t} dz \; (\because (3))  \\&= \frac {q^t} {(1 - q)^t}\int_0^1 \mu(z) \frac {1} {\sigma^{2t}}dz \\&= \frac {q^t} {(1 - q)^t \sigma^{2t}} \int_0^1 \mu(z) dz \\&< \frac {q^t} {(1 - q)^t \sigma^{2t}} \end{align*}$$

 

또한, $C$ term은 다음과 같이 정리된다.

$$\begin{align*} \int_{1}^{\infty} \mu(z) \left| \left( \frac {\mu_0(z) - \mu(z)} {\mu(z)} \right) ^t \right| dz &\leq \int_1^{\infty} \mu(z)  \left| \left( \frac { q (\mu_0(z) - \mu_1(z))} { (1 - q) \mu_0(z) } \right)^t \right| dz \; (\because (4)) \\&= \frac {q^t} {(1 - q)^t} \int_1^{\infty} \mu(z)  \left| \left( \frac {\mu_0(z) - \mu_1(z)} { \mu_0(z) } \right)^t \right| dz \\&\leq \frac {q^t} {(1 - q)^{t - 1}} \int_1^{\infty} \mu_0(z) \frac {(\frac {z} {\sigma^2} (\mu_1(z))^t} {(\mu_0(z))^t} dz \; (\because (3)) \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_1^{\infty} \mu_0(z) \left( \frac {z \mu_1(z)} {\mu_0(z)} \right)^t dz \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_1^{\infty} \mu_0(z) \left( z \times e^{- \frac {(z - 1)^2} {2\sigma^2} + \frac {z^2} {2\sigma^2}}  \right)^t dz \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_1^{\infty} \mu_0(z) \left( z \times e^{\frac {2z - 1} {2\sigma^2}} \right)^t dz \\&\leq \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_1^{\infty} \mu_0(z) \times e^{\frac {2tz - t} {2\sigma^2}} \times z^t dz \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_1^{\infty} \frac {1} {\sqrt{2\pi}\sigma} e^{\frac {z^2} {2\sigma^2} + \frac {2tz - t} {2\sigma^2}} \times z^t dz \\&= \frac {q^t} {(1 - q)^{t - 1} \sigma^{2t}} \int_1^{\infty} \frac {1} {\sqrt{2\pi}\sigma} e^{\frac {(z - t)^2 + t^2 - t} {2\sigma^2}} \times z^t dz \\&= \frac {q^t e^{\frac {t^2 - t} {2\sigma^2}}} {(1 - q)^{t - 1} \sigma^{2t}} \int_1^{\infty} \mu_0(z - t) \times z^t dz \\&\leq \frac {q^t e^{\frac {t^2 - t} {2\sigma^2}}} {(1 - q)^{t - 1} \sigma^{2t}} \times \frac {1} {2} \int_{-\infty}^{\infty} \mu_0(z - t) \times z^t dz \\&\leq \frac {(2q)^t e^{\frac {t^2 - t} {2\sigma^2}} (\sigma^t (t - 1)!! + t^t)} {(1 - q)^{t - 1} \sigma^{2t}} \; (\because (5)) \end{align*}$$

 

 주어진 $q, \sigma, \lambda$의 조건을 고려하였을 때, $t > 3$인 경우 $A, B, C$ 모두 그 값이 현저히 작아짐을 알 수 있다. $t = 3$ 인 경우에는 앞서 확인한 바와 같이 $O(\frac {q^3 \lambda^3} {\sigma^3})$로 bound되기 때문에, 최종적으로 $(*)$은 $\frac {\lambda (\lambda + 1) q^2} {(1 - q) \sigma^2} + O(\frac {q^3 \lambda^3} {\sigma^3})$로 bound된다. $\square$

 

 $\text{Lemma 3}$은 주어진 가정(이는 우리가 hyperparameter로 조절해야 하는 부분입니다)을 만족하는 임의의 mechanism $\mathcal{M_i}$의 log moment $\alpha_{\mathcal{M}_i} (\lambda)$를 bound할 수 있다는 것을 의미합니다. 다음 포스트에서는 이를 이용하여 우리의 최종 목적인 $\text{Theorem 1}$을 증명한 후, 실제 implementation이 어떻게 되었는지 살펴보는 시간을 갖도록 하겠습니다.