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

Aleksandr Beznosikov, Peter Richtarik, Michael Diskin, Max Ryabinin, Alexander Gasnikov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


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.
Original languageEnglish (US)
Title of host publication36th Conference on Neural Information Processing Systems, NeurIPS 2022
PublisherNeural information processing systems foundation
ISBN (Print)9781713871088
StatePublished - Jan 1 2022


Dive into the research topics of 'Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees'. Together they form a unique fingerprint.

Cite this