[ICML 2019] Agnostic FL - (3)

논문 제목: Agnostic Federated Learning

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

 

 지난 포스트에서 fairness에 관한 내용을 간단하게 다룬 후, 몇 가지 definition을 확인하였습니다. (이전 글 보기) 이번 포스트에서는 첫 번째 learning guarantee에 관하여 살펴보겠습니다. paper에 있는 증명은 생략된 부분이 매우 많습니다. 최대한 자세하게 풀어서 적고자 했으니, 참고 바랍니다.

 

5. Learning Guarantee - (1)

 

$\text{Theorem 2}$

 

 $M > 0$에 의하여 loss $l$이 bounded되어 있고,  $\epsilon > 0$가 고정된 상황을 가정하자. $S_k \sim \mathcal{D}_k ^{m_k}$를 sampling하였을 때, 임의의 $\delta > 0$에 대해서 최소 $(1 - \delta)$의 확률로   모든 $h \in \mathcal{H}$, $\lambda \in \Lambda$에 대하여 다음 부등식이 성립한다:

$$\mathcal{L}_{\mathcal{D}_\lambda} (h) \leq \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) + 2 \mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda) + M \epsilon + M \sqrt{\frac {\mathfrak{s} (\lambda \parallel \overline{\textbf{m}})} {2m} \log \frac {|\Lambda_\epsilon|} {\delta}}$$

 

$\text{Proof}$

 $\lambda$를 고정하고, 임의의 sample $S = (S_1, \cdots, S_p)$에 대해서 $\Psi(S_1, \cdots, S_p)$를 다음과 같이 정의하자.

$$\Psi(S_1, \cdots, S_p) := \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\lambda} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right)$$

그리고 $S' = (S_1', \cdots, S_p')$는 $S$와 딱 한 가지 point만 다른 sample로 정의하고, 이때 그 서로 다른 point를 $S_k$의 $x_{k, i}$와 $S'_k$의 $x'_{k, i}$라고 하자. 그렇다면 $\Psi(S_1, \cdots, S_p)$와 $\Psi(S'_1, \cdots, S'_p)$의 차이는 존재하지 않거나, 만약 존재한다면 차이가 나타나는 $x_{k, i}$,  $x'_{k, i}$ 지점이 원인일 것이다. 따라서,

$$\begin{align*} \Psi(S'_1, \cdots, S'_p) - \Psi(S_1, \cdots, S_p) &= \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\lambda} (h) -  \mathcal{L}_{\mathcal{\overline{D}}'_\lambda} (h) \right) - \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\lambda} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \\&\leq \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\lambda} (h) -  \mathcal{L}_{\mathcal{\overline{D}}'_\lambda} (h) \right) - \left( \mathcal{L}_{\mathcal{D}_\lambda} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \\&\leq \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\lambda} (h) -  \mathcal{L}_{\mathcal{\overline{D}}'_\lambda} (h) - \mathcal{L}_{\mathcal{D}_\lambda} (h) +  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \\&= \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) - \mathcal{L}_{\mathcal{\overline{D}}'_\lambda} (h) \right) \\&= \sup_{h \in \mathcal{H}} \left( \sum_{p=1}^k \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} \ell (h(x_{k, i}), y_{k,i}) - \sum_{p=1}^k \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} \ell (h(x'_{k, i}), y'_{k,i}) \right) \\&=  \sup_{h \in \mathcal{H}} \frac {\lambda_k} {m_k} \left[ \ell (h(x_{k, i}), y_{k,i}) - \ell (h(x'_{k, i}), y'_{k,i}) \right] \\&\quad(\because \text{$x_{k, i}$ and $x'_{k, i}$ are the only differences by assumptions}) \\&\leq \frac {\lambda_k} {m_k} M \; (\because \text{error is bounded by $M$ by assumptions}) \end{align*}$$

임을 알 수 있다. 따라서, $\text{McDiarmid's inequality}$에 의하여 임의의 $h \in \mathcal{H}$에 대해서 다음 부등식이 성립한다:

$$\begin{align*} &P \left(\Psi(S) - \mathbb{E} \left[ \Psi(S) \right]  \geq \epsilon \right) \leq \underbrace{\exp \left( - \frac {2 \epsilon^2} {\sum_{k=1}^p \sum_{i=1}^{m_k} \left( \frac {\lambda_k} {m_k} M \right)^2} \right)}_{=: \delta} \\\iff\; &1 - P \left(\Psi(S) - \mathbb{E} \left[ \Psi(S) \right]  \geq \epsilon \right) \geq 1 - \delta \\\iff\; &P \left( \Psi(S) - \mathbb{E} \left[ \Psi(S) \right] \leq \epsilon \right) \geq 1 - \delta  \end{align*}$$

다시 말해, $\epsilon$은 임의로 지정한 값이므로, 임의의 $\delta > 0$에 대해서 적어도 $(1 - \delta)$의 확률로 다음 부등식이 성립한다:

$$\begin{align*} &\Psi(S) \leq \epsilon - \mathbb{E} \left[ \Psi(S) \right]  = M \sqrt{\sum_{k=1}^p \frac {\lambda_k^2} {2 m_k} \log \frac {1} {\delta}} \; (\because \epsilon > 0) \\\iff\; &\sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) - \mathbb{E} \left[ \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \right] \leq M \sqrt{\sum_{k=1}^p \frac {\lambda_k^2} {2 m_k} \log \frac {1} {\delta}}  \\\implies\; &\mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) - \mathbb{E} \left[ \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \right] \leq M \sqrt{\sum_{k=1}^p \frac {\lambda_k^2} {2 m_k} \log \frac {1} {\delta}} \\\iff\; &\mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) \leq \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) + \mathbb{E} \left[ \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \right] + M \sqrt{\sum_{k=1}^p \frac {\lambda_k^2} {2 m_k} \log \frac {1} {\delta}} \end{align*}$$

 지금까지는 $\lambda$를 특정한 값 하나로 고정한 상태였다. 이제 임의의 $\lambda \in \Lambda_\epsilon$에 대해서 고려를 하고자 하는데, 이는 $|\Lambda_\epsilon|$만큼 더 tight하게 잡으면 되므로 $\log \frac {1} {\delta}$ term을 $\log \frac {|\Lambda_\epsilon|} {\delta}$으로 수정해주면 된다. 그리고 더 나아가서 임의의 $\lambda \in \Lambda_\epsilon$에 대해서 고려할 경우, $\Lambda_\epsilon$의 정의에 따라 임의의 $\lambda \in \Lambda$에 대해서 $\mathcal{L}_{\mathcal{D}_\lambda (h)} - \mathcal{L}_{\mathcal{D'}_\lambda (h)} \leq M \epsilon$을 만족하는 $\lambda' \in \Lambda_\epsilon$이 존재하기 때문에, $M \epsilon$ term이 추가적으로 필요하다. 즉, 임의의 $\delta > 0$, $\lambda \in \Lambda$에 대해서 적어도 $(1 - \delta)$의 확률로 다음 부등식이 성립한다:

$$\mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) \leq \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) + \mathbb{E} \left[ \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \right] + M \epsilon + M \sqrt{\sum_{k=1}^p \frac {\lambda_k^2} {2 m_k} \log \frac {|\Lambda_\epsilon|} {\delta}}$$

 

---

$\text{Claim}$: $\mathbb{E} \left[ \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \right] \leq 2 \mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda)$

 

$\text{Proof}$

$$\begin{align*} 2 \mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda)  &= 2 \mathbb{E}_{S_k \sim \mathcal{D}_k^{m_k} \\ \quad \boldsymbol{\sigma}} \left[ \sup_{h \in \mathcal{H}} \sum_{k=1}^p \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} \sigma_{k, i} \ell (h (x_{k, i}, y_{k, i})) \right] \\&=  \mathbb{E}_{S_k \sim \mathcal{D}_k^{m_k} \\ \quad \boldsymbol{\sigma}} \left[ \sup_{h \in \mathcal{H}} \sum_{k=1}^p \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} \sigma_{k, i} \ell (h (x_{k, i}, y_{k, i})) \right] \\&\quad + \mathbb{E}_{S'_k \sim \overline{\mathcal{D}}_k^{m_k} \\ \quad \boldsymbol{\sigma}} \left[ \sup_{h \in \mathcal{H}} \sum_{k=1}^p \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} - \sigma_{k, i} \ell (h (x'_{k, i}, y'_{k, i})) \right] \\&\quad (\because \sigma_{k, i} \text{'s are Rademacher random variables}) \\&\geq  \mathbb{E}_{S_k \sim \mathcal{D}_k^{m_k} \\ S'_k \sim \overline{\mathcal{D}}_k^{m_k} \\ \quad \boldsymbol{\sigma}} \left[ \sup_{h \in \mathcal{H}} \sum_{k=1}^p \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} \sigma_{k, i} \left( \ell (h (x_{k, i}, y_{k, i}))  - \ell (h (x'_{k, i}, y'_{k, i})) \right) \right] \\&\quad (\because \text{the subadditivity of supremum}) \\&= \mathbb{E}_{S_k \sim \mathcal{D}_k^{m_k} \\ S'_k \sim \overline{\mathcal{D}}_k^{m_k}} \left[ \sup_{h \in \mathcal{H}} \sum_{k=1}^p \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} \left( \ell (h (x_{k, i}, y_{k, i}))  - \ell (h (x'_{k, i}, y'_{k, i})) \right) \right] \\&\quad (\because \sigma_{k, i} \text{'s are Rademacher random variables}) \\&\geq \mathbb{E}_{S_k \sim \mathcal{D}_k^{m_k}} \left[ \sup_{h \in \mathcal{H}} \mathbb{E}_{S'_k \sim \overline{\mathcal{D}}_k^{m_k}} \left[ \sum_{k=1}^p \frac {\lambda_k} {m_k} \sum_{i=1}^{m_k} \left( \ell (h (x_{k, i}, y_{k, i}))  - \ell (h (x'_{k, i}, y'_{k, i})) \right) \right] \right] \\&\quad (\because \text{the subadditivity of supremum}) \\&= \mathbb{E} \left[ \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \right] \; (\because \text{the Law of Iterated Expectations}) \; \square  \end{align*}$$

---

 $\text{Claim}$에 의하여 $\mathbb{E} \left[ \sup_{h \in \mathcal{H}} \left( \mathcal{L}_{\mathcal{D}_\mathcal{\lambda}} (h) -  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) \right) \right] \leq 2 \mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda)$이며,

$$\begin{align*} \chi^2 (\lambda \parallel \overline{\textbf{m}}) + 1 &= \sum_{k=1}^p \frac {\left( \lambda_k - \frac {m_k} {n} \right)^2} {\frac {m_k} {m}} + 1 = \sum_{k=1}^p \frac {\lambda_k^2} {\frac {m_k} {m}} - 2 \sum_{k=1}^p \lambda_k + \sum_{k=1}^p \frac {m_k} {m} + 1 \\&= \sum_{k=1}^p \frac {\lambda_k^2} {\frac {m_k} {m}} - 2 + 1 + 1 \; (\because \sum_{k=1}^p \lambda_k = 1 \text{ and } \sum_{k=1}^p m_k = m) \\&= m \sum_{k=1}^p \frac {\lambda_k^2} {m_k} \end{align*}$$

이므로, $\sum_{k=1}^p \frac {\lambda_k^2} {2m_k} = \frac {1} {2m} \left( \chi^2 (\lambda \parallel \overline{\textbf{m}}) + 1 \right) \leq \frac {\mathfrak{s} (\lambda \parallel \overline{\textbf{m}})} {2m}$임을 알 수 있다. 따라서,

$$M \sqrt{\sum_{k=1}^p \frac {\lambda_k^2} {2 m_k} \log \frac {|\Lambda_\epsilon|} {\delta}}  \leq M \sqrt{\frac {\mathfrak{s} (\lambda \parallel \overline{\textbf{m}})} {2m} \log \frac {|\Lambda_\epsilon|} {\delta}}$$

로 bounded되며, 이것으로 증명을 마친다. $\square$

 

 직관적으로 보았을 때, $\text{Theorem 2}$은 고정된 $\lambda$에 대해서 $\mathcal{L}_{\mathcal{D}_\lambda} (h)$의 variance가 skewness term $\mathfrak{s} (\lambda \parallel \overline{\textbf{m}})$에 dependent한다는 것을 이야기하고 있습니다. (참고로, 해당 theorem은 upper bound를 이야기하고 있지만, lower bound 역시 $\mathfrak{s} (\lambda \parallel \overline{\textbf{m}})$에 dependent합니다. 즉, loss의 variance에 skewness가 큰 영향을 주고 있는 셈입니다. 다만, lower bound는 주제에서 벗어나기 때문에 이에 관하여 자세하게 언급하지 않도록 하겠습니다.) 그리고 이 variance는 $\lambda$가 $\overline{\textbf{m}}$에서 멀어지면 $\lambda \approx \overline{\textbf{m}}$일 때보다 조금 더 큰 bound가 필요할 수 있다는 것으로 해석 가능합니다.

 

 또한, $\lambda$ 대신 $\Lambda$에 관한 loss를 고려할 때에는 단순히 $\text{Theorem 2}$의 부등식 양 변에 $\max_{\lambda \in \Lambda}$를 취해주면 됩니다. 즉, $\mathcal{L}_{\mathcal{D}_\Lambda}$는 다음과 같이 bounded됨이 최소 $(1 - \delta)$의 확률로 보장됩니다.

$$\begin{align*} \mathcal{L}_{\mathcal{D}_\Lambda} = \max_{\lambda \in \Lambda} \mathcal{L}_{\mathcal{D}_\lambda} (h) &\leq \max_{\lambda \in \Lambda} \left(  \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) + 2 \mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda) + M \epsilon + M \sqrt{\frac {\mathfrak{s} (\lambda \parallel \overline{\textbf{m}})} {2m} \log \frac {|\Lambda_\epsilon|} {\delta}} \right) \\&\leq \mathcal{L}_{\mathcal{\overline{D}}_\Lambda} (h) + 2 \mathfrak{R}_\textbf{m} (\mathcal{G}, \Lambda) + M \epsilon + M \sqrt{\frac {\mathfrak{s} (\Lambda \parallel \overline{\textbf{m}})} {2m} \log \frac {|\Lambda_\epsilon|} {\delta}} \end{align*}$$

 

 다음 포스트에서는 $\text{Theorem 2}$를 VC-dimension의 관점에서 다시 살펴보도록 하겠습니다.