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

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

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

 

 예전에 Agnostic FL을 다루면서 Contribution Evaluation 분야를 잠깐 언급한 적이 있었는데, 이번에는 이 부분에 대해서 이야기를 해보려고 합니다. (이전 글 보기) 이성적인 client라면, "굳이 내가 나의 data를 제공하지 않아도, 충분히 (다른 사람들의 data에 기반하여) 잘 학습된 model을 받아와서 쓸 수 있잖아?"라는 생각을 할 수도 있습니다. 한두 사람만 이러한 생각을 한다면 다행이지만, 만약 다수의 client가 비슷한 생각을 한다면, 결국 model은 올바른 방향으로 학습되지 못할 것입니다. 이러한 "free-rider"들을 어떻게 해결할 것인지에 관하여 지금부터 확인해봅시다.

 

※ 주의 사항: 초보적인 수준의 경제학 혹은 게임이론 지식이 요구될 수 있습니다.

※ 주의 사항: Workshop Paper입니다.

 

1. Data의 Value와 Cost

 

 다수의 client로부터 만들어진 Dataset $\mathcal{D}$에 대해서, $m : = |\mathcal{D}|$로, value function $v$를 $v(\mathcal{D}): 2^{\mathcal{D}} \rightarrow [0, 1]$로 정의합시다. (여기에서, value는 test accuracy입니다. 즉, $\mathcal{D}$의 각 subset $\mathcal{D}_k \subset \mathcal{D} \; (k = 1, 2, \cdots, 2^m)$에 대해서 test accuracy를 매기는 함수가 $v(\mathcal{D})$인 것입니다.) 이때, 편의 상 $m \in \mathbb{Z}_{\geq 0}$가 아니라 $m \in \mathbb{R}_{\geq 0}$로 정의한다면(즉, Dataset의 크기가 continuous하게 변화한다면), value function $v$를 다음과 같이 고쳐 쓸 수 있습니다:

$$v(m) : \mathbb{R}_{\geq 0} \rightarrow [0, 1], \; m \mapsto \max \{ 0, b(m) \}, \text{ where  $b$ is continuous, non-decreasing and concave.}$$

(직관적으로 보았을 때, data의 수가 많아지면 test accuracy가 점차 높아지겠지만, marginal한 accuracy의 향상 정도는 data가 추가될 때마다 줄어들 것입니다. 이러한 부분을 반영한 것이 $b (\cdot)$입니다.) 그리고 $v(0) = 0$, $\lim_{m \rightarrow \infty} v(m) > 0$을 가정합니다. 그러면, 결국 우리가 FL에서 원하는 것은 각 client들이 잘 협력하여 $v (\mathcal{D})$를 maximize하는 것입니다.

 

 다만, data가 공짜로 얻어지지는 않습니다. model을 학습시키기 위해서 dataset을 구성할 때에는 data를 일정한 형태로 가공할 필요가 있고, 여기에는 (직접 할 경우에는) 시간 혹은 (다른 사람에게 맡길 경우에는) 돈이 수반됩니다. 지금부터는 이를 아울러서 cost라고 표현하겠습니다. 그리고 각 client $i$가 1개의 추가적인 data를 만들 때 소요되는 cost를 $c_i$로 정의하겠습니다. (marginal cost를 상수로 정의한 것이 직관에서 크게 벗어나지는 않습니다만, 원한다면 $c_i$도 어떠한 함수의 형태로 표현 가능할 것입니다.) 즉, client $i$가 $m$개의 data를 생성하는 데에 요구되는 cost는 $cost_i (m) := c_i m$입니다. 당연히 cost는 적을수록 좋은 것이므로, $cost_i (m)$를 minimize하는 것 역시 우리가 관심가져야 할 부분입니다. (cost가 너무 크다면, free-riding을 하려는 사람이 늘어날 것입니다.) 즉, 다시 정리하면 우리의 목표는 각 client $i$ 별로 net utility $u_i (m) := v(m) - c_i m$을 maximize하는 것입니다.

 

(해당 paper에서 $a(\cdot)$와 $v(\cdot)$가 계속해서 혼용되고 있는데, 저는 value의 의미를 살려서 $v(\cdot)$로 통일하겠습니다. 즉, 위 그래프의 $a(m)$은 $v(m)$이고, $u_i (m) = a (m) - c_i (m)$입니다.)

 

$\text{Theorem 1}$ [Optimal Individual Generation]

 

 data point 당 marginal cost $c_i$, value function $v(\cdot)$을 가지고 있는 client $i$가 연합 없이 혼자서 학습을 수행한다고 가정하자. (즉, $u_i (m_i) = v(m_i) - c_i m_i$이다.) 이때, dataset의 optimal한 크기 $m_i^*$는 다음과 같다:

\begin{equation} m_i^* = \begin{cases} 0 & \text{if $ \max_{m_i \geq 0} u_i (m_i) \leq 0$}\\ \alpha_i^*, \text{ where } b' (\alpha_i^*) = c_i & \text{elsewhere} \end{cases} \end{equation}

더 나아가, 임의의 두 clients $i, j$에 대해서, 만약 $c_i \leq c_j$라면, $u_i (m_i^*) \geq u_j (m_j^*)$이고, $m_i^* \geq m_j^*$이다.

 

$\text{Proof}$

 $m^0 := \text{argmax}_m \{ v(m) = 0\} $라고 정의하자. (다시 말해, $m^0$까지는 dataset의 size를 아무리 키워도 value가 $0$이다.) 그러면 $v(\cdot)$의 정의 상, 임의의 $m_i > m^0$에 대해서 $v(m_i) = b(m_i) > 0$이다. 또한, $u_i (m_i) = v(m_i) - c_i m_i$의 양변을 $m_i$에 대해서 미분하면  $u'_i (m_i) = v'(m_i) - c_i$를 얻을 수 있는데, 가정에 의하여 $b(\cdot)$는 concave하므로, 임의의 $m_i \leq m^0$에 대해서 $b' (m_i)$는 (그리고 곧 $u'_i (m_i)$는) $m_i = m^0$인 지점에서 최대값을 갖는다.

 

 지금부터는 $\text{Case}$를 총 세 가지로 나누어 살펴볼 것이다.

 

$\text{Case 1}$ [High-cost Agent] ($u'_i (m^0) \leq 0$, 위 그래프 중 $(d)$에 해당)

 이 경우에는, $b(\cdot)$가 가정 상 concave하므로, 임의의 $m_i > m^0$에 대해서 $u'_i (m_i) \leq u'_i (m^0) \leq 0$이다. 그리고 임의의 $0 \geq m_i \geq m^0$에 대해서는 $u'_i (m_i) = -c_i \leq 0$이다. 즉, 모든 $m_i \geq 0$에 대하여 $u'_i (m_i) \leq 0$이고, 이는 곧 $u_i (m_i)$가 non-increasing함을 의미한다.

 

$\text{Case 2}$ [Mid-cost Agent] ($u'_i (m^0) > 0 \text{ and } \max_{m_i} u_i (m_i) \leq 0 $, 위 그래프 중 $(c)$에 해당)

 이 경우에는, $u'_i (m^0) > 0$이므로 $b'(m^0) > c_i$이다. 그리고  $b(\cdot)$가 가정 상 concave하므로, 임의의 $m_i > m^0$에 대해서 $u_i' (m_i) = b' (m_i) - c_i < b' (m^0) - c_i = u_i' (m^0)$이다. 즉, $u'_i (m^0) > 0$인 상태에서 시작하다가 어느 순간 marginal utility가 증가하지 않는 지점에 도달하게 되고, 그 이후에는 오히려 marginal utility가 감소하기 시작한다. 그러므로, $\max_{m_i \geq 0} u_i (m_i) \leq 0$인 상황에서는 marginal utility가 증가하지 않는 지점에서도 utility가 $0$ 이하라는 의미이기에, $m_i^* = 0$이다.

 

$\text{Case 3}$ [Low-cost Agent] ($u'_i (m^0) > 0 \text{ and } \max_{m_i} u_i (m_i) > 0 $, 위 그래프 중 $(b)$에 해당)

 한편, 이 경우는 위의 $\text{Case 2}$와는 달리 $\max_{m_i} u_i (m_i) > 0$이므로, $u_i (m_i) > 0$를 만족하는 $m_i > m^0$가 존재한다. 그리고 그러한 $m_i$들 중 가장 높은 utility를 보여주는 $m_i^*$는 marginal utility가 증가하거나 감소하지 않는 지점의 $m_i$ 값이므로, $u'_i (m_i^*) = b'(m_i^*) - c_i = 0$를 만족한다.

 

 다음으로, $c_i \leq c_j$를 만족하는 임의의 두 client $i, j$를 가정하자. 그러면 주어진 $m$에 대해서 $u_i (m) \geq u_j (m)$이고, 이는 곧 $u_i (m_i^*) \geq u_j (m_i^*)$, $u_i (m_j^*) \geq u_j (m_j^*)$임을 의미한다.여기에서, 만약 $j$가 low-cost agent가 아니라면, 당연히 $m_i^* \geq m_j^* = 0$이다. 한편, 만약 $j$가 low-cost agent라면, $c_i \leq c_j$이므로 $i$ 역시 low-cost agent인 경우만 고려하여도 충분하다. 그리고 이때에는 $m_i^* = b'^{-1} (c_i)$, $m_j^* = b'^{-1} (c_j)$이고, $b'(\cdot)$가 non-increasing하면 $b'^{-1} (\cdot)$ 역시 non-increasing하므로, $m_i^* \geq m_j^*$이다. 정리하자면, $c_i \leq c_j$일 경우, 항상 $m_i^* \geq m_j^*$이고, 따라서 $u_i (m_i^*) \geq u_i (m_j^*) \geq u_j (m_j^*)$이다. $\square$

 

 위의 그래프에서 알 수 있듯이, 만약 $m^0$가 너무 크다면, 즉, 우리가 해결해야 하는 task가 너무 어려운 것이어서 data를 상당히 많이 모았음에도 value가 $0$이라면, (연합의 도움 없이) client 개인이 해당 task를 푸는 것은 쉽지 않을 것입니다. 그리고 이는 marginal cost $c_i$가 과도하게 큰 경우에도 동일하게 적용되는 이야기입니다. 저자들은 이러한 경우에 "FL을 적극적으로 이용하여 문제를 해결"하자고 주장합니다. (위 그래프의 $(b)$처럼 $m^0$가 충분히 작은 경우에는 혼자서도 충분히 해당 task를 해결할 수 있을 것입니다.)

 

 지금까지는 특정 client $i$의 관점에서 살펴보았는데, 다음 포스트에서는 여러 client 간에 collaboration이 이루어지는 과정에 관하여 이야기하겠습니다.