Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity

In recent years, as data and problem sizes have increased, distributed learning has become an essential tool for training high-performance models. However, the communication bottleneck, especially for high-dimensional data, is a challenge. Several techniques have been developed to overcome this problem. These include communication compression and implementation of local steps, which work particularly well when there is similarity of local data samples. In this paper, we study the synergy of these approaches for efficient distributed optimization. We propose the first theoretically grounded accelerated algorithms utilizing unbiased and biased compression under data similarity, leveraging variance reduction and error feedback frameworks. In terms of communication time our theory gives ?(1+[M^(-¼)+?^(-½)]√(? /?)) complexity for unbiased compressors and ?(1+β^(¼)√(? /?)) for biased ones, where M is the number of computational nodes, β is the compression power, ? is the similarity measure and ? is the parameter of strong convexity of the objective. Our theoretical results are of record and confirmed by experiments on different average losses and datasets.