Collaboration Equilibrium in Federated Learning

背景

• 医院直接进行联邦学习，当与具有非常不同患者群体的医院合作时，模型的性能可能会降低。这是样本分布造成的差异
• 联邦学习合作不是越多client越好的
• collaboration equilibrium ：没有其他的联盟设置可以使任何个人客户受益更多（例如，获得更好的模型性能）
• 将所有的client看作一张图，将图分割成不重叠的子图，子图里的client进行联邦学习合作每个个体效益最大

贡献

1. 基于Pareto optimization为网络中的每个客户端确定必要的协作者，以实现其最大的效用

2. 公用数据集和现实数据集验证了方法的有效性

3. 开源了代码 https://github.com/cuis15/learning-to-collaborate

问题定义

optimal collaborator set（OCS）定义： I的最好的合作网络

I加入OCS能达到最好效果，OSC中每个client都对I有帮助，图中的egde i->j 代表i属于j的OCS， OSC用图benefit graph (BG)表示。

• coalition： C 子图里的所有client只和其中的其他client合作才能达到最好表现
• 每个client I都试图组成最好的C，这就使得合作图发成了几个不重叠的子图

何为collaboration equilibrium (CE)？

内部协议

• 所有的子集合都能因为加入C取得收益
• 总会存在一个I离开C，当C中的一个子集合C‘分割离C

外部协议

• 另外的子集合无法带来更好的收益

解决算法

iterative graph-theory-based method： 目的是达到CE

(1) 在给定的Benefit Graph（BG）中达到Collaboration Equilibrium（CE），穷尽所有分割方法的计算量是指数级的，本文提出了几何级的策略

• 找出stable coalition

stable coalition中的任何客户都无法再得到更好的合作方式。给定客户们的benefit graph(BG),stable coalition属于BG的强连通分量

• 利用Tarjan算法，时间复杂度O(V+E),找到所有的强连通分量，根据条件判断是非为stable coalition

(2) 如何建立Benefit Graph

• 建立BG就是找出每个client应该合作的对象，合作方式有2^(N-1)种，也是难以遍历的
• 通过Specific Pareto Optimization（SPO）
• learn a Pareto model given the weight of all clients 𝒅
• optimize the weight vector 𝒅 to search for a best model 𝑀∗ (𝐼𝑖) by gradient descent.

帕累托最优：在一定资源条件下，不存在另一种分配方式，使得某个个体利益增加而其他个体利益不受损失

• 利用超网（用另一个网络生成一个网络的参数）得到帕累托模型M

• 𝒅中非零的序号就是要合作的client编号

实验

(1) 和穷举法对比显示帕累托方法的有效性

(2) 使用CE理论进行联邦学习验证了模型效果提高

总结

针对联邦学习中的合作问题给出了合作均衡准则，有效提高联邦学习效果