# Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes

arXiv: https://arxiv.org/abs/2406.02939 · HTML: https://mlsanity.com/paper/2406.02939/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 62 references that are in the map.
- First posted on arXiv 5 Jun 2024.

## Builds on (most cited first, 30 of 45)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Sharp Minima Can Generalize For Deep Nets](https://mlsanity.com/paper/1703.04933/) (2017)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Learning Adversarially Fair and Transferable Representations](https://mlsanity.com/paper/1802.06309/) (2018)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/1808.05671/) (2018)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [A Novel Convergence Analysis for Algorithms of the Adam Family](https://mlsanity.com/paper/2112.03459/) (2021)
- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [A Decentralized Parallel Algorithm for Training Generative Adversarial Nets](https://mlsanity.com/paper/1910.12999/) (2019)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Adversarial Attack Generation Empowered by Min-Max Optimization](https://mlsanity.com/paper/1906.03563/) (2019)
- [Adaptive extra-gradient methods for min-max optimization and games](https://mlsanity.com/paper/2010.12100/) (2020)
- [Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems](https://mlsanity.com/paper/2007.13605/) (2020)

## Built on by (most cited first, 1 of 1)

- [Fully First-Order Methods for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2410.19319/) (2024)

## Abstract (arXiv)

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 tildeO 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.