[FL-NeurIPS 2022] Data Maximization - (6)

논문 제목: Mechanisms that Incentivize Data Sharing in Federated Learning

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

 

 지난 포스트까지는 각 client의 cost가 알려져 있는 상황을 가정하고 내용을 전개하였습니다. (이전 글 보기) 이번 포스트에서는 이러한 가정 없이, 즉, cost를 모르는 상황에서 data-maximizing mechanism을 찾는 방법에 관하여 알아보도록 하겠습니다.

 

7. Value Shaping Mechanism (Cost를 모르는 경우)

 

 지금부터는 정보의 비대칭성이 존재합니다. 다시 말해, 각 client $i$는 본인의 cost $c_i$를 알고 있지만, server에서는 이를 알지 못하는 상황입니다. 논의를 간결하게 하기 위하여, cost에는 low-cost $\underline{c}$와 high-cost $\bar{c}$, 이렇게 두 가지 종류만 존재한다고 가정하겠습니다. (이는 충분히 generalization이 가능한 부분입니다.) 그리고 각 client $i$별로 cost가 $\underline{c}$일 확률 $p_i$가 알려져 있다고 가정하겠습니다. (이는 다소 비현실적인 부분입니다.) 그렇다면 자동적으로 $i$의 cost가 $\bar{c}$일 확률은 $1 - p_i$이고, 어찌되었든 $c_i$는 이 둘 중 하나이지만, 여전히 server는 $c_i$에 대하여 알지 못 하는 상황입니다. server가 아는 것은 $c_i$의 distribution이 전부입니다. 이러한 상황에서, 저자들은 다음과 같은 mechanism $\mathcal{M}$을 제안합니다:

 

\begin{equation} [\mathcal{M} (\textbf{m})]_i := \begin{cases} v (m_i) & \text{if $ m_i \leq \bar{m}_i^*$} \\ v(\bar{m}_i^*) + (\bar{c} + \epsilon) (m_i - \bar{m}_i^*) & \text{if $\bar{m}_i^* < m_i \leq m_i^\uparrow$} \\ v(m_i^\downarrow + \sum_{j \neq i} m_j) - (\underline{c} + \epsilon) (m_i^\downarrow - \bar{m}_i) & \text{if $m_i^\uparrow < m_i \leq m_i^\downarrow$} \\ v(\sum_j m_j) & \text{if $m_i > m_i^\downarrow$} \end{cases} \; (\dagger \dagger) \end{equation}

 

 여기에서 $\underline{m}_i^*$는 $c_i = \underline{c}$일 때의 equilibrium이고, $\bar{m}_i^*$는 $c_i = \bar{c}$일 때의 equilibrium입니다. 그리고 $\epsilon > 0$은 임의의 양의 실수입니다. $\text{Theorem 1}$에 의하여 $\underline{c} < \bar{c}$가 $\underline{m}_i^* > \bar{m}_i^*$를 내포하므로, 각 client가 high-cost agent인지 low-cost agent인지 상관 없이 일단 $A$, 즉 $\bar{m}_i^*$까지는 별도의 incentive가 필요하지 않습니다.

 

 다음으로, $\overline{AC}$와 $\overline{CD}$를 살펴보겠습니다. 만약 client $i$가 high-cost agent라면, 즉 $c_i = \bar{c}$라면, $A$ 지점이 이미 equilibrium이기 때문에, 이 이상의 data를 제공하기 위해서는 추가적인 incentive가 요구될 것입니다. 따라서 $m_i^\uparrow$, 즉 $C$까지 추가적인 data를 제공하게 하는 부분이 $\overline{AC}$입니다. 한편, 만약 client $i$가 low-cost agent라면, 즉 $c_i = \underline{c}$라면, 아직까지 추가적인 contribution이 가능한 상황이며, 최대 $m_i^\downarrow$, 즉 $D$까지 incentive를 제공하면서 해당 agent의 참여를 유도할 수 있습니다. 이 이후에는 $v(\sum_j m_j)$를 따라갑니다. (여기에서, $\underline{m}_i^*$가 사용되지 않았다는 점 확인 바랍니다.)

 

 이때, $m_i^\uparrow$과 $m_i^\downarrow$의 값은 data contribution의 기댓값인 $(1 - p_i) m_i^\uparrow + p_i m_i^\downarrow$를 최대화하는 방향으로 지정해주면 되며, 자세한 방법은 다음과 같습니다. 우선, $\Delta m_{-i}$, $\bar{m}^\text{max}$, $\underline{m}^\text{max}$를 각각 다음과 같이 정의합니다:

\begin{align*} \Delta m_{-i} &:= \sum_{j \neq i} m_j \\ v (\bar{m}^\text{max} + \Delta m_{-i}) &= v (\bar{m}^*) + \bar{c} (\bar{m}^\text{max} - \bar{m}^*) \\ v (\underline{m}^\text{max} + \Delta m_{-i}) &= v (\underline{m}^*) + \underline{c} (\underline{m}^\text{max} - \underline{m}^*)\end{align*}

그리고 다음을 만족하는 $D$, 즉 $m_i^\downarrow$ 지점을 찾은 뒤, $\overline{AC}$와 $\overline{CD}$의 교점을 계산하여 $C$, 즉 $m_i^\uparrow$ 지점을 계산합니다.

$$v' (m_i^\downarrow + \Delta m_{-i}) = \min \left\{ \max \left\{ \underline{c} - \frac {p_i} {1 - p_i}  \bar{c}, v' (\underline{m}^\text{max} + \Delta m_{-i}) \right\}, v' (\bar{m}^\text{max} + \Delta m_{-i}) \right\}$$

 

$\text{Theorem 7}$ [Cost가 알려져 있지 않을 때의 Data Maximization]

 

 $(\dagger \dagger)$와 같이 정의된 mechanism $\mathcal{M}$은 feasible하고, $\text{IR}$을 만족하며, 다음과 같은 unique Nash equilibrium를 가진다:

\begin{equation} m_i^\text{eq} := \begin{cases} m_i^\uparrow & \text{if $ c_i = \bar{c}$} \\ m_i^\downarrow & \text{if $c_i = \underline{c}$} \end{cases} \end{equation}

또한, $\mathcal{M}$은 $\epsilon \to 0^+$일 때 data-maximizing이며, 이때 모이는 dataset size의 기댓값은 다음과 같다:

$$\sum_j (1 - p_i) m_j^\uparrow + p_j m_j^\downarrow = \max_\mathcal{M} \left\{ \mathbb{E}_\textbf{c} \left[ m_j^\mathcal{M} \right], \text{ for all the $\mathcal{M}$'s feasible and satisfying IR} \right\}$$

 

$\text{Theorem 8}$ [Information Rent]

 

 $\text{Theorem 7}$과 동일한 setting을 가정하자. 만약 client $i$가 high-cost agent라면, $u_i$는 다음과 같이 변하지 않는다:

$$v(\bar{m^*}) + \bar{c} (m_i^\uparrow - \bar{m}^*) - \bar{c}m_i^\uparrow = v(\bar{m}^*) - \bar{c} \bar{m}^*$$

반면, 만약 client $i$가 low-cost agent라면, $u_i$가 아래의 수치만큼 증가하게 된다:

$$\left( \underline{c} (\underline{m}^\text{max} - m_i^\downarrow) - v (\underline{m}^\text{max} + \Delta m_{-i}) + v(m_i^\downarrow + \Delta {m_{-i}}) \right) \geq 0$$

 

 $\text{Theorem 7, 8}$의 증명은 $\text{Theorem 4, 5}$의 증명과 유사한 방식으로 진행되기 때문에 생략하도록 하고, 대신 위 $\text{Theorem}$들이 의미하는 바를 살펴보겠습니다. 우선, $\text{Theorem 7}$에 의하면, client $i$가 high-cost agent일 때에는 $m_i^\uparrow \in [\bar{m}^*, \bar{m}^\text{max}]$만큼의 기여를 하게 됩니다. 이는 개인적으로 학습할 때의 equilibrium인 $m^*$보다는 분명히 많은 양이지만, 각 client의 cost가 알려져 있는 상황($\text{Theorem 4}$)보다는 적은 양입니다. 즉, 다른 조건들이 모두 동일하다면, 각 client의 cost가 알려져 있지 않은 상황에서는 모이는 총 data의 수가 감소하게 됩니다. 한편, client $i$가 low-cost agent일 때에는 $m_i^\downarrow \in [\bar{m}^\text{max}, \underline{m}^\text{max}]$만큼의 기여를 하게 되는데, 만약 $\underline{c} - \frac {p_i} {1 - p_i} \bar{c} \leq 0$이라면, 즉, $p_i \geq \frac {\underline{c}} {\underline{c} + \bar{c}}$라면, 정의 상 $m_i^\downarrow = \underline{m}^\text{max}$입니다.

 

 이러한 상황 속에서, low-cost agent인 client $i$는 이러한 생각을 할 수도 있습니다: "내가 high-cost agent이면 data contribution을 덜 해도 되는 거네? 내가 low-cost agent인 것은 data 가공에 능숙하기 때문인데, 이 점이 오히려 나에게 불리하게 작용하고 있어. 그러면 나도 high-cost agent인 척을 해야지." 반면, high-cost agent는 low-cost agent인 척을 하는 것이 좋을 리 없기 때문에, 해당 mechanism에서 별다른 힘을 갖지 못하게 됩니다. $\text{Theorem 8}$은 이러한 low-cost agent의 우위 때문에 발생하는 extra utility에 관하여 설명하고 있으며, 이를 "information rent"라고 저자들은 부르고 있습니다. (이에 대한 명확한 설명은 없지만, data를 더 많이 제공하는 사람의 입장에서 갖게 되는 효용이기 때문에 이렇게 이름을 붙인 것이 아닌가 생각됩니다.)

 

8. 의의 및 한계

 

 합리적인 개인은 FL에 참여하지 않는 것이 본인에게 더 도움이 된다는 생각 하에 data를 제공하지 않는 free-rider가 될 수도 있는데, FL을 수행하는 과정을 적절하게 design함으로써 이러한 client를 FL에 참여하도록 유도할 수 있다는 것을 보여주었다는 점에서 해당 논문은 의의를 갖습니다. 또한, 이러한 동기 부여 과정에서 더욱 많은, 또 다양한 data를 모을 수 있다는 것 역시 큰 이점입니다. 이러한 mechanism 구성은 단순히 전체 client 중 일부를 sampling한 후, 그중 straggler를 제외한 client들의 학습 결과를 가지고 global model을 update하는 기존의 방식과는 분명히 차별점이 존재합니다. 또한, game theory를 이용하여 내용을 전개하였음에도 nash equilibrium이 unique하다는 점을 보임으로써 randomness로부터 다소 자유로워졌다는 점 역시 해당 논문의 강점이라고 볼 수 있습니다.

 

 다만, 개선하여야 하는 부분 역시 존재하였습니다. 해당 논문은 저자들이 제안한 mechanism이 data-maximizing하다는 것을 보여주었지만, 이러한 mechanism이 그것 하나뿐임을 보이지는 않은 상황입니다. (각 mechanism마다의 nash equilibrium이 유일하다는 것이지, data-maximizing mechanism이 유일하다는 이야기는 다루어지지 않았습니다.) 따라서 또 다른 형태의 data-maximizing mechanism도 충분히 존재할 수 있으며, 이 점은 후속 연구에서 계속해서 다루어질 필요가 있어 보입니다. 또한, 각 client의 cost에 대한 distribution을 알고 있다는 가정 역시 다소 강한 편이므로, 추후 이 가정을 완화하기 위한 방법에 관한 고민도 필요하다고 생각되는데, 이 경우 모이는 data의 수가 더욱 줄어들게 될 것이라고 추측할 수 있습니다. 따라서 이 문제의 경우, 해당 논문과는 조금 다른 방식의 접근이 필요해 보입니다.