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

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

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

 

 지난 포스트에서 이상적인 FL mechanism이 만족해야 하는 조건에 관하여 알아본 뒤, 그러한 이상적인 상황에서는 반드시 Nash Equilibrium이 존재한다는 것을 확인하였습니다. (이전 글 보기) 이번 포스트에서는 free-riding에 관하여 살펴보도록 하겠습니다.

 

4. Free-Riding

 

 만약 모든 client로부터 학습된 결과를 받는다면, 이러한 mechanism $\mathcal{M}$은 $\left[ \mathcal{M} (\textbf{m}) \right]_i = v (\sum_j m_j)$으로 표현될 것입니다. 지금부터 이처럼 정의된 mechanism $\mathcal{M}$을 standard federated learning mechanism이라고 지칭하겠습니다. 이 mechanism은 정의 상 자명하게 feasiable하고, 또 $\text{IR}$을 만족합니다. 그러므로, 이전 포스트에서 살펴보았듯이 $\mathcal{M}$이 Nash Equilibrium을 갖는다는 것이 보장됩니다.  하지만 그렇다고 해서 해당 mechanism을 그대로 사용하는 것은 적절하지 못할 수 있습니다. 이에 관한 단적인 예시가 아래의 $\text{Theorem 3}$입니다.

 

$\text{Theorem 3}$ [Catastrophic Free-Riding]

 

 $n$개의 client가 FL에 참여하는 상황에서, 각 client의 cost를 $c_i$로, 각 client가 각자 학습을 수행할 때의 equilibrium contribution을 $m_i^*$로 표기하자. 그리고 $c_\text{min} := \min_i c_i$값을 cost로 갖는 client $\tilde{i}$는 unique하다고 가정하자. 이때, 만약 모든 client $i \in [n]$가 standard federated learning mechanism $\left[ \mathcal{M} (\textbf{m}) \right]_i = v (\sum_j m_j)$을 수행한다면, equilibrium은 다음과 같이 형성된다(즉, client $\tilde{i}$ 한 명만 $\mathcal{M}$에 기여한다):

\begin{equation} m_i^\text{eq}:= \begin{cases} m_i^* & \text{if $c_i = c_\text{min}$}\\ 0 & \text{otherwise} \end{cases} \end{equation}

 

$\text{Proof}$

 $\text{Theorem 1}$에 의하여, 임의의 $j \in [n]$에 대하여 $m_j^* \leq m_\tilde{i}^*$임을 알 수 있다. 여기에서 만약 $m_\tilde{i}^* = 0$이라면, 임의의 $i \in [n]$에 대하여 $m_i^* = 0$이다. 따라서 어떠한 client도 $\mathcal{M}$에 기여를 할 이유가 없고, 결국 $\textbf{m} = \textbf{0}$에서 equilibrium이 형성된다. 한편, 만약 $m_\tilde{i} > 0$이라면, $\tilde{i}$가 $m_\tilde{i}^*$만큼의 data를 기여할 것이고, 다른 모든 client들은 $m_\tilde{i}^*$만큼 학습된 결과에 접근할 수 있게 된다. 이 지점에서는 $b' (m_\tilde{i}^*) = c_\tilde{i}$이고, 가정 상 임의의 $j \in [n]$에 대하여 $c_\tilde{i} = c_\text{min} < c_j$이므로, 다른 client $j$들은 굳이 학습 과정에 추가적인 data를 기여하지 않는 것이 합리적인 행위이다. 그러므로 client $\tilde{i}$ 한 명만 $\mathcal{M}$에 기여하게 된다고 결론을 내릴 수 있다. $\square$

 

 처음에 이야기하였듯이, 만약 본인이 Low-cost Agent여서 혼자서 문제를 해결하는 것이 가능하다면, 굳이 주어진 FL mechanism에 기여할 필요 없이 스스로 학습을 진행하면 됩니다. 다만, 우리가 상정한 standard federated learning mechanism은 feasiable한 동시에 $\text{IR}$을 만족하기 때문에, 이러한 client는 존재하지 않습니다. 만일 주어진 FL mechanism에 기여하지 않은 client가 존재한다면, 그 이유는 해당 client가 스스로 문제를 해결할 수도 없으며, 이와 동시에 해당 client가 주어진 mechanism에 기여한다고 해서 그 client가 얻을 수 있는 효용이 증가하지 않기 때문입니다. 만약 해당 client가 rational하다면, 그저 다른 client의 데이터에 기반하여 학습된 결과물만을 가져다 쓰면 된다는 결론에 도달한다는 이야기입니다. 그리고 모두가 이와 같이 행동한다면, $\text{Theorem 3}$과 같은 극단적인 결과를 초래할 수도 있습니다.

 

 이러한 점을 미루어 보았을 때, $\text{Theorem 3}$이 주는 또 하나의 교훈은 다음과 같습니다: 만일 모든 client가 전혀 $\mathcal{M}$에 기여하지 않았다면, 즉, $\textbf{m} = \textbf{0}$에서 equilibrium이 형성되었다면, 이는 우리가 해결하고자 하는 문제가 너무나도 어려웠거나, 혹은 모든 $i$에 대하여 $c_i$가 지나치게 컸기 때문일 것입니다. 다시 말해, standard federated learning mechanism으로는 (여러 client가 합심하더라도) 개개인이 해결하기 어려운 문제를 해결하기 어렵다는 이야기입니다. 이는 "어차피 다른 client도 기여를 포기하고 free-riding을 하지 않을까"라는 생각을 모든 client들이 가지고 있었다고 이해하면 좋을 것입니다.

 

 그렇다면, free-riding을 방지하기 위해서는 어떠한 방식으로 mechanism을 구성해야 할까요? 다음 포스트부터 이에 관련된 이야기를 다루어보겠습니다. 우선, 모든 client의 cost가 공개된 상황(crowd sourcing 등)에서 내용을 전개한 뒤, cost를 알지 못하는 경우(일반적인 FL 상황)를 살펴볼 계획입니다.