# Optimizing Federated Learning on Non-IID Data with Reinforcement Learning筆記(2023/03/03更新)

###### tags: `Paper`

## Introduction
- 雖然行動裝置能不斷產生大量的資料(如照片、聲音)，但將這些私有資料集中訓練可能有隱私疑慮，因此，聯邦式學習(Federated Learning)便被提了出來
- 聯邦式學習會面臨一些挑戰，如無線網路的連線限制、行動裝置的不穩定、non-IID資料分布等等
- Federated Averaging(FEDAVG)演算法能降低溝通回合(communication rounds)的次數
- 現有的聯邦式方法無法解決異質本地資料集(heterogeneous local datasets)所帶來的問題
- 本篇提出了一個名為FAVOR的控制框架，基於強化學習，FAVOR能幫助加速並穩定聯邦式學習的訓練過程，並抵銷non-IID資料的影響
## Background and Motivation
1. Federated Learning
- 透過多個客戶裝置(client devices)的更新，訓練一個共享的全域模型(shared global model)
- 網路連線上可能有速度慢以及不穩定等問題
- 伺服端(server)每回合(round)隨機選一組(subset)可用的客戶裝置參與訓練
- 先從伺服端下載最新的模型權重，再用各自裝置上的本地資料(local datasets)去訓練， 訓練完後再將練好的權重傳回伺服端
- 更新全域模型使用到了Federated Averaging(FEDAVG)演算法

2. The Challenges of Non-IID Data Distribution
- 當資料分布為non-IID時，FEDAVG會不穩定(unstable)且有可能發散(diverge)
- 這和客戶端執行的SGD演算法之間不一致(inconsistency)有關
- 在聯邦學習中，減少溝通次數(communication rounds)相當重要
- 因為行動裝置的計算能力(computation capacity)和溝通頻寬(communication bandwidth)有限

3. Deep Reinforcement Learning(DRL)
- 透過深度強化學習(deep reinforcement learning)來幫助每回合裝置上的選取
- double Deep Q-learning Network(DDQN)

## DRL for Client Selection
1. The Agent based on Deep Q-Network
- State :
$$
s_t = (w_t,w_t^{(1)},...,w_t^{(N)})
$$
其中w和t表示第t輪後的global model權重，1~N表示N台的裝置
- Action : 從N個裝置中選出K個

2. Workflow

3. Dimension Reduction
- 運用主成分分析(PCA)來壓縮模型權重

4. Training the Agent with Double DQN

## Evaluation
這裡分別用了3種資料集做訓練，分別是MNIST、FashionMNIST、CIFAR-10

各自的模型架構如下:

實驗主要會以探討溝通回合為主
1. Training the DRL agent

2. Different Levels of Non-IID Data
這裡比較了FAVOR、FEDAVG、K-Center三種方法，並準備了4種不同程度的non-IID資料

3. Device Selection and Weight Updates
FAVOR相較於FEDAVG能在更早的時間點收斂

4. Increasing Parallelism
增加平行度並沒有減少溝通回合，相反的，反而會有增加的現象

## Related Work
在FL中效能時常被拿來討論，所以在這分成了兩類 :
1. Communication efficiency
- Communication effciency
- Sample efficiency
2. Sample efficiency

## Concluding Remarks
1. 本篇提出了名為FAVOR的控制框架，並降低了FL訓練時的溝通回合
- MNIST中減少了49%
- FashionMNIST中減少了23%
- CIFAR-10中減少了42%
2. 以Double DQN選擇行動裝置的最佳子集合(best subset)