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

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

## Key facts

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

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [NIPS 2016 Tutorial: Generative Adversarial Networks](https://mlsanity.com/paper/1701.00160/) (2016)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [FreeLB: Enhanced Adversarial Training for Natural Language Understanding](https://mlsanity.com/paper/1909.11764/) (2019)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [SCAFFOLD: Stochastic Controlled Averaging for Federated Learning](https://mlsanity.com/paper/1910.06378/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/1703.06182/) (2017)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)

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

- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Rates](https://mlsanity.com/paper/2310.09804/) (2023)
- [Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalities](https://mlsanity.com/paper/2206.09446/) (2022)
- [Federated Minimax Optimization with Client Heterogeneity](https://mlsanity.com/paper/2302.04249/) (2023)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities](https://mlsanity.com/paper/2403.07148/) (2024)
- [Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top](https://mlsanity.com/paper/2206.00529/) (2022)
- [Distributed Extra-gradient with Optimal Complexity and Communication Guarantees](https://mlsanity.com/paper/2308.09187/) (2023)
- [Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similarity](https://mlsanity.com/paper/2412.16414/) (2024)
- [Layer-wise Quantization for Quantized Optimistic Dual Averaging](https://mlsanity.com/paper/2505.14371/) (2025)
- [Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity](https://mlsanity.com/paper/2405.16126/) (2024)
- [Resilient Decentralized Wireless Federated Learning via Gradient Tracking with AdamW](https://mlsanity.com/paper/2608.25535/) (2026)
- [Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression](https://mlsanity.com/paper/2609.36610/) (2026)

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