일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- FedAvg
- ordered dropout
- value shaping
- deep learning
- Federated Transfer Learning
- OOD
- Agnostic FL
- FedProx
- 딥러닝
- Analysis
- ML
- free rider
- DP
- q-FFL
- Open Set Recognition
- OSR
- Differential Privacy
- PPML
- 기계학습
- Federated Learning
- data maximization
- Machine learning
- 개인정보
- convergence
- Fairness
- OoDD
- 머신러닝
- FL
- 연합학습
- q-FedAvg
- Today
- Total
Federated Learning
[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를 아는 경우)
Definition C [Data Maximization]
임의의 mechanism M에 대하여, 해당 mechanism의 equilibrium에 해당하는 지점에서 요구되는 data의 수를 meq(M)으로 표기하자. 이때, 만약 임의의 feasible하고 IR을 만족하는 mechanism M에 대하여 ˆM∈argmaxM∑j[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 mi≤m∗iv(m∗i)+(ci+ϵ)(mi−m∗i)if m∗i<mi≤mmaxi(†)v(∑jmj)if mi>mmaxi
여기에서, 각 agent i의 cost ci는 알려져 있는 상황이라고 가정하고, mmaxi는 아래의 식을 만족합니다:
v(mmaxi+∑j≠imj)=v(m∗i)+(ci+ϵ)(mi−m∗i)

오른쪽 그래프가 이러한 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 i가 mmaxi(≥m∗i)만큼 기여하여, 총 ∑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이다. 더 나아가, BM은 ∑j≠imj에 대하여 non-decreasing이다.
Proof
우선, i가 Low-cost Agent인 경우, 즉, m∗i>0인 경우부터 살펴보자. Theorem 1의 증명 과정에서 살펴보았듯이, 이 경우에는 v′(m∗i)=b′(m∗i)=ci이다. 그리고 정의 상 u′i(mi;M)=∂[M(m)]i∂mi−ci이며, 임의의 mi<mmaxi에 대해서 u′i(mi;M)>0이다.
Claim: mmaxi는 client i의 unique equilibrium contribution이다.
Proof
i를 제외한 client들의 기여 정도를 Δm−i:=∑j≠imj로 표기하고, 임의의 Δm−i 값이 주어졌다고 가정하자. 그러면 mmaxi에서의 marginal utility는 u′i(mmaxi;M)=v′(mmaxi+Δm−i)−ci이다. 이떄, 정의 상 mmaxi+Δm−i≥m∗i이고, b(⋅)는 continuous, non-decreasing, concave하므로, 다음이 성립한다:
u′i(mmaxi;M)=v′(mmaxi+Δm−i)−ci=b′(mmaxi+Δm−i)−ci≤b′(m∗i)−ci=0
따라서, mmaxi가 client i의 unique equilibrium contribution이다. ◻
지금부터는 귀류법을 사용하여 [BM(m)]i≥[B˜M(m)]i임을 보일 것이다. 우선, 다음을 만족시키는 mechanism ˜M이 존재한다고 가정하자:
˜mi:=argmaxmi([˜M(m)]i−cimi)>mmaxi
이는 곧 임의의 mi≤˜mi에 대해서 u′i(mi;˜M)>0임을 의미하고, 따라서 ∂[˜M(m)]i∂mi>ci이다. 더 나아가, ˜mi>mmaxi라는 것은 곧 임의의 mi∈(m∗i,mmaxi]에 대해서 ∂[˜M(m)]i∂mi>∂[M(m)]i∂mi임을 의미한다. (1) 또한, 가정 상 ˜M은 IR을 만족하기 때문에, 다음이 성립한다:
[˜M(m∗i,m−i)]i≥v(m∗i)=[M(m∗i,m−i)]i(2)
이때, (1)과 (2)를 종합하면, 임의의 mi∈(m∗i,mmaxi)에 대하여 [˜M(m)]i>[M(m)]i임을 알 수 있는데, 이는 feasible하다는 ˜M의 가정을 위배한다. 왜냐하면, [˜M(mmaxi,m−i)]i>[M(mmaxi,m−i)]i=v(∑jmj)이기 때문이다. ↯
따라서, 임의의 feasible하고 IR을 만족하는 mechanism ˜M에 대하여, [BM(m)]i≥[B˜M(m)]i이다.
i가 Mid-cost 혹은 High-cost Agent인 경우, 즉, m∗i=0인 경우도 위와 유사한 방식으로 증명 가능하고, BM이 ∑j≠imj에 대하여 non-decreasing인 점은 정의 상 자명하므로, 이후의 증명 과정은 생략한다. ◻
다음 포스트에서는 Theorem 4의 증명 과정을 살펴본 후, 해당 Theorem이 갖는 의미에 관하여 알아보도록 하겠습니다. 또한, 여유가 된다면 간단한 experiments도 함께 확인할 계획입니다.
'Federated Learning > Papers' 카테고리의 다른 글
[FL-NeurIPS 2022] Data Maximization - (6) (0) | 2023.01.24 |
---|---|
[FL-NeurIPS 2022] Data Maximization - (5) (0) | 2023.01.19 |
[FL-NeurIPS 2022] Data Maximization - (3) (0) | 2023.01.05 |
[FL-NeurIPS 2022] Data Maximization - (2) (0) | 2023.01.03 |
[FL-NeurIPS 2022] Data Maximization - (1) (0) | 2022.12.13 |