碩論 v2 - HackMD

# 碩論 v2 ## introduction * 現今的手機擁有很強的計算能力，並且具備了執行DNN、CNN類神經網路，因此手機用戶透過自身所收集的數據來幫助global model訓練也成了一個可行途徑 * 在真實的手機使用者環境中，wireless network通常會因為所在區域環境因素以及不同技術而有很大變化，且使用者會移動此造成這是一個dynamic transmission environment(core -> hard to use game/optimization theory to solve) ## motivation ## system model ![螢幕擷取畫面 (468)](https://hackmd.io/_uploads/HyDPRYT3p.png) * 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($i \in N$) * 每個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都具有一個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時沒有被選到則不會有能量消耗 ## problem formulation * P1: $\max acc(\omega_T) - \delta \sum^{T}_{t=1}(L^t)$ 1. $a^t_i \in {0,1},\forall i,t$ 2. $\sum_{t=1}^{T}E_i^T \le B_i,\forall i$ * $acc(\omega_t)$: t時間，使用aggregate後的model $\omega_t$在test dataset所得的accuracy ## Challenge and related work ### Challenge in FL 1. **heterogencous client** 1. data heterogencous (non-iid) * 在傳統的centralized learning中，由於資料被統一被集中在server因此可以被視為iid。但在FL中由於每個client行為的不同可能造成每個client dataset有不同的資料分布以及資料量(ie. non-iid)，此問題在很多paper中提出會嚴重影響performance * non-iid survey * non-iid造成peformance下降paepr: * 降低non-iid帶來的影響有很多不同層面的解決方式 1. frame work，大部分對於FL研究都是基於FedAvg(paper~)的架構下改進，但也有部分研究改變framework 1. update method.... 3. personalized Federated learning，關注在如何藉由共同合作學習來讓每個餐與者能夠最終得到一個適合自己local dataset的model * paper 4. client selection and dynamic weight，透過更好的選擇策略竟可能選擇優質的client來提升最終global model accuracy * NOTE: 甚麼是優質? 此是這類型paper主要研究議題，透過clients' dataset size, data quality以及各種因素來決定 * 此外有些研究也表明，過度的選擇相同client會造overfit，因此確保選擇過程的fairness也很重要 | - | dataset size | distribution | computation capacity | communication latency | battery | fairness | |:------:|:------------:|:------------:|:--------------------:|:---------------------:|:-------:|:--------:| | paper~ | | | | | | | 2. hardware capacity heterogencous * computation and comunication capacity * straggler problem: 在FedAvg架構中採用synchronous aggregate方式(等待所有或依定比例client upload後才進行aggregate)，此類framework會因為運算速度或傳輸速度較慢的client造成該輪training latency變慢，進而使得整體訓練速度下降 * data heterogencous與hardware capacity heterogencous共同帶來的潛在問題overfiting * 為了解決前面問題，selection policy會對特定client有偏好性，使得只有特定client被選擇，最終trained global model偏向部分client不夠generalized 2. **privacy issue** * FL的提出主要要解決privacy議題，以local training方式代替將raw data直接上傳到centralized server以防止client隱私外洩，同時每個cient dataset的distribution也被視不可被server access的資訊 * data distribution在client selection時是一項重要資訊，其對accuracy以及convergence time有很大影響，因此在不知道這些資訊情況下如何透過其他可以取得資訊來推敲出data distribution是一項重要議題 * 常見的方式 1. local training loss代替真實的data distribution 2. 透過RL以及MAB這類方式來隱性的預測這些值 3. **dynamic enviroment** * 在真實世界中，每個client的capacity(computation以及communication)、local dataset和availabilty以及網路狀況都在變化難以使用model去描述。例如現今的手機電腦允許多執行續執行，運算速度會因為device當下任務多寡而有很大不同我們難以在使用者層級(OS概念)來去調控個別device的運算資源；又或者網路情況通常受限於硬體以及網路供應商的設計，此也很難透過應用層面來解決。 * 因此在尋求最終objective最佳化時就很難透過量化來找到最佳解 * 因此相比P1 offline型式我們應該把問題轉換成online型式 4. **target task is non-convex problem** * 使用FL來學習linear problem或convex probelm時，我們可以透過理論分析來找到各項因素(data size, learning rate,...)與最終performance之間關係(accuracy, convergence speed...)。這些現有的研究提供使用傳統最佳化方式來解決linear task與convex task中client selection的機會。 * 理論paper: * 應用paper: * 現今FL主要學習neural network(DNN, CNN, RNN)來應付更複雜的應用情境，而這類model都是non-convex問題，先前基於linear problem和convex probelm問題提出的理論分析不再準確，並且各項因素與最重performance有極其複雜且難以預測的關係，如何在缺乏理論基礎下仍可以找到approximate optimazed solution是一個重要議題 5. **fairness** 1. 透過實驗TOPIC8可以觀察到即使選擇label數量較多的client(接近iid)頻率更高也無法帶來更好的表現反而使得performance下降。 * 因此在每一輪的client selection中必須確保所使用到的data diversity 2. 夠過實驗TOPIC4可以發現，在確保每個client選擇總次數相同下，不均勻選擇的方式容易造成造成local optimized，同時收斂速度以及performance都沒有比較好 * 因此訓練過程確保每個client足夠均勻被選擇很重要 * EXPERIMENT: * [TOPIC8-1, 每一輪選的iid數量相同情況下，變動non-iid數量](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPIC8-1-%E6%AF%8F%E4%B8%80%E8%BC%AA%E9%81%B8%E7%9A%84iid%E6%95%B8%E9%87%8F%E7%9B%B8%E5%90%8C%E6%83%85%E6%B3%81%E4%B8%8B%EF%BC%8C%E8%AE%8A%E5%8B%95non-iid%E6%95%B8%E9%87%8F>) * [TOPIC2, 不同client selection pattern(前期後期數量不同) ](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPIC2---%E4%B8%8D%E5%90%8Cclient-selection-pattern%E5%89%8D%E6%9C%9F%E5%BE%8C%E6%9C%9F%E6%95%B8%E9%87%8F%E4%B8%8D%E5%90%8C-uni10ascdes>) * [TOPIC3, 前期全部選iid/non-iid;後期全部選non-iid/iid](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPIC3---%E5%89%8D%E6%9C%9F%E5%85%A8%E9%83%A8%E9%81%B8iidnon-iid%E5%BE%8C%E6%9C%9F%E5%85%A8%E9%83%A8%E9%81%B8non-iidiid-uni10noniidiidiidnoniid>) * [TOPIC4, 前期選non-iid並多選一點，後期選iid並選少一點](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPIC4---%E5%89%8D%E6%9C%9F%E9%81%B8non-iid%E4%B8%A6%E5%A4%9A%E9%81%B8%E4%B8%80%E9%BB%9E%EF%BC%8C%E5%BE%8C%E6%9C%9F%E9%81%B8iid%E4%B8%A6%E9%81%B8%E5%B0%91%E4%B8%80%E9%BB%9E-noniid_20_iid_1noniid_20_iid_3noniid_20_iid_5>) * 常見處理手段: * lyapunov: * (client number那篇peper) * how to ensure the fairness selection under the battery constraint? 7. **mislabel** * mislabel會導致model往非正確方向訓練而降低performance * 因此要如何避免選擇mislabel client * 常見手段: * 利用test dataset訓練的model來算期在每個dataset中的loss ### Related work to overcome these challenge 1. **optimization method**: 1. offline client selection: 只有在最一開始選擇 paper~ 2. online client selection: 每一輪都重新選擇一次 paper ~ * 缺點: 1. offline會有overfit問題且對於變動環境沒有堤共好的機制來應付 2. offline與online方式都是基於model出各項因素之間關係來做討論，但在FL中這樣的假設並不夠準確。且在不知道環境的變動機率分布下也很難去model 2. **game theory method**: 1. Non-cooperative game: paepr~ 2. Auction: paper~ 3. Coalition game: paper~ * 缺點: 與optimization method一樣，基於model出各項因素之間關係來做討論，但在FL中這樣的假設並不夠準確。且在不知道環境的變動機率分布下也很難去model 3. **reinforcement learning based**: 又可以在細分為multu-armed bandit及DRL(deep reinforcement learning) 1. multu-armed bandit: * paepr~ 2. DRL: * paper~ * 優點: 1. reinforcement learning沒有明確的定義出client contribution/score/quality，並且透過探索及學習方式來找到一個更好的score function/policy，因此相比前面兩類方式更接近實際應用。此外這樣邊探索邊學習的方式也賦予model更好的generalization，對環境的變化以及不同client情況有更好的適應性。 * 缺點: 1. generalization(DRL): 大部分DRL採用linear layer，其限制了state space dimension，而這樣的設定讓訓練好的DRL model很難應用在其他FL training中，變成每次FL learning前都必須先經過DRL traing(此過程也是在進行FL)，這樣做法不實際並使RL實際應用受到限制解決: 使用attention layer(可以有dynamic state space) 2. exponential action space(DRL and MAB): client selection問題可以看成optimal subset problem，因此RL agent的action space是$O(2^N)$。而RL本質就是一種探索優化過程，在這樣exponential action space下會造成RL training的學習效率非常低難以學習解決: 採用sequential/continuous action(policy based，連續從policy選取k個client作為此輪selection)或first-k action(valued based，以Q-value最高的k個client作為此輪selection or MAB)此能讓action space降到$O(N)$ * paper~ ## re-model the problem * 由於網路環境以及行動裝置資源管理都是由網路供應商以及硬體或韌體層來管理，這讓使用者(包含client以及server)無法直接的控制transmission power以及cpu frequence，同時行動裝置是多工處理造成每個時段client可運用資源也變得難以在offline處理，因此把問題轉換成online型式 * P1-2: $\max \sum_{t=1}^{T} \Delta acc^t_S - \sum^{T}_{t=1}(L^t)$ 1. $a^t_i \in {0,1},\forall i,t$ 2. $\sum_{t=1}^{T}E_i^T \le B_i,\forall i$ * $\Delta acc_t = acc^t_S - acc^{t-1}_S$ * 每一輪的client selection目標(online): * P2: $\max_{S_t \subseteq N} \Delta acc^t_S - \max_{i \in S_t} l_i^t$ * $l_i^t$以及$\Delta acc^t_S$都是在結束後我們才有辦法得知，而client selection發生於前，所以這兩項目前只能用**預估值**(怎麼預估後面會講) * P2-2: $\max_{S_t \subseteq N} \hat{\Delta acc^t_S} - \max_{i \in S_t} \hat{l_i^t}$ * $\hat{\Delta acc^t_S}$ ****: 時間t，針對S集合所產生accuracy progress預估 * $\hat{l_i^t}$ : 時間t，針對client i完成訓練並回傳的latency預估 ### 1. fairness & battery aware model * 接著經過前面的討論，fairness是一個同時可以確保收斂速度以及accuracy的因素，因此我們必須確保client被**選擇的次數相同**同時**均勻選擇**。 * 首先我們可以定義在t時間client i的virtual queue $Q^t_i$ (可以看成client多久沒有被使用過了，因此當client queue越大表示我們越有動力要去選擇他) * $Q^{t+1}_i = Q^t_i + \beta - a_i^t , Q^0_i=0,\forall i$ * $\beta$ 代表每個client被選的頻率 * $a_i^t$表示client i在time t是否有被選擇到 * 但在此問題中，由於每個client都有不同大小battery以及不同功耗，因此每個client設定相同$\beta$不合理 * 此會造成擁有較少能量次數的client雖然在前期與其他client擁有相似選擇次數，但訓練中途就沒有電無法繼續參與訓練。 * 到了後期由於缺乏其所提供資料使得後期model會有local optimized可能。 * client的耗電量是動態改變(剩下電量隨著時間變化)，為一個隨著時間t變化的值。記為$\beta_i^t$ * $Q^{t+1}_i = Q^t_i + \beta_i^t - a_i^t, Q^0_i=0,\forall i$ * $\beta_i^t = \frac{\hat{\varphi^t_i}}{\sum_{i=1}^{N}\hat{\varphi^t_i}}$ * $\hat{\varphi^t_i} = \frac{RemaindBattery_i}{\hat{E^t_i}}$ * $\hat{\varphi^t_i}$: 預估還可以執行的次數 * $\hat{E^t_i}$: 預估每一次local traing所花的能量 * 定義Lyapunov function為$L(t) = \frac{1}{2} \sum_{i=1}^{N}(-{Q^{t}_i}^2)$，如果Lyapunov function能夠stable則可以使得client selection fairness。而stablize Lyapunov function的目標式可以定義成: * Lyapunov drift ([推導](<https://hackmd.io/UQ6FiXH7TYC6rWpKvhFgTg?view#Lyapunov-drift%E6%8E%A8%E5%B0%8E>)): * $\begin{aligned} \Delta L(t) &= L(t+1)-L(t)\\ &= \frac{1}{2} \sum_{i=1}^{N}({Q^{t+1}_i}^2-{Q^{t}_i}^2)\\ &= \frac{1}{2} \sum_{i=1}^{N}((Q^t_i + \beta_i^t - a_i^t)^2-{Q^{t}_i}^2)\\ &\le -\sum^{N}_{i=1} Q^t_i a_i^t \end{aligned}$ * objective: $max \sum^{N}_{i=1} F_i^t$ * $F_i^t = Q^t_i a_i^t$，用$F_i^t$表示client的fairness score * NOTE: 可以看成盡可能選擇有較長virtual queue的client，較長virtual queue表示此client越久沒有被選擇到 * 結合P2的目標可以重新定義一個含有Lyapunov的目標式(Lyapunov optimization中稱作Drift-plus-penalty Expression) * P3: $\max_{S_t \subseteq N} \hat{\Delta acc^t_S} - \max_{i \in S_t} \hat{l_i^t} + V \sum^{N}_{i=1} F_i^t$ * V: 是一個參數，用來調整fairness與原問題之間的平衡。([理論分析](< http://cslabcms.nju.edu.cn/problem_solving/images/c/c0/2018-zhao.pdf>) ) ### 2. accuracy progress prediect model * **overview** * 是否能夠model出client的公開資訊以及歷史紀錄與其所能產生accuracy progress之間關係? * 有哪些資訊我們在model時必須納入考量? * 要怎樣去設計我們的model?使我們可以很好的用client的資訊來得出預估accuracy progress * **有哪些資訊我們在model時必須納入考量?** 1. 每一輪參與訓練client的**data size**越大，則收斂速度以及accuracy都會提升 * EXPERIMENT: [TOPIC6-1](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPIC6-1-%E5%90%8Cdistribution%E5%8F%8Aclient-selection-method%E4%B8%8B%EF%BC%8C%E4%B8%8D%E5%90%8Cclient-data-size%E6%AF%94%E8%BC%83>) * 要考慮data size同時也可以觀察到隨著data size增加也會有邊際效應產生 2. 每一輪參與的**client number**越多或是每一輪**total traing data size**越多，收斂速度越快且accuracy越高，但同時也可以觀察到隨著client數量增加會有邊際效遞減 * EXPERIMENT * client number: [TOPIC1, 不同client selection number](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPICE1---%E4%B8%8D%E5%90%8Cclient-selection-number-uni1uni5uni10uni20all>) * total traing data size: [TOPIC7-1, 同一種selection mechanism下，不同total data量所帶來影響](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPIC7-1-%E5%90%8C%E4%B8%80%E7%A8%AEselection-mechanism%E4%B8%8B%EF%BC%8C%E4%B8%8D%E5%90%8Ctotal-data%E9%87%8F%E6%89%80%E5%B8%B6%E4%BE%86%E5%BD%B1%E9%9F%BF>) * marginal utility: [topic7-2, total data相同下，client number不同情況下](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPIC7-2-total-data%E7%9B%B8%E5%90%8C%E4%B8%8B%EF%BC%8C%E4%B8%8D%E5%90%8C%E5%90%8C%E4%B8%80%E7%A8%AEselection-mechanism%E7%9A%84%E5%BD%B1%E9%9F%BF>) * 雖然越多越好，但同時增加client也會一定程度降低一點accuracy，因此client數量也必須考量 * ie. acc應該要是一個隨著client而增加但同時具有邊際效應產生 3. client的**mislable**會造成accuracy下降 * 這邊可以利用[[DLR+21](<https://ieeexplore.ieee.org/document/9647925>)]中提出的方式: 在FL開始前預先使用global testing dataset訓練一個簡單的global testing model，並用此test model再local上面算loss以此做為mislabel的代替 4. client的**data quality** * EXPERIMENT: * [TOPIC1, 不同client selection number](<https://hackmd.io/DmHhn746TjG6oAXhlhf-gA?view#TOPICE1---%E4%B8%8D%E5%90%8Cclient-selection-number-uni1uni5uni10uni20all>) 1. 可能方法(一): 在FL開始前預先使用local training dataset訓練一個簡單的local testing model，並用這些local testing model算於global testing model的accuracy，並以此作為代替 2. 可能方法(二): 每一輪有參與訓練的client紀錄其結果(例如: loss) * NOTE: 但是這裡必須考量到loss以及accuracy的增長會隨著model準確度提升而下降，因此過去的歷史資料是否還有存在價值必須考量!!! 5. **fairness score** * **要怎樣去設計我們的model?** * 在client set($S \subset N$)中的client i有(1)**data size $\vert D_i \vert$** (2)**mislabel $M_i$** (3)**data quality $Q_i$** (4) **fairness $F_i$** * client i預估的accuracy progress，記作$\hat{\Delta acc^t_i}$ * $\hat{\Delta {acc}_i} = \log(\vert D_i \vert^{\theta_1} M_i^{\theta_2} Q_i^{\theta_3}) + \theta_4 F_i$ * 用log來把前三個乘積包起來可以呼應實驗中data size會有marginal utility * $F_i$不包在log是因為前三個可以看成"sample總量 * sample質量"，而$F_i$則跟client比較有關與單位資料量沒有關係 * client set $S \subset N$所可以產生的accuracy progress，記作$\hat{\Delta acc^t_i}$ * $\hat{\Delta {acc}_S} = \frac{\sum_{i \in S} \hat{\Delta {acc}_i}}{\log(\vert S \vert)}$ * NOTE: 這裡用log表示了邊際效應，但也可以用其他函數代替可以在研究 1. 直接把所有CLIENT個別預估的acc相加然後放進一個log裡面(但這樣做的缺點是假如總量acc預估值相同下，只有一個client與分散到多個client的預估值會是一樣的，but實驗中看起來應該是境可能放在一個會比較好) * objective function * P4: $\max_{S_t \subseteq N} \hat{\Delta acc^t_S} - \max_{i \in S_t} \hat{l_i^t}$ * NOTE: 這邊把fairness score直接放在$\hat{\Delta acc^t_S}$裡面，這樣原本P3中$\sum^{N}_{i=1} F_i^t$這一項會變成$\frac{\sum^{N}_{i=1} F_i^t}{\log(\vert S \vert)}$ * 不合理: 1. 由原本lyapunov設計推導出來的fairness score多除上了$\log(\vert S \vert)$，這間接讓fairness與latency之間關係(ie.P3的$V$)變成變動的，隨著所選的數量增加而下降 * 合理: 1. 還是遵循著盡可能選擇virtual queue比較長的(比較沒有被選到)的原則 2. fairness score也應該隨著client number有邊際效應。fairness這邊設計思維是用它來控制global層面的accuracy，從TOPIC1實驗看到隨著fairness score越高，最終再accuracy以及covergence speed都有邊際遞減發生，因此也合理 ## ALGORITHM * challenge to solve P3 1. **在accuracy progress prediect model中的$\theta_1$、$\theta_2$、$\theta_3$和$\theta_4$是一個超參數要如何決定此值?** * 傳統optimization paper中此值是由實驗者給定，這樣的設定限制了其真實環境的通用性(generalization)，很可能potential clients變化或是FL task變化而有很大performance差別 * 使用RL/ML with DNN model來預測，但我認為這會產生兩個缺點: 1. DNN這樣的模型需要足夠好品質的訓練資料集來訓練，而FL中不同task之間的變化性以及資料關聯性(完成一次FL learning，過程中每次selection前後都會有高度相關性)讓取得iid資料非常難 2. 透過實驗可以發現，相同training client在不同訓練階段會展現出不同的訓練效能(accuracy progress)，這讓DNN model的維度從原本一次client selection變成一次是一個完整的FL learning(ie. 計算訓練資料量的單位從一次client selection變成一次一個FL learning) * 因此具有一個快速學習同時動態調整的learning方式才是更適合的方式 * [ridge regression](<https://hackmd.io/s5vE5NGHR4aK1dxLVQQFNA?view>) * 是一種linear regression，相比於DNN model使用backward一步一步慢慢優化模型，它可以很直接的使用矩陣運算求得model同時可以藉由控制回歸資料多寡(時間前後)來讓model更快的適應變化 * application * $\hat{\Delta {acc}_i} = \log(\vert D_i \vert^{\theta_1} M_i^{\theta_2} Q_i^{\theta_3}) + \theta_4 + F_i = \theta_1 \log(\vert D_i \vert) + \theta_2 \log(M_i) + \theta_3 \log(Q_i) + \theta_4 F_i$ $\Rightarrow$轉換成一個線性回歸問題 * 根據[ridge regression](<https://hackmd.io/s5vE5NGHR4aK1dxLVQQFNA?view>)中的format，$x_i^t$和$y_i^t$定義成 * $x_i^t = [log(\vert D_i^t \vert), log(M_i^t), log(Q_i^t), F_i]$ * $y_i^t =$ $\Delta {acc^t_i}_i$ 2. **how to get $\Delta {acc^t_i}_i$ ? client contribution issue** * client contribution: 每次FL learning後只會得到一個經由test dataset計算來的accuracy值，其包含了此輪參與訓練client的共同成果，要如何得知每一個client對這次訓練的貢獻值? * [GTG-Shapley](<https://arxiv.org/abs/2109.02053>) * [HTZ+20](<https://arxiv.org/abs/2011.06830>)針對**influence-based method**([WEZ+19](<https://arxiv.org/pdf/1909.08525>))、**Reputation quanty method**、**Shapley value**他們針對mislabel client的分辨能力，Shapley value有非常好的表現 * ![螢幕擷取畫面 (166)](https://hackmd.io/_uploads/SyhO-wpZ0.png) * ![螢幕擷取畫面 (167)](https://hackmd.io/_uploads/HkUKZw6bR.png) * ![螢幕擷取畫面 (168)](https://hackmd.io/_uploads/HylcZw6-A.png) * 但是Shapley value的計算量是$O(2^N)$，因此**GTG-Shapley**提出了一個$O(Nlog(N))$的演算法來使得計算量大幅下降情況下又能夠得到接近真實Shapley value * 原理: 利用隨著client數量增加contribution會快速下降的特點，我們只需要計算前幾個set就可以，隨著set變大contribution接近零就沒有意義不需要計算 3. 如何預估$\hat{l_i^t}$和$\hat{E_i^t}$ * * RELATED WORK: 以MAB/contextual MAB方式針對latency預測的: [[XQG+20](<https://arxiv.org/abs/2007.02315>)]、[[HLW+20](<https://arxiv.org/abs/2011.01783>)] 4. **P4 is not the easy problem(P3非binary integer programming)** * 由於latency那一項限制了可能的組合(ie 假如選定特定client並以其latency作為最大允選latency，那剩下可以加入的clients範圍就會被限制住)，因此可以把P3化成N個sub-problem P3-sub，每一個的constraint多了一個最大latency限制 * P3-sub的問題就變成: 在有限的client(latency小於該輪設定最大latency)中，找到maxized score的組合 1. 可以先將所有client依據$\hat{\Delta {acc}_i}$ sort由大排到小 2. 由大開始往小增加集合大小，並記錄此client set $S_j$預估$\hat{\Delta {acc}_{S_j}}$，直到$\hat{\Delta {acc}_{S_j}}$變小停止該輪 * time complexity: $O(n\log(n)+n^2)$ * **ALGORITHM** ![螢幕擷取畫面 (170)](https://hackmd.io/_uploads/SJtRU9abR.png) 1. initialize * $A^0 = \lambda I_{d \times d}$ * $B^0 = 0_{1 \times d}$ (zero vector) 2. client selection * predict each client's $\hat{\Delta {acc^t_i}}$ by $x^t_i \hat{\theta}^T$ * where observation $x^t_i = (log(\vert D_i^t \vert), log(M_i^t), log(Q_i^t), F_i^t)$ * where $\hat{\theta} = {A^t}^{-1} B^t$ * predict each client's training latency * select the clients, named $S_t$ * solve the 3. Federated learning 4. use the **GTG-Shapley** to compute each selected client's contribution(accuracy progress from client. named $y_i^t$) * input $\omega^{t-1}$, $\{ \omega^{t}_i \}$ * NOTE: client set $S$所得到的testing accuracy要先乘上$\log(\vert S \vert)$ 6. update the accuracy progress prediect model $(A^t, B^t)$ to $(A^{t+1}, B^{t+1})$ by: * for each client i selected in this round, do $A^{t+1} = A^{t} + \sum_{\forall i \in S_t } {x_i^t}^T \times x_i^t$ * for each client i selected in this round, do $B^{t+1} = B^{t} + \sum_{\forall i \in S_t } {x_i^t}^T y_i^t$ 7. repeat 2 ~ 6 ## EXPERIMENT ### SETTING 1. reference 1. [DLR+22](<https://ieeexplore.ieee.org/document/9647925>) 1. random 50% of them have mislabeled training data samples, and a random 50% of them have randomly generated non-IID data distribution 2. data size of clients is generated uniformly within the range [100,1000] 3. emulated candidate clients have different training data size, mislabel rate, and data distribution 2. [HTZ+20](<https://arxiv.org/abs/2011.06830>) 1. When the attackers train their local models, they inject data noise by flipping the label with a probability p. The label is flipped with one of the other 9 labels randomly. 2. The flipping probability p is varied between 10%, 30%, 50% and 100%