Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization

We propose a novel single-loop decentralized algorithm, DGDA-VR, for solving the stochastic nonconvex strongly-concave minimax problems over a connected network of agents, which are equipped with stochastic first-order oracles to estimate their local gradients. DGDA-VR, incorporating variance reduction, achieves O(ε^−3) oracle complexity and O(ε^−2) communication complexity without resorting to multi-communication rounds – both are optimal, i.e., matching the lower bounds for this class of problems. Since DGDA-VR does not require multiple communication rounds, it is applicable to a broader range of decentralized computational environments. To the best of our knowledge, this is the first distributed method using a single communication round in each iteration to jointly optimize the oracle and communication complexities for the problem considered here.

Authors

• Xuan Zhang Harvest Fund Management Co., Ltd.
• Gabriel Mancino-Ball Rensselaer Polytechnic Institute
• Necdet Serhat Aybat Pennsylvania State University
• Yangyang Xu Department of Mathematical Sciences, Rensselaer Polytechnic Institute

Keywords

• ML: Distributed Machine Learning & Federated Learning
• ML: Optimization
• SO: Distributed Search
• SO: Non-convex Optimization