Exploiting Shared Representations for Personalized Federated Learning
原文传送门 http://proceedings.mlr.press/v139/collins21a/collins21a.pdf
摘要
深度神经网络已经展示了从图像和文本等数据中提取通用特征表示的能力，这些数据对各种学习任务都很有用。然而，表示学习的成果尚未在联邦环境中完全实现。尽管联合设置中的数据通常是非独立同分布的。跨客户端，集中式深度学习的成功表明数据通常共享全局特征表示，而跨客户端或任务的统计异质性集中在标签中。基于这种直觉，我们提出了一种新颖的联邦学习框架和算法，用于学习跨客户端的共享数据表示和每个客户端的唯一本地头。我们的算法利用客户端的分布式计算能力，针对表示的每次更新，针对低维局部参数执行许多局部更新。我们证明了该方法在线性设置中以接近最优的样本复杂度获得了对ground-truth表示的线性收敛，证明了它可以有效地减少每个客户端的问题维度。此外，我们提供了广泛的实验结果，证明了我们的方法在异构环境中优于替代个性化联邦学习方法的改进。
1、介绍
现代机器学习的许多最引人注目的成功都来自于集中式设置，其中一个模型是在大量集中存储的数据上训练的。 然而，越来越多的数据收集设备需要分布式架构来训练模型。 联邦学习旨在通过提供一个平台来解决这个问题，在该平台中，一组客户端通过利用所有客户端的本地计算能力、内存和数据来协作为每个客户端学习有效的模型（McMahan 等，）。 客户端之间的协调任务由一个中央服务器完成，该服务器组合每轮从客户端接收到的模型并将更新的信息广播给它们。 重要的是，服务器和客户端仅限于满足通信和隐私约束的方法，从而阻止它们直接应用集中式技术。
然而，联邦学习中最重要的挑战之一是数据异构性问题，其中客户端任务的基础数据分布可能彼此之间存在很大差异。 在这种情况下，如果服务器和客户端学习单个共享模型（例如，通过最小化平均损失），则生成的模型对于网络中的许多客户端可能表现不佳（并且也不能很好地泛化不同的数据（Jiang 等人） ., ))。 事实上，对于一些客户来说，简单地使用他们自己的本地数据（即使它很小）来训练一个本地模型可能会更好； 参见图 1。最后，（联合）训练模型可能无法很好地推广到未参与训练过程的看不见的客户。 这些问题提出了这个问题：
“我们如何在数据异构环境中利用所有客户的数据和计算能力来为每个客户学习个性化模型？”
我们通过利用客户之间的共同表示来解决这个问题。 具体来说，我们将数据异构联邦学习问题视为可能具有某些共同结构的 n 个并行学习任务，我们的目标是学习和利用这种共同表示来提高每个客户端模型的质量。事实上，这与我们对集中学习的理解一致，我们见证了通过利用流行机器学习任务（例如，图像分类、下一个词的预测）中的通用（低维）表示同时训练多个任务的成功。 预测）（Bengio 等人，；LeCun 等人，）。
主要贡献：我们介绍了一种新颖的联邦学习框架和一种用于数据异构设置的相关算法。接下来，我们介绍我们的主要贡献。
(i) FedRep 算法。联邦表示学习 (FedRep) 利用跨客户端存储的全部数据量，使用基于梯度的更新来学习全局低维表示。此外，它使每个客户端能够计算一个个性化的低维分类器，我们称之为客户端的本地头，它解释了每个客户端本地数据的唯一标签。
(ii) 收敛速度。我们展示了 FedRep 以指数级快速收敛到最优表示，并且样本复杂度接近最优，在每个客户端旨在使用两层线性神经网络解决线性回归问题的情况下。
(iii) 实验结果。通过合成的和真实的数据集（CIFAR10、CIFAR100、FEMNIST、Sent140）的组合，我们展示了 FedRep 在以下方面的优势：（a）利用许多本地更新，（b）对不同级别的异质性的鲁棒性，（c ) 推广到新客户。我们考虑了几个重要的基线，包括 FedAvg (McMahan et al., )、Fed-MTL (Smith et al., )、LG-FedAvg (Liang et al., ) 和 Per-FedAvg (Fallah et al., ）。我们的实验表明，FedRep 在共享全局表示的异构设置中优于这些基线。
FedRep 的好处：接下来，我们列出 FedRep 相对于标准联邦学习（学习单个模型）的优势。
（一）更多本地更新。通过减少问题维度，每个客户端可以在每轮通信中进行许多本地更新，这有利于学习自己的个人头脑。这与标准联邦学习不同，在标准联邦学习中，异构环境中的多个本地更新会使每个客户端远离最佳平均表示，从而损害性能。
（二）合作的成果。将 ddd 表示为数据维度，将nnn 表示为客户端数量。从我们的样本复杂度界限可以看出，对于 FedRep，每个客户端的样本复杂度缩放为 Θ(log(n)+d/n)\Theta(log(n) + d/n)Θ(log(n)+d/n)。另一方面，本地学习（没有任何协作）的样本复杂度为Θ(d)\Theta(d)Θ(d)。因此，如果1≪n≪eΘ(d)1 \ll n \ll e^{\Theta(d)}1≪n≪eΘ(d)（详见第 4.2 节），我们期望通过联合进行协作的好处。当 ddd 很大时（这在实践中很典型），eΘ(d)e^{\Theta(d)}eΘ(d) 呈指数级增长，并且联合对每个客户端都有帮助。据我们所知，这是第一个基于样本复杂度的异构联邦学习结果，展示了合作的好处。
（三）向新客户端推广。对于一个新的客户端，由于有现成的表示，客户端只需要学习一个具有kkk维低维表示的头部即可。因此，其样本复杂度仅按 Θ(klog(1/e))\Theta(k log(1/e))Θ(klog(1/e)) 缩放，准确度误差不超过eee。
相关工作。最近的各种工作已经使用例如局部微调（Wang 等人，；Yu 等人，）、元学习（Chen 等人，；Khodak 等人）研究了联邦学习中的个性化。 ., ;Jiang et al., ; Fallah et al., )，局部和全局模型的加性混合 (Hanzely & Richta ́rik, ; Deng et al., ; Mansour et al., )，以及多任务学习（Smith 等人，）。在所有这些方法中，每个客户的子问题仍然是全维的——没有学习降维的局部参数集的概念。最近，Liang 等人。 () 还提出了一种用于联邦学习的表示学习方法，但他们的方法试图学习许多局部表示和单个全局头，而不是单个全局表示和多个局部头。早些时候，Arivazhagan 等人。 () 提出了一种学习局部头部和全局网络体的算法，但他们的局部程序联合更新头部和身体（使用相同数量的更新），并且他们没有为他们提出的方法提供任何理论依据。同时，另一项工作研究了异构环境中的联邦学习（Karimireddy 等人，；Wang 等人，；Pathak & Wainwright，；Haddadpour 等人，；Reddi 等人， ; Reisizadeh et al., ; Mitra et al., )，这些工作中基于优化的见解可用于补充我们的公式和算法。
2 、问题表述
具有 nnn 个客户端的联邦学习的一般形式是
其中fif_{i}fi和qiq_{i}qi分别是第iii个客户端的误差函数和学习模型，QnQ_{n}Qn是nnn个模型的可行集空间。 我们考虑一个监督设置，其中第iii个客户端的数据由分发服务器 (xi,yi)∼Di(x_{i}, y_{i}) \sim D_{i}(xi,yi)∼Di 生成。 学习模型qi:Rd→Yq_{i}:R^{d} \rightarrow Yqi:Rd→Y 将输入xi∈Rdx_{i} \in R^{d}xi∈Rd映射到预测标签 qi(xi)∈Yq_{i}(x_{i}) \in Yqi(xi)∈Y，我们希望将其与真实标签yiy_{i}yi 相似。 误差 fif_{i}fi 的形式是对 DiD_{i}Di 的预期风险，即 fi(qi):=E(xi,yi)∼Di[l(qi(xi),yi)]f_{i}(q_{i}) := E_{(x_{i},y_{i}) \sim D_{i}} [l(q_{i}(x_{i}), y_{i})]fi(qi):=E(xi,yi)∼Di[l(qi(xi),yi)]，其中 l:Y×Y→Rl: Y \times Y \rightarrow Rl:Y×Y→R 是一个损失函数，它惩罚 qi(xi)q_{i}(x_{i})qi(xi) 与 yiy_{i}yi 的距离。
为了最小化fif_{i}fi，第iii个客户端访问来自 DiD_{i}Di的具有MiM_{i}Mi个标记样本 {(xij,yij)}j=1Mi\{(x_{i}^{j} , y_{i}^{j} )\}^{M_{i}}_{j=1}{(xij,yij)}j=1Mi的数据集进行训练。联邦学习解决了MiM_{i}Mi相对于问题维度通常较小的设置，而客户端数量nnn很大的情况。 因此，客户端可能无法通过仅在其 $M_{i} 本地样本上完全本地训练来获得具有较小预期风险的解 qiq_{i}qi。 相反，联邦学习使客户端能够通过与中央服务器交换消息进行合作，以便使用所有客户端的累积数据来学习模型。
联邦学习的标准方法旨在学习单个共享模型 q=q1=⋯=qnq = q_{1} = \dots = q_{n}q=q1=⋯=qn，该模型在客户端平均表现良好（McMahan 等人，；Li 等人，）。 通过这种方式，客户旨在解决问题 (1) 的特殊版本，即在选择共享模型qqq 时最小化 (1/n)∑ifi(q)(1/n) \sum_{i} f_{i}(q)(1/n)∑ifi(q)。 但是，这种方法可能会产生一种解决方案，该解决方案在数据分布 DiD_{i}Di 因客户端而异的异构环境中表现不佳。 实际上，在存在数据异质性的情况下，误差函数fif_{i}fi将具有不同的形式，并且它们的最小化器也不相同。 因此，学习共享模型 qqq 可能无法很好地解决问题 (1)。 这需要寻找更个性化的解决方案 {qi}\{q_{i}\}{qi}，这些解决方案可以使用客户数据以联合方式学习。
学习一个共同的表示。我们受到来自集中式机器学习的见解的启发，这些见解表明，尽管具有不同的标签，但分布在任务中的异构数据可能共享一个共同的表示（Bengio et al., ; LeCun et al., ）； 例如，跨多种类型的图像或跨单词预测任务共享特征。 使用这种通用（低维）表示，可以使用线性分类器或浅层神经网络简单地学习每个客户端的标签。
形式上，我们考虑一个由全局表示组成的设置 qϕ:Rd→Rkq_{\phi} : R^{d} \rightarrow R^{k}qϕ:Rd→Rk，它是一个由 ϕ∈Φ\phi\in\Phiϕ∈Φ 参数化的函数，它将数据点映射到维度 kkk 的较低空间，以及特定于客户端的头 qhi：Rk→Yq_{h_{i}}：R^{k}\rightarrow Yqhi：Rk→Y，它们是由 hi∈Hh_{i} \in Hhi∈H 参数化的函数，用于i∈[n]i \in [n]i∈[n]，从低维表示空间映射到标签空间。 第 iii 个客户端的模型是客户端的本地参数和表示形式的组合：qi(x)=(qhi∘qϕ)(x)q_{i}(x) = (q_{h_{i}} \circ q_{\phi})(x)qi(x)=(qhi∘qϕ)(x)。 至关重要的是，k≪dk \ll dk≪d，这意味着每个客户端必须在本地学习的参数数量可能很少。 因此，我们可以假设任何客户端的任何固定表示的最佳分类器都易于计算，这激发了以下重写的全局目标：
为了便于记号，我们使用了简写fi(hi,ϕ):=fi(qhi∘qϕ)f_{i}(h_{i},\phi ) := f_{i}(q_{h_{i}} \circ q_{\phi} )fi(hi,ϕ):=fi(qhi∘qϕ)。 在我们提出的方案中，客户端合作使用所有客户端的数据来学习全局模型，同时他们使用他们的本地信息来学习他们的个性化头部。 我们将在第 3 节中详细讨论这一点。
2.1 与标准联邦学习的比较
为了正式证明我们的公式在具有共享表示的异构设置中优于标准（单模型）联邦学习公式的优势，我们研究了具有二次损失的线性表示设置。正如我们将在下面看到的，标准联邦学习无法恢复面对异质性的潜在表示，而我们的公式确实可以恢复它。
考虑一个设置，其中函数 fif_{i}fi 是二次损失函数，表示qϕq_{\phi}qϕ 是在矩阵 B∈Rd×kB \in R^{d \times k}B∈Rd×k 给出的 RdR^{d}Rd 的 kkk 维子空间上的投影，第 iii 个客户端的局部头部 qhiq_{h_{i}}qhi 是向量 wi∈Rkw_{i} \in R^{k}wi∈Rk .在此设置中，我们对客户端 {Di}i\{D_{i}\}_{i}{Di}i 的本地数据进行建模，使得 yi=wi∗⊤B∗⊤xiy_{i} = {w_{i}^{*\top}} {B^{*\top}} x_{i}yi=wi∗⊤B∗⊤xi 用于某些真实表示 B∗∈Rd×kB^{*} \in R^{d \times k}B∗∈Rd×k 和本地头部 wi∗∈Rkw_{i}^{*} \in R^{k}wi∗∈Rk。该设置将在第 4 节中详细描述。具体而言，可以证明数据分布 DiD_{i}Di 上的预期误差具有以下形式：fi(wi,B)≔12∥Bwi−B∗wi∗∥22f_{i}(w_{i}, B) \coloneqq \frac{1}{2}{\Vert Bw_{i} - B^{*}w_{i}^{*}\Vert}_{2}^{2}fi(wi,B):=21∥Bwi−B∗wi∗∥22。
因此，问题 (2) 变为
相比之下，标准的联邦学习方法旨在为所有客户学习一个共享模型(B，w)(B，w)(B，w)，解决:
让(B^,{w^i})(\hat B,\{ \hat w_{i}\})(B^,{w^i})代表一个公式（3）的一个全局最小化器。因此我们有 B^w^i=B∗wi∗\hat B\hat w_{i} = B^{*}w_{i}^{*}B^w^i=B∗wi∗对于所有i∈[n]i \in [n]i∈[n]。此外，不难看出 (B◊,w◊)(B^{\Diamond},w^{\Diamond})(B◊,w◊) 是 (4) 的全局最小化器，当仅当B◊w◊=B∗(1n∑i=1nwi∗)B^{\Diamond}w^{\Diamond}=B^{*}(\frac{1}{n}\sum^{n}_{i=1}w^{*}_{i})B◊w◊=B∗(n1∑i=1nwi∗)。因此，我们的公式找到了一个全局误差为零的精确解，而标准联邦学习的全局误差为12n∑i=1n∥1nB∗∑i′=1n(wi′∗−wi∗)∥22\frac{1}{2n}\sum^{n}_{i=1}{\Vert \frac{1}{n}B^{*}\sum^{n}_{i^{'}=1}(w^{*}_{i^{'}}-w^{*}_{i})\Vert}^{2}_{2}2n1∑i=1n∥n1B∗∑i′=1n(wi′∗−wi∗)∥22，它随着wi∗w^{*}_{i}wi∗的异质性而增长。 此外，由于求解我们的公式提供了nnn 个矩阵方程，随着wi∗w^{*}_{i}wi∗张成的RkR^{k}Rk，我们可以完全恢复B∗B^{*}B∗的列空间。 相反，求解 (4) 只产生一个矩阵方程，因此对于任何 k>1k > 1k>1，没有希望恢复B∗B^{*}B∗的列空间。
3、FedRep算法
FedRep 通过在客户端之间分配计算来解决问题 (2)。 服务器和客户端旨在一起学习全局表示的参数，而第iii个客户端旨在本地学习其唯一的本地头（见图 2）。 为此，FedRep 在每一轮通信中交替进行客户端更新和服务器更新。
客户端更新。在每一轮中，选择恒定分数 r∈(0,1]r \in (0, 1]r∈(0,1] 的客户端来执行客户端更新。在客户端更新中，客户端iii进行τ\tauτ次基于局部梯度的更新，以在由服务器通信给定的当前全局表示ϕt\phi^{t}ϕt的情况下求解其最优头部。即，对于
s=1,...,τs = 1,...,\taus=1,...,τ，客户端 iii 更新其头部如下：
其中 GRD(f,h,α)GRD(f, h, \alpha)GRD(f,h,α) 是使用函数 fff 相对于hhh的梯度和步长 α\alphaα 来更新变量 hhh 的通用符号。 例如，GRD(fi(hit,s,ϕt),hit,s,α)GRD(f_{i}(h^{t,s}_{i},\phi^{t}), h^{t,s}_{i}, \alpha)GRD(fi(hit,s,ϕt),hit,s,α)可以是一步梯度下降、随机梯度下降（SGD）、带动量的SGD等。关键是客户端iii做了很多本地更新，即τ\tauτ很大，来根据其本地数据找到最佳头部， 给出从服务器接收到的最新表示ϕt\phi^{t}ϕt。
服务器更新。一旦关于头部 hih_{i}hi 的局部更新完成，客户端通过对当前表示进行一次基于局部梯度的更新来参与服务器更新，即计算
然后它将 ϕit+1\phi^{t+1}_{i}ϕit+1 发送到服务器，服务器平均所有本地更新以计算下一个表示ϕt+1\phi^{t+1}ϕt+1。 整个过程在算法 1 中进行了概述。
4、低维线性表示
在本节中，我们使用二次损失函数和线性模型分析问题 (2) 的一个实例，如第 2.1 节所述。 在这里，每个客户端的问题是用两层线性神经网络解决线性回归。 特别是，每个客户端 iii 尝试在低维子空间 B∈Rd×kB \in R^{d\times k}B∈Rd×k和唯一回归量 wi∈Rkw_{i} \in R^{k}wi∈Rk 上找到共享全局投影，它们一起准确地将其样本 xi∈Rdx_{i} \in R^{d}xi∈Rd 映射到标签 yi∈Ry_{i} \in Ryi∈R。矩阵 BBB 对应表示ϕ\phiϕ，wiw_{i}wi 对应于第 iii 个客户端的本地头 hih_{i}hi。 因此我们有 (qhi∘qϕ)(xi)=wi⊤B⊤xi(q_{h_{i}} \circ q_{\phi})(x_{i})= {w_{i}^{\top}} {B^{\top}} x_{i}(qhi∘qϕ)(xi)=wi⊤B⊤xi。 因此，客户端 iii 的损失函数由下式给出：
意味着全局目标是：
其中 W=[w1⊤,...,wn⊤]∈Rn×kW = [w_{1}^{\top}, . . . , w_{n}^{\top}] \in R^{n\times k}W=[w1⊤,...,wn⊤]∈Rn×k 是客户端特定头的串联。 为了评估 FedRep 学习准确表示的能力，我们对本地数据集 {Di}i\{D_{i}\}_{i}{Di}i进行建模，使得对于i=1...,ni = 1 . . . , ni=1...,n
对于一些真实的表示 B∈Rd×kB \in R^{d\times k}B∈Rd×k 和局部头 wi∗∈Rkw^{*}_{i} \in R^{k}wi∗∈Rk,即标准回归设置。 换句话说，所有客户的最优解都存在于 RdR^{d}Rd 的相同 kkk 维子空间中，其中 kkk 被假定为很小。 此外，我们对样本 xix_{i}xi 做出以下标准假设。
假设 1（亚高斯设计）。 样本 xi∈Rdx_{i} \in R^{d}xi∈Rd是 i.i.d。 均值为 0，协方差 IdI_{d}Id ，并且是 IdI_{d}Id -sub-gaussian，即对于所有v∈Rdv \in R^{d}v∈Rd有E[ev⊤xi]≤e∥v∥22/2E[e^{v^{\top}x_{i}}] \leq e^{\Vert v \Vert^{2}_{2}/2}E[ev⊤xi]≤e∥v∥22/2。
4.1 FedRep
接下来我们将讨论 FedRep 如何尝试在此设置中恢复最佳表示。 首先，服务器和客户端执行矩方法来学习初始表示。 然后，客户端和服务器更新以交替方式执行，如下所示。
客户端更新。与算法 1 一样，在第 ttt轮选择 rnrnrn 个客户端来更新他们当前的本地头部witw_{i}^{t}wit和全局表示 BtB^{t}Bt。 每个选定的客户端 iii 根据其本地数据分布 DiD_{i}Di 对 mmm 个样本的新批次 {(xit,j,yit,j)}j=1m\{(x_{i}^{t,j} , y_{i}^{t,j} )\}^{m}_{j=1}{(xit,j,yit,j)}j=1m 进行采样，以用于在其被选中的每一轮 ttt 上更新其头部和表示。 也就是说，在这一轮中，客户 iii 考虑批量损失
由于 f^it\hat f^t_if^it 相对于 witw_i^twit 是强凸的，客户端可以在最多 log(1/ϵ)log(1/\epsilon)log(1/ϵ) 局部梯度更新后找到一个局部头部的更新，该更新是ϵ\epsilonϵ接近 (7) 的全局最小值。 或者，由于该函数也是二次函数，客户端可以直接在 Θ(mk2+k3)\Theta(mk^2 + k^3)Θ(mk2+k3) 操作中求解最优 www。 因此，为了简化分析，我们假设每个选定的客户端在每轮本地更新期间获得 wit+1=argminwf^it(w,Bt)w^{t+1}_{i} = argmin_w \hat f_i^t (w, B^t )wit+1=argminwf^it(w,Bt)。
服务器更新。更新其头部后，客户端 iii 使用相同的mmm 个样本通过梯度下降一步更新全局表示，并将更新发送到服务器，如算法 2 中所述。然后，服务器通过对接收到的表示进行平均来计算新的表示。
4.2 分析
如前所述，在 FedRep 中，每个客户端iii 执行交替最小化下降方法来解决 (7) 中的非凸目标。 这意味着在第ttt 轮所有客户端的全局损失由下式给出
该目标具有许多全局最小值，包括所有矩阵对 (Q−1W∗,B∗Q⊤)(Q^{-1} W^{*}, B^{*}Q^{\top})(Q−1W∗,B∗Q⊤)，其中 Q∈Rk×kQ \in R^{k\times k}Q∈Rk×k 是可逆的，从而消除了准确恢复基本事实因子 (W∗,B∗)(W^* , B^* )(W∗,B∗) 的可能性。 相反，服务器的最终目标是恢复真实表示，即B∗B^{*}B∗的列空间。 为了评估列空间恢复的紧密程度，我们将子空间之间的距离定义如下。
定义 1.B1,B2∈Rd×kB_1 , B_2 \in R^{d\times k }B1,B2∈Rd×k的列空间之间的主角距离由下式给出
B^1,⊥\hat B_{1,\perp}B^1,⊥和B^2,⊥\hat B_{2,\perp}B^2,⊥ 是满足 span(B^1,⊥)=span(B1)⊥span(\hat B_{1,\perp})= span(B_1)^{\perp}span(B^1,⊥)=span(B1)⊥ 和span(B^2)=span(B2)span(\hat B_{2})= span(B_2)span(B^2)=span(B2)。
主角距离是测量子空间之间距离的标准度量（例如（Jain et al., ））。 接下来，我们做两个正则性假设。
假设 2（客户多样性）。 令σˉmin,∗\bar{\sigma}_{min,*}σˉmin,∗是任何矩阵Wˉ∈Rrn×k\bar{W} \in R^{rn \times k}Wˉ∈Rrn×k 的最小奇异值，其中行是真实客户特定参数 {w1∗,...,wn∗}\{w^*_1,...,w^*_n\}{w1∗,...,wn∗}的 rnrnrn 大小子集。那么σˉmin,∗>0\bar{\sigma}_{min,*}>0σˉmin,∗>0。
假设 2 表明，如果我们选择任何 rnrnrn 个客户，他们的最优解张成 RkR^kRk。 事实上，这个假设很弱，因为我们预计参与客户的数量 rnrnrn 大大大于 kkk。 请注意，如果我们没有张成RkR^kRk 的客户端解决方案，恢复 B∗B^*B∗ 将是不可能的，因为样本 (xij,yij)(x^j_i , y_i^j )(xij,yij) 可能永远不会包含有关 B∗B^*B∗ 的一个或多个特征的任何信息。
假设 3（客户端规范化）。 对于所有 i∈[n]i \in [n]i∈[n]，真实客户端特定参数满足 ∥wi∗∥2=k\Vert w^*_i \Vert _2 = \sqrt k∥wi∗∥2=k，并且B∗B^*B∗具有正交列。
假设 2 确保真值矩阵W∗B∗⊤W^*B^{*^{\top}}W∗B∗⊤ 是逐行不连贯的，即其行范数具有相似的幅度。 我们在附录 B 中正式定义了这一点。真实矩阵的不连贯性是高效矩阵补全和其他稀疏测量感知问题所需的关键属性（Chi et al., ）。 由于我们的测量矩阵是逐行稀疏的，因此我们需要基本事实的逐行不连贯性。 请注意，假设 3 可以放宽以允许 ∥wi∗∥2≤O(k)\Vert w^*_i \Vert _2 \leq O( \sqrt k)∥wi∗∥2≤O(k)，因为精确的归一化只是为了简化分析。
我们的主要结果表明，FedRep 在此设置中生成的迭代Btt{B^t}_tBtt 线性收敛到主角距离的最佳表示 B∗B_*B∗。
定理1 定义E0≔1−dist2(B^0,B^∗)E_0 \coloneqq 1-dist^2(\hat B^0,\hat B^*)E0:=1−dist2(B^0,B^∗)和σˉmax,∗≔maxI∈[n],∣I∣=rnσmax(1rnWI∗)\bar{\sigma}_{max,*} \coloneqq max_{I \in [n],|I|=rn} \sigma _{max}(\frac{1}{\sqrt{rn}}W^*_I)σˉmax,∗:=maxI∈[n],∣I∣=rnσmax(rn1WI∗)和σˉmin,∗≔minI∈[n],∣I∣=rnσmin(1rnWI∗)\bar{\sigma}_{min,*}\coloneqq min_{I \in [n],|I|=rn} \sigma _{min}(\frac{1}{\sqrt{rn}}W^*_I)σˉmin,∗:=minI∈[n],∣I∣=rnσmin(rn1WI∗),即任何矩阵的最大和最小奇异值，可以通过取 1rnW∗\frac{1}{\sqrt{rn}}W^*rn1W∗ 的rnrnrn 行。让κ≔σˉmax,∗/σˉmax,∗\kappa \coloneqq \bar{\sigma}_{max,*}/\bar{\sigma}_{max,*}κ:=σˉmax,∗/σˉmax,∗ ,对于一些绝对常数 ccc假设m≥c(κ4k3log(rn)/E02+κ4k2d/(E02rn))m\geq c(\kappa^4k^3log(rn)/E^2_0+\kappa^4k^2d/(E^2_0rn))m≥c(κ4k3log(rn)/E02+κ4k2d/(E02rn))。 那么对于任何 ttt 和任何η≤1/(4σˉmax,∗2)\eta \leq 1/(4\bar{\sigma}_{max,*} ^2)η≤1/(4σˉmax,∗2),我们有
概率至少为1−Te−100min(k2log(rn),d)1-Te^{-100min(k^2log(rn),d)}1−Te−100min(k2log(rn),d)
根据假设 2，我们有σˉmin,∗2>0\bar{\sigma}_{min,*} ^2>0σˉmin,∗2>0，因此 (10) 的 RHS 严格随着 TTT 减小，以获得适当的步长。 考虑到 mmm 的复杂性和算法以指数速度快速收敛的事实，每个客户端在主角距离上达到ϵ\epsilonϵ精确解所需的样本总数为 Θ(mlog(1/ϵ))\Theta(m\log(1/\epsilon))Θ(mlog(1/ϵ))，即
接下来，关于这个样本复杂性的一些评论如下。
联邦何时以及向谁提供帮助？观察到，对于没有协作的单个客户，样本复杂性按Θ(d)\Theta(d)Θ(d)缩放。然而，对于 FedRep，样本复杂度按Θ(log(n)+d/n)\Theta(\log(n)+d/n)Θ(log(n)+d/n)缩放。因此，只要log(n)+d/n≪d\log(n)+d/n \ll dlog(n)+d/n≪d，联邦就会有所帮助。这适用于几种设置，例如当 1≪n≪eΘ(d)1 \ll n \ll e^{\Theta(d)}1≪n≪eΘ(d) 时。在实际场景中，ddd（数据维度）很大，因此eΘ(d)e^{\Theta(d)}eΘ(d)呈指数级增长；因此，协作可以帮助每个客户。此外，从后来进入系统的新客户端的角度来看，它有一个免费可用的表示，并且这个新客户端适应其任务的样本复杂度仅为 klog(1/ϵ)k \log(1/\epsilon)klog(1/ϵ)。因此，整个系统的好处（已经学习了一个表示，这对新客户很有用，因为它现在只需要学习一个头部），并且每个参与联合培训的个人客户也受益。
连接到矩阵传感器。（6）中的问题是矩阵感知的一个例子；有关详细信息，请参见附录 B 中的证明。考虑到这种联系，我们的理论结果也有助于矩阵传感的理论研究。尽管矩阵传感是一个经过充分研究的问题，但我们的设置提出了两个新的分析挑战：（i）由于测量中的行稀疏性，传感算子在有效的范围内不满足常用的受限等距属性（RIP）样本数量，即它不能有效地集中在所有 rank-kkk 矩阵上的恒等运算，(ii) FedRep 执行一种新颖的非对称过程。我们在附录 B.5 中进一步讨论了这些挑战。据我们所知，定理 1 为解决矩阵感知问题的交替最小化下降过程提供了第一个收敛结果。这也是第一个显示任何解决方案对具有秩一、逐行稀疏测量的矩阵传感的样本有效线性收敛的结果。钟等人给出了最接近我们的矩阵传感设置的最新结果。 () 对于 rank-1、独立的高斯测量，我们的结果与 Θ(κ2)\Theta(\kappa^2)Θ(κ2)因子匹配。然而，我们的设置更具挑战性，因为我们有 rank-1 和 row-wise 稀疏测量，并且之前在稀疏测量的设置中观察到对 κ4\kappa^4κ4 的依赖性，例如矩阵完成（Jain et al., ）。
新用户和降维。定理 1 与在多任务学习的背景下研究表示学习的工作有关。特里普拉尼尼等人（）和Duet al (）提供了泛化误差的上限，该误差是由于学习假设共享共同表示的任务的低维表示而导致的。他们表明，如果学习了通用表示，那么新任务上的额外风险界限为 O(C(Φ)nm+kmnew)O(\frac{C(\Phi)}{nm}+\frac{k}{m_{new}})O(nmC(Φ)+mnewk)，其中 C(Φ)C(\Phi)C(Φ) 是表示类的复杂度，mmm 是来自学习者可以用于微调的新任务。由于测试样本的数量必须仅超过 O(k)O(k)O(k)，其中假设 kkk 很小，因此这些工作证明了表示学习的降维优势。我们的工作通过展示如何可证明和有效地学习线性情况下的表示来补充这些结果。
初始化备注。定理 1 要求初始主角距离 dist(B^0,B^∗)(\hat B^0 , \hat B^ *)(B^0,B^∗)大于常数 c>0c > 0c>0。这可以通过矩量法来实现，而无需将每个客户的样本复杂度增加到对数因子 (Tripuraneni et等人，）。反过来，每个用户必须在学习过程开始时向服务器发送他们数据的多项式，即 ∑j=1m(yij)2xij(xij)⊤\sum ^m_{j=1}(y_i^j)^2x^j_i (x^j_i )^{\top}∑j=1m(yij)2xij(xij)⊤，这不会损害隐私。我们在附录 B 中讨论了这方面的细节。
5. 实验
我们在实验中关注三点：（i）许多本地更新对 FedRep 中本地头的影响（ii）FedRep 学习的全局表示的质量以及（iii）FedRep 对广泛数据集的适用性。完整的实验细节在附录 A 中提供。
5.1 综合数据
我们首先尝试第 4 节中分析的多线性回归问题的一个实例。根据这个公式，我们生成合成样本xij∼N(0,Id)x_i^j \sim N(0,I_d)xij∼N(0,Id)和标签yij∼N(wi∗⊤B^∗⊤xij,10−3)y^j_i \sim N(w_i^{*^{\top}} \hat B^{*^{\top}}x_i^j,10^{-3})yij∼N(wi∗⊤B^∗⊤xij,10−3)。客户端 i∈[n]i \in [n]i∈[n] 的 真实头 wi∗∈Rkw_i^*\in R^kwi∗∈Rk 和真实表示 B^∗∈Rd×k\hat B^* \in R^{d\times k}B^∗∈Rd×k 是通过对高斯矩阵进行采样和归一化随机生成的。
找到最佳头部的好处。我们首先证明 FedRep 的收敛性随着客户端 nnn 的增加而提高，使其高度适用于联合设置。此外，我们提供的证据表明，这种改进通过 FedRep 中的最小化步骤得到增强，因为将 FedRep 中的最小化步骤替换为 1 步和 10 步梯度下降（分别为 GD-GD 和 10GD-GD）的方法不能用 nnn 正确缩放。在图 3 中，我们为四个不同的nnn 值和固定的mmm、ddd、kkk 和 rrr 绘制了 FedRep、GD-GD 和 10GD-GD 的收敛轨迹。正如我们在图 3 中观察到的，通过增加节点 n 的数量，客户端可以更快地收敛到真实表示。此外，运行更多本地更新以查找本地头会加快 FedRep 的收敛速度。特别是，与 GD-GD 和 10GD-GD 相比，FedRep 在每一轮中准确地找到最佳局部头部，速度最快，分别只运行 1 次和 10 次局部更新来学习头部。
推广到新客户。接下来，我们评估 FedRep 学习的表示在降低未参与培训的新客户的样本复杂性方面的有效性。我们首先在一组固定的 n=100n = 100n=100 个客户端上训练 FedRep 和 FedAvg，如图 1 所示，其中 (d,k)=(20,2)(d, k) = (20, 2)(d,k)=(20,2)。新客户可以访问 mnewm_{new}mnew 标记的本地样本。它将使用从训练客户那里学到的表示 B^∗∈Rd×k\hat B^* \in R^{d\times k}B^∗∈Rd×k，并使用该表示及其本地训练样本来学习个性化的头部。对于 FedRep 和 FedAvg，我们在给定这些样本和训练期间学习的表示的情况下求解最佳头部。我们将新客户端测试数据上生成的模型的 MSE 与图 4 中仅使用来自新客户端（仅限本地）的 mnewm_{new}mnew 标记样本训练的模型的 MSE 进行比较。FedAvg 的大误差表明它没有学习地面实况表示。同时，FedRep 学习的表示允许为新客户端找到一个准确的模型，只要 mnew≥km_{new} \geq kmnew≥k，这大大提高了本地的复杂性仅当（mnew=Ω(d)）（m_{new}=\Omega(d)）（mnew=Ω(d)）。
5.2.真实数据
接下来，我们研究这些见解是否适用于非线性模型和真实数据集。
数据集和模型。我们使用四个真实数据集：CIFAR10 和 CIFAR100 (Krizhevsky et al., )、FEMNIST (Caldas et al., ; Cohen et al., ) 和 Sent140 (Caldas et al., )。前三个是图像数据集，最后一个是文本数据集，其目标是将推文的情绪分类为正面或负面。我们通过为每个客户分配不同数量的类 SSS 来控制 CIFAR10 和 CIFAR100 的异质性，分别来自 10 个和 100 个总类。每个客户端都分配了相同数量的训练样本，即 50,000/n50, 000/n50,000/n。对于 FEMNIST，我们将数据集限制为 10 个手写字母，并根据对数正态分布将样本分配给客户端，如 (Li et al. , )。我们考虑 n=150n = 150n=150 个客户端的分区，平均每个客户端有 148 个样本。对于 Sent140，我们使用推文的自然分配给他们的作者，并使用 n=183n = 183n=183个客户端，每个客户端平均有 72 个样本。我们对 CIFAR 数据集使用 5 层 CNN，对 FEMNIST 使用 2 层 MLP，对 Sent140 使用 RNN（详见附录 A）。
基线。我们与各种个性化的联邦学习技术以及学习单个全局模型及其微调类似物的方法进行比较。在个性化方法中，FedPer (Arivazhagan et al., ) 与我们最相似，因为它也学习全局表示和个性化头部，但同时对两组参数进行局部更新，因此产生相同数量的头部的局部更新和每个局部回合的表示。 Fed-MTL (Smith et al., ) 学习本地模型和正则化器来编码客户端之间的关系，PerFedAvg (Fallah et al., ) 利用元学习来学习单个模型，该模型在适应每个任务后表现良好和 LG-FedAvg (Liang et al., ) 学习局部表示和全局头部。 APFL (Deng et al., ) 在局部模型和全局模型之间进行插值，L2GD (Hanzely & Richta ́rik, ) 和 Ditto (Li et al., ) 学习局部模型，这些局部模型被全球鼓励靠近在一起正则化。对于全局 FL 方法，我们考虑 FedAvg (McMahan et al., )、SCAFFOLD (Karimireddy et al., ) 和 FedProx (Li et al., )。为了获得微调结果，我们首先在整个训练期间训练全局模型，然后每个客户端在其本地训练数据上仅微调头部 10 个 SGD 时期，然后计算最终测试准确度。
执行。在每个实验中，我们在每一轮中对所有客户端的比率 r=0.1r = 0.1r=0.1进行采样。我们随机初始化所有模型，并为 CIFAR 数据集训练 T=100T = 100T=100 轮通信，对于 Sent140 训练 T=50T = 50T=50，对于 FEMNIST 训练 T=200T = 200T=200。在每种情况下，FedRep 执行 10 个带有动量的 SGD 本地 epoch 来训练本地头部，然后在每次本地更新（取决于数据集）中进行 1 个或 5 个 epoch 的表示。所有其他方法都使用与 FedRep 相同数量的本地 epoch 来更新表示。精度是通过在最后 10 轮通信中取所有用户的平均局部精度来计算的，微调方法除外。这些精度是在为每个客户端本地训练完全训练的全局模型的头部十个epoch后计算的。
更多本地更新的好处。如第 1 节所述，我们的公式的一个关键优势是它使客户端能够运行许多本地更新，而不会导致与全局最优解的分歧。我们在图 5 中演示了一个示例。这里有 n=100n = 100n=100 个客户端，每个客户端有 S=2S = 2S=2类图像。对于 FedAvg，我们观察到运行更多本地更新并不一定会提高性能。相比之下，FedRep 的性能随着 EEE 单调不递减，即 FedRep 需要较少的 EEE 调整，并且不会受到更多本地计算的影响。
对不同程度的异质性、客户数量和每个客户的样本数量的鲁棒性。我们在表 1 中显示了针对各种设置的所有算法的平均局部测试误差。在所有情况下，FedRep 要么是表现最好的方法，要么非常接近表现最好的方法。回想一下，对于 CIFAR 数据集，每个客户端的训练样本数等于 50,000/n50, 000/n50,000/n，因此具有 1000 个用户的列每个客户端的样本数最少。
推广到新客户。我们还评估了 FedRep 在适应新用户方面学习的表示的强度。为此，我们首先在包含 10 个手写字母（FEMNIST-letters）的 FEMNIST 分区的常规设置中训练 FedRep、FedAvg、PerFedAvg、LG-FedAvg、APFL、L2GD 和 FedProx。然后，我们遇到客户端的数据来自 FEMNIST 数据集的不同分区，其中包含手写数字的图像。我们假设我们可以在这个新客户端访问包含 500 个样本的数据集来微调头部。使用这些，对于每个算法，我们在多个 epoch 上微调头部，同时保持表示固定。在图 6 中，我们在多个时期重复扫描相同的 500 个样本以进一步细化头部，并绘制相应的局部测试精度。很明显，FedRep 的性能明显优于这些基线。
6. 讨论
我们为联邦学习引入了一种新颖的表示学习框架和算法，以及它在联邦环境中的实用性的理论和经验证据。 正如我们在这里展示的那样，FedRep 框架非常通用且简单，可以轻松应用于广泛的联邦学习问题，从线性回归到图像分类再到情感分析。 尽管如此，它仍然足够强大，可以在各种个性化联邦学习基线上显着提高局部准确性。 一个有趣的观察结果是，微调全局联邦学习方法，尤其是FedAvg，也往往表现得非常好。 我们计划在未来的工作中进一步研究这一现象。 实际上，可能会提出更复杂的 FedRep 框架扩展，以提高与微调方法相关的性能。
