An Optimistic Gradient Tracking Method for Distributed Minimax Optimization

Abstract

This paper studies the distributed minimax optimization problem over networks. To enhance convergence performance, we propose a distributed optimistic gradient tracking method, termed DOGT, which solves a surrogate function that captures the similarity between local objective functions to approximate a centralized optimistic approach locally. Leveraging a Lyapunov-based analysis, we prove that DOGT achieves linear convergence to the optimal solution for strongly convex-strongly concave objective functions while remaining robust to the heterogeneity among them. Moreover, by integrating an accelerated consensus protocol, the accelerated DOGT (ADOGT) algorithm achieves an optimal convergence rate of $\mathcal{O}\left(\hat{I}º\log \left(\hat{I}{\mu }^{-1}\right)\right)$ and communication complexity of $\mathcal{O}\left(\hat{I}º\log \left(\hat{I}{\mu }^{-1}\right)/\sqrt{1-\sqrt{\ddot{I}{}_W}}\right)$ for a suboptimality level of $\hat{I}\mu >0$, where $\hat{I}º$ is the condition number of the objective function and $\ddot{I}{}_W$ is the spectrum gap of the network. Numerical experiments illustrate the effectiveness of the proposed algorithms.

This manuscript has been accepted for presentation at the 64th IEEE Conference on Decision and Control