A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning
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.