联邦power（联邦学习：FedProx框架）

FEDERATED OPTIMIZATION IN HETEROGENEOUS NETWORKS

每日一诗：《当年万马尽腾空    
    
    
    
  ，就中紫骝尤最雄》

明·张居正

当年万马尽腾空 


     


     


     


     
，就中紫骝尤最雄    
    
    
    
  。

战罢不知身着箭

 




 




 




 




，飞来祇觉足生风 


     


     


     


     
。

北风猎猎吹原野   

   

   

   

 ，长河水澌血流赭

 




 




 




 




。

谁言百万倒戈中  

     

     

     

     ，犹有弯弧射钩者   

   

   

   

 。

1.概述：

联邦学习不同于传统的分布式优化的两个关键挑战:高度的系统和统计异构性  

     

     

     

     。引入了一个框架


  




  




  




  




，FedProx以解决联邦网络的异构性（统计异构 系统异构）


  




  




  




  




。FedProx可以看作是FedAvg的泛化
    
    
    
    
、重构  


  


  


  


。

对于非独立分布(统计异质性)的训练数据  


  


  


  


，框架提供收敛性保证（统计异构）；允许每个参与的设备执行可变数量的工作(系统异构性)来遵守设备级系统约束   
     
     
     
     。FedProx在一组真实的联邦数据集上比FedAvg更健壮的收敛



   




   




   




   



。特别是   
     
     
     
     ，在高度异构的环境下



   




   




   




   



，FedProx表现出比FedAvg更稳定和准确的收敛行为——平均提高22%的绝对测试精度 



 



 



 



。

1.1 系统挑战

通信传输瓶颈     


     


     


     


  、存储能力 




 




 




 




 
、计算能力

   

   

   

   

、联网能力     

     

     

     

 、电池  




  




  




  




  、stragglers


  


  


  


  


、容错

1.2 统计挑战

数据异构     
     
     
     
、非独立同分布   




   




   




   




   、不平衡

关键词具体描述见本人系列相关文章

2.FedAvg：

2.1 优劣：

FedAvg在FedSGD的基础上为每个节点设定统一的E （epochs） 



 



 



 



，用以增大本地计算量 提升本地模型更新的精度                       ，进而加快全局拟合速度




    




    




    




    


，减少通信次数；同时可以解决非凸损失函数的问题                       。

从系统异构角度：FedAvg不允许参与设备根据其系统约束执行可变数量的本地工作;相反



















，通常是简单地丢弃在指定时间段内无法计算E个epoch的设备

从统计角度：FedAvg在数据非独立同分布的情况下适应性弱                       ，因此FedAvg很难在现实场景中（多为非独立同分布）进行理论分析来保证其收敛性




    




    




    




    


。

2.2 算法： 2.3 参数E控制：

正确调整其优化超参数至关重要 本地epochs的大小在其拟合的过程中发挥重要作用



















。

1.执行更多的局部迭代允许更多的局部计算和减少通信



     



     



     



     

，这可以大大提高通信受限网络的整体收敛速度                       。

2.由于本地客户端间不同的目标函数




















，局部epoch太大可能会导致每个客户端朝向其局部目标的最优更新    
    
    
    
  ，而不是全局目标最优——潜在地影响全局收敛 


     


     


     


     
，甚至导致收敛偏离



     



     



     



     

。

3.强迫每个设备执行统一的工作量是不现实的(即

 




 




 




 




，在FedAvg中所有客户端运行相同数量的局部epoch, E）由于系统资源异构   

   

   

   

 ，本地epoch大会导致客户端无法在给定的迭代伦次内完成训练而掉队




















。

实践中  

     

     

     

     ，在允许鲁棒收敛的同时


  




  




  




  




，将局部epoch设为高(以减少通信)    
    
    
    
  。

注意到本地epoch数量的“最佳
    
    
    
    
”设置可能会在每次迭代和每个设备上改变-  


  


  


  


，可以将其设置为关于本地数据和可用系统资源的函数 


     


     


     


     
。比强制规定固定数量的局部epochs更好的方法是允许epochs根据iteration和本地数据与资源进行变更

 




 




 




 




。来适应实际联邦学习中的异质性

3.FedProx

3.1 Tolerating partial work：

系统异构：联邦网络中的不同设备在计算硬件



 



 



 



 


、网络连接和电池水平方面通常有不同的资源约束   

   

   

   

 。强迫每个设备执行统一的epochs是不现实的(即   
     
     
     
     ，运行相同数量的局部epoch, E）  

     

     

     

     。

在FedProx中



   




   




   




   



，将FedAvg泛化 



 



 



 



，允许根据本地数据和可用的系统资源在本地执行可变数量的工作（相比于丢弃设备                       ，该机制会聚合从掉线设备发送的部分结果


  




  




  




  




。）换句话说




    




    




    




    


，不是假设在整个训练过程中所有设备都有一个统一的γ



















，适应不同的设备和不同的迭代轮数产生λ  


  


  


  


。

3.2 λ-inexact solution：

λtk 衡量第k个客户端在全局第t iteration 本地计算量                       ，因此可以根据该变量代理本地epochs次数   
     
     
     
     。

3.3 近似术语：Proximal term

虽然λtk 可以帮助减轻系统异构的影响



   




   




   




   



。但是由于统计异构



     



     



     



     

，不太好通过λtk 来严格限制本地更新的次数




















，过多的本地更新仍然可能(潜在地)导致全局模型偏离 



 



 



 



。

引入了近似术语（Proximal term）来辅助FedProx应对统计异构的挑战                       。

在本地目标函数表达式上添加辅助式子




    




    




    




    


。 有效地限制本地更新对全局模型更新的影响



















。

改进后的目标函数：

3.3.1 优点：

1.它通过限制本地更新    
    
    
    
  ，使其更接近初始(全局)模型 


     


     


     


     
，而不需要手动设置本地epochs的数量

 




 




 




 




，解决了统计异质性的问题                       。（限制）

2.它允许安全地合并由系统异构性产生的可变数量的本地工作



     



     



     



     

。（辅助）

该辅助函数在优化问题中很常见




















。

3.4 算法

references：

Li, Tian, et al. “Federated optimization in heterogeneous networks.     


     


     


     


  ” Proceedings of Machine Learning and Systems 2 (2020): 429-450.