Decentralized Min-Max Optimization with Gradient Tracking
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913841262100480 |
|---|---|
| author | You, Runze Huang, Kun Pu, Shi |
| author_facet | You, Runze Huang, Kun Pu, Shi |
| contents | This paper presents a novel distributed formulation of the min-max optimization problem. Such a formulation enables enhanced flexibility among agents when optimizing their maximization variables. To address the problem, we propose two distributed gradient methods over networks, termed Distributed Gradient Tracking Ascent (DGTA) and Distributed Stochastic Gradient Tracking Ascent (DSGTA). We demonstrate that DGTA achieves an iteration complexity of $\mathcal{O}(κ^2\varepsilon^{-2})$, and DSGTA attains a sample complexity of $\mathcal{O}(κ^3\varepsilon^{-4})$ for nonconvex strongly concave (NC-SC) objective functions. Both results match those of their centralized counterparts up to constant factors related to the communication network. Numerical experiments further demonstrate the superior empirical performance of the proposed algorithms compared to existing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10631 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decentralized Min-Max Optimization with Gradient Tracking You, Runze Huang, Kun Pu, Shi Optimization and Control This paper presents a novel distributed formulation of the min-max optimization problem. Such a formulation enables enhanced flexibility among agents when optimizing their maximization variables. To address the problem, we propose two distributed gradient methods over networks, termed Distributed Gradient Tracking Ascent (DGTA) and Distributed Stochastic Gradient Tracking Ascent (DSGTA). We demonstrate that DGTA achieves an iteration complexity of $\mathcal{O}(κ^2\varepsilon^{-2})$, and DSGTA attains a sample complexity of $\mathcal{O}(κ^3\varepsilon^{-4})$ for nonconvex strongly concave (NC-SC) objective functions. Both results match those of their centralized counterparts up to constant factors related to the communication network. Numerical experiments further demonstrate the superior empirical performance of the proposed algorithms compared to existing methods. |
| title | Decentralized Min-Max Optimization with Gradient Tracking |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2505.10631 |