# Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 62 references that are in the map.
- First posted on arXiv 18 Jun 2021.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Towards Principled Methods for Training Generative Adversarial Networks](https://mlsanity.com/paper/1701.04862/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems](https://mlsanity.com/paper/2010.15768/) (2020)
- [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)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [Adaptive extra-gradient methods for min-max optimization and games](https://mlsanity.com/paper/2010.12100/) (2020)
- [Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets](https://mlsanity.com/paper/1912.11940/) (2019)
- [Quantized Adam with Error Feedback](https://mlsanity.com/paper/2004.14180/) (2020)
- [Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/2005.02426/) (2020)
- [A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise](https://mlsanity.com/paper/1902.01637/) (2019)
- [Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates](https://mlsanity.com/paper/1911.09030/) (2019)
- [Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration](https://mlsanity.com/paper/2101.05471/) (2021)
- [Efficient Algorithms for Federated Saddle Point Optimization](https://mlsanity.com/paper/2102.06333/) (2021)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)

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

- [AdaSAM: Boosting Sharpness-Aware Minimization with Adaptive Learning Rate and Momentum for Training Deep Neural Networks](https://mlsanity.com/paper/2303.00565/) (2023)
- [Robust Decentralized Learning with Local Updates and Gradient Tracking](https://mlsanity.com/paper/2405.00965/) (2024)

## Abstract (arXiv)

Large scale convex-concave minimax problems arise in numerous applications, including game theory, robust training, and training of generative adversarial networks. Despite their wide applicability, solving such problems efficiently and effectively is challenging in the presence of large amounts of data using existing stochastic minimax methods. We study a class of stochastic minimax methods and develop a communication-efficient distributed stochastic extragradient algorithm, LocalAdaSEG, with an adaptive learning rate suitable for solving convex-concave minimax problems in the Parameter-Server model. LocalAdaSEG has three main features: (i) a periodic communication strategy that reduces the communication cost between workers and the server; (ii) an adaptive learning rate that is computed locally and allows for tuning-free implementation; and (iii) theoretically, a nearly linear speed-up with respect to the dominant variance term, arising from the estimation of the stochastic gradient, is proven in both the smooth and nonsmooth convex-concave settings. LocalAdaSEG is used to solve a stochastic bilinear game, and train a generative adversarial network. We compare LocalAdaSEG against several existing optimizers for minimax problems and demonstrate its efficacy through several experiments in both homogeneous and heterogeneous settings.