{"ID":2876668,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.21431","arxiv_id":"2508.21431","title":"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( κ\\log \\left( ε^{-1} \\right) \\right)$ and communication complexity of $\\mathcal{O} \\left( κ\\log \\left( ε^{-1} \\right) /\\sqrt{1-\\sqrt{ρ_W}} \\right)$ for a suboptimality level of $ε\u003e0$, where $κ$ is the condition number of the objective function and $ρ_W$ is the spectrum gap of the network. Numerical experiments illustrate the effectiveness of the proposed algorithms.","short_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 opti...","url_abs":"https://arxiv.org/abs/2508.21431","url_pdf":"https://arxiv.org/pdf/2508.21431v1","authors":"[\"Yan Huang\",\"Jinming Xu\",\"Jiming Chen\",\"Karl Henrik Johansson\"]","published":"2025-08-29T08:59:04Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DC\"]","methods":"[]","has_code":false}