mlsanityData to 7 Oct 2026

Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees

arXiv 2110.03313 ↗First posted 7 Oct 2021cs.LG stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

Variational inequalities in general and saddle point problems in particular are increasingly relevant in machine learning applications, including adversarial learning, GANs, transport and robust optimization. With increasing data and problem sizes necessary to train high performing models across various applications, we need to rely on parallel and distributed computing. However, in distributed training, communication among the compute nodes is a key bottleneck during training, and this problem is exacerbated for high dimensional and over-parameterized models. Due to these considerations, it is important to equip existing methods with strategies that would allow to reduce the volume of transmitted information during training while obtaining a model of comparable quality. In this paper, we present the first theoretically grounded distributed methods for solving variational inequalities and saddle point problems using compressed communication: MASHA1 and MASHA2. Our theory and methods allow for the use of both unbiased (such as Randk; MASHA1) and contractive (such as Topk; MASHA2) compressors. New algorithms support bidirectional compressions, and also can be modified for stochastic setting with batches and for federated learning with partial participation of clients. We empirically validated our conclusions using two experimental setups: a standard bilinear min-max problem, and large-scale distributed adversarial training of transformers.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 70 of its 103 references that are in the map. First posted on arXiv 7 Oct 2021.

Builds on

70 of 103 references.

References · 70

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,266
  4. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  5. 2016Layer Normalizationcited by 5,579
  6. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,854
  7. 2019Advances and Open Problems in Federated Learningcited by 3,021
  8. 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsitycited by 3,014
  9. 2019ALBERT: A Lite BERT for Self-supervised Learning of Language Representationscited by 2,772
  10. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  11. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  12. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 471
38 more
  1. 2017Robust Adversarial Reinforcement Learningcited by 439
  2. 2018Sparsified SGD with Memorycited by 373
  3. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  4. 2016NIPS 2016 Tutorial: Generative Adversarial Networkscited by 284
  5. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  6. 2019FreeLB: Enhanced Adversarial Training for Natural Language Understandingcited by 261
  7. 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 234
  8. 2018The Convergence of Sparsified Gradient Methodscited by 228
  9. 2017Training GANs with Optimismcited by 217
  10. 2019A Survey on Distributed Machine Learningcited by 187
  11. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 174
  12. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  13. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  14. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  15. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  16. 2020On Biased Compression for Distributed Learningcited by 140
  17. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  18. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  19. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 131
  20. 2020Adversarial Training for Large Neural Language Modelscited by 109
  21. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
  22. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  23. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  24. 2019Natural Compression for Distributed Deep Learningcited by 88
  25. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  26. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 77
  27. 2016CoCoA: A General Framework for Communication-Efficient Distributed Optimizationcited by 69
  28. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  29. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  30. 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 61
  31. 2021Distributed Deep Learning in Open Collaborationscited by 58
  32. 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 57
  33. 20158-Bit Approximations for Parallelism in Deep Learningcited by 56
  34. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  35. 2019Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedbackcited by 49
  36. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  37. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  38. 2021Stochastic Variance Reduction for Variational Inequality Methodscited by 46

50 most cited of 70 All 70 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 5; 2024: 3; 2025: 1; 2026: 2.

15 papers.

Sort:

  1. 2022Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methodscited by 37
  2. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  3. 2023Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Ratescited by 12
  4. 2022Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalitiescited by 8
  5. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  6. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  7. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  8. 2024Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalitiescited by 5
  9. 2023Distributed Extra-gradient with Optimal Complexity and Communication Guaranteescited by 2
  10. 2024Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similaritycited by 2
  11. 2025Layer-wise Quantization for Quantized Optimistic Dual Averagingcited by 1
  12. 2022Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Topcited by 0
3 more
  1. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0
  2. 2026Resilient Decentralized Wireless Federated Learning via Gradient Tracking with AdamWcited by 0
  3. 2026Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compressioncited by 0