Federated Learning

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

Federated Learning/Papers

[ICML 2019] Agnostic FL - (4)

pseudope 2022. 11. 8. 12:00
728x90

논문 제목: 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 GVCdim(G)=d를 만족할 때, 다음 부등식이 성립한다:

Rm(G,λ)2s(λ¯m)dmlog(emd)

 

Proof

 임의의 λΛ에 대해서, AλRm를 다음과 같이 정의하자.

Aλ={[λkmk(h(xk,i),yk,i)](k,i)[p]×[mk]|xXm,yY}

이때, 임의의 aAλ에 대해서 다음이 성립한다:

||a||2=pk=1mki=1λ2km2k=pk=1mkλ2km2k=pk=1λ2kmk=pk=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)

  이때, 만약 \ellh에 대하여 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하다는 것을 알 수 있습니다. 따라서 앞으로는 \ellh에 대하여 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
Comments