일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- deep learning
- FedProx
- 머신러닝
- Federated Transfer Learning
- DP
- q-FedAvg
- Machine learning
- OOD
- FedAvg
- Differential Privacy
- data maximization
- q-FFL
- Analysis
- value shaping
- OSR
- 딥러닝
- Federated Learning
- FL
- free rider
- PPML
- Open Set Recognition
- convergence
- ordered dropout
- Agnostic FL
- Fairness
- 개인정보
- 기계학습
- OoDD
- 연합학습
- ML
- Today
- Total
Federated Learning
[ICML 2019] Agnostic FL - (3) 본문
논문 제목: 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가 고정된 상황을 가정하자. Sk∼Dmkk를 sampling하였을 때, 임의의 δ>0에 대해서 최소 (1−δ)의 확률로 모든 h∈H, λ∈Λ에 대하여 다음 부등식이 성립한다:
LDλ(h)≤L¯Dλ(h)+2Rm(G,λ)+Mϵ+M√s(λ∥¯m)2mlog|Λϵ|δ
Proof
λ를 고정하고, 임의의 sample S=(S1,⋯,Sp)에 대해서 Ψ(S1,⋯,Sp)를 다음과 같이 정의하자.
Ψ(S1,⋯,Sp):=suph∈H(LDλ(h)−L¯Dλ(h))
그리고 S′=(S′1,⋯,S′p)는 S와 딱 한 가지 point만 다른 sample로 정의하고, 이때 그 서로 다른 point를 Sk의 xk,i와 S′k의 x′k,i라고 하자. 그렇다면 Ψ(S1,⋯,Sp)와 Ψ(S′1,⋯,S′p)의 차이는 존재하지 않거나, 만약 존재한다면 차이가 나타나는 xk,i, x′k,i 지점이 원인일 것이다. 따라서,
Ψ(S′1,⋯,S′p)−Ψ(S1,⋯,Sp)=suph∈H(LDλ(h)−L¯D′λ(h))−suph∈H(LDλ(h)−L¯Dλ(h))≤suph∈H(LDλ(h)−L¯D′λ(h))−(LDλ(h)−L¯Dλ(h))≤suph∈H(LDλ(h)−L¯D′λ(h)−LDλ(h)+L¯Dλ(h))=suph∈H(L¯Dλ(h)−L¯D′λ(h))=suph∈H(k∑p=1λkmkmk∑i=1ℓ(h(xk,i),yk,i)−k∑p=1λkmkmk∑i=1ℓ(h(x′k,i),y′k,i))=suph∈Hλkmk[ℓ(h(xk,i),yk,i)−ℓ(h(x′k,i),y′k,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 |