Efficient Algorithms for Federated Saddle Point Optimization
arXiv:2102.06333
Abstract
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.
References in corpus (10)
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Local SGD Converges Fast and Communicates Little
- A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
- Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
- Variance Reduced Local SGD with Lower Communication Complexity
- Minibatch vs Local SGD for Heterogeneous Distributed Learning
- Generative Models for Effective ML on Private, Decentralized Datasets
- Stochastic Variance Reduction Methods for Saddle-Point Problems
- Federated Accelerated Stochastic Gradient Descent
- Local SGD: Unified Theory and New Efficient Methods