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

Variational inequalities in general and saddle point problems in particular\nare increasingly relevant in machine learning applications, including\nadversarial learning, GANs, transport and robust optimization. With increasing\ndata and problem sizes necessary to train high performing models across various\napplications, we need to rely on parallel and distributed computing. However,\nin distributed training, communication among the compute nodes is a key\nbottleneck during training, and this problem is exacerbated for high\ndimensional and over-parameterized models. Due to these considerations, it is\nimportant to equip existing methods with strategies that would allow to reduce\nthe volume of transmitted information during training while obtaining a model\nof comparable quality. In this paper, we present the first theoretically\ngrounded distributed methods for solving variational inequalities and saddle\npoint problems using compressed communication: MASHA1 and MASHA2. Our theory\nand methods allow for the use of both unbiased (such as Rand$k$; MASHA1) and\ncontractive (such as Top$k$; MASHA2) compressors. New algorithms support\nbidirectional compressions, and also can be modified for stochastic setting\nwith batches and for federated learning with partial participation of clients.\nWe empirically validated our conclusions using two experimental setups: a\nstandard bilinear min-max problem, and large-scale distributed adversarial\ntraining of transformers.\n