摘要
《Federated Learning of a Mixture of Global and Local Models》這篇論文的目的是在Local和Global之間尋找一個trade off，對全局模型和局部模型進行混合，并提出适用于這一想法的幾種新的梯度下降算法，如L2GD，該算法還能改進通信複雜度。
本文的兩項動機
1、全局模型在用戶端的實用性問題。
2、傳統的LGD在理論上，并不能改善通信複雜度。
目标函數
其中f(x)是全局平均損失值，λ≥0是懲罰項參數， x 1 x_1 x1… x n x_n xn∈ R d R^d Rd是本地模型，x:=( x 1 x_1 x1… x n x_n xn)∈ R n d R^{nd} Rnd是混合模型，x_hat是所有本地模型的平均值。
文章中假設 f i f_i fi: R d R^d Rd→R是L-smooth和μ-strongly convex，是以（2）有唯一解，表示為：
Local model(λ=0)： x i x_i xi(0)是裝置i僅基于本地資料訓練得到的本地模型。
Mixed model(λ∈(0,∞))：當λ增大時，懲罰項λψ(x)也将增大，此時需要保持通信（及時更新全局模型），防止各個性化模型存在過大差異。
Global model(λ=∞)：當λ→無窮時，優化目标将由（2）變成優化f，這樣就會使每個本地模型變成單純的全局模型，x(∞) := ( x 1 x_1 x1(∞),…, x n x_n xn(∞))。即FedAvg：
最優解的特征
定理一：
随着λ的增長，最優局部模型 x i x_i xi(λ)越來越相似。the loss f(x(λ)) increases with λ, but never exceeds the optimal global loss f(x(∞)) of the standard FL formulation (1)
定理二：
裝置i的最優個性化模型是通過"所有裝置上的最優個性化模型的平均"減去裝置i上的損失函數的梯度來獲得的。所有裝置都達到最優個性化模型時，所有本地梯度的總和為0，這在λ = ∞時顯然是正确的，當λ > 0時就不那麼明顯。
L2GD: Loopless Local GD
L2GD其實就是通過機率(0<p<1)選擇進行讓目标函數導數中的▽f(x)還是▽ψ(x)來計算梯度G(x)，定義F在x∈ R n d R^{nd} Rnd的随機梯度G(x)如（7）所示。本地模型更新： x k + 1 x^{k+1} xk+1 = x k x^{k} xk - aG( x k x^{k} xk)，其中步長a是受限的，目的是使aλ/np≤1/2。将▽f或▽ψ的公式代入（7）便可以得到L2GD的完整表達形式，如Algorithm 1所示。
總的來說，當算法采取的local GD步驟越多，個性化模型越接近純局部模型；采取的average步驟越多，個性化模型越接近它們的平均值。執行local GD與average的相對次數由參數p控制：local GD的預期次數為1/p，連續average的預期次數為1/(1-p)。
定義Device→Master和後續的Master→Device稱為一輪通信。L2GD的第k次疊代中通信的預期輪次為p(1-p)k。
主要貢獻
一、能夠混合全局模型和局部模型的新目标函數。
通過加入一個系數為λ的懲罰項ψ(λ>0)，使各個性化模型之間不會存在過分差異。
二、文章證明的的關于目标函數(2)的幾個結論
1、當λ設定為零時，每個裝置隻根據自己的本地資料訓練模型，這樣子效果通常比較一般。
2、證明了最優局部模型以O(1/λ)的速率收斂至 m i n 1 / n Σ i = 1 n f i ( x ) min\ 1/n Σ_{i=1}^nf_i(x) min 1/nΣi=1nfi(x)
3、證明了所有局部模型 f i ( x ) f_i(x) fi(x)的loss的和不會高于全局模型 1 / n Σ i = 1 n f i ( x ) 1/n Σ_{i=1}^nf_i(x) 1/nΣi=1nfi(x)的loss。
三、用于求解目标函數(2)的梯度下降算法：Loopless Local Gradient Descent (L2GD)
L2GD與Local Gradient Descent(LGD)在本質上其實差不多，主要差別在于它們在實際應用中的通信複雜度。
該算法通過機率控制是執行裝置訓練還是伺服器聚合，并且給裝置訓練更高的機率，這樣就能進行多次本地訓練進而改善通信複雜度，當然，本地訓練的疊代次數也不是固定的，而是随機的。GD更新分為兩次，一次是在裝置訓練時，一次是在伺服器聚合後；
通信次數：當λ→0時，每個裝置幾乎僅基于本地資料訓練局部模型，通信輪數趨于0。當λ→∞時，目标函數收斂于最優全局模型，此時達到通信輪數的上限O((L/μ)log(1/ε))
四、局部目标函數用于解決什麼問題？
局部更新的作用并不是單純的降低通信複雜度。他們的作用是引導函數找到一種全局模型和純局部模型的混合。
我們越希望函數偏向于純粹的局部模型(即懲罰參數λ越小)，L2GD所采取的局部步驟就越多，并且L2GD的總通信複雜度就越好。
實驗
文章比較了三種不同的方法:L2SGD+，帶有局部下采樣的L2GD(附錄中的L2SGD)，隻為ψ構造局部子采樣和控制變量的L2GD(附錄中的L2SGD2)。
對于同構資料，文章對資料進行随機打亂。對于異構資料，文章首先根據标簽對資料進行排序，然後根據目前順序建構本地資料。
實驗結果展示了減少方差的重要性–它確定了L2SGD+的快速全局收斂。
L2SGD+線性收斂到全局最優解，而L2SGD和L2SGD2都收斂到某個鄰域。
每種方法都适用于同構或異構資料，這說明資料異質性不會影響所提出方法的收斂速度。
讨論
如前文所述，L2GD的本地更新為的不單是降低通信複雜度，其主要目的是引導方法找到一種全局模型和純本地模式的混合。
其優化目标為
對比FedProx：
兩個優化目标看起來差不多，都是在FedAvg的基礎上加入了一個正則化項。差別在于L2GD的目标函數是從用戶端的角度出發（訓練個性化模型），FedProx的目标函數是從伺服器的角度出發（訓練統一的全局模型）。這也是為什麼FedProx的正則參數為0時算法等于FedAvg，而L2GD的正則參數為無窮時算法等于FedAvg。