Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Authors: Ze'ev Zukerman
Bassel Hamoud
Kfir Yehuda Levy
Venue: ICML 2025 poster (2025)
Keywords: Distributed Learning
Compressed Gradients
Multilevel Monte Carlo
Primary area: optimization->large_scale_parallel_and_distributed

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.

Beyond Communication Overhead: A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Ze'ev Zukerman 1
Bassel Hamoud ! Kfir Y. Levy'
Abstract
et al., 2017: Lin et al., 2018). However, these methods intro- duce trade-off between unbiased and biased compressors (Beznosikov et al., 2020).
Distributed learning methods have gained substan- tial momentum in recent years, with communica- tion overhead often emerging as critical bottle- neck. Gradient compression techniques allevi- ate communication costs but involve an inherent trade-off' between the empirical efficiency of bi- ased compressors and the theoretical guarantees of unbiased compressors. In this work, we intro- duce a novel Multilevel Monte Carlo (MLMC) compression scheme that leverages biased com- pressors to construct statistically unbiased esti- mates. 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 im- prove its performance. We validate our method empirically on distributed deep learning tasks.
Unbiased compression techniques, such as random sparsi- fication (e.g., Rand-k) and statistical quantization methods (e.g., QSGD (Alistarh et al., 2017)). ensure that the ex- pected 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 often suboptimal since they select elements at random rather than prioritiz- ing the most informative components of the gradient. This leads inefficient gradient updates, which negatively affect performance.
In contrast, biased compressors, such as Top-k sparsifica- tion, retain the most informative components the gradient while discarding less significant elements, leading to supe- rior empirical performance (Seide et al., 2014; Richtárik et al., 2021). However, they introduce a degradation in theo- retical 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.
1. Introduction
Distributed learning has emerged as a critical paradigm for scaling machine learning to massive datasets across multiple computing nodes. In this setting, central server coordi- nates 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 miti- gate this, gradient compression techniques are commonly employed to reduce the volume of transmitted data (Alistarh
Beyond gradient compression, distributed learning encom- passes wide range of techniques aimed at improving seala- bility and efficiency. Methods such asynchronous training (Recht al., 2011; Dean et al., 2012; Tyurin al., 2024), in which worker nodes update the central model without waiting for all nodes to synchronize, help mitigate commu- nication delays. Federated learning (Koneený et al., 2016; Kairouz et al., 2021), which enables training while pre- serving data privacy, has also gained significant traction. Furthermore, decentralized training (Koloskova et al., 2019) removes the need for server maintain the model and in- stead propagates knowledge through "gossip" mechanisms. Additionally, techniques like local updates (Stich, 2019; Da- han & Levy, 2024; Mishchenko et al., 2022; Condat et al., 2023), where workers perform multiple gradient steps be- fore communicating with the server, reduce communication frequency and enhance efficiency. Each of these methods
'Equal contribution 'Viterby Faculty of Electrical and Computer Engineering, Technion, Israel. Correspondence to: Ze'ev Zukerman <ze.zukermane @ wwwppp/s..eccioo........o Bas- sel Hamoud <bassell @ee@@amcmmamcmmiiiiii tcc.niio...i.......... Kfir Y. Levy <kfirylevy@teed @wwcheion..c..iii
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
aims strike a balance between computation, communica- tion, and convergence guarantees.
gate 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 bi- ased ones, in contrast to our work. Horváth & Richtárik (2021) developed 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.
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 qual- ity (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.
Biased Compression Methods and Error Feedback. Bi- ased 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 compo- nents, 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 re- strictive assumptions and improve theoretical guarantees. EFF1-SGDM (Fatkhullin al., 2023) further stabilizes up- dates using momentum, reducing sample complexity and improving convergence speed. Adaptive gradient sparsifica- tion (Han et al., 2020) dynamically adjusts sparsity levels, balancing communication efficiency and performance. The introduction of bias typically adds additional terms to the convergence bounds (Fatkhullin et al., 2023) which can hinder performance in massive parallelization settings.
We apply our MLMC-based framework to popular compres- sors, demonstrating how it enhances their performance by reducing compression bias while keeping the communica- tion costs minimal. Furthermore, we introduce an adaptive version of our approach, dynamically optimizing compres- sion levels to further improve efficiency. We validate our method through various deep learning experiments, show- casing its convergence speed and communication efficiency.
By leveraging MLMC 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 dis- tributed learning frameworks that maintain both strong the- oretical 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 guaran- tees and empirical performance. Some works also explore bidirectional compression, where both worker-to-server and sevver-to-worker communication is compressed (Horváth et al., 2022; Gorbunov et al., 2020). While bidirectional compression is relevant in some distributed learning set- tings, our focus remains on gradient compression, where the primary challenge is reducing worker-to-server commu- nication while ensuring convergence.
In summary, unbiased methods are well understood, easy to analyze, and enjoy simple bounds, but are often impracti- cal due to inefficiency, while biased methods, coupled with EF techniques, offer superior empirical results. Our work builds on these insights by further refining biased compres- sion strategies and offering a Blug-and-play mechanism to construct unbiased estimates from biased ones. We further show that our technique works seamlessly for any compres- sor and enhances convergence efficiency, bridging the gap between biased and unbiased compression methods.
2. Background
Unbiased Compression Methods. Unbiased compres- sion 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 guaran- tees 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 (Gor- bunoy al., 2021) incorporates variance reduction to miti-
2.1. Problem Statement
We consider the distributed machine learning setting with a master server and M machines = 1,... M. We assume heterogeneous setting in which each machine i E [M] has access to i.i.d samples from some data distribution D,. We aim to minimize the following problem:
M
arg min f(z) = arg min
1
Σ fl(z)
(I)
#CRd
ZERd
M
i=
2

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
where J R4 I measures the expected loss of the model on the local data of machine i. Namely, fi(x)) [fi, =:)], where fi(z, z4) is the loss of model x w.r. sample 2; ~ D,. In each step t E [T], the master server broadcasts the current model Iy E R2d to the M machines, and each machine i [M]] computes a stochastic gradient V4,4 - V [i Rt.i,, where Zt,; ~ D, computes a compression (an estimate) gt,t of Vt,s. and sends gr back to the server. The server aggregates ( and uses the result to update the model. Note that when Jr,i Vr,i, we have the known Data-parallel SGD scheme, which is formalized in Alg. 1 and Theorem 2.3 (Dekel et al., 2012: Ghadimi & Lan, 2013). Note that a central property of Theorem 2.3 is that the gradients are conditionally unbiased, i..., [[+
2.2 and by optimizing over 1). the error bound (both for the convex and the nonconvex cases) can be written as:
O
VMT (
a
Up to factors that are independent of T, .M and a. As we elaborate next, incorporating compression into parallel SGD in Alg. alters these bounds, either by increasing the vari- ance term in the case of unbiased compression, or by ren- dering them obsolete in the case of biased compression.
2.2. Training with Compressed Gradients
While the naive parallelization scheme in Alg. 1 straight- forward, it neglects the communication cost between the machines and the server. With today's computational power, communication serves as the main bottleneck in the learn- ing process. Consequently, many methods resort to using compressed versions of the gradients to reduce the com- munication cost (see Sec. 1.1). Such compressors can be broadly classified into two main categories:
V (zz),, Vt This assumption is not always satisfied when compression is introduced, as we elaborate in the following subsections.
We make the following assumptions throughout the paper: Assumption 2.1. The loss functions St are I-ssmooh::
fa(v) & f((x) + (V...)),yy - z) + 1 ly - x11² Vx, y E Re, Vi E [M].
Assumption 2.2. The uncompressed stochastic gradients Vi((e, 2) have bounded variance: Vi [M], Va E IR.
(1) Unbiased compressors, which for w 2 0 and Ve E Bd satisfy:
(1,,) Vf(())) <
[[C(z)] = x BII[(()) - ==1²1 = w ||=|| (3)
Algorithm 1 Data-parally SGD
Input: initialization 31, step-size n).
(2) Biased compressors, which for 0 < < 1 and Vz e Rdd satisfy:
for t = 1 to 7 do
The server broadcasts Ie to machines = 1, M
([C())++r; BIIC(+) x1 s (1 a) ||t|| (4)
for i= 1 to M in parallel do
Sample 2,,; from local dataset D;
Compute Vt.;- = Vii( 2.,)
where the above expectations are w.r.t. the randomization potentially introduced by C. The use of unbiased compres- sors is usually straightforward as they are easy to incorpo- rate into the parallelization scheme in Alg. 1 where only the second term will affected with an increased vari- ance. However, biased compressors generally yield better practical results, since they tend retain more energy of the compressed entity compared unbiased counterparts. Unfortunately, their naive incorporation in Alg. may fail to converge (Beznosikov et al., 2020), since now the com- pressed gradients are not unbiased estimates of the true gradients, and more sophisticated optimization schemes are required (Seide et al., 2014; Richtárik al., 2021). We now survey a few popular compressors that are used for training with compressed gradients.
Send D to server
end for
Server aggregates: et EM De1
Server updates: r++1 = T2 7p0
end for
Theorem 2.3. Under Assumption 2.1, Alg. I guarantees the following error in the convex case, for any 1) S 1/2L:
E [ f(x)))
S + "
D2
T
EV2,
2T
t=1
and the following error in the nonconvex case, for 1) S 1/L.
Σ E EV(((E))
T
24,
nT.
EV?,
T
Tn
where öT 7 EE=12
No. x² = arg min& f(x) D
Top-k
is popular compressor which retains the largest k elements in absolute value of given vector and zeros the rest. Naturally, Top-k is a biased compressor that satisfies Eq. (4) with a = k/d and k between I and d. It is generally empirically superior to its prevalent unbiased counterpart, Rand-k; which retains & randomly selected elements of a
||| x= V = M² MM Elllu,, fi(xx))) |aze, and
A [(x) f(x*).
Note that the error bounds in Theorem 2.3 depend on the variance of the gradients. Furthermore, under assumption
3

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
vector. Moreover, we consider a generalization of Top-k, which term s-segmented Top-k, or s-Top-k, which sorts given vector of length d, divides it into segments of length (except perhaps the last segment), and retains the k segments with the largest norm. Accordingly, a = sk/d and k ranges from to s.. Note that regular Top-k can be recovered from its generalized variant when 8 =
2.3. Multilevel Monte Carlo methods
Monte Carlo methods construct a variance-reduced estima- tor for the expectation of some random variable X using an ensemble of independent stochastic samples. In its simplest 1z=1
form, given unbiased i.i.d. samples { of X, such that E[X = [[ Vj [NV] a Monte Carlo estimate of [ is given by 1 Σy= x This estimator enjoys a reduced variance by factor of 1/N compared to that of the individual samples. This method implicitly assumes that the cost and quality (variance) of each sample are identical.
Bit-wise compressors are methods that utilize binary rep- resentation to compress numerical data. In our setting, we perform bit-wise compression of the binary representation of each element in the gradient vector in an element-wise manner. There are two common approaches for bit-wise compression:
Multilevel Monte Carlo (MLMC) methods (Giles, 2013) generalize this to setting where we can access samples of increasing quality but at an increasing cost. MLMC methods also obviate the need for unbiased samples, unlike regular Monte Carlo. Namely, given samples X1.() with variance V' and cost K for j E [N] and I E [L], where typically V decreases while K increases with 1, the MLMC estimator of [[[] is given by:
(1) Fixed-point compressors. Fixed-point methods code numbers with fixed integer and fractional bits. Compression is done by discarding the least significant bits and keeping the F most significant bits, introduc- ing distortion that is bounded by 2- F for each element.
X 1 (X'-x'-1) x where l
(2) Floating-point compressors. Floating-pon poinggg-ponttt methods encode numbers using a mantissa, the fractional part, and an exponent, the scale factor. Floating point com- pressors retain the exponent and the F' most significant bits of the mantissa, forming biased compressor that satisfies Eq. (4) with a = 1-
1~pl, p',
(5)
where {pi is non-zero probability distribution over the levels / E [Z] and X and X are some estimators of E[X] based on samples of levels I and [ - 1, respec- tively. One of the most intriguing properties of the MLMC estimator is that it is a naturally unbiased estimator of the highest-level expectation, namely [[[] = -[ Fur- thermore, MLMC methods effectively transduce bias into variance. This important property will play central role in our method, where X will be an unbiased estimate of E [X]. implying that X is an unbiased estimate of B[X].
As mentioned, the introduction of compression changes the error bounds of gradient-based methods. Unbiased compression only changes the variance. That because [2 (xx)),
B[C(v,,)] E [C namely the compressed gradients are still unbiased esti- mates of the true gradient. Additionally, note that:
[[](C(v..) V (
3. Multilevel Monte Carlo Parallel SGD
B[I[C(e(,) - Ue, + U2,s (a((2)) [are]
Motivated by the trade-off between biased compressors, which have superior performance but suffer worse theoret- ical guarantees, and unbiased compressors, which exhibit the opposite, we set to explore method to bridge this gap. Namely, we pose the following question:
E[I[C((e,)) vll [20]]
[lll (z,))) lm:).
22omp
and simply plugging this updated variance term into the known bounds of Theorem 2.3 yields the corresponding error bounds. The use of biased compressors, although empirically superior to their prevalent unbiased counterparts, requires a different treatment to account for the bias they introduce, which often hinders parallelization and affects the error bounds (Fatkhullin et al., 2023).
Can we simultaneously utilize the superior performance of biased compressors and enjoy the better theoretical guarantees of unbiased compressors?
address this, we propose a novel method that exploits the properties of MLMC estimators and allows us to use biased compressors without adversely affecting the theo- retical convergence guarantees. Our idea is to generate MLMC estimators of the biased gradient compressions and use those to update the model. This way, although the com- pressed gradients can be biased, their MLMC estimators are always unbiased, but are typically accompanied by a slightly increased variance.
In our work, we suggest novel approach construct unbi- ased versions of popular compressors such that we retain the most important information (as biased compressors) with- out hindering parallelization (as unbiased compressors). We aim to construct new enhanced estimators that achieve the best of both worlds using a novel compression scheme based on Multilevel Monte Carlo on which we elaborate next.
4

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Each compressor (e.g.. Top-k, s-Top-k, bit-wise compres- sors, etc.) typically has parameter that tunes the extent of compression. For example, smaller k in Top-k or s- Top-k translates to more aggressive compression. We define the "estimate levels" 7 E [7.] of the MLMC estimate in correlation with these parameters, such that lower levels correspond to more aggressive compression, while higher levels correspond to a softer compression. For efficiency, we incorporate this into new class of compressors, which we term Multilevel Compressors, and define it as follows.
We formalize our method in Alg. 2, where each machine E [M]: (1) computes the gradient ta,i based on one stochastic sample žt,i, (2) samples compression level E [L] according to predefined probability distribution (r') (3) constructs the MLMC gradient ft, according to Eq. (6), and (4) sends it back to the server. The server aggregates the MLMC gradients and updates the model. Note that while the general template of Alg. 2 requires two compressions in each iteration for the levels I and - 1, in certain cases computing the residual أ¹ 9 can be done efficiently without explicitly calculating each term, and it can be transmitted cheaply as well. For example, for Top-k, I.. - includes only the l'th largest element (in absolute value), and for 8- s-Top-k, the residual includes the segment of length s with the l'th largest norm.
Definition 3.1. C² : :" + R is a multilevel compressor, where 1 E [L] corresponds to the compression level and the highest level L corresponds to no compression, i.c.,
YU E Rd (v) = u.
For example, in the case of Top-k and s-Top-k, the levels correspond to the parameter k. Thus, lower levels lead to a worse estimate of the original gradient but lower commu- nication cost, while higher levels yield a better estimate but a higher communication cost, and the highest level I. corre- sponds to no compression at all (e.g., Top-k with &- = d, or 8- Topp- with k= = [d/s]).
Algorithm 2 MLMC LLLMC-Compressed Parallel SGD
Input: initialization Tı, step-size 1), multilevel compres- sor C², and level probabilities (r///2
for = 1 to T do
The server broadcasts 24 to machines i 1,,,, M
for i to M in parallel do
Concretely, given a multilevel compressor C², where I E [L]. non-zero level probabilities {r') 1== and an uncom- pressed stochastic gradient Ur the MLMC gradient esti- mate of v a is given by:
Sample 24, from local dataset D; Compute v1,4" Vie(
Sample ~ p'
Compress gi,4 C* (vr,),
H2. 1-1 = (vr))
Construct 9t,5 = gh. + # (g/ 9
He,4 = -6.5 + /)
(sh: - -
where I 1n
(6)
Send Dt. to server end for Server aggregates: gr 1
pr
where Ji.+- (v.,), gtt (t,)( and we define oh = 0 (e.g.. Top-k with lo = 0). This MLMC compression scheme yields an unbiased estimate of the true gradient in step t, fz.)), as we formalize in Lemma 3.2.
M Ei=1 It.
Server updates: It-1 = It. - 179h end for
Lemma 3.2. For any multilevel compressor C² [L] and any non-zero probabilities {y' Jp' the MLMC estimator I.,t & gº,++ + (g',, - ). where L ~ p'. is a conditionally unbiased estimate of the true gradient, V f(()). Namely: Elg.. [r]] = f((e))) Vt E [i). [M].
Note that the optimization scheme in Alg. 2 is very similar to that of Alg. (regular data-paralle SGD). That is thanks to the unbiasedness of the MLMC estimates (Lemma 3.2).
1-1,
In the next subsections, we analyze our algorithm and derive the optimal level probabilities that minimize the MLMC estimate variance for popular baseline compressors, and for special cases of gradient distributions that arise in deep learning models.
We defer the proof to App. A. Intuitively, our MLMC block can be thought of as a black box that takes the stochastic gradient, a compressor (e.g., s- s-Top-k), and a probability distribution over the compression levels (c.g., the values of k) and outputs an unbiased estimate of the true gradient. The probability distribution is optimized to minimize the variance of the MLMC estimator. In some cases, we show that the probability distribution can be chosen in an adaptive manner, per sample, optimize the variance for each sam- ple independently. Furthermore, since our method replaces the stochastic gradients with their MLMC estimates, which are also unbiased (see Lemma 3.2), the error bounds in The- orem 2.3. for the convex and the nonconvex case, remain largely the same and only the variance term is affected.
3.1. WLMCCM Comprrsooooniio Using Bis- Compressors
A popular compression method used in distributed learning is bit-wise compression, especially fixed-point and floating- point compression (Seide et al., 2014; Dryden et al., 2016; Chmiel et al., 2021). We now discuss the fixed-point-basee MLMC compression scheme. The analysis of floaiin-poiin MLMC compression is similar but does not enjoy the same compression rate since the exponent must always be trans- mitted. We defer the full analysis to App. B.
5

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Since fixed-point compressors operate in an element-wise manner, we consider some entry Gt of gradient vector Vt,i- Assuming le,,il S (note that we can divide the entries of Ut. by the largest entry and transmit it as well), Ct.; can be written as a 64-bit fixed-point binary number, as follows:
method. For a given vector Ve,a E R4, the distortion in- troduced by Top-k and some compression level I [7.] can be written as follows:
[| ue,ell (1- af.)) |ouel
(10)
63
where 0 < oh,, S 1 is chosen appropriately such that the equality is satisfied. Eq. (10) describes the tightest possible bound (an equality) on the distortion introduced by the com- pressor, and this bound is different (adaptive) for different vectors U2
E, = (- Σ 6,2
J=1
where bj E {0. 1) is the j-th bit in the binary representation. For each entry et,;, the multilevel fixed-point compressor C" truncates the sum to / elements, with ranging between 1 and 63. The resulting distortion introduced by the com- pression is bounded by 2- for each entry.
Additionally, note that when using Top-k with our method in Alg. 2, the residual g - o consists only of one term that corresponds to the / I'th largest element (in absolute value) of the uncompressed stochastic gradient V/,,s. Thus, the com- munication cost in this case will be the cost of transmitting one entry. Similarly, for s-Top-k; g1,; g/.²² consists of the l'th largest segment (in norm) of Vt, (containing en- tries, at most), thus the communication cost will be that of transmitting s numbers.
We incorporate the fixed-point compressor into the MLMC compression scheme. Each entry of the residual 9 Ft.s I-1 in this case consists of two bits, one information bit and one sign bit. Therefore, the transmission cost of the MLMC gra- dient, It... is the cost of transmitting two bits for each entry in the residual vector, 64 additional bits for the maximum entry, and [log2 [63)] for i.e., 2d + 64 + [log2 (63)] bits in total in each iteration for each machine. Note that when d >> 1 (which is often the case in deep learning), this com- pression scheme transmits approximately 2d bits in each iteration, compared to 64d bits for the uncompressed vec- tors. This is a x32 improvement in communication costs. Furthermore, the lisaance-miimmiiing level probabilities are formalized in Lemma 3.3 (proof in App. C).
Given this insight, in Lemma 3.4, we exploit this adaptive bound and use it to derive an adaptive probability distribu- tion over the compression levels that minimizes the variance of the MLMC gradient in each iteration.
Lemma 3.4. Given any multilevel compressor C², the op- timal probability distribution that minimizes the variance of MLMC estimator in iteration E {T) and for machine i E [M] is given by:
Lemma 3.3. The optimal probability distribution that min- imizes the variance of the fixed-point MLMC estimator is given by:
pl. =
(11)
2
Σ
A
p
(8)
1 2-63'
where A/,; || s ||. and note that for a multilevel
3.2. MLMC-Compresiion Using Top-k
compressor based on s- sTopp- kk ph,, in Lemma 3.4 further
Given any vector v E Rd, Top-k retains its largest A: ele- ments (in absolute value) and zeros the rest. Namely, Top-k is a biased compressor with a = k/d, whose distortion satisfies the following bound for any vector Rd (note
Vol..- reduces to pl., Σイ
(proof in App. D).
We incorporate this adaptive probability distribution over the compression levels with our MLMC compression method into a new adaptive optimization scheme formalized in Alg. 3. This optimization scheme is similar to that of Alg. 2, although here, the level probability distribution is chosen in an adaptive manner for each sample in each step (see Lemma 3.4). Since the MLMC gradients are unbi- ased estimates of the true gradients, namely [[]rr=| = f((e)) Vt E [T] Vi E [M], only the variance term in Theorem 2.3 will be affected.
that Top-k is deterministic):
(9) Similarly to the analysis with bit-wise compressors, we wish to find the optimal probability distribution p' over the com- pression levels E [L]. However, note that the bound in Eq. (9) a worst-case bound, and the equality is satisfied only when e is uniform. Fortunately, in practice and espe- cially in Deep Learning, we often encounter non-uniform gradients (Glorot & Bengio, 2010). This key observation serves as motivation for developing more adaptive methods to close this gap.
[[C(v) =1 < (1 a1 ||o||2
Interestingly, our method recovers importance sampling (IS) techniques (c.g., (Beznosikov et al., 2020)) in certain cases. For example, in the case of Top-k, our method is equivalent to sampling and communicating the I-th entry of o,, (scaled by 1/p(.)) with probability ph.-- However, our
We exploit this oveen-overlooked property and use a tighter adaptive bound for each sample to further enhance our
6

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
2018). Specifically, (Glorot & Bengio, 2010; Shi al., Algorithm 3 Adaptive WLLMC-Compresseer Parallel SGD
Input: initialization 21,, step-size 77, multilevel compres-
2019) show that gradients in neural networks during train- ing often have Gaussian-like distributions. We demonstrate the adaptability of our method in this case and show that it indeed exploits this special structure for more efficient training. For ease of analysis, let us consider a more relaxed case in which the entries of the gradients decay exponen- tially in absolute value (note that ae- S bee", : Va, x E IR, for an appropriate choice of b. and therefore this the more general case). We formalize this in Assumption 3.5.
sors {C"]
for 1. = 1 to T do
The server broadcasts Te to machines i 1, M for i = 1 to M in parallel do
Sample Zz.s from local dataset D;
Compute Vt,1 = V [1 21,5)
A/.
Compute Pt.s Σト A
for forle E [Z]]
Sample 1 ~ pi.
Assumption 3.5. For any L E (T] and any i E [M], the sorted entries of the gradient Vt, satisfy, for Tr, > 0:
Compress lh., C¹ (vr,),, Jt. -2 (vL,))
Construct Jt.: = G.. + pt (ot,5 - )
Send St.s to server end for
= (0),e "
Server aggregates: 9t M EM gr.s
Server updates: 2++1 32- 19t end for
Note that this assumption implies that most of the energy of Ur is concentrated in 1/re, entries. This observation gives rise to two regimes depending of 1 1/rr.i and the length of the vector d: (1) d is very small compared to 1/rr,s, which implies slow decay and the tail is not negligible. If decay is very slow, i.e., the entries are approximately uniform, our method, Rand-k, and Top- k perform similarly; and (2) very large compared to 1/rr.,, which implies that a the tail of the gradient vector is negligible. Here, we expect our method to have a significant benefit over other unbiased estimators (e.g., Rand-k). This is the more interesting case and we formalize it in Lemma 3.6 (Please refer to App. E for the full proof).
the relative values
method strictly generalizes IS techniques, as it is compati- ble with complex structured compressors that do not admit such a coordinate-wise decomposition, and where IS is not naturally defined. This equivalence seems to arise only for sparsification-base methods such as Top-k. More involved compression methods exist for which there are no IS-like interpretations, e.g., structured quantization-bast such as Round-to-N to-eersst (RTN) (Gupta et al., 2023) and ECUQ (Dorfman et al., 2023).
methods
Lemma 3.6. Under Assumption 3.5 for sufficiently large r d, Alg. 3 with the s-Top-k compressor, and the optimal probabilities in Lemma 3.4. guarantees O variance of the MLMC estimator.
RTN- methods, for example, quantize each element of a given vector by rounding it to the nearest level on fixed grid. The spacing of this grid is controlled by a quantization step-size 8¹. Namely, the RTN-compression (of level-I) of v -c, c), where
8 clip(round(()) 2- and "round"' rounds each element to its nearest integer. Here, I E N corresponds to the compression level. No IS interpretation exists in this case since the difference g'.- Ir, 1-1 does not necessarily reduce to simple structure that can facilitate IS.
given by C² C'RTN())
In contrast, the variance of the compressed gradients when using Rand-k with k = is O (1) (Condat et al., 2022). Thus, when 1/ra, < d, our MLMC compressor enjoys smaller variance.
6' 2c
4. Convergence and Parallelization
Moreover, IS requires a specific, nontrivial construction which differs for each compression method, whereas our MLMC compression functions as a plug-and-play frame- work that works for any series of compressors satisfying Definition 3.1, without requiring any additional tuning or specific construction.
We proposed novel method that bridges the strengths of biased and unbiased methods by leveraging MLMC tech- niques to generate unbiased estimates of biased-compressed gradients. Our method statistically retains the more impor- tant parts of the gradients (similar to biased compression methods) while still enjoying good parallelization guaran- tees (like unbiased methods).
3.3. Special Case Analysis
Our adaptive MLMC compression scheme seems especially attractive in scenarios in which the entries of the gradients are far from uniform. Interestingly, in many cases when training deep learning models, the gradients appear to have special structures that we can exploit (Micikevicius et al.,
Note that since our MLMC gradient estimates are unbiased, similar error bound to Eq. (2) holds, with an additional term that stems from compression. For simplicity, we focus on the homogencous data setting. We formalize this in the following Theorem (we defer the proof to App. F.I).
7

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Theorem 4.1. Under Assumptions 2.1-2.2, Alg. 2 and Alg. 3 guarantee the following error bounds in the homogeneous convex and noncorvex cases, respectively:
5.1. Experiments with Sparsification Compressors
In the first set of experiments, we tested our MLMC- compression technique, with Top-k as a baseline compres- sor, and optimized the learning rate for each one individually. We compared the performance of our Adaptive MLMC- Top-k compressor (Alg. 3), the biased compressors Top-k and EF21-SGDM (Fatkhullin et al., 2023), and the unbiased compressor Rand-k, and Uncompressed SGD as a baseline. We evaluated two criteria: communication efficiency and iteration efficiency, which compare the test accuracy of the algorithms as a function of the communication complexity (the number of communicated bits) and as a function of the epochs (the number of iterations).
DEL T
WDDLL
+ (e + DJoD
MT
VMT
1 T
AIL T
SPAIL
MT + (++ 1)ovL
B /|V
EO
VMT
where @ the compression coefficient of our MLMC es- timator (see Eq. (3)). Exact calculations of for various compressors are available in App. B, D, E. Note that the middle term is asymptotically negligible compared to the right term, and thus these error bounds are usymptotically identical to those of ParalleI-SGD (Theorem 2.3; Eq. (2)), with a slightly increased variance due to compression.
We present the communication efficiency experimental re- sults in Figure I, for M = 4 machines (top quartet) and M 32 machines (bottom quartet). Each subplot displays the test accuracy of the compared algorithms, against the number of communicated bits, for various sparsification lev- els. specifically for is E {0.01n, 0.05m, 0.1n, 0.5m}. where n & 1.1 x 10s is the number of model parameters. We used a batch size of 16 in all experiments and averaged over 5 seeds. Moreover, we display these results against the number of epochs (iterations) in Figure 2.
In contrast, the error bound for biased methods, e.g., EF21- SGDM (Corollary 3 in (Fatkhullin et al., 2023)), which is the current state of the art, is given by (nonconvex case):
+ AL Ao T BIISS E o (Ar oT 01/273/1 MMT
1
+
Thus, our method allows parallelization over M = O(T). or equivalently M = O(VN), machines without a degra- dation of performance (where N is the size of the dataset), while EF21-SGDM allows M O( or equivalently /3). Moreover, our method complements methods like EF21-SGDM and others (which may be beneficial when M is small), in the regime of massive parallelization, i.c., when M is very large. We defer the analysis to App. F.3.
Figures 1-2 show that our comp-esonn method out- performs the other methods, both in terms of communica- tion and iteration efficiency. Notably, our method achieves a higher test accuracy for the same number of transmitted bits and enjoys a faster convergence rate compared to other meth- ods across different sparsification levels. Also, our method converges faster for M = 32 compared to M 4, which is consistent with our bounds in Theorem 4.1. Moreover, Fig- ure 2 shows that our method outperforms other compression methods in iteration efficiency, in terms of convergence rate and accuracy, and enjoys the same performance as uncom- pressed SGD, despite using significantly less information. Additional experiments on CIFAR-10 10 image classification using ResNet18 are available in App. G.I.
Our method works in the heterogeneous data setting as well, although O Ge
term is added to the error bounds
VMT
(in the convex and nonconvex cases), where { 2 0 quanti- fies the heterogeneity [+)) - { < 52, Vx E Idd Please refer to App. F.4 for the full analysis. Moreover, since our MLMC compression method produces unbiased gradi- ent estimates, it can be seamlessly incorporated into more so- phisticated optimization templates such MARINA (Gor- bunov et al., 2021) or DASHA (Tyurin & Richtárík, 2023), which would fully mitigate the heterogeneity term.
5.2. Experiments with Bit-Wise Quantization
We evaluated our nonadaptive MCCoooomprsssoon method (Alg. 2) with bit-wise quantization compressors on image classification tasks using the ResNet18 architecture and the CIFAR-10 dataset. We compare the communication efficiency of our method to biased 2-hit quantization, un- biased 2-bit QSGD (Alistarh et al., 2017), for the same compression level, and uncompressed SGD as a baseline. We present the results in Figure 3. These results show that also in the case of bit-wise compressors, our method enjoys significant advantage over the others in terms of commu- nication efficiency, convergence rate, and final test accuracy. Additional experiments evaluating RTN compressors on BERT GLUE SST2 finetuning are available in App. G.2.
5. Experiments
We present several deep learning experiments involving fine- tuning BERT (Devlin et al., 2018) on GLUE SST-2 (Wang al., 2018) and CIFAR-10 (Krizhevsky, 2009) image classi- fication using R (He et al., 2016). We evaluated the performance of our MLMC-based compressors in compari- son to biased and unbiased compressors. Our experiments were implemented using Py PoTch and executed on NVIDIA GeForce RTX 4090 GPUs.
8

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
MPC
Teal
PJN:
P.M.
MUNS
Sext
56
24-
550
520
MPF
PLN
P.M.
MUNC
20
56
24-
500
#Golt Carmunieated
14
9-bbtt
140
520
146
240
MPC
Tac
Tea.
40
160
200
146
20
140
MFC Tec
02 kmn
1911 K0TM
1.
25
48
180
220
146
20
Figure 1. Finetuning BERT on GLUE SST2 communication effi- ciency comparison of Adaptive MLMC-Top Top-k (Alg. 3). Top-k, EF21-SGDM, Rand-k, and uncompressed SGD for sparsification levels m0.01m, 0.05m, 0.1n, 0.5m).
Figure 2. Finetuning BERT on GLUE SST2 iteration efficiency comparison the Adaptive MLMC-Top-k (Alg. 3), Top-k, EF21- SGDM, Rand-k, and uncompressed SGD for sparsification levels E (0.01., 0.05n, 0.1m, 0.5m), batch size of 16 samples, averaged over 5 different seeds.
4,32 machines, and a batch size of 16 samples, averaged over 5 different seeds.
4, 32 machines, and a
6. Conclusions
g
We presented a novel method that bridges the gap between unbiased and biased compression approaches typically used to overcome communication overhead in distributed learn- ing settings. MLMC serves at the heart our method and facilitates the transduction of bias into variance, combin- ing the strengths of both worlds: the superior empirical performance of biased methods and the strong theoretical guarantees of unbiased techniques. We validated our algo- rithms on deep learning tasks showcasing their empirical efficiency compared existing methods.
PANC
24
20117
20003 #0003
GOOCE
500CE
Figure 3. CIFAR-10 image classification using ResNet18, commu- nication efficiency comparison of our Fixed-Point-basse MLMC compression method (Alg. 2), 2-bit Fixed-Poimt quantization, 2-bit QSGD, and uncompressed SGD, size of 128 and for M 32 machines and a hatch size of 64, averaged over different seeds.
= machines and a batch
Acknowledgments
Impact Statement
This research was partially supported by Israel PBC-VATAT, by the Technion Artificial Intelligent Hub (Tech.AI), and by the Israel Science Foundation (grant No. 3109/24). The second author would like to thank VATAT (through the Israel Council for Higher Education) for supporting this research.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here.

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
References
Dorfman, R., Yehya, N., and Levy, K. Y. Dynamic byzantine-robust learning: adapting switching byzan- tine workers. In Proceedings of the 41st International Conference on Machine Learning, ICML'24, 2024.
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, sgd via gradient quan- tization and encoding. In Advances in Neural Information Processing Systems, volume 30, 2017.
M. Qsgd: Communication--fficee
Dryden, N., Moon, T., Jacobs, A.. and Van Essen, B. Communication quantization for data-parallel training of deep neural networks. In 2016 2nd Workshop on Machine Learning in HPC Environments (MLHPC), 2016.
Bernstein, J., Wang, Y.-X., Azizzadeneshelli, K., and Anand- kumar, A. signsgd: compressed optimisation for non- convex problems. In International Conference on Ma- chine Learning, 2018.
Fatkhullin, I,, Tyurin, A., and Richtárik, P. Momentum provably improves error feedback! In Proceedings of the 37th International Conference on Neural Information Prucessing Systems, NIPS '23, 2023.
Beznosikov, A., Horvath, S.. Richtárik, P., and Safaryan, M. On biased compression for distributed learning. J. Mach. Learn. Res., 24:276:1-276:50 2020.
Ghadimi, S. and Lan, G. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 23:2341-23666 2013.
Chmiel, B., Ben-UUri,U L., Shkolnik, M., Hoffer, E., Banner, R., and Soudry, D. Neural gradients are near near-lognormal improved quantized and sparse training. In International Conference on Learning Representations, 2021.
Giles, M. B. Multilevel monte carlo methods. Acta Numer- ica, 24:259 328, 2013.
Condat, I.,, Yi, K., and Richtarik, P. Ef-bv: unified the- ory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed opti- mization. In Advances Neural Information Processing Systems, volume 35, pp. 17501-17514, 2022.
Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In Teh, Y. W. and Titterington, M. (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 249 -566, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR.
Condat, L., Agarsky, I., Malinovsky, G., and Richtárik, P. Tamuna: Doubly accelerated distributed optimization with local training, compression, and partial participation. International Workshop Federated Learning in the Age of Foundation Models, NeurlPS, 2023.
Gorbunov, E., Kovalev, D., Makarenko, D., and Richtarik, P. Linearly converging error compensated sgd. In Advances in Neural Information Processing Systems, volume 33, 2020.
Dahan, T. and Levy, K. Y. SLowcalSGD Slow query points improve local-SGD for stochastic convex optimization. In The Thirtt-eighth Annual Conference on Neural Infor- mation Processing Systems, 2024.
pp.
Gorbunov, E., Burlachenko, K. P., Li, Z., and Richtarik, P. Marina: Faster non-convex distributed learning with compression. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pp. 3788-3798. PMLR, 2021.
Dean, J., Corrado, G. S., Monga, R., Chen, K., Devin, M., Le, Q V., Mao, M. Z., Ranzato, M., Senior, A. W., Tucker, P. A., Yang, K., and Ng, A. Large scale distributed deep networks. In Neural Information Processing Systems, 2012.
Gupta, K., Fournarakis, M.. Reisser, M., Louizos, C., and Nagel, M. Quantization robust federated learning for effi- cient inference on heterogeneous devices. Transactions Machine Learning Research, 2023. ISSN 2835-8856.
Dekel, O., Gilad-Bachrach, R., Shamir, O., and Xiao, L. Optimal distributed online prediction using mini-batches. JMLR, 13:165-202, January 2012. ISSN 1532-4435.
Han, P., Wang, S., and Leung, K. K. Adaptive gradient sparsification for efficient federated learning: An online learning approach. 2020 IEEE 40th International Con- ference on Distributed Computing Systems (ICDCS), pp. 300-310, 2020.
Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for lan- guage understanding. CoRR, abs/1810.04805, 2018
Dorfman, R., Vargaftik. S., Btn-k, Y., and Levy, K. Y. Docofl: downlink compression for cross-device feder- ated learning. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, 23, 2023.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), pp. 770-778, 2016.
10

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Horváth, S. and Richtárik, P. A better alternative error feedback for communication-effiicee. distributed learn- ing. ICLR, 2021.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Horváth, S., Ho, C.-Y,, Horváth, L., Sahu, A. N., Canini, M., and Richtárik, P. Natural compression for distributed deep learning. In 3rd Annual Conference on Mathematical and Scientific Machine Learnings, 2022.
Lin, Y., Han, S., Mao, H., Wang. Y., and Dally, B. Deep gra- dient compression: Reducing the communication band- width for distributed training. In International Conference on Learning Representations, 2018.
Horváth, S., Kovalev, D., Mishchenko, K., Stich, S., and Richtárik, P. Stochastic distributed learning with gradient quantization and variance reduction, 2019. URL https: / www.ii.orgg........o..ooo..o..oa abs/ 1904. 05115.
Micikevicius, P., Narang, S., Alben, J., Diamos, G., Elsen, E., Garcia, D., Ginsburg, B., Houston, M., Kuchaiev, O., Venkatesh, G., and Wu, H. Mixed precision training. In International Conference on Learning Representations, 2018.
Jain, P., Netrapalli, P., Kakade, S. M., Kidambi, R., and Sidford, A. Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. JMLR, (8((1)8258-88) 8299, 2017. ISSN 1532-4435.
Mishchenko, K., Malinovsky, G., Stich, S., and Richtárik, P. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! ICMI., 2022.
Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik, P. Distributed learning with compressed gradient dif- ferences, 2023, URL httpt::/atxxii...to/./ http///axxvv.r././ /bbs/ 1901. 09269.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Nitin Bhagoji, A., Bonawitz, K., Charles, Z., Cor- mode, G.. Cummings, R., D' O'Oliveira, R. G. L., Eichner, H., EI Rouayheh, S., Evans, D., Gardner, J., Garrett, Z.,, Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M. Har- chaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Koneený, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D.. Song, W., Stich, S. U., Sun, Z., Suresh, A. T., Tramèr, E. Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q., Yu, F. X., Yu, H., and Zhao, S. Advances and open prob- lems in federated learning. Found. Trends Mach. Learn., 14(1-2), 2021. ISSN 1935-8237.
Recht, B., Ré, C., Wright,, S. J., and Niu, F. Hogwild: A lock- free approach to parallelizing stochastic gradient descent. In Neural Information Processing Systems, 2011.
Richtárik, P., Sokolov, I., and Fatkhullin, Ef21: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems, 2021.
Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. 1-bit stochas- tic gradient descent and its application to data-pat data-parallel distributed training of speech dnns. In Interspeech, 2014.
Shi, S., Chu, X., Cheung, K. C., and See, S. Understanding top-k sparsification in distributed deep learning, 2019.
Karimireddy, S. P., Rebjock, Q., Stich, S. U., and Jaggi, M. Error feedback fixes signsgd and other gradient com- pression schemes. International Conference Machine Learning, 2019.
Stich, S. U. Local SGD converges fast and communicates little. In International Conference Learning Represen- tations, 2019.
Koloskova, A., Stich, S., and Jaggi, M. Decentralized stochastic optimization and gossip algorithms with com- pressed communication. In Chaudhuri, K. and Salakhut- dinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Pro- ceedings of Machine Learning Research, pp. 3478-3487. PMLR, 09 -15 Jun 2019.
Stich, S. U., Cordonnier, J.-B., and Jaggi, M. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, volume 31, 2018
Tyurin, A. and Richtárik, P. DASHA: Distributed noncon- vex optimization with communication compression and optimal oracle complexity. In The Eleventh International Conference on Learning Representations, 2023.
Konecný, J., McMahan, H. B., Ramage, D., and Richtárik, P. Federated optimization: Distributed machine learning for on-device intelligence. ArXiv, abs/1610.02527, 2016.
Tyurin, A., Pozzi, M., Ili,, I., and Richtárik, P. Shadowheart SGD: distributed asynchronous SGD with optimal time complexity under arbitrary computation and communica- tion heterogeneity. In Advances in Neural Information Processing Systems, 2024.
Konečný, J., McMahan, H. B., Yu, F., Suresh, A. T., Ba- con, D., and Richtárik, P. Federated learning: Strategies for improving communication efficiency, 2018

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S. R. GLUE: A multi-task benchmark and anal- ysis platform for natural language understanding. CoRR, abs/1804.07461, 2018.
Wang, J., Charles, Z., Xu, Z., Joshi, G., McMahan, H. B., y Arcas, B. A., Al-Shedivat, M., Andrew, G., Avestimehr,
S., Daly, K., Data, D., Diggavi, S., Eichner, H., Gadhikar,
A., Garrett, Z., Girgis, A. M., Hanzely, F., Hard, A., He,
C., Horvath, S., Huo, Z., Ingerman, A., Jaggi, M., Javidi,
T., Kairouz, P. Kale, S., Karimireddy, P., Konecny, J., Koyejo, S., Li, T., Liu, L., Mohri, M., Qi. H., Reddi, J., Richtarik, P. Singhal, K., Smith, V. Soltanolkotabi, M., Song, W., Suresh, A. T. Stich,, S. U., Talwalkar, A., Wang. H., Woodworth, B., Wu, S., Yu, F. X., Yuan, H., Zaheer, M., Zhang, M., Zhang, T., Zheng, C., Zhu, C., and Zhu, W. A field guide to federated optimization, 2021. URL ht attps:// / /arxivvv.. org/ abs/ 019777
06917.
12

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
A. Proof of Lemma 3.2
Lemma 3.2 For any multilevel compressor C', [L], any non-zero level probabilities H- the MLMC gradient x
estimator It.i & Pi + (g -',²²) is conditionally unbiased estimate of the true gradient at step t, Vf()),) [V),vie E [M]. Namely: [[] = V f((z)).
Proof.
E Elgr, [xc]]
Esp'' s. D. + p (oh. )
(12)
- DD BBnng bb, + p (oh. - , " | x.l
(13)
- E Σ p' + 7 +1 (ri. st. [raa
1
(14)
Es lo.. E(oi+ -
(15)
1=1
EaLAnD D, [ore]
(16)
EN V (
(17)
Vf(x))
(18)
where transition (1) since W// ) is probability distribution, i.e., Σte 1. (2) follows since by the definition of
multilevel compressors in 3.1 where the highest level L corresponds to no compression (e.g., top-k with k = d).
B. Analysis of the Floating-Point based MLMC compressor
Given an element of the gradient denoted by e, can be represented a 64-bit floating-poing binary number. The floating-pon point number consists of three parts the Sign denoted by S, the Exponent denoted by E and the Mantissa which is binary number with digits {m, 152 The entry can be written as follows:
e (-1)52B-1023
1 Σ m
(19)
The Floating-Poin Point Compressor (e() truncates the sum to elements, which implies that the resolution will be up to 2F-10232 and the Compressor's ' parameter (which determines the extent of compression) ranges between to 52. Since the Exponent = [co] + 1023, the Floating-Pois biased compressor satisfies Eq. (4) with 2-
We apply the MLMC scheme with the Floating- Compressor and thus only need transmit the residual gi,- 9 The residual has the same Exponent and Sign bits the original entry, but contains only information bit of the mantissa for every element in the vector. This means that the Floating- -Pint MLMC compressor needs to only transmit 13d + loga (52) bits instead of 64d bits, where the extra log, (52) bits are needed to transmit the sampled l. Furthermore, note that for d > those additional bits are negligible, implying x 64
T3 R x4.9 improvement Communication cost.
Similarly to the Fixed-Point case, the MLMC technique requires probability distribution to sample the I-compression parameter with the compressor. We would like to use the ideal distribution to minimize the variance introduced by the compression process. We formalize this in Lemma B.1.
Lemma B.1. The optimal probability distribution that minimizes the variance of the Floating- Point MLMC estimator is given by:
2-1
(20)
2 2-52
13

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Proof. The second moment of the Floating-Point MLMC compressor is given by:
1 gh. + p [oc. o
|1]
a1 E
(21)
where II-II is the 1z-norm. Since this compressor operates in an element-wise manner, we consider the r-th element in Jr, which we denote by (r). Since ;r, for every r we obtain:
52
1-1 m, (r)
1 - p
-47
Σ
2 2 1023
1 Σ mr(r)2
--(r)) 1023
(1+
[
P
pf
/=1
(22)
52
202(
(mi(r)2-1)
(23)
p'
22 2026
(r)2
(24)
where (1) follows by the floating-pon priiigg--onttttoo representation of the (r), and (2) follows since every binary digit my satisfies mn = my (since m² can either be or 1). Now, similarly to the proof in appendix C, we wish to find the optimal probability distribution that minimizes the variance (note that the probability distribution should sum to 1). There are no additional assumptions on the binary number we wish to compress. Namely, for any my can be or and we would like to minimize the objective regardless of the values of m'. We formalize this using the following optimization problem:
2 2026
Σ p -1
p' arg min max Ti A20
Σ
2 21
+
(25)
By setting the gradients with respect p' and zero, we obtain the following:
(26)
( 1023
p
2
(27)
VA
These equations show that pt is proportional to 2-1 Thus, with proper normalization, by solving for À and extracting pl, we have:
2
D - 2-52
(28)
which concludes our proof.
Note that we can calculate the optimal variance of the MLMC estimator using the optimal probabilities we obtained above. We first calculate the second moment of some element the MLMC gradient estimate:
BIlē,, = E | -4 -
27
52 Σ
E()
52
-
my (r)2-22
22E( - -32 mm
mm)
(r)2
p
(29)
-00 - 2-22 (lee
52
(22
1
Σ
(mi(r)2-1]]
- (25())-1023)
(30)
1=1
- (20(3)))023) )
---52 (102
(31)
14

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Now, by summing the second moments of all the elements and using the unbiasedness of the MLMC estimator (Lemma 3.2).
obtain the compression variance component of the MLMC estimator's variance as follows (Note that the total variance is given by o comp + )²):
Elller, ||=] (B(ll +11) = Σ (r)) vf,
(32)
comp
p()) (100-102(11-- (1-2 ---52)(((r) - - -
(33)
C. Proof of Lemma 3.3
Lemma 3.3 The optimal probability distribution that minimizes the variance of the Fixed-Poing MLMC estimator is given by:
2
p
(34)
2-63
Proof. The second moment of the Fixed-Poin MLMC compressor given by:
1 (sh. ge.s E gh. + o
>1]
B aIll |
(35)
where ||-|I is the lz-norm. Since fixed-point compressors are element-wise, similarly to the foating-poinl compressor, we consider single entry of gr.i, which we denote by o Since ef, O, we have:
27
E
(ce,
@
Σ
Pl
1
Σ
b
Σ
0,2-5
(36)
p
1=1
1
(b.2
1
(37)
63
(2)
b, 21
(38)
where (1) follows using the binary representation of the normalized element. and (2) follows since every binary 6 = b (note that 6' can only be 0 or 1). We wish to find the optimal probability distribution that minimizes the variance (note no additional assumptions on the binary number we wish to
that the probability distribution should sum to 1). There compress. Namely, for any 1, by can be or 0, and we would like to minimize the objective regardless of the values of b/. We bound and formalize this in the following optimization problem:
63
63
arg min max
2 21
+
Σ
pl
(39)
(r' )
X20
by setting the gradients with respect to pt and À to zero, we obtain the following:
p
1
(40)
1=1
1
2-1
(41)
which imply that ze must be proportional to 2-1, and with with proper normalization (by solving for À and extracting p/), we have:
2
(42)
1 -
2-63 63
which concludes the proof.
15

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Note that calculate the variance of the MLMC estimator using the optimal probabilities that we obtained. We start by calculating the second moment of some entry in the MLMC gradient estimate vector St.s-
| (cl (
E &t 1 E
b,2 b 21
(1 2
Σ b,22 -1-2 (1-22-0)lec.l leaal
(43)
and by the unbiasedness of the MLMC estimate (Lemma 3.2), its compression variance is given by (note that the total variance is equal to ccomp + o²):
0e comp 1 ( (Elll,, II) (1 2 1----3)llue ||u,,,ll1 ||
(44)
D. Proof of Lemma 3.4
Lemma 3,4 Given any multilevel compressor C¹, the optimal probability distribution that minimizes the variance of MLMC estimator in iteration E [T'] and for machine i [M] is given by:
Pe.
(45)
Σi= A.
where A the &g norm the residual vector step i.e., 4/,5 |lgh.
Proof. The second moment of the MLMC-based compressor is given by:
gr ||21 [ E gf. + Ph,
(oh.s
g2.5 1-1)
(46)
Using our definition that gf, = 0 and the definition of A we obtain:
Elll 11 = E (pL,)2 (A,
(47)
amd by writing the expectation w.r.t pl explicitly, have:
Blll St.e 11=
Σ 1=1 Pr.
(48)
We wish to find the optimal probability distribution that minimizes the variance (note that the probability distribution should sum to 1). We formalize this into the following optimization problem:
L Etha-1)
Pl. arg min max
Σ ( (A
(49)
( X20
Pr.
By setting the gradients with respect to ph., and X to zero, we obtain the following:
Σ pL.=1 =1
(50)
p
A
(51)
VX
where +/x is the normalization factor of the probability distribution. With proper normalization (by solving for X and
extracting il the optimal probability distribution is given by:
A
P1 = Σ AV
(52)
which concludes the proof.
16

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
We calculate the variance of the MLMC estimate using the optimal probabilities we obtained. We start by writing the second moment of the MLMC gradient estimate Ir.::
E
00 +
(gi.i
gi.i
(53)
L Σ
A
(54)
f
Pt.
Thus, since the MLMC estimator unbiased (Lemma 3.2), the compression variance of the MLMC compressor is given by (note that the total variance is equal to ccoomp + o²):
i.cmp
Ell 12] (Bllla,.
A
(55)
This result is general and does not assume a specific multilevel compressor of the method.
Now, we apply those results to the case of s-Top--- k-based MLMC compressor and derive the second moment of the MLMC estimate. Here, note that the adaptive distortion bound in Eq. (10) to write A in terms of af, Recall that A is given by:
A = 9 ا
(56)
and since gh,, contains only subset of the elements of the original uncompressed stochastic gradient Ut.i (recall that s-top-k retains the non-overlapping segments of length s with the largest norms of the sorted stochastic gradient vector):
||.i.e ai, ||,,,
(57)
Similarly, we have:
(Al,)² = |1 - 11 || -
(58)
This is because the norm of the difference is equivalent toy the norm of the 1-th segemnt of length s the sorted stochastic gradient. Therefore, (A can be written as follows:
(A )2 |ol. "!. = || | (al,, a ||
(59)
Plugging into the optimal probabilities and the corresponding compression variance, we have:
1-1 ph. V
de. Vol. oi
( at. - at
1
Vot.
1- of compp
(60)
Ei=1 V at's -,,
1=1
E. Proof of Lemma 3.6
Lemma 3.6 Under Assumption 3.5 for sufficiently large r d, Alg, 3 with the s-top-k compressor, and the optimal probabilities in Lemma 3.4, guarantees O
variance of the MLMC estimator.
Proof. The compression variance of the MLMC estimator in the case of s-top-ki occoppp is derived in Appendix D and given by (see Eq. (55)):
L
2 A/, - ||
Σ
comm =
(61)
Under Assumption 3.5, the absolute value of the j-th element of the uncompressed stochastic gradient vr, is given by:
(v,,(i) = (0)le "
(62)
17

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Thus, the of the vector can be written
(v,; (0))e [v), (0).:(0))----- -
(63)
j=0
where the second equality follows by the sum of geometric series. Similarly, (4 is given by:
e e = (0) (0)00)00011) ( r.
-
Σ
(64)
ee
(=.-(1-)
these results give rise to two regimes depending on the value rr, compared to d:
(1) r. d < 1: In this case, the exponential decay is slow, and the "tail" of the sorted vector entries is not negligible. Namely, if decay is very slow, the gradient vector entries would be nearly uniform. This is the worst-case scenario in which our MLMC compressor, rank-k; and top-k all have similar performance since: A R A R ~ A
(2) and d > 1: This is the more interesting case in which we expect our method to have an edge over the other. Accordingly, derive approximation for the variance under this regime. by plugging the expression of the A/, and ||,,,e1l into the expression for the variance (Eq. (55)), we have:
e (1 (1 - r
E rued
o.commp (0))
(65)
1-
1
2
(0))
6 6-
(66)
1 Tr.
Pr
L
2
1 1,eed
(0))
Σ
(1-)((11)
(67)
1 P6
e P1.i
1
Ptiss
4
aL
2
1 reed
(0)
(68)
8
1 E
1
Iudd
Turd
(0)]
(69)
4
r
1 - Tr,c
1
Tii
2
|
(70)
Tr
where in (1) we used the expression for the norm of the gradient. To approximate the variance, we use the fact that r d >> to approximate the exponents in the expression:
2.2 2
1 e Teai
1 1-e
Z.comp = =1lu,,112
1 - e ro
-
(71)
1 c
Pe,ss
2 ||
(72)
Recall that is hyperparameter that we can choose as we see fit, and specifically, we consider such that s Pr.i $ 1. This implies that the number of the elements we transmit is less or equal ra Thus, obtain the following
18

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
approximation to the variance:
- P
ccopp 2 ||2,,11?
(73)
- e- Sye
||ee,el?
Pt,i 8
(74)
(124 s)
|||e@el?
(75)
12,18
1
0
(76)
Tr,88
which concludes the proof.
19

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
F. Convergence and Parallelization
F.I Proof of Theorem 4.1
Proof. We assume the homogeneous data setting in which D, = DD and thus f((z) = f(x), Vi. We analyze the convex and nonconvex cases separately.
Homogeneous Convex case.
Since our MLMC gradients, it in Alg. 2 and Alg. 3 are unbiased estimates of the true gradients, Vf())), for all i E (7)
and E [M] (see Lemma 3.2), the following bound holds for S 21. (see, e.g., Appendix A.1 in Dorfman et al. (2024)):
1 T
D
B[f(xr) - f(x))) S
Blf f(x")) v
EV2
(77)
2n T
Ei + where Zy= = + the variance of the MLMC gradients. Let us now consider the variance term, V22. We have:
= arg min, f(z). D = - and V22 = Billa
(xxe)) |xe]. Note that in this case V??
-
V22 = Elll: (1=)))l [xr]]
(78)
1
M Blllr,.
(xx))l [x:+]
(79)
M
2
[B[llr. u..ll [ane] + Elllv (xx0))1 lord)
(80)
M
2
[B[lãe. re.e11 [ooa] + x2)
(81)
M
2
(DPElllue [2d] + +0²)
(82)
M
(5)
4
(aP1Elllu, Vf(x))1 |x.] 2² [V 2=)+== +
20
(83)
M
M
(6)
2(20²
1)0²
+
4
Σ W² [[+((x)))1
(84)
M
M
(7) 2(20² + +)0²
8 L
+
M (f(xt) - f(x"))
(85)
M
where (1) follows since 9. 1/ EM Dt.; and the data samples are i.i.d, (2) and (5) since ||a + b1| < 2 ||a|| + 2 |bb|², Va,b E IRd, (3) and (6) by Assumption 2.2, (4) by Eq. (3) since our MLMC compressor is unbiased (see Lemma 3.2),
and (7) by Lemma F.1 since f is L-smooth by Assumption 2.1. Now, plugging this result back into Eq. (77) yields:
Elf(Er) - f(=)((())]
Σ Elf(x:) -f(x=)
T
-
D2
+
n
T
EV2
(86)
T
2nT
T
D2
2(222 + 1)02
1.
T
<
+
+ 11
E(f(x)) f(x")
(87)
2nT
M
MT
Choosing <
M 16247 and rearranging, we have:
1
D2
4(200 1)o²
+ 1
(88)
T
n/T
M
20

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Thus, for S min
DVM
we have:
2L 16
20
T =
2D
16
20 22 + +1D
- -((()))((x()))))
T (E((()))((x')>
Σ
+
(89)
T
MT
VMT
Homogeneous Nonconvex case. The proof here follows very similarly to the one the convex case. Here, similarly, we use the following bound, which holds for S 7. (see Appendix A.2 (Dorfman et al., 2023)):
T
24
nL
T
EV?
(90)
Tn
T
where A1 = f(x1) - f(x") and V??
Elll: fx(t))) |.z]] Plugging in the expression for V,2 Eq. (84) yields:
T E (
24
2(203 + +
4 L
1 MT
E [V
(91)
Tn
Choosing
M 7
and rearranging, we have:
4
1(2 + 1)o2L
(92)
T
Tn
M
Thus, for < min
M L
M
we have:
I
ov (202+1)ET
T
4
32 32 I
40 /2222222222 + 1)L
+
+
(93)
T
T
MT
VMT
F.2 Self-bounding Property of Smooth Functions
Lemma F.I. A function IRd TK. that is L-smooth (see Assumption 2.1) satisfies the following, for any x E IRd:
< < =
(94)
where arg min, f(x).
Proof. Note that f(x*) I f(x),, for any x' E Rd, by definition of x". Thus we have, for x' = Vf())
f(x") S f x Vf(x))
(95)
L
1 < ((x)) |V/(())
L
2 12 IV
(96)
where (1) follows by the smoothness of Rearranging yields:
|Vf(()] < 2L(f())-((e))
(97)
21

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
E33 Parallelization Guarantees
Our method, formalized in Alg. (nonadaptive) and Alg. 3 (adaptive) produces unbiased gradient estimates. Therefore, the error bound of our method is very similar to that of Alg. (data-parallel SGD). concretely, Alg. 2-3 guarantee the following error bounds in the convex and nonconvex cases, and in the homogeneous setting, respectively (Theorem 4.1):
D
D
(Ø + 1))DD
-(z)))
(98)
T
MT
VMT
T T
ALL
APALL
(i+ 1)ovL
(99)
T
MT
VMT
Note that the middle terms are asymptotically negligible, and therefore these bounds are asymptotically similar to the bounds guaranteed by Alg. 1, i.e.:
o c VMT
(100)
albeit with the an increased variance (4² + 1)0r (that depends on the baseline compression method we use, e.g., top-k or fixed-point compression) instead of a. Note that depends on the compressor and therefore on the compression coefficient a. Please refer to Appendices B, D, E, for exact calculations for certain examples. Note that the same asymptotic bound holds for the heterogeneous case, with the heterogeneity bound & added a.
In contrast, biased compression methods utilize error correction mechanism to account for the bias. While these achieve impressive results, additional terms are added to the error bounds due to the bias of the gradients). Specifically, EF21-SGDM (Fatkhullin et al., 2023) guarantees the following bound (Corollary 3 in Fatkhullin et al. (2023), nonconvex case):
Lo A. + (
A (ATT) 1/233// VMT
E BlV)(=)) o
(101)
Let us consider our bounds in Eq. (98)-199). Note that asymptotically, the third term is dominant. Therefore, M can be as large o(T), or equivalently o( o(VN), N). where N is the size of the whole dataset, without degradation in performance. Moreover, these bounds can be written in terms of the size of the dataset, N, since T N/M (N points split on M machines). Thus, asymptotically, performance starts to degrade when (neglecting constants other than and M (which depends on 7)):
1 - MT T
(102)
Now, similarly considering the parallelization limit of the bound of EF21-SGDM in Eq. (101), and note that the second term is always more dominant than the first, asymptotic performance starts to degrade when:
-
M TT
M
N1/3
(103)
VMT T3/1
which implies a parallelization limit of up ol (V).) or equivalently ((N133), without degradation in performance. This shows that in the regime of massive parallelization, i.e., when M is very large. method enables better (more) parallelization without a degradation in performance. Interestingly, when M is small, EF21-SGDM might have slight edge, as the dominant terms are VMT bias into variance, increasing it slightly. However, our experimental results show that our method maintains its edge over EF21-SGDM even when M is very small.
a for EF21-SGDM and (a (1*+1)a for our method, since MLMC methods tranduce
VMTT
F.4. Extension to the Heterogeneous Case
Our method can be naturally extended to the heterogencous case in which each machine samples points from a different distribution. That is, each machine E [M] can sample i.i.d data from some data distribution D. We assume that the heterogencity is bounded, namely there exists & 2 such that, Va e Rd:
M
vf()) 5
(104)
M
22

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Under this assumption, our method guarantees the bounds formalized in Theorem F.2 in the convex and nonconvex cases.
Theorem F.2. Under Assumptions 2.1-2.2, and the bounded heterogeneiry assumption in Eq. (104), Alg. 2 and Alg. 3 guarantee the following error bounds in the heterogeneous convex and nonconvex cases, rexpectively:
DOL
W 2( + oD VMT
f(=)))
MT
VMT
A
WA
a(0 +(v+ oVL
|| E
+
T
MT
VMT
VMT
Proof. Heterogeneous Convex Case.
Similarly to the homogeneous case, since the MLMC gradients, Jr.s used in Alg. 2-3 are unbiased estimators of the true machine-spece gradients, namely Elgr, [xr]] fi(x)), Vt e [T], Vi e [M], we have the following bound the convex case, for 7) S 2T, ((Dorfman al., 2024)):
T Blf(x,) f(x*)] -
D2
T
Bff(at) f(x")1 S T
+
EV?
(105)
2n/
T
1=1
where ör = ΣE x² = argmin, f(x). D = ||.1 - x= and V22 Bilg. - vf(xx)]]
[zz]. We now consider the
term V??:
V22 = Elll 1211)11(11111
(106)
M
=
E
(e.s V
(107)
M
1=1
Blller,: vf((x=))11 [xc]
(108)
M2
2
Billgr. v2,1l [xc] + -[]l,,- [mr]
(109)
M
M
Billg. - 12 [xe] + 0²)
(110)
M
M
Σ
[''Ellu,. [xe] + +o2)
(111)
M
1-1
662
202
Bllluz,
vf((z)))1 1=( [ vf(ai)1 (Vf())))1)
(112)
M
M
(0) 2(3 + 1)02
G:ogg2
6
M Σ
[V
(113)
M
M
IA3
2(3 + 1)0²
126 L
(f(z:) f(x)))
(114)
M
M
M
where (1) follows since ÿr = 17 En It.; and the data samples are i.i.d, (2) since ||a + b11 < 2 ||aa|| 2 +2 ||b1 Va, E Rdd (3) by Assumption 2.2, (4) by Eq. (3) since our MLMC compressor is unbiased (see Lemma 3.2), (5) since ||a b +cl
3(||a| []b]]] + [] Va, b, c E Rd, (6) by Assumptions 2.2 and Eq. (104), and (7) by Lemma E.1 since I-smooth by
23

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Assumption 2.1. plugging this result back into Eq. (105) yields:
Bff f(x')()))))))
T
(lf(r))
f((x))]]
D2
!
EV?
(115)
T
21j
T
D²
2(302 1)o²
6
1262
T
1 2nH
+
+1
+ 1|
Σ
Bif(z)) - f(x)))
(116)
M
M
MT
Choosing
M 24247
and rearranging, have:
T T -
D2
4(30² + 1)o² + 1202
- f(x")] I
1/[ +1
(117)
M
Thus, for S min
1
M 16
DVM
we have:
21
v +332+1100=200 122
T
2D
16 D
V4(322 + 1)0² 12
E[f(2r) f(x))]
B[f(z,) f(x))]
(118)
MT
VMT
Therefore:
D T
D ((D
oD VMT
f(z))
(119)
MT
VMT
Note that this bound is consistent with its homogeneous counterpart when & = 0.
Heterogeneous Nonconvex Case.
The proof follows very similarly to the one for the convex case. Here, we have for rj S 1
(DDoffaan et al., 2024)):
T
24 Tn
nL T
T
EV?
(120)
where A = [(x1) - [(x)) and V/2 = Elllā: - vs(x))11 [ca)]-
Plugging in the expression for V?? in Eq. (113) yields:
1
2A
2(302 + +1002L
G02E2
2 T
T (()))()))))
<
+
E
(
(121)
Tn
M
M
MT
Choosing 17 S T
and rearranging, we have:
T
4A
(4(322 + 1)o² + 1262
E f(aa)
+
(122)
T
Tn
M
Thus, for n) S min
I, I
M
M
have:
T
4
480 A I
+ 4V + 1)02 + 32)
E
(123)
T
T
MT
VM
Therefore:
T EO
ALL +
SALL +(O+
oVL
Σ
(124)
MT VMT
VMT
Note that his bound consistent with its homogeneous counterpart when & 0.
24

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
G. Additional Experiments
G.I. Sparsification Compressors Evaluation on CIFAR-10 Image Classification Using ResNet18
We ran additional experiments comparing the performance of our MLMC-Top-k compression method (Alg. 3), Top-k, Rand-k; EF21-SGDM, and uncompressed SGD, on CIFAR- Image Classification using ResNet18.
Figure shows the test accuracy of the compared algorithms function of communication complexity (the number of transmitted bits), for M machines and batch size of 128 (top quartet) and M 32 machines and a batch size of 64 (bottom quartet), and for various levels of sparsification A: E {0.001, 0.005, 0.01, 0.05)m, where 1.1 x 10? is the number of model parameters. The results were averaged over 5 different seeds to mitigate randomness, We display these results as a function of the epoch (the number iterations) in Figure 5.
Figures 4-5 show that our method demonstrates an advantage over the others terms convergence speed and test accuracy.
G.2. RTN Compression Evaluation on BERT Finetuning on GLUE SST-2
We evaluate the performance of our comcCoooooosiinnn scheme on quantization based compressors. Specifically we consider Round-to-Neares (RTN) compression. Given a vector v, RTN compresses by defining quantization grid and rounding each element of the nearest integer on this grid. The spacing of this grid is controlled by the quantization step-size, 8', where defines the quantization level (a larger corresponds to finer quantization). Specifically, given vector its RTN-compression (of level !) is given by
(urN(U) = 8 clip(round(r/08). -c,c),
(125)
where the division, rounding, and clipping are done in an element-wise manner, and "round" rounds each element its nearest integer the grid defined by 8'
2c
We evaluated our Adaptive MLMC- compeesonnns method (Alg. 3) with the RTN compressor as baseline (which we term MLMC-RTNN, and compared it to regular RTN compression (without MLMC) with / E {2, 4, 8, 16). and to uncompressed and averaged over 5 different seeds to mitigate
SGD, for M = 4 and M 32 machines. We used a batch size randomness. We present the results in Figure 6. Note that our method enjoys significant advantage in communication efficiency compared to the others in this case as well. Interestingly, the performance of all methods in terms of iteration efficiency is very similar, with SGD having slight advantage over the others.
25

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
70
00
60
40
40
40
10
MUMC
Topk
Topk
20
RandK
RandK
EF21
BF21-SGDM
10
Mc4, km
SGD
10
k= 005n
SGD
10000
20000
30503
40000
50000
50000
100000
150000
200000
250000
#Gbit Communicated
#Gbit Communicated
60
70
30
10
40
30
Tapk
Topk
EF21 SCDM
20
EF21-SGDM
10
10
1000.0
200000
50,000
400003
500000
2.0
Communicated
#Gbit Communicated
1e6
10
50
MUMC
30
MLMC
RandK
20
RandK
EF21-5GDM
EF21-5GDM
M= 32, k=0.0011
SGD
M2 k 0=00005m
SGD
10000
29000
30000
40002
50000
100000
150000
200000
@bit Communicated
#bit Communicated
70
70
(%6)
80
30
40
40
MUMC
MLMC
Tapk
Tapk
RandK
RandK
20
10
3232, K-0.0in
SGD
10
M2 k-0.05n
SGD
100000
200000
300000
400000
0.5
03
10
2.0
#Gitt Communicated
#Gbit Communicated
Figure 4. CIFAR-10 image classification using ResNet18, communication efficiency comparison of our MLMC-Top-k Compressor (Alg. Topk,, Rand-k, EF21-SGDM, uncompressed SGD, machines batch size of 128 and machines and batch size of 64, averaged over 5 different seeds.
26

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
70
00
60
40
40
40
30
MUMC
MLMC
Topk
Topk
20
RandK
RandK
EF21
10
k=0.0000000000 0.
5GD
10
k= 0055
SG0
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
Epochs
Epochs
70
30
40
30
Tapk
Topk
EF21 SCDM
20
EF21-SGDM
10
10
100
125
150
175
200
100
125
190
175
200
Epochs
Epochs
10
000
MUMC
30
MLMC
Topk
RandK
20
RandK
2-11-G
EF21-5GDM
M=32, k=0.001n
SGD
32 k= 0=00005m
SGD
0.0
5.0
7.5
10.0
12.5
15.0
17.5
0.0
7.5
10.0
12.5
15.0
37.5
Epochs
Epochs
70
803
50
40
40
MUMC
MLMC Tapk
Tapk
Randk
RandK
20
10
M=32, K= 01m
SGD
10
M432, K=0.05m
SGD
0.0
2.5
3.0
7.3
10.0
12.5
15.0
17.5
2.0
5.0
75
10.
12.5
15.0
175
Epochs
Epochs
Figure 5. CIFAR-10 image classification using ResNet18, iteration efficiency comparison of our MLMC- Top-- Compressor (Alg. Top- Rand-k, BF21-SGDM, and uncompressed SGD, for M machines batch 128 and machines batch size of 64, averaged over 5 different seeds.
27

---

A Multilevel Monte Carlo Approach for Mitigating Compression Bias in Distributed Learning
Test Accuracy (%)
Test Accuracy (%)
MLMC-RTN
MLMC-RTN
2-bits RTN
2-bits RTN
4-bits RTN
4-bits RTN
8-bits RTN
8-bits RTN
16-bits RTN
16-bits RTN
M
SGD
M=32
SGD
#Gbit Communicated
1e11
#Gbit Communicated
1e11
90
90
Test Accuracy (%)
Test Accuracy (%)
80
80
70
70
MLMC-RTN
MLMC-RTN
2-bits RTN
2-bits RTN
60
4-bits RTN 8 8-bits RTN 16-bits RTN
60
4-bits RTN
8-bits RTN
16-bits RTN
50
M=4
SGD
50
M=
25
50
75
100
125
150
175
25
50
75
100
125
150
175
Epoch
Epoch
Figure 6. Finetuning BERT on GLUE SST2 communication efficiency (top row) and iteration efficiency (bottom row) comparison of the Adaptive MLMC-RTN (Alg. 3), RTN with E 12, 4, 8, 16), and uncompressed SGD, and M -22 machines and batch size of 16 samples. The results are averaged over 5 different seeds.
28


Reviews:
[{"review_id": "NNa5IAQGl9", "reviewer": "Reviewer_FZxr", "summary": "This paper introduces a novel Multilevel Monte Carlo (MLMC) compression scheme that leverages biased compressors to construct statistically unbiased estimates. The proposed algorithm effectively bridges the gap between biased and unbiased methods, combining the strengths of both. The empirical results show that the proposed algorithm outperforms the baselines. Theoretical analysis show that the proposed algorithm can reduce the variance incurred by the compression.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation of our contributions, including the novelty of our MLMC compression scheme and the theoretical analysis. We address the concerns below and will incorporate these improvements into the final version.\n\n**1. Implementation**\n\nWe appreciate the reviewer’s suggestion to discuss real-world implementation. In our experiments, since hardware is limited, we used the \"Multiprocessing\" package to run multiple processes in parallel, each representing a different machine. This method accurately simulates a real-world parallel optimization scheme that runs on multiple machines. We will add this to the paper.\n\n**2. Computational Overhead**\n\nThat is a good point. However, the adaptive sampling step in Algorithm 3 does **not** introduce significant additional computational overhead. For example, in the case of top-$k$ or $s$-top-$k$, we only need to compute each $\\Delta_{t,i}^l$ (which is some norm) once per iteration, similar to what optimizers like AdaGrad already do when computing the full gradient norm. Furthermore, these norms are computed over **disjoint segments**, since $\\sqrt{\\Delta_{t,i}^l} = ||g_{t,i}^l - g_{t,i}^{l-1}||$, which is equivalent to the absolute value of the $l$-th largest element of $v_{t,i}$ (in top-$k$) or the norm of the segment of length $s$ with the $l$-th largest norm (in $s$-top-$k$).\nTherefore, the total computational cost is *identical* to that of computing the norm of the *full* gradient, as is done in existing adaptive methods like AdaGrad.\nA similar smart computation of the probabilities can be done for other compressors. For example, in bit-wise compressors, $g_{t,i}^l - g_{t,i}^{l-1}$ corresponds to the sign-bit and the $l$-th information bit.\n\nMoreover, the number of compression levels does not have to be linear in the dimension of the compressed entity, but could be logarithmic (which is less general, but still works). This is the \"classical\" case of MLMC [1] in which the quality of the \"levels\" (which is *inversely* correlated with the extent of compression in our case) increases exponentially and thus induces a logarithmic number of levels.\n\nAlso, the computational overhead (even when calculating multiple compressions) is usually negligible compared to the overhead introduced by communication, which is the main motivation behind this work and prior works. This has been discussed extensively in prior work [2,3].\n\n**2. Experiments**\n\nWe acknowledge that our current experiments are on modest-sized vision tasks, due to limited hardware. Although these are the standard benchmarks used in prior works, we agree that broader empirical validation is beneficial.\nWe ran additional experiments. The results are available at \"https://anonymous.4open.science/r/ICML2025MLMC-5346\". We recommend downloading the repository. It includes two folders, as we elaborate below:\n\n**BERT Top-k**:\n\nWe evaluated our adaptive MLMC method using Top-k compression on the SST-2 benchmark using BERT finetuning. We used the AdamW optimizer.\nThe folder includes 2 files showcasing the accuracy vs. #Gbit communicated, and accuracy vs. iteration (#steps), both for M=4 machines and for k={0.01n, 0.05n, 0.1n, 0.5n}.\nWe evaluated our MLMC method against EF21-SGDM, Top-k, Rand-k, and SGD (we keep this terminology, for clarity, with a slight abuse of notation, but note that the underlying optimizer for all is AdamW).\n\nAs is evident by these plots, our MLMC method enjoys the fastest convergence for the same \\#Gbit communicated, and it enjoys similar convergence to that of (uncompressed) SGD, and still performs better than other methods, for the same number of steps.\nThese results (in addition to the ones in the paper) prove a strong advantage and efficiency of our method compared to existing methods, both in communication efficiency and convergence rate, across vastly different tasks like CV and NLP.\n\n\n**RESNET CIFAR10 Top-k**:\n\nWe evaluated our adaptive MLMC method using Top-k compression on CIFAR-10 using ResNet-18 against EF21-SGDM, Top-k, Rand-k, and (uncompressed) SGD.\nThe folder includes 4 files showcasing the accuracy vs. #Gbit and accuracy vs. iteration (#steps), both for M=4 and M=32 machines and for k={0.001n, 0.005n, 0.01n, 0.05n}.\n\nOur method enjoys a significant advantage over comparable methods in terms of communication efficiency, convergence speed, and final accuracy.\nOur method's advantage grows with the number of machines. In the accuracy vs. iteration plots, uncompressed SGD eventually surpasses all methods, as expected, although our method is comparable when compression is not too extreme while other compression methods still experience performance degradation.\n\nThank you again for your constructive feedback!\n\n[1] Giles, \"Multilevel Monte Carlo methods\", 2013.\n\n[2] Konecny, \"Federated learning: Strategies for improving communication efficiency\", 2018.\n\n[3] Wang, \"A field guide to federated optimization\", 2021", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Most of the proposed methods make sense for the problem.\n\nFor the proposed methods:\n\nI think there should be some discussion about the implementation of the proposed algorithm in the real-world distributed environment. I understand that the hardware resources are limited and the experiments in this paper seems to be simulations. However, a discussion of the implementation is still necessary. I have some concern: for Algorithm 3, the adaptive probability distribution requires the calculation of compression of all levels, hence incurring heavy computation overhead if the number of levels is large.", "theoretical_claims": "I've skimmed the proofs and they seems correct to me.", "experimental_designs_or_analyses": "For the experiments, I have some concerns:\n\n1. The experiments are very small for distributed training. I would recommend cifar-100 or even larger such as imagenet.\n\n2. The experiments are limited to CV models. I would recommend to add some NLP (transformer) experiments.\n\n3. Although not covered by the theoretical analysis of convergence, I would like to see some experiments of how the proposed compressor works with Adam (actually AdamW) optimizer.\n\n4. All the experiments only show accuracy vs. #Gbit communicated. I strongly recommend to add plots of accuracy vs. steps, so that we could see the gap between the compressed methods and the optimal (final) accuracy of full-precision SGD.", "relation_to_broader_scientific_literature": "There is nothing related to the broader scientific literature.", "essential_references_not_discussed": "The references look good to me.", "other_strengths_and_weaknesses": "In overall, the idea seems very interesting and makes sense. My major concerns are about the experiments.", "other_comments_or_suggestions": "Please refer to the comments of the proposed method and experimental designs above.", "questions_for_authors": "Please refer to the comments of the proposed method and experimental designs above, and try to resolve my concerns.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hoEctKT9sv", "reviewer": "Reviewer_LHZE", "summary": "The article presents a new compression method that uses the MLMC algorithm to turn biased compressors into unbiased ones.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and detailed feedback. Below, we address each concern and clarify the relationship between our MLMC framework and IS.\n\n**1. MLMC vs. Importance Sampling**\n\nWe thank the reviewer for the insightful observation regarding the similarity between our MLMC construction and importance sampling (IS) in specific settings. That is an excellent point! We agree that in certain simple cases (bit-wise, Top-k) the MLMC estimator indeed reduces to an IS-like scheme, as you correctly pointed out. However, we respectfully argue that MLMC is not merely an instance of IS, but rather a significantly more general and natural framework for constructing unbiased estimators from biased compressors.\n\nIn fact, IS can be viewed as a special case of MLMC, where sampling is performed non-uniformly over coordinates, as you have stated. MLMC provides a systematic multilevel hierarchy over increasingly accurate (less compressed) estimators, and forms unbiased estimates by applying Monte Carlo sampling over the differences between successive levels. This telescoping structure is particularly well-suited to biased compressors, where compression is naturally available at varying levels of fidelity.\n\n**Importantly, MLMC offers several advantages beyond IS:**\n\n* It can be applied immediately to any sequence of biased compressors, with no need for any manual design of coordinate-level sampling probabilities or the structure of the communicated entity, which IS requires. For e.g. top-$k$, IS uses $1/p_l \\cdot g_l$ w.p. $p_l |g_l|$ to achieve the same result, and while it's straightforward in this case, it might not be as straightforward or even feasible for more complex compressors, as we elaborate below. Also, please note that this intuition regarding IS with top-$k$ was enabled by MLMC.\n\n* It is compatible with complex structured compressors that do not admit a coordinate-wise decomposition, and where IS is not naturally defined. For example, ECUQ [1] and Round-to-Nearest (RTN) [2,3] involve structured quantization (e.g., entropy constraints, grid-based rounding) for which the MLMC framework does not naturally decompose into an IS-like scheme. In such cases, it is unclear whether or how suitable IS can be defined, whereas MLMC applies seamlessly. MLMC enables these compressors to be used in a principled way to construct unbiased estimators, with automatic adaptation over compression levels.\n\n* From a practical perspective, MLMC is also more flexible and intuitive: one can simply define a sequence of biased compressors with increasing accuracy, and MLMC provides a plug-and-play mechanism for building an unbiased gradient estimate without needing to manually tune the probabilities or derive the communicated entity.\n\nWe will revise the manuscript to clarify these points and include a detailed discussion comparing MLMC and IS, including when they coincide and when MLMC provides a strictly richer modeling framework. We thank you again for raising this important point.\n\n**2. Experiments**\n\nWe acknowledge the reviewer’s concern regarding the ResNet18+CIFAR-10 setting. We chose this standard benchmark to align with prior works (e.g., EF21).\nRegarding accuracy, 90% requires use of Adam, LR scheduling, and more, which we did not employ as our focus was to isolate compression effects.\n\nWe fully agree that larger-scale settings will better demonstrate the advantages of our method, and we ran additional NLP experiments. The results are available at \"https://anonymous.4open.science/r/ICML2025MLMC-5346\".\n\n**BERT Top-k**:\n\n(See repository). We evaluated our adaptive MLMC method using Top-k compression on the SST-2 benchmark using BERT finetuning. We used the AdamW optimizer.\nThe folder includes 2 files showcasing the accuracy vs. \\#Gbit communicated, and accuracy vs. iteration (#steps), both for M=4 machines and for k={0.01n, 0.05n, 0.1n, 0.5n}.\nWe evaluated our MLMC method against EF21-SGDM, Top-k, Rand-k, and SGD (we keep this terminology, for clarity, with a slight abuse of notation, but note that the underlying optimizer for all is AdamW).\n\nAs is evident by these plots, our MLMC method enjoys the fastest convergence for the same #Gbit, and it enjoys similar convergence to that of (uncompressed) SGD, and still performs better than other methods, for the same number of steps.\nThese results (in addition to the ones in the paper) prove a strong advantage and efficiency of our method compared to existing methods **even for less aggressive compression**, both in communication efficiency and convergence rate, across different tasks like CV and NLP.\n\nThank you again for your constructive feedback!\n\n[1] Dorfman et al., “DoCoFL: Downlink Compression for Cross-Device Federated Learning,” ICML 2023.\n\n[2] Gupta et al., “Quantization Robust Federated Learning for Efficient Inference on Heterogeneous Devices,” TMLR 2017.\n\n[3] Dettmers et al., “GPT3.int8(): 8-bit Matrix Multiplication for Transformers at Scale,” NeurIPS 2022.", "claims_and_evidence": "The claims in the paper are correct and verified.", "methods_and_evaluation_criteria": "The proposed methods are proved under generally accepted assumptions on the target function. The algorithms are validated on the ResNEet+ Cifar10 problem, which is common.", "theoretical_claims": "The proofs and facts appear to be correct.  But I'm left unclear about one thing that seems like it should definitely be clarified, how do these approaches differ from importance sampling (see Sec 2.2 from Beznosikov et al)? It looks like, all these compressors can be reduced to a simpler form. Let me provide examples:\n\n__Bit-wise compressors:__ Here, the difference $g^l - g^{l-1}$ is used, and from the proposed compressor, it follows that $C(g) = 1/p^l (-1)^b_0 b_l 2^{-l}$, meaning that with probability $\\sim 2^{-l}$, the $l$-th bit, multiplied by $2^l$, is sent. Essentially, we assign weights from the simplex to all bits and sample them non-uniformly, but according to some prior distribution $p$. \n\n__TopK:__ Similarly, we send the coordinate $j$ with probability $\\sim |g_j|$, as follows from formula (11). It's not entirely clear why it's written so complicatedly, as it is essentially equivalent to: $p_j = |g_j| / \\| g \\|_1$. Again, we assign weights from the simplex to each coordinate and sample the coordinate according to $p$, resulting in a regular unbiased compressor.\nTherefore we use not a uniform distribution, but $p$. According to my calculations for such a compressor $\\omega = \\sum 1/p_j$. And I don't understand why it is a new approach.\n\nMaybe I'm wrong! I think it's important to explain!", "experimental_designs_or_analyses": "1) Basic ResNet18+CIFAR10 training gives more than 90 percent on test. Such experiments do not make sense, we have lost 20% of quality for all operators. It seems that if we use less aggressive compression, MLMC will lose to TopK.\n\n2) Please add to the comparison operators that compute the important sampling of coordinates. \n\n3) Still, ResNet+CIFAR10 although a classic production, are outdated. It would be interesting to see heavier tasks that require real distributed computation (resnet on cifar on a laptop learns in a few hours). I recommend for example BERT learning or Llama finetuning.", "relation_to_broader_scientific_literature": "The authors propose a new way of compression. It doesn't make a big breakthrough either way. Moreover, the applicability of these approaches and the big difference from the existing ones is questionable.", "essential_references_not_discussed": "All references necessary for understanding the article are provided.", "other_strengths_and_weaknesses": "I can't recommend for acceptance just yet.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MaaQO8dIt6", "reviewer": "Reviewer_yf8R", "summary": "The work proposed to consider Multilevel Monte Carlo (MLMC) in Distributed Learning to mitigate the problem with unbiased compressors analysis. Work introduced a novel Multilevel Monte Carlo (MLMC) compression scheme that leverages biased compressors to construct statistically unbiased estimates.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and encouraging feedback, and for pointing out areas where the theoretical analysis could be clarified. We respond to each concern below and will revise the paper accordingly.\n\n**1. Variance Analysis and Convergence Guarantee**\n\nWe appreciate your observation regarding the variance and convergence analysis.\n\nRegarding the variance, we presented the full derivations of the variance of the MLMC estimators as part of the calculation of the optimal probability distribution (which is optimized to minimize the variance) in Appendices B,C, and D (see Eq. (33, 44, 55)).\n\nFor a more practical example, in Lemma 3.6 we show that the variance of our MLMC estimator in the exponential distribution case (see Assumption 3.5) is given by $O(1/rs)$, where $r$ is the exponential decay rate of the vector's elements, which is better than the $O(d/s)$ variance of rand-$k$ when $1/r < d$ (i.e., when the decay rate is sufficient, which is the more interesting scenario).\nNote that when the vector is nearly uniform, we have $1/r \\approx d$ and the variances will be comparable in this case, as expected.\n\nRegarding convergence, please note that since our MLMC gradient estimators are unbiased by construction, convergence follows by the standard SGD convergence analysis, where the only difference is the additional variance introduced by the compression, as we state in lines 186-200. However, we agree that making these derivations explicit would strengthen the presentation, and we will add this to the paper as you suggested to make it clearer.\n\nSpecifically, the formal convergence theorem for Alg. 2 and Alg. 3 will hold under Assumptions 2.1 (smoothness) and 2.2 (bounded variance) and will guarantee similar error bounds (for the convex and nonconvex cases) as the ones in Theorem 2.1 and Eq. (2), only with $\\sigma_{comp}+\\sigma$ in place of $\\sigma$, where $\\sigma_{comp}$ depends on the compressor and thus on $\\alpha^l, l\\in[L]$ (see e.g. Eq. (60) in Appendix D).\n\nWe formalize the convergence theorem as follows.\n\nTheorem (convex case). Under Assumptions 2.1 (smoothness) and 2.2 (bounded variance), Alg. 2 (nonadaptive MLMC compression) guarantees the following error bound: $O(\\frac{1}{T}+\\frac{\\sigma_{comp}+\\sigma}{\\sqrt{MT}})$\n\nAlthough the proof follows very similarly to the SGD convergence theorem, we will formalize and add it to the paper for completeness. Similar Theorem and proof follow for the nonconvex case and we will add them as well.\n\n**2. Bounds dependence on compression constants**\n\nWe believe the reviewer’s concern refers to the apparent disappearance of level-specific compression constants (i.e., $\\alpha_{t,i}^l$) in the final rate. This is a good point. As we mentioned in the previous point, these constants come to light in the variance introduced by compression, i.e., in $\\sigma_{comp}$ (see e.g. Eq. (60) in Appendix D) which appears in the final convergence rate. We agree with the reviewer's suggestion to add this to the main paper to make it clearer, and we will incorporate this in the final version.\n\n**3. Minor Points**\n\nWe thank the reviewer for the helpful suggestions regarding notation, definitions, and related clarity issues.\nWe will revise the manuscript accordingly to improve clarity. \n\n* You are correct that the unbiasedness of our MLMC estimator depends on the highest level, $L$. Since we define $C^L(v):=v$, i.e., there is no compression, our MLMC method produces unbiased estimates of the true gradient.\n\n* Regarding the convergence rate of convex and non-convex SGD, we formalized the assumptions in our paper, but we will elaborate more on this and on the optimality of the bounds to improve clarity as you suggested.\n\n* Regarding eliminating humans from the loop in experiments, we ran additional NLP experiments using the AdamW optimizer, which employs an adaptive learning rate and alleviates the need for extensive learning rate tuning. The results are anonymously available at \"https://anonymous.4open.science/r/ICML2025MLMC-5346\".\n\nThank you again for your constructive feedback!", "claims_and_evidence": "The paper in general is written pretty well. \n\n**Major:**\n\n1. Unfortunately, I have concerns about the paper. The authors highlighted the possibility of using an interesting mechanism. However, the proof presented in Parallelization 3.4, the second paragraph, is not complete. The MLMC is unbiased and satisfies the Assumption hidden in Line 117, but nothing has been analyzed in terms of variance in terms of Assumption 2.2. For me, the proof is a bit artificial and the authors should elaborate way more on the Analysis.  Essentially, I don't like the fact that the original estimator is replaced by another and nothing has been said in terms of its variance.\n\n2. I'm pretty skeptical that if use L=2, and use for L=2 identical mapping and for L=1 TopK[k=1] compressor the \\alpa=k/d does not come into the rate (2) at all. However, the authors claim: \"Note that since our MLMC gradient estimates are unbiased, a similar error bound to Eq. (2) holds\"\n\n3. It's great that you have auxiliary Lemmas, but please formulate and prove the convergence theorem in detail (either for convex or non-convex case).\n\n**Minor:**\n\n4. Please use the notation in Line 135 to highlight the estimator of \\nabla f_i. You notation is slightly overload because you have both f_i(x) and f_i(x,z)\n\n5. Please elaborate more on the fact that rate (2) is optimal for convex setting in terms of rate for Stochastic  Gradient Descend.\n\n6. Please, if Assumption 3.2 is too restrictive, use \"Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M. Gower, and Peter Richtarik, Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization, arXiv:2006.11573, 2020\"\n\n7. Please elaborate more on the rate for non-convex cases. The rates 1/T to 1/sqrt{T} depend on assumptions and methods.\n\n8.  > This way, although the compressed gradients can be biased, their MLMC estimators are always unbiased.\n\nI can take take expectation of (5) and get line 187 right column. But the estimator is biased or not will -- depend on X^L.\n(please rephrase)\n\n9. Please be more concrete in Definition 3.1. and specify that C^i, i \\in [L], i \\ne L can be any compressor (1) or (2).\n\n10. Please add experiments with Convex Setting (Quadratics or Logistic Regression) by selecting step-size according to theory to demonstrate the correctness of your method.", "methods_and_evaluation_criteria": "In Applied Optimization sense, there are experiments wth training ResNet-18. \nIn a more restrictive setting with trying to eliminate humans from the loop during training, there are no such experiments.", "theoretical_claims": "Appendix A, D.", "experimental_designs_or_analyses": "Yes. In the Applied Optimization sense, methods sound good.", "relation_to_broader_scientific_literature": "The proposed methodology is interesting and has serious potential to revolutionize how we think about ways to mitigate problems with the analysis of biased compressors.", "essential_references_not_discussed": "All related works are properly introduced and utilized.", "other_strengths_and_weaknesses": "The paper is well written, but requires more elaborated work on Theory and minor polishing.", "other_comments_or_suggestions": "No.", "questions_for_authors": "See Claims And Evidence section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None."}}, {"review_id": "hevnEDsdP3", "reviewer": "Reviewer_Fo3R", "summary": "The paper introduces a Multilevel Monte Carlo compression scheme that leverages biased compressors to construct unbiased gradient estimates. The proposed approach aims to combine the empirical efficiency of biased compressors (Top-k, bitwise compression) with the theoretical guarantees of unbiased methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation of our paper and for the constructive feedback. Below, we address the questions raised:\n\n**1. Scaling with number of machines**\n\nYou are right that the performance gains from MLMC grow with the level of parallelization. When using only 4 machines, variance reduction is not as effective, so the gains are naturally smaller. However, as shown in our scalability plots (e.g., Figure 1 ($M=4$) compared to Figure 2 ($M=32$)), MLMC achieves significant speedups, smaller errors, and improved communication efficiency in large-scale distributed settings.\n\nThis is a key strength of our method. It retains the empirical efficiency of biased compressors while providing the unbiasedness and theoretical guarantees needed for scalable, stable learning in high-parallelism regimes. Moreover, higher parallelization induces a better variance reduction effect, which makes our MLMC estimator even better.\n\nWe will clarify this in the revised paper to better highlight the scaling advantages of MLMC.\n\n**2. Computational overhead**\n\nThat is a good point. The computational overhead of MLMC is comparable to standard methods such as Top-k and AdaGrad, and is often negligible relative to the overall training time. Similar works also focus less on the computational overhead since it is often negligible compared to the overhead introduced by the communication.\n\nSpecifically, using top-$k$, for example, incurs $O(d\\log(k))$ computational complexity per iteration and per machine while our adaptive MLMC method (Alg. 3) incurs $O(d\\log(d))$, which is a very small difference in practical scenarios.\n\nIn more detail, using top-$k$ requires finding the $k$ largest elements, which costs $O(d\\cdot\\log(k))$ in each iteration and for each machine.\nIn contrast, our adaptive MLMC method (Alg. 3) with top-$k$ requires sorting the vector first, costing $O(d\\cdot\\log(d))$, and computing the probabilities and constructing the MLMC estimator, which costs $O(d)$ in total (for computing the norm of the vector, similar to AdaGrad, and for picking the $l$-th largest element, which costs $O(1)$ since the vector is sorted).\nHowever, you are right that this is worth discussing to improve clarity, and we will add it to our paper.\n\n**3. Clarification on Figure 3**\n\nThank you for pointing this out. The results in Figure 3 correspond to Algorithm 2. We will clarify this in the figure caption and text to avoid confusion.\n\n**4. Experiments**\n\nWe ran new experiments, including NLP experiments using BERT on SST-2. These are anonymously available at \"https://anonymous.4open.science/r/ICML2025MLMC-5346\".\n\nThank you again for your constructive feedback!", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "satisfactory", "essential_references_not_discussed": "none", "other_strengths_and_weaknesses": "Strength:\n1. The paper is well-written and easy to follow.\n2. The paper introduces an innovative way to bridge biased and unbiased compression techniques.\n3. The authors provide thorough theoretical analysis of their method, including detailed proofs of unbiasedness and variance bounds.\n\nWeakness:\n3. The paper does not provide explicit per-iteration time cost comparisons.", "other_comments_or_suggestions": "none", "questions_for_authors": "1. As acknowledged in the paper, the MLMC approach trades bias for increased variance, which might impact performance in some scenarios, such as setup with a small number of machines. Is this the reason when with 4 machines, the performance gain is not that huge?\n3. Can the author provide per iteration time cost for different schemes?\n3. Is MLMC in Figure 3 based on Algorithm 2 or 3?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel Multilevel Monte Carlo (MLMC) compression scheme that leverages biased compressors to construct statistically unbiased estimates. The proposed algorithm effectively bridges the gap between biased and unbiased methods, combining the strengths of both. The empirical results show that the proposed algorithm outperforms the baselines. Theoretical analysis show that the proposed algorithm can reduce the variance incurred by the compression.

The paper received somewhat mixed reviews, with two reviewers leaning towards acceptance (scores 4 and 3), and two reviewers leaning toward rejection (scores 2 and 2). I have read the reviews, rebuttals, discussion, and skimmed through the paper, too. 

However, I propose acceptance - although I believe the paper can benefit from incorporating all meaningful feedback from the reviewers, which will require a major revision. I trust the authors will do so, thoroughly. I think the idea of the paper makes sense, but it is important to spend a good amount of space to show how the new approach gives rise to new compressors that were not considered in the literature before (and not merely show that the MLMC approach can lead to compressors that are not IS).

More remarks:
- I have seen a similar multilevel approach applied to SVRG before; this paper should be cited.
- I believe a more detail comparison to EF-BV is needed since this work considers a class of compressors that interpolates between biased and unbiased ones, which is similar in spirit to what the authors aim to do here with the MLMC approach). These compressors retain some strength of the biased counterparts, yet also partially benefit from unbiasedness. Can your approach recover these compressors? Can you obtain new compressors which do not belong to the EF-BV class? I think it is important to distinguish yourself from this work (although clearly your generation method is different, I am wondering about the end result).
- Yet another important missing citation is Horvath & Richtarik, A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning, arXiv:2006.11077. Just like your work, this paper tried to transform a biased compressor into an unbiased one, maintaining some benefits of the biased compressor, and yet benefiting from unbiasedness of the induced compressor. How do your compressors compare to these?
- Since you generate unbiased compressors in the end, you can use more powerful methods than EF, such as DIANA, ADIANA, Marina and Dasha. These methods rely on unbiased compressors and they are orders of magnitude better than EF21, for example, in theory, and reach the performance of biased compressors in practice (e.g., Marina with the PermK compressor does; see Szlendak et al, Permutation compressors for provably faster distributed nonconvex optimization, ICLR 2022).  How do your methods compare to, say, Marina with the PermK compressor?
- When you mention asynchronous training in the intro, it may be worthwhile mentioning the Shadowheart SGD method (Tyurin et al; Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity, NeurIPS 2024) - since this is the first parallel SGD method in terms of time complexity which caters to arbitrary computation and communication times. It utilizes unbiased compressors, and uses asynchronous communication. It was shown to be the optimal asynchronous method in terms of time complexity; and none of the methods you cite can beat it. It is relevant since your work is on the topic of communication compression. 
- When mentioning local updates in the intro, you may wish to mention the ProxSkip method of Mishchenko et al (ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally!, ICML 2022) -- since this is the first paper showing that local updates, when performed appropriately, lead to provable communication acceleration. Interestingly, further improvement in comm complexity can be obtained by designing appropriate communication compression strategies; and this was recently shown in TAMUNA (Condat et al, TAMUNA: Doubly Accelerated Distributed Optimization with Local Training, Compression, and Partial Participation). The first work showing such double acceleration was Condat et al, Provably doubly accelerated federated learning: the first theoretically successful combination of local training and compressed communication, arXiv:2210.13277.

AC
Decision: Accept (poster)