Federated Minimax Optimization with Client Heterogeneity
Federated Minimax Optimization with Client Heterogeneity
复制标题
DOI：
10.48550/arxiv.2302.04249
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Pranay Sharma;Rohan Panda;Gauri Joshi
中科院分区：
文献类型：
--
作者：
Pranay Sharma;Rohan Panda;Gauri Joshi
随着Gans等现代应用程序的出现，MinimMax优化引起了人们的极大兴趣，而且它本身就比简单的最小化更具挑战性。驻留在多个边缘设备或客户端的训练数据加剧了难度，尤其是当这些客户端可能具有异类数据集和本地计算能力时。我们提出了一个通用的联邦极小极大优化框架，它包含了这些设置和几种现有的方法，如局部SGDA。我们表明，异类局部进度的天真聚集会导致优化不匹配的目标函数--这是以前在标准联邦最小化中观察到的现象。为了解决此问题，我们建议通过在连续通信轮次之间执行的本地步骤数量来标准化客户端更新。针对非凸-凹和非凸-非凹函数类，我们分析了该算法的收敛特性，并刻画了客户数据异构性、部分客户参与性和异构性局部计算对算法的影响。与文献中所考虑的相比，我们的分析是在关于客户端内部噪声和客户端间异质性的更一般假设下工作的。对于所考虑的所有函数类，我们显著改善了现有的计算和通信复杂性结果。实验结果支持了我们的理论主张。
Minimax optimization has seen a surge in interest with the advent of modern applications such as GANs, and it is inherently more challenging than simple minimization. The difficulty is exacerbated by the training data residing at multiple edge devices or \textit{clients}, especially when these clients can have heterogeneous datasets and local computation capabilities. We propose a general federated minimax optimization framework that subsumes such settings and several existing methods like Local SGDA. We show that naive aggregation of heterogeneous local progress results in optimizing a mismatched objective function -- a phenomenon previously observed in standard federated minimization. To fix this problem, we propose normalizing the client updates by the number of local steps undertaken between successive communication rounds. We analyze the convergence of the proposed algorithm for classes of nonconvex-concave and nonconvex-nonconcave functions and characterize the impact of heterogeneous client data, partial client participation, and heterogeneous local computations. Our analysis works under more general assumptions on the intra-client noise and inter-client heterogeneity than so far considered in the literature. For all the function classes considered, we significantly improve the existing computation and communication complexity results. Experimental results support our theoretical claims.