个性化联邦学习算法#
在个性化联邦学习 (Personalized Federated Learning, PFL) 中，每个子节点都寻求一个适合自身数据分布的模型，同时仍受益于其他子节点上的知识。对 PFL 进行建模的一种简单而通用的方式是* 弱共识* (Weak Consensus)：不再强制完全共识 \(\theta_1 = \cdots = \theta_K\) ，而是添加一个惩罚子节点模型之间偏差的正则项 \(\mathcal{R}\) 。本页收集各 PFL 算法（在 fl_sim 中实现的以及密切相关的），并给出它们的建模、理论与伪代码。
L2SGD ：无环局部随机梯度下降#
这一族算法中最简单的是 [Hanzely and Richtárik[1]] 提出的无环随机梯度下降（Loopless Local SGD， L2SGD ）。它考虑如下弱共识问题
其中 \(\lambda \geqslant 0\) 为罚参数，\(\bar{\theta} = \frac{1}{K} \sum_{k=1}^K \theta_k\) 为全局平均模型。当 \(0 < \lambda < \infty\) 时，解 \(\bar{\theta}, \theta_1, \ldots, \theta_K\) 被称作一组* 混合模型* （mixed models）。容易看出，上述问题与 临近算法一节 中 FedProx 所考察的问题等价。
[Hanzely and Richtárik[1]] 没有在每次迭代都计算完整的梯度 \(\nabla F = \nabla f + \lambda \nabla \varphi\) ，而是为 \(F\) 定义了如下无偏随机梯度
其中 \(p \in (0, 1)\) 。注意，计算 \(\nabla f(\Theta) = \col(\nabla f_1(\theta_1), \ldots, \nabla f_K(\theta_K))\) 是完全块分离的：在联邦学习的场景下，这一步只需在客户端本地完成，不涉及与服务器的任何通信，这对以通信为主要瓶颈的联邦学习是巨大的优势。从这个意义上说， L2SGD 已经融入了 无环 （跳步）的思想；参见 跳步算法一节 中的 ProxSkip 。在额外的有限和假设 \(f_k(\theta_k) = \sum_{j=1}^m f_{k,j}(\theta_k)\) 下，还可以进一步把该随机梯度与随机 Kaczmarz 型（重要性采样）更新结合起来；关于无环方法的分析参见 [Kovalev et al.[2]]。由此得到的算法总结如下。
\begin{algorithm}
\caption{PseudoCode for \texttt{L2SGD}}
\begin{algorithmic}
\REQUIRE penalty coefficient $\lambda,$ learning rate $\eta,$ probability $p \in (0, 1)$
\STATE {Initiation:}
\STATE local (clients) model parameters $\theta_k^{(0)} \in \R^d, ~ \forall k \in [K]$
\FOR{each round $t = 0, 1, \cdots, T-1$}
\STATE \COMMENT{with probability $1-p$: no global communication, only clients update}
\STATE \FOR{each client $k \in [K]$ {in parallel}}
\STATE sample $j \in [m]$ (uniformly at random)
\STATE $g_k^{(t)} \gets \frac{1}{K(1-p)} \left( \nabla f_{k,j}(\theta_k^{(t)}) \right)$
\STATE $\theta_k^{(t+1)} \gets \theta_k^{(t)} - \eta g_k^{(t)}$
\STATE \ENDFOR
\STATE \COMMENT{with probability $p$: global communication}
\STATE client $k$ sends $\theta_{k}^{(t)}$ to the server, $\forall k \in [K]$
\STATE {Server Update:}
\STATE $\hspace{1.3em}$ $\theta^{(t)} \gets \frac{1}{K} \sum\limits_{k=1}^K \theta_{k}^{(t)}$ \COMMENT{compute the global average}
\STATE server broadcasts $\theta^{(t)}$ to clients $k \in [K]$
\STATE {Clients Update:}
\STATE \FOR{each client $k \in [K]$ {in parallel}}
\STATE $g_k^{(t)} \gets \frac{\lambda}{Kp} \left( \theta_k^{(t)} - \theta^{(t)} \right)$
\STATE $\theta_k^{(t+1)} \gets \theta_k^{(t)} - \eta g_k^{(t)}$
\STATE \ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}pFedMe ：个性化联邦均值算法#
pFedMe 算法 [Dinh et al.[3]] 考虑了与 (1) 同一族的弱共识问题，其中全局模型作为单一变量 \(\theta \in \R^d\) 出现，
其中 \(\lambda \geqslant 0\) 是罚参数。特别地，文献基于联邦学习中心节点--子节点这一二元结构，进一步将上述问题等价地转换为一个* 双层优化问题* (Bi-level Optimization Problem)，
其内层目标函数 \(F_k(\theta)\) 恰为 \(f_k\) 的 Moreau 包络 \(\mathcal{M}_{f_k, \lambda}(\theta) := \inf_{\theta_k} \{ f_k(\theta_k) + \frac{\lambda}{2} \lVert \theta_k - \theta \rVert^2 \}\) ，而相应的内层极小点即临近算子 \(\prox_{f_k, \lambda}(\theta) := \argmin_{\theta_k} \{ f_k(\theta_k) + \frac{\lambda}{2} \lVert \theta_k - \theta \rVert^2 \}\) 在全局模型 \(\theta\) 处的取值——这个取值正是 pFedMe 算法得到的子节点 \(k\) 上的个性化模型。通过 Moreau 包络与临近算子的关系式可知，外层目标函数的梯度为
如此，对 \(F\) 的一步（随机）梯度下降即分解为子节点侧部分更新 \(\theta^{(t)} - \eta \lambda \left( \theta^{(t)} - \prox_{f_k, \lambda} (\theta^{(t)}) \right)\) 的平均。具体执行时，每个子节点持有全局模型的一份拷贝 \(\omega_k^{(t, r)}\) ，并在两次通信之间交替执行 \(R\) 轮
其中 \(b_r\) 是第 \(r\) 轮的小批量数据；随后中心节点进行聚合
值得特别注意的是，(6) 的两部分并不是交替进行的，而是先在子节点上执行 \(R\) 轮本地迭代，之后才与中心节点通信——这是无环（跳步）思想的又一个实例；参见 L2SGD 以及 跳步算法一节 。伪代码总结如下。
\begin{algorithm}
\caption{PseudoCode for \texttt{pFedMe}}
\begin{algorithmic}
\REQUIRE penalty coefficient $\lambda,$ learning rate $\eta,$ global update smoothing factor $\beta,$ {\bfseries proximal solvers} $\texttt{prox\_update}_k$
\STATE {\bfseries Initiation:}
\STATE $\hspace{1.3em}$ {\bfseries Init server:} global model parameters $\theta^{(0)} \in \mathbb{R}^d$
\STATE $\hspace{1.3em}$ {\bfseries Init clients:} personalized model parameters $\theta_k^{(0)} \in \mathbb{R}^d, ~ \forall k \in [K]$
\FOR{each round $t = 0, \cdots, T-1$}
\STATE Server sends $\theta^{(t)}$ to all clients
\FOR{each client $k = 1, \cdots, K$ in parallel}
\STATE $\omega_{k}^{(t, 0)} = \theta^{(t)}$ \COMMENT{a copy of the global model $\theta^{(t)}$}
\FOR{$r = 0,\cdots, R-1$}
\COMMENT{solve inner problem $\min\limits_{\theta_k \in \mathbb{R}^d} \left\{ f_k(\theta_k) + \frac{\lambda}{2} \left\lVert \theta_k - \theta \right\rVert^2 \right\}$}
\STATE sample a mini-batch $b_r$
\COMMENT{use proximal solver $\texttt{prox\_update}_k$ to solve $\underset{\theta_k}{\text{argmin}} \left\{ \ell_k(\theta_k; b_r) + \frac{\lambda}{2} \left\lVert \theta_k - \omega_{k}^{(t, r)} \right\rVert^2 \right\}, \text{ where } f_k(\theta_k) = \mathbb{E}_{b}[\ell_k(\theta_k; b)]$}
\STATE $\theta_k^{(t, r)} \gets \texttt{prox\_update}_k (\omega_{k}^{(t, r)}; b_r)$
\COMMENT{update the local copy of the global model}
\STATE $\omega_{k}^{(t, r+1)} \gets \omega_{k}^{(t, r)} - \eta \lambda \left( \omega_{k}^{(t, r)} - \theta_k^{(t, r)} \right)$
\ENDFOR
\STATE $\theta_k^{(t+1)} \gets \theta_k^{(t, R)}$ \COMMENT{update the personalized model}
\ENDFOR
\STATE Server uniformly samples a subset of clients $\mathcal{S}^{(t)}$
\STATE each client in $\mathcal{S}^{(t)}$ sends the local model $\omega_{k}^{(t, R)}$ to the server
\STATE Sever update $\theta^{(t+1)} \gets (1-\beta)\theta^{(t)} + \frac{\beta}{\# \mathcal{S}^{(t)}} \sum\limits_{k \in \mathcal{S}^{(t)}} \omega_{k}^{(t, R)}$
\ENDFOR
\STATE final global model: $\theta^* \gets \theta^{(T)}$
\STATE final personalized models: $\theta_k^* \gets \theta_k^{(T)}$
\end{algorithmic}
\end{algorithm}Ditto ：公平且鲁棒的个性化模型#
Ditto 算法 [Li et al.[4]] 进一步发展了 FedProx 添加临近项求解子问题的思想，将其改造为从* 子节点* 视角出发的* 双层* 问题格式（稍早提出的 APFL 也采用了类似的视角，见下文），
其中 \(G\) 是中心节点上对子节点模型执行聚合的规则，例如 FedAvg 中的求均值。解读这一问题格式：内层问题即是仅关于全局模型 \(\theta\) 的一个普通联邦优化问题，而外层问题则为每个子节点附带一个用于个性化的临近任务——且个性化模型 \(\omega_k\) * 不* 参与全局模型的更新。全局模型与个性化模型由此解耦合，两者的迭代更新可以更灵活地进行。
由此，每个子节点每轮求解两个问题：全局模型的更新 \(\theta_k^{(t)} \gets \operatorname{\mathbf{UpdateGlobal}}(\theta^{(t)}, f_k)\) （内层问题），以及解点追踪移动中心 \(\theta^{(t)}\) 的临近任务，
与 FedSplit 或 pFedMe 在内循环中将临近算子求解至（近似）最优不同， Ditto 对外层问题每轮只执行* 一步* （随机）梯度下降，让临近中心 \(\theta^{(t)}\) 随全局模型一起演化。伪代码总结如下。
\begin{algorithm}
\caption{PseudoCode for \texttt{Ditto}}
\begin{algorithmic}
\REQUIRE penalty coefficient $\mu,$ learning rate $\eta,$ methods $\textbf{UpdateGlobal}, \textbf{Aggregate}$
\STATE {\bfseries Initiation:}
\STATE $\hspace{1.3em}$ {\bfseries Init server:} global model parameters $\theta^{(0)} \in \mathbb{R}^d$
\STATE $\hspace{1.3em}$ {\bfseries Init clients:} local model parameters $\omega_k^{(0)} \in \mathbb{R}^d, ~ \forall k \in [K]$
\FOR{each round $t = 0, 1, \cdots, T-1$}
\STATE $\mathcal{S}^{(t)} \gets$ (random set of clients) $\subseteq [K]$
\STATE broadcast $\theta^{(t)}$ to clients $k \in \mathcal{S}^{(t)}$
\FOR{each client $k \in \mathcal{S}^{(t)}$ {\bfseries in parallel}}
\COMMENT{solve the local sub-problem of $G(\dot)$ inexactly starting from $\theta^{(t)}$ to obtain $\theta_k^{(t)}$}
\STATE $\theta_k^{(t)} \gets \textbf{UpdateGlobal}(\theta^{(t)}, f_k)$
\COMMENT{update the personalized model via solving the proximal problem}
\STATE $\omega_k^{(t+1)} \gets \omega_k^{(t)} - \eta \left( \nabla f_k(\omega_k^{(t)}) + \mu (\omega_k^{(t)} - \theta^{(t)}) \right)$
\STATE send $\Delta_k^{(t)} \gets \theta_k^{(t)} - \theta^{(t)}$ to server
\ENDFOR
\STATE {\bfseries Server Update:}
\STATE $\hspace{1.3em}$ $\theta^{(t+1)} \gets \textbf{Aggregate} (\theta^{(t)}, \{ \Delta_k^{(t)} \}_{k \in \mathcal{S}^{(t)}})$
\ENDFOR
\end{algorithmic}
\end{algorithm}APFL ：自适应个性化联邦学习算法#
比 Ditto 稍早提出的 APFL [Deng et al.[5]] 考虑了如下的双层问题
其中 \(\alpha_k \in (0, 1)\) 被称作* 混合权重* (Mixture Weights)。与 (8) 最主要的区别在于个性化的机制：不再是二次临近项，而是将局部目标函数在辅助局部模型与全局模型的凸组合 \(\alpha_k \omega_k + (1 - \alpha_k) \theta^*\) 处取值；混合权重 \(\alpha_k\) 起到与临近项中罚参数 \(\mu\) 类似的调节子节点模型个性化程度的作用。最终得到的个性化模型为
值得特别注意的是：当 \(\mathrm{dom} f_k\) 是 \(\R^d\) 的 真 子集时，(11) 中的凸组合可能无法取到 \(f_k\) 的极小点——凸组合 \(\alpha_k \omega_k^* + (1 - \alpha_k) \theta^*\) 能取到的区域可以只是搜索区域的一个真子集，且不包含极小点。扩大 \(\omega_k\) 的搜索区域固然可以恢复可达性，但此时 \(\hat{\omega}_k\) 完全可以通过直接极小化 \(f_k\) （即仅使用节点自身的数据进行训练）获取——这与个性化联邦学习的目的是相违背的。伪代码总结如下。
\begin{algorithm}
\caption{PseudoCode for \texttt{APFL}}
\begin{algorithmic}
\REQUIRE mixture weights $\alpha_1, \ldots, \alpha_K,$ synchronization gap $\tau$
\STATE {Initiation:}
\STATE $\hspace{1.3em}$ {Init server:} global model parameters $\theta^{(0)} \in \mathbb{R}^d,$ random set of clients $S^{(t)} \subseteq [K]$
\STATE $\hspace{1.3em}$ {Init clients:} local model parameters $\omega_k^{(0)} \in \mathbb{R}^d, ~ \theta_k^{(0)} \gets \theta^{(0)}, ~ \forall k \in [K]$
\STATE $\hspace{1.3em}$ {Constants:} condition number $\kappa \gets \frac{L}{\mu},$ $a \gets \max\{128\kappa, \tau\}$
\FOR{each round $t = 0, 1, \cdots, T-1$}
\FOR{each client $k \in \mathcal{S}^{(t)}$ {in parallel}}
\STATE $\bar{\omega}_k^{(t)} \gets \alpha_k \omega_k^{(t)} + (1-\alpha_k) \theta_k^{(t)}$ \COMMENT{mixture model}
\STATE $\eta^{(t)} \gets \frac{16}{\mu(t+a)}$ \COMMENT{decay learning rate}
\STATE $\theta_k^{(t+1)} \gets \theta_k^{(t)} - \eta^{(t)} \nabla f_k(\theta_k^{(t)})$ \COMMENT{inner problem (global model) update}
\STATE $\omega_k^{(t+1)} \gets \omega_k^{(t)} - \eta^{(t)} \nabla f_k(\bar{\omega}_k^{(t)})$ \COMMENT{outer problem (personalized model) update}
\COMMENT{Optional: adaptive mixture weights update}
\COMMENT{$\alpha_k \gets \alpha_k - \eta^{(t)} \nabla_{\alpha_k} f_k(\bar{\omega}_k^{(t)}) = \alpha_k - \eta^{(t)} \left\langle \omega_k^{(t)} - \theta_k^{(t)}, \nabla f_k(\bar{\omega}_k^{(t)}) \right\rangle$}
\ENDFOR
\IF{$t$ not divides synchronization gap $\tau$}
\STATE {Server updates:} $\mathcal{S}^{(t+1)} \gets \mathcal{S}^{(t)}$
\ELSE
\STATE each client $k \in \mathcal{S}^{(t)}$ sends $\theta_k^{(t+1)}$ to server
\STATE {Server updates:}
\STATE $\hspace{1.3em}$ $\theta^{(t+1)} \gets \frac{1}{\# \mathcal{S}^{(t)}} \sum_{k \in \mathcal{S}^{(t)}} \theta_k^{(t+1)}$
\STATE $\hspace{1.3em}$ $\mathcal{S}^{(t+1)} \gets$ (random set of clients) $\subseteq [K]$
\STATE $\hspace{1.3em}$ broadcast $\theta^{(t+1)}$ to clients $k \in S^{(t+1)}:$ $\theta_k^{(t+1)} \gets \theta^{(t+1)}$
\ENDIF
\ENDFOR
\STATE final personalized model: $\hat{\omega}_k \gets \frac{1}{S_T}\sum\limits_{t=1}^{T} p_t \left( \alpha_k \omega_k^{(t)} + (1-\alpha_k)\frac{1}{\#\mathcal{S}^{(t-1)}}\sum\limits_{k\in\mathcal{S}^{(t-1)}}\theta_k^{(t)} \right)$
\STATE final global model: $\hat{\theta} \gets \frac{1}{S_T}\sum\limits_{t=1}^{T} \frac{p_t}{\#\mathcal{S}^{(t-1)}} \sum\limits_{k\in\mathcal{S}^{(t-1)}}\theta_k^{(t)}$
\STATE where $p_t = (t+a)^2, S_T = \sum\limits_{t=1}^{T}p_t$
\end{algorithmic}
\end{algorithm}FedDyn ：动态正则化联邦学习算法#
前文介绍的算法（以及 FedProx 等）都是以 静态 的临近项正则化局部目标函数：在第 \((t+1)\) 轮，子节点 \(k\) 极小化 \(f_k(\theta_k) + \frac{\mu}{2} \lVert \theta_k - \theta^{(t)} \rVert^2\) 。 FedDyn 算法 [Acar et al.[6]] 对此进行改进，提出了* 动态正则化* 的目标函数，
其可以等价地写为
换言之，对 \(F_k\) 的每一步（随机）迭代都沿着带临近项目标函数的下降方向进行，并用 \(f_k\) 在上一步局部迭代点 \(\theta_k^{(t)}\) 处的线性化（即 \(\mathfrak{g}_k^{(t)} := \nabla f_k(\theta_k^{(t)})\) ）对其加以* 修正* 。动态正则化问题 (12) 另一个值得注意的性质是其一阶最优性条件
由此可得如下的递推格式
即局部梯度估计* 无需* 额外的函数或梯度计算即可维护——这对计算与算法实现是巨大的便利。伪代码总结如下。
\begin{algorithm}
\caption{PseudoCode for \texttt{FedDyn}}
\begin{algorithmic}
\REQUIRE penalty coeffecient $\mu$
\STATE {\bfseries Initiation:}
\STATE $\hspace{1.3em}$ {\bfseries Init server:} global model parameters $\theta^{(0)} \in \mathbb{R}^d,$ $h = 0 \in \mathbb{R}^d$
\STATE $\hspace{1.3em}$ {\bfseries Init clients:} local gradient $\mathfrak{g}_k^{(0)} \gets 0 \in \mathbb{R}^d, ~ \forall k \in [K]$
\FOR{each round $t = 0, 1, \cdots, T-1$}
\STATE $\mathcal{S}^{(t)} \gets$ (random set of clients) $\subseteq [K]$
\STATE broadcast $\theta^{(t)}$ to clients $k \in \mathcal{S}^{(t)}$
\FOR{each client $k \in \mathcal{S}^{(t)}$ {\bfseries in parallel}}
\STATE $\theta_k^{(t+1)} \gets \underset{\theta_k}{\text{argmin}} \left\{ f_k(\theta_k) - \langle \mathfrak{g}_k^{(t)}, \theta_k \rangle + \frac{\mu}{2} \lVert \theta_k - \theta^{(t)} \rVert^2 \right\}$
\STATE $\mathfrak{g}_k^{(t+1)} \gets \mathfrak{g}_k^{(t)} - \mu (\theta_k^{(t+1)} - \theta^{(t)})$ \COMMENT{update local gradient}
\STATE send $\theta_k^{(t+1)}$ to server
\ENDFOR
\STATE {\bfseries Server Update:}
\STATE $\hspace{1.3em}$ $h^{(t+1)} \gets h^{(t)} - \frac{\mu}{K} \left(\sum\limits_{k \in \mathcal{S}^{(t)}} \theta_k^{(t+1)} - \theta^{(t)} \right)$
\STATE $\hspace{1.3em}$ $\theta^{(t+1)} \gets \left( \frac{1}{\# \mathcal{S}^{(t)}}\sum\limits_{k \in \mathcal{S}^{(t)}} \theta_k^{(t+1)} \right) - \frac{1}{\mu} h^{(t+1)}$
\ENDFOR
\end{algorithmic}
\end{algorithm}pFedMac ：极大化相关性的个性化联邦学习算法#
与 FedDyn 的“方向修正”思路相关， pFedMac 算法 [Li et al.[7]] 考虑了如下的双层问题
其中内层问题利用全局模型 \(\theta\) 通过内积对个性化模型 \(\theta_k\) 进行修正。在概率与统计中，\(\langle \theta_k, \theta \rangle\) 量化了个性化模型与全局模型之间的* 相关性* ；因此该技术被称作* 极大化相关性* (Maximizing Correlation)。两个初等的变形将其与上文的问题格式联系起来：把全局项从内层极小化中移出，得 \(F_k(\theta) = F_k'(\theta) + \frac{\mu}{2} \lVert \theta \rVert^2_2\) ，其中 \(F_k'(\theta) := \min_{\theta_k} \{ f_k(\theta_k) - \mu \langle \theta_k, \theta \rangle \}\) ；而配方后可得
即带临近项的目标函数再减去一个关于 \(\theta_k\) 自身的二次项——这正是 (13) 的味道，因此同样的单步方向修正更新在此适用。 pFedMac 进一步借助附加的 \(\ell_1\) 项研究了* 稀疏* 个性化模型，
此外，它还将中心节点--子节点的二元结构扩展为带次中心（边缘节点或枢纽）的* 三层* 结构：每个次中心先聚合一个集群 \(\{ \theta_{k,1}, \ldots, \theta_{k, J_k} \}\) 内的子节点模型，再与中心节点通信——随着联邦网络规模的扩大，这类结构预计会越来越常见，并与聚类联邦学习密切相关。伪代码总结如下。
\begin{algorithm}
\caption{PseudoCode for \texttt{pFedMac}}
\begin{algorithmic}
\REQUIRE learning rate $\eta$, penalty coefficient $\lambda$, $\beta$
\STATE {\bfseries Initiation:} global (server) model parameters $\theta^{(0)} \in \mathbb{R}^d$
\FOR{each round $t = 0, 1, \cdots, T-1$}
\STATE $\mathcal{S}^{(t)} \gets$ (random set of clients) $\subseteq [K]$
\STATE broadcast $\theta^{(t)}$ to clients $k \in \mathcal{S}^{(t)}$
\FOR{each client $k \in \mathcal{S}^{(t)}$ {\bfseries in parallel}}
\STATE $\theta_k^{(t)} \gets$ {\bfseries ClientUpdate}$(k, \theta^{(t)})$
\STATE send $\theta_k^{(t)}$ to server
\ENDFOR
\STATE {\bfseries Server Update:}
\STATE $\hspace{1.3em}$ $\theta^{(t+1)} \gets (1 - \beta) \theta^{(t)} + \frac{\beta}{\lvert \mathcal{S}^{(t)} \rvert} \sum\limits_{k\in \mathcal{S}^{(t)}} \theta_k^{(t)}$
\ENDFOR
\PROCEDURE{ClientUpdate}{$(k, \theta)$} \COMMENT{on client $k$}
\STATE $\omega_k^{(t,0)} = \theta_k^{(t,0)} = \theta^{(t)}$
\FOR{local step $r = 0, 1, \cdots, R-1$}
\STATE $\mathcal{D}_{k, r} \gets$ (sample a mini-batch data)
\STATE $\omega_k^{(t,r)} \gets \argmin_{\omega_k} \left\{ \ell_k(\omega_k; \mathcal{D}_{k, r}) - \lambda \langle \omega_k, \theta_k^{(t,r)} \rangle \right\}$
\STATE $\theta_k^{(t,r+1)} \gets \theta_k^{(t,r)} - \eta\lambda \left( \theta_k^{(t,r)} - \omega_k^{(t,r)} \right)$
\ENDFOR
\RETURN{$\theta_k^{(t,R)}$}
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}FPFC ：融合惩罚联邦聚类#
除了在每对 局部 模型之间的偏差（如 L2SGD ）或局部模型与全局模型之间的偏差上做正则之外，还可以在* 不预先知道簇结构* 的情况下，鼓励客户端聚成若干簇、簇内共享同一模型。融合惩罚联邦聚类（ FPFC ）算法（见 arXiv:2211.04218）通过在模型之差上施加非凸的* 成对* 融合惩罚来实现这一点。引入辅助变量 \(\theta_{ij} \equiv \omega_i - \omega_j\) （\(i, j \in [m]\) ），它考虑
其中 \(\tilde{g}(\cdot)\) 是平滑的 SCAD 型罚函数（由 \(\xi, \lambda, a\) 参数化），其近端算子把较小的成对差收缩到零（同簇的客户端），而几乎不动较大的差（不同簇的客户端）。该问题用 ADMM 式（Douglas--Rachford）分裂求解：增广拉格朗日罚参数为 \(\rho\) ，对偶变量为 \(v_{ij}\) ；每一轮，随机选中的一部分设备在 \(f_i(\omega) + \frac{\rho}{2} \lVert \omega - \zeta_i \rVert^2\) 上做 \(T_i\) 个 epoch 的本地梯度下降，服务器对活跃设备的成对变量 \(\theta_{ij}\) 施加分段近端更新并做对偶上升。训练结束后，\(\lVert \theta_{ij} \rVert\) （近乎）为零的设备 \(i\) 与 \(j\) 被分到同一个簇。伪代码总结如下；注意，无论簇的个数还是簇的成员关系都不需要事先指定。
\begin{algorithm}
\caption{PseudoCode for \texttt{FPFC}}
\begin{algorithmic}
\REQUIRE number of devices $m,$ number of rounds $K,$ local epochs $T_i,$ stepsize $\alpha,$ penalty parameters $\xi, \lambda, a,$ and $\rho$
\STATE {Initiation:}
\STATE $\omega_1^0 = \cdots = \omega_m^0$ on the clients
\STATE $\zeta_i^0 = \omega_i^0$ for $i \in [m]$, $\theta_{ij}^0 = 0$ and $v_{ij}^0 = 0$ for $i, j \in [m]$ on the server
\FOR{each round $k = 0, 1, \cdots, K-1$}
\STATE the server randomly chooses a subset of devices $\mathcal{A}_k$
\STATE the server downloads $\zeta_i^k$ to each device $i \in \mathcal{A}_k$
\STATE \FOR{each device $i \in \mathcal{A}_k$ {in parallel}}
\STATE $\omega_i^{k,0} = \omega_i^k$
\STATE \FOR{$t = 0, 1, \cdots, T_i - 1$}
\STATE $\hspace{1.3em}$ $\omega_i^{k,t+1} = \omega_i^{k,t} - \alpha \left[ \nabla f_i(\omega_i^{k,t}) + \rho \left( \omega_i^{k,t} - \zeta_i^k \right) \right]$
\STATE \ENDFOR
\STATE $\omega_i^{k+1} = \omega_i^{k,T_i}$
\STATE \ENDFOR
\STATE each device $i \in \mathcal{A}_k$ uploads $\omega_i^{k+1}$ to the server
\STATE {Server Update:}
\STATE \FOR{$i, j \in \mathcal{A}_k$ ($i < j$)}
\STATE $\hspace{1.3em}$ $\delta_{ij}^{k+1} = \omega_i^{k+1} - \omega_j^{k+1} + v_{ij}^k / \rho$
\STATE $\hspace{1.3em}$ $\theta_{ij}^{k+1} \gets \underset{\theta}{\text{prox}}$ of the (scaled) fusion penalty at $\delta_{ij}^{k+1}$ (Eq. (6) of the paper)
\STATE $\hspace{1.3em}$ $v_{ij}^{k+1} = v_{ij}^k + \rho \left( \omega_i^{k+1} - \omega_j^{k+1} - \theta_{ij}^{k+1} \right)$
\STATE $\hspace{1.3em}$ $\theta_{ji}^{k+1} = -\theta_{ij}^{k+1}, ~ v_{ji}^{k+1} = -v_{ij}^{k+1}$
\STATE \ENDFOR
\STATE for $i \notin \mathcal{A}_k$ or $j \notin \mathcal{A}_k$: $\theta_{ij}^{k+1} = \theta_{ij}^k, ~ v_{ij}^{k+1} = v_{ij}^k$
\STATE for $i \in [m]$: $\hspace{0.5em}$ $\zeta_i^{k+1} = \frac{1}{m} \sum\limits_{j=1}^m \left( \omega_j^{k+1} + \theta_{ij}^{k+1} - v_{ij}^{k+1} / \rho \right)$
\ENDFOR
\end{algorithmic}
\end{algorithm}FedCR ：基于跨客户端共性表示的个性化联邦学习#
上述方法个性化的是整个局部模型。 FedCR （见 ICML 2023）则将每个局部模型 \(w_i = [w_i^f, w_i^p]\) 解耦为跨客户端共享、在服务器端聚合的特征提取器（主体）:math:w_i^f ，以及保持个性化的预测器（头部）:math:w_i^p 。特征提取器经由共性表示进行对齐：对每个类别 \(c\) ，局部的类条件互信息被约束为接近全局的类条件互信息；借由马尔可夫链 \(y \to x \to z\) ，这等价于类别级的特征对齐
对齐项由拉格朗日乘子 \(\beta \geqslant 0\) 加权（即 CMI 正则项）。表示映射建模为对角高斯分布 \(p(z \mid x_i) = \mathcal{N}\left(z \,\middle|\, \mu(x_i), \Sigma(x_i)\right)\) ；在此之下，难以直接求解的全局后验由活跃客户端集合 \(\mathcal{P}_t\) 的类别级局部后验的专家乘积（PoE）来估计，先验取 \(p(z) = \mathcal{N}(0, 1)\) ：
其中 \(p^c(z \mid x_i)\) 为客户端 \(i\) 上类别 \(c\) 的 \(N_i^{c}\) 个样本的（几何平均）局部专家乘积，直接取自本地训练中最新一轮前向传播的结果。高斯分布的乘积仍为高斯分布，故两个 PoE 都可化为类别级的均值与协方差：每个客户端只需上传其拥有的类别的 \((\mu_i^c, \Sigma_i^c)\) ，服务器经由精度（协方差之逆）解析地合并，
同时对特征提取器做平均：\(w^f = \frac{1}{\lvert \mathcal{P}_t \rvert} \sum_{i \in \mathcal{P}_t} w_i^f\) 。所有活跃客户端都不具备的类别沿用上一轮的统计量。客户端 \(i\) 的局部目标即其经验损失加上上述对齐项，
对随机特征采用重参数化技巧进行优化。由于专家乘积的后验可以比任何单一专家更尖锐，共性表示不仅承载客户端之间的共性信息，也承载互补信息；对齐项同时起到向局部特征注入噪声的作用，可改善泛化与不确定性校准。注意当 \(\beta = 0\) 且 \(\Sigma(x_i) = 0\) （确定性特征）时，该方法退化为 FedPer 。伪代码总结如下。
\begin{algorithm}
\caption{PseudoCode for \texttt{FedCR}}
\begin{algorithmic}
\REQUIRE number of clients $m,$ number of rounds $T,$ local steps $K,$ learning rate $\eta,$ CMI coefficient $\beta$; class-wise initialization $\mu_0^c = 0,$ $\Sigma_0^c = I$ for all classes $c$
\FOR{each round $t = 1, 2, \cdots, T$}
\STATE the server samples a subset of active clients $\mathcal{P}_t$ and sends $w^f$, $\mu_t^c$ and $\Sigma_t^c$ ($\forall c \in \mathcal{C}$) to each $i \in \mathcal{P}_t$
\STATE \FOR{each client $i \in \mathcal{P}_t$ {in parallel}}
\STATE initialize the local model as $w_{i,0} = [w^f, w_i^p]$
\FOR{$k = 1, 2, \cdots, K$}
\STATE $\hspace{1.3em}$ update the whole network by SGD on the local objective:
\STATE $\hspace{1.3em}$ $w_{i,k} = w_{i,k-1} - \eta \nabla L_i$, where
\STATE $\hspace{2.3em}$ $L_i \approx \frac{1}{N_i} \sum\limits_{n=1}^{N_i} \left[ -\log \hat{p}\left( y_i^{(n)} \,\middle|\, z^{(n)} \right) + \beta \, \mathrm{KL}\left[ p(z^{c = y_i^{(n)}} \mid x) \,\middle\|\, p(z \mid x_i^{(n)}) \right] \right]$
\STATE \ENDFOR
\STATE aggregate the class-wise local features via the local PoE: $\mu_i^c, \Sigma_i^c$ for $c \in \mathcal{C}_i$
\STATE keep the personal head $w_i^p = w_{i,K}^p$
\STATE send $w_{i,K}^f$ and $\mu_i^c, \Sigma_i^c$ ($\forall c \in \mathcal{C}_i$) to the server
\STATE \ENDFOR
\STATE {Server Update:}
\STATE average the feature extractors: $w^f = \frac{1}{\lvert \mathcal{P}_t \rvert} \sum\limits_{i \in \mathcal{P}_t} w_{i,K}^f$
\STATE for classes $c$ contained in no active client: keep $\mu_t^c = \mu_{t-1}^c$, $\Sigma_t^c = \Sigma_{t-1}^c$
\STATE aggregate the global class-wise features via the PoE with prior $p(z) = \mathcal{N}(0, 1)$, i.e. for $c$ contained in some active client:
\STATE $\hspace{1.3em}$ $\Sigma_t^c = \left( I + \sum\limits_{i \in \mathcal{P}_t} \left( \Sigma_i^c \right)^{-1} \right)^{-1}$, \quad $\mu_t^c = \Sigma_t^c \sum\limits_{i \in \mathcal{P}_t} \mu_i^c \left( \Sigma_i^c \right)^{-1}$
\STATE send $w^f$, $\mu_t^c$ and $\Sigma_t^c$ ($\forall c \in \mathcal{C}$) to the clients
\ENDFOR
\end{algorithmic}
\end{algorithm}参考文献