일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- q-FedAvg
- Agnostic FL
- ML
- value shaping
- free rider
- 연합학습
- q-FFL
- 개인정보
- OOD
- PPML
- Federated Learning
- 기계학습
- Open Set Recognition
- 딥러닝
- FedProx
- convergence
- 머신러닝
- FedAvg
- Machine learning
- ordered dropout
- OSR
- Fairness
- DP
- data maximization
- Analysis
- deep learning
- FL
- OoDD
- Differential Privacy
- Federated Transfer Learning
- Today
- Total
Federated Learning
[ICML 2019] Agnostic FL - (3) 본문
논문 제목: Agnostic Federated Learning
출처: https://arxiv.org/abs/1902.00146
지난 포스트에서 fairness에 관한 내용을 간단하게 다룬 후, 몇 가지 definition을 확인하였습니다. (이전 글 보기) 이번 포스트에서는 첫 번째 learning guarantee에 관하여 살펴보겠습니다. paper에 있는 증명은 생략된 부분이 매우 많습니다. 최대한 자세하게 풀어서 적고자 했으니, 참고 바랍니다.
5. Learning Guarantee - (1)
Theorem 2
M>0에 의하여 loss l이 bounded되어 있고, ϵ>0가 고정된 상황을 가정하자. Sk∼Dmkk를 sampling하였을 때, 임의의 δ>0에 대해서 최소 (1−δ)의 확률로 모든 h∈H, λ∈Λ에 대하여 다음 부등식이 성립한다:
LDλ(h)≤L¯Dλ(h)+2Rm(G,λ)+Mϵ+M√s(λ∥¯m)2mlog|Λϵ|δ
Proof
λ를 고정하고, 임의의 sample S=(S1,⋯,Sp)에 대해서 Ψ(S1,⋯,Sp)를 다음과 같이 정의하자.
Ψ(S1,⋯,Sp):=suph∈H(LDλ(h)−L¯Dλ(h))
그리고 S′=(S′1,⋯,S′p)는 S와 딱 한 가지 point만 다른 sample로 정의하고, 이때 그 서로 다른 point를 Sk의 xk,i와 S′k의 x′k,i라고 하자. 그렇다면 Ψ(S1,⋯,Sp)와 Ψ(S′1,⋯,S′p)의 차이는 존재하지 않거나, 만약 존재한다면 차이가 나타나는 xk,i, x′k,i 지점이 원인일 것이다. 따라서,
Ψ(S′1,⋯,S′p)−Ψ(S1,⋯,Sp)=suph∈H(LDλ(h)−L¯D′λ(h))−suph∈H(LDλ(h)−L¯Dλ(h))≤suph∈H(LDλ(h)−L¯D′λ(h))−(LDλ(h)−L¯Dλ(h))≤suph∈H(LDλ(h)−L¯D′λ(h)−LDλ(h)+L¯Dλ(h))=suph∈H(L¯Dλ(h)−L¯D′λ(h))=suph∈H(k∑p=1λkmkmk∑i=1ℓ(h(xk,i),yk,i)−k∑p=1λkmkmk∑i=1ℓ(h(x′k,i),y′k,i))=suph∈Hλkmk[ℓ(h(xk,i),yk,i)−ℓ(h(x′k,i),y′k,i)](∵xk,i and x′k,i are the only differences by assumptions)≤λkmkM(∵error is bounded by M by assumptions)
임을 알 수 있다. 따라서, McDiarmid's inequality에 의하여 임의의 h∈H에 대해서 다음 부등식이 성립한다:
P(Ψ(S)−E[Ψ(S)]≥ϵ)≤exp(−2ϵ2∑pk=1∑mki=1(λkmkM)2)⏟=:δ⟺1−P(Ψ(S)−E[Ψ(S)]≥ϵ)≥1−δ⟺P(Ψ(S)−E[Ψ(S)]≤ϵ)≥1−δ
다시 말해, ϵ은 임의로 지정한 값이므로, 임의의 δ>0에 대해서 적어도 (1−δ)의 확률로 다음 부등식이 성립한다:
Ψ(S)≤ϵ−E[Ψ(S)]=M√p∑k=1λ2k2mklog1δ(∵ϵ>0)⟺suph∈H(LDλ(h)−L¯Dλ(h))−E[suph∈H(LDλ(h)−L¯Dλ(h))]≤M√p∑k=1λ2k2mklog1δ⟹LDλ(h)−L¯Dλ(h)−E[suph∈H(LDλ(h)−L¯Dλ(h))]≤M√p∑k=1λ2k2mklog1δ⟺LDλ(h)≤L¯Dλ(h)+E[suph∈H(LDλ(h)−L¯Dλ(h))]+M√p∑k=1λ2k2mklog1δ
지금까지는 λ를 특정한 값 하나로 고정한 상태였다. 이제 임의의 λ∈Λϵ에 대해서 고려를 하고자 하는데, 이는 |Λϵ|만큼 더 tight하게 잡으면 되므로 log1δ term을 log|Λϵ|δ으로 수정해주면 된다. 그리고 더 나아가서 임의의 λ∈Λϵ에 대해서 고려할 경우, Λϵ의 정의에 따라 임의의 λ∈Λ에 대해서 LDλ(h)−LD′λ(h)≤Mϵ을 만족하는 λ′∈Λϵ이 존재하기 때문에, Mϵ term이 추가적으로 필요하다. 즉, 임의의 δ>0, λ∈Λ에 대해서 적어도 (1−δ)의 확률로 다음 부등식이 성립한다:
LDλ(h)≤L¯Dλ(h)+E[suph∈H(LDλ(h)−L¯Dλ(h))]+Mϵ+M√p∑k=1λ2k2mklog|Λϵ|δ
Claim: E[suph∈H(LDλ(h)−L¯Dλ(h))]≤2Rm(G,λ)
Proof
2Rm(G,λ)=2ESk∼Dmkkσ[suph∈Hp∑k=1λkmkmk∑i=1σk,iℓ(h(xk,i,yk,i))]=ESk∼Dmkkσ[suph∈Hp∑k=1λkmkmk∑i=1σk,iℓ(h(xk,i,yk,i))]+ES′k∼¯Dmkkσ[suph∈Hp∑k=1λkmkmk∑i=1−σk,iℓ(h(x′k,i,y′k,i))](∵σk,i's are Rademacher random variables)≥ESk∼DmkkS′k∼¯Dmkkσ[suph∈Hp∑k=1λkmkmk∑i=1σk,i(ℓ(h(xk,i,yk,i))−ℓ(h(x′k,i,y′k,i)))](∵the subadditivity of supremum)=ESk∼DmkkS′k∼¯Dmkk[suph∈Hp∑k=1λkmkmk∑i=1(ℓ(h(xk,i,yk,i))−ℓ(h(x′k,i,y′k,i)))](∵σk,i's are Rademacher random variables)≥ESk∼Dmkk[suph∈HES′k∼¯Dmkk[p∑k=1λkmkmk∑i=1(ℓ(h(xk,i,yk,i))−ℓ(h(x′k,i,y′k,i)))]](∵the subadditivity of supremum)=E[suph∈H(LDλ(h)−L¯Dλ(h))](∵the Law of Iterated Expectations)◻
Claim에 의하여 E[suph∈H(LDλ(h)−L¯Dλ(h))]≤2Rm(G,λ)이며,
χ2(λ∥¯m)+1=p∑k=1(λk−mkn)2mkm+1=p∑k=1λ2kmkm−2p∑k=1λk+p∑k=1mkm+1=p∑k=1λ2kmkm−2+1+1(∵p∑k=1λk=1 and p∑k=1mk=m)=mp∑k=1λ2kmk
이므로, ∑pk=1λ2k2mk=12m(χ2(λ∥¯m)+1)≤s(λ∥¯m)2m임을 알 수 있다. 따라서,
M√p∑k=1λ2k2mklog|Λϵ|δ≤M√s(λ∥¯m)2mlog|Λϵ|δ
로 bounded되며, 이것으로 증명을 마친다. ◻
직관적으로 보았을 때, Theorem 2은 고정된 λ에 대해서 LDλ(h)의 variance가 skewness term s(λ∥¯m)에 dependent한다는 것을 이야기하고 있습니다. (참고로, 해당 theorem은 upper bound를 이야기하고 있지만, lower bound 역시 s(λ∥¯m)에 dependent합니다. 즉, loss의 variance에 skewness가 큰 영향을 주고 있는 셈입니다. 다만, lower bound는 주제에서 벗어나기 때문에 이에 관하여 자세하게 언급하지 않도록 하겠습니다.) 그리고 이 variance는 λ가 ¯m에서 멀어지면 λ≈¯m일 때보다 조금 더 큰 bound가 필요할 수 있다는 것으로 해석 가능합니다.
또한, λ 대신 Λ에 관한 loss를 고려할 때에는 단순히 Theorem 2의 부등식 양 변에 maxλ∈Λ를 취해주면 됩니다. 즉, LDΛ는 다음과 같이 bounded됨이 최소 (1−δ)의 확률로 보장됩니다.
LDΛ=maxλ∈ΛLDλ(h)≤maxλ∈Λ(L¯Dλ(h)+2Rm(G,λ)+Mϵ+M√s(λ∥¯m)2mlog|Λϵ|δ)≤L¯DΛ(h)+2Rm(G,Λ)+Mϵ+M√s(Λ∥¯m)2mlog|Λϵ|δ
다음 포스트에서는 Theorem 2를 VC-dimension의 관점에서 다시 살펴보도록 하겠습니다.
'Federated Learning > Papers' 카테고리의 다른 글
[ICML 2019] Agnostic FL - (5) (0) | 2022.11.14 |
---|---|
[ICML 2019] Agnostic FL - (4) (0) | 2022.11.08 |
[ICML 2019] Agnostic FL - (2) (1) | 2022.11.05 |
[ICML 2019] Agnostic FL - (1) (0) | 2022.11.02 |
[NeurIPS 2021] FjORD - (4) (0) | 2022.09.13 |