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

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

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

 

 지난 포스트에서 free-riding에 관한 이야기를 다루면서, standard federated learning mechanism은 free-riding을 막기 어렵다는 것을 확인하였습니다. (이전 글 보기) 이번 포스트에서는 free-riding을 방지할 수 있는 방안에 관하여 살펴보도록 하겠습니다.

 

5. Value Shaping Mechanism (Cost를 아는 경우)

 

$\text{Definition C}$ [Data Maximization]

 

 임의의 mechanism $\mathcal{M}$에 대하여, 해당 mechanism의 equilibrium에 해당하는 지점에서 요구되는 data의 수를 $\textbf{m}^\text{eq} (\mathcal{M})$으로 표기하자. 이때, 만약 임의의 feasible하고 $\text{IR}$을 만족하는 mechanism $\mathcal{M}$에 대하여 $\hat{\mathcal{M}} \in \text{argmax}_\mathcal{M} \sum_j \left[ m^\text{eq} (\mathcal{M}) \right]_j$를 만족하는 mechanism $\hat{\mathcal{M}}$가 존재한다면, 이를 data-maximizing mechanism이라고 정의한다.

 

 위 정의를 풀어서 생각해보면, 어떠한 mechanism이 data-maximizing이라는 것은 곧 equilibrium을 기준으로 해당 mechanism이 가장 많은 data를 모을 수 있다는 것을 의미합니다. data-maximizing mechanism에 해당하는 mechanism으로는 다양한 것들이 존재하겠으나, 저자들이 제안하는 mechanism $\mathcal{M}$은, 충분히 작은 $\epsilon > 0$에 대하여, 다음과 같습니다:

$$\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}$} & (\dagger) \\ v(\sum_j m_j) & \text{if $m_i > m_i^\text{max}$} \end{cases} \end{equation}$$

 

 여기에서, 각 agent $i$의 cost $c_i$는 알려져 있는 상황이라고 가정하고, $m_i^\text{max}$는 아래의 식을 만족합니다:

$$v (m_i^\text{max} + \sum_{j \neq i} m_j) = v(m_i^*) + (c_i + \epsilon) (m_i - m_i^*)$$

 오른쪽 그래프가 이러한 $\mathcal{M}$을 잘 표현하고 있습니다. (첫 포스트에서 설명하였듯이, 그래프의 $a (\cdot)$은 $v (\cdot)$입니다.) $A$ 지점 이전까지는 빨간 선을 따라가는데, 이는 오직 본인의 데이터만으로 학습을 진행하는 구간입니다. 그러다가 $A$ 지점부터 $B$ 지점까지는 직선으로 이동하는데, 이는 $A$ 지점 이후로 FL에 참여하는 것보다 개인적인 학습 과정을 진행하는 것이 더 적은 marginal utility를 주기 때문입니다. 즉, $A$ 지점에서 $B$ 지점 사이가 해당 client $i$에게 동기가 부여되는 구간입니다. 하지만, 이러한 동기 부여가 한없이 지속되지는 못합니다. $B$ 지점 이후로 client $i$는 더 이상 data generation을 하지 않을 것이고, 따라서 FL의 학습 결과를 그대로 받아들일 것입니다.

 

 이와 같이 mechanism을 design할 경우, 이전 포스트에서 살펴본 free-riding이 발생하기 어려울 것입니다. 다만, 이러한 mechanism $\mathcal{M}$이 실제로 data-maximizing한지에 관해서는 별도의 증명 과정이 필요합니다.

 

※ 주의 사항: feasible하고 $\text{IR}$을 만족하는 mechanism 중에서 data-maxinizing인 것을 찾는 것이기 때문에, 어떠한 mechanism이 data-maxinizing하다는 이야기는 해당 mechanism이 feasible하고 $\text{IR}$을 만족한다는 의미를 내포합니다. 즉, 우리는 해당 mechanism이 feasible한지, 또 $\text{IR}$을 만족하는지에 관하여 증명할 필요가 없습니다. 저자들이 data-maxinizing mechanism에 동일하게 $\mathcal{M}$ notation을 사용해버린 관계로 다소 혼동의 여지가 있는데, 해당 paper가 journal이나 conference에 게재될 때에는 notation 수정이 어느 정도 필요해보입니다.

 

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

 

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

 

 해당 $\text{Theorem}$을 증명하기 위해서는, 아래의 $\text{Lemma 8}$이 필요합니다. 우선 이 $\text{Lemma}$를 증명한 후, 다음 포스트에서 $\text{Theorem 4}$의 증명 과정을 살펴보도록 하겠습니다. 두 정리 모두 귀류법(proof by contradiction)에 의존하여 증명되기 때문에, 증명 과정이 다소 복잡해졌다는 점 참고 바랍니다.

 

$\text{Lemma 8}$

 

 $(\dagger)$와 같이 정의된 mechanism $\mathcal{M}$과 임의의 feasible하고 $\text{IR}$을 만족하는 mechanism $\tilde{\mathcal{M}}$에 대하여, 각각의 best response를 $B_\mathcal{M}$, $B_\tilde{\mathcal{M}}$ 로 표기하자. 이때, 임의의 client $i$와  data contribution $\textbf{m}$에 대해서 $[B_\mathcal{M} (\textbf{m})]_i \geq [B_\tilde{\mathcal{M}}(\textbf{m})]_i$이다.  더 나아가, $B_\mathcal{M}$은 $\sum_{j \neq i} m_j$에 대하여 non-decreasing이다.

 

$\text{Proof}$

 우선, $i$가 Low-cost Agent인 경우, 즉, $m_i^* > 0$인 경우부터 살펴보자. $\text{Theorem 1}$의 증명 과정에서 살펴보았듯이, 이 경우에는 $v' (m_i^*) = b'(m_i^*) = c_i$이다. 그리고 정의 상 $u'_i (m_i; \mathcal{M}) = \frac {\partial [\mathcal{M} (\textbf{m})]_i} {\partial m_i} - c_i$이며, 임의의 $m_i < m_i^\text{max}$에 대해서 $u'_i (m_i; \mathcal{M}) > 0$이다.

---

$\text{Claim}$: $m_i^\text{max}$는 client $i$의 unique equilibrium contribution이다.

 

$\text{Proof}$

 $i$를 제외한 client들의 기여 정도를 $\Delta m_{-i} := \sum_{j \neq i} m_j$로 표기하고, 임의의 $\Delta m_{-i}$ 값이 주어졌다고 가정하자. 그러면 $m_i^\text{max}$에서의 marginal utility는 $u'_i (m_i^\text{max}; \mathcal{M}) = v' (m_i^\text{max} + \Delta m_{-i}) - c_i$이다. 이떄, 정의 상 $m_i^\text{max} + \Delta m_{-i} \geq m_i^*$이고, $b(\cdot)$는 continuous, non-decreasing, concave하므로, 다음이 성립한다:

$$u'_i (m_i^\text{max}; \mathcal{M}) = v' (m_i^\text{max} + \Delta m_{-i}) - c_i = b' (m_i^\text{max} + \Delta m_{-i}) - c_i \leq b' (m_i^*) - c_i = 0$$

따라서, $m_i^\text{max}$가 client $i$의 unique equilibrium contribution이다. $\square$

---

 지금부터는 귀류법을 사용하여 $[B_\mathcal{M} (\textbf{m})]_i \geq [B_\tilde{\mathcal{M}}(\textbf{m})]_i$임을 보일 것이다. 우선, 다음을 만족시키는 mechanism $\tilde{\mathcal{M}}$이 존재한다고 가정하자:

$$\tilde{m}_i := \text{argmax}_{m_i} \left( [\tilde{\mathcal{M}} (\textbf{m})]_i - c_i m_i \right) > m_i^\text{max}$$

이는 곧 임의의 $m_i \leq \tilde{m}_i$에 대해서 $u'_i (m_i ; \tilde{\mathcal{M}}) > 0$임을 의미하고, 따라서 $\frac {\partial [\tilde{\mathcal{M}} (\textbf{m})]_i} {\partial m_i} > c_i$이다. 더 나아가, $\tilde{m}_i > m_i^\text{max}$라는 것은 곧 임의의 $m_i \in (m_i^*, m_i^\text{max}]$에 대해서 $\frac {\partial [\tilde{\mathcal{M}} (\textbf{m})]_i} {\partial m_i} > \frac {\partial [\mathcal{M} (\textbf{m})]_i} {\partial m_i}$임을 의미한다. $(1)$ 또한, 가정 상 $\tilde{\mathcal{M}}$은 $\text{IR}$을 만족하기 때문에, 다음이 성립한다:

$$[\tilde{\mathcal{M}} (m_i^*, \textbf{m}_{-i})]_i \geq v(m_i^*) = [\mathcal{M} (m_i^*, \textbf{m}_{-i})]_i \quad (2)$$

이때, $(1)$과 $(2)$를 종합하면, 임의의 $m_i \in (m_i^*, m_i^\text{max})$에 대하여 $[\tilde{\mathcal{M}} (\textbf{m})]_i > [\mathcal{M} (\textbf{m})]_i$임을 알 수 있는데, 이는 feasible하다는 $\tilde{\mathcal{M}}$의 가정을 위배한다. 왜냐하면, $[\tilde{\mathcal{M}} (m_i^\text{max}, \textbf{m}_{-i})]_i > [\mathcal{M} (m_i^\text{max}, \textbf{m}_{-i})]_i  = v (\sum_j m_j)$이기 때문이다. $\textbf{↯}$

 따라서, 임의의 feasible하고 $\text{IR}$을 만족하는 mechanism $\tilde{\mathcal{M}}$에 대하여, $[B_\mathcal{M} (\textbf{m})]_i \geq [B_\tilde{\mathcal{M}}(\textbf{m})]_i$이다.

 

 $i$가 Mid-cost 혹은 High-cost Agent인 경우, 즉, $m_i^* = 0$인 경우도 위와 유사한 방식으로 증명 가능하고, $B_\mathcal{M}$이 $\sum_{j \neq i} m_j$에 대하여 non-decreasing인 점은 정의 상 자명하므로, 이후의 증명 과정은 생략한다. $\square$

 

 다음 포스트에서는 $\text{Theorem 4}$의 증명 과정을 살펴본 후, 해당 $\text{Theorem}$이 갖는 의미에 관하여 알아보도록 하겠습니다. 또한, 여유가 된다면 간단한 experiments도 함께 확인할 계획입니다.