---
# System prepended metadata

title: '[DCL+21]Matching-Theory-Based Low-Latency Scheme for Multitask Federated Learning in MEC Networks'

---

# Matching-Theory-Based Low-Latency Scheme for Multitask Federated Learning in MEC Networks

在現有MEC架構下，edge node可以有足夠資源來進行FL的aggregate同時其也足夠接近IoT device。藉由可以減少communication時間。

此篇主要貢獻:
1. 使用many-to-one( hospitals–residents) matchong problem來formulate 多個client與多個server間的配對問題
    * client只能assign給一個server，但一個server可以assign給多個client
2. 使用incomplete preference list(IPL)來描述matching中每個player的preference
    * 在IoT環境下，不可能每個client與server都能夠完整了解全部人的狀況並且做出preference list for全部對象，因此更為實際的必會是incomplete
    * 假設preference會是strict order
3. 追求low-latency 
    * 提出的algorithm目標是minimize整體multi-task FL的訓練時間(objective)

MODEL(TIME):
1. total time = computation time + communication time
2. computation time
    ![螢幕擷取畫面 (291)](https://hackmd.io/_uploads/BJQrvWwSa.png)
    * 紅色: 表示在要達到**目標accuracy下所需要local update次數**
        (引用paper: *Federated learning over wireless networks: Optimization model design and analysis*)
    * 每round時間則是 **每輪update所需資料量*不同model隊單位資料處理量/node計算能力**
        (引用paper: *Self organizing federated learning over wireless networks: A socially aware clustering approach*)
3. communication time
![螢幕擷取畫面 (294)](https://hackmd.io/_uploads/SySdFWvHT.png)
    transmission rate: ![螢幕擷取畫面 (292)](https://hackmd.io/_uploads/B1OYF-DBp.png)



PROBLEM:
* <font color="#f00">這裡我覺得不是很合理有點怪怪的，這讓我感覺只是一個特別掰出來的object function用來衡量是不是他所提出matching方式有做到很好。但我覺得應該事先提出optimized problem再來決定方式設計好不好</font>
    * <font color="#f00">此處的latency是全部相加，但實際狀況是只需要考量最慢的那個人就好</font>
    * <font color="#f00">此處考量的是所有model最終一起訓練時間，但實際應該該在乎的是在一個model中，是否有一個stragger且可能有些model本來就練比較久，應針對對個別model來reduce latency</font>
![螢幕擷取畫面 (295)](https://hackmd.io/_uploads/ry1P9bPB6.png)
![螢幕擷取畫面 (296)](https://hackmd.io/_uploads/Sk7v5Wvr6.png)
* r θi is introduced, which is denoted as the willingness for participation of the ith device. Intuitively, θi is determined by the remained energy percentage, i.e., θi = 1 when δ ≤ ci and vice versa.
1. **每輪global round執行一次matching**
2. **每輪global round都optimized，則整體latency也optimized**
3. **只要local update次數足夠就可以保證最終global有足夠accuracy**
    (引用paper: 
        1. Communication-efficient federated deep learning with layerwise asynchronous model update and temporally weighted aggregation
        2. Federated learning based mobile edge computing for augmented reality applications)

MATCHING:
1. IPL in the HR game
2. 作者提到，雖然演算法**允許每輪都重新配對，但這樣的配對會造成需要重新更新local端的model以及相關設定耗時間**(hyperparameter及loss function等等)，因此我們要去找一個"stable matching"確保不會一值變動
    1. stable in IPL
        * 簡單講不存在一組pair能夠block matching。而block表示裡面的player能夠找到更好的pair於現有情況中
    
        ![螢幕擷取畫面 (297)](https://hackmd.io/_uploads/ByvpCZvSa.png)
 


ALGORITHM:
1. preference如何設定:
    1. **client對server**:
        * 依據每個client與server的communication time(越小越喜歡)
        * client的energy resource必須大於一個值for server model(因為對client來說運算需要耗能，而行動裝置很在意電量，這對client是一個重要的考慮因素)
        ![螢幕擷取畫面 (287)](https://hackmd.io/_uploads/HkOCEZvr6.png)
             * com - > communication
             * N_i -> IoT device

    2. **server對client**: 
        * 依據每個client對server model的computation time(越小越喜歡)
        ![螢幕擷取畫面 (286)](https://hackmd.io/_uploads/HJfc4WPrp.png)
            * cmp -> computation
            * j -> edge node(server)
2. 演匴法流程(沒有看)
![螢幕擷取畫面 (288)](https://hackmd.io/_uploads/H1YzIWDST.png)


其他:
<font color="#f00">此篇看起來實際沒有解決non-iid問題，在分配時所使用到preference list是依據時間等因素來排而非data distribution</font>

