Federated Learning

[ICML 2019] Agnostic FL - (3) 본문

Federated Learning/Papers

[ICML 2019] Agnostic FL - (3)

pseudope 2022. 11. 7. 01:00
728x90

논문 제목: 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가 고정된 상황을 가정하자. SkDmkk를 sampling하였을 때, 임의의 δ>0에 대해서 최소 (1δ)의 확률로   모든 hH, λΛ에 대하여 다음 부등식이 성립한다:

LDλ(h)L¯Dλ(h)+2Rm(G,λ)+Mϵ+Ms(λ¯m)2mlog|Λϵ|δ

 

Proof

 λ를 고정하고, 임의의 sample S=(S1,,Sp)에 대해서 Ψ(S1,,Sp)를 다음과 같이 정의하자.

Ψ(S1,,Sp):=suphH(LDλ(h)L¯Dλ(h))

그리고 S=(S1,,Sp)S와 딱 한 가지 point만 다른 sample로 정의하고, 이때 그 서로 다른 point를 Skxk,iSkxk,i라고 하자. 그렇다면 Ψ(S1,,Sp)Ψ(S1,,Sp)의 차이는 존재하지 않거나, 만약 존재한다면 차이가 나타나는 xk,i,  xk,i 지점이 원인일 것이다. 따라서,

Ψ(S1,,Sp)Ψ(S1,,Sp)=suphH(LDλ(h)L¯Dλ(h))suphH(LDλ(h)L¯Dλ(h))suphH(LDλ(h)L¯Dλ(h))(LDλ(h)L¯Dλ(h))suphH(LDλ(h)L¯Dλ(h)LDλ(h)+L¯Dλ(h))=suphH(L¯Dλ(h)L¯Dλ(h))=suphH(kp=1λkmkmki=1(h(xk,i),yk,i)kp=1λkmkmki=1(h(xk,i),yk,i))=suphHλkmk[(h(xk,i),yk,i)(h(xk,i),yk,i)](xk,i and xk,i are the only differences by assumptions)λkmkM(error is bounded by M by assumptions)

임을 알 수 있다. 따라서, McDiarmid's inequality에 의하여 임의의 hH에 대해서 다음 부등식이 성립한다:

P(Ψ(S)E[Ψ(S)]ϵ)exp(2ϵ2pk=1mki=1(λkmkM)2)=:δ1P(Ψ(S)E[Ψ(S)]ϵ)1δP(Ψ(S)E[Ψ(S)]ϵ)1δ

다시 말해, ϵ은 임의로 지정한 값이므로, 임의의 δ>0에 대해서 적어도 (1δ)의 확률로 다음 부등식이 성립한다:

Ψ(S)ϵE[Ψ(S)]=Mpk=1λ2k2mklog1δ(ϵ>0)suphH(LDλ(h)L¯Dλ(h))E[suphH(LDλ(h)L¯Dλ(h))]Mpk=1λ2k2mklog1δLDλ(h)L¯Dλ(h)E[suphH(LDλ(h)L¯Dλ(h))]Mpk=1λ2k2mklog1δLDλ(h)L¯Dλ(h)+E[suphH(LDλ(h)L¯Dλ(h))]+Mpk=1λ2k2mklog1δ

 지금까지는 λ를 특정한 값 하나로 고정한 상태였다. 이제 임의의 λΛϵ에 대해서 고려를 하고자 하는데, 이는 |Λϵ|만큼 더 tight하게 잡으면 되므로 log1δ term을 log|Λϵ|δ으로 수정해주면 된다. 그리고 더 나아가서 임의의 λΛϵ에 대해서 고려할 경우, Λϵ의 정의에 따라 임의의 λΛ에 대해서 LDλ(h)LDλ(h)Mϵ을 만족하는 λΛϵ이 존재하기 때문에, Mϵ term이 추가적으로 필요하다. 즉, 임의의 δ>0, λΛ에 대해서 적어도 (1δ)의 확률로 다음 부등식이 성립한다:

LDλ(h)L¯Dλ(h)+E[suphH(LDλ(h)L¯Dλ(h))]+Mϵ+Mpk=1λ2k2mklog|Λϵ|δ

 


Claim: E[suphH(LDλ(h)L¯Dλ(h))]2Rm(G,λ)

 

Proof

2Rm(G,λ)=2ESkDmkkσ[suphHpk=1λkmkmki=1σk,i(h(xk,i,yk,i))]=ESkDmkkσ[suphHpk=1λkmkmki=1σk,i(h(xk,i,yk,i))]+ESk¯Dmkkσ[suphHpk=1λkmkmki=1σk,i(h(xk,i,yk,i))](σk,i's are Rademacher random variables)ESkDmkkSk¯Dmkkσ[suphHpk=1λkmkmki=1σk,i((h(xk,i,yk,i))(h(xk,i,yk,i)))](the subadditivity of supremum)=ESkDmkkSk¯Dmkk[suphHpk=1λkmkmki=1((h(xk,i,yk,i))(h(xk,i,yk,i)))](σk,i's are Rademacher random variables)ESkDmkk[suphHESk¯Dmkk[pk=1λkmkmki=1((h(xk,i,yk,i))(h(xk,i,yk,i)))]](the subadditivity of supremum)=E[suphH(LDλ(h)L¯Dλ(h))](the Law of Iterated Expectations)


 Claim에 의하여 E[suphH(LDλ(h)L¯Dλ(h))]2Rm(G,λ)이며,

χ2(λ¯m)+1=pk=1(λkmkn)2mkm+1=pk=1λ2kmkm2pk=1λk+pk=1mkm+1=pk=1λ2kmkm2+1+1(pk=1λk=1 and pk=1mk=m)=mpk=1λ2kmk

이므로, pk=1λ2k2mk=12m(χ2(λ¯m)+1)s(λ¯m)2m임을 알 수 있다. 따라서,

Mpk=1λ2k2mklog|Λϵ|δMs(λ¯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ϵ+Ms(λ¯m)2mlog|Λϵ|δ)L¯DΛ(h)+2Rm(G,Λ)+Mϵ+Ms(Λ¯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