Federated Learning

논문 제목: On the Convergence of FedAvg on Non-IID Data 출처: https://arxiv.org/abs/1907.02189 지난 포스트에 이어서 증명을 진행하겠습니다. (이전 글 보기) 3. Key Lemmas for $\text{Theorem 1}$ - 이어서 $\text{Lemma 2}$ [Bounding the variance] $\text{Assumption 3}$이 성립한다고 가정할 때, $\mathbb{E} [||g_t - \bar{g_t}||^2] \leq \sum_{k=1}^N p_k^2 \sigma_k^2$이다. $\text{Proof}$ 정의 상 $g_t = \sum_{k=1}^N p_k \nabla F_k(w_t^k, \xi_t^k)$, $\bar{..

논문 제목: On the Convergence of FedAvg on Non-IID Data 출처: https://arxiv.org/abs/1907.02189 지난 포스트에서, 우리는 full device participation case에서 FedAvg의 convergence analysis를 진행하기 위한 사전 준비를 마쳤습니다. (이전 글 보기) 이번 포스트에서는 해당 내용에 관한 증명 과정을 다루도록 하겠습니다. 증명 과정이 다소 길기 때문에, 두세 편으로 나누어서 게재할 예정입니다. 3. Key Lemmas for $\text{Theorem 1}$ 우선, 증명에 앞서 추가적인 notation을 언급하도록 하겠습니다. (이는 증명 과정에서만 사용됩니다.) $\bar{v}_t := \sum_{k=1..

논문 제목: On the Convergence of FedAvg on Non-IID Data 출처: https://arxiv.org/abs/1907.02189 지난 포스트에서, 우리는 model aggregation method의 convergence를 엄밀하게 증명한 첫 논문인 FedProx에 관하여 알아보았습니다. (이전 글 보기) heterogeneous한 구성에서 FedProx가 잘 작동한다는 것은 알 수 있었지만, FedAvg의 convergence에 관한 명확한 이야기를 들어볼 수 없었다는 점은 조금 아쉽기도 했습니다. 이번에 살펴볼 논문이 이에 대한 대답을 줄 수 있을 것 같은데, 한 번 확인해보도록 하겠습니다. 해당 논문은 (FedProx와 더불어) convergence analysis의 ..

논문 제목: Federated Optimization in Heterogeneous Networks 출처: https://arxiv.org/abs/1812.06127 이전 포스트에서 FedProx에 관한 증명은 모두 마쳤고, 추가적으로 hyperparameter $\mu$의 중요성에 대해서 확인해보았습니다. (이전 글 보기) 이번 포스트에서는 $\gamma_k^t$가 어떻게 정해지는지, 그리고 어떠한 역할을 하는지 확인한 후, 각종 ablation study를 살펴보도록 하겠습니다. 9. $\gamma_k^t$가 정해지는 과정과 $\gamma_k^t$의 역할 1회의 global update를 위해서 정해진 global clock이 존재한다고 가정해봅시다. (1시간, 30분 등) 이때, 해당 round에 ..

얼마 전 FedProx 논문을 정리하면서, $1 \ll B \leq 0.5 \sqrt{K}$를 입력해야 하는 일이 있었는데, $\ll$라는 기호는 수학적으로 잘 정의된 것이 아니기 때문에 평소에 볼 일이 없었습니다. 직감적으로는 "much more less than" 정도로 읽힐 것이라는 것을 알고 있었지만, 이 기호를 $\TeX$로 어떻게 입력해야 할지 감이 오지 않았습니다. 아마 다른 분들도 논문을 작업하시거나, 발표자료를 준비하시면서 "아니, 이 기호는 어떻게 입력해야 하지?"라고 생각하신 적이 종종 있으시리라 생각합니다. 이런 경우에 제가 애용하는 사이트 하나를 소개하겠습니다. 사이트: https://detexify.kirelabs.org/classify.html Detexify라는 곳인데, 사용..

논문 제목: Federated Optimization in Heterogeneous Networks 출처: https://arxiv.org/abs/1812.06127 이전 포스트에서, 우리는 non-convex한 $F_k$에 관한 FedProx의 convergence를 증명하였습니다. (이전 글 보기) 이번 포스트에서는 FedProx의 convergence rate를 구해보고, convex case와 $\gamma$가 device 별로, 또 round 별로 달라지는 case에 관해서도 살펴볼 것입니다. 6. non-convex case의 convergence rate $\text{Theorem 6}$ (Convergence rate: FedProx) $\epsilon > 0$이 주어졌을 때, $B > B..