A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning-猫眼课题宝

DOI：

10.48550/arxiv.2206.01132

发表时间：

2022-06

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Zhenyu Sun;Ermin Wei

在本文中，我们研究了一个大规模的多智能体极大极小优化问题，该问题模拟了统计学习和博弈论中许多有趣的应用，包括生成对抗网络（GAN）。总体目标是代理的私人局部目标函数的总和。我们首先分析一个重要的特殊情况下，经验极大极小问题，其中的总体目标近似于一个真正的人口极大极小风险的统计样本。我们通过Rademacher复杂性分析为学习提供了泛化范围。然后，我们专注于联邦设置，代理可以执行本地计算并与中央服务器通信。大多数现有的联邦极小极大算法要么需要每次迭代通信或缺乏性能保证，但局部随机梯度下降上升（SGDA），一个多个本地更新下降上升算法，保证收敛下的一个递减步长。通过分析局部SGDA的理想条件下，没有梯度噪声，我们表明，一般不能保证精确的收敛与恒定的步长，从而遭受缓慢的收敛速度。为了解决这个问题，我们提出了FedGDA-GT，一种改进的联邦（美联储）梯度下降上升（GDA）方法的基础上梯度跟踪（GT）。当局部目标为Lipschitz光滑且强凸-强凹时，证明了FedGDA-GT以$\mathcal{O}（\log（1/\log））$轮的通信量以常数步长线性收敛到全局$\mathcal $-近似解，其时间复杂度与集中式GDA方法相当.最后，我们用数值方法证明了FedGDA-GT的性能优于Local SGDA。

In this paper, we study a large-scale multi-agent minimax optimization problem, which models many interesting applications in statistical learning and game theory, including Generative Adversarial Networks (GANs). The overall objective is a sum of agents' private local objective functions. We first analyze an important special case, empirical minimax problem, where the overall objective approximates a true population minimax risk by statistical samples. We provide generalization bounds for learning with this objective through Rademacher complexity analysis. Then, we focus on the federated setting, where agents can perform local computation and communicate with a central server. Most existing federated minimax algorithms either require communication per iteration or lack performance guarantees with the exception of Local Stochastic Gradient Descent Ascent (SGDA), a multiple-local-update descent ascent algorithm which guarantees convergence under a diminishing stepsize. By analyzing Local SGDA under the ideal condition of no gradient noise, we show that generally it cannot guarantee exact convergence with constant stepsizes and thus suffers from slow rates of convergence. To tackle this issue, we propose FedGDA-GT, an improved Federated (Fed) Gradient Descent Ascent (GDA) method based on Gradient Tracking (GT). When local objectives are Lipschitz smooth and strongly-convex-strongly-concave, we prove that FedGDA-GT converges linearly with a constant stepsize to global $\epsilon$-approximation solution with $\mathcal{O}(\log (1/\epsilon))$ rounds of communication, which matches the time complexity of centralized GDA method. Finally, we numerically show that FedGDA-GT outperforms Local SGDA.

A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning

文献摘要

相似文献