[ICLR 2020] q-FFL, q-FedAvg - (3)

논문 제목: Fair Resource Allocation in Federated Learning

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

 

 지난 포스트에서는 각기 다른 uniformity의 정의를 가지고 두 model 간의 fairness를 비교하는 몇 가지 예시를 확인하였습니다. (이전 글 보기) 이번 포스트에서는 uniformity 간의 관계를 확인해본 후, q-FFL의 generalization bounds를 분석하도록 하겠습니다. ($f_q (w)$는 이전 포스트와 동일하게 unweighted version을 사용할 것입니다.)

 

5. Uniformity 간의 관계

 

$\text{Lemma 11}$ [Entropy 관점의 uniformity와 Cosine Distance 관점의 uniformity의 equivalence]

 

 $\text{Definition 5}$의 uniformity와 $\text{Definition 6}$의 uniformity는 서로 동치이다. 더 나아가서, 다음과 같이 $(a)$와 $(b)$를 정의하였을 때, $(a) \iff (b)$이다.

 

    $(a)$: 임의의 $p, q \in \mathbb{R}$에 대해서, $\frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \geq 0$이다.

    $(b)$: 임의의 $0 \leq t \leq r$, $0 \leq v \leq u$에 대해서, $\frac {f_t (w_u^*)} {f_r (w_u^*)} \geq \frac {f_t (w_v^*)} {f_r (w_v^*)}$이다.

 

$\text{Proof}$

 

임의의 $0 \leq t \leq r$, $0 \leq v \leq u$에 대해서, 다음이 성립한다:

\begin{align*} \frac {f_t (w_u^*)} {f_r (w_u^*)} \geq \frac {f_t (w_v^*)} {f_r (w_v^*)} &\iff \log \frac {f_t (w_u^*)} {f_r (w_u^*)} \geq \log \frac {f_t (w_v^*)} {f_r (w_v^*)} \iff \log \frac {f_t (w_u^*)} {f_r (w_u^*)} - \log \frac {f_t (w_v^*)} {f_r (w_v^*)} \geq 0 \\&\iff \int_v^u \frac {\partial} {\partial \tau} \log \frac {f_t (w_\tau^*)} {f_r (w_\tau^*)} d\tau \geq 0 \iff \frac {\partial} {\partial p} \log \frac {f_t (w_p^*)} {f_r (w_p^*)} \geq 0 \text{ for any } p \geq 0 \\&\iff \frac {\partial} {\partial p} \log f_t (w_p^*) - \frac {\partial} {\partial p} \log f_r (w_p^*) \geq 0 \text{ for any } p \geq 0 \\&\iff \frac {\partial} {\partial p} \log f_r (w_p^*) - \frac {\partial} {\partial p} \log f_t (w_p^*) \leq 0 \text{ for any } p \geq 0 \\&\iff \int_t^r \frac {\partial^2} {\partial p \partial q} \log f_q (w_p^*) dq \leq 0 \text{ for any } p, q \geq 0 \\&\iff \frac {\partial^2} {\partial p \partial q} \log f_q (w_p^*) \leq 0 \text{ for any } p, q \geq 0 \\&\iff \frac {\partial} {\partial p} \left( \frac {\partial} {\partial q} \log f_q (w_p^*) \right) \leq 0 \text{ for any } p, q \geq 0 \\&\iff - \frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \leq 0 \text{ for any } p, q \geq 0 \\&\iff \frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \geq 0 \text{ for any } p, q \geq 0 \end{align*}

여기에서, $q = 1$인 경우가 $\text{Definition 6}$의 uniformity이고, $t = 0, r = 1$인 경우가 $\text{Definition 5}$의 uniformity이므로, 이 둘은 동치라고 할 수 있다. $\square$

 

6. Generalization Bounds

 

 이제 q-FFL의 learning bound를 알아보도록 하겠습니다. 그리고 이 bound가 Agnostic FL의 bound를 포함한다는 것도 확인해보겠습니다. 우선, 우리의 objective function을 다음과 같이 정의합니다: (여기에서, $\lambda \in \Lambda$, $D_k$는 client $k$가 가진 dataset의 distribution, $h \in \mathcal{H}$는 hypothesis function)

$$L_\lambda (h) := \sum_{k=1}^m \lambda_k \mathbb{E}_{(x, y) \sim D_k} \left[ \ell (h(x), y) \right]$$

그리고 이 $L_\lambda (h)$의 estimate $\hat{L}_\lambda (h)$를 다음과 같이 정의합니다: (여기에서, $n_k$는 client $k$가 가진 data의 개수이며, $(x_{k,  j}, y_{k, j}) \sim D_k$입니다.)

$$\hat{L}_\lambda (h) := \sum_{k=1}^m \frac {\lambda_k} {n_k} \sum_{j=1}^{n_k} \ell (h(x_{k,  j}), y_{k, j})$$

 

 이러한 상황에서 $\min_w f_q (w)$를 수행할 것인데, 이는 $\frac {1} {p} + \frac {1} {q + 1} = 1$를 만족시키는 $p$에 대해서 (위의 표현을 빌려)

$$\tilde{L}_q (h) := \max_{\nu, \; ||\nu||_p \leq 1} \sum_{k=1}^m \frac {\nu_k} {n_k} \sum_{j=1}^{n_k} \ell (h(x_{k, j}, y_{k, j}))$$

를 minimize하는 것과 동치입니다.

 

 아래의 $\text{Lemma}$에 대한 자세한 증명 과정은 Agnostic FL의 $\text{Theorem 2}$를 참고 바랍니다. (바로가기) $(\dagger)$

 

$\text{Lemma 12}$

 

 loss $\ell$이 $M > 0$으로 bounded되어 있고, $m$개의 client가 각각 $(n_1, \cdots, n_m)$개의 local data를 가지고 있다고 가정하자. 이때, 임의의 $\delta > 0, \lambda \in \Lambda, h \in \mathcal{H}$에 대해서, 적어도 $(1 - \delta)$의 확률로 다음 부등식이 성립한다:

$$ L_\lambda (h) \leq A_q (\lambda) \tilde{L}_q (h) + \mathbb{E} \left[ \max_{h \in \mathcal{H}} \left( L_\lambda (h) -  \hat{L}_\lambda (h) \right) \right] + M \sqrt{\sum_{k=1}^m \frac {\lambda_k^2} {2 n_k} \log \frac {1} {\delta}}$$

(단,  $A_q (\lambda) := ||\lambda||_p$이고, $\frac {1} {p} + \frac {1} {q + 1} = 1$이다.)

 

$\text{Proof}$

 $(\dagger)$와 동일한 전개에 의하여, 다음 부등식이 성립한다: $(1)$

$$ L_\lambda (h) \leq \hat{L}_\lambda (h) + \mathbb{E} \left[ \max_{h \in \mathcal{H}} \left( L_\lambda (h) -  \hat{L}_\lambda (h) \right) \right] + M \sqrt{\sum_{k=1}^m \frac {\lambda_k^2} {2 n_k} \log \frac {1} {\delta}}$$

따라서, $\hat{L}_\lambda (h)$ term에 대해서만 살펴보아도 충분하다. 이때,

\begin{align*} \hat{L}_\lambda (h) &:= \sum_{k=1}^m \frac {\lambda_k} {n_k} \sum_{j=1}^{n_k} \ell (h(x_{k,  j}), y_{k, j}) \\&= \sum_{k=1}^m \lambda_k F_k \; (\because \text{Definition of $F_k$}) \\&\leq \left( \sum_{k=1}^m \lambda_k^m \right)^{\frac {1} {p}} \left( \sum_{k=1}^m F_k^{q + 1} \right)^{\frac {1} {q + 1}} \; (\because \text{Hölder's inequiality with $\frac {1} {p} + \frac {1} {q + 1} = 1$}) \\&= ||\lambda||_p ||F_k||_{q + 1} \\&= A_q (\lambda) \tilde{L}_q (h) \end{align*}

이므로, 이를 다시 $(1)$에 대입하면 증명이 마무리된다. $\square$

 

 $\text{Lemma 12}$는 특정 $\lambda \in \Lambda$에 대한 bound만을 보장해주며, 임의의 $\lambda \in \Lambda$로 이를 확장하기 위해서는 아래의 $\text{Lemma 13}$이 필요합니다. 다만, 너무나도 자명하므로 증명은 생략합니다. 

 

$\text{Lemma 13}$

 

loss $\ell$이 $M > 0$으로 bounded되어 있고, $m$개의 client가 각각 $(n_1, \cdots, n_m)$개의 local data를 가지고 있다고 가정하자. 이때, 임의의 $\delta > 0, \lambda \in \Lambda, h \in \mathcal{H}$에 대해서, 적어도 $(1 - \delta)$의 확률로 다음 부등식이 성립한다:

$$ L_\lambda (h) \leq \max_{\lambda \in \Lambda} \left( A_q (\lambda) \right) \tilde{L}_q (h) + \max_{\lambda \in \Lambda} \left( \mathbb{E} \left[ \max_{h \in \mathcal{H}} \left( L_\lambda (h) -  \hat{L}_\lambda (h) \right) \right] + M \sqrt{\sum_{k=1}^m \frac {\lambda_k^2} {2 n_k} \log \frac {1} {\delta}} \right)$$

(단,  $A_q (\lambda) := ||\lambda||_p$이고, $\frac {1} {p} + \frac {1} {q + 1} = 1$이다.)

 

 $\text{Lemma 12, 13}$에서 만약 $q \rightarrow \infty$라면, $\frac {1} {p} + \frac {1} {q + 1} = 1$이므로 $p = 1$이고, 따라서 $A_q (\lambda) := ||\lambda||_p = \sum_{k=1}^m |\lambda_k| = 1$입니다. 그러므로 우리는 q-FFL의 generalization bounds가 Agnostic FL의 generalization bounds를 cover한다고 이야기할 수 있습니다. 다음 포스트에서는 q-FFL의 solver인 q-FedAvg에 관하여 알아보겠습니다.