# 碩論
## introduction
* 現今的手機擁有很強的計算能力，並且具備了執行DNN、CNN類神經網路，因此手機用戶透過自身所收集的數據來幫助global model訓練也成了一個可行途徑
* 在真實的手機使用者環境中，wireless network通常會因為所在區域環境因素以及不同技術而有很大變化，且使用者會移動此造成這是一個dynamic transmission environment(core -> hard to use game/optimization theory to solve)
*
## system model
* Role
* server
* 具有一個test dataset $𝐷_{test}$ ，serve透過federated learning使得$𝑤_𝑡$在$𝐷_{𝑡𝑒𝑠𝑡}$具有更好的accuracy
* server具有N個事先決定好的potential client set，其會隨著訓練進行因為client沒電或網路不穩定斷線而逐漸減小且過程中不會有新的client加入
* Server在每一輪global iteration前需要從potential client set中決定摻與此輪的clients($𝐴^𝑡$)以及規定此輪local training latency($𝐿^𝑡$)
* client selection $A$
* $A=\{A^1,A^2,...,A^t,...,A^T\}$
* $A^t=\{a^t_1,a^t_2,...,a^t_i,...,a^t_N\}$
* $a^t_i\in\{0,1\}$
* training latency $𝐿$
* $L=\{L^1,L^2,...,L^t,...,L^T\}$
* $L^t\in R$
* client
* 每個client具有一個dataset $𝐷_𝑖$其dataset size記作$|𝐷_𝑖 |$。並且由於Client之間以及與serve的test dataset之間因為不同習慣而有不同data distribution(ie non-iid)
* 依據[ZXL+21],[MZL+22],[LDC+21],[ZLL+22] non-iid主要可以分為feature skew以及label skew，但feature skew在實際上我們很難去準確定義出feature，因此現今主要的paper都是討論label skew。而此項指標可以依據 [ZLL+22] 中所定義的EMD來衡量。其描述了$𝐷_𝑖$ 的label distribution與$𝐷_{𝑡𝑒𝑠𝑡}$ 的label distribution之間差異
* 每個client具有一個最大frequency為$𝐹_𝑖$的CPU。在local training中，client會用最低可以滿足$𝐿^𝑡$的CPU frequency $𝑓_𝑖^𝑡$來執行local training以達到energy efficient目的
* 每個client都具有一個battery budget。每次完整的federating learning過程中battery不會充電，並且只要有執行local training就會有相對應的energy consumption，當battery沒電或不再足夠訓練時則此client不再提供訓練服務(ie. Server不能再select此client)
1. **computation model**
* Computation Energy( $𝑒_{\text{cmp},𝑖}^𝑡$ )
* $𝑒_{\text{cmp},𝑖}^𝑡=𝑘 H_i 𝐼_𝐿 𝐶_𝑖 𝐷_𝑖 {𝑓_𝑖^𝑡}^2$
* $𝑘$: model coefficient (fixed)
* $H_i$: device heterogeneous coefficient (fixed)
* $𝐼_𝐿$: local iteration (fixed)
* $𝐶_𝑖$: CPU cycle/bit (fixed)
* $𝐷_𝑖$: data size(bits) (fixed)
* $𝑓_𝑖$: CPU frequency (passive, determine by $𝐿^𝑡$)
* Computation Latency( $𝑙_{\text{cmp},𝑖}^𝑡$ )
* $𝑙_{\text{cmp},𝑖}^𝑡=\frac{𝐼_𝐿 𝐶_𝑖 𝐷_𝑖}{𝑓_𝑖^𝑡}$
2. **communication model**
* **Transmission rate**
* $\lambda^t_i=b_i\log_2(1+\frac{\overline{g_i p^t_i}}{N b_i})$
* $b_i$: the bandwidth resources allocated to local device i
* $p^t_i$: the average transmit power of local device i
* $\overline{g_i}$: the average channel gain between local device i and the server
* $N$: the background noise
* **Communication Latency**
* $l^t_{\text{com},i}=l^t_{\text{com_R},i}+l^t_{\text{com_C},i}$
* $l^t_{com_R,i}$: latency through wireless network(device to base station)
* $l^t_{com_R,i}=\frac{D_M}{\lambda^t_i}$
* $D_M$: the size of the model weight
* $l^t_{\text{com_C},i}$: latency through core network(base station to server)
* **communication Energy**
* $e^t_{\text{com},i}=l^t_{\text{com},i}p^t_i$
* We don’t formular such dynamic, complicated and unpredicted Communication model and using RL to implicitly consider these factor
3. **System model**
* Total latency of client at time step t
* $l^t_i = l_{\text{cmp},𝑖}^𝑡 + l_{\text{com},𝑖}^𝑡$
* client i's energy consumption at time $t$
* $𝑒_𝑖^𝑡=a^t_i(𝑒_{\text{com},𝑖}^𝑡+𝑒_{\text{cmp},𝑖}^𝑡)+e^t_{\text{basic},i}$
* $e^t_{\text{basic},i}$: device maintain energy consumption per time step
* $e^t_{\text{basic},i}=m_i L^t$
* $m_i$: device’s maintain consumption coefficient
* Remained battery at begin of time step t
* $𝑏_𝑖^𝑡=𝑏_𝑖^{𝑡−1}−𝑒_𝑖^{𝑡−1}$
* time $t$還沒有使用前所剩下能量
* 如果client在時間t時沒有被選到則不會有能量消耗

* federated learning
1. **Application stage**
* client依據自己$EMD_i$、$|D_i|$、$B_i$及$𝐹_𝑖$向server提出加入FL請求。
* server從中選擇N個client作為其potential set成員(此處部討論如何選擇poteantial client)。
* server儲存資訊$EMD_i$、$|D_i|$、$B_i$及$𝐹_𝑖$做為日後選擇client依據
2. **client selection and download stage**
* server依據現有情況決定此global iteration摻與training的client($𝐴^𝑡$)以及此輪training的computation最長時間($L^t$)，接著發送$\omega^{t-1}$給selected client
3. **local training stage**
* selected client執行local training
4. **upload stage**
* selected client完成local training後得到$w^{t}_{i}$，並回傳$\{\omega^{t}_{i},\;\text{ loss}(\omega^{t}_{i}),\;b_i^t\}$給server
5. **aggregate stage**
* client等待所有???
* server aggregate收到的$\omega^{t}_{i}$成$\omega^{t}$
* aggregate method: $\omega^{t}\leftarrow\sum^N_{i=1}\frac{a^t_i|D_i|}{\sum^N_{j=1}|D_j|}\omega^{t}_{i}$
6. 重複步驟(2)~(5)，直到
1. 沒有client可以選擇
2. accuracy無法再進步

## problem formulation

## motivation
the drawback of previous studies
1. 現在有關federated learning中client selection的方法大多都假定**選擇越多的client對performance越好**
1. [DLR+22](<https://ieeexplore.ieee.org/document/9647925>): 考量了data size以及data quality，盡可能的選擇client直到其budget
2. ...
2. 已經有很多paper在討論使用reinforcement learning來幫助FL選擇client，但由於client selection problem中action space為$O(2^N)$(N是the number of potential clients)這會造成RL agent難以學習。因此現今大部分的paper都採用**sequential action**，agent每次都只會選擇一個client，並重複選擇直到達到每輪期望要選的數量。但在這些使用sequential action技巧的RL-based client selection都是**假定client數量為固定**
1. [DLR+22](<https://ieeexplore.ieee.org/document/9647925>): 使用sequential action技巧，並以budget來間接限制client選擇數量(budget 10~20, price of each client 1~3)
2. [ZLZF+23](<https://www.sciencedirect.com/science/article/abs/pii/S0167739X23000870>): 使用continuous action space, agent的output是一個N個client被選擇的probability($O(N)$)，每一輪固定選擇10個client
3. [ZLZ+23](<https://ieeexplore.ieee.org/document/10181138>): 使用continuous action space, agent的output是一個N個client被選擇的probability($O(N)$)，每一輪固定選擇10個client
4. [WKN+20](<https://ieeexplore.ieee.org/abstract/document/9155494?casa_token=VbY-5Ky-MHsAAAAA:9-b26NEXlBqx8fyY9iPGFnplrXdtQJfY2uk354lR79fOesDgyVco0nG1LB3CkaPu1U1XqfAqEg>): 採用DQN，每一個action(client)都被一個Q-value來衡量。每一次選擇都選前k個Q-value高的action

然而透過實驗可以發現，每一輪**number of selected client**也對**model performace**以及**convergence speed**有很大的影響。並且實驗也說明，在滿足最低選擇數量下，選擇越少的client反而能夠得到越高的accucracy。
* 在實驗[TOPIC1](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPICE1---%E4%B8%8D%E5%90%8Cclient-selection-number-uni1uni5uni10uni20all>)中，針對6種不同non-iid程度的potential clients依據每一輪數量1/5/10/15/all以FedAvg來訓練，並從中觀察每一種實驗收斂速度以及accuracy
* 透過實驗可以發現，在不同non-iid setting中
1. 達到最大accuracy每一輪最佳選擇的數量是在1~5之間，同時此數量最著non-iid 程度降低而減少，當為iid情況時甚至只需要每一輪一個client就足夠了，選擇越多client反而造成accuracy下降
2. 收斂速度則隨著client數量增加而增加。在每一種setting中，每一輪都選擇全部potential clients收斂速度都是最快的

因此，如何決定適當的number of selected clients也是一個重要的議題

## solution
* 目標:
* 設計一個RL agent其可以幫助我們select client
* 挑戰
1. 直接使用RL agent決定optimal selected clients會使得action space變成$O(2^N)$難以學習
2. 有些paper採用sequential action方式，並且這些paper中都假定client選擇數量是固定，此可以使得action space降成$O(N)$。但由先前實驗可以發現**每輪client數量也會影響到final testing accuracy，並且並不是越多client就會有越好的final testing accuracy**，因此在sequential action方式要如何決定每輪client數量也很重要。
* 構想:
* 在每一輪的client selection時，會有兩個agent摻與
1. **client selection agent**: 針對目前client state選出此輪要摻與訓練的clients。採用sequential action方式選擇client
* client selection agent的目標是能讓所訂定objective function達到optimal
* sequential action:每一輪的global round t中，client selection agent會進行$M_t$輪的scheduling round。每一輪scheduling round m會一次選擇一個client作為t輪的training client，並執行$M_t$次共選擇$M_t$個client摻與t輪的training。
* $M_t$是一個decision variable，其決定方式是由**guidance agent**依據目前已經選擇client來判斷
2. **guidance agent**: 依據目前**已經選擇**clients來導client selection agent的scheduling round是否要繼續選擇client
* guidance agent目標只是要判斷目前所選擇的client數量是否能夠學習到東西而不會甚麼都學不起來。<font color="#f00">不考慮這個數量是不是可以找到optimal solution</font>
* implement:
1. **client selection agent**: <font color="#f00">還在想...</font>
2. **guidance agent**
* input: 現在已經選擇client的state
* output: 是否足夠(足夠->停止scheduling round；不夠->scheduling round繼續選client)
* 實驗 guidance_agent-task1
* 我這裡有一個想法是，原本針對client number是每一輪都隨機選但是最後數量client number(長期來看)。但是如果只是每一輪判斷，我在練這個agent時這個組合好不好也跟未來策略怎麼選擇有關係(client selection agent)，那我要怎麼去定義現在這個組合是好的還是不好的?
1. 如果client selection agent是random選擇，那guidance_agent其中選擇就用random
2. 如果client selection agent是rl agent，那如果

## experiment
* https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view

## reference
* Motivate
* [XW+21][Client Selection and Bandwidth Allocation in Wireless Federated Learning Networks: A Long-Term Perspective](<https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9237168>)
* NON-IID classify
* [ZXL+21][Federated Learning on Non-IID Data: A Survey](<https://hackmd.io/@nnlijpg3Ts6jTgdB-pUfEw/rkxtkCFN6>)
* [MZL+22][A state-of-the-art survey on solving non-IID data in Federated Learning](<https://hackmd.io/@nnlijpg3Ts6jTgdB-pUfEw/Hk5d8bsNp>)
* [LDC+21][Federated Learning on Non-IID Data Silos: An Experimental Study](<https://hackmd.io/@nnlijpg3Ts6jTgdB-pUfEw/Hyp5hWjN6>)
* [ZLL+22][Federated Learning with Non-IID Data](<https://hackmd.io/@nnlijpg3Ts6jTgdB-pUfEw/HkTey-iET>)
* FL performance can be improved by selecting more clients in each round
* Federated learning via over the-air computation
* Energy-efficient radio resource allocation for federated edge learning

## others
紀錄：https://hackmd.io/kHOxZA9sS_SVPjCH-h-QqQ?view
coding: https://hackmd.io/eFYaw0JPQw2iyGfnxV26uA

## ~~Solution(想法)~~
* Client Quality model
* 在federated learning有以下幾個因素會影響到training結果
1. **Data Heterogeneity (Non-IID degree)**: 由[ZLL+22]所提出的結果，當dataset的$EMB_i$越大，則最終結果的accuracy bias越大
2. **Data Quantity Skew**: 提供越大量的資料所帶來的效益也越高
3. **Freshness**: 有一些client雖然EMD以及data size很差，但是由於他有一些獨有的資料，透過freshness設計來增加探索到這些client機會
* $𝑞(𝑖,𝑡)= \alpha\frac{|𝐷_𝑖|\log⁡𝑡}{𝐸𝑀𝐷_{𝑖+1}}+ \beta \sqrt{\frac{\ln⁡𝑡}{𝑁_𝑖^𝑡}} + \gamma 𝑄_𝑖^𝑡$
* $\alpha$,$\beta$,$\gamma$: weight
* $t$: time step(iteration)
* $D_𝒊$: dataset of client i
* $EMD_i$: EMD of client i(test dataset vs client’s dataset)
* $EMD_i = \sum_{l=1}^{label}|P_i(y=l)-P_{test}(y=l)|$
* $N_i^t$: the total number of client i selected before t
* $N_i^t=\sum_{t^{\prime} =1}^ta_i^{t^{\prime}}$
* $Q_i^t$: history performance
* $Q_i^t=\begin{cases} loss(\omega_i^t), a_i^t=1 \\ Q_i^{t-1}\cdot\xi, a_i^t=0 \end{cases}$
* $\xi$: decay rate
* design
1. $\log⁡𝑡$ : 在一開始訓練時，主要學習的只是basic knowledge(每個client都有)，因此對資料品質的要求不用那麼高(探索比較重要)。透過個隨時間增加的函數來讓月後其越重視資料品質
2. $\sqrt{\frac{\ln⁡𝑡}{𝑁_𝑖^𝑡}}$ : 此項主要啟發於Multi-Armed Bandit Testing中的UCB(Upper Confidence Bound )。用來讓增加探索度
3. $𝑄_𝑖^𝑡$ : 表示過去performance history。從實驗可以知道，當model訓練到後期成長速度會變慢，因此假如client沒有被選到，則他在t時間的performance history就用過去資料乘上衰減率來代替(necessary?)

* Accuracy and Quality model
* $accprog_t = \epsilon \cdot acc(\omega_{t-1})\cdot \log (\; \theta \cdot acc(\omega_{t-1}) \cdot \sum_{i=1}^t a_i^t q(i,t)\;)$
* 𝜀,𝜃,𝜇 is hyperparameter
* 啟發於[XW+21]。在整個訓練過程，前期model還非常不準確時，由於只是在學習basic knowledge，因此不需要太多的client，而選擇過多反而會造邊際效應的遞減；到了後期model已經有足夠準確度時，則因為需要學習更精細的細節，因為選過多client所帶來的邊際效應遞減會越少(選越多越好)
* Model-$\omega_𝑡$的準確度最直接衡量的方式就是用model在test dataset中所測得的accuracy來衡量。越大越準，越小則越不準確
* $acc(𝜔_{𝑡} )$: 在$D_{test}$上用$\omega_{𝑡}$測得的accuracy
* $accprog_t = \epsilon \cdot \mu^{-t} \cdot \log (\; \theta \cdot \mu^{-t} \cdot \sum_{i=1}^tq(i,t)\;)$
* [Optional]此為另外一種model方式，這裡假設model隨著時間不逐漸變準確，則直接用t來代替loss function

老師 針對上次討論"要把控制client數量的agent加在哪裡?"

我目前有兩個想法，一個是只在一開始決定選擇client數量(offline)，另外一個則是每一輪都會決定一次選擇client數量一次(online)
offline的方法主要是去判斷"整個"potential client的分布，然後來決定未來每一輪要選擇幾個(固定)，這種方式比較值觀好設計rl agent，但缺點是如果想要加在其他rl-based或具有resourece allocation的方法中，那這樣事先用整體potential client的分布判斷就會有點是失準。

online的方式我的想法是結合先前paper他們所採用sequential select方式，在每次選出一個client後去判斷已經選擇client是否已經足夠，如果不夠在繼續選(這裡的夠不夠就是指是否所選擇client的dataset含有足夠的label數量)。這種方式比較可以結合不同演算法，但要怎麼去設計如此agent(包含input/output是甚麼，怎麼train)還要再想想

我目前想法是