TY - JOUR
T1 - Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization
AU - Zhang, Xuan
AU - Mancino-Ball, Gabriel
AU - Aybat, Necdet Serhat
AU - Xu, Yangyang
N1 - Publisher Copyright:
Copyright © 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2024/3/25
Y1 - 2024/3/25
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85189517803&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85189517803&partnerID=8YFLogxK
U2 - 10.1609/aaai.v38i18.30076
DO - 10.1609/aaai.v38i18.30076
M3 - Conference article
AN - SCOPUS:85189517803
SN - 2159-5399
VL - 38
SP - 20865
EP - 20873
JO - Proceedings of the AAAI Conference on Artificial Intelligence
JF - Proceedings of the AAAI Conference on Artificial Intelligence
IS - 18
T2 - 38th AAAI Conference on Artificial Intelligence, AAAI 2024
Y2 - 20 February 2024 through 27 February 2024
ER -