Federated Learning

[ICML 2019] Agnostic FL - (3) 본문

Federated Learning/Papers

[ICML 2019] Agnostic FL - (3)

pseudope 2022. 11. 7. 01:00
728x90

논문 제목: Agnostic Federated Learning

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

 

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

 

5. Learning Guarantee - (1)

 

Theorem 2

 

 M>0에 의하여 loss l이 bounded되어 있고,  ϵ>0가 고정된 상황을 가정하자. SkDmkk를 sampling하였을 때, 임의의 δ>0에 대해서 최소 (1δ)의 확률로   모든 hH, λΛ에 대하여 다음 부등식이 성립한다:

LDλ(h)L¯Dλ(h)+2Rm(G,λ)+Mϵ+Ms(λ¯m)2mlog|Λϵ|δ

 

Proof

 λ를 고정하고, 임의의 sample S=(S1,,Sp)에 대해서 Ψ(S1,,Sp)를 다음과 같이 정의하자.

Ψ(S1,,Sp):=suphH(LDλ(h)L¯Dλ(h))

그리고 S=(S1,,Sp)S와 딱 한 가지 point만 다른 sample로 정의하고, 이때 그 서로 다른 point를 Skxk,iSkxk,i라고 하자. 그렇다면 Ψ(S1,,Sp)Ψ(S1,,Sp)의 차이는 존재하지 않거나, 만약 존재한다면 차이가 나타나는 xk,i,  xk,i 지점이 원인일 것이다. 따라서,

Ψ(S1,,Sp)Ψ(S1,,Sp)=suphH(LDλ(h)L¯Dλ(h))suphH(LDλ(h)L¯Dλ(h))suphH(LDλ(h)L¯Dλ(h))(LDλ(h)L¯Dλ(h))suphH(LDλ(h)L¯Dλ(h)LDλ(h)+L¯Dλ(h))=suphH(L¯Dλ(h)L¯Dλ(h))=suphH(kp=1λkmkmki=1(h(xk,i),yk,i)kp=1λkmkmki=1(h(xk,i),yk,i))=suphHλkmk[(h(xk,i),yk,i)(h(xk,i),yk,i)](

임을 알 수 있다. 따라서, \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의 관점에서 다시 살펴보도록 하겠습니다.

'Federated Learning > Papers' 카테고리의 다른 글

[ICML 2019] Agnostic FL - (5)  (0) 2022.11.14
[ICML 2019] Agnostic FL - (4)  (0) 2022.11.08
[ICML 2019] Agnostic FL - (2)  (1) 2022.11.05
[ICML 2019] Agnostic FL - (1)  (0) 2022.11.02
[NeurIPS 2021] FjORD - (4)  (0) 2022.09.13