mlsanityData to 7 Oct 2026

Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization

arXiv 2106.10022 ↗First posted 18 Jun 2021cs.LG cs.DC math.OCcited by 2

Not on the map. Why?

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.

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

Builds on

35 of 62 references.

References · 35

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2018Large Scale GAN Training for High Fidelity Natural Image Synthesiscited by 2,609
  3. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  4. 2020Adaptive Federated Optimizationcited by 1,036
  5. 2019On the Convergence of Adam and Beyondcited by 834
  6. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  7. 2017Towards Principled Methods for Training Generative Adversarial Networkscited by 460
  8. 2017Training GANs with Optimismcited by 217
  9. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
  10. 2018On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimizationcited by 173
  11. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  12. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
23 more
  1. 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 124
  2. 2017Cycles in adversarial regularized learningcited by 122
  3. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  4. 2021Distributionally Robust Federated Averagingcited by 104
  5. 2018Negative Momentum for Improved Game Dynamicscited by 59
  6. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  7. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  8. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  9. 2014Accelerated Schemes For A Class of Variational Inequalitiescited by 30
  10. 2020Adaptive extra-gradient methods for min-max optimization and gamescited by 30
  11. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  12. 2020Quantized Adam with Error Feedbackcited by 27
  13. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  14. 2019A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noisecited by 26
  15. 2019Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Ratescited by 26
  16. 2021Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Accelerationcited by 25
  17. 2021Efficient Algorithms for Federated Saddle Point Optimizationcited by 20
  18. 2013Optimal Primal-Dual Methods for a Class of Saddle Point Problemscited by 19
  19. 2020Adaptive Primal-Dual Stochastic Gradient Method for Expectation-constrained Convex Stochastic Programscited by 10
  20. 2020CADA: Communication-Adaptive Distributed Adamcited by 10
  21. 2018Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutionscited by 9
  22. 2020A Distributed Training Algorithm of Generative Adversarial Networks with Quantized Gradientscited by 2
  23. 2020Geometry-Aware Universal Mirror-Proxcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1.

2 papers.

  1. 2023AdaSAM: Boosting Sharpness-Aware Minimization with Adaptive Learning Rate and Momentum for Training Deep Neural Networkscited by 21
  2. 2024Robust Decentralized Learning with Local Updates and Gradient Trackingcited by 8