일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
- Federated Learning
- 개인정보
- Federated Transfer Learning
- OOD
- ML
- 머신러닝
- FL
- PPML
- q-FedAvg
- Machine learning
- Fairness
- DP
- 연합학습
- value shaping
- deep learning
- Agnostic FL
- convergence
- FedAvg
- 기계학습
- q-FFL
- Analysis
- ordered dropout
- data maximization
- OoDD
- free rider
- OSR
- 딥러닝
- FedProx
- Differential Privacy
- Open Set Recognition
- Today
- Total
Federated Learning
[ICML 2019] Agnostic FL - (4) 본문
논문 제목: Agnostic Federated Learning
출처: https://arxiv.org/abs/1902.00146
지난 포스트에서 weighted Rademacher complexity에 기반한 Agnostic FL의 learning guarantee를 확인하였습니다. (이전 글 보기) 이번 포스트에서는 해당 guarantee를 VC-dimension의 관점에서 다시 확인해본 후, Agnostic FL의 learning guarantee가 기존의 general bound와 어떠한 차이점을 보이는지에 관해서 알아보도록 하겠습니다.
5. Learning Guarantee - (2)
Lemma 3
ℓ이 −1 혹은 1의 값만 가지는 loss function이고, 이러한 loss들로 이루어진 family G가 VCdim(G)=d를 만족할 때, 다음 부등식이 성립한다:
Rm(G,λ)≤√2s(λ∥¯m)dmlog(emd)
Proof
임의의 λ∈Λ에 대해서, Aλ⊂Rm를 다음과 같이 정의하자.
Aλ={[λkmkℓ(h(xk,i),yk,i)](k,i)∈[p]×[mk]|x∈Xm,y∈Y}
이때, 임의의 a∈Aλ에 대해서 다음이 성립한다:
||a||2=√p∑k=1mk∑i=1λ2km2k=√p∑k=1mkλ2km2k=√p∑k=1λ2kmk=√p∑k=1λ2km⋅¯mk(∵
그러므로, 다음 부등식이 성립한다:
\begin{align*} \mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda) &= \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] \\&\leq \mathbb{E}_{\boldsymbol{\sigma}} \left[ \sup_{\textbf{a} \in A_\lambda} \sum_{k=1}^p \sum_{i=1}^{m_k} \sigma_{k, i} a_{k, i} \right] \; (\because a_{k, i} = \frac {\lambda_k} {m_k} \ell (h(x_{k, i}), y_{k, i})) \\&\leq \sqrt{\frac {\mathfrak{s} (\Lambda \parallel \overline{\textbf{m}})} {m}} \sqrt{2 \log |A_\lambda|} \; (\because \text{Massart's Lemma}) \\&= \frac{\sqrt{2 \mathfrak{s} (\Lambda \parallel \overline{\textbf{m}}) \log |A_\lambda|}} {m} \\&\leq \sqrt{\frac{2 \mathfrak{s} (\Lambda \parallel \overline{\textbf{m}}) \log \left( \frac {em} {d} \right)^d} {m}} \; (\because \text{Sauer's Lemma}) \\&= \sqrt{2 \mathfrak{s} (\Lambda \parallel \overline{\textbf{m}}) \frac {d} {m}\log \left( \frac {em} {d} \right)} \; \square \end{align*}
\text{Theorem 2}와 마찬가지로, \text{Lemma 3}에서도 \mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda)의 upper bound에 skewness term이 영향을 미친다는 것을 확인할 수 있습니다. 그리고 이 skewness tearm \mathfrak{s} (\lambda \parallel \overline{\textbf{m}}) 부분만 제외하면 기존의 generalization bound와 상당히 유사한 모습을 보인다는 것을 알 수 있습니다. 실제로, 기존의 가정처럼 \lambda_k = \frac {m_k} {m}으로 \lambda \in \Lambda를 구성할 경우, 놀랍게도 \text{Theorem 2}과 \text{Lemma 3} 모두 기존의 generalization bound와 동일해집니다.
7. Regularization
이제부터는 실제로 Agnostic FL이 어떻게 작동하는지 확인해볼 차례입니다. 우선, objective function을 구성해야 하는데, 당연히 \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h)를 그대로 사용하지는 않고, regularization term을 붙일 것입니다.
\text{Definition} [Convex Hull]
점들의 집합 \mathcal{P} \subset \mathbb{R}^d의 convex hull \text{conv} (\mathcal{P})는 다음과 같이 정의된다: \text{conv} (\mathcal{P}) := \left\{ \sum_{i=1}^n \lambda_i p_i \;\middle|\; n \in \mathbb{Z}_{>0} \wedge \sum_{i=1}^n \lambda_i = 1 \wedge \forall i \in [n], p_i \in \mathcal{P} \right\}
다시 말해서, \mathcal{P}의 convex combination을 모두 모은 것이 \text{conv} (\mathcal{P})라는 이야기입니다. 알고리즘을 공부하셨던 분들이라면 계산기하학 분야에서 Convex Hull을 접해보셨을텐데, 그것과 동일한 개념입니다. 즉, \text{conv} (\mathcal{P})를 "\mathcal{P}를 포함하는 minimal convex set"으로 이해하셔도 좋습니다. 다만, 굳이 위와 같이 정의를 하는 이유는, \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h)이 \lambda에 관하여 linear하다는 것을 고려하였을 때 \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) = \mathcal{L}_{\mathcal{\overline{D}}_{\text{conv} (\lambda)}} (h)라는 점을 이용하기 위해서입니다. (그리고 사실 이 두 정의는 서로 동치입니다.)
다음으로, 우리의 hypothesis set \mathcal{H}에 적절한 norm을 줄 수 있다고 가정합시다. (이는 대부분의 paper에서 가정하고 있는 것으로, 크게 문제가 되는 부분은 아닙니다.) 그리고 임의의 r \geq 0에 대해서, \Lambda_r을 다음과 같이 정의합니다.
\Lambda_r := \left\{ \lambda \in \text{conv} (\Lambda) \; \middle| \; \chi^2 (\lambda \parallel \overline{\textbf{m}}) + 1 \leq r \right\}
\mathfrak{s} (\Lambda \parallel \overline{\textbf{m}}) := \max_{\lambda \in \Lambda} \chi^2 (\lambda \parallel \overline{\textbf{m}}) + 1임을 고려하였을 때, \Lambda_r는 skewness term에 restriction을 주는 것으로 이해할 수 있습니다. 이러한 상황에서, 우리의 objective function을 \mathcal{L}_{\mathcal{\overline{D}}_{\lambda_r}} (h) + \gamma ||h||로 잡는 것은 매우 자연스럽습니다. (단, r \geq 0, \gamma \geq 0, || \cdot ||은 적절한 norm) 그리고 이를 최적화하는 과정은 다음과 같이 표현할 수 있습니다. (여기에서, r \geq 0 term을 \mu \geq 0 term으로 변경하였습니다.)
\min_{h \in \mathcal{H}} \max_{\lambda \in \text{conv}{(\Lambda)}} \left( \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) + \gamma ||h|| - \mu \chi^2 (\lambda \parallel \overline{\textbf{m}}) \right)
이때, 만약 \ell이 h에 대하여 convex하다면, \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) 역시 그러하고, 또 ||h||는 그 자체로 h에 대하여 convex하기 때문에 우리의 objective function \mathcal{L}_{\mathcal{\overline{D}}_\lambda} (h) + \gamma ||h|| - \mu \chi^2 (\lambda \parallel \overline{\textbf{m}})가 h에 대하여 convex하다는 것을 알 수 있습니다. 따라서 앞으로는 \ell이 h에 대하여 convex하다는 가정 하에 convex optimization을 수행할 것입니다. (아쉽게도, 해당 논문은 convex case만 다루고 있습니다. 따라서 다음 포스트부터 진행될 optimization에는 non-convex optimization이 포함되어 있지 않습니다. 하지만 많은 paper의 결과가 그러하듯이, convex case에서의 결과가 잘 보장된다면 non-convex의 case에서도 empirical하게는 성능이 보장될 것이기 때문에 큰 걱정은 하지 않아도 됩니다.)
'Federated Learning > Papers' 카테고리의 다른 글
[ICML 2019] Agnostic FL - (6) (0) | 2022.11.17 |
---|---|
[ICML 2019] Agnostic FL - (5) (0) | 2022.11.14 |
[ICML 2019] Agnostic FL - (3) (0) | 2022.11.07 |
[ICML 2019] Agnostic FL - (2) (1) | 2022.11.05 |
[ICML 2019] Agnostic FL - (1) (0) | 2022.11.02 |