Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Ze’ev Zukerman, Bassel Hamoud, Kfir Y. Levy · 2025
Read Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning by Ze’ev Zukerman, Bassel Hamoud, Kfir Y. Levy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05508.txt.
Introduction
Ze'ev Zukerman, Bassel Hamoud, and Kfir Levy present a study from twenty twenty-five on cutting talk costs in distributed learning without skewing the result. Many machines train one model and must swap gradient data. Squeezing that data saves bandwidth. Fast squeezers skew the data, while clean ones lack firm ground in tests. The team seeks both speed and clean math.
Their scheme stacks many levels of squeezed reads in a Monte Carlo blend. The blend wipes out the skew while it keeps the speed. They apply it to top-k and bit wise squeezers and gain sharper forms of each. A self tuning form lifts scores more. Tests on deep learning tasks back the claims.
Catalog record
| CREATOR | Ze’ev Zukerman, Bassel Hamoud, Kfir Y. Levy |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-05508
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning Ze’ev Zukerman, Bassel Hamoud, Kfir Y. Levy 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 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. † † affiliationnotice: Equal contribution 1 Introduction Distributed learning has emerged as a critical paradigm for scaling machine learning to massive datasets across multiple computing nodes. In this setting, a central server coordinates multiple worker nodes, each computing local gradients on their respective data shards and communicating updates back to the server. This parallelization accelerates training, but introduces a fundamental bottleneck: communication overhead ( Konečný et al. 2018 ; Wang et al. 2021 ) . To mitigate this, gradient compression techniques are commonly employed to reduce the volume of transmitted data ( Alistarh et al. 2017 ; Lin et al. 2018 ) . However, these methods introduce a trade-off between unbiased and biased compressors ( Beznosikov et al. 2020 ) . Unbiased compression techniques, such as random sparsification (e.g., Rand- k ) and statistical quantization methods (e.g., QSGD ( Alistarh et al. 2017 ) ), ensure that the expected value of the compressed gradient remains equal to the original gradient. They are well understood theoretically because they align with the standard theoretical guarantees of data-parallel SGD ( Jain et al. 2017 ; Dekel et al. 2012 ) . However, their empirical performance is often suboptimal since they select elements at random rather than prioritizing the most informative components of the gradient. This leads to inefficient gradient updates, which negatively affect performance. In contrast, biased compressors, such as Top-k sparsification, retain the most informative components of the gradient while discarding less significant elements, leading to superior empirical performance ( Seide et al. 2014 ; Richtárik et al. 2021 ) . However, they introduce a degradation in theoretical guarantees, as their biased nature prevents them from directly aligning with the classical analysis of data-parallel SGD. This necessitates additional correction mechanisms, such as error feedback (e.g., EF21 ( Richtárik et al. 2021 ) ), to ensure convergence. Beyond gradient compression, distributed learning encompasses a wide range of techniques aimed at improving scalability and efficiency. Methods such as asynchronous training ( Recht et al. 2011 ; Dean et al. 2012 ; Tyurin et al. 2024 ) , in which worker nodes update the central model without waiting for all nodes to synchronize, help mitigate communication delays. Federated learning ( Konecný et al. 2016 ; Kairouz et al. 2021 ) , which enables training while preserving data privacy, has also gained significant traction. Furthermore, decentralized training ( Koloskova et al. 2019 ) removes the need for a server to maintain the model and instead propagates knowledge through ”gossip” mechanisms. Additionally, techniques like local updates ( Stich 2019 ; Dahan & Levy 2024 ; Mishchenko et al. 2022 ; Condat et al. 2023 ) , where workers perform multiple gradient steps before communicating with the server, reduce communication frequency and enhance efficiency. Each of these methods aims to strike a balance between computation, communication, and convergence guarantees. To bridge the gap between unbiased and biased compression techniques, we introduce a novel compression scheme based on Multilevel Monte Carlo (MLMC) methods ( Giles 2013 ) . MLMC techniques construct an estimator by combining multiple levels of approximation, each with a different quality (variance) and cost. The heart of the MLMC method is that it transduces bias into variance. We leverage this core property to construct unbiased estimates from biased compressed gradients, transducing their bias into controlled variance, and thereby ensuring both empirical efficiency and good parallelization ability. We apply our MLMC-based framework to popular compressors, demonstrating how it enhances their performance by reducing compression bias while keeping the communication costs minimal. Furthermore, we introduce an adaptive version of our approach, dynamically optimizing compression levels to further improve efficiency. We validate our method through various deep learning experiments, showcasing its convergence speed and communication efficiency. By leveraging MLMC to mitigate compression bias, our work provides a principled solution that reconciles the strengths of biased and unbiased compression techniques. This contribution paves the way for more efficient distributed learning frameworks that maintain both strong theoretical guarantees and superior empirical performance. 1.1 Related Work Gradient compression techniques are essential for reducing communication costs in distributed optimization. These methods fall into unbiased and biased approaches, each offering different trade-offs in terms of convergence guarantees and empirical performance. Some works also explore bidirectional compression , where both worker-to-server and server-to-worker communication is compressed ( Horváth et al. 2022 ; Gorbunov et al. 2020 ) . While bidirectional compression is relevant in some distributed learning settings, our focus remains on gradient compression , where the primary challenge is reducing worker-to-server communication while ensuring convergence. Unbiased Compression Methods. Unbiased compression methods ensure that the expectation of the compressed gradient equals the true gradient. QSGD ( Alistarh et al. 2017 ) and natural compression ( Horváth et al. 2022 ) are prominent examples, providing strong theoretical guarantees but suffering from slow empirical convergence due to the random selection of gradient components. DIANA ( Mishchenko et al. 2023 ; Horváth et al. 2019 ) overcomes this by compressing gradient differences. MARINA ( Gorbunov et al. 2021 ) incorporates variance reduction to mitigate this issue by using unbiased compressions of gradient differences. DASHA ( Tyurin & Richtárik 2023 ) improves efficiency using structured and compressed updates only. EF-BV ( Condat et al. 2022 ) offers a unifying framework for biased and unbiased compressors, which recovers both DIANA and EF21 ( Richtárik et al. 2021 ) as special cases, but does not aim to generate unbiased estimators from biased ones, in contrast to our work. Horváth & Richtárik 2021 developed a related approach, which constructs an unbiased compressor from two biased ones using an error feedback mechanism, achieving better convergence at the cost of roughly doubling the communication cost. Biased Compression Methods and Error Feedback. Biased compressors, such as Top-K sparsification ( Stich et al. 2018 ) and SignSGD ( Bernstein et al. 2018 ; Karimireddy et al. 2019 ) , retain the most informative gradient components, leading to superior empirical performance. However, these methods introduce biases that require correction to ensure convergence. Error feedback (EF) ( Seide et al. 2014 ) was introduced as a correction mechanism, which was later refined by EF21 ( Richtárik et al. 2021 ) to eliminate restrictive assumptions and improve theoretical guarantees. EF21-SGDM ( Fatkhullin et al. 2023 ) further stabilizes updates using momentum, reducing sample complexity and improving