목록Analysis (7)

Federated Learning

[ICLR 2020] Convergence of FedAvg - (7)

논문 제목: On the Convergence of FedAvg on Non-IID Data 출처: https://arxiv.org/abs/1907.02189 이번 포스트에서는 해당 paper의 또 다른 topic인 decaying learning rate에 관하여 이야기할 계획입니다. (이전 글 보기) 만약 $E = 1$이고 full batch를 사용하는 상황이라면, 이는 곧 full batch GD와 동일하다는 것을 FedAvg 논문에서 이미 확인한 바 있습니다. 그리고 full batch GD에서는 굳이 learning rate를 decay할 필요가 없다는 것은 익히 알려진 사실입니다. 하지만 저자들은 $E > 1$일 때에는 full batch GD를 사용하더라도 반드시 learning rate를 ..
Federated Learning/Papers 2022. 8. 30. 00:30
[ICLR 2020] Convergence of FedAvg - (6)

논문 제목: On the Convergence of FedAvg on Non-IID Data 출처: https://arxiv.org/abs/1907.02189 이번 포스트에서는 hyperparameter $K$와 $E$에 관한 이야기를 다룬 후, experiments를 살펴 볼 계획입니다. (이전 글 보기) 9. Hyperparameter $E$ 정하기 $\text{Theorem 2, 3}$에서 확인하였듯이, partial device participation에서의 FedAvg는 다음을 만족합니다. $$\mathbb{E} [F (W_T)] - F^* \leq \frac {\kappa} {\gamma + T - 1} \left( \frac {2(B+C)} {\mu} + \frac {\mu \gamma} {..
Federated Learning/Papers 2022. 8. 28. 19:00
[ICLR 2020] Convergence of FedAvg - (5)

논문 제목: On the Convergence of FedAvg on Non-IID Data 출처: https://arxiv.org/abs/1907.02189 지난 포스트에 이어서 partial device participation case의 convergence를 증명하도록 하겠습니다. (이전 글 보기) $C$ term만 다르기 때문에, $\text{Scheme I}$과 $\text{II}$ 구분 없이 동시에 증명합니다. 7. Partial Device Participation Case $\text{Theorem 2}$ $\text{Assumtion 1 ~ 4}$가 성립하고, $\text{Scheme I}$을 사용한다고 가정하자. (즉, $\text{Assumption 5}$가 성립한다고 가정하자.) ..
Federated Learning/Papers 2022. 8. 27. 04:30
[ICLR 2020] Convergence of FedAvg - (4)

논문 제목: On the Convergence of FedAvg on Non-IID Data 출처: https://arxiv.org/abs/1907.02189 지난 두 개의 포스트를 통해, 우리는 full decive participation case에서 FedAvg의 convergence를 확인하였습니다. (이전 글 보기) 이번 포스트부터는 partial device participation case를 살펴볼 것입니다. 마찬가지로 증명 과정이 다소 길기 때문에 두세 편에 나누어서 작성될 예정입니다. 5. Assumtions - (2) 이전 포스트에서 살펴보았듯이, Sampling 과정에서 replacement가 허용되는지(FedProx 논문에서 제시한 Sampling 기법) 혹은 그렇지 않은지(해당 논..
Federated Learning/Papers 2022. 8. 25. 23:00
[ICLR 2020] Convergence of FedAvg - (3)

논문 제목: 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{..
Federated Learning/Papers 2022. 8. 19. 00:30
[ICLR 2020] Convergence of FedAvg - (2)

논문 제목: 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..
Federated Learning/Papers 2022. 8. 16. 22:30
Prev 1 2 Next