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

논문 제목: Deep Learning with Differential Privacy

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

 

 지난 포스트까지 해서 $\text{Theorem 1}$을 증명하기 위한 사전 준비를 모두 마쳤습니다. (이전 글 보기) 이번 포스트에서 증명을 마무리하도록 하고, implementation이 어떻게 되었는지 확인해보겠습니다.

 

6. $\text{Theorem 1}$ 증명하기

 

$\text{Theorem 1}$

 다음을 만족시키는 $c_1, c_2 \in \mathbb{R}$가 존재한다: 임의의 $\epsilon < c_1 q^2 T$와 $\delta > 0$에 대하여, 만약 $\sigma \geq c_2 \frac {q \sqrt{T \log \frac {1} {\delta} }} {\epsilon}$를 만족하는 $\sigma$를 선택한다면, DPSGD 알고리즘은 ($\epsilon$, $\delta$)-DP가 보장된다. (여기에서, $q := \frac {L} {N}$, $T$는 step 수)

 

$\text{Proof}$

 $\text{Lemma 3}$의 가정을 만족하도록 $\sigma$와 $q$를 설정하자. (즉, $\sigma \geq 1, q < \frac {1} {16\sigma}$) 이때, $\text{Theorem 2.1}$에 의하여 DPSGD 알고리즘의 $\alpha(\lambda)$ 값은 각 step마다의 $\alpha_t(\lambda)$ 값들의 합으로 bound되며($t = 1, 2, \cdots, T$), $\text{Lemma 3}$에 의하여 각 $\alpha_t (\lambda)$는 $\frac {q^2 \lambda (\lambda + 1)} {(1 - q) \sigma^2} + O \left( \frac {q^3 \lambda^3} {\sigma^3} \right) \approx \frac {q^2 \lambda^2} {\sigma^2}$로 bound 되므로, $\alpha(\lambda) \leq T \frac {q^2 \lambda^2} {\sigma^2}$이다. 그러면, $\text{Theorem 2.2}$에 의하여, $\delta = \min_{\lambda} \; e^{ \left( \alpha(\lambda) - \lambda \epsilon \right) }$를 만족하는 $\delta$에 대하여 DPSGD는 $(\epsilon, \delta)$-DP를 만족하게 된다.

 

 여기에서, $e^{\alpha(\lambda) - \lambda \epsilon} \leq e^{T \frac {q^2 \lambda^2} {\sigma^2} - \lambda \epsilon}$이므로, $\lambda$에 대한 1계도함수를 고려할 때, $2T \frac {q^2} {\sigma^2} \lambda - \epsilon \leq \lambda$,  즉,  $T \frac {q^2 \lambda^2} {\sigma^2} \leq \frac{\lambda \epsilon} {2}$이어야 한다. 그리고 이에 따라 $e^{-\frac {\lambda \epsilon} {2}} \leq \delta$를 만족해야 한다. 또한, $\text{Lemma 3}$을 이용하기 위해서, $\lambda \leq \sigma^2 \log \frac {1} {q \sigma}$이어야 한다.

 

이때, 만약 $\epsilon = c_1 q^2 T$라면, $\sigma = c_2 \frac {q \sqrt{T \log \frac {1} {\delta} }} {\epsilon}$로 설정하여 위 조건들을 모두 충족시킬 수 있다. 따라서, $\epsilon < c_1 q^2 T$일 경우, $\sigma \geq c_2 \frac {q \sqrt{T \log \frac {1} {\delta} }} {\epsilon}$로 $\sigma$를 지정하면 된다. $\square$

 

 이제 DPSGD 알고리즘이 (우리가 hyperparameter를 잘 지정해주면) $(\epsilon, \delta)$-DP를 보장한다는 것을 알기 때문에, 우리는 model 학습 과정에서 개인정보를 보호하고자 할 때, 이 알고리즘을 사용하는 것을 충분히 고려해볼 수 있습니다.

 

7. Hyperparameter 설정하기

 

 $\text{Theorem 1}$의 가정을 충족시키는 hyperparameter $\delta$, $q$, $\sigma$ 등을 지정하는 것도 물론 중요하지만, accuracy를 중시할 것인지, privacy cost를 중시할 것인지, 학습 속도를 중시할 것인지 등 여러 목적에 따라서 그러한 hyperparameter들의 조합 중 적절한 것을 선택하는 것 역시 중요합니다. 이는 experiments에서 살펴보도록 하겠습니다.

 

  다음으로, $\text{Theorem 1}$의 가정을 다시 살펴보면, $\sqrt{T}$ term 때문에 $T$가 커질수록 (즉, epoch 당 batch 수가 많아질수록) privacy cost가 증가한다는 것을 알 수 있습니다. (이에 반해, $q$ term의 영향력은 미비합니다.) 만약 objective function이 convex하다면 batch size를 $1$에 근접하게 잡는 것이 좋겠으나, 그러한 보장이 없기 때문에 적당히 작은 batch size를 잡으면 될 것입니다.

 

 마지막으로 learning rate의 경우, 일반적인 학습 과정에서는 decaying 시키지만, DPSGD의 경우 optimal하게 수렴하는 것이 현실적으로 불가능하기 때문에 그렇게까지 할 필요는 없다고 저자들은 이야기하고 있습니다. 이후에 experiments에서 살펴보겠지만, warmup 후 decaying을 하되, 일정 epoch 이상에서는 constant한 learning rate를 사용하는 것이 최고의 성능을 보여줍니다.

 

8. Implementation

 

 오른쪽 code는 실제 tensorflow를 이용하여 python으로 DPSGD를 implement한 code입니다. __init__()을 보면 "accountant"와 "sanitizer", 이렇게 두 가지의 component가 사용되는 것을 확인할 수 있는데, 각각이 무엇인지 살펴보도록 하겠습니다.

 

 sanitizer는 $(1)$ Gradient Clipping, $(2)$ noise 첨가, 이렇게 두 가지의 일을 수행합니다. 다만, 저자들은 tensorflow로 구현할 때 (pseudo code의 방식인) lot 단위가 아닌 batch 단위로 gradient computation을 수행하도록 구현하는 것이 성능 상에서 이점을 보였다고 이야기하고 있습니다. 비록 학습 속도가 조금 느려지겠지만, batch size가 큰 경우에도 그다지 속도 차이가 크지 않아서 이러한 구현 방식을 최종적으로 택하였다고 합니다.

 

 accountant는 $\alpha(\lambda)$를 계산하는 역할을 담당합니다. 계산하는 방법에는 여러 가지가 있겠지만, 저자들은 (Gaussian noise를 사용한다는 가정 하에) numerical integration을 통하여 $E_1 := \mathbb{E}_{z \sim \mu_0} \left[ \left( \frac {\mu_0(z)} {\mu(z)} \right)^\lambda \right]$와 $E_2 := \mathbb{E}_{z \sim \mu} \left[ \left( \frac {\mu(z)} {\mu_0(z)} \right)^\lambda \right]$를 구한 뒤, $\alpha(\lambda) = \log \max \{ E_1, E_2 \}$를 계산하였습니다.

 

 한편, 여러 $\lambda$의 값에 대하여 $\alpha(\lambda)$ 구한 뒤, 그때의 $\epsilon$과 $\delta$ 값을 서로 비교하여 가장 좋은 $\lambda$를 선택하는 것 역시 중요할텐데, 저자들은 $\lambda \leq 32$까지만 고려하면 충분하다고 이야기합니다. (이 주장에 대한 근거를 해당 논문에서 찾지 못하였는데, 아마도 실험에 의한 결과가 아닐까 생각됩니다.)

 

 다음 포스트에서는 DPSGD에 관한 각종 experiment를 살펴보도록 하겠습니다.