[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)

 

$\text{Lemma 3}$

 

 $\ell$이 $-1$ 혹은 $1$의 값만 가지는 loss function이고, 이러한 loss들로 이루어진 family $\mathcal{G}$가 $\text{VCdim} (\mathcal{G}) = d$를 만족할 때, 다음 부등식이 성립한다:

$$\mathfrak{R}_\textbf{m} (\mathcal{G}, \lambda) \leq \sqrt{2 \mathfrak{s} (\lambda \parallel \overline{\textbf{m}}) \frac {d} {m} \log \left( \frac {em} {d} \right)}$$

 

$\text{Proof}$

 임의의 $\lambda \in \Lambda$에 대해서, $A_\lambda \subset \mathbb{R}^m$를 다음과 같이 정의하자.

$$A_\lambda = \left\{ \left[ \frac {\lambda_k} {m_k} \ell (h(x_{k, i}), y_{k, i}) \right]_{(k, i) \in [p] \times [m_k]} \;\middle|\; \textbf{x} \in \mathcal{X}^m, \textbf{y} \in \mathcal{Y} \right\}$$

이때, 임의의 $\textbf{a} \in A_\lambda$에 대해서 다음이 성립한다:

$$\begin{align*} ||\textbf{a}||_2 &= \sqrt{\sum_{k=1}^p \sum_{i=1}^{m_k} \frac {\lambda_k^2} {m_k^2}} = \sqrt{\sum_{k=1}^p m_k \frac {\lambda_k^2} {m_k^2}} =  \sqrt{\sum_{k=1}^p \frac {\lambda_k^2} {m_k}} = \sqrt{\sum_{k=1}^p \frac {\lambda_k^2} {m \cdot \overline{\textbf{m}}_k}} \; (\because \overline{\textbf{m}_k} = \frac {m_k} {m}) \\&= \sqrt{\frac {1} {m} \sum_{k=1}^p \frac {(\lambda_k - \overline{\textbf{m}_k})^2 + 2 \lambda_k \overline{\textbf{m}_k} - \overline{\textbf{m}_k}^2} {\overline{\textbf{m}}_k}} = \sqrt{\frac {1} {m} \left( \chi^2 (\lambda \parallel \overline{\textbf{m}}) + \sum_{k=1}^p (2 \lambda_k - \overline{\textbf{m}_k}) \right)} \\&= \sqrt{\frac {1} {m} \left( \chi^2 (\lambda \parallel \overline{\textbf{m}}) + 2 - 1 \right)} \; (\because \sum_{k=1}^p \lambda_k = 1 \text{ and } \sum_{k=1}^p \overline{\textbf{m}_k} = 1) \\&= \sqrt{\frac {\chi^2 (\lambda \parallel \overline{\textbf{m}}) + 1} {m}} \leq \sqrt{\frac {\mathfrak{s} (\Lambda \parallel \overline{\textbf{m}})} {m}} \; (\because \mathfrak{s} (\Lambda \parallel \overline{\textbf{m}}) = \max_{\lambda \in \Lambda} \chi^2 (\lambda \parallel \overline{\textbf{m}}) + 1) \end{align*}$$

 그러므로, 다음 부등식이 성립한다:

$$\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하게는 성능이 보장될 것이기 때문에 큰 걱정은 하지 않아도 됩니다.)