Federated Learning

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

Federated Learning/Papers

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

pseudope 2023. 1. 14. 17:30
728x90

논문 제목: 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를 아는 경우)

 

Definition C [Data Maximization]

 

 임의의 mechanism M에 대하여, 해당 mechanism의 equilibrium에 해당하는 지점에서 요구되는 data의 수를 meq(M)으로 표기하자. 이때, 만약 임의의 feasible하고 IR을 만족하는 mechanism M에 대하여 ˆMargmaxMj[meq(M)]j를 만족하는 mechanism ˆM가 존재한다면, 이를 data-maximizing mechanism이라고 정의한다.

 

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

[M(m)]i:={v(mi)if mimiv(mi)+(ci+ϵ)(mimi)if mi<mimmaxi()v(jmj)if mi>mmaxi

 

 여기에서, 각 agent i의 cost ci는 알려져 있는 상황이라고 가정하고, mmaxi는 아래의 식을 만족합니다:

v(mmaxi+jimj)=v(mi)+(ci+ϵ)(mimi)

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

 

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

 

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

 

Theorem 4 [Cost가 알려져 있을 때의 Data Maximization]

 

 ()와 같이 정의된 mechanism Mϵ0+일 때 data-maximizing이다. 또한, 해당 mechanism의 equilibirum에서는 각 rational client immaxi(mi)만큼 기여하여, 총 jmmaxj만큼의 데이터가 확보된다.

 

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

 

Lemma 8

 

 ()와 같이 정의된 mechanism M과 임의의 feasible하고 IR을 만족하는 mechanism ˜M에 대하여, 각각의 best response를 BM, B˜M 로 표기하자. 이때, 임의의 client i와  data contribution m에 대해서 [BM(m)]i[B˜M(m)]i이다.  더 나아가, BMjimj에 대하여 non-decreasing이다.

 

Proof

 우선, i가 Low-cost Agent인 경우, 즉, mi>0인 경우부터 살펴보자. Theorem 1의 증명 과정에서 살펴보았듯이, 이 경우에는 v(mi)=b(mi)=ci이다. 그리고 정의 상 ui(mi;M)=[M(m)]imici이며, 임의의 mi<mmaxi에 대해서 ui(mi;M)>0이다.


Claim: mmaxi는 client i의 unique equilibrium contribution이다.

 

Proof

 i를 제외한 client들의 기여 정도를 Δmi:=jimj로 표기하고, 임의의 Δmi 값이 주어졌다고 가정하자. 그러면 mmaxi에서의 marginal utility는 ui(mmaxi;M)=v(mmaxi+Δmi)ci이다. 이떄, 정의 상 mmaxi+Δmimi이고, b()continuous, non-decreasing, concave하므로, 다음이 성립한다:

ui(mmaxi;M)=v(mmaxi+Δmi)ci=b(mmaxi+Δmi)cib(mi)ci=0

따라서, mmaxi가 client i의 unique equilibrium contribution이다.


 지금부터는 귀류법을 사용하여 [BM(m)]i[B˜M(m)]i임을 보일 것이다. 우선, 다음을 만족시키는 mechanism ˜M이 존재한다고 가정하자:

˜mi:=argmaxmi([˜M(m)]icimi)>mmaxi

이는 곧 임의의 mi˜mi에 대해서 ui(mi;˜M)>0임을 의미하고, 따라서 [˜M(m)]imi>ci이다. 더 나아가, ˜mi>mmaxi라는 것은 곧 임의의 mi(mi,mmaxi]에 대해서 [˜M(m)]imi>[M(m)]imi임을 의미한다. (1) 또한, 가정 상 ˜MIR을 만족하기 때문에, 다음이 성립한다:

[˜M(mi,mi)]iv(mi)=[M(mi,mi)]i(2)

이때, (1)(2)를 종합하면, 임의의 mi(mi,mmaxi)에 대하여 [˜M(m)]i>[M(m)]i임을 알 수 있는데, 이는 feasible하다는 ˜M의 가정을 위배한다. 왜냐하면, [˜M(mmaxi,mi)]i>[M(mmaxi,mi)]i=v(jmj)이기 때문이다.

 따라서, 임의의 feasible하고 IR을 만족하는 mechanism ˜M에 대하여, [BM(m)]i[B˜M(m)]i이다.

 

 i가 Mid-cost 혹은 High-cost Agent인 경우, 즉, mi=0인 경우도 위와 유사한 방식으로 증명 가능하고, BMjimj에 대하여 non-decreasing인 점은 정의 상 자명하므로, 이후의 증명 과정은 생략한다.

 

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

Comments