mlsanityData to 7 Oct 2026

Distributed Extra-gradient with Optimal Complexity and Communication Guarantees

arXiv 2308.09187 ↗First posted 17 Aug 2023cs.LG cs.DC math.OCcited by 2

Not on the map. Why?

Abstract (arXiv)

We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local stochastic dual vectors. This setting includes a broad range of important problems from distributed convex minimization to min-max and games. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. To this end, we propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs. We provide an adaptive step-size rule, which adapts to the respective noise profiles at hand and achieve a fast rate of mathcal O(1/T) under relative noise, and an order-optimal mathcal O(1/√T) under absolute noise and show distributed training accelerates convergence. Finally, we validate our theoretical results by providing real-world experiments and training generative adversarial networks on multiple GPUs.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 35 of its 82 references that are in the map. First posted on arXiv 17 Aug 2023.

Builds on

35 of 82 references.

References · 35

  1. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  2. 2022Generative Adversarial Networkscited by 5,603
  3. 2016Layer Normalizationcited by 5,579
  4. 2019Advances and Open Problems in Federated Learningcited by 3,021
  5. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  6. 2016DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradientscited by 557
  7. 2017Robust Adversarial Reinforcement Learningcited by 439
  8. 2015Deep Learning with Limited Numerical Precisioncited by 368
  9. 2018Adversarially Robust Generalization Requires More Datacited by 318
  10. 2017TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learningcited by 253
  11. 2017The Marginal Value of Adaptive Gradient Methods in Machine Learningcited by 248
  12. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
23 more
  1. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  2. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  3. 2014Deep learning with Elastic Averaging SGDcited by 90
  4. 2018Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGDcited by 76
  5. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  6. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  7. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  8. 2020Adaptive Gradient Quantization for Data-Parallel SGDcited by 43
  9. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  10. 2018Golden Ratio Algorithms for Variational Inequalitiescited by 38
  11. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  12. 2013Petuum: A New Platform for Distributed Machine Learning on Big Datacited by 35
  13. 2015Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithmscited by 31
  14. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  15. 2019A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noisecited by 26
  16. 2020Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimismcited by 22
  17. 2019NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantizationcited by 17
  18. 2021Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guaranteescited by 15
  19. 2020Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithmscited by 14
  20. 2022Optimal Algorithms for Decentralized Stochastic Variational Inequalitiescited by 14
  21. 2020Towards Tight Communication Lower Bounds for Distributed Optimisationcited by 6
  22. 2018Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oraclecited by 4
  23. 2021Adaptive first-order methods revisited: Convex optimization without Lipschitz requirementscited by 4

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Addressing Label Shift in Distributed Learning via Entropy Regularizationcited by 1
  2. 2025Layer-wise Quantization for Quantized Optimistic Dual Averagingcited by 1