Communication-efficient solution of distributed variational inequalities using biased compression, data similarity and local updates

Voronov R.E., Maslennikov E.M., Beznosikov A.N.
 pdf (740K) / Supplementary information

Variational inequalities constitute a broad class of problems with applications in a number of fields, including game theory, economics, and machine learning. Today’s practical applications of VIs are becoming increasingly computationally demanding. It is therefore necessary to employ distributed computations to solve such problems in a reasonable time. In this context, workers have to exchange data with each other, which creates a communication bottleneck. There are three main techniques to reduce the cost and the number of communications: the similarity of local operators, the compression of messages and the use of local steps on devices. There is an algorithm that uses all of these techniques to solve the VI problem and outperforms all previous methods in terms of communication complexity. However, this algorithm is limited to unbiased compression. Meanwhile, biased (contractive) compression leads to better results in practice, but it requires additional modifications within an algorithm and more effort to prove the convergence. In this work, we develop a new algorithm that solves distributed VI problems using data similarity, contractive compression and local steps on devices, derive the theoretical convergence of such an algorithm, and perform some experiments to show the applicability of the method.

Keywords: variational inequalities, biased compression, data similarity, local updates
Citation in English: Voronov R.E., Maslennikov E.M., Beznosikov A.N. Communication-efficient solution of distributed variational inequalities using biased compression, data similarity and local updates // Computer Research and Modeling, 2024, vol. 16, no. 7, pp. 1813-1827
Citation in English: Voronov R.E., Maslennikov E.M., Beznosikov A.N. Communication-efficient solution of distributed variational inequalities using biased compression, data similarity and local updates // Computer Research and Modeling, 2024, vol. 16, no. 7, pp. 1813-1827
DOI: 10.20537/2076-7633-2024-16-7-1813-1827
URL: http://crm-en.ics.org.ru/journal/article/3570/

 

Supplementary information:

 

Proof of Theorem 1

SI_voronov.pdf

 

Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2025 Institute of Computer Science