Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity

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 varepsilon-duality gap within communication rounds of mathcal O(δ D2/varepsilon), communication complexity of mathcal O(n+√nδ D2/varepsilon), and local gradient calls of tildemathcal O(n+(√nδ+L)D2/varepsilonlog(1/varepsilon)), 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/varepsilon)), mathcal O((n+√nδ/μ)log(1/varepsilon)), and tildemathcal O(n+(√nδ+L)/μ)log(1/varepsilon)) respectively, which are also nearly tight. Furthermore, we conduct the numerical experiments to show the empirical advantages of proposed method.