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

논문 제목: Fair Resource Allocation in Federated Learning

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

 

 Agnostic FL이 나름대로 Fairness를 FL 분야로 끌어오기는 했으나, 아직은 부족한 부분이 많았습니다. (이전 글 보기) 문제가 되는 부분은 크게 두 가지였는데, 하나는 학습에 참여하는 client가 많아지면 학습이 어려워진다는 것, 다른 하나는 Agnostic FL이 "가장 성능이 낮은" 한 가지 client의 성능을 높일 수는 있어도, 그 외의 client에게는 유의미한 보정을 해줄 수 없다는 것이었습니다. 이번에는 이 두 가지를 해결하려고 시도한 paper를 살펴보도록 하겠습니다.

 

1. $\alpha$-fairness

 

 $\alpha$-fairness라는 개념은 network 분야의 resource allocation에서 사용되던 개념입니다. 임의의 사용자에게 $x$에 해당하는 resource(예를 들어 주파수 대역 등)가 allocated되었을 때, 해당 사용자의 individual utility를 다음과 같이 정의합니다:

\begin{equation} U_\alpha (x) = \begin{cases} \ln (x) & \text{if $\alpha = 1$} \\ \frac {1} {1 - \alpha} x^{1 - \alpha} & \text{if $0 < \alpha < 1$ or $\alpha > 1$} \end{cases} \end{equation}

여기에서, 우리의 목표는 모든 사용자가 가지는 utility의 총합, 즉, $\sum_x U_\alpha (x)$를 최대한 키울 수 있는 $\alpha \geq 0$를 찾는 것입니다. 이때, 만약 $\alpha = 0$이라면, $U_\alpha (x) = x$이므로 별 다른 조치가 취해지지 않게 되고, 따라서 이 경우를 zero fairness라고 이야기하겠습니다. 이외에도 몇몇 $\alpha$들에 대하여 fairness에 이름이 붙어있는데, $\alpha = 1$인 경우를 proportional fairness, $\alpha = 2$인 경우를 harmonic mean fairness, 그리고 $\alpha = \infty$인 경우를 max-min fairness라고 부릅니다.

 

2. q-Fair Federated Learning (q-FFL)

 

 저자들이 제안하는 학습 방식인 q-FFL은 $\alpha$-fairness의 개념에 기반한 것인데, 그저 각 client의 utility를 각 client의 loss로 대체한 것뿐입니다. 다만, utility는 클수록 좋은 것이지만 loss는 작을수록 좋은 것이기 때문에, 합을 maximize하는 것이 아니라 minimize한다는 점, max-min fairness 대신 min-max fairness를 정의한다는 점 정도의 차이가 존재합니다. $\alpha$-fairness를 FL의 언어로 다시 써본, q-FFL의 objective function은 다음과 같습니다: (여기에서, $m$은 학습에 참여하는 총 client의 수, $n_k$는 client $k$가 가진 data의 개수, $p_k$는 client $k$에 대한 가중치입니다. 이때, $p_k \geq 0$이고, $\sum_{k=1}^m p_k = 1$입니다. 그리고 $q \geq 0$은 hyperparameter이며, $F_k^{q+1} (\cdot) := \left( F_k (\cdot) \right)^{q+1}$입니다.)

$$f_q (w) := \sum_{k=1}^m \frac {p_k} {q + 1} F_k^{q + 1} (w) \text{, where } F_k (w) := \frac {1} {n_k} \sum_{j_k=1}^{n_k} \ell_{j_k} (w)$$

 위 식에서, 만약 $q = 0$이라면, 아래와 같이 FedSGD / FedAVG의 모습을 나타냅니다. 이는 $\alpha$-fairness에서도 그러하였듯이 zero fairness에 해당하는 상황입니다.

$$f_0 (w) = \sum_{k=1}^m p_k F_k (w)$$

그리고 만약 $q > 0$라면, fairness를 보장하기 위하여 어떠한 조치가 취해지고 있는 상황인 것이고, $q$가 커질수록 더 높은 수준의 fairness가 강제되고 있음을 의미합니다. 더 나아가, 만일 $q = \infty$라면, 가장 큰 loss를 보이는 특정 한 client에 대해서 optimization이 수행될 것이기 때문에, ($\alpha$-fairness에서의 max-min fairness 대신) min-max fairness에 해당하는 상황이 펼쳐질 것이며, 이는 정확히 이전 review에서 살펴본 Agnostic FL에 해당합니다. 즉, q-FFL은 Agnostic FL의 generalization입니다. hyperparameter $q$를 사용하여 fairness와 accuracy 사이의 trade-off를 조절하게 만든 것이죠. (이는 $\alpha$ 값을 조절하여 fairness와 utility 사이의 trade-off를 조절하는 $\alpha$-fairness의 개념과 일맥상통합니다.)

 

3. q-FFL의 uniformity

 

 다음은 두 model 간의 uniformity를 비교하기 위한 몇 가지 definition입니다.

 

$\text{Definition 1}$ [Fairness of the Performance Distribution]

 

 두 개의 model $w$, $\tilde{w}$와 $m$개의 device가 존재할 때, 만약 $m$개의 device에 대한 performance가 $\tilde{w}$보다 $w$에서 더욱 uniform한 distribution을 보인다면, $w$가 $\tilde{w}$보다 더 "fair"한 solution이라고 부르기로 약속하자.

 

$\text{Definition 4}$ [Uniformity 1: Variance of the Performance Distribution]

 

 만약 $\text{Var} (F_1 (w), \cdots, F_m (w)) < \text{Var} (F_1 (w'), \cdots, F_m (w'))$이라면, $w'$보다 $w$에서 $m$개의 device들이 가지는 performance distribution $\{F_1 (w), \cdots, F_m (w)\}$이 더욱 uniform하다고 정의한다.

 

$\text{Definition 5}$ [Uniformity 2: Cosine Similarity between the Performance Distribution and $\textbf{1}$]

 

 만약 $\{F_1 (w), \cdots, F_m (w)\}$과 $\textbf{1}$ 사이의 cosine similarity가 $\{F_1 (w'), \cdots, F_m (w')\}$과 $\textbf{1}$ 사이의 cosine similarity보다 크거나 같다면 즉,

$$\frac {\frac {1} {m} \sum_{k=1}^m F_k(w)} {\sqrt{\frac {1} {m} \sum_{k=1}^m F_k^2(w)}} \geq \frac {\frac {1} {m} \sum_{k=1}^m F_k(w')} {\sqrt{\frac {1} {m} \sum_{k=1}^m F_k^2(w')}}$$

이라면, $w'$보다 $w$에서 $m$개의 device들이 가지는 performance distribution $\{F_1 (w), \cdots, F_m (w)\}$이 더욱 uniform하다고 정의한다.

 

$\text{Definition 6}$ [Uniformity 3: Entropy the Performance Distribution]

 

 $\tilde{H} (F(w))$를 performance distribution $\{F_1 (w), \cdots, F_m (w)\}$를 normarlize한 것에 대한 entropy로 정의하자. 즉,

$$\tilde{H} (F(w)) := - \sum_{k=1}^m \frac {F_k (w)} {\sum_{k=1}^m F_k (w)} \log \left( \frac {F_k (w)} {\sum_{k=1}^m F_k (w)} \right)$$

일 때, 만약 $\tilde{H} (F(w)) \geq \tilde{H} (F(w'))$이라면, $w'$보다 $w$에서 $m$개의 device들이 가지는 performance distribution이 더욱 uniform하다고 정의한다.

 

 $\text{Definition 1}$에서 "performance"에 해당하는 metric으로는 다양한 것들이 있겠으나, 해당 paper는 test accuracy를 기준으로 삼고 있습니다. 따라서, 별도의 언급이 있지 않는 한, performance $\equiv$ test accuracy로 받아들이시면 됩니다. 또한, $\text{Definition 1}$에 의하여, $\text{Definition 4 ~ 6}$의 "$w'$보다 $w$에서 $m$개의 device들이 가지는 performance distribution이 더욱 uniform하다"를 "$w'$보다 $w$가 더 fair한 solution이다"로 바꾸어 표현하여도 좋습니다. 다음 포스트에서는 위 definition들을 가지고 몇 가지 lemma를 확인해보도록 하겠습니다.