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

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

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

 

 지난 포스트에서 data-maximizing mechanism의 정의를 알아보고, 저자들이 제안하는 mechanism은 어떠한 방식으로 동작하는지 확인하였습니다. (이전 글 보기) 이번 포스트에서는 해당 mechanism이 data-maximizing하다는 것을 보이도록 하겠습니다.

 

5. Value Shaping Mechanism (Cost를 아는 경우) - 이어서

 

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

 

 임의의 $\epsilon > 0$에 대해서, mechanism $\mathcal{M}$을 다음과 같이 정의하자:

$$\begin{equation} [\mathcal{M} (\textbf{m})]_i := \begin{cases} v (m_i) & \text{if $ m_i \leq m_i^*$} \\ v(m_i^*) + (c_i + \epsilon) (m_i - m_i^*) & \text{if $m_i^* < m_i \leq m_i^\text{max}$} \\ v(\sum_j m_j) & \text{if $m_i > m_i^\text{max}$} \end{cases} \end{equation}$$

$\epsilon \to 0^+$일 때, $\mathcal{M}$은 data-maximizing이다. 또한, 해당 mechanism의 equilibirum에서는 각 rational client $i$가 $m_i^\text{max}(\geq m_i^*)$만큼 기여하여, 총 $\sum_j m_j^\text{max}$만큼의 데이터가 확보된다.

 

$\text{Proof}$

 임의의 feasible하고 $\text{IR}$을 만족하는 mechanism $\tilde{\mathcal{M}}$이 존재한다고 가정하자. 그러면 앞서 증명한 $\text{Lemma 8}$에 의하여, 임의의 client $i$와 data contribution $\textbf{m}$에 대하여 $[B_\mathcal{M} (\textbf{m})]_i \geq [B_\tilde{\mathcal{M}}(\textbf{m})]_i$이다. 또한, $\text{Theorem 2}$에 의하여 $\mathcal{M}$과 $\tilde{\mathcal{M}}$ 모두 $\mathcal{C} := \prod_i \left[ 0, \frac {1} {c_i} \right]$ 안에 equilibrium이 존재한다.

 

 이러한 상황에서, $\tilde{\textbf{m}}$을 $\tilde{\mathcal{M}}$의 equilibrium이라고 가정하자. 그러면 정의 상 $\tilde{\textbf{m}} \in B_\tilde{\mathcal{M}} (\tilde{m})$이다. 그리고 다음과 같은 subspace를 정의하자:

$$\mathcal{C}_{\geq \tilde{\textbf{m}}} := \prod_j \left[ \tilde{\textbf{m}}_j,  \frac {1} {c_j} \right]$$

이때, $\mathcal{C}_{\geq \tilde{\textbf{m}}}$는 compact, convex하므로, $\text{Theorem 2}$에 의하여 equilibrium point $\textbf{m}$이 $\mathcal{C}_{\geq \tilde{\textbf{m}}}$ 안에 존재한다는 것이 보장된다. 즉, 다음이 성립한다:

$$[\textbf{m}]_i \in \text{argmax}_{m_i \geq \tilde{m}_i} \{ [\mathcal{M} (\tilde{m}_i, \mathbb{m})]_i - c_i \tilde{m}_i \}$$

여기에서 $m_i \geq \tilde{m}_i$를 $m_i > 0$으로 확장하여, 다음이 성립한다는 것을 보이려고 한다:

$$\textbf{m} \in [B_\mathcal{M} (\textbf{m})], \text{ where } [B_\mathcal{M} (\textbf{m})]_i := \text{argmax}_{m_i \geq 0} \{ [\mathcal{M} (\tilde{m}_i, \mathbb{m})]_i - c_i \tilde{m}_i \}$$

 

---

$\text{Claim}$: $\textbf{m} \in B_\mathcal{M} (\textbf{m})$

 

$\text{Proof}$

 귀류법을 사용하여 증명하자. 즉, $\textbf{m}_i \notin [B (\textbf{m})]_i$이고, 따라서 $[B_\mathcal{M} (\textbf{m})]_i < \tilde{\textbf{m}}_i$인 client $i$가 존재한다고 가정하자. 이때, $\textbf{m} \in \mathcal{C}_{\geq \textbf{m}}$d이므로 $\sum_{j \neq i} \textbf{m}_j \geq \sum_{j \neq i}$이고,  $\text{Lemma 8}$에 의하여 다음이 성립한다:

$$[B_\mathcal{M} (\textbf{m})]_i \geq [B_\mathcal{M} (\tilde{\textbf{m}})]_i \geq [B_\tilde{\mathcal{M}} (\tilde{\textbf{m}})]_i = \tilde{\textbf{m}}_i \; (\because \tilde{\textbf{m}} \in B_\tilde{\mathcal{M}})$$

이는 $[B_\mathcal{M} (\textbf{m})]_i < \tilde{\textbf{m}}_i$라는 가정에 모순된다. $\textbf{↯}$ 따라서, $\textbf{m} \in B_\mathcal{M} (\textbf{m})$이다. $\square$

---

 즉, 앞서 발견한 $\textbf{m} \in \mathcal{C}_{\geq \tilde{\textbf{m}}}$이 곧 $\mathcal{M}$의 equilibrium이며, 이때의contribution은 적어도 $\tilde{\mathcal{M}}$의 equilibrium에서의 contribution 이상임을 알 수 있다. 따라서, 정의 상 $\mathcal{M}$은 data-maximizing mechanism이다. $\square$

 

 해당 증명에서 $\epsilon \to 0^+$이라는 조건을 사용하지 않았는데, 이는 아래의 $\text{Theorem 5}$에 등장해야 하는 것이 잘못 작성된 것으로 보입니다. 임의의 $\epsilon > 0$에 대해서 $\mathcal{M}$은 data-maximizing한 mechanism입니다.

 

$\text{Theorem 5}$ [Incentive Compatibility]

 

 각 client $i$의 cost $c_i$를 알고 있는 상황 하에 $\text{Theorem 4}$에서 정의된 mechanism $\mathcal{M}$을 사용한다고 가정하자. 이때, 각 client $i$의 utility $u_i$는 변하지 않는다. 즉, 다음 식이 성립한다:

$$v (\sum_j m_j^\text{max}) - c_i m_i^\text{max} = v(m_i^*) - c_i m_i^*$$

 

$\text{Proof}$

임의의 $m_i \in (m_i^*, m_i^\text{max}]$에 대하여, 다음이 성립한다: $$u_i' (m_i; \mathcal{M}) = \frac {\partial [\mathcal{M}]_i} {\partial m_i} - c_i = c_i + \epsilon - c_i = \epsilon \to 0$$ 이는 곧 $m_i = m_i^*$ 이후로 해당 구간 내에서 marginal utility가 계속해서 변하지 않는다는 것을 의미한다. $\square$

 

 $\text{Theorem 4}$을 통해서, 우리는 data-maximizing mechanism $\mathcal{M}$을 design하는 방법을 알게 되었습니다. 그렇다면, $\mathcal{M}$은 단순히 "더 많은 데이터를 모으게 해준다"는 것 외에 어떠한 이점을 가지고 있을까요? $\text{Lemma 8}$에 의하면, $\mathcal{M}$에서는 모든 client $i$가 $m_i^*$ 이상의 양인 $m_i^\text{max}$만큼의 기여를 하게 됩니다. 즉, 정의 상 $\sum_j m_j^\text{max}$의 크기를 가지는 dataset이 생긴다는 이점도 존재하지만, 기여하지 않는 client, 즉 free-rider가 발생하지 않는다는 점 역시 해당 data-maximizing mechanism의 장점이라고 볼 수 있습니다. 또한, 이들이 추가적인 data를 제공함에도 utility가 감소하지 않는다는 것이 $\text{Theorem 5}$에 의해서 보장되고 있고, 이 역시 해당 방법론이 매력적인 선택지인 이유 중 하나입니다.

 

 지금부터는 논의를 간략하게 하기 위하여 모든 client의 cost가 $c$로 동일하다고 가정하겠습니다. 그렇다면 총 $n m^\text{max}$의 data가 모이게 되는데, client의 수가 많아지면 참여에 대한 incentive가 커질 것이므로 $m^\text{max}$ 역시 $n$에 dependent하다고 볼 수 있습니다. 하지만 incentive가 무한정으로 커질 수는 없는데, 왜냐하면 $v(\cdot)$는 $1$보다 큰 값을 가질 수 없기 때문입니다. 따라서 $m^\text{max}$의 크기는 $v(m^*) + c (m^\text{max} - m^*) = 1$을 만족할 때에 최대가 될 것입니다. 다시 말해, $\left[ nm^*, n \left( m^* + \frac {1 - v(m^*)} {c} \right) \right]$ 안에서 total dataset의 크기가 결정된다고 이야기할 수 있습니다. 그리고 편의 상 이를 $m^\text{total} := nm^\text{max}$로 표기하겠습니다.

 

 만약 $m^* = 0$이라면, 즉, 어떠한 client도 개인적으로는 주어진 문제를 해결할 수 없는 경우라면, 기존의 방식(standard federated learning mechanism)대로는 FL을 이용하더라도 해결할 수 없을 것입니다. 하지만 $\mathcal{M}$을 채택한 상황에서는 $m^\text{total} > 0$일 수도 있으며, 이것이 저자들이 원하는 상황입니다. 그럼에도 $m^\text{total} = 0$ 역시 가능한 경우이며, 저자들은 만약 이러한 상황이 발생한다면 "platform 운영자가 스스로 mechanism에 참여함으로써 client들의 참여를 유도"할 것을 제안합니다.

 

 6. Experiments

 

 위 그래프는 data-maximizing mechanism $\mathcal{M}$에 기반하여 FL을 수행하였을 때의 결과를 비교한 것입니다. (여기에서, $k$는 문제가 얼마나 어려운지를 나타내며, 모든 client가 동일한 cost를 가진다는 가정 하에 실험을 진행하였습니다. 또한, 모든 client $i$에 대하여 $m_i^* = 0$입니다.) 우선 $(a)$를 보면, FL에 참여하는 client가 많아질수록 비교적 선형적으로 data도 더 많이 모인다는 것을 확인할 수 있습니다. 이때, $k$에 따라 data가 모이기 시작하는 지점이 달라지는데, 이는 우리의 직관에 충분히 부합하는 부분입니다.

 

 다음으로, $(b)$는 cost가 커질수록 모이는 data의 수가 적어지는 모습을 보여줍니다. 이 역시 비교적 선형적인 관계를 보이고 있으며, 더 쉬운 문제일수록 cost에 조금 더 관대하다는 것 또한 포착할 수 있습니다.

 

 마지막으로, $(c)$는 client가 최소한 얼마나 모여야 $m_i^\text{max} > 0$을 만족하여 정상적으로 FL이 작동하는지를 보여주고 있습니다. cost가 클수록, 또 문제가 어려울수록 client가 더 많이 필요하다는 것 역시 우리의 직관에 충분히 부합하며, 이 부분도 마찬가지로 비교적 선형적인 관계를 보인다는 것을 알 수 있습니다.

 

 지금까지는 각 client 별로 cost가 알려져 있다고 가정한 상태에서 이야기를 전개하였는데, 다음 포스트에서는 cost를 모르는 상황에서 어떻게 mechanism을 design하여야 할지에 관하여 알아보도록 하겠습니다.