【張老師文章】聯邦學習中裝置的靈活參與

這是張老師的二作文章，可得好好讀。
           

摘要

  傳統的聯邦學習算法對裝置的參與率有嚴格的要求，這限制了聯邦學習的潛在覆寫範圍。本文擴充了目前的學習範式，以包括可能變得不活躍、計算不完整更新以及在訓練過程中離開或到達的裝置。我們得出了分析結果，以說明當資料non-IID時，允許更靈活的裝置參與影響學習收斂。

  然後，文章提出了一種新的聯邦聚合方案，即使裝置可能處于非活動狀态或傳回不完整的更新，該方案也會收斂。我們還研究了學習過程如何适應早離或晚到，并分析了它們對收斂的影響。

1 引言

  考慮到聯邦學習通常需要數千個通信輪才能收斂，是以在實踐中很難確定在整個訓練過程中所有裝置都可用。此外，通常有多個應用程式同時運作在使用者裝置上，競争已經高度受限的硬體資源。是以，不能保證裝置在每一輪訓練中都能按預期完成指定的訓練任務。

  雖然已經提出了許多方法來減輕單個裝置的工作負載，如權重壓縮和聯邦dropout，但它們不能完全消除裝置無法履行其訓練職責的可能。是以，在大規模聯邦學習中，首先必須排除許多資源受限的裝置加入聯邦學習，這限制了訓練資料集的潛在可用性，削弱了聯邦學習的适用性。此外，現有的工作并沒有具體說明當遇到意外的裝置行為時如何反應，也沒有分析這些行為對訓練進度的(負面)影響。

  在本文中，我們放寬了這些限制，并允許裝置遵循更靈活的參與模式：

• 不完全性：裝置可能在一輪中隻送出部分完成的工作。
• 不活動：此外，裝置可能不完成任何更新，或根本不響應協調器。
• 早退：在極端情況下，現有裝置可能會在未完成所有訓練回合前退出訓練。
• 遲到：除現有裝置外，新裝置可能在訓練開始後加入。

  我們提高裝置參與靈活性的方法包括以下元件，這些元件補充了現有的FedAvg算法，并處理靈活裝置參與帶來的挑戰：

• 部分模型更新的去偏置
• 裝置到達時快速重新開機
• 重新定義裝置偏離的模型适用性

2 相關工作

  （一些異步訓練的工作）算法中的異步聚合可以自然地應用于随機非活動裝置，但作者沒有分析他們的算法的收斂性是如何受到裝置不活動或不完整以及資料異構性的影響的。

  （一些放寬參與裝置要求的工作）這些工作并沒有顯示裝置的變化如何影響訓練的收斂性，也沒有将使用者資料的異質性納入算法設計中。

  等等相關工作的調研。

3 收斂性分析

3.1 算法描述

  假設這裡有 N N N個裝置，我們為每個裝置 k k k定義一個局部目标函數 F k ( w ) F_k(w) Fk​(w)。其中 w w w顯然就是機器學習的權重參數， F k ( w ) F_k(w) Fk​(w)可以是裝置 k k k上的所有點的平均經驗損失。我們的全局目标是最小化以下的函數：

F ( w ) = ∑ k = 1 N p k F k ( w ) F(w)=\sum_{k=1}^Np_kF_k(w) F(w)=k=1∑N​pk​Fk​(w)

  其中 p k = n k n p^k=\frac{n_k}{n} pk=nnk​​， n k n_k nk​是裝置 k k k所擁有的資料數量，且 n = ∑ k = 1 N n k n=\sum_{k=1}^Nn_k n=∑k=1N​nk​。令 w ∗ w^* w∗是函數 F ( w ) F(w) F(w)取最小值的權重參數。我們用 F k ∗ F_k^* Fk∗​表示 F k F_k Fk​的最小值。

  為了描述裝置 k k k的資料分布與其他裝置的資料分布的不同程度，我們量化為 Γ k = F k ( w ∗ ) − F k ∗ \Gamma_k=F_k(w^*)-F_k^* Γk​=Fk​(w∗)−Fk∗​，同時令 Γ = ∑ k = 1 N p k Γ k \Gamma=\sum_{k=1}^Np_k\Gamma_k Γ=∑k=1N​pk​Γk​.

  考慮離散的時間步長 t = 0 , 1 , ⋯ t=0,1,\cdots t=0,1,⋯.當 t t t是 E E E的倍數時，模型權重進行同步。假設最多有 T T T個回合，對于每一輪（例如在第 τ \tau τ輪），我們執行以下三個步驟：

1. 同步：伺服器廣播最新權重 w τ E G w_{\tau E}^\mathcal{G} wτEG​給所有的用戶端。每個用戶端更新自己的權重參數： w τ E k = w τ E G w_{\tau E}^k=w_{\tau E}^\mathcal{G} wτEk​=wτEG​
2. 本地訓練：當 i = 0 , ⋯   , s τ k − 1 i=0,\cdots,s_\tau^k-1 i=0,⋯,sτk​−1時，每個裝置對自己的損失函數 F k F_k Fk​運作SGD算法： w τ E + i + 1 k = w τ E + i k − η τ g τ E + i k w_{\tau E+i+1}^k=w_{\tau E+i}^k-\eta_\tau g_{\tau E+i}^k wτE+i+1k​=wτE+ik​−ητ​gτE+ik​這裡的 η τ \eta_\tau ητ​是随 τ \tau τ衰減的學習率， 0 ≤ s τ k ≤ E 0\le s_\tau^k\le E 0≤sτk​≤E表示在本輪中完成的本地更新的時間步數。 g t k = ∇ F k ( w t k , ξ t k ) g_t^k=\nabla F_k(w_t^k,\xi_t^k) gtk​=∇Fk​(wtk​,ξtk​)則是裝置 k k k的随機梯度，其中 ξ t k \xi_t^k ξtk​代表了本地mini-batch的資料。我們同樣定義 g ˉ t k = ∇ F k ( w t k ) \bar g_t^k=\nabla F_k(w_t^k) gˉ​tk​=∇Fk​(wtk​)表示裝置 k k k的全batch梯度，是以 g ˉ t k = E ξ t k [ g t k ] \bar g_t^k=\mathbb E_{\xi_t^k}[g_t^k] gˉ​tk​=Eξtk​​[gtk​]
3. 聚合：協調器聚合梯度并生成下一個全局權重參數： w ( τ + 1 ) E G = w τ E G + ∑ k = 1 N p τ k ( w τ E + s τ k − w τ E G ) w ( τ + 1 ) E G = w τ E G − ∑ k = 1 N p τ k ∑ i = 0 s τ k η τ g τ E + i k w_{(\tau+1) E}^\mathcal{G}=w_{\tau E}^\mathcal{G}+\sum_{k=1}^Np_\tau^k(w_{\tau E+s_{\tau}^k}-w_{\tau E}^\mathcal{G})\\w_{(\tau+1) E}^\mathcal{G}=w_{\tau E}^\mathcal{G}-\sum_{k=1}^Np_\tau^k\sum_{i=0}^{s_\tau^k}\eta_\tau g_{\tau E+i}^k w(τ+1)EG​=wτEG​+k=1∑N​pτk​(wτE+sτk​​−wτEG​)w(τ+1)EG​=wτEG​−k=1∑N​pτk​i=0∑sτk​​ητ​gτE+ik​如果 s τ k = 0 s_\tau^k=0 sτk​=0（即是說，裝置 k k k在第 τ \tau τ輪沒有任何更新），那麼我們就說裝置 k k k在第 τ \tau τ輪是不活躍的。如果 0 < s τ k < E 0<s_\tau^k<E 0<sτk​<E，那麼我們說裝置 k k k是不完整的。我們将每個 s τ k s_\tau^k sτk​視為遵循任意分布的随機變量，如果不同裝置的 s τ k s_\tau^k sτk​具有不同的分布，那麼他們是異質的，否則是同質的。同時，我們允許聚合的權重系數 p τ k p_\tau^k pτk​随時間步數 τ \tau τ變化。（一般來說 p τ k p_\tau^k pτk​是 s τ k s_\tau^k sτk​的函數 ）

作為一種特殊情況，傳統的FedAvg假設所有的裝置每輪都能完成所有的 E E E個時間步數的訓練，是以 s τ k ≡ E s_\tau^k\equiv E sτk​≡E。且全裝置參與的FedAvg所使用的聚合系數 p τ k ≡ p k p_\tau^k\equiv p^k pτk​≡pk，是以上一個公式的右側可以寫成： w ( τ + 1 ) E G = ∑ k = 1 N p τ k w τ E k w_{(\tau+1) E}^\mathcal{G}=\sum_{k=1}^Np_\tau^kw_{\tau E}^k w(τ+1)EG​=k=1∑N​pτk​wτEk​這是因為梯度聚合相當于直接對模型參數進行聚合。

3.2 一般收斂界

  這部分通過各類假設（包括Lipschitz梯度等等）證明了以下的收斂界：

3.3 全局目标轉移

  這一章描述了由于接受了特定裝置的權重後，全局的損失函數會向這個裝置的方向偏移的現象。文章有以下定理：

  之後文章推導了在全局目标轉移的情況下，新的收斂界。