Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization
Xuan Zhang, Gabriel Mancino-Ball, Necdet Serhat Aybat, Yangyang Xu
Abstract
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.
BibTeX
@article{Zhang_Mancino-Ball_Aybat_Xu_2024, title={Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/30076}, DOI={10.1609/aaai.v38i18.30076}, abstractNote={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.}, number={18}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Zhang, Xuan and Mancino-Ball, Gabriel and Aybat, Necdet Serhat and Xu, Yangyang}, year={2024}, month={Mar.}, pages={20865-20873} }