2024/05/25 by Zhou, Qihao, Ye, Haishan, Luo, Luo · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2405.16126
This paper considers the distributed convex-concave minimax optimization under the second-order similarity. We propose stochastic variance-reduced optimistic gradient sliding (SVOGS) method, which takes the advantage of the finite-sum structure in the objective by involving the mini-batch client sampling and variance reduction. We prove SVOGS can achieve the ε-duality gap within communication rounds of \mathcal O(δD2/ε), communication complexity of \mathcal O(n+√(n)δD2/ε), and local gradient calls of \mathcal O(n+(√(n)δ+L)D2/εlog(1/ε)), where n is the number of nodes, δ is the degree of the second-order similarity, L is the smoothness parameter and D is the diameter of the constraint set. We can verify that all of above complexity (nearly) matches the corresponding lower bounds. For the specific μ-strongly-convex-μ-strongly-convex case, our algorithm has the upper bounds on communication rounds, communication complexity, and local gradient calls of \mathcal O(δ/μlog(1/ε)), \mathcal O((n+√(n)δ/μ)log(1/ε)), and \mathcal O(n+(√(n)δ+L)/μ)log(1/ε)) respectively, which are also nearly tight. Furthermore, we conduct the numerical experiments to show the empirical advantages of proposed method.