原創 Synced 機器之心
機器之心分析師網絡
作者：仵冀穎
編輯：H4O
本文是我們聯邦學習系列研究文章中的一篇，重點聚焦的是聯邦學習中的通信開銷問題（Communication Cost）。
0. 引言
聯邦學習（Federated Learning）允許用戶在將數據保留在本地端不共享的前提下形成一個聯合體訓練得到全局模型，從而有效解決數據隱私和安全保護問題。同時，還可以有效應用聯合體各方用戶所掌握的標註數據，解決標註數據缺乏的問題。在聯邦學習架構的每一輪學習過程中，中央伺服器在當前全部客戶端中選定一些客戶端子集並將全局模型下發給這些客戶端子集。然後，這些客戶端子集在本地運行隨機梯度下降（SGD）等優化處理步驟後生成本地模型。最後，客戶端子集將本地模型發送回中央伺服器。反覆執行訓練過程直到模型收斂，生成最終的全局模型。
目前，聯邦學習的應用面臨四個主要問題：通信開銷問題、隱私保護問題、客戶端無狀態問題和客戶端中數據非獨立同分布問題。其中，通信開銷問題主要是由客戶端和中央伺服器之間經由網絡連接和傳輸數據（模型、參數）所造成的。隱私保護問題主要是指經由網絡傳輸時用戶信息、模型信息的隱私和安全保護問題。客戶端無狀態問題是指一般情況下在多輪訓練期間，沒有一個客戶端會參與超過一次的訓練。客戶端中數據非獨立同分布問題則是指不同客戶端，特別是邊緣設備，所收集到的數據通常不是獨立的，也不具備相同的數據分布特性。本文重點關注通信開銷問題的最新研究進展。通信帶寬是聯邦學習的主要瓶頸，因為大量的設備都將其本地更新發送到中央伺服器中。因此，對於一個通信效率高的聯邦學習算法來說，這種更新必須以壓縮和不頻繁的方式發送。
在實際場景中，特別是在所需的全局模型規模較大的情況下，網絡帶寬限制和工作節點數量可能會加劇聯邦學習的通信瓶頸，從而造成客戶端設備掉隊 / 退出的問題。在經典的聯邦學習框架下，系統會將一些網絡帶寬受限或訪問受限的客戶端排除在訓練的輪次之外，即不將全局模型發送給這些客戶端進行本地優化。這種簡單的處理方式會大大影響這些客戶端所提供的服務，進而影響用戶的使用體驗。
針對通信開銷問題最簡單直接的解決方案是以犧牲模型準確度為代價、在聯邦學習的整體框架中僅訓練佔用通信空間較小的低容量模型。從這個角度出發，來自 Google 的研究人員 Koneˇcný et al. 提出了一種降低上行通信成本（Client-to-Server FL Communication）的方法 [1]：客戶端只將本地計算得到的模型更新傳遞到中央伺服器，而不是完整的本地模型。很顯然，這種方法雖然能夠降低通信成本，但是並不能滿足複雜場景下業務應用需要。在此基礎上，來自同一研究小組的 Caldas et al. 提出了一種能夠有效降低下行通信成本（Server to Client Communication）同時與已有降低上行通信成本方法無縫集成的方法[2]，具體包括在伺服器到客戶端的全局模型上使用有損壓縮，以及允許用戶在全局模型的較小子集上高效完成本地訓練的、能夠同時減少客戶端到伺服器的通信成本和本地計算的 Federated Dropout。
與這兩篇文章的思路類似，Rothchild el al. 提出了一種使用 Count Sketch 對客戶端模型更新進行壓縮處理的方法 FedSGD [3]。由於 Count Sketch 是線性的，可以通過 Sketch 計算動量和誤差累積，從而將動量和誤差累積的計算任務從客戶端轉移到中央伺服器，克服了稀疏客戶端參與更新的問題，同時保持高壓縮率和良好的收斂性。
Reisizadeh et al. 提出了一種周期平均和量化的處理方法 FedPAQ [6]，量化處理本身也是壓縮的一種方式。FedPAQ 允許網絡中的客戶端在與中央伺服器同步之前執行本地訓練，僅將活躍客戶端的更新發送回中央伺服器，且發回的僅為本地信息的量化版本。
與上述從壓縮角度出發的工作較為不同的是，Hamer el al. 提出了一種主要解決下行通信成本問題的集成方法：FedBoost [4]。集成方法是機器學習中的一種通用技術，用於組合多個基本預測因子或專家來創建一個更精確的模型。FedBoost 主要通過學習一組預先訓練好的基本預測因子（Base Predictors）實現聯邦集成（Federated Ensembles）。
此外，Malinovsky el al. 提出了一種高效通信的分布式定點優化方法（Fixed-point optimization）[5]，從解決優化問題或尋找凸凹函數的鞍點的角度出發限制客戶端本地計算，從而解決聯邦學習通信開銷瓶頸問題。
1. 解決通信開銷問題的研究進展
1.1 通過壓縮方法解決通信開銷問題
通過壓縮處理減少聯邦學習框架中上行、下行傳遞的數據量是最直接的解決通信開銷問題的方法。我們首先來看一看這一類方法的研究進展情況。
1.1.1 模型更新上傳方法 [1]
聯邦學習的目標是從存儲在大量客戶端的數據中學習包含在真實矩陣 W 中參數的模型。在第 t 輪訓練過程中，中央伺服器將當前模型 W_t 分發給總共 n_t 個客戶端的子集 S_t。這些客戶端子集根據其本地數據獨立訓練並更新本地模型。具體介紹，第 i 個客戶端的更新過程如下式所示：
這些更新可以是在客戶端上計算得到的單個梯度值，也可以是使用更複雜的計算方式得到的結果，例如，在客戶端的本地數據集上執行多個隨機梯度下降（Stochastic Gradient Descent，SGD）處理。選定的客戶端會將更新發送回中央伺服器，中央伺服器通過聚合所有客戶端更新來計算得到全局模型：
其中，η_t 表示中央伺服器中的學習速率。
作者介紹兩種部分模型更新上傳至中央伺服器的方法。值得注意的是，本文只關注了客戶端 - 中央伺服器這一段的上行通信成本。第一種方法為結構更新（Structure Update）。令更新(H_t)^i 為預先定義的結構。本文具體考慮兩種結構：低秩（Low-Rank）和隨機掩模（Random Mask）。在低秩情況下，令(H_t)^i=(A_t)^i ・(B_t)^i。在後續計算過程中，隨機生成(A_t)^i 並在本地訓練過程中將其考慮為一個常數，只優化(B_t)^i。在實際實現中，可以將(A_t)^i 壓縮成隨機種子的形式，客戶端只需要向中央伺服器發送訓練後的(B_t)^i。在每一輪次的更新中為每個客戶端重新生成(A_t)^i 矩陣。在隨機掩模的情況下，令(H_t)^i 為一個遵循預定義的隨機稀疏模式（即隨機掩模）的稀疏矩陣。在每一輪次的更新中每個客戶端獨立生成新的掩模。與低秩方法類似，稀疏掩模可以通過一個隨機種子生成，因此只需要將(H_t)^i 的非零項值與種子一起發送。
第二種方法為草圖更新（Sketched Update）。首先，在客戶端完整的計算模型更新(H_t)^i。在發送至中央伺服器之前，以有損壓縮進行編碼處理。中央伺服器收到編碼後解碼再進行聚合處理。生成 Sketch 的方法包括：（1）下採樣（Subsampling），採樣更新的平均值是真實平均值的無偏估計值 E[H^_t]=H_t。與隨機掩模的結構化更新類似，下採樣掩碼在每輪中也是在每個客戶端獨立隨機採樣的，並且掩碼本身可以存儲為同步種子。（2）概率量化（Probabilistic quantization），即將模型的權重（weights）量化處理。對於更新(H_t)^i，令 h=(h_1, ..., h_(d1x2d))=vec((H_t)^i)，h_max=max_j(h_j)，h_min=min_j(h_j)。h 的壓縮更新為：
對於 4 個字節的浮點數，這種方法實現了 32 倍的壓縮。對於一個比特的量化處理來說，首先均勻區分 [h_min, h_max] 為 2^b 個間隔。h_i 落在 h』和 h』』限定的區間內。量化操作將上述方程的 h_min 和 h_max 分別替換為 h』和 h』』。設定參數 b 以平衡準確度和通信成本，並通過隨機化旋轉改進量化。當尺度在不同維度上近似相等時，上述 1 比特和多比特量化方法效果最好。當 max=1，min=-1，且大部分值為 0 時，1 比特量化將會導致較大誤差，一般可以通過在量化前對 h 進行隨機旋轉（h 乘以隨機正交矩陣）來解決這個問題。在解碼階段，中央伺服器需要在聚合所有更新之前執行反向旋轉。
作者在實驗中對比的是結構更新和草圖更新兩種方法的模型效果，如圖 1 CIFAR 庫和圖 2 REDDIT 庫中的結果。CIFAR 庫中使用的模型有 9 個卷積層，其中第一層和最後一層的參數明顯少於其他層。在壓縮處理過程中只壓縮內部 7 層，每個層都具有相同的參數。圖 1 中使用關鍵字「mode」表示這種方法。對於低秩更新，「mode=25%」表示更新的秩被設置為全層變換的秩的 1/4，對於隨機掩模（Random Mask）或草圖繪製（Sketching），「mode=25%」的意思是對 25% 以外的所有參數進行置零處理。由圖 1，結構化的隨機掩模方法效果更優。
圖 1. 在 CIFAR 資料庫中結構化隨機掩碼更新和無量化 Sketched 更新的對比結果。
基於 REDDIT 資料庫，作者訓練了一個 LSTM 單詞預測模型。該模型被訓練成給定當前單詞和前一時間傳遞的狀態向量來預測下一個單詞。為了減少更新的規模，除一些內存消耗小於 0.01% 的微小變量（例如 bias）外對所有模型變量進行 Sketching 處理。圖 2 中使用 AccuracyTop1 進行評估，即模型賦予最高概率的單詞是正確的預測結果。
圖 2. Sketching 比較，在 Reddit 數據上訓練一個 LSTM 模型，每輪隨機抽樣 50 個客戶端。
1.1.2 有損壓縮方法 [2]
在 1.1.1 節中提出的模型更新傳遞方法也是一種有損壓縮策略，它主要解決的是客戶端 - 中央伺服器的上行通信開銷問題，本節中的方法主要聚焦中央伺服器 - 客戶端的下行通信開銷，同時還能與處理上行通信開銷的方法進行無縫集成。
圖 3. 有損壓縮方法整體思路。
該有損壓縮方法的整體思路如圖 3 所示。（1）通過 Federated Dropout 構造子模型，（2）對生成的對象進行無損壓縮，來減小通信模型的大小。然後將這個壓縮模型發送給客戶端，（3）客戶端使用本地數據對其進行解壓縮和訓練，（4）壓縮最終的本地更新。將本地更新發送回中央伺服器，（5）中央伺服器執行解壓縮，（6）中央伺服器聚合生成全局模型。
在方法第（2）步中所提到的「無損壓縮」借鑑的是節 1.1.1 中闡述的方法，包括基本變換、下採樣、概率量化等。只不過本文將這些壓縮應用於中央伺服器到客戶端的交換中，這也意味著，這種方法不能利用在中央伺服器端通過無損壓縮平均噪聲解壓縮處理（Averaging the Noisy Decompressions）的改進。關於下採樣和概率量化處理本節不再詳述。關於基本變換的處理，作者 Koneˇcný et al. 在文獻 [1] 中並未詳述。實際上文獻 [1] 中的基本變換為隨機 Hadamard 變換（HD），目的是均勻地將向量信息分布在各個維度上。而本文中除隨機 Hadamard 變換外，還考慮了 Kashin 表徵方法（K）從而儘可能在每個維度上傳播向量的信息。
為了進一步降低通信成本，本文引入 Federated Dropout 的有損壓縮方式，即每個客戶端不需要局部訓練全局模型的更新，只是訓練一個更小的子模型的更新。在傳統的 Dropout 方法中，使用一個隨機的二進位掩碼乘以隱藏單元，以便在每次訓練經由網絡傳輸時丟棄一部分期望的神經元。因為每個過程中的掩碼都會發生變化，所以每一個過程都需要計算相對於不同子模型的梯度。這些子模型可以有不同的大小（結構），具體取決於每層中丟棄多少個神經元。在本文處理中，為了滿足節省聯邦學習通信開銷的要求，在每個全連接層上都將固定數量的激活歸零，這樣使所有子模型都具有相同的簡化體系結構。如圖 4 所示。
圖 4. 應用於兩個全連接層的 Federated Dropout。
中央伺服器可以將必要的值映射到這個簡化的架構中，這意味著只將必要的係數傳輸到客戶端，重新打包成更小的密集矩陣。客戶端（可能完全不知道原始模型的架構）訓練其子模型並發送其更新，然後中央伺服器將其映射回全局模型。對於卷積層來說，將激活歸零不會實現任何空間的節省，因此，作者去掉了一定比例的濾波器。
除了節省伺服器到客戶端的通信開銷外，Federated Dropout 還帶來了另外兩個好處。首先，客戶端到中央伺服器更新的規模也減少了。其次，本地訓練過程現在只需要運行較少的梯度更新。當前所有的矩陣乘法都是較小維度的（相對於全連接層來說），或者是只需要使用較少的濾波器（對於卷積層來說）。因此，使用 Federated Dropout 進一步降低了聯邦學習中的本地計算成本。
在實驗部分，作者首先分別基於 CIFAR-10 和 EMNIST 庫驗證了壓縮處理對本文方法的影響。由圖 5 的實驗結果，（1）對於每一個模型，都能找到一組至少與基線方法（no compression）相匹敵的壓縮參數設置；（2）Kashin 表徵方法對量化處理最為有用；（3）在中央伺服器到客戶端的通信過程中進行下採樣處理的效果並不好。
圖 5. 有損壓縮參數對 CIFAR-10 和 EMNIST 的影響。
然後，作者通過實驗驗證 Federated Dropout 方法對全局模型準確度的影響。圖 6 給出了模型在不同的 Federated Dropout 率下的收斂情況。在本文模型中，將每層保留的神經元（或卷積層的過濾器）的百分比定義為 Federated Dropout 率。將每個實驗重複 10 次，最終報告 10 次重複實驗結果的平均值。由圖 6，對於每個模型來說都存在小於 1.0 的 Federated Dropout 率與基線方法效果相當。在某些情況下，甚至可以提高模型的最終準確度。此外，Federated Dropout 率為 0.75 的情況下不同模型都可以獲得較好的效果。這種 Dropout 率相當於丟棄掉 25% 的行和全連接層的權重矩陣的列（即，相當於減少了 43%），並減少相應百分比的濾波器。如果 Federated Dropout 率過高，往往會減慢模型的收斂速度，儘管較高的 Federated Dropout 率有時可能獲得更高的準確度。
圖 6. Federated Dropout 的結果，改變每層保留的神經元百分比。
最後，作者進行了實驗以驗證將兩種策略（有損壓縮和 Federated Dropout）與客戶端到伺服器壓縮方案（節 1.1.1 中文獻 [1] 提出的方法）相結合時本文方法的效果。作者評估了本文模型在 3 種不同的壓縮方案（Aggressive、Moderate 和 Conservative）和 4 種不同的 Federated Dropout 率（0.5、0.625、0.75 和 0.875）的表現。圖 7 給出了 CIFAR-10 和 EMNIST 中的實驗結果。重複每個實驗 5 次，最終報告 5 次重複實驗結果的平均值。對於所有三個模型，除了 Aggressive 壓縮方案外，Federated Dropout 率為 0.75 時在所有壓縮方案下都不會造成模型準確度下降。對於 MNIST 和 EMNIST，中央伺服器到客戶端的通信成本節省了 14 倍，客戶端到中央伺服器的通信成本節省了 28 倍，本地計算量減少了 1.7 倍，所有這些通信開銷成本的節約都不會降低最終全局模型的準確性（有時甚至還能夠提高準確性）。
圖 7. 壓縮和 Federated Dropout 對 CIFAR-10 和 EMNIST 的影響。
1.1.3 Count Sketch 壓縮處理 [3]
這篇文章中提出的 FetchSGD 使用 Count Sketch 來壓縮模型更新，然後利用 Sketches 的可合併性來將不同客戶端的模型更新進行合併。FetchSGD 設計中的一個關鍵問題是，由於 Count Sketch 是線性的，動量和誤差累積都可以在 Count Sketch 中進行。這使得該方法能夠將動量和誤差累積從客戶端轉移到中央伺服器中，從而在克服稀疏客戶端參與挑戰的同時，確保高壓縮率和良好的收斂性。FetchSGD 的完整方法見圖 8：（1）在客戶端本地計算梯度，（2）將梯度的 sketches 發送到中央伺服器中，中央伺服器聚合梯度（3）sketches（4）動量和誤差累積（5），（6）提取近似的 top-k 值，（7）中央伺服器將稀疏值更新到參與下一輪訓練的客戶端設備中。
圖 8. FetchSGD 完整方法圖示。
在 FetchSGD 的每次迭代中，第 i 個參與的客戶端使用部分（或全部）本地數據計算隨機梯度 (g_i)^t，然後使用稱為 Count Sketch 的數據結構壓縮(g_i)^t。每個客戶端將 Sketch S((g_i)^t) 作為其模型更新發送到聚合器（中央伺服器）。Count Sketch 是一種隨機的數據結構，它可以通過將向量多次隨機投影到低維空間來壓縮向量，以便後續近似地恢復高幅值（High-Magnitude Elements）數據。如下式：
由於 Count Sketch 具備線性特性，中央伺服器可以在給定 S((g_i)^t)的情況下，計算出每個小批量梯度 g^t 的 sketch：
此外，Count Sketch 的另一個有用特性是，對於 sketching 操作符 S()，有一個對應的解壓操作符 U()返回原始向量的無偏估計，從而實現對向量高幅值元素的近似：
簡而言之，U()近似地「撤消」由 S() 計算的投影，然後使用這些重建來估計原始向量。基於 Sketch S((g_i)^t)，中央伺服器利用下式更新全局模型：
Top-k(g^t) 不是 g^t 的無偏估計，因此不具備經典 SGD 的聚合性。不過，研究人員也證明了如果有偏梯度壓縮方法累積了有偏梯度壓縮算子所產生的誤差，並在以後的優化中重新引入誤差，則仍然可以收斂。在 FetchSGD 中，由 Top-k 引入的 bias 可以在中央伺服器端進行誤差累積，從而將其重新零初始化（zero-initialized）為 sketch S_e：
相比之下，其他有偏梯度壓縮方法在壓縮梯度時會給客戶端帶來偏差，因此客戶端本身必須保持單獨的誤差累積向量。這在聯邦學習中是很難保證的，這是由於客戶端僅能參與一次更新，這樣就沒有機會在下一輪中重新引入錯誤。從另一個角度看，由於 S()是線性的，並且誤差累積只包含線性操作，因此在 S_e 的中央伺服器上進行誤差累積相當於在每個客戶端上進行誤差累積，並將結果 Sketch 上傳到中央伺服器。更進一步，我們注意到動量也只包含線性操作，因此動量可以等價地在客戶端或中央伺服器上執行。推廣上述方程可以得到：
完整的 FetchSGD 計算流程如下：
本文實驗主要在小型本地數據集和 Non-IID 數據上完成，因為作者認為這是聯邦學習中一個重要且相對未解決的問題。經典的梯度稀疏化方法是將每個客戶端的局部 top-k 梯度元素聚合在一起訓練全局模型的，當各個客戶端的本地數據集非常小或相互之間差異非常大時，這種方法在近似全局梯度的真正 top-k 梯度元素時的表現就會非常差。在這種情況下，與經典方法相比 FetchSGD 有一個關鍵的優勢：FetchSGD 的壓縮算子是線性的。在 FetchSGD 中「只使用具有 N 個數據的單個客戶端執行一個步驟相當於使用 N 個客戶端執行一個步驟」，因此，每個客戶端只貢獻一次數據，小型客戶端本地數據集不會帶來任何問題。獨立同分布的問題也可以通過隨機選擇客戶端得到解決，FetchSGD 將參與訓練的各個客戶端的數據聚合起來，因此可以得到更完整的數據分布樣本。
實驗中，作者以上傳和下載的總字節數表徵相對於未壓縮的 SGD 所實現的壓縮效果。這些數據中沒有考慮到的一個重要因素是，在 FedAvg 中，客戶端必須在參與之前立即下載一個完整的模型，因為每個模型的權重在每一輪中都會得到更新。相比之下，局部 Top-k 和 FetchSGD 每輪只更新有限數量的參數，因此未參與的客戶端可以相對更新當前模型，從而減少了必須在參與之前立即下載的新參數的數量。這使得本地 Top-k 和 FetchSGD 的上傳壓縮比下載壓縮更重要。下載壓縮對於這三種方法（FedAvg、Top-k、FetchSGD）也不那麼重要，因為目前邊緣設備的網際網路連接的下載速度往往遠遠高於上傳速度。作者給出了整體壓縮（包括上傳和下載）的結果，在圖 9 中把這些圖分成單獨的上傳和下載部分進行展示。FetchSGD 在不同的數據集和上傳、下載和整體壓縮的任務中，表現都較優。
圖 9. CIFAR10（左）和 CIFAR100（右）的上傳（頂部）、下載（中間）和整體（底部）壓縮效果比對。為了提高可讀性，每個圖只顯示該圖中顯示的壓縮類型的運行的帕累託邊界。
1.1.4 周期平均和量化的壓縮處理方法 [6]
這篇文章介紹了一種周期平均和量化處理的聯邦學習方法（a Communication-efficient Federated learning algorithm with Periodic Averaging and Quantization, FedPAQ）。其中的量化處理也可以看作是一種壓縮方式。
在經典聯邦學習框架中，為了利用客戶端節點上所有可用的數據樣本，參與訓練的客戶端在每次訓練迭代中通過中央伺服器同步其模型，因此，客戶端和中央伺服器之間要進行多次通信，從而導致網絡上的通信爭用造成較大通信開銷。本文提出的周期平均和量化處理方法令客戶端進行本地更新並定期通過中央伺服器進行同步。一旦某客戶端節點從中央伺服器中獲取到更新的模型，客戶端節點每隔 τ 次本地 SGD 就向中央伺服器發送更新信息以更新聚合模型。這種周期平均方案減少了中央伺服器和客戶端之間的通信次數，從而降低了訓練模型的總體通信成本。如果在客戶端中運行 T 次 SGD 迭代，則客戶端需要與中央伺服器進行 K=T/τ 輪通信，從而將總通信成本降低為原成本的 1/τ。這就是「周期平均」的處理思路。
從 K=T/τ 的計算公式可以直觀看出，選擇較大的 τ 值可以減少固定迭代次數 T 的通信次數，進而降低通信成本。但是這種降低是以犧牲模型準確度為代價的。增大 τ，會增加系統的噪聲，進而客戶端中的局部模型會逐漸收斂到局部最優解，而不是全局最優解。因此，作者考慮運行更多次迭代 T 來使模型達到特定的準確度。事實上，我們需要解決的一個關鍵問題是找到最優 τ，以使整個過程通信成本最小化。
在聯邦學習網絡中，通常有大量的設備（如智慧型電話）與中央伺服器（基站）進行通信。但是，基站本身的下載帶寬有限，因此只有少數設備能夠同時將其消息上載到基站。由於這一限制，從客戶端設備發送的消息將在中央伺服器基站中進行流水線式的串行傳輸，這導致訓練速度大大減慢。另一方面，如果讓所有的客戶端設備都參與到整個訓練過程中，將會造成巨大的、昂貴的網絡通信開銷。此外，在實際應用中，並不是所有的客戶端都在每一輪訓練的過程中發揮作用的。有很多因素決定客戶端是否參與當前的訓練過程：設備需在當前狀態下處於中央伺服器基站通信可達的範圍內、客戶端設備在當前狀態下為空閒可用狀態、客戶端設備通電且聯網等等。
考慮到上述因素，FedPAQ 假設，在總共 n 個客戶端設備中每輪訓練中只有 r 個節點（r ≤ n）可用，且這 r 個可用設備在網絡上隨機且均勻地分布。在第 k 個訓練周期內，中央伺服器將其當前模型 x_k 發送給本輪選定的參與訓練的 S_k 個客戶端子集中的 r 個客戶端節點，r 個客戶端節點在該子集的總共 n 個客戶端節點之間隨機均勻分布。另一方面，聯邦學習中的設備上行鏈路帶寬有限，這使得從客戶端到中央伺服器的通信緩慢且昂貴，這也是前面幾節中各種壓縮方法所考慮的主要問題。本文所提出的方法是在傳輸信息中使用量化算子，通過交換量化更新來降低網絡通信開銷。
在進行 τ 輪本地 SGD 更新後，每個客戶端 i∈S_k 中擁有本地模型 (x_k,τ)^i，其中 x_k 為最新從中央伺服器中獲取的全局模型。每個客戶端對 x_k 和(x_k,τ)^i 的差值應用量化算子 Q()，並將量化結果 Q((x_k,τ)^i-x_k) 發送至中央伺服器。中央伺服器接收到量化結果後進行反量化解碼處理，並基於處理結果生成新的全局模型 x_k+1。本文使用的量化算子為：
其中，ξ_i(x,s) 為以概率 |x_i|/||x||)s-l 確定值為 (l+1)/s 的隨機變量。控制參數 s 表徵量化水平，l∈[0,s) 為滿足下式的整數：
完整的 FedPAQ 方法如下：
總的來說，FedPAQ 通過使用三個模塊來降低通信負載：周期平均、部分客戶端參與和量化處理。然而，這種通信減少帶來了收斂準確度降低的問題，因此需要更多次的訓練迭代。作者在原文中還進行了 FedPAQ 的收斂性分析，並給出了 FedPAQ 強凸和非凸損失函數的近似最優理論證明。我們在這裡不再詳述。
作者在實驗中對比了通信開銷和收斂性的 tradeoff 的結果分析。實驗以總的訓練時間為代價目標，包括通訊時間和計算時間。首先，定義網絡帶寬（Bandwidth，BW），每輪的通訊時間為上傳的總比特數除以 BW。每輪的總比特數計算為 r ・ | Q(p,s)|，其中 | Q(p,s)| 表示根據具有 s 級（s levels）的特定量化算子對 p 維向量進行量化編碼所需的比特數。在本文實驗中使用的量化算子中，假定它需要 pF 位來表示長度為 p 的未量化向量，其中 F 為 32 位。然後，利用梯度計算時間的位移指數模型（Shifted-Exponential Model）確定計算時間。假設對於任何客戶端，計算一個周期內的 τ 次迭代和批量大小為 B 的梯度需要確定位移 τ ・ B ・ scale^(-1) ，其中 shift 和 scale 分別是位移指數模型的位移和尺度參數，實驗中 B 確定為 10。每輪的總計算時間就是 r 個貢獻客戶端節點中最大的本地計算時間。最後，計算通信 - 計算比為：
在圖 10 中，前四個圖展示了在 MNIST 數據集（'0'和'8'位）上，T=100 次迭代的正則化邏輯回歸問題的訓練時間。聯邦學習網絡中共有 n=50 個客戶端節點，每個節點加載 200 個樣本。設置 C_comm/C_comp=100/1 來捕獲通信瓶頸。第一列圖中曲線顯示了在中央伺服器上每輪的訓練時間與所獲得的訓練損失之間的關係。第二列圖中曲線顯示了參與更新的客戶端數量 n 的影響。第三列論證了周期長度 τ 在通信 - 計算 tradeoff 中的作用。最後一列圖比較了 FedPAQ 與其他兩個基線方法 FedAvg 和 QSGD 的訓練時間。後四個圖為 CIFAR-10 資料庫中神經網絡的實驗結果。具體圖例與 MNIST 中結果相同。
圖 10. 訓練損失與訓練時間：MNIST 的 Logistic 回歸分析（上），CIFAR-10 的神經網絡結果（下）。
1.2 其它處理方法
1.2.1 集成方法 [4]
針對聯邦學習的通信開銷問題，這篇文章提出了利用集成方法（Ensemble method）的思路。集成方法是機器學習中的一種通用技術，用於組合多個基本預測因子（Base predictors）或專家（Experts）來創建一個更精確的模型。作者認為，聯邦學習中的通信開銷問題是由每輪從中央伺服器發送到客戶端（下行）和從客戶端發送到中央伺服器（上行）的參數數量引起的。在每輪訓練過程中，中央伺服器將當前模型的迭代狀態發送給全部參與的客戶端，直接將集成方法應用於這種聯邦學習框架中會由於每輪都需要傳遞預測值而導致通信爆炸。本文提出的 FedBoost 能夠在降低通信成本的同時實現計算加速、收斂保證和隱私保護。這種方法可以通過聯邦學習使用客戶端設備上的數據來訓練一個原本可能超過客戶端的通信帶寬和存儲容量的模型。此外，FedBoost 能夠同時降低中央伺服器到客戶端（下行）和客戶端到中央伺服器（上行）的通信成本。
集成方法通過聯邦學習的框架在中央伺服器端只需要學習混合權重，所需要經由客戶端發送給中央伺服器的數據量非常小。因此，作者認為在集成方法中客戶端到中央伺服器（上行）的通信成本可以忽略不計。本文提出了標準（Standard）和任務不可知（Agnostic）的聯邦學習集成方法，以解決中央伺服器到客戶端（下行）的通信瓶頸問題。
首先介紹標準聯邦學習集成方法。給定一組預先訓練的基本預測因子或假設：H≜{h_1, ..., h_q}。在標準集成方法中，將全部的假設都發送給每個參與的客戶端。然而，在實踐中，由於中央伺服器和客戶端之間的通信帶寬以及客戶端的內存和計算能力的限制，這種處理方式是不可行的。作者提出了一種抽樣方法，只將其中一部分假設發送給客戶端。這雖然可以降低通信複雜度，但同時會帶來整體梯度偏差的問題以及集成收斂性的不確定性問題。經典的集成方法為：
其中，D_k 表示第 k 個域分布，h 為預先確定的假設，B_F 表示域分布 D_λ與假設估計 h 之間的 Bregman 散度。
給定確定的基本預測因子，引入一個集成權重 α。令 L_k(α)表示經驗損失函數，L_D(k)(h_α) 表示域 k 中 m_k 個樣本的集成：
其中的集成權重 h_α，定義為：
設 C 為每輪發送給客戶端的最大基本預測因子數，即 C 能夠表徵通信效率。中央伺服器端的目標函數是學習一組針對預先訓練的基本估計量 h_k 的係數 α：
FedBoost 的完整算法流程如下：
在每輪訓練中，FedBoost 在中央伺服器上抽取兩個子集：一個預訓練假設子集，其中每一個子集以概率 γ_k,t 抽取得到（用 H_t 表示）；N 個客戶端的隨機子集（用 S_t 表示）。定義以下 Bernoulli 指標：
在隨機採樣的條件下，t 時刻的集成為：
針對該集成的偏置估計為：
通過除以概率γ_k,t 的方式來解決這一問題，從而得出對集成的無偏估計：
作者提出了兩種計算概率 γ_k,t 的方法。一是均勻抽樣，γ_k,t=C/q。二是加權隨機抽樣，
然後，我們介紹任務不可知的聯邦學習集成方法。作者將上述標準聯邦學習環境中的集成方法推廣到任務不可知的聯邦學習中。在不可知損失函數中，優化問題涉及兩組參數：集成權重 α 和混合權重 λ。不可知損失函數如下：
其中，L_k(α) 為標準聯邦學習中域 k 的經驗損失。針對 L(α,λ)的優化問題為一個兩人博弈問題，找到最小化目標函數和對手的 α，同時使用λ最大化目標函數。最終目標是找到給定 α_opt 的極小極大博弈的均衡，它使得對於混合權重λ_opt 的損失最小化。l 為凸函數，可以使用一般鏡像下降（generic mirror descent）或其他基於梯度的算法來優化解決這個問題。
作者提出了任務無關的 AFLBoost 方法優化上述目標函數。AFLBoost 可以看作是 FedBoost 和針對任務無關損失函數的隨機鏡像下降算法 [7] 的結合。AFLBoost 的詳細算法流程如下：
作者在實驗中證明了 FedBoost 在不同通信成本下對密度估計（Density estimation）任務的有效性。具體包括三種方法：（1）無通信效率處理（無採樣）：γ_k,t=1。（2）均勻抽樣：γ_k,t=C/q。（3）加權隨機抽樣：γ_k,t ∝ α_k,t·C。
作者首先創建了一個 p=100 的合成數據集，其中每個 h_k 是單個元素上的點質分布(Point-mass distribution)，初始化每個 α_k 為 1/p，混合權重λ遵循冪律分布(Power law distribution)。實驗結果見圖 11。由圖 11 左，加權抽樣的性能優於均勻抽樣，兩種方法的損失都在穩步下降。由圖 11 中，在通信預算為 64 的情況下，不考慮通信效率均勻抽樣和加權抽樣的性能與 FedBoost 相同。此外，作者還在經典 Shakespeare 數據集中進行實驗。如圖 11 右，加權隨機抽樣比均勻抽樣的表現更好，在這個庫中加權抽樣的表現甚至優於 FedBoost，具有更好的收斂性能。
圖 11. 實驗對比圖。左：合成數據集的損失曲線比較；中：合成數據集中取樣方法的比較；右：Shakespeare 聯邦學習數據集的損失曲線比較。
1.2.2 分布式不動點優化方法 [5]
針對聯邦學習的通信開銷問題，一些研究人員的解決思路是利用客戶端的本地計算。也就是說，在通信和模型聚合處理之前，在每個客戶端設備中進行更多的本地計算，從而減少獲得全局有意義的解決方案所需的通信總輪數。在這種思路下，研究人員集中考慮了一些局部梯度下降算法以改進本地計算的效果。本文就是這種思路的工作之一。但是本文的工作並不局限於通過梯度下降來最小化目標函數，作者引入了計算 M 個操作算子平均值的不動點的方法。實際上，大多數迭代方法都屬於不動點方法（Fix-Point method），其目的是尋找某個算子的不動點。
為了從不動點方法角度進行分析，首先介紹經典的分布式不動點優化模型。令分布式系統中共包括 M 個並行計算節點（客戶端）。每個節點中處理的變量可看作是歐氏空間中的向量。令Τ_i 表示歐氏空間的操作算子，平均算子為：
本文方法的核心是找到Τ的不動點，即找到向量 x* 滿足 Τ(x*)=x*。可以通過在每個節點重複應用Τ_i，同時進行平均化處理以達到共識來最終獲得目標解 x*。本文作者考慮，經過多次迭代後，每個客戶端節點將其變量同步傳遞到遠程中央伺服器中。然後中央伺服器計算所接收到的向量的平均值並將其廣播到所有節點。
本文考慮兩種不動點優化策略：第一種策略是對於每個客戶端計算節點，迭代執行若干次某個操作序列（稱之為局部步驟，local steps）。第二種策略是減少通信步驟的數量，即僅以一定的較低概率到中央伺服器中共享信息，並且只在中間過程進行局部計算。
將 T 定義為歐氏空間中的一個操作算子，令 Fix(T) 表示 T 的不動點集合，對於歐氏空間中的每個 x 和 y，如果 T 滿足下式，則稱 T 是χ-Lipschitz 連續的：
此外，如果 T 是 1-Lipschitz 連續和χ- 收縮的，則稱 T 是非擴張的。如果 T 是收縮的，則它具有存在且唯一的不動點。對於任意 α∈(0,1]，如果對於一些非擴張算子 T』 ，如果存在 T=αT』+Id，則稱 T 是 α 平均的。如果 T 是 1/2 平均的，則稱 T 是堅決不擴張的。
令(t_n)_n∈N 表示通信過程中的整數序列。在每次迭代過程中，操作算子Τ_i 應用於節點 i，並利用參數λ進行鬆弛。對於一定數量的迭代，M 個計算節點全部將其本地向量傳輸給中央伺服器的主節點，主節點計算平均值並將平均值廣播給全部節點。全部節點在新的一輪迭代開始時擁有相同的變量 (x^)^k。該算法是局部梯度下降法（Federated Averaging）的推廣。
我們把一系列本地迭代稱為一個 epoch，然後求取平均值。也就是說，第 n 個 epoch 是指數 k+1=t_(n-1)+1,...,t_n 的迭代序列。假設在兩個聚合計算平均值步驟之間的每個 epoch 的迭代次數由某個整數 H 限定。則對於每個 n≥1，有 1≤t_n - t_(n-1) ≤H。具體，第一種策略的詳細算法流程如下：
接下來，作者提出了第二種策略。第一種策略中的本地處理步驟可以看作是兩個通信步驟之間的內環（Inner Loop），將內環用概率聚合（Probabilistic Aggregation）來代替，即可得到第二種策略。在以下意義上，它是通信 - 有效的：在第一種策略中，通信輪數除以 H（或是非均勻情況下 t_n - t_(n-1)的平均值），而在第二種策略中該值乘以概率 p≤1。第二種策略的詳細算法流程如下：
在原文中，作者對兩種策略算法的收斂性能進行了充分的論證，我們在這裡不再詳述。
作者選擇經典分類問題的邏輯回歸進行實驗。相應的目標函數如下：
其中，a_i∈R^d，b_i∈{-1,+1} 為數據樣本。使用 LIBSVM 庫中的「a9a」和「a4a」數據集，並將 k 設為 L/n，其中 n 是數據集的大小，L 是ᐁf 第一部分的 Lipschitz 常數，且沒有經過正則化處理。
本文實驗中考慮梯度下降（Gradient Descent，GD）作為操作算子。也就是說，我們考慮最小化有限和問題：
其中，函數 f_i 為凸且 L 平滑的。令：
使用 1/L 作為步長，則每個Τ_i 都是堅決不擴張的。
使用第一種策略的算法 1 和使用第二種策略的算法 2 的實驗結果見圖 12 和圖 13。參數 H 和λ的值越大，初始收斂速度越快，但鄰域半徑越大。就計算時間而言，該算法沒有太大的優勢，因為實驗是在一臺機器上進行的，通信時間可以忽略不計。但是在通信速度較慢的分布式環境中，本文的算法就有明顯的優勢。我們也可以觀察到圖中實驗結果曲線沒有出現振蕩。因此，當只需要達到有限的準確度時，本文提出的本地方法具有明顯的優勢。
圖 12. 具有梯度下降步長的算法 1 在均勻通信時間 t_n=nH 下的收斂性，（a）不同 H 值的通訊輪數，λ=0.5，（b）不同 H 值的計算時間，λ=0.5，（c）不同λ值的計算時間，H=4。
圖 13. 梯度下降步長算法 2 的收斂性，λ=0.5，（a）梯度步長相同情況下，不同 p 值的通訊輪次數量，（b）梯度步長相同情況下，不同 p 值的計算時間，（c）梯度步長與 p 是成比例的，不同 p 值的通訊輪次數量。
2. 總結
我們在這篇文章重點關注了聯邦學習框架中的通信開銷研究進展。目前，大多數文章都從壓縮的角度出發解決通信開銷問題，這種方法的思路很直觀：壓縮後需要上行、下行傳遞的數據量就會減小，從而減輕通信開銷。當然，壓縮的方法有很多，例如有損壓縮、提取 sketch、量化等等。此外，我們也分析了兩篇非壓縮思路的文章，作者分別使用了集成方法和加強本地計算的方法。在不同的文章中，作者對比和分析的實驗指標各不相同，這說明目前還沒有標準化、統一化、權威性的衡量聯邦學習通信開銷的指標，畢竟通信開銷和計算效率是一對 tradeoff 的指標。單純用通信時間或通信數據量去衡量方法的優劣並不客觀。
目前，隨著 5G 技術的發展，5G 網絡中通信速率問題變得不再是問題。依託 5G，使用邊緣設備的應用場景也越來越多，例如校園安全監控、明廚亮灶監控、移動執法等等。在這種情況下，是否能夠緩解聯邦學習中的通信開銷問題，進而推動聯邦學習更快的發展和應用？讓我們拭目以待吧！
參考文獻
[1] Jakub Koneˇcný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.
Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016b. https://arxiv.org/pdf/1610.05492.pdf.
[2] Caldas, S., Koneˇcny, J., McMahan, H. B., and Talwalkar, A. Expanding the reach of federated learning by reducing
client resource requirements. arXiv preprint arXiv:1812.07210, 2018.
[3] Rothchild, D. , Panda, A. , Ullah, E. , Ivkin, N. , Stoica, I. , & Braverman, V. , et al. (2020). FetchSGD: communication-efficient federated learning with sketching, ICML 2020, http://arxiv.org/abs/2007.07682v1.
[4] Jenny Hamer, Mehryar Mohri , Ananda Theertha Suresh, FedBoost: A Communication-Efficient Algorithm for Federated Learning,ICML 2020.
[5] Malinovsky, G. , Kovalev, D. , Gasanov, E. , Condat, L. , & Richtarik, P. . (2020). From local sgd to local fixed point methods for federated learning, ICML 2020, https://arxiv.org/abs/2004.01442.
[6] Reisizadeh A , Mokhtari A , Hassani H , et al. FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization[J]. arXiv, 2019.https://arxiv.org/pdf/1909.13014.pdf.
[7] Mohri, M., Sivek, G., and Suresh, A. T. Agnostic federated learning. In International Conference on Machine Learning, pp. 4615–4625, 2019.
分析師介紹：
仵冀穎，工學博士，畢業於北京交通大學，曾分別於香港中文大學和香港科技大學擔任助理研究員和研究助理，現從事電子政務領域信息化新技術研究工作。主要研究方向為模式識別、計算機視覺，愛好科研，希望能保持學習、不斷進步。
關於機器之心全球分析師網絡 Synced Global Analyst Network
機器之心全球分析師網絡是由機器之心發起的全球性人工智慧專業知識共享網絡。在過去的四年裡，已有數百名來自全球各地的 AI 領域專業學生學者、工程專家、業務專家，利用自己的學業工作之餘的閒暇時間，通過線上分享、專欄解讀、知識庫構建、報告發布、評測及項目諮詢等形式與全球 AI 社區共享自己的研究思路、工程經驗及行業洞察等專業知識，並從中獲得了自身的能力成長、經驗積累及職業發展。
原標題：《如何解決聯邦學習中的通信開銷問題？》
閱讀原文