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.

Authors

• Dmitry Bylinkin Moscow Institute of Physics and Technology Ivannikov Institute for System Programming of the Russian Academy of Sciences
• Aleksandr Beznosikov Ivannikov Institute for System Programming of the Russian Academy of Sciences Moscow Institute of Physics and Technology Sber AI Lab Skoltech

Keywords

No keywords are indexed for this paper.