Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910472834383872 |
|---|---|
| author | Huang, Yan Li, Xiang Shen, Yipeng He, Niao Xu, Jinming |
| author_facet | Huang, Yan Li, Xiang Shen, Yipeng He, Niao Xu, Jinming |
| contents | In this paper, we show that applying adaptive methods directly to distributed minimax problems can result in non-convergence due to inconsistency in locally computed adaptive stepsizes. To address this challenge, we propose D-AdaST, a Distributed Adaptive minimax method with Stepsize Tracking. The key strategy is to employ an adaptive stepsize tracking protocol involving the transmission of two extra (scalar) variables. This protocol ensures the consistency among stepsizes of nodes, eliminating the steady-state error due to the lack of coordination of stepsizes among nodes that commonly exists in vanilla distributed adaptive methods, and thus guarantees exact convergence. For nonconvex-strongly-concave distributed minimax problems, we characterize the specific transient times that ensure time-scale separation of stepsizes and quasi-independence of networks, leading to a near-optimal convergence rate of $\tilde{\mathcal{O}} \left( ε^{-\left( 4+δ\right)} \right)$ for any small $δ> 0$, matching that of the centralized counterpart. To our best knowledge, D-AdaST is the first distributed adaptive method achieving near-optimal convergence without knowing any problem-dependent parameters for nonconvex minimax problems. Extensive experiments are conducted to validate our theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_02939 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes Huang, Yan Li, Xiang Shen, Yipeng He, Niao Xu, Jinming Optimization and Control Distributed, Parallel, and Cluster Computing Machine Learning In this paper, we show that applying adaptive methods directly to distributed minimax problems can result in non-convergence due to inconsistency in locally computed adaptive stepsizes. To address this challenge, we propose D-AdaST, a Distributed Adaptive minimax method with Stepsize Tracking. The key strategy is to employ an adaptive stepsize tracking protocol involving the transmission of two extra (scalar) variables. This protocol ensures the consistency among stepsizes of nodes, eliminating the steady-state error due to the lack of coordination of stepsizes among nodes that commonly exists in vanilla distributed adaptive methods, and thus guarantees exact convergence. For nonconvex-strongly-concave distributed minimax problems, we characterize the specific transient times that ensure time-scale separation of stepsizes and quasi-independence of networks, leading to a near-optimal convergence rate of $\tilde{\mathcal{O}} \left( ε^{-\left( 4+δ\right)} \right)$ for any small $δ> 0$, matching that of the centralized counterpart. To our best knowledge, D-AdaST is the first distributed adaptive method achieving near-optimal convergence without knowing any problem-dependent parameters for nonconvex minimax problems. Extensive experiments are conducted to validate our theoretical results. |
| title | Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing Machine Learning |
| url | https://arxiv.org/abs/2406.02939 |