文章鏈接：Federated Learning of a Mixture of Global and Local Models

發(fā)表期刊（會(huì)議）: ICLR 2021 Conference（機(jī)器學(xué)習(xí)頂會(huì)）

本博客從優(yōu)化函數(shù)角度出發(fā)，學(xué)習(xí)傳統(tǒng)聯(lián)邦學(xué)習(xí)$?$ 和 新型聯(lián)邦學(xué)習(xí) $?$ 的差異

1. 背景介紹

菲利普和彼得兩位學(xué)者在阿卜杜拉國(guó)王科技大學(xué)發(fā)表的一篇文章中，對(duì)于聯(lián)邦學(xué)習(xí)（Federated Learning）和混合專家（MoE）的結(jié)合進(jìn)行了早期的數(shù)理討論。

有意思的是這兩位學(xué)者的研究動(dòng)機(jī)是為了保護(hù)自己的移動(dòng)設(shè)備數(shù)據(jù)不外露的同時(shí)，還可以用這些數(shù)據(jù)進(jìn)行機(jī)器學(xué)習(xí)。他們給了兩個(gè)很簡(jiǎn)單的理由。

• First, many device users are increasingly sensitive to privacy concerns and prefer their data to never leave their devices.
• Second,moving data from their place of origin to a centralized location is very inefficient in terms of energy and time.
  
  一個(gè)理由是不安全，還有一個(gè)理由是不方便。

2. 傳統(tǒng)聯(lián)邦學(xué)習(xí)

目前為止，FL 已經(jīng)成為一個(gè)跨學(xué)科領(lǐng)域，專注于通過(guò)直接在邊緣設(shè)備上訓(xùn)練機(jī)器學(xué)習(xí)模型來(lái)解決問(wèn)題。傳統(tǒng)的FL框架，每個(gè)客戶參與FL訓(xùn)練。

參數(shù)定義：訓(xùn)練客戶數(shù)量 N；全局模型結(jié)構(gòu) $M_G$；全局模型參數(shù) $\theta (d_1)維$
其中 $\theta \in {\mathbb{R}}^{d_1}$ and ${\mathbb{R}}^{d_1}\in \mathbb{R}$
FL的學(xué)習(xí)目標(biāo)為：
$$?\underset{\theta \in {\mathbb{R}}^{d_1}}{\min }F(\theta )=\frac{1}{N}\sum _{i=1}^N{f}_i(\theta )$$
對(duì)于每一個(gè)$f_i$，由于數(shù)據(jù)分布不同，假設(shè)第 $i$ 個(gè)客戶的數(shù)據(jù)分布定義為 ${\mathcal{D}}_i$ 則：
$$f_i(\theta )={\mathbb{E}}_{(x,y)～{\mathcal{D}}_i}[f(x,\xi )]$$
其中$L_i(?)$是客戶 $i$ 的損失函數(shù)

求解 $F(\theta )$ 最流行的方法是FedAvg算法，在FedAvg最簡(jiǎn)單的形式中，即當(dāng)不使用部分參與、模型壓縮或隨機(jī)近似時(shí)，FedAvg縮減為局部梯度下降(LGD)。這是GD在聚合之前對(duì)每個(gè)設(shè)備執(zhí)行多個(gè)梯度步長(zhǎng)的擴(kuò)展。

FedAvg已被證明在經(jīng)驗(yàn)上是有效的，特別是對(duì)于非凸問(wèn)題（存在多個(gè)局部極小值的問(wèn)題）。但在數(shù)據(jù)異質(zhì)時(shí)，與非本地對(duì)應(yīng)的算法相比，FedAvg的收斂保證較差。

FL 雖然已經(jīng)有了諸多理論證明其可行性，但是它的最終結(jié)果是全局性的，我們需要思考，對(duì)于那些數(shù)據(jù)異構(gòu)的個(gè)體而言，使用全局方案解決個(gè)體問(wèn)題效用一定好嗎？

答案是否定的，數(shù)據(jù)異構(gòu)性不僅對(duì)設(shè)計(jì)新的訓(xùn)練方法來(lái)解決 $?$ 提出了挑戰(zhàn)，而且不可避免地對(duì)這種全局解決方案對(duì)個(gè)人用戶的效用提出了質(zhì)疑。事實(shí)上，在所有設(shè)備的所有數(shù)據(jù)中訓(xùn)練的全局模型可能會(huì)從個(gè)人用戶體驗(yàn)的典型數(shù)據(jù)和使用模式中刪除，以至于使其幾乎無(wú)用。

---

3. FL新范式

本文提出了一種新的訓(xùn)練聯(lián)邦學(xué)習(xí)模型的優(yōu)化公式。標(biāo)準(zhǔn)FL旨在從存儲(chǔ)在所有參與設(shè)備上的私人數(shù)據(jù)中找到一個(gè)單一的全局模型。相比之下，新方法尋求全局模型和局部模型之間的權(quán)衡，每個(gè)設(shè)備可以從自己的私有數(shù)據(jù)中學(xué)習(xí)而無(wú)需通信。

本文開發(fā)了有效的隨機(jī)梯度下降(SGD)變體來(lái)求解新公式，并證明了通信復(fù)雜性的保證。該工作的主要貢獻(xiàn)包括結(jié)合全局和局部模型的FL新范式、新范式的理論性質(zhì)、無(wú)環(huán)路局部梯度下降(L2GD)、L2GD的收斂理論以及對(duì)局部步驟在聯(lián)邦學(xué)習(xí)中的作用的見解。該文件還強(qiáng)調(diào)了本地SGD在通信復(fù)雜性和個(gè)性化聯(lián)邦學(xué)習(xí)的好處方面優(yōu)于傳統(tǒng)SGD的潛力。

本文提出的訓(xùn)練監(jiān)督聯(lián)邦學(xué)習(xí)新范式如下：

? min ? x 1 , . . . , x n ∈ R d { F ( x ) : = f ( x ) + λ ψ ( x ) } f ( x ) : = 1 n ∑ i = 1 n f i ( x i ) ψ ( x ) : = 1 2 n ∑ i = 1 n ∥ x i ? x ￣ ∥ 2 \clubsuit \quad \min_{x_1,...,x_n \in \mathbb{R}^d } \{ F(x): = f(x)+ \lambda \psi (x)\} \\ f(x):=\frac{1}{n}\sum_{i=1}^{n} f_i(x_i) \\ \psi (x) := \frac{1}{2n}\sum_{i=1}^{n} \left \| x_i-\overline{x} \right \| ^2 ?x1?,...,xn?∈Rdmin?{F(x):=f(x)+λψ(x)}f(x):=n1?i=1∑n?fi?(xi?)ψ(x):=2n1?i=1∑n?∥xi??x∥2 其中 $\lambda \ge 0$ 是一個(gè)懲罰超參， $x_1,...,x_n\in {\mathbb{R}}^d$ 是本地模型參數(shù) ， $x:=(x_1,x_2,...,x_n)\in {\mathbb{R}}^{nd}$ 并且 $\overline{x}:=\frac{1}{n}{\sum }_{i=1}^n{x}_i$ 是所有本地模型的平均值。

文章假設(shè)由 $f_i$ 得到的 $F$ 是一個(gè)強(qiáng)凸函數(shù)。 凸函數(shù)是二階導(dǎo)始終為正（負(fù)）的函數(shù)，局部最小值即為全局最小值。對(duì)于 $?$ 有一個(gè)唯一的解。這個(gè)解可以表示為：
$$x(\lambda ):=(x_1(\lambda ),...,x_n(\lambda ))\in {\mathbb{R}}^{nd}$$接著可以計(jì)算 $\overline{x}(\lambda ):=\frac{1}{n}{\sum }_{i=1}^n{x}_i(\lambda )$

---

理論邏輯

所提范式 $?$ 的理論邏輯：

• Local models ($\lambda =0$) ：此時(shí)模型退化為局部模型，只需要將本地?fù)p失降到最低，即求解$$\underset{x_i\in {\mathbb{R}}^d}{\min }{f}_i(x_i)$$也就是說(shuō)，$x_i(0)$ 僅基于存儲(chǔ)在設(shè)備 $i$ 上的數(shù)據(jù) $D_i$ 的局部模型。該模型可以由設(shè)備 $i$ 計(jì)算，而無(wú)需任何通信。通常情況下，$D_i$ 不夠豐富，無(wú)法使用此本地模型。為了學(xué)習(xí)更好的模型，還必須考慮其他客戶的數(shù)據(jù)。然而，這存在溝通成本。
• Mixed models ($\lambda \in (0,\infty )$)：隨著 $\lambda$ 的增加，懲罰 $\lambda \psi (x)$ 的效果越來(lái)越明顯，需要溝通以確保模型不會(huì)太不相似，否則懲罰 $\lambda \psi (x)$ 會(huì)增大。
• Global model ($\lambda =\infty$)：現(xiàn)在我們來(lái)看 $\lambda \to \infty$ 的極限情況。直觀上，這種極限情況應(yīng)該迫使最優(yōu)局部模型之間是相同的，同時(shí)最小化損失 $f$，即讓 $\psi (x)\to 0$ 。$$\psi (x):=\frac{1}{2n}\sum _{i=1}^n{\Vert x_i?\overline{x}\Vert }^2$$此時(shí)，這種情況有一個(gè)特殊的極限解： min ? { f ( x ) : x 1 , . . . , x n ∈ R d , x 1 = ? = x n } \min\{ f(x):x_1,...,x_n\in \mathbb{R}^d ,x_1=\cdots=x_n \} min{f(x):x1?,...,xn?∈Rd,x1?=?=xn?}?？梢苑醋C，如果 $\lambda =\infty$ 并且 $x_1=x_2=?=x_n$不成立，那么 $F(x)=\infty$

---

重要假設(shè)

對(duì)于每一個(gè)設(shè)備 $i$ ,它的目標(biāo)函數(shù) $f_i:{\mathbb{R}}^d\to \mathbb{R}$ 是 $L?smooth$ 并且 $\mu ?strongly$ 的凸函數(shù)。

• $L?smooth$：通常用來(lái)描述一個(gè)函數(shù)的平滑程度。一個(gè)函數(shù)被稱為是 L-smooth 的，如果它的一階導(dǎo)數(shù)（梯度）是 Lipschitz 連續(xù)的，即梯度的變化受到了一定的約束。
  如果存在一個(gè)常數(shù) $L>0$，使得函數(shù) $f$ 的梯度 $?f(x)$ 對(duì)于任意的 $x$ 和 $y$ 滿足以下不等式：$$\Vert ?f(x)??f(y)\Vert \le L\Vert x?y\Vert$$$\Vert ?\Vert$ 是向量的范數(shù)。這個(gè)定義表明函數(shù)的梯度變化受到了 $L$ 的限制，也就是說(shuō)在函數(shù)曲面上相鄰點(diǎn)處的梯度變化是有界的。
• $\mu ?strongly$：描述函數(shù)的彎曲程度，指的是一個(gè)函數(shù)在某種程度上比一個(gè)凸函數(shù)更加強(qiáng)烈地彎曲。如果存在一個(gè)常數(shù) $\mu >0$ ,它滿足以下不等式：$$f(y)\ge f(x)+??f(x),y?x?+\frac{\mu }{2}?\Vert y?x{\Vert }^2$$ $??,??$ 表示內(nèi)積運(yùn)算。這個(gè)不等式表明函數(shù) $f$ 在任意點(diǎn) $x$ 處的曲率至少為 $\mu$，即函數(shù)圖像在局部區(qū)域內(nèi)彎曲程度足夠大。

$L?smooth$ 函數(shù)的特性使得在優(yōu)化問(wèn)題中的求解更為可行和穩(wěn)定。因?yàn)榫哂?Lipschitz 連續(xù)梯度的函數(shù)對(duì)于梯度下降等優(yōu)化算法而言，更容易收斂到局部最優(yōu)解，避免了梯度變化劇烈導(dǎo)致的震蕩或發(fā)散。確保收斂

$\mu ?strongly$ 函數(shù)在局部區(qū)域內(nèi)有一個(gè)嚴(yán)格的下界，這種特性使得優(yōu)化算法能夠更快速地收斂到全局最優(yōu)解。加速收斂

---

解的特性

對(duì)于 $?$ 的最優(yōu)解，它應(yīng)該具備以下三個(gè)特性：

我們將表征局部和全局的兩個(gè)函數(shù) $f(x(\lambda ))$ 和 $\psi (x(\lambda ))$ 視作關(guān)于變量 $\lambda$ 的函數(shù)。

• 特性一： $\psi (x(\lambda ))$ 是非遞增的，對(duì)于 $?\lambda >0$ 有$$\psi (x(\lambda ))\le \frac{f(x(\infty ))?f(x(0))}{\lambda }$$進(jìn)一步 $f(x(\lambda ))$ 是非遞減的，所以 $f(x(\infty ))\ge f(x(\lambda ))$ 。
  
  上述式子表明：隨著 $\lambda$ 的增大，懲罰項(xiàng) $\psi (x(\lambda ))$ 會(huì)逐漸減少到 0 ，因此最優(yōu)的局部模型 $x_i(\lambda )$ 會(huì)隨著 $\lambda$ 的增長(zhǎng)越來(lái)越相似。同時(shí)根據(jù)第二種表述，$f(x(\lambda ))$隨 $\lambda$ 增加而增加，但不超過(guò)標(biāo)準(zhǔn)FL公式的最優(yōu)全局損耗 $f(x(\infty ))$ 。
• 特性二：對(duì)于 $?\lambda >0$ and $1\le i\le n$ 我們可以得到如下最優(yōu)局部解表示：$$x_i(\lambda )=\bar{x}(\lambda )?\frac{1}{\lambda }?f_i(x_i(\lambda ))$$ 進(jìn)一步還有$$\begin{gathered} \sum _{i=1}^n?f_i(x_i(\lambda ))=0 \\ \psi (x(\lambda ))=\frac{1}{2{\lambda }^2}||?f(x(\lambda ))|{|}^2 \end{gathered}$$從平均模型中減去局部梯度的倍數(shù)，可以得到最優(yōu)局部模型。在最優(yōu)狀態(tài)下，局部梯度的總和總是為零。這對(duì) $\lambda =\infty$ 顯然是正確的，但這對(duì) $?\lambda >0$ 都不太明顯。
• 特性三：最優(yōu)局部模型以 $O(1/\lambda )$ 的速度收斂于傳統(tǒng)的FL解。
  令 $P(z):=\frac{1}{n}{\sum }_{i=1}^n{f}_i(z)$ ，此時(shí) $x(\infty )$ 是 $P$ 的唯一最小值，可以得到：$$||?P(\bar{x}(\lambda ))|{|}^2\le \frac{2L^2}{\lambda }(f(x(\infty ))?f(x(0)))$$

$?$ 的解 $x(\lambda )$ 到純局部解 $x(0)$ 和純整體解 $x(\infty )$ 的距離是 $\lambda$ 的函數(shù)。

---