Abstract: Distributed learning methods have gained substantial momentum in recent years, with communication overhead often emerging as a critical bottleneck. Gradient compression techniques alleviate communication costs but involve an inherent trade-off between the empirical efficiency of biased compressors and the theoretical guarantees of unbiased compressors. In this work, we introduce a novel Multilevel Monte Carlo (MLMC) compression scheme that leverages biased compressors to construct statistically unbiased estimates. This approach effectively bridges the gap between biased and unbiased methods, combining the strengths of both. To showcase the versatility of our method, we apply it to popular compressors, like Top-$k$ and bit-wise compressors, resulting in enhanced variants. Furthermore, we derive an adaptive version of our approach to further improve its performance. We validate our method empirically on distributed deep learning tasks.

Lay Summary:

In large-scale machine learning, especially when training very large models like ChatGPT, computers often work together by exchanging information, but this communication can become a major bottleneck. To save bandwidth, systems compress the data they send. However, this introduces a trade-off: the most efficient compressions reduce theoretical reliability, while the safest ones reduce the efficiency of the training process. Our work introduces a new technique that uses a concept from statistics called “Multilevel Monte Carlo” to get the best of both worlds: fast, efficient communication with reliable learning guarantees. We show how this approach turns even biased, aggressive compressions into accurate and trustworthy information. This helps machine learning systems train faster across many devices, without sacrificing robustness or accuracy.