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

논문 제목: Fair Resource Allocation in Federated Learning

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

 

 지난 포스트에서 q-FFL을 정의한 후, Agnostic FL을 q-FFL의 특수한 case로 볼 수 있다는 것을 확인하였습니다. 그리고 두 model 간의 fairness를 비교하기 위하여, 몇 가지 형태의 uniformity를 정의하였습니다. (이전 글 보기) 이번 포스트에서는 fairness를 비교하는 몇 가지 예시들을 확인해보도록 하겠습니다.

 

4. Uniformity 비교

 

 시작하기에 앞서, 증명 과정에서의 편의를 위하여 $f_q (w)$를 다시 정의하도록 하겠습니다.

$$f_q (w) := \sum_{k=1}^m \frac {p_k} {q + 1} F_k^{q + 1} (w)\quad \longrightarrow \quad f_q (w) := \left( \frac {1} {m} \sum_{k=1}^m F_k^{q + 1} (w) \right)^{\frac {1} {q + 1}}$$

즉, $p_k$ term 대신 $\frac {1} {m}$ term을 사용한, unweighted version의 objective function이라고 보시면 됩니다. ($\frac {1} {q + 1}$을 지수로 옮긴 것은 $\ell (h(x), y)$가 $\log$ 값을 가지고, 이들의 합인 $F_k(w)$도 $\log$로 표현되기 때문입니다.) 앞으로는 이와 같이 정의한 $f_q (w)$를 $w$에 대하여 minimize하는 task를 수행할 것이며, 이 $f_q (w)$에 대한 global optimum solution을 $w_q^*$로 표기하겠습니다.

 

$\text{Lemma 7}$

 

 Performance Distribution의 variance에 대한 관점에서 볼 때, $q = 1$이 $q = 0$보다 더욱 fair한 solution을 이끌어낸다. 다시 말해, $\text{Var} (F_1 (w_1^*), \cdots, F_m (w_1^*)) \leq \text{Var} (F_1 (w_0^*), \cdots, F_m (w_0^*))$이다.

 

$\text{Proof}$

$$\begin{align*} w_0^* &= \text{argmin}_w \; f_0(w) \text{, where } f_0 (w) = \left( \frac {1} {m} \sum_{k=1}^m F_k (w) \right), \\ w_1^* &= \text{argmin}_w \; f_1(w) \text{, where } f_1 (w) = \left( \frac {1} {m} \sum_{k=1}^m F_k^2 (w) \right)^{\frac {1} {2}} \end{align*}$$

이므로,

$$\sum_{k=1}^m F_k^2 (w_1^*) \leq \sum_{k=1}^m F_k^2 (w_0^*), \; \sum_{k=1}^m F_k (w_1^*) \geq  \sum_{k=1}^m F_k (w_0^*)$$

이다. $(\dagger)$ 따라서,

$$\begin{align*} \text{Var} (F_1 (w_1^*), \cdots, F_m (w_1^*)) &= \frac {\sum_{k=1}^m F_k^2 (w_1^*)} {m} - \left( \frac {1} {m} \sum_{k=1}^m F_k (w_1^*) \right)^2 \; (\because \text{Var} (X) = \mathbb{E} [X^2] - \left( \mathbb{E} [X] \right)^2) \\&\leq \frac {\sum_{k=1}^m F_k^2 (w_0^*)} {m} - \left( \frac {1} {m} \sum_{k=1}^m F_k (w_1^*) \right)^2 \; (\because (\dagger)) \\&\leq \frac {\sum_{k=1}^m F_k^2 (w_0^*)} {m} - \left( \frac {1} {m} \sum_{k=1}^m F_k (w_0^*) \right)^2 \; (\because (\dagger)) \end{align*}$$

이다. $\square$

 

$\text{Lemma 8}$

 

 Performance Distribution과 $\textbf{1}$ 간의 Cosine Similarity에 대한 관점에서 볼 때, $q = 1$이 $q = 0$보다 더욱 fair한 solution을 이끌어낸다. 다시 말해,

$$\frac {\frac {1} {m} \sum_{k=1}^m F_k(w_1^*)} {\sqrt{\frac {1} {m} \sum_{k=1}^m F_k^2(w_1^*)}} \geq \frac {\frac {1} {m} \sum_{k=1}^m F_k(w_0^*)} {\sqrt{\frac {1} {m} \sum_{k=1}^m F_k^2(w_0^*)}}$$

이다.

 

$\text{Proof}$

 $\text{Lemma 7}$의 $(\dagger)$에 의하여 자명하다. $\square$

 

 물론, $q = 0$, $q = 1$일 때에만 이러한 이야기를 할 수 있는 것은 아닙니다. 지금부터는 조금 더 general한 case를 살펴보겠습니다.

 

$\text{Lemma 9}$

 

  $F (w)$가 $w$에 대해서 twice differnetiable하고, $\nabla^2 F (w) \succ 0$이라고 가정하자. 이때, 다음이 성립한다:

$$\frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \bigg\rvert_{p=q} \geq 0$$

 

$\text{Proof}$

$$\begin{align*} \frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \bigg\rvert_{p=q} &= - \frac {\partial} {\partial p} \sum_{k=1}^m \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \log \left( \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \right) \bigg\rvert_{p=q} \; (\because \text{By definition of $\tilde{H} (\cdot)$}) \\&= - \frac {\partial} {\partial p} \sum_{k=1}^m \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \log F_k^q (w_p^*) \bigg\rvert_{p=q} + \frac {\partial} {\partial p} \sum_{k=1}^m \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \log \sum_{k=1}^m F_k^q (w_p^*) \bigg\rvert_{p=q} \\&= - \frac {\partial} {\partial p} \sum_{k=1}^m \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \log F_k^q (w_p^*) \bigg\rvert_{p=q} + \frac {\partial} {\partial p} \log \sum_{k=1}^m F_k^q (w_p^*) \underbrace{\frac {\sum_{k=1}^m F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)}}_{= 1} \bigg\rvert_{p=q} \\&= \underbrace{- \frac {\partial} {\partial p} \sum_{k=1}^m \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \log F_k^q (w_p^*) \bigg\rvert_{p=q}}_{=: A} + \underbrace{\frac {\partial} {\partial p} \log \sum_{k=1}^m F_k^q (w_p^*) \bigg\rvert_{p=q}}_{=: B} \end{align*}$$

여기에서,

$$\begin{align*} A &:= - \frac {\partial} {\partial p} \sum_{k=1}^m \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \log F_k^q (w_p^*) \bigg\rvert_{p=q} = - \sum_{k=1}^m \frac {\partial} {\partial p} \left( \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \log F_k^q (w_p^*) \right) \bigg\rvert_{p=q} \\&= - \sum_{k=1}^m \frac {\partial} {\partial p} \left( F_k^q (w_p^*) \right) \frac {\log F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \bigg\rvert_{p=q} - \sum_{k=1}^m \frac {\partial} {\partial p} \left( \log F_k^q (w_p^*) \right) \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \bigg\rvert_{p=q} \\&\quad - \sum_{k=1}^m \frac {\partial} {\partial p} \left( \frac {1} {\sum_{k=1}^m F_k^q (w_p^*)}  \right) \log F_k^q (w_p^*) F_k^q (w_p^*) \bigg\rvert_{p=q} \\&=  - \sum_{k=1}^m \frac{ \left( \frac {\partial} {\partial p} w^*_p \right)^T \nabla F_k^q (w_p^*)} {1} \frac {\log F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \bigg\rvert_{p=q} - \sum_{k=1}^m \frac{ \left( \frac {\partial} {\partial p} w^*_p \right)^T \nabla F_k^q (w_p^*)} {F_k^q (w_p^*)} \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \bigg\rvert_{p=q} \\&\quad + \sum_{k=1}^m \left( \frac {\sum_{k=1}^m \frac {\partial} {\partial p} F_k^q (w_p^*)} {\left(\sum_{k=1}^m F_k^q (w_p^*) \right)^2}  \right) \log F_k^q (w_p^*) F_k^q (w_p^*) \bigg\rvert_{p=q} \\&= - \sum_{k=1}^m \frac{ \left( \frac {\partial} {\partial p} w^*_p \right)^T \nabla F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \left( \log F_k^q (w_p^*) + 1 \right) \bigg\rvert_{p=q} \\&\quad + \underbrace{\sum_{k=1}^m \left( \frac {\sum_{k=1}^m \left( \frac {\partial} {\partial p} w^*_p \right)^T \nabla F_k^q (w_p^*)} {\left(\sum_{k=1}^m F_k^q (w_p^*) \right)^2}  \right) \log F_k^q (w_p^*) F_k^q (w_p^*) \bigg\rvert_{p=q}}_{= 0 \; (\because \text{optimal})} \\&= - \sum_{k=1}^m \frac{ \left( \frac {\partial} {\partial p} w^*_p \bigg\rvert_{p=q} \right)^T \nabla F_k^q (w_q^*)} {\sum_{k=1}^m F_k^q (w_q^*)} \left( \log F_k^q (w_q^*) + 1 \right) , \\ B &:= \frac {\partial} {\partial p} \log \sum_{k=1}^m F_k^q (w_p^*) \bigg\rvert_{p=q} = \frac {\sum_{k=1}^m \left( \frac {\partial} {\partial p} w^*_p \right)^T \nabla F_k^q (w_p^*)} { \sum_{k=1}^m F_k^q (w_p^*)} = 0 \; (\because \text{optimal})\end{align*}$$

이므로,

$$\begin{align*} \frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \bigg\rvert_{p=q} &= A + B = - \sum_{k=1}^m \frac{ \left( \frac {\partial} {\partial p} w^*_p \bigg\rvert_{p=q} \right)^T \nabla F_k^q (w_q^*)} {\sum_{k=1}^m F_k^q (w_q^*)} \left( \log F_k^q (w_q^*) + 1 \right) \end{align*}$$

이고 $(1)$, 따라서 $\frac {\partial} {\partial p} w^*_p \bigg\rvert_{p=q}$의 값만 확인하면 된다. 우선, 정의 상 $\sum_{k=1}^m \nabla_w F_k^p (w_p^*) = 0$임을 알고 있고, 해당 식의 양변을 $p$에 대해서 미분해주면 다음과 같은 식을 얻을 수 있다:

$$\begin{align*} 0 &= \frac {\partial} {\partial p} \left( \sum_{k=1}^m \nabla_w F_k^p (w_p^*) \right) = \sum_{k=1}^m \frac {\partial} {\partial p} \left( \nabla_w F_k^p (w_p^*) \right) \\&= \sum_{k=1}^m \left( \nabla_w^2 F_k^p (w_p^*) \frac {\partial} {\partial p} w_p^* + \left( \log F_k^p (w_p^*) + 1 \right) \nabla_w F_k^p (w_p^*)\right) \; (\because \frac {\partial} {\partial p} x^p = x^p \log x) \\&= \sum_{k=1}^m \left( \nabla_w^2 F_k^p (w_p^*) \frac {\partial} {\partial p} w_p^* \right) + \sum_{k=1}^m \left( \log F_k^p (w_p^*) + 1 \right) \nabla_w F_k^p (w_p^*) \end{align*}$$

따라서, Implicit Function Theorem에 의하여

$$\frac {\partial} {\partial p} w_p^* = -  \left( \sum_{k=1}^m \nabla_w^2 F_k^p (w_p^*) \right)^{-1} \sum_{k=1}^m \left( \log F_k^p (w_p^*) + 1 \right) \nabla_w F_k^p (w_p^*)$$

이며, 여기에 $p = q$를 대입하여$\left( \frac {\partial} {\partial p} w^*_p \bigg\rvert_{p=q} \right)$를 구한 후, 이를 $(1)$에 대입하면 증명이 마무리된다. $\square$

 

 $\text{Lemma 9}$가 말하는 것은, $p$가 고정되었을 때, 임의의 충분히 작은 $\epsilon > 0$에 대해서 $\left\{ F_1^p (w_{p + \epsilon}^*), \cdots, F_1^p (w_{p + \epsilon}^*) \right\}$가 $\left\{ F_1^p (w_p^*), \cdots, F_m^p (w_p^*) \right\}$보다 Entropy의 관점에서 더욱 uniform하다는 것입니다. 아래의 $\text{Lemma 10}$은 이를 조금 더 generalize한 것으로, 임의의 $p, q$에 대해서, $\left\{ F_1^q (w_{p + \epsilon}^*), \cdots, F_m^q (w_{p + \epsilon}^*) \right\}$가 $\left\{ F_1^q (w_p^*), \cdots, F_1^q (w_p^*) \right\}$보다 Entropy의 관점에서 더욱 uniform하다는 것을 말합니다. 비록 $m = 2$인 case로 한정지어서 이야기하고 있지만, 충분히 임의의 $m \in \mathbb{Z}_{>0}$으로 확장할 수 있습니다.

 

$\text{Lemma 10}$

 

  $F (w)$가 $w$에 대해서 twice differnetiable하고, $\nabla^2 F (w) \succ 0$이라고 가정하자. 이때, 임의의 $q > 0$에 대해서, $m=2$일 경우에 다음이 성립한다:

$$\frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \geq 0$$

 

$\text{Proof}$

 우선, $\text{Lemma 9}$에 의해서 다음 부등식이 성립한다는 것을 알고 있다:

$$\frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \bigg\rvert_{p=q} \geq 0$$

여기에서, $\theta_q (w)$를 다음과 같이 정의하자:
$$\theta_q (w) := \frac {F_1^q (w)} {F_1^q (w) + F_2^q (w)}$$

이때, 일반성을 잃지 않고, $\theta_q (w_p^*) \in (0, \frac {1} {2}]$라고 하자. (만약 $\frac {1} {2}$를 초과할 경우, $F_1$과 $F_2$를 서로 바꾸어 정의하면 된다.) 정의 상

$$\begin{align*} \tilde{H} (F^q(w_p^*)) \bigg\rvert_{p=q} &:= - \sum_{k=1}^m \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \log \left( \frac {F_k^q (w_p^*)} {\sum_{k=1}^m F_k^q (w_p^*)} \right) \bigg\rvert_{p=q} \\&= - \sum_{k=1}^2 \frac {F_k^q (w_p^*)} {\sum_{k=1}^2 F_k^q (w_p^*)} \log \left( \frac {F_k^q (w_p^*)} {\sum_{k=1}^2 F_k^q (w_p^*)} \right) \; \bigg\rvert_{p=q} (\because m = 2) \\&= - \sum_{k=1}^2 \frac {F_k^q (w_p^*)} {F_1^q (w_p^*) + F_2^q (w_p^*)} \log \left( \frac {F_k^q (w_p^*)} {F_1^q (w_p^*) + F_2^q (w_p^*)} \right) \bigg\rvert_{p=q} \\&= - \frac {F_1^q (w_p^*)} {F_1^q (w_p^*) + F_2^q (w_p^*)} \log \left( \frac {F_1^q (w_p^*)} {F_1^q (w_p^*) + F_2^q (w_p^*)} \right) \bigg\rvert_{p=q} \\&\quad - \frac {F_2^q (w_p^*)} {F_1^q (w_p^*) + F_2^q (w_p^*)} \log \left( \frac {F_2^q (w_p^*)} {F_1^q (w_p^*) + F_2^q (w_p^*)} \right) \bigg\rvert_{p=q} \\&= - \underbrace{\theta_q (w_p^*) \log \theta_q(w_p^*) \bigg\rvert_{p=q}}_{\leq 0} - \underbrace{(1 - \theta_q (w_p^*)) \log (1 - \theta_q (w_p^*)) \bigg\rvert_{p=q}}_{ \leq 0} \\&\geq 0 \end{align*}$$

이므로, $\frac {\partial} {\partial p} \theta_q (w_p^*) \bigg\rvert_{p=q} \geq 0$이고, $\frac {\partial} {\partial p} \left( \frac {F_1 (w_p^*)} {F_2 (w_p^*)} \right)^q \bigg\rvert_{p=q} \geq 0$이다. 또한, 임의의 $q > 0$에 대해서, $x^q$가 $x$에 관하여 monotonic하다는 것이 보장되므로, $\frac {\partial} {\partial p} \left( \frac {F_1 (w_p^*)} {F_2 (w_p^*)} \right)^q \geq 0$이라고 하여도 무방하다. 따라서, $\frac {\partial} {\partial p} \tilde{H} (F^q (w_p^*)) \geq 0$ 역시 성립한다. $\square$

 

 다음 포스트에서는 서로 다른 uniformity 간의 관계를 살펴본 후, q-FFL의 generalization bounds를 확인하도록 하겠습니다.