Efficient Algorithms for Federated Saddle Point Optimization
  We consider strongly convex-concave minimax problems in the federated
setting, where the communication constraint is the main bottleneck. When
clients are arbitrarily heterogeneous, a simple Minibatch Mirror-prox achieves
the best performance. As the clients become more homogeneous, using multiple
local gradient updates at the clients significantly improves upon Minibatch
Mirror-prox by communicating less frequently. Our goal is to design an
algorithm that can harness the benefit of similarity in the clients while
recovering the Minibatch Mirror-prox performance under arbitrary heterogeneity
(up to log factors). We give the first federated minimax optimization algorithm
that achieves this goal. The main idea is to combine (i) SCAFFOLD (an algorithm
that performs variance reduction across clients for convex optimization) to
erase the worst-case dependency on heterogeneity and (ii) Catalyst (a framework
for acceleration based on modifying the objective) to accelerate convergence
without amplifying client drift. We prove that this algorithm achieves our
goal, and include experiments to validate the theory.
