FedHybrid: A Hybrid Federated Optimization Method for Heterogeneous Clients
FedHybrid: A Hybrid Federated Optimization Method for Heterogeneous Clients
复制标题
DOI：
10.1109/tsp.2023.3240083
复制
发表时间：
2021-06
影响因子：
5.4
通讯作者：
Xiaochun Niu;Ermin Wei
中科院分区：
文献类型：
--
作者：
Xiaochun Niu;Ermin Wei
我们考虑一个分布式的共识优化问题的服务器-客户端（联合）网络，其中所有的客户端连接到一个中央服务器。目前的分布式算法无法捕捉客户端的本地计算能力的异构性。受集中式优化中的乘数方法的启发，我们推导出一个牛顿型原始对偶方法，并利用服务器-客户端拓扑结构实现了分布式实现。然后，我们提出FedHybrid作为一种混合原始-对偶方法，允许异构客户端执行不同类型的更新。具体地，具有较高计算能力和/或执行计算的较便宜成本的那些客户端可以在本地实现牛顿型更新，而其他客户端可以采用简单得多的梯度型更新。在理论上，我们提出了一种新的价值函数结合对偶最优间隙和原始跟踪误差。我们证明了FedHybrid线性收敛到强凸函数的精确最优点，无论客户端选择梯度型或牛顿型更新。最后，我们展示了数值研究，以证明我们的方法在实践中的有效性。据我们所知，这是第一个混合方法，允许异构本地更新分布式共识优化可证明的收敛性和速度保证。
We consider a distributed consensus optimization problem over a server-client (federated) network, where all clients are connected to a central server. Current distributed algorithms fail to capture the heterogeneity in clients' local computation capacities. Motivated by the method of multipliers in centralized optimization, we derive a Newton-type primal-dual method with a distributed implementation utilizing the server-client topology. Then we propose FedHybrid as a hybrid primal-dual method that allows heterogeneous clients to perform different types of updates. Specifically, those clients with higher computational capabilities and/or cheaper costs to perform computation can implement Newton-type updates locally, while other clients can adopt much simpler gradient-type updates. Theoretically, we propose a novel merit function by combining the dual optimality gap and the primal tracking error. We prove that FedHybrid converges linearly to the exact optimal point for strongly convex functions, regardless of clients' choices of gradient-type or Newton-type updates. Finally, we show numerical studies to demonstrate the efficacy of our method in practice. To the best of our knowledge, this is the first hybrid method allowing heterogeneous local updates for distributed consensus optimization with provable convergence and rate guarantees.