Async-HFL：階層式 IoT 網路中高效率且穩健的非同步聯邦學習

原文：Async-HFL: Efficient and Robust Asynchronous Federated Learning in Hierarchical IoT Networks，arXiv:2301.06646v4，2023-04-10，IoTDI 2023。
來源：2301.06646v4.pdf；翻譯日期：2026-10-05。
翻譯範圍：18 頁，包含正文、演算法、表格、圖說、致謝、62 筆參考文獻及附錄 A 的證明文字。數學符號保留原義；附錄冗長的連續代數推導以原文圖頁完整保留，並翻譯每段推導說明。原圖內的英文標籤仍保留，中文圖說與解讀另列。
與研究題目的關係另見 Async-HFL與主動式網路報修的關聯評估；該筆記是分析，不是論文原文。

作者與出版資訊

Xiaofan Yu、Harsh Vardhan、Quanling Zhao、Emily Ekaireb、Xiyuan Zhang、Arya Mazumdar、Tajana Šimunić Rosing：美國加州大學聖地牙哥分校（UCSD），La Jolla，California。Ludmila Cherkasova：Arm Research，San Jose，California。

聯絡信箱依作者順序：x1yu@ucsd.edu、lucy.cherkasova@gmail.com、hharshvardhan@ucsd.edu、quzhao@ucsd.edu、eekaireb@ucsd.edu、xiyuanzh@ucsd.edu、arya@ucsd.edu、tajana@ucsd.edu。

允許為個人或課堂用途免費製作本文全部或部分的數位或紙本副本，前提是不得以營利或商業利益為目的製作或散布，且副本首頁必須載有本聲明及完整引用。本文第三方內容的著作權必須受到尊重。其他用途請聯絡著作權人／作者。

IoTDI ’23，2023 年 5 月 9–12 日，美國德州 San Antonio。© 2023 著作權由著作權人／作者持有。ACM ISBN 979-8-4007-0037-8/23/05；DOI：10.1145/3576842.3582377。

CCS 分類：電腦系統組織 → 感測器網路；計算方法 → 機器學習。

關鍵字：聯邦學習、階層式感測器與 IoT 網路、非同步聯邦學習。

ACM 引用格式：Xiaofan Yu, Ludmila Cherkasova, Harsh Vardhan, Quanling Zhao, Emily Ekaireb, Xiyuan Zhang, Arya Mazumdar, and Tajana Šimunić Rosing. 2023. Async-HFL: Efficient and Robust Asynchronous Federated Learning in Hierarchical IoT Networks. In International Conference on Internet-of-Things Design and Implementation (IoTDI ’23), May 9–12, 2023, San Antonio, TX, USA. ACM, New York, NY, USA, 18 pages. DOI: 10.1145/3576842.3582377。

摘要

近年來，聯邦學習（Federated Learning，FL）作為一種在裝置上執行的分散式學習典範，受到日益增加的關注。然而，要在真實世界具有階層結構的物聯網（Internet-of-Things，IoT）網路中部署 FL，仍有多項挑戰需要處理。既有研究雖然提出各種方法，分別考量資料異質性、系統異質性、非預期的落後節點（stragglers）及可擴展性，卻沒有任何一項研究提供系統性的解決方案，同時處理階層式且不可靠 IoT 網路中的所有挑戰。

本文提出非同步階層式框架 Async-HFL，在常見的三層 IoT 網路架構中執行 FL。面對差異極大的網路與系統處理延遲，Async-HFL 在閘道與雲端兩層皆採用非同步聚合，避免漫長的等待時間。為充分發揮 Async-HFL 在系統異質性與落後節點存在時的收斂速度潛力，我們在閘道層設計裝置選擇，在雲端層設計裝置與閘道的關聯配置。裝置選擇模組即時挑選資料多樣且速度快的邊緣裝置，觸發本地訓練；裝置與閘道關聯模組則每隔若干雲端 epoch，定期決定有效率的網路拓樸。兩個模組都滿足頻寬限制。

我們以 ns-3 為基礎的大規模模擬，以及來自 NYCMesh 的網路拓樸，評估 Async-HFL 的收斂加速效果。結果顯示，相較於具有客戶端選擇機制的先進非同步 FL 演算法，Async-HFL 依實際經過時間衡量的收斂速度快 1.08–1.31 倍，總通訊成本最多節省 21.6%。我們也在實體部署上驗證 Async-HFL，觀察到它在非預期落後節點出現時仍能穩健收斂。

1. 緒論

在無所不在的 IoT 裝置中嵌入智慧，能執行更複雜的任務，進而使個人醫療照護 [9]、智慧城市 [29] 與自駕車 [6] 等廣泛應用受益。為使大規模網路能進行分散式學習，FL 已成為一種前景看好的典範。學習流程始於中央伺服器將全域模型分發至選定的裝置。接著，各裝置利用本地資料集進行梯度下降訓練，並將更新後的模型傳回伺服器。最後，中央伺服器聚合收到的模型，取得新的全域模型。邊緣裝置不公開本地資料集，只分享更新後的模型。因此，FL 能在保護使用者隱私的同時，讓分散式裝置協作學習。

FL 的經典基準是 Federated Averaging（FedAvg）[42]，它使用同步全域聚合：中央伺服器必須等到最慢的裝置回傳，才進行聚合，因此受到無法接受的長延遲或落後節點拖累。近期半非同步 FL 的研究 [12, 15, 44, 52, 59]，藉由聚合一定期間內到達的更新，並非同步處理遲到的模型更新，緩解此問題。然而，在異質且不可靠的網路中，半非同步機制的等待期間難以調整，仍然會受到更新不及時的影響。

對真實世界的 IoT 網路而言，整體系統的多樣性妨礙了有效率且穩健的 FL 部署。大量實際部署採階層式組織，例如 NYCMesh [2]、HPWREN [1]。這些架構都可簡化成圖 1 所示的三層結構：雲端伺服器、閘道聚合器、邊緣裝置。雲端層提供資源充足、處理能力強大的伺服器。閘道層包含基地台與路由器，作為連接雲端與邊緣裝置的中介樞紐。最底層的邊緣裝置指感測器、智慧型手機、無人機等小型行動系統，通常受限於資源及能源。

圖 1：在具有異質延遲與不可靠網路的常見三層 IoT 網路中，執行 FL 應用的系統架構。原圖見 第 2 頁。

在異質且階層式 IoT 網路部署 FL，面臨以下挑戰：

• C1 資料分布異質性：因環境變化或使用者特性，邊緣裝置的本地資料分布可能差異極大。研究已顯示，若沒有謹慎且針對性的管理，非獨立同分布（non-iid）資料會使 FL 收斂變慢，甚至無法收斂 [30, 38, 49]。
• C2 系統特性異質性：邊緣裝置具備不同的 CPU、記憶體儲存及通訊技術。因此，圖 1 中各層計算延遲及層間通訊延遲可能差異極大。同步與半非同步 FL 會承受較長等待時間。
• C3 非預期落後節點／裝置退出：能源不足、電路問題或無線干擾，讓 IoT 網路每一層都常有落後節點。若管理不當，學習流程可能被延誤，甚至完全停住。
• C4 可擴展性：直接把兩層演算法延伸到三層以上的階層網路，可能導致顯著的效能退化，例如模型不收斂或通訊負載增加 [40]。如何在擴展階層架構時保留效益並避免不希望的退化，仍是活躍研究議題。

既有研究雖已探討如何在資料異質性 [30, 38, 49]、系統異質性 [11, 33, 37]、非預期落後節點 [43]，及為提高可擴展性而設計的階層式 FL [20, 60] 中，改善一至兩項因素下的 FL 收斂，卻沒有研究為階層式且不可靠的 IoT 網路提供能同時處理全部挑戰的系統性方案。本研究提出首個端到端框架，利用非同步階層式 FL 演算法與系統管理設計，增強效率及穩健性，處理 C1–C4。

本文提出 Async-HFL，讓三層且不可靠的 IoT 網路執行 FL。

在演算法方面，Async-HFL 在閘道與雲端皆採非同步聚合，亦即一收到更新模型便立即聚合。因此，快的邊緣裝置不用等待較慢的同儕；落後節點下載最新全域模型後，也能輕易跟上。相較於把既有兩層非同步 FL 直接延伸至三層，Async-HFL 增加中介閘道聚合層，穩定收斂並節省通訊成本。

在系統管理方面，我們提出兩個模組，改善非同步演算法在系統異質性與落後節點存在時的效能：閘道層裝置選擇，以及雲端層裝置與閘道關聯。閘道層即時決定觸發哪些裝置本地訓練；雲端層則管理網路拓樸，即哪個裝置連到哪個閘道，以提升較長期的效能。兩個模組都建立並求解整數線性規劃，聯合考量資料異質性、系統特性及落後節點。對資料異質性，我們受到線上 coreset 選擇 [57] 啟發，定義學習效用指標，量化裝置梯度的親和性及多樣性。對系統異質性，我們監控各閘道與裝置鏈路的延遲，以及可用連線。

Async-HFL 與過去研究的不同之處在於：它考量比單純損失值更細緻的梯度多樣性資訊，既有先進非同步客戶端選擇演算法 [61] 使用的則只是損失值；它也在不同層級結合裝置選擇及網路拓樸管理，協作最佳化階層式、不可靠 IoT 網路中的模型收斂。為降低通訊額外成本，我們在暖機期間收集所有裝置的梯度，執行主成分分析（PCA），並把 PCA 參數分發給所有裝置。訓練期間只交換梯度的主成分。

本研究的貢獻如下：

1. 辨識階層式且不可靠 IoT 網路的獨特挑戰，在閘道及雲端皆使用非同步聚合，並正式證明 Async-HFL 在 non-iid 資料分布下的收斂。
2. 提出根據梯度多樣性建立的學習效用指標，更細緻地量化資料異質性，指引 Async-HFL 的決策。
3. 結合分散式閘道裝置選擇與雲端裝置閘道關聯模組，在資料、系統異質性與落後節點存在時，共同最佳化模型收斂；利用 PCA 壓縮梯度交換降低通訊額外成本。
4. 以 ns-3 [3] 和 NYCMesh [2] 為基礎實作並評估不同網路特性下的收斂加速與通訊節省。相較於先進非同步 FL，實際收斂時間加速 1.08–1.31 倍，總通訊節省最多 21.6%。此外，在 Raspberry Pi 4 與 CPU 叢集實體部署上，展示面對落後節點的穩健收斂。

與其他 FL 研究的關係：Async-HFL 著重階層式 IoT 網路的系統變動及潛在落後節點，因此與個人化 [47]、剪枝 [35]、遮罩 [36] 等 FL 技術正交。可以與這些方法結合，但不是本文的焦點。

本文其餘部分安排如下：第 2 節回顧相關研究；第 3 節介紹背景及模型；第 4 節提出動機研究；第 5 節詳述 Async-HFL；第 6 節說明實驗設定及結果；第 7 節總結全文。

2. 相關研究

本節回顧先進研究，並在表 1 中根據 C1–C4 比較既有框架。

同步 FL：以 FedAvg 為基礎，大量研究從理論及實務角度探討資料、系統異質性下的同步 FL [11, 30, 33, 38, 43, 49]。透過各種理論工具 [8, 31, 45, 48, 55, 56]，能精心設計客戶端／裝置選擇流程，緩解異質性。多數工作僅考量資料與計算延遲異質性；TiFL [11]、Oort [33]、PyramidFL [37] 則提出通訊延遲差異，實作智慧客戶端選擇，平衡統計效用與系統效用。然而，上述研究都考量資料中心中的 FL；不可靠 IoT 網路的長延遲及落後節點，會使同步方法的表現不理想。

非同步 FL：相較於同步機制，非同步機制在不穩定網路、尤其有數百萬裝置時，收斂較快 [27]。近年非同步 FL 研究不斷增加，焦點包括客戶端選擇 [16, 23, 28, 61, 62]、權重聚合 [51, 51, 58] 及傳輸排程 [34]。半非同步機制用於聚合緩衝的更新 [12, 15, 44, 52, 59]。然而，如何在階層式、異質的 IoT 系統充分運用非同步特性，仍未獲處理。

表 1：Async-HFL 與既有研究的比較。

階層式 FL：閘道先執行中介聚合，再把本地模型送到雲端，降低閘道與雲端之間的回程通訊 [40]。多項研究建立客戶端關聯與資源配置問題，在同步階層式 FL 中共同最佳化計算及通訊效率 [4, 5, 40, 41]。近期研究考量移動性 [20]，以及針對新資料的動態階層聚合 [60]。SHARE [18] 把裝置選擇、裝置與閘道關聯拆成兩個子問題，再共同最小化通訊成本、塑造聚合器資料分布，以提高全域準確率。RFL-HA [50] 在子叢集內同步聚合，叢集首領（閘道）與中央雲端間非同步聚合。上述方法都在系統中採用同步聚合，因此受到落後節點影響。

唯一研究非同步階層式 FL 的工作是 [51]。相較之下，我們提供系統性框架，加入管理模組，即時適應並最佳化 C1–C4 下的收斂。

3. 背景

本節介紹學習模型（3.1）、系統模型（3.2），以及既有兩層非同步 FL 的常用技術（3.3）。表 2 列出符號；圖 2 是範例部署，後續介紹模型時會引用。

3.1 學習模型

假設感測裝置 $i$ 收集資料點 $(x_i,y_i)\sim\mathcal D_i$，其中 $\mathcal D_i$ 代表裝置 $i$ 的底層資料分布。假設所有分布來自同一領域。當各裝置 $i\ne j$ 的 $\mathcal D_i\ne\mathcal D_j$ 時，即出現 non-iid 資料。實務上底層分布未知，各裝置只能存取有限的 $n_i$ 筆樣本。不同裝置、不同時間的 $n_i$ 可不同；為簡化表示，省略時間下標。

目標是 FL 的典型目標：學得統一模型 $\omega\in\mathbb R^d$，部署於所有分散式裝置。也可結合個人化模型，但超出本文範圍。損失函數 $\ell(\omega;x_i,y_i)$ 衡量模型在樣本上的表現誤差。我們最小化所有裝置的經驗風險：

$L_N$ 是中央雲端的全域損失，$L_i$ 是感測裝置的損失。

表 2：問題定義的重要符號。

3.2 系統模型

網路拓樸：在階層式 IoT 網路，中央雲端記為 $\mathcal C$，$[n]=\{1,\ldots,n\}$。$\mathcal G=[G]$ 為閘道／基地台集合，$\mathcal N=[N]$ 為大量靜態部署感測裝置集合。所有閘道都有到中央雲端的可行路徑；一個感測裝置可能到得了多個閘道。可達性受無線技術距離限制、感測裝置故障、網路骨幹故障等因素限制。將這些因素納入矩陣 $J_t\in\mathbb Z^{N\times G}$，表示實際時間 $t$ 的可行配對：

J_{t,ij}=\begin{cases}1,&\text{感測器 }i\text{ 與閘道 }j\text{ 在 }t\text{ 可連接}\\0,&\text{其他情況。}\end{cases}\tag{2}

訓練時，每個感測器同時只關聯一個閘道。該閘道觸發其本地訓練，裝置需把結果回傳同一閘道；但感測器可以在兩次聚合之間改連其他閘道。用同樣形狀的 $I_t\in\mathbb Z^{N\times G}$ 作即時連線的決策變數：

I_{t,ij}=\begin{cases}1,&\text{感測器 }i\text{ 在 }t\text{ 連接閘道 }j\\0,&\text{其他情況。}\end{cases}\tag{3}

圖 2 中裝置 2 可以連到閘道 1 與 2，但當輪只與閘道 1 通訊，因此 $J_{t,21}=J_{t,22}=1$，$I_{t,21}=1$，$I_{t,22}=0$。

圖 2：階層式 FL 部署範例。原圖見 第 4 頁。

計算與通訊模型：計算及通訊延遲是系統異質性的主要來源。本文採通用模型；若取得更多資訊，可採更特定、參數化的 CPU／網路模型，例如 [14, 41]。我們更關注最後一跳鏈路的通訊延遲，因為這裡頻寬更受限，傳送端感測裝置的發射功率也較低。執行時量測裝置 $i$ 與閘道 $j$ 完成一輪的時間 $\tau_{ij}$，包括：閘道傳模型至裝置的下行延遲 $\tau_{ji}^D$、裝置本地訓練計算延遲 $\tau_i^C$，以及裝置回傳更新模型的上行延遲 $\tau_{ij}^U$。圖 2 的紅、藍箭頭分別表示下行、上行傳輸，綠箭頭表示本地訓練。因此 $\tau_{ij}=\tau_{ji}^D+\tau_i^C+\tau_{ij}^U$。閘道、雲端一般有較多計算資源，因此忽略它們的聚合計算延遲。

頻寬限制：頻寬限制為吞吐量／資料速率設定上限。與同步設計不同，非同步情境無法準確建模時間 $t$ 的吞吐量。因此，給定一輪延遲 $\tau_{ij}$ 及大小 $M$ 的 FL 模型，估計鏈路平均資料速率為 $R_{ij}=M/\tau_{ij}$。閘道 $j$ 所有選定裝置的總資料速率為 $R_j=\sum_{i=1}^N I_{ij}R_{ij}$。$B_j$ 為閘道最後一跳鏈路平均資料速率上限。圖 2 中裝置 1、2 都受 $B_1$ 約束，以藍色弧線表示。

3.3 兩層非同步 FL

在非同步 FL，各裝置從雲端下載最新全域模型，執行本地訓練，再將模型上傳至雲端，立即進行非同步聚合。近期演算法 [16, 54] 使用兩項常見技術。

第一，除原始損失 $L_i(\omega^i)$ 外，裝置加入正則化項，懲罰目前模型與下載的全域模型 $\omega_\tau$ 之差：

g_i(\omega^i;\omega_\tau)=L_i(\omega^i)+\frac\rho2\|\omega^i-\omega_\tau\|^2.\tag{4}

$\rho$ 是正則化權重。

第二，在雲端使用感知陳舊度的權重聚合：

\alpha_h\leftarrow\alpha s(h-\tau),\tag{5a} \omega_h\leftarrow(1-\alpha_h)\omega_{h-1}+\alpha_h\omega_{new}.\tag{5b}

$\omega_{new}$ 是新收到的模型權重，$h$ 是目前雲端 epoch。$\alpha_h$ 是常數 $\alpha$ 乘以陳舊度函數 $s(h-\tau)$。陳舊度指模型自上次全域更新以來的 epoch 差異：$h$ 是目前聚合 epoch，$\tau$ 是模型下載時的全域 epoch。陳舊度越大，模型越過時，因此應給較低重要性。這種聚合在非同步情境模擬平均流程。$s(h-\tau)$ 決定聚合的衰減係數；本文依 [54] 使用多項式函數 $s_q(h-\tau)=(h-\tau+1)^{-q}$，$q>0$。

4. 動機研究

本節在階層式、不可靠網路中檢驗既有 FL 框架，為 Async-HFL 的演算法及管理設計提供依據。

近期研究已注意客戶端選擇須考量延遲 [11, 33, 37]，但只考量資料中心的延遲分布，這與真實無線網路差異很大。實際量測顯示，無線網路具有長尾延遲分布，且高度不可預測 [46]。我們以 ns3-fl [19] 實作 FL 框架，從 NYCMesh [2] 已安裝節點的位置擷取三層拓樸，見圖 3 左。假設邊緣裝置透過 Wi-Fi 連接閘道，閘道透過 Ethernet 連接伺服器。各節點經度、緯度與高度輸入 ns-3 的 HybridBuildingsPropagationLossModel，以取得平均點對點延遲。為納入網路不確定性，每輪本地訓練在平均延遲上疊加對數常態延遲。假設所有裝置都被選中，一輪內各裝置延遲分布見圖 3 左起第二圖。模擬延遲仿照 [46] 的量測結果。

使用人體活動辨識資料集 [7]，把每位受試者的資料配置到單一裝置，形成自然 non-iid 資料。所有實驗中閘道頻寬上限設為 20 KB/s。

圖 3：左：NYCMesh 拓樸；左起第二：所有邊緣裝置一輪延遲的分布；右：NYCMesh 動機研究中，以實際經過時間衡量的收斂表現。原圖見 第 5 頁。

在此設定中，比較：使用先進延遲感知客戶端選擇 Oort [33] 的 FedAvg；雲端非同步、閘道同步聚合的 RFL-HA [50]；雲端同步、閘道依 [44] 半非同步聚合的 Semi-async；閘道僅轉送資料，把兩層非同步演算法 [16, 54] 直接延伸成三層的 Two-tier Async；以及本文提出、具有中介閘道聚合的三層 Async-HFL。

圖 3 右顯示實際時間收斂；表 3 顯示相對於 Async-HFL 的總傳輸資料量。即使使用先進客戶端選擇，FedAvg 與 RFL-HA 收斂仍顯著變慢。Semi-async 的等待期間測試 50、100、150 秒，採最佳結果。它雖可加速收斂，但達到相同 95% 準確率仍比完全非同步方法多花 0.39 倍時間。

表 3：動機研究中，達到 95% 測試準確率前的總通訊資料量，相對於 Async-HFL 的比例。

相較 Two-tier Async，三層 Async-HFL 收斂更穩定、稍快，少掉以 Async-HFL 為基準的 0.3 倍通訊負載，相當於 426 MB 或 1,498 個 MLP 模型。此增益來自中介閘道聚合：多一層「平均」不只平滑曲線，也避免不必要的來回傳輸。

除了演算法，框架管理也是關鍵。我們測試隨機選擇（Async-Random）、優先短延遲（Async-ST）的閘道裝置選擇，以及完整管理的 Async-HFL。圖 3 右顯示，精心設計模組後，Async-HFL 收斂比隨機選擇快 1.24 倍。然而，忽略資料異質性的 Async-ST 等不良選擇，可能使達到 95% 準確率所需時間增至 2.13 倍，最壞情況甚至不收斂。

5. Async-HFL 設計

5.1 概觀

為系統性處理 C1–C4，提出端到端框架 Async-HFL，特別針對階層式、不可靠 IoT 網路，提供有效率且穩健的 FL。主要差異是：以梯度多樣性的學習效用量化 non-iid 資料分布；加入策略性管理元件，即雲端裝置閘道關聯（圖 4 步驟 ①）與閘道裝置選擇（③），共同加速異質資料及系統下的實際收斂。

圖 4 逐步呈現一輪雲端聚合。為簡化，只展示一個階層分支。暖機初始化後，雲端決定底層網路拓樸，即裝置閘道關聯（①），然後向所有閘道分發最新全域模型（②）。閘道把模型分發到選定裝置（③–④）。裝置訓練 $E$ 個 epoch，回傳更新模型（⑤–⑥）。閘道立即非同步聚合新模型（⑦）。經過 $Z$ 次閘道更新後，當前閘道模型上傳雲端，進行全域非同步聚合（⑧–⑨）。

圖 4：Async-HFL 在一個階層網路分支內的逐步流程。原圖見 第 6 頁。

本節後續詳述設計：5.2 提出非同步階層演算法及收斂證明；5.3 定義量化梯度多樣性的學習效用；5.4 說明裝置選擇與裝置閘道關聯的具體設計。

5.2 非同步階層式 FL 演算法

除雲端非同步聚合外，Async-HFL 使用中介閘道層，在閘道進行 $Z$ 個 epoch 的陳舊度感知非同步聚合。相較於閘道直接轉送非同步模型更新到雲端，中介聚合降低通訊負擔，且只加入少量假設便維持收斂保證。圖 4 的④–⑦對應兩層非同步 FL，本文階層演算法則涵蓋②、④–⑨，跨越 IoT 三層。

演算法 1 呈現雲端、閘道、裝置的具體實作。雲端及各閘道執行 Cloud 或 Gateway 程序，完成初始化，並非同步觸發 Updater 執行緒進行聚合，直到達到預定 epoch 數。各感測裝置執行 Sensor 程序，以 SGD 本地求解正則化最佳化問題。過去研究按計算資源調整本地 epoch [38]，以模型品質交換較快回傳；但因 Async-HFL 採非同步聚合，且網路延遲更長、更不可預期，這類增益可能很小。因此裝置及閘道分別使用固定 $E$、$Z$。

演算法 1：非同步階層式 FL。 輸入：$\mathcal C,\mathcal G,\mathcal N,H,Z,E,\alpha,\beta,s(\cdot),g_i(\cdot),\omega_0$。

程序 Cloud()
  將 (ω₀, 0) 傳給全部閘道 j∈G
  非同步平行執行 CloudUpdater()

執行緒 CloudUpdater()
  對雲端 epoch h∈[H]：
    若收到閘道 j 的 (ω_new^j, τ)：
      ω_h ← (1−α_h)ω_(h−1) + α × s(h−τ)ω_new^j
      將 (ω_h, h) 傳給全部閘道

程序 Gateway(j)
  若 Cloud() 觸發：
    接收全域模型與時間戳 (ω_h, h)
    更新 τ←h，ω_(τ,0)^j←ω_h
    將 (ω_(τ,z)^j, z) 傳給連接 j 的選定感測器
    非同步平行執行 GatewayUpdater(j)

執行緒 GatewayUpdater(j)
  對閘道 epoch z∈[Z]：
    接收感測節點 i 的 (ω_new^i, ζ)
    ω_(τ,z)^j ← (1−β_z^j)ω_(τ,z−1)^j + β_z^j ω_new^i
    將 (ω_(τ,z)^j, z) 傳給連接 j 的全部感測器 i
  將 (ω_(τ,Z)^j, τ) 上傳雲端

程序 Sensor(i)
  若 Gateway(j) 觸發：
    接收 (ω_(τ,z)^j, z)
    更新 ζ←z，ω_(τ,ζ,0)^i←ω_(τ,z)^j
    對裝置 epoch e∈[E]：
      ω_(τ,ζ,e)^i ← ω_(τ,ζ,e−1)^i
                       − γ∇g_i(ω_(τ,ζ,e−1)^i; ω_(τ,z)^j)
    將 (ω_(τ,ζ,E)^i, ζ) 上傳閘道 j

收斂分析：本節令 $s(\cdot)=1$。損失函數需满足 $L$-smooth、$\mu$-weakly convex 及梯度有界等正則條件。$\mu$ 弱凸允許處理非凸（$\mu>0$）、凸（$\mu=0$）、強凸（$\mu<0$）損失。下列是額外假設與收斂結果。完整證明在補充材料，亦可見 arXiv:2301.06646。

假設 1，梯度有界：雲端 $L_N$ 及每個裝置 $g_i$ 的梯度滿足：

$\|\nabla L_N(\omega)\|^2\le V_1,\quad\forall\omega\in\mathbb R^d,$ $\|\nabla g_i(\omega;\omega')\|^2\le V_2,\quad\forall\omega,\omega'\in\mathbb R^d,\ i\in\mathcal N.$

假設 2，延遲有界：雲端模型延遲 $h-\tau$ 及閘道模型延遲 $z-\zeta$ 滿足：

h-\tau\le K_c,\qquad z-\zeta\le K_g.\tag{6}

假設 3，正則化 $\rho$ 足夠大：$\rho$ 夠大，使某固定 $c>0$、所有 $\tau,\zeta>0$、$h\ge1$、$i\in[N]$，有：

-(1+2\rho+c)V_1+(\rho^2-\rho/2)\mathbb E\|\omega^i_{\tau,\zeta,h-1}-\omega^i_{\tau,\zeta}\|^2\ge0.\tag{7}

定理 5.1：對 $L$-smooth、$\mu$ 弱凸損失 $\ell$，在假設 1–3 下，取 $\gamma\le L^{-1}$、$\alpha\le K_c^{-3/2}$、$\beta\le K_g^{-3/2}$。演算法 1 執行 $H,Z,E$ 個雲端、閘道、裝置 epoch 後：

\mathbb E L_N(\omega^i_{\tau,\zeta,e}) \le\mathbb E L_N(\omega^i_{\tau,\zeta,e-1}) -\gamma c\mathbb E|\nabla L_N(\omega^i_{\tau,\zeta,e-1})|^2 +\gamma^2O(\rho E^2V_2),\tag{12}

\mathbb E|\omega_\zeta-\omega_{\zeta,e-1}|^2 =\mathbb E\left|\sum_{r=1}^{e-1}\gamma\nabla g_{\omega_\zeta}(\omega_{\zeta,r})\right|^2 \le\gamma^2(e-1)\sum_{r=1}^{e-1}\mathbb E|\nabla g_{\omega_\zeta}(\omega_{\zeta,r})|^2 \le\gamma^2(e-1)^2V_2\le\gamma^2E^2V_2.

\ge -V_1(\rho+\tfrac12+c)-V_2(\rho+\tfrac12) +(\rho^2-\tfrac\rho2)\mathbb E|\omega_{\zeta,e-1}-\omega_\zeta|^2.

\mathbb E L_N(\omega^i_{\tau,\zeta,E}) \le\mathbb E L_N(\omega^i_{\tau,\zeta}) -\gamma c\sum_{e=1}^E\mathbb E|\nabla L_N(\omega^i_{\tau,\zeta,e-1})|^2 +\gamma^2O(\rho E^3V_2),\tag{13}