Adaptive Personalized Federated Learning
论文地址： https://arxiv.org/abs/2003.13461
摘要
对联邦学习算法个性化程度的研究表明，只有最大化全局模型的性能才会限制局部模型的个性化能力。在本文中，我们提倡自适应个性化联合学习（APFL）算法，其中每个客户端将训练其本地模型，同时为全局模型做出贡献。我们推导出局部模型和全局模型混合的泛化界限，并找到最佳混合参数。我们还提出了一种有效通信的优化方法来协作学习个性化模型并分析其在平滑强凸和非凸设置中的收敛性。大量的实验证明了我们的个性化模式的有效性，以及已建立的泛化理论的正确性。
adaptive personalized federated learning (APFL)
1. Introduction
仅针对全局模型的准确性进行优化会导致本地客户的泛化能力较差。
根据这些观察结果，为了平衡与其他用户协作的好处和不同用户域之间统计异质性的缺点之间的权衡，本文提出了一种自适应个性化联邦学习（APFL）算法旨在为每个用户学习个性化模型，该模型是最佳局部模型和全局模型的混合。我们从理论上分析了个性化模型对局部分布的泛化能力，依赖于混合参数、局部和全局分布之间的差异以及局部和全局训练数据的数量。为了学习个性化模型，我们提出了一种有效通信的优化算法，该算法在学习过程中利用局部模型和全局模型之间的相关性来自适应地学习模型。如图 1 所示，通过逐步增加多样性，与 FedAvg 和 SCAFFOLD 学习的全局模型相比，所提出的算法找到的个性化模型表现出更好的泛化能力。我们用广泛证实的实验结果补充了我们的理论发现，这些实验结果证明了所提出的个性化模式相对于常用 FO 算法的全局和局部模型的优越性。
federated optimization（FO）
Organization
- Section 2. relatework
- Section 3. introduce the APFL & its generalization guarantees
- Section 4. communication-effcient optimization problem
- Section 5. convergence rate
- Section 6. experimental
- Section 7 & 8. discussion & future work
2. Relate work
联邦学习个性化方法主要分为三类： local fine-tuning. multi-task learning, contextualization
- local fine-tuning: 每个客户端接收一个全局模型，并使用自己的局部收据和几个梯度下降步骤进行调整。（元学习、域适应、迁移学习）。
- multi-task learning： 每个客户端的优化可以被视为一个新任务，或者根据某些特征对客户端聚类，将其作为相似任务
- contextualization： 针对一个客户的不同环境设置个性化模型
- personalization via model regularization： 模型正则化，通过规范全局模型和局部模型之间的差异来引入不同的个性化方法。（个性化的知识蒸馏）
- personalization via model interpolation：模型插值
“什么程度的个性化最适合每个客户？” 本文自适应地调整每个客户端地个性化程度来回答这个问题。
PFL personalized fedrated learning
每个客户端都可以访问自己的数据分布Di，对于任何假设h，损失函数定义为l，局部分布的真实风险由 L D i ( h ) = E ( x , y ) ∼ D i [ l ( h ( x ) , y ) ] L_{D_i}(h)=E_{(x,y)\sim D_i}[l(h(x),y)] LDi(h)=E(x,y)∼Di[l(h(x),y)] 表示。由 L ^ D i ( h ) \hat L_{D_i}(h) L^Di(h)来表示h在分布D_i上的经验风险，用均值 D ˉ \bar{D} Dˉ 表示客户端的平均分布。
与联邦学习相同，全局模型通过训练以最小化相对于分布 D ˉ \bar{D} Dˉ 的经验损失，即 min h ∈ H L ^ D ˉ ( h ) \min_{h \in \mathcal{H}} \hat{\mathcal{L}}_{\bar{D}}(h) minh∈HL^Dˉ(h)
3.1 Personalized model
具有自适应权重的局部模型与全局模型相混合的联合预测模型——个性化模型。
对于全局模型，目标仍然是最小化经验风险。
h ˉ ⋆ = arg min h ∈ H L ^ D ˉ ( h ) \bar{h}^\star =\arg\min_{h \in \mathcal{H}} \hat{\mathcal{L}}_{\bar{D}}(h) hˉ⋆=argh∈HminL^Dˉ(h)
对于每个用户的本地模型，则是通过权重 α i \alpha_i αi聚合部分本地模型和部分全局模型,则本地模型的目标为
h ˉ l o c , i ⋆ = arg min h ∈ H L ^ D ˉ ( α i h + ( 1 − α i ) h ˉ ⋆ ) \bar{h}^\star_{loc,i} =\arg\min_{h \in \mathcal{H}} \hat{\mathcal{L}}_{\bar{D}}(\alpha_i h+(1-\alpha_i)\bar{h}^\star) hˉloc,i⋆=argh∈HminL^Dˉ(αih+(1−αi)hˉ⋆)
最后，第i个个性化模型是 h ˉ ⋆ \bar{h}^\star hˉ⋆ 和 h ˉ l o c , i ⋆ \bar{h}^\star_{loc,i} hˉloc,i⋆的凸组合。
h α i = α i h ˉ l o c , i ⋆ + ( 1 − α i ) h ˉ ⋆ h_{\alpha_i}=\alpha_i \bar{h}^\star_{loc,i}+(1-\alpha_i)\bar{h}^\star hαi=αihˉloc,i⋆+(1−αi)hˉ⋆
h α i h_{\alpha_i} hαi不一定是经验风险的最小化，因为是在部分合并全局模型的情况下优化了 h ˉ l o c , i ⋆ \bar{h}^\star_{loc,i} hˉloc,i⋆ 。大多数情况下，如果在从D_i中提取的训练集上进行评估， h α i h_{\alpha_i} hαi将会产生residual risk
3.2 Generalization guarantees
二分类问题考虑squared hinge loss ‘ ( h ( x ) , y ) = ( m a x 0 , 1 − y h ( x ) ) 2 `(h(x), y) = (max{0, 1 − yh(x)})2 ‘(h(x),y)=(max0,1−yh(x))2
回归问题考虑 MSE loss ‘ ( h ( x ) , y ) = ( h ( x ) − y ) 2 `(h(x), y) = (h(x) − y)2 ‘(h(x),y)=(h(x)−y)2
定义1. 一对模型间最坏情况的分歧量化。该度量通过计算样本训练集上两个假设之间的最大分歧来衡量假设类的复杂性。（一种全局模型和局部模型泛化误差间的权衡）
定理1. 前文所提个性化方法的主要结果，由VC维来衡量。的数据量）。会导致全局模型有更好的泛化性，
泛化风险主要取决于下面三种
- m（D中提取的数据量）：相对于个人用户数量较大，全局模型通常由更好的泛化性。
- D与D_i间的散度：平均分布与第i个分布的数据异质性，差异过大会导致全局模型损害局部泛化。
- m_i（D_i提取的数据量）：mi一般较小，局部模型的泛化可能很差。
因此应该选一个小的权重 α i \alpha_i αi来包含更多比例的全局模型。
最优最小参数
RHS (Right-Hand Side),右侧
4 Optimization Method
自动更新权重的自适应算法：将原本的模型分为两阶段优化问题，全局更新共享模型，本地更新用户本地模型。每个本地客户端要解决的问题为：
min v ∈ R d f i ( α i v + ( 1 − α i ) w ⋆ ) \min_{\mathcal{v}\in R^d}f_i(\alpha_i v+(1-\alpha_i)w^\star) v∈Rdminfi(αiv+(1−αi)w⋆)
其中 w ⋆ = arg min w F ( w ) w^\star=\arg\min_w F(w) w⋆=argminwF(w) 为全局最优模型。这两个模型间的平衡由 α i \alpha_i αi 控制。
4.1 Local Descent APFL
双层优化算法Local Descent APFL。服务器随机选择一定的K个客户端作为一组U，每个选定的客户端维护三个模型：全局模型w，自己持有的本地模型v，和混合个性化模型v=alphav+(1-alpha)w，选定的客户端在本地对自己的数据更新w和v两个参数
在本地进行 τ \tau τ轮更新狗后，将各自本地的w发送到服务器，通过均值聚合。
4.2 Adaptive α \alpha α update
注意到 α \alpha α的值与个性化版本和本地版本全局模型的差异及设备内个性化模型的梯度间相关性进行更新的。这表明，当全局模型偏离个性化模型时，α值会发生变化，以调整全局模型捕获的所有设备之间的本地数据和共享知识之间的平衡。显然，当个性化模型和全局模型非常接近时（IID 数据），α 值不会发生太大变化。
5 Convergence Analysis
本节对固定 α \alpha α的APFL在强凸和非凸函数上的收敛性进行分析。
定义2：（梯度多样性） 参数化不变量，parameterization-invariant quantities
定义3：（本地-全局最优性差距）针对强凸，需要以下反应异质性的量
v和w取决于客户端之间本地数据的分布和loss的几何形状。
假设：
5.1 强凸损失函数
假设
定理2：（局部下降 APFL 的全局模型收敛）
定理3：（Local Descent APFL 的个性化模型收敛）
推论1：
定理4：（局部下降 APFL 的个性化模型收敛，无需假设 αi）
5.2 非凸损失函数
定义4：（梯度差异）
6 Experiments
6.1 Setup
- 基本情况：Azure、PyTorch（with ‘distributed’）、F64s虚拟机、每个节点64个vCPU
- Datasets：
- MNIST：每个客户端2类，每个客户端4类，iid
- CIFAR10：每个客户端2类
- EMNIST
- else（除非特殊说明）：learning rate 每 iteration 降低1.本地更新10次
6.2 Results
- strongly convex loss（带有参数正则化的逻辑回归）：不同学习率下的acc和loss对比，iid时fedavg性能更好，noniid时personalized更好。另外更大的学习率对noniid数据集有正面作用。
- 还比较了不同的sample ratio下的训练性能，越大性能越好
- 自适应 α \alpha α 相较于其它结果
- nonconvex loss：Cifar-10 vs FedAvg、SCAFFOLD
- Natural heterogeneous data： EMNIST vs FedAvg
- Comparison with other personalization methods: EMNIST vs FedAvg、PerAvg、pFedMe
7 讨论
- 关于文本所提的适应性：当局部分布远离全局分布时，全局模型对本地模型更新帮助较小，因此改变自适应alpha的值，让本地模型的比例更大，可以更好得适应不同本地分布。
- 面向新节点的个性化（seen task）：
- APFL vs MAML. APFL：不同用户间共享知识，以减少泛化误差；MAML：更关心如何构建元学习器，用更少的样本更快的训练本地个性化模型
- 实验对比，在训练完全局模型后，增加的新节点上，APFL的性能比FedAvg更好。
