Towards Faster Decentralized Stochastic Optimization with Communication Compression
Authors: Rustem Islamov
Yuan Gao
Sebastian U Stich
Venue: ICLR 2025 Poster (2025)
Keywords: Optimization
Decentralized Learning
Federated Learning
Communication Compression
Primary area: optimization

Abstract: Communication efficiency has garnered significant attention as it is considered the main bottleneck for large-scale decentralized Machine Learning applications in distributed and federated settings. In this regime, clients are restricted to transmitting small amounts of compressed information to their neighbors over a communication graph. Numerous endeavors have been made to address this challenging problem by developing algorithms with compressed communication for decentralized non-convex optimization problems. Despite considerable efforts, current theoretical understandings of the problem are still very limited, and existing algorithms all suffer from various limitations. In particular, these algorithms typically rely on strong, and often infeasible assumptions such as bounded data heterogeneity or require large batch access while failing to achieve linear speedup with the number of clients. In this paper, we introduce MoTEF, a novel approach that integrates communication compression with $\textbf{Mo}$mentum $\textbf{T}$racking and $\textbf{E}$rror $\textbf{F}$eedback. MoTEF is the first algorithm to achieve an asymptotic rate matching that of distributed SGD under arbitrary data heterogeneity, hence resolving a long-standing theoretical obstacle in decentralized optimization with compressed communication. We provide numerical experiments to validate our theoretical findings and confirm the practical superiority of MoTEF.

Published as a conference paper at ICLR 2025
TOWARDS FASTER DECENTRALIZED STOCHASTIC OPTIMIZATION WITH COMMUNICATION COMPRESSION
Rustem Islamov Yuan 2. Sebastian U. Stich
Universität Basel, Universität des Saarlandes, SCISPA Helmholtz Center for Information Security rustem. asvamove e wnibas.......................a. ch, {yuan. gao, stich) @cispa.
ABSTRACT
Communication efficiency has garnered sigmificant attention as it considered the main bottleneck for large-scale decentralized Machine Learning applications in dis- tributed and federated settings. In this regime, clients are restricted to transmitting small amounts of compressed information to their neighbors over a communication graph. Numerous endeavors have been made to address this challenging problem by developing algorithms with compressed communication for decentralized non- convex optimization problems. Despite considerable efforts, current theoretical understandings of the problem are still very limited, and existing algorithms all suffer from various limitations. In particular, these algorithms typically rely on strong, and often infeasible assumptions such as bounded data heterogeneity or re- quire large batch access while failing to achieve linear speedup with the number of clients. this paper, we introduce MoTEF, a novel approach that integrates com- munication compression with Momentum Tracking and Error Feedback. MoTEF is the first algorithm to achieve an asymptotic rate matching that of distributed SGD under arbitrary data heterogeneity, hence resolving long-standing theoreti- cal obstacle in decentralized optimization with compressed communication. We provide numerical experiments validate theoretical findings and confirm the practical superiority of MoTEF.
INTRODUCTION
Decentralized machine learning approaches increasingly popular in numerous applications such as the internet-of-things (IoT) and networked autonomous systems (Marvasti et al., 2014 Savvzzii al. 2020), primarily due to their scalability larger datasets and systems, well their respect for data locality and privacy concerns, In this work, we focus on decentralized optimization techniques that operate without a central coordinator, relying solely on on-device computation and local communication with neighboring devices. This encompasses traditional scenarios like training Machine Learning models large data centers, as well as emerging applications where computations occur directly on devices. Such setting is preferred over centralized topology which often poses significant bottleneck on the central node in terms of communication latency, bandwidth, and fault tolerance.
Considering the enormous size of modern Machine Learning models, classic single-node training often impossible. Moreover, the training of large models requires huge amount of data that does not the memory of a single machine. Therefore, modern training techniques heavily rely on distributed computations
set of computation nodes/clients (Shoeybi al. 2019) Wang et al. 2020: Ramesh et al. 2021 2022). One of the instances of distributed training is Federated Learning (FL) (Konecný et 2016 Kairouz al. 2222] which has recently gathered a lot of attention. In this setting, clients, such as hospitals or owners of edge devices, collaboratively train model on their devices while retaining their data locally.
A key issues in distributed optimization is the communication bottleneck (Seide et al. 2014 Ström
2015) that limits the scaling properties of distributed deep learning training (Seide et al. 2014 Alistarh et al. 2017). One of the remedies to decrease communication expenses involves communication
Equual contribution.

---

Published as a conference paper at ICLR 2025
compression, where only quantized messages (with fewer bits) exchanged between clients using compression operators. When used appropriately, contractive compressors (see Definition T such as Top-K. are often empirically preferable. However, the naive application of contractive compression operators might lead to divergence (Beznosikov et al.) 2023). To make compression suitable for distributed training, the Error Feedback (EF) mechanism (Seide al., [014] Stich et al. 2018) is
widely used in practice. It plays a crucial role in achieving high compression ratios.
However, most of the works analyzed EF mechanism in the centralized setting (Stich & Karimireddy 2019 Gorbunov et al. 2020 Stich 2020). Recent research achievements (Gao et al. [024]] Patkhullin
ct al. 2024) demonstrate that this regime properly constructed EF mechanism can handle both client drift Mishhhenko et al. 2019 Karimireddy et al., (020b) and stochastic noise from the gradients, and
can achieve near-optimal convergence rates. the more challenging decentralized setting, a series of studies (Zhao et al. 2022 Yan et al.) 2023) introduced algorithms capable of effectively managing the drift but fail achieve linear acceleration parallel training, i.e. increasing the number of devices used for training does not lead to decrease in the training time. Yau & Wai (2022) partially solved this issue under stronger assumptions achieving linear speed-up using variance reduction, but with worse dependency on the variance of the noise
Designing a method that addresses client drift while preserving linear acceleration in decentralized training has been challenging due to the complex interplay between client drift, Error Feedback mechanism and the communication topology. In our study, we introduce MoTEF, a novel method that tackles these challenges concurrentyy. Our primary contributions can be outlined as follows.
We propose novel method MoTEF that incorporates momentum tracking with compression and Error Feedback, and provably works under standard assumptions (i) without imposing any data heterogeneity bounds, (ti) without any impractical assumptions such large batches, (1é1) with arbitrary contractive compressor, and (iv) achieves linear speed-up with the number of clients n. We provide convergence guarantees for the general class of non-convex functions, and for the structured class of non-convex functions satisfying the Polyak-t.ojasiewiee (PI.) condition.
We propose MOTEF-VR, a momentum-based STORM-type (Cutkosky & Orabona 2019) variance- reduced variant of our base method that improves further the asymptotic rate of convergence.
Finally, we provide an extensive numerical study of MoTEF demonstrating the superiority of the proposed method in practice and supporting theoretical claims.
1.1 RELATED WORKS
Decentralized optimization and gradient tracking. First works in the field studied gossip av- eraging procedures that are typically used to reach consensus (Kempe et al. 2003 Xiao & Boyd 2004 Nevertheless, direct use of gossip averaging might be sub-optimal convergence (Nedic & Ozdaglar, 2009). Gradient tracking (Qu & Li 2017 Nedic et al. 2017] Koloskova et al.) 2021) is one the most popular remedies to this issue. has been widely applied to obtain faster decentralized algorithms (Sun et al.) [2200] Xin et al., 2022: 2021 Li et al., 2022 Zhao jet al.) 2022). In this work, we follow a similar approach but perform a tracking step on momentum term instead of gradients. Takezawa et al. 22022) might be the first to analyze momentum tracking in decentralized optimization, but they do not consider communication compression.
often results in slow
Momentum in distributed training. Lately, the utilization of momentum (Polyak 1 1964) has attracted attention in distributed optimization. Several works empirically showed that momentum
can improve performance in distributed setting (Wang et al. 2019a| Karimireddy et al., 2020a Das
et al. 2022). Besides, it has recently been shown that the use of momentum improves convergence
guarantees Yau Wai 2022 Fatkhullin et al.) 2024 Cheng al., 2024, Huang et al.,
2024) fully
removing dependencies on data heterogeneity bounds. In this work, we follow this approach and apply the momentum technique to the more challenging decentralized setting.
Short history of Error Feedback. Initially, the Error Feedback mechanism was introduced as heuristic (Seide et al. 2014) and was subsequently analyzed within a simple single-node framework (Stich al. 2018 K Karimireddy al.) 2019). The first findings in the distributed context were
achieved under strong assumptions such as IID data distributions (Karimireddy et al. 2019) or
bounded gradients (Cordonnier) 2018 Alistarh et al. 2018 Koloskova et 2019 2020a). EF21
2

---

Published as a conference paper at ICLR 2025
(Richtárik et al. 2021) stands out the first algorithm proven to operate with any contractive compressors and under arbitrary heterogeneity, albeit failing to converge when clients are limited to using only stochastic gradients (Fatkhullin et al. 2024). Subsequently, EF21 was extended to diverse practical scenarios (Fatkhullin et al. (021) y and decentralized training (Zhao et al. 2022 improving the dependencies on some problem parameters. Recent advancements (Gao al.
2024
Fatkhullin et al. 2024) have demonstrated that a carefully designed EF mechanism (through the control of feedback signal strength or the use of momentum) results in nearly optimal convergence guarantees in a centralized setting.
Issues of Error Feedback in decentralized setting. Despite having been studied in the centralized setting extensively, EF-based algorithms in the decentralized regime still fail to achieve desirable properties.
Strong assumptions. Many earlier theoretical results for EF require strong assumptions, such as
either the bounded gradient assumption (Koloskova et al.) 2019 2020a) or global heterogeneity
bound (Lian et al. 2017 Tang et al., 2019: Lu & De Sa. [021]] Singh et al. (202T).
Mega batches. Convergence of BEER algorithm(Zhao et 2022) requires large batches that
can be costly or even infeasible in some applications, For example, in medical applications (Rieke
al.
2020) or Reinforcement Learning (Khodadadian et al., 2022] Jin al. [022]] Mitra et al.
2023
sampling large batches is often intractable. Moreover, it has been shown that training with
small
batch sizes improves generalization and convergence (Wilson & Martinez 2003 Keskar
et al.
2016; Sekhari et al. 2021).
Suboptimal rates. The stochastic term of several algorithms does not improve with n the number of clients (Zhao et al., 2022] Yan et al., 2023). while the opposite is often desirable, and can be achieved in the centralized training setting (Fatkhullin et al. 2024 Gao et al.) 2024). Other work achieves speed-up with n, but requires stronger smoothness assumptions and has a worse dependency on the noise variance (Yau & Wai (022). Moreover, (Koloskova et al. 2019 2020a) do not achieve standard (1/s²)) convergence rate in noiseless regime.
Necessity of unbiased compression. Finally, early works analyzed decentralized algorithms only for a more restricted class of unbiased compressors (Tang et al. 2018a 8a, Kovalev et al. 2021).
Huang & Pu (2023) modify any contractive compressor using an additional unbiased compressor following the results of (Horväth & Richtárik 2020). This approach enables the creation of a better sequence of gradient estimators, albeit with twice the per-iteration communication cost.
we provide a summary of known theoretical results in decentralized training with compression that are most relevant to our work. We highlight the main issues of existing algorithms.
In Table 1
2 PROBLEM SETUP
Formally, we consider the following optimization problem
min XER
= +
where n is the number of clients participating in the training, x are the parameters of a model, f fxx is the global objective, and (x) == EE,-D, (, &)] is the local objective over local dataset D, Throughout this work, we assume that the global function
bounded below by f > -00.
In the setting of decentralized communication, the clients are restricted to communicating with their neighbors only over a certain undirected communication graph ([m).. E). Each vertex [n] represents a client, and each edge in E represents communication link between clients. Besides, we assign a positive weight to W/y if there an edge (i, E F, and wi, = if (i, & E. Weights wij form a mixing matrix W E Raxn (sometimes also called gossip or interaction matrix). The mixing matrix W should satisfy the following standard assumption.
Assumption We assume that W E gaxa is symmetric (W WT) and doubly stochastic (W1 = 1, W = 1 1T) matrix with eigenvalues 1 = (>((W) > Aa (W) 2 ... 2 (W)). We denote the spectral gap of W as
p == 1 DaalaaWWll)) 10.
(2)
3

---

Published as a conference paper at ICLR 2025
Table 1: Summary of convergence guarantees for decentralized methods supporting contractive compressors. nCVX supports non-convex functions: PL = supports functions satisfying PL condition.
present the convergence in terms of E [ (Xous) )I [ I E² and E (X(ot) - l"] I e in PL regimes for specifically
chosen Xout. Here oe E [xx) ['] and are smoothness constants, P a spectral gap, and o² stochastic variance bound.
Asymptotic Complexity
Extra Assamptions?
Method
Large Batches?
nCVX
Pt.
Choco-SGD Koloskova et al. 2019
LF
Bounded Gradients [/x, ()l" s C2
X
X
BEER (Zhao et al 2022
LE" 8 p'o"p" ptz
Batch size of order o²
0 p"e"
CEDAS
LF
Additional Unbiased
(Huang & Pu. 2023
Compressor
DeepSqueeze [Tang et al. 2019
LE
Bounded Heterogeneity
X
n
Σ,
[V - ff(())] <
DoCoM Yau & Wai 2022
1
X
x
1
CDProxSGT Yan et al., 2023)
1,8
MoTEF [This work]
LF
LF
X
X
MoTEF-VR [This work]
The spectral gap typically used to measure the influence of network topology in the training (Aldous & Fill 2002 Nedić et al. 2018).
In our work, we consider algorithms combined with compressed communication. Formally, we analyze methods utilizing practically useful contractive compression operators.
Definition 1. We say that (possibly randomized) mapping C: TR + Rd is a contractive compression operator for some constant S it holds
E [[](()) (1-a)
(3)
One of the classic examples of compressors satisfying B Top-K (Stich et al.] 2018). It acts
on the input by preserving K largest by magnitude entries while zeroing the rest. The class of contractive compressors includes well-known sparsification Alistarh et al. (2018); Stich el. (2018) and quantization (Wen et al. 2017 Bernstein al.] 2018 Horváth et 2002)) operators. We refer to (Islamov et al.) 2021] Qian et al. 2021 Beznosikov et al. 2023 Safaryan et al. 2022 Islamov et al.
2023) for more examples of contractive compressors.
In decentralized training, typically, each client receives the messages from its neighbors and transfers back to them the aggregated information. We highlight that, contrary to many prior works, analysis supports an arbitrarily heterogeneous setting, i.e. it does not require any assumptions on the heterogeneity level, which means that local data distributions might be distant from each other. Next, we provide standard assumptions on the function class and noise model.
Assumption 2. We assume that each local local function f; is L-smooth, i.e. for all x, E IRd, and E [n] it holds
f - (. < L|x - yll. yll-
Next, we assume that each client has access to an unbiased gradient estimator with bounded variance. Assumption 3. We assume that we have access to gradient oracle g' (x): Rd - Rd for each local function f, such that for all x E Rd and E [n]] it holds
E [g(()))
fx(),,
[x) V (x) < <?
(5)
It is important to mention that mini-batches allowed well, effectively reducing the variance by the local batch size. Nevertheless, there is no requirement for any specific (minimal) batch size, and for simplicity, we consistently assume a batch size of one.
4

---

Published as a conference paper at ICLR 2025
Finally, consider the structural class of non-convex functions satisfying Polyak-Lofj Dolyak-Lojasiewicz condition (Polyak] 1963). This assumption one of the weakest conditions under which vanilla Gradient Descent converges linearly (Karimi et al. 2016).
Assumption 4. We assume that the global function f is for some μ > 0, ie. for all x E Rd it holds
|Vf(x)] (x(f(z)- ft).
(6)
Note that the PL condition is a relaxation of strong convexity, i.e. if strong convexity with parameter j implies j-PPt condition.
3 THE ALGORITTMM AND THEORETICAL ANALYSIS
In this section, we introduce our main algorithm MoTEF, summarized in Algorithm | MoTEF combines Momentum Tracking with Error Feedback tackle the three major challenges of decen- tralized optimization with compression at once: client drift, stochastic noise of the gradient, and compression bias. line 5 and line 10 we apply the EF-enhanced gossip step inspired by Zhao et al. (2022) and Koloskova et al. (2019) and in line we apply the Momentum Tracking mechanism, which combines the classical Gradient Tracking method with Polyak's 's momentum. We will show that MoTEF is the fisrt algorithm that achieves an optimal asymptotic rate matching that of distributed SGD without any additional, and possibly impractical, assumptions.
It is well-known in the literature that the asymptotic rate of SGD cannot be improved under the standard assumptions. There is long line of work, known as Variance Reduction, that attempts to accelerate SGD under the additional wwean-squared-smootnee
assumption (for which such acceleration is crucial) (Fang et al. 2018 Cutkosky & Orabona 2019, Tran-Dinh et al., 2022 Wang jet al. 20196; Xu & Xu 2022). To demonstrate the flexibility and effectiveness of approach MoTEF, we also present a momentum- based variance-reduced variant MoTEF-VR summarized in Algorithm
Next we present the theoretical analysis of MoTEF and MoTEF-VR.
3.1 NOTATION
Before going into details, we introduce a notation that we use throughout the paper. We stack the local parameters x stored at each clients into matrix X = |xi....,x;, Rdxi, and denote the average model x' == x where 1 is vector of ones. Other quantities are defined similarly. To track local gradients, we define VF(X') V f (x",, E dd Similarly we write ( as the collection of local stochastic gradients. Finally, C. (X) denotes the contractive compression operator C. applied column-wiss on a matrix X, i.e. C, (X) = ((,x)))..,,((xx. Rdxa.
paper.
3.2 CONVERGENCE OF MoTEF
Now are ready to present convergence guarantees for MoTEF. Below we summarize the conver- gence guarantees for Algorithm| in general non-convex and PL settings. Our analysis relies on the Lyapunov function of the form
b' F G + mz O + 24 + Sxz S + ep S2
eaz D1
(7)
where {cx (e are absolute constants defined in the appendix represents the sub-optimality function gap, and the error terms are defined as follows
(32
Fet = [[ - 1
G = [IV((X)) M'
T
[VF(X*)
M
22 = E
H'
1
x
2 = E
G
V'
S =
||X'
1
(8)
FF
2 = E
V
21
22 = E
TTo find a suitable choice of constants we Symbolic Math Toolbox in MATLAB Inc. be found at http://////oooooooooooooo.oeeeee
2023
Our code
cication
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 MoTEF
Algorithm 2 MoTEF-VR
1: Input: X I Go H V :7,7A,
Input: X x"1 G H. V ,,,,A,
2: Ca
2: Ca
3: for
t = 2,... do
for
1 = 1,,
4:
X =X * (W- - 1) - V
4:
X = =x +7 - -T) 1/Vi
5:
0 =Ca(X H
0 (x H
6:
H H' +
H H'+QQ
7:
M (1- -- XVF(X
M VF(X*1 _
8:
V G
+ 1-)( VF(X E
9:
Q = Ca(V++ G
V V*+ -W- (W-I) -I
10:
G G = G Q+1
10:
Q4+1 C. (V++1 G
11:
G G' + Q 2+1
Our theory relies on the descent of the Lyapunov function of introduced above. Lemma 1 (Descent of the Lyapunov function). Let Assumptions 2 and and holld Then there exist absolute constants Ciyy CXy CyN and v such that if we set stepsizes 7 C, exap"T c T such that the Lyapunov function o' decreases
T s a' G,
[[V)(())
-202 + + (3cap + coap? + sea e, nL
20
(9)
Using the above descent of the Lyapunov function, we demonstrate the convergence guarantees for MoTEF.
Theorem 1 (Convergence of MoTEF). Let Assumptions 2 and hold. Then there exist absolute constants Cyp Cx2 Cny and some T S such that if we set stepsizes 7 = Cy = cxap"
and choosing the initial batch size Binit 2 1F then after at most
T ==
0² net
+ a LF
(10)
app1zg3
where Nout is chosen uniformly random from ( 11, and O suppresses absolute constants.
iterations of Algorithm 1 it holds E (xxo(())) S S
Remark 2. Note that using large initial batch size Bist is not required for convergence of MoTEF. If we set Bua = 1, the above theorem still holds by replacing F by Φ
We observe that the use of momentum in MoTEF allows us to improve convergence guarantees BEER. Indeed, Algorithm 1arritthmmacchie achieves optimal asymptotic complexity with desirable linear speed-up with the number of clients n. Morcover, MoTEF provably converges for any batch size in contrast BEER.
Discussion of the convergence rate. In the stochastic regime (a² >> 0), we note that the asymp- totically dominating term is ((0²/net), which is independent of the spectral gap and compression rate and is optimal in all problem parameters (Arjevani et al. 2023). To the best of our knowledge, MoTEF is the first decentralized algorithm incorporating contractive compressors that achieves under Assumptions and 3 without data heterogeneity restrictions. In the deterministic regime 2a 0), the convergence rate becomes O()app)"). This optimal in and (Huang al. 2022) and sub-optimal in We would like to highlight that having sub-optimal dependency on well-known challenge in the theoretical analysis of the gradient tracking mechanism (Koloskova et al. 2021). Besides, the same sub-optimal 1/0² dependency is also observed in the analysis of BEER algorithm. It is an active research direction to either improve the convergence analysis of gradient tracking obtain better p dependence (Koloskova al.) 2021) to design more sophisticated tracking mechanisms that might achieve better rates (Di et al. 2022). Either way, involves significantly more complicated analyses and we defer these to future work. We also point
2
the spectral gap
that it is unclear whether the 3/p" dependence is inherent to the tracking mechanism or an artifact
This means the regime when

---

Published as a conference paper at ICLR 2025
of the analysis. In Section 4 we provide numerical evidence showing that MoTEF might be much less sensitive to p than the theoretical analysis suggests. A more detailed discussion of the results of previous works is deferred to Appendix A
Now we derive convergence guarantees of MoTEF for the class of functions satisfying Assumption 4
Theorem 2 (Convergence of MoTEF). Let Assumptions 2 too hold. Then there exist absolute constants Crys Ox2 Ca, and some T I such that if we set slepsizes 7 = Cy = exappT, Top", and choosing the initial batch size Binit 2
[==)) then after at most
La and O suppresses absolute constants and iterations of Algorithm / it holds TE [
T ==Ō -
Lo² +
(11)
paps
factors..
Remark 3. Note that using large initial batch size Butt is not required for convergence of MoTEF. If we set Buit = 1, the above theorem still holds by replacing F by 40, which is hidden in the logarithmic terms.
Contrary to BEER, we demonstrate that the asymptotic rate of MoTEF in the PL setting improves with and does not require large batches. To the best of our knowledge, MoTEF is the first decentralized algorithm that supports contractive compressors and achieves linear speed-up with n under Assumptions to Moreover, we highlight that in the noiseless regime MoTEF converges linearly as expected. Another momentum-basee algorithm DoCom was analyzed under more restricted Assumption only. Therefore, its applicability in this setting is not known. Besides, DoCoM achieves linear speed-up with n, but with sub-optimal dependency on the noise variance o².
3.3 CONVERGENCE OF MoTEF-VR
We demonstrated that MoTEF achieves an asymptotic complexity of distributed SGD under As- sumptions 2 and 3 and this result cannot be improved. However, if we consider strengthening Assumption 5 then further acceleration on the
of Assumption the mean-squared--soollie stochastic term might be achieved via variance reduction. We emphasize that Assumption [ is the standard assumption made for variance reduction, and is the key one for circumventing existing lower bounds on stochastic methods (Fang al. 2018) Cutkosky & Orabona 2019 Tran Dinh et al. 2022
Wang et al. 2019b Xu & Xu 2022).
Assumption 5. We assume that each local function Sc is E-mean-squaredd-moooh. i.e. for all x, E Rd, , E [n], it holds
[IV]((()) V.((y,)) S e e yll-
(12)
In MoTEF-VR, instead of simple momentum term, each client now maintains a momentum- based variance reduction term, similar to the STORM estimator (Cutkosky & Orabona 2019). The algorithm also maintains a momentum parameter X, and turns out that the additional variance reduction terms and Assumption 5 allow us to set the momentum parameter more aggressively, leading to an improved convergence rate.
Theorem 3 (Convergence of MOTEF-VR). Let Assumptions 3 and 5 hold. Then there exists absolute constants Ciy, Cx2 Cn and some т such that we stepsizes 7 c.,,,, CAn aa2 '2pppp 7²
c- and initial batch size Buii 2 [[ 1, then after at most
2/3
T=O
+
n2/3
11
"appe EFU
(13)
iterations of Algorithm 2 holds E [X s² where Xout is chosen uniformly at random
from (xo. -XT-1). and O suppresses absolute constants and poly-logarithmic factors.
Remark 4. Note that using large initial batch size Bin is required for convergence of MoTEF-VR. If we set Buii = 1, the above theorem still holds replacing F by n
Compared to MoTEF, MoTEF-VR achieves improved asymptotic rate. Moreover, all stochastic terms (the ones with σ) have a speed-up with n in contrast to the convergence of DoCoM, where only asymptotic term improves with
7

---

Published as a conference paper at ICLR 2025
2 Cliens
4 Clienes
Clienes
Client
Tointoo
Exa 1933 lterations
EER 1XE leeraions
terations
1230
1/p
(a) BEER
(b) MoTEF
(c)
(d)
Figure 1: (a) BEER with different number of clients n; (b) MoTEF with different number of clients n; (c)
MoTEF with different momentum parameter À. MoTEF's error decreases the number of clients increases, while the error of BEER does not. The error of MoTEF inereases the momentum parameter increases. In all cases, we set
K/a 0.1. We 0.0005, À = 0.005, and n = 16, if the opposite is not stated. (d) The number of iterations for MoTEF to reach error of 10ma compared to the theoretical prediction (1),2)) We see that the convergence of MoTEF is much less sensitive to than the theoretical prediction.
20, < = 10, = 10. and apply Top-K compressor with
parameters 7 = 0.1.
MoTEF
CHOCO-SGD
12"
12'
10 12 20"
10
12 Iterations
32" 10
10 127 Iterations
Iterations
Figure 2: Performance of MoTEF, BEER and CHOCO-SGD with varying data heterogeneity and fixed noise level We see that MoTEF outperforms BEER and CHOCO-SGD in all cases, and not affected by the data hetcrogeneity, while CHOCO-SGD's performance degrades as Ç increases. We set 20, n = and apply Top-K compressor with a = K/4= 0.1. We set the target error to be 0.01.
point out that MOTEF-VR applies the STORM mechanism locally to achieve the variance reduction effect. STORM is specifically designed for non-convex optimization problems, and its convergence rate in the more structured class of functions satisfying Assumption Dis still unclear in the literature (Cutkosky & Orabona 2019 Xu & Xu 2022) even for the simplest centralized SGD setting. In this work, we also do not consider the rate of MoTEF-V under the Pt. condition.
NUMERICAL EXPERIMENTS
In this section, we complement the theoretical results on the convergence of Algorithm with numerical evaluations.
4.1 SYNTHETIC LEAST SQUARES PROBLEM
We first consider simple synthetic least squares problem to demonstrate some of the important This problem is designed by Koloskova et al. (2020b) and studied in (Gao et al. 2024p. For each client i, fx(x = ||, b where A? == */ L and each b; is sampled from (0, (*)) for some parameter Ç which controls the gradient dissimilarity of the problem (Koloskova al. 2020b). It's easy
theoretical properties of Algorithm |
that when Ç 0, Vfi(x") = 0, Vi. We add Gaussian noise to the gradients to control the stochastic level o² of the gradient. We use the ring network topology for the synthetic experiment unless stated otherwise We run experiments
AMD EPYC 9554 64-Core Processor.
Increasing the number of nodes. In Figure (a-b) we study the effect of increasing the number of nodes on the convergence of Algorithm A crucial property of Algorithm i that its convergence rate provably improves linearly with the number of nodes, which BEER does not possess. Here we fix small stepsize and investigate the error that Algorithm I accieves with an increasing number of nodes. We observe that the error decreases linearly with the number of nodes, which consistent with the theoretical results, while for the error of BEER it is not the case.
'The code reproduce our synthetic experiment
available
https://
Inonymous.4opem http://cccciineeeeeeeeeeeeeteeee
exp- 4x6-
8

---

Published as a conference paper at ICLR 2025
BEER
MoTEF
Choco-SGD
DSGD
60
Lon
100
Test Accuracy
Gradi ent Norn
Test Accuracy
Grad ant Norm
1or
60-
15
20
200
10
10 15
10
Communicated bits, x30
Communicated bits, x10*
Communicated bits, x300
Communicaaees bits, X30*
(a) a9a
(b) a9a
(c) w8a
(d) w8a
Figure 3: Comparison of MoTEF, BEER, Choco-SGD, DSGD, D2 in terms of communication complexity on logistic regression with non-convex regularization ring topology with batch size and gsgde compressor. We observe that MoTEF outperforms other algorithms in terms both test accuracy and gradient norm.
Effect of the momentum parameter. In Figure (c) we investigate the effect of the momentum parameter A. In particular, how it affects the convergence in the noisy regime. Our theoretical analysis suggests that the momentum parameter À x 1) is crucial for the convergence Mo TEFEF. We observe that the eтror increases as the momentum parameter increases. Note that when À 1, we recover BEER which is known not converge with the presence of noise in the local gradients, which our experiment confirms.
Effect changing heterogeneity. In Figure 2 we investigate the effect changing data heterogeneity { on the performance of MoTEF, BEER, and Choco-SGD. The hyperparameters were tuned; the detailed description is given in Appendix D. We observe that MoTEF outperforms other algorithms and is not affected by the changing Ç. BEER is also not affected by the changing Ç. while CHOCO- SGD's performance degrades as ( increases. This is consistent with the theoretical results.
Effect of communication topologies In Figure[] we investigate the effect of the spectral gap on the convergence of MoTEF. We set 0² since the optimization term is most affected by p in the analysis. We detail the setup of the communication network in Appendix D.2 While the theory suggests that there might be 1/2² dependence, our experiment shows that the convergence of MoTEF is much less sensitive to p. Future research is needed to understand the discrepancy between the theory and the practice of the tracking mechanisms.
4.2 NON-CONVEX LOGISTIC REGRESSION
Following (Khirirat et al.
Makarenko et al. 2023 Islamov et 2024) we compare algorithms on logistic regression problem with non-convex regularizatior
2023
min 1 E f((x) + + of xcRd n
1t f(() = m Σド= log(1
1
(14)
where (beg asyl } j=11 is local dataset. We set À = 0.05,
100 and use LibSVM datasets (Chang Lin 2011). We do not shuffle datasets to have a more heterogeneous setting. Besides, each dataset equally distributed among all clients. In all experiments on logistic regression, we use More details this experiments are given in
gsgd, compressor (Alistarh et al. 2017) with Appendix
Comparison against other methods. We compare BEER Zhao et al. 2022). Choco-SGD (Koloskova et al., 2019). DSGD (Alistarh et al., 2017). and D2 (Tang al. 2018b) algorithms with MOTEF on ring topology. Detailed description is given in Appendix[D44 D.4 For each algorithm,
fine-tune all stepsizes to achieve better convergence. According the results in Figure 3 observe that MoTEF outperforms other algorithms in terms communication complexity in both cases, when the convergence is measured by training gradient additionally compare MoTEF against CEDAS (Huang & Pu 2023
and test accuracy. In Figure
Robustness to communication topology. Next, we study the effect of the network topology on the convergence of MoTEF. We run experiments for ring, star, grid, Erdös-Rènyi (p = 0.2 and p 0.5) topologies. Note the spectral gaps of these networks 0.012, 0.049, 0.063 0.467, 0.755
correspondingly. The hyperparameters of algorithms are given in Appendix D.3
Despite the
"Our implementation is hased open-source code from /hao et al. bioyue/bberr and is available
2022
httph:tt/////. httpa::/githob.comm T/M

---

Published as a conference paper at ICLR 2025
Ring
Star
Grid
ER, p=0.2
ER, p=
Test Accuracy
Gradient Norm
Test Accuracy
Grad Gradiemn eent Norm
10-2
80
40
10
20
10
15
20
10"
2
Communicated bits, x30*
Communicated bits, X10
Communicated bits, x10
Communicated bits, X
(a) a9a
(b) a9a
(c) w8a
(d) wSa
Figure 4: Performance of MoTEF changing of network topology tested logistic regression with non convex regularization. We n 40, À 0.05, and hatch size 100. We observe that MoTEF is very robust against changing network topologies practical problems.
Test Accuracy
Gradlent Norm
10f-
Chece-520
BEER
10-1
0.5
1.5
0.5
1.5
25
Communicated bits, x10"
Communicated bits, x 100
(a) MLP
(b) MLP
Figure 5: Comparison of MoTEF, BEER. Choco-SGD, DSGD, D2 terms of communication complexity on training MLP with hidden layer. We observe that MoTEF outperforms the other methods.
theoretical analysis showing a strong dependence p, in Figure we demonstrate that convergence MoTEF is not affected much by the change in spectral gap. These results demonstrate the robustness of MoTEF the change of network topology practice.
Training of MLP. Finally, we consider training MLP on MNIST dataset DDegg 2012) with 1 hidden layer of size 32. We present the results in Figure We observe that MLP trained with MoTEF and BEER achieve similar gradient norm, but MoTEF is much faster in accuracy metric showing the advantage from using momentum tracking. In addition, provide the results of training a CNN model in Appendix D.5
5 CONCLUSION AND OUTLOOK
In this work, we address critical challenge in decentralized stochastic non-convex optimization with communication compression, that is, achieving the optimal asymptotic rate of ("""/ne") matching that of the distributed SGD under the standard assumptions and without any impractical assumptions, such as bounded data heterogeneity or access to large batches. We propose new algorithm, MoTEF, incorporating momentum tracking and Error Feedback, and prove that it achieves this goal. We also extend the framework to MOTEF-VR and show that it achieves the variance-reduced rates under standard variance reduction assumption. We support our theoretical findings with extensive experimental study.
The tracking mechanism plays critical role in algorithmic design, and well-known challenge in these tracking mechanism is that induces worse dependence on the spectral gap of the network. However, our preliminary numerical experiment shows that MoTEF might be much less sensitive the spectral gap than what the theory predicts. We believe that future work can look into this aspect and either improve our analysis design even better tracking mechanisms. In our study, we focus only on compressed communication while there are many approaches such as performing several local steps (Mishchenko et al. 2022b, Gorbunov al. 202T) or asynchronous communication (Islamov et al. 2024; Mishchenko et al.) 2022a) that might be useful. We also note that some recent works attempt to improve the dependencies on the smoothness parameters for variants of Error Feedback algorithms (Richtárik et al. 2024), where each local objective is assumed to be L,-smooth, and more careful analysis of the method gives dependency on the average-smoothnee maX L,. Therefore, combining the aforementioned
= n >> L;
instead of the maximum smoothness research directions with our proof techniques might lead more improved results. We defer the exploration of these possible extensions future research endeavors.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs. Unfinished monograph, recompiled 2014, 2002.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communicationn efficient sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31, 2018.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematiccal Programming, 199(1): 165-214, 2023.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, 2018.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal of Machine Learning Research, 2023.
Chih-Chune Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2011.
Ziheng Cheng, Xinmeng Huang. Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. In The Twelfth International Conference on Learning Representa- tions, 2024.
Captitae Cordonnier. Convex optimization using sparsified stochastic gradient descent with memory. Master thesis, 2018.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topcu. Faster non-convex federated learning via global and local momentum. In Uncertainty in Artificial Intelligence, 2022.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2012.
Hao Di, Haishan Ye, Xiangyu Chang, Guang Dai, and Ivor Tsang. Double stochasticity gazes faster: Snap-shot decentralized stochastic gradient tracking methods. In Forty-first International Conference Machine Learning, 2022.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path inteerintertted differential estimator. Advances in neural information processing systems, 31, 2018
Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtarik. B121 with bells and whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv: 2110.03294, 2021.
Ilyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves enror feedback! Advances in Neural Information Processing Systems, 2024.
Yuan Gao, Rustem Islamov, and Sebastian Stich. EControl: Fast distributed optimization with com- pression and error control. In The Twelfth International Conference Learning Representations, 2024.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging error compensated sgd. Advances in Neural Information Processing Systems, 2020.

---

Published as a conference paper at ICLR 2025
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local sgd: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics, 2021.
Luyao Guo, Sulaiman A Alghunaim, Kun Yuan, Laurent Condat, and Jinde Cao. Revisiting decen- tralized proxskip: Achieving linear speedup. arXiv preprint arXiv:2310.09883, 2023.
Samuel Horváth and Peter Richtárik. A better alternative efficient distributed learning. arXiv preprint arXiv:2006. /077, 2020.
feedback for communication-
Samuel Horváth, Chen-Ye Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, 2022.
Kun Huang and Shi Pu. Cedas: A compressed decentralized stochastic gradient method with improved convergence. arXiv preprint arXiv:2301.0580 00.0072.......... 2023.
Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algo- rithms in distributed learning with communication compression. Advances in Neural Information Processing Systems, 35: 15:18955-1899, 2022.
Xinmeng Huang, Ping Li, and Xiaoyun Li. Stochastic controlled averaging for federated learn- ing with communication compression. In The Twelfth International Conference Learning Representations, 2024.
The MathWorks Inc. Symbolic math toolbox version: 23.2 (r2023b). The MathWorks Inc., 2023.
URL https: http:://wwww..t www.kuawwwwkkc..oooom
Rustem Islamov, Xun Qian, and Peter Richtárík. Distributed second order methods with fast rates and compressed communication. In International conference on machine learning, pp. 4617-4628. PMLR, 2021.
Rustem Islamov, Xun Qian, Slavomír Hanzely, Mher Safaryan, and Peter Richtárik. Distributed newton-type methods with communication compression and bernoulli aggregation. Transactions on Machine Learning Research, 2023.
Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis of asynchronous- SGD algorithms. In Proceedings of The 27th International Conference Artificial Intelligence and Statistics, 2024.
Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity, In International Conference on Artificial Intelligence and Statistics, 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and trends@ in machine learning, 2021.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Machine Learning and Knowledge Discovery Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part 16, 2016.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, 2019.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning, arXiv preprint arXiv:2008.0366 0060000000000.... 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference machine learning. PMLR, 2020b.
12

---

Published as a conference paper at ICLR 2025
David Kempe, Alin Dobra, and Johannes Gehrke. dossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., 2003.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On sargebbtchl training for deep learning: Generalization gap and sharp minima. arXiv preprint ar 110.:466090 2016.
Sarit Khirirat, Eduard Gorbunov, Samuel Horváth, Rustem Islamov, Fakhri Karray, and Peter Richtárik. Clip21: Error feedback for gradient clipping. arXiv preprint: arXiv 2305. 18929, 2023.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference on Machine Learning, 2022.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference Machine Learning, 2019.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations, 2020a.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified the- ory of decentralized sgd with changing topology and local updates. In Proceedings of International Conference on Machine Learning, pp. 5381-5392 PMLR, 2020b.
Anastasiia Koloskova, Tao Lin, and Sebastian U Stich. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 2021.
Jakub Konecný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint drX0v:/6/0.05492,, 2016.
Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 2020.
Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi. Peter Richtarik, and Sebastian Stich. A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In International Conference on Artificial Intelligence and Statistics, 2021.
Boyue Li, Zhize Li, and Yuejie Chi. Destress: Computation-optinns and communication-efficceenn decentralized nonconvex finite-sum optimization. SIAM Journal on Mathematics of Data Science 2022.
Yao Li, Xiaorui Liu, Jiliang Tang, Ming Yan, and Kun Yuan. Decentralized composite optimization with compression. arXiv preprint wxXiv2210.004424 2021.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu, Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 2017.
Xiaorui Liu, Yao Li, Rongrong Wang, Jiliang Tang, and Ming Yan. Linear convergent decentralized optimization with compression. In International Conference on Learning Representations, 2021.
Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In International Conference on Machine Learning, 2021.
Maksim Makarenko, Elnur Gasanov, Abdurakhmon Sadiev, Rustem Islamov, and Peter Richtárik. Adaptive compression for communication-efficie distributed training. Transactions on Machine Learning Research, 2023.
13

---

Published as a conference paper at ICLR 2025
Amin Kargarian Marvasti, Yong Fu, Saber DorMohammadi, and Masoud Rais-Rohani. Optimal operation of active distribution grids: A system of systems framework. IEEE Transactions on Smart Grid, 2014.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint 1901v:990.000266 2019.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems. 2020.
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. Asynchronous sgd beats minibatch sgd under arbitrary delays. Advances in Neural Information Processing Systems, 2022a.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! local gradient steps provably lead communication acceleration! finally! In International Conference on Machine Learning, 2022b.
Aritra Mitra, George Pappas, and Hamed Hassani. Temporal difference learning with compressed updates: feror-feedbace meets reinforcement learning. arXiv preprint arXiv:2301.00944 2023.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 2009.
Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over varying graphs. SIAM Journal on Optimization, 2017.
Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 2018.
Boris T Polyak. Gradient methods for the minimisation of functionals. USSR Computational
Mathematics and Mathematical Physics, 1963.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 1964.
Xun Qian, Rustem Islamov, Mher Safaryan, and Peter Richtárik. Basis matters: better communication- efficient second order methods for federated learning. arXiv preprint arXiv:2111.01847, 2021.
Guannan Qu and Na Li. Harnessing smoothness accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 2017.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International conference on machine learning, 2021.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. arXiv preprint arXiv:2204.06125. 2022.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster enror feedback. Advances in Neural Information Processing Systems, 2021.
Peter Richtárik, Elnur Gasanov, and Konstantin Pavlovich Burlachenko. Error feedback reloaded: From quadratic to arithmetic mean of smoothness constants. In The Twelfth International Confer- ence on Learning Representations, 2024.
Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni, Spyridon Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier-Hein, al. The future of digital health with federated learning. NPJ digital medicine, 2020.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtarik. FedNL: Making Newton-type methods applicable to federated learning. In Proceedings of the 39th International Conference on Machine Learning, 2022.
14

---

Published as a conference paper at ICLR 2025
Stefano Savazzi, Monica Nicoli, and Vittorio Rampa. Federated learning with cooperating devices: A consensus approach for massive iot networks. IEEE Internet of Things Journal, 2020.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth annual conference of the international speech communication association, 2014.
Ayush Sekhari, Karthik Sridharan, and Satyen Kale. Sgd: The role of implicit regularization, batch-size and multiple-epochs. Advances In Neural Information Processing Systems, 2021.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catan- zaro. Megatron-Img Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv:1909.0800 2019.
Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. Squarm-sgd: Communication efficient momentum sgd for decentralized optimization. IEEE Journal on Selected Areas in Information Theory, 2021.
Sebastian U Stich. On communication compression for distributed optimization on heterogencous data. arXiv preprint arXiv:2009.023388. 2020.
Sebastian U Stich and Sai Praneeth Karimireddy, The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint arXiv:1909.05350 2019.
Sebastian Stich, lean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in neural information processing systems, 31, 2018.
Nikko Ström. Scalable distributed dnn training using commodity gpu cloud computing. In Interspeech 2015, 2015.
Haoran Sun, Songtao Lu, and Mingyi Hong. Improving the sample and communication complexity for decentralized non-convex optimization: Joint gradient estimation and tracking. International conference on machine learning, 2020.
Yuki Takezawa, Han Bao. Kenta Niwa, Ryoma Sato, and Makoto Yamada. Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data. arXiv preprint arXiv:2209. 15505, 2022.
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. Advances in Neural Information Processing Systems, 2018a.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training over decentralized data. In International Conference on Machine Learning, 2018b.
Hanlin Tang, Xiangru Lian, Shuang Qiu, Lei Yuan, Ce Zhang, Tong Zhang, and Ji Liu. Deepsqueeze: Decentralization meets croo--comensated compression. arXiv preprint arXiv: 1907.0734,, 2019.
Quoc Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. A hybrid stochastic optimization framework for composite nonconvex optimization. Mathematical Programming, 191(2):1005. 1071, 2022.
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving
communicaiion-etiiicann distributed sgd with slow momentum. arXiv preprint arXiv:1910.0064 2019a.
Meng Wang, Weijie Fu, Xiangnan He, Shijie Hao, and Xindong Wu, A survey on large-scale machine learning. IEEE Transactions on Knowledge and Data Engineering, 2020.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. Advances in Neural Information Processing Systems, 32, 2019b.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. Advances neural information processing systems, 2017.
15

---

Published as a conference paper at ICLR 2025
D Randall Wilson and Tony R Martinez. The general inefficiency of batch training for gradient descent learning. Neural networks, 2003.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 2004.
Ran Xin, Usman Khan, and Soummya Kar. fast randomized incremental gradient method for
decentralized nonconvex optimization. IEEE Transactions on Automatic Control, 2021.
Ran Xin, Usman A Khan, and Soummya Kar. Fast decentralized nonconvex finite-sum optimization with recursive variance reduction. SIAM Journal on Optimization, 2022.
Yangyang Xu and Yibo Xu. Momentum-based variance-reduucd proximal stochastic gradient method for composite nonconvex stochastic optimization. arXiv preprini arXiv: 2006. 0006,00425, 2022.
Yonggui Yan, Jie Chen, Pin- Yu Chen, Xiaodong Cui, Songtao Lu, and Yangyang Xu. Compressed decentralized proximal stochastic gradient method for nonconvex composite problems with hetero- geneous data. International Conference on Machine Learning, 2023.
Chung-Yiu Yau and Hoi-To Wai. Docom: Compressed decentralized optimization with near-optimal sample complexity. arXiv preprint arXiv:2202.0022 2022.
Jiaqi Zhang, Keyou You, and Lihua Xie. Innovation compression for communication-effcieentt distributed optimization with linear convergence. IEEE Transactions on Automatic Control, 2023,
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, and Yuejic Chi. Beer: Fast o(1/t) rate for decentralized nonconvex optimization with communication compression. Advances in Neural Information Processing Systems, 2022.
16

---

Published as a conference paper at ICLR 2025
A EXTENDED RELATED WORK
In this section, we provide additional discussion the related works on decentralized optimization specifically focusing on the dependency of the deterministic optimization term on the spectral gap p.
In the non-compressed, strongly convex, and deterministic regime, Kovalev al. (2020) and Mishchenko et al. (2022b) achieve optimal /(/L/o)), i.e. the dependency on the spectral V().)) Kovalev et al. (2020) proposed an algorithm APAPC based on the Chebyshey acceleration while Mishchenko al. (2022b) boosts the convergence through incorporating multiple local steps. We highlight that both algorithms do not impose any bounds on the data heterogeneity. Later, the results of Mishchenko et al. (2022b) were extended to the stochastic regime (Guo et al., 2023) beyond p the stochastic regime worsened to (()))) Liu et al. (2021 Li al. (202)) achieved ('//up) convergence rate but with the use of a stricter class of unbiased compression operators and in the full-batch regime. [Zhang et al. (2023) proposed an algorithm called COLD that attains Ö(4/p + a convergence rate in the deterministic strongly convex regime with contractive compressors. BEER algorithm (Zhao et al. 2022) achieves the rate that depends on 5 similarly to the rate of MoTEF but under unrealistic large batch requirement. DoCoM algorithm attains the linear speed-up with n in the stochastic regime but has worse + dependency on the spectral gap. Both DeepSqueeze (Tang al. 201 8a) and Cho Koloskova et al. 2019) achieve A but under bounded data heterogeneity assumptions.
strongly convex functions with linear speed-up in However, the dependency
To summarize, to the best of our knowledge, there is no work in the most general setting considered in this work, namely, stochastic non-convex decentralized optimization with contractive compression under arbitrary data heterogeneity, that achieves better dependency on the spectral gap Most of the works make additional assumptions with possible improvement of the rate w.r.t. p. however, the question remains if the results are transferable to the considered setting. Therefore, additional effort is needed to either improve the convergence guarantees of MoTEF with more involved analysis using enhanced tracking mechanism or show the lower bound that the optimal vp dependency is not achievable in the worst case.
A.1 INTUITION BEHIND MoTEF ALGORITHM DESIGN
Designing an algorithm with strong convergence guarantees without imposing assumptions on the problem or data is complicated. In MoTEF we incorporate three main ingredients to make it converge faster under arbitrary data heterogeneity. In particular, the combination of EF21-type Error Feedback (Richtárik et al. 2021) and Gradient Tracking mechanisms is the key factor in getting rid of the influence of data heterogeneity. We emphasize that not using one of them would lead to restrictions on the data heterogeneity. Indeed, EF21 is known to remove such dependencies in centralized training while the GT mechanism is essential in decentralized learning (Koloskova et al., 202I). Nonetheless, EF21 does not handle the error coming from stochastic gradients and momentum known to be one of the remedies to it (Fatkhullin et al. 2024).
B MISSING PROOF FOR MoTEF
We recall the notation prove convergence of MoTEF:
17

---

Published as a conference paper at ICLR 2025
G VF((')1 -
1 f( ml
= V - M
10 - a1
H' [
42
G' v-[l
X x11
42 =
| v'1
Ω = E |
Moreover, F E (x)) - / Let us define Ω = [ G 24, 22 22 24]T. In addition, we
denote (F = g [x] ...... (x
Rdx= a matrix that contains local stochastic gradients.
We denote C == max W 1] 4.
Lemma 5 (Lemma B.2 from (Zhao et al.
2022
Let W be mixing matrix with spectral gap p.
Then for any matrix X Rdxh and X
x1 we have
XWW- x1 T 1 S (1 p)[[ X1 2
(15)
Moreover, for any 7 E (0, the matrix W = I 7( W 1) has spectral gap at least rpp
Lemma 6. The iterates of Algorithm satisfy
4L+1 - 1,
(16)
72
and
x1+1
M'1.
(17)
Proof. By induction, we can show that 3²
1 M',, if we initialize v M Indeed, we have
n
n V
1 -M -MM-I-M'))
v'1
G 1)1
n
- v'1 +
MM V
1
Therefore, we have
x++
x + IHH (W- I)1 Lv'1
n
n
x² n/v x¹
" M' n
B. GENERAL NON-CONVEX SETTING.
Lemma 7. Assume that Assumption holds. Then we have the following descent on Ft
Fen Ft T [IVS(x))12]
+ G 2L² 21 -f 1/2)
(18)
18

---

Published as a conference paper at ICLR 2025
Proof. Using smoothness get
1/2 L [||v|1|]
P11 P. 1/ ( **>
= =F E
1 + 2 ||| f( - v11 (-1/2 1/242) [1|V`1]]
2
F. " E [[ || + E
VF
M'1
(-n/2 "² 4/2)E [|']
n
n
$ F. 2 E V || + 7E
1 VF(X') 1 M''1
2
VF(x') 1 VF(X")1
+ n
---1/22 1/2/2 [|[v*1]]
7
|| + 1 c + nL3 E
S F.
xx-- x'1
1x'-x'117 11] -1-1/2 - 1/2200
n
n
+ 7 c+ + nL2
F.- E [|V
(-1/2 1/2)
n
n
Lemma 8. Assume that Assumptions 2 and 3 hold. Then we have the following descent on &t
G s A)E COFF(X)J-MMII)) + (1
n)?
E X
x'+1112
+ 22 (19)
A
Proof.
Using the update rules of Algorithm T we get
G++1 = // - M 11|"
= VF(X (1- AJM - 2
= E [|(0 ()FF
- FF(X(t1))
+ +11- (11A)((F((*)) - 1F(X))113
< (1 - E [[(VF(X M (VF+((VV))))))))) VF(X (F1X')111 + X2
< (1 AJE V - - + (1- (1=A)
E ||| -x 1|2] + n2
where the first inequality we use the fact that (F((*+1) = VF(X+1) and Assumption 3
and in the second inequality we use ||a + bl2 < (1 + |||l + (1+ 8 ||b|| for any vectors a, and constant b.
Lemma 9, Assume that Assumptions 2 and 3 hold. Then we have the following descent on G
G++1 < X20n + (1 - 12
B [|x
x"1[]] (1-
(20)
X
19

---

Published as a conference paper at ICLR 2025
Proof.
G++1 |VF(X*+) |
E E /||/F(X*+) (1 A)M XVF(X
S Xo (1 1) ||V M7]
2 X + (1 (1-))))111 37 E -
+ +11 - -1) 3
- V |1
S Noon+ + (1- E
|F((*+)) - vF(X))
+ + A)E -
|IM v
A
< Xonn+ (1 - 2)2
||x xx11 +1-
E
X
where we choose 31
A [I-AJ
Lemma 10. Let Co be any contractive compressor with parameter a. Then we have the following descent Q
21 S (1 a/2)E
[1x
(21)
Proof. We have
2 = E
H H+1 x x
= E
H + C. (x - H³)
x -1 [|2]
< (1 a) H -
S (1 - 2/2/E
||HH x21]2]
+
- ||x
x
Lemma 11. Let Ca be any contractive compressor with parameter a. Then we have the following descent on 22
Proof. The proof is similar the one of Lemma 10
= = [[| v |
$ (1 (1-o/2)3 ||
2
||v
v++1 ||:
+
Lemma 12. We have the following descent on S2/
2 (1 (1-09/2)54 (1 2//n)2 + (1 2/
(22)
20

---

Published as a conference paper at ICLR 2025
Proof.
X ++ x ++ [1
E
E
x H HW (W- -
-'1" 1 [P]
E
X'W x'11 +H(H X 1) v' + 1144r
(1 () Bp ||X
x [|]
(1 (1+ (1 3 [| X D)
2n/E E v - v )
s (1 10/2) || - -x1 [p]]
(1+
H' -''X'111
TE R || V - -
(1 - -1/222)22 + (1 + 2 + (1 + 3/50)21
where
7p/2 and we define W 1-7p
(W I) which has a spectral gap at least yp by
Lemma 5
Lemma 13. have the following descent on 522
S4 $ (1 (1-70/2)E ||v 111)
+ (1+ (110/) (272EE [||G* |||* v''l + 21 M -M'm (P2))
(23)
Proof.
1+1 E
V V'1TT + 4'1T 1
V++1 1'1 21 nE -445 (
8
5 B
Vt+1 2'1
E
V + 7G' -1) 11 M -
vv'-v'17j v'17 1
- 1'1 + G V') -) (I) M -M' MM 1|:
E
< (1 10/2)LE || 1'1
+ (1 +11+3/0)27700B [IG'-
| M 11 [?])
+ 2E
Lemma 14 (Lemma B.4, Eq. (18) from (Zhao et al. 2022 ) We have the following control of the
iterates at iterations L and +
E
[| < 2 + 3- Cn. + 3n + 3
(24)
Lemma 15. Assume Assumptions and hold. Then we have the following control of the momentum at iterations and t.
E ||M++I-N - M³ || < X2n= + 2x |VF(X') - -M]]] + 22 [|x - x (25)
21

---

Published as a conference paper at ICLR 2025
Proof.
E | M| = =
v M
| VF(x*+1) + VF(x+!)) - -MM
A
S x A ||FF(X++1) ||
S > + 2 ||V - M + 2 | x
Lemma 16.
We have the following control of the gradient estimator V at iterations i and t +
- v'[
+ +3, + 3E -
(26)
Proof.
E V 1-
-
|| (W - - M
V') - 1) (V - -v'1") ""'")(W (W I) M M M'
- 33 |||* - v'Il + ||
v'17 [1
+ 3E || -
---H1-1-- ||]
= =3 + C + 3IE | M'
Theorem 1 (Convergence of MoTEF). Let Assumptions 2 and hold. Then there exist absolute constants Cyp, Ox2 Cy. and some S 1 such that if we set stepsizes y c,,,, = cxap'
C. p.I.-"opp' T, and choosing the initial batch size Bunit 2 -= then after at most
T O
LF
(10)
ap
iterations of Algorithm ir holds EE [IV
)13]
S 62, where Xout is chosen uniformly random
from ( 8T and O suppresses absolute constants.
Proof. From Lemma
15 and Lemma
14 we get
E
M +1 - M' F <
n0 + 21
(27)
Using the above and Lemma
16 we get
|| - [
< 3X2no" + 6 18A"" +
+ (3+2C + + 2
(28)
Using 27 and Lemma we get the following descent on &"
(r- - (1 x) + C o 3L 2 +
ru) 2 +
n
D + X2n02.
A
A
Using
and Lemma we get the following descent on T
G++l < x) + 2C Ω +
3
31222
3I.2nm2
2
+
+
2S + 2
A
A
A
22

---

Published as a conference paper at ICLR 2025
Using 27
28
and Lemma
10
get the following descent on f2s
a
2
O +
6
2
+
6n
22 +
6n
S2z
2
Using 27
28
and Lemma
we get the following descent on 22
6y
6A2
36A2 G
36X232L2C
+
f2 +
2
a
a
a
a
C
3612 2
X2
36
2
X2L
6
24 +
Og + g².
a
Using and Lemma 12 we get the following descent f2
2
s (1
3P
6yC
22 +
6n²
Ωz
(29)
P
PP
Finally, using 27
28 and Lemma
13 we get the following descent on Ω2:
24
S
(1
7P
361/² 361 22
12X²
G +
36>22L2C
2 +
67C
36yA2L
22
2
7P
7p
P
p
367
6A
02
+
0
7p
Now can gather all together
3L 3L2
AL
3L 3L2
0
31
=
32
0
1 -
X
0
+ 2g
0
0
211
61²
36A 120
128
36X2 IPC
,
22
0
0
GgC
0
Q
a
y
Gy2
0
12x²
36 30 L.C
GgyC
36-A2
70
2 x
36n
7PP
2
TP
31 nnp
71
2n O fn
6n
S2
X²02.
(30)
361
L
Ö
6n
3 1.2
bu
We remind that the Lyapunov function &² has the following form
Φ- = Ft
Ci 6t + C2T T
+ CgL pinn
St + CAT 2t
+
CoL St + p'r
C&T pLL
F² + TT
n2L
nL
paL
where {cx absolute constants. Let
C1
C2T eaL
CAT egL GCT T pnL Par pnI.)
nL
p
23

---

Published as a conference paper at ICLR 2025
Therefore, the descent o' for is the following
+1+2 = ph+l
'2' + p
nL
s Fi " [| || + 7 6
Ω2 (7/2 4/2332
n
+ c (AS'' R3bb + b2)
lr -"-"B || || |1|]
+ T2 + (q +c c -11/2 1/4/2 c bbb1
+ c 022202
o' - " || (q A - cJ)s' - (1/2 1/2/2 c. b,
2
+ b2
where q= (%/,, 0, 0, nL'/n, 0)T We need coefficients next to Ω and Og to be negative. This is equivalent to finding such that
A b
q
(31)
We make the following choice stepsizes
Ggap" 3T
A = CRaPT = c,ap,
1)
L
with the following choice constants:
CA
200 Cy
200 Gy
100000
and,
13
1
1
9
1
Cs
(32)
500
200000"
20"
400000
100
200000
The system of inequalities 31 are satisfied when F S
Given the complexity of the inequalities and the choices of the parameters, we do not attempt to write down a proof for the correctness of the choices manually, instead, we verify these choices using the Symbolic Math Toolbox in MATLAB. We also perform such verification for our parameters and constants choices for MoTEF in PE case and MoTEF-VR. The code performing all the verification can be found at this anonymous link We also note that, when cX2 Cy and C, are fixed, we can search for a feasible Jieje efficiently using the Linear Program solver with MATLAB as well. But searching for feasible set of choices for cA. C. and C, is very much trial-and-eree and-error process.
Note that this choice gives us both À and smaller than This choice of constants gives the following result
< Φx Gnap"t
t1+1
E [
[[V]((*'
+
C1 n²T. n 2
21.
C2T 2ne 2 2202
nL
- + CAT 6n 2 22p200000
mT.
CGT 6n 20pp002002 Gaaap .202 nI
PnL c,ap
Φ GappT
2L E [[V)
c22220
+ BeocZ 7302. Gb
+
(33)
L
24

---

Published as a conference paper at ICLR 2025
By this, proved Lemma]
I
Let us define constants
G,app
B =
21.
QqaZp'
C
nL
66 Gegcaap
+ 20302a2 (cocfap")
D
+
caL
=
Using 7 S E and unrolling
33 for T iteeattions we get
1 E
Σ
[IV]((
$
C
D To²²
+
T
BBT
B
B
1/2
1/3
So need to choose T min
1
80
40
and we get the following rate
E
CTo²
DT
T
F
C$802
1/2
VD
2/3
[IVS((*)
0
+
+
BT
B
B3/2T
L
[IT002
1/2
0
+
ap²T
n.
2/3
Vap + p² + ap L
+
03/2/9/TT
L
O n.T
1/2
( (
+ 1/2 p 1)L
2/3 )
0
T
ap3/2T
that translates the rate in terms of to
(Le
L
L
L ap
L
L ap3/2g3
T T= O
app'z
n
+
a1/2 3/2g3
+
Σ E [[V s
In the result above the fifth term always dominates the third and fourth. Therefore, we remove the third and fourth terms from the rate and derive the following rate
(
L
0 ne
LØoO ap$/2g3
T-1
T=o
Σ
app'
Note that with the choice V
= G M = vF(X") H = x = 1T
we get
G S 0
G0 < n f = 22 = 22 = 22 = 0.
to F 0
d +
C2T 2nn. nL
(34)
If we choose the initial batch size Bini
>
L
a²
we get
1
o²
1 o²
To
F
S 3F0
(35)
nL Buui
L Bunt
25

---

Published as a conference paper at ICLR 2025
B.1.1 CONVERGENCE OF CONSENSUS ERROR
Now we show that the workers achieve consensus automatically with MoTEF. We notice that (33) be tighten. In particular, if we substitute the choices of constants in into (11. have the following:
La
(q - c < -C
prn
where e7 an absolute constant. We highlight that the choice of constants {c can be tightened but we are interested in the dependency on the problem-specific parameters only. In particular, this implies that we have the following (instead of (33)
Φ++1
CpappT 2L
E
|-]
La CT
La prn
22 + Seaap 7202
nL
60 60Jcrap L
203 pa
+ 6co22ap')
Gbl )
(36)
L
Therefore, we have:
Σ
207 1?2
1
T
T-1
2 BBT
$0
C TO²
D B Dro.
pnppT2
n
where B, C, D are defined in the proof of Theorem | Le
before. In particular, this means that Cup'Tz 7 Σ S converges to zero at the same speed as -I-I [x*))() By our
choice of т < 1, we have:
T-1
Cnpt
10
C
D
O2
S
+
+
Tn
20
TBT
pTO
1/2
(p²+ + 1303000000 2/3
S 0
+
+
aLT
nL3T
al2T
Therefore, we obtain that
T= o pap
P²00022
T-1
n 52 Σ
aLge
nI3gt
at2e3
Tn
t=0
B.1.2 CONVERGENCE OF LOCAL MODELS
Since we have the convergence of the averaged gradient norm / -T- sensus error Tm
T- E E and the con-
0 Dg we also obtain the convergence local models. Indeed, we have t=
T-1
T Tn
T
<
E
- -((+)) -
Tn
2 T-1
E (
Tn
21 T-1
2 T n
Tn Σ E
|
1 x{|
E
[|
Tn
2L T-1
T-1
Σ
Ω
+
Σ
Tn 1=0
Tn
t=0
26

---

Published as a conference paper at ICLR 2025
B.2 PE SETTING.
Theorem 2 (Convergence of MoTEF). Let Assumptions 2 to
hold. Then there exist absolute
constants Cry CX2 Cg. and some S such that we stepsizes 7 Cypp, cxax'T,
c, and choosing the initial batch size Binit
2
LF then after at most
o²
T=
Lo² u-ne a0r/210/2g113
La
(11)
pape
iterations of Algorithm it holds E [[(x*) | poly-log tohariogaii factors.
S, and Ô suppresses absolute constants and
Proof. The only change in the proof is the descent of the Lyapunov function. In Pt. case, the descent on &f becomes
41+1 = = +2
$ F. "E ||]
- 2zz (1/2 - 1f
n22
n1²
n
+ (A + +1/b1 + x²0²bz)
I (1 - n/ - (1 n// N + ( T +b= A (1 (1-1 )
(1/2 1/1/2 blb,))b 20 + bbd
(1 7/) +b (1 n/)b 'r -/2- +
+
+b byd
where in the second incquality we use PE condition. Similar to the proof Theorem | satisfy
we need to
(1 (1-p7) I
A
b
b
for some coefficients b. We set the stepsizes such that
Gapp+
= exap'T
7 == c.ap, 1/
T.
and
b1 but byL bAT bsL bGT L nL p² puL p²nnt pnL
b
n
with the choice
1
Cx 200000* Cy = 200000 On 100000000*
and
13
1
01
250 0/
by
20 8u 400000 .b 2, hs 200000
200000
gives the following descent on क' (note that both y and À are smaller than with this choice of constants)
(1-
ábbippp' ?202
r1+1
5
66 bsaps L
202braipp (bseeape) -302. L
+ cyb
(37)
Let us define constants
Gapp' F
B
2L capp
C
nL
6 crap
+ 202era2p0
+ beoezapt)
L
caL
E
27

---

Published as a conference paper at ICLR 2025
Unrolling (37 for T iterations get
f (1- BT) +
C 00
-- -1-
+ 0
C 2
332
Br
Br
B
Br
where we use the fact that
m-1 1
Σ
(1
BT)
1 (1
BT) m
1
BT)
Br
Choosing min 1
log
B
1
log
40 Do²
leads to the following rate
E BT
Co
BT
B T
Co
Do
exp
B
B
We refer MMihhheenko al. 2020) for more detailed derivation (proof of Corollary 1, page 20). To achieve F1 I E, we need to perform
Co²
VDo
T =
+
B
B B3/2g
La iterations. Note that the fourth term always dominates the third and fifth terms. Therefore, we remove them from the rate and derive the following rate
L
Lo²
La
La
paps
12
+ a. p2 22
//2222
p32223/211/2
(HUTP
L
Lo²
Lo
+
12/2223//2111
C MISSING PROOFS FOR MoTEF-VR
this section, we provide the proof of convergence of Algorithm 2 Note that this case Lemma remains unchanged.
Lemma 17.
Let Assumptions andd hold. Then we have the following descent on &2
G++1
< (1 - -) 2 PB [ x x1
(38)
Proof. We have
G++1
E
M 1- |1|
+1 -1 (
=
E
E
+ A) -14))) - -FXX) -F(X,
+(1 A) VF(X))) 11]]
< (1 X)2 E (M 11
+ + ( |E++)) -VF(X*+))
+ 2 - 2) (F V
- OF(X", g ))1
(1- A) + 22200n
+ + - -
(39)
28

---

Published as a conference paper at ICLR 2025
For the last term above continue follows
E
, - - - E
E
fi [x] - V.- Vf((x) V.(((.tft
Σ
E
V (. V V((() x
I (x (....t)))))))))))) - -
C || x [[:]
(40)
Therefore, from 39 get
G++l S (1 (1 + 22200n + [1x
(41)
Lemma 18. Assume Assumptions (andd hold. Then we have the following descent on &
Gi+ S (1 (1- A) ( B
(42)
Proof. The proof is similar to the one of Lemma
Note that Lemmas 10 to 14 and 16 do not change in this setting, thus, we do not repeat them.
Lemma 19. Assume Assumptions and 5 hold. Then we have the following control of momentum at iterations and +
E [[]M*++ - 1 s X 2X2n02 + 2 -X*1)
(43)
Proof.
Using the update of Mc we have
[[ - M M [|]] = E +X +1 A)(M - ( M
E JIF((X - AM ,
E MM) E(4)) VF(X))
+ + +1 | F -(+1)
- + A(F - VF(X))
+ (1 -F( =
2XO +2X + 28 2 X [1]
Now we introduce the following Lyapunov function of the form
T aprt GH + ne
T
+ dap da pri
Dr
dal pnr
22
+ ds pnt
D'
(44)
where {dx 1 are absolute constants defined in 44 Again, we present the descent lemma on the I Lyapunov function Tpa
29

---

Published as a conference paper at ICLR 2025
Lemma 20 (Descent of the Lyapunov function). Let Assumptions and hold. Then there exists ab- solute constants Cay, CX2 Cnj and < such that if we set stepsizes Y ap, = cAn a? .7, Cep enp--app T then the Lyapunov function &e decreases as
a2p0=²,
g I V Gapp" TE
+ 2010 n2e a p
2L [IV](()))
222ezaap2 12d4cza2 6daeza" n
)
(45)
n2e
nel
Remark 21. Compared to Lemma 7 in Lemma 20 the leading stochastic term has cubic dependence T, whereas in Lemmal 7 the dependence is quadratic. The improved dependence is the key ingredient to the speed-up up for variance reduction rype methods.
Proof. From Lemmas and 19 we get
E [
M
S
X
no + 22 2 (3 +3,90 +33
no + 2²0 + + 6C 6n +
2
(46)
From the above inequality 46 and Lemma 16 we get
E [[]++
- -
Cn2 + CN2
3 no + x 6 6C, 6n) + 6
6x + 3 180- 2 + 30
+ 180
(3Cg² - 2 ) + 18nn" (
(47)
From Lemmas
14 and 17
get the following descent on G
+ +31 Gt+1 (1 X)C² +2 + (3) +3 + 3y
2X200n
(1-))= 30 + 3C + 2 + 3nm 22
Similarly, from Lemmas
14 and 18
get the following descent on G
GH+1 22X (1
λ)ō + 30 + 3C72 + 3 3n
From Lemmas 10 and 14 we get the following descent on !
2 23 + 3y 3 372n())
2+1 (1 - a/2)I ||H' x
a
= =11 - 0/2 6C 6cx2 + 6C²²
6n² Ω + 6nn? 2z.
2 +
a
From Lemma and (47 we get the following descent on 22
2 $ (1 (1- (1-9/)) + 2 no + +3x + 180 18072
+ (30g² + 18C7 12 21 + 18m7 Rng.
12nX2 02 +
6x 7tt + 26
of + (1 - 0/2 6002%/)6)))) 26
2
2
26n 12
+ - (30²² + 18 20 2 +
a
30

---

Published as a conference paper at ICLR 2025
The descent on f2
29
from the proof of MoTEF remains unchanged
2 <
2
Sgg
G l2 +
6n²²
Szz
7p
From Lemma
13 and (46)
we get the following descent on !2
< (1- -
+
+ 2(1 2/70) + X²6" 6C)2 + 60C22 + 6 6mm)
6n 0² 312
+ 1807f2
607
18Cxe2 22
of
+ p
2 + (1 -0/22-0000000/ + 180222/70)
7P
7P
18
70 5z.
We remind that 52 (G', G 12,22 Qz (4)T.
Now we can gather all inequalities together
A
0
30
0
3C
31/2
1
X
22
3C 22
3r
0
1 1
+ 60
6C
6r
12+ <
6A2
6C
36C 2
6C
36n y
Ω
2
0
G
20
6x2²
TP
3x2
18CrE
6C
18C
181 2
7.
P
TPP
3rm2 C²
3roy' C
2n
Gnnn
36nm 3 8 Ö
S +
2²02.
(48)
18mr) TPP
1= b2
:=b1
Now we consider the following choice of stepsizes
20722672
n= Grap3
n 7 = c.ap,
and constants
d1 d2 dzl d4 dyl
ds
d = appnt ne pni mnl" pe pnf
where
Cx
200 C, 200 On 100000
di 0.0020, d2 0.000065, d3 0.005, d4 0.0000025, d, 0.01, de 0.000005
(49)
Note that choosing 7 < makes the system of inequalities following descent V Ft d Ω
(48 hold. Using this choice, we get the
31

---

Published as a conference paper at ICLR 2025
V s V GaapTT
d1 ap
E [[
28
+ d2
2nc p 12 22700
ne
+ d1
12n
Cja p 7
pnl
de
6n 2 p22
pnl
cap
V Saap'
2d1 a² 0²0²
28 + [IV](')
12]
n²f
a
6dgc2a2 a
='0O. )
+
(50)
n
2²6
n²6
By this, we proved Lemma 20
O
Theorem 3 (Convergence of MOTEF-VR). Let Assumptions 3 and 5 hold. Then there exists absolute constants Cyp C2S Cy and some such that if we stepsizes 7 C,o,,, X cxn cxn-ta 2 72 n
app" and initial batch size Bunit 2 LF then after at most
T=
T
axpt EF
(13)
nE
iterations of Algorithm
2 holds E
(xxun))
where Xont is chosen uniformly random
from (So. .xT-1). and O suppresses absolute constants and poly- tollrylogait factors.
Proof. We apply Lemma 20 and consider the following:
B Grap
28
2d
C =
?26 a a
220g a 112
12d
odgeza² n2e
D =
n²e
n?e
E = 1.
Unrolling (50) for T iterations we get
Σ
[[(IS((>>
<
+
C
D
D B
BBT
B
1=0
(corr
1/3
( DoLT
(Dor
1/4
Choosing min
E CoPT
gives the following rate
ExG
V
2/3
DDViSyy 3/1
E
[[V]((*)
+
T
BT
B3/2T
B4/3T
eyo
2/3
+
aP3T
n.
2/3 + a
1/3 -1/3p
1/3pp-10
2/3 + a
-1/3
1111p21/3/////11111221/ 2/3 2/3/ 3/4
2/3
T
that translates into the rate in terms of
LTO
2/33
2/13
Σ E [イイ
se o
ap'e2
ngJ
8/33
a
2/3 /3/3/3/3n2//33111
e
2/33
2/3
32

---

Published as a conference paper at ICLR 2025
Note that the last term always dominates the third and fourth terms in the rate. Therefore, the final convergence rate has the following form
| Se² 0
2 a
ETD 2/3
ap'
ng
2/3 22/3p2/33// n2 2//
Note that with the choice
= M VF(X"), H X xx1 get
G S oonn
6 S o n
24 = 22 = 02 = 02 = 0.
di 0² +
d2 2n
nD < FD +
(51)
apuntl
nt.
If we choose the initial batch size Binit
2 IF
1, we get
0²
o²
T S F +
+ i Binit
S 3F"
(52)
ap3 l Binit
D EXPERIMENT DETAILS
D.1 EFFECT OF CHANGING HETEROGENEITY
We perform grid search for the parameters y from 0.01, 0.0010.0..... 7) from the log space from 10-2 to 10-1 and the log space from x 10-4 to 5 x 10-1, For MoTEF we search the momentum parameter À from the same log space as 17 well.
D.2 EFFECT OF COMMUNICATION TOPOLOGY (SYNTHETIC PROBLEM)
To study networks with different spectral gaps, we set n = 400 and construct random regular graphs with different degrees т. We sample the random graphs with degree r (3,3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 7, 10, 13, 16), the resulting inverses of the spectral gaps are around 1/p E (21.41, 18.40, 18.59, 8.24, 8.55, 8.65, 7.92, 5.57, 5.36, 4.03, 4.34,3.76, 2.56, 2.17, 1.99).
D.3 ROBUSTNESS TO COMMUNICATION TOPOLOGY.
Next, we study the effect of the network topology on the convergence of MoTEF. We set 40, A = 0.05, choose batch size 100, and run experiments for ring, star, grid, Erdös-Rènyi (p 0.2 and p 0.5) topologies. For all topologies, we " 0.05, 7 0.5, X 0.01 for a9a dataset and 7) = 0.05, 7 = 0.5, À = 0.01 for w8a. Note that the spectral gaps of these networks 0.012, 0.049, 0.063, 0.467, 0.755 correspondingly.
D.4 HYPERPARAMETERS FOR SECTION 4
For MoTEF we tune stepsize as follows E {0.001, 0.01, 0.05), E [0.1, 0.2,0, e (0.005, 0.01, 0.05, 0.1). For BEER tune the stepsizes in the range 77 E 0.01,,,,,0,, (0.1, 0.5, 0.9}. For Choco-SGD we tune the stepsizes in the range E (0.01, E
(0.1, 0.9). Finally, for DSGD and D2 we choose the stepsize r) = 0.01.
D.5 COMPARISON ON TRAINING CNN MODEL
We additionally provide an experiment where we compare MoTEF against BEER and Choco-SGD on ring and ER = 0.6 topologies using CNN model on MNIST dataset. We use CNN model with two convolution layers each followed by batch normalization, ReLU, and max pooling. The classification layer fully connected. We tune the stepsize for each algorithm from 7 E {0.0001, 0.001, 0.01, 0.13 and gossip stepsize y E {0.1. 0.9). We demonstrate the performance of algorithms in Figure 6 We observe that in both cases MoTEF achieves faster convergence w.r.t. both test accuracy and train loss than competitors supporting theoretical findings.
33

---

Published as a conference paper at ICLR 2025
2.71
To5 Rocugg
Toin LOVE
Test ACCU TOC
Teain
Epocits
Epochs
Epochs
Epochs
ER p = 0.6
Ring
Figure 6: Performance of MoTEF, BEER, and Choco-SGD ring and ER 0.6 topologies in training CNN model MNIST dataset.
01 Noam
Grodent Nomm
8/
Bits
825
a7a
ijenn
a9a
mushrooms
Figure 7: Performance of McTEF and CEDAS in training logistic regression with non-convex regularization on LibSVM datasets.
D.6 COMPARISON AGAINST CEDAS
In this section, we consider the comparison against CEDAS algorithm. We demonstrate the per- formance of MoTEF and CEDAS in the training of logistic regression with non-convex reg- Similarly, we use LibSVM datasets. We tune the parame- 10-1011,, E (10-133 10 10-3 0--3.3 10-3,10-2,3 10-2.3- 10 10-10-1110 33 10 2 E.
ularization used in Section 4.2
ters 7 E (10-3, 3.3 3- 10-3 10,,003-..0 10
100) for CEDAS algorithm, and 30 10-21-1--000 1- 10-10-22 10-1,3. 10-1 100) (0.9,0.8.0.1) for MoTEF. We use Rand-K compressor for CEDAS and Top- for 10,
10 10-2.10 13 3 10 10 1,
MoTEF both with =010, and mini-batch stochastic gradients with batch size 16. We compare the performance of algorithms on the ring topology with n = 10 and regularization parameter 10 averaging over different random seeds. In Figure 7 we demonstrate the communication perfor- mance of CEDAS and MoTEF with the best set of parameters. We observe that the performance of MoTEF and CEDAS is similar on ijennl and mushrooms datasets while MoTEF outperforms CEDAS on a7a and a9a datasets.
34


Reviews:
[{"review_id": "YEawXzs66Z", "reviewer": "Reviewer_rAXz", "summary": "This paper proposes a novel approach MoTEF to achieve an asymptotic rate matching that of distributed SGD under arbitrary data heterogeneity by adding momentum tracking and error feedback technique, solving a theoretical obstacle in decentralized optimization with compression. This paper conducts numerical experiments to illustrate the effectiveness of MoTEF.", "questions": "1. Though the proof is clear enough, I am interested in the insight of the construction of the  Lyapunov function. Adding an overview of the technique before the theoretical results is better.\n2. It is a valuable study. If the author explains my concerns, I would like to improve my score.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. MoTEF achieves the convergence rate matching distributed SGD without strong assumptions, such as bounded gradient or global heterogeneity bound. It is an important improvement in distributed optimization with compression.\n2. MoTEF supports arbitrary contractive compressors (variance-bounded estimate) without unbiasedness.\n3. Extension MoTEF to the stochastic setting can achieve an improved rate with variance reduction.\n4. This paper proposes theoretical analysis under the PL condition.", "weaknesses": "1. The comparison needs to be more clarified and detailed. Especially, the total communication complexity is important in optimization with compression. Most compression algorithms can only reduce the communication overhead of single-step iteration, but cannot reduce the total communication overhead required for convergence. It is necessary to discuss it in detail.\n2. Though the numerical experiments are enough to illustrate the effectiveness of MoTEF, more evidences in practical problems are necessary. For example, a lightweight training on transformers instead of only MLP.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "Grc5ii4y5R", "reviewer": "Reviewer_DwbG", "summary": "This paper studies decentralized stochastic optimization with communication compression. It introduces the momentum tracking technique with error feedback, and achieves the first linear speedup convergence rate under the standard assumptions. Numerical experiments are conducted to validate the theoretical findings.", "questions": "1. Please highlight the challenges in analysis and algorithmic developments compared to the EControl algorithm (Gao et.al., 2024).\n\n2. Please have an in-depth discussion on how the algorithm is developed. Why does the combination of the momentum tracking and error feedback result in the linear speedup rate?   \n\n3. If there is no communication compression and error feedback, does your algoithm reduce to the pure momentum tracking algorithm? How does this momentum tracking algorithm compare with the well-known gradient tracking algorithm in convergence rate?\n\n4. In your Theorem 1, if the network is fully connected, i.e., rho=1, how does your algorithm compare with state-of-the-art centralized compressed algorithm such as EControl, Error-feedback with momentum, and NEOLITHC?\n\n5. The numerical studies are a little bit trivial. In your MLP task, what dataset did you use? Can you evalaute your algorithm over more realistic tasks, such as ResNet on Cifar10?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. It combines momentum tracking and error feedback to attain an effective compressed decentralized algorithm.\n\n2. It achieves the first linear speedup convergence rate for decentralized algorithms with contractive compressors.", "weaknesses": "1. The novelty seems a little bit limited. The main idea and analysis techniques seems to be a direct extension of the centralized algorithm EControl (Gao et.al., 2024) to decentralized settings. \n\n2. The insight behind the proposed algorithm is not well clarified. Why does the combination of the momentum tracking and error feedback result in the linear speedup rate? It is encouraged to discuss how the algorithms are developed and highlight the insight.\n\n3. The dependence on the network topology, as the authors have discussed, is much worse than decentralized algorithms without compression.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "p2zHkGkCUJ", "reviewer": "Reviewer_SzmB", "summary": "This paper proposes MoTEF which achieves faster asymptotic convergence rate on decentralized optimization with communication compression, without using strong assumptions such as bounded gradient, bounded heterogeneity or unbiased compression. A variance-reduction version called MoTEF-VR is also introduced. Ablation studies show that MoTEF enjoys linear speed-up and is robust to network topology. Numerical experiments show that MoTEF performs better than Choco-SGD and BEER.", "questions": "1. Can the authors better illustrate the advantage of MoTEF against CEDAS both theoretically and empirically? For example, in what sense using contractive compression is better than unbiased compression, and whether MoTEF can perform better than CEDAS?\n2. The result for CNN seems missing. Please make sure to include both the results and the implementation details.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This work achieves the fastest asymptotic convergence rates with weakest assumptions.\n2. The presentation is neat and clear.", "weaknesses": "1. The improvement on theoretical convergence result is not significant. Compared to CEDAS, it seems that the only improvement is removing the need for an additional unbiased compressor. To better illustrate this improvement, it is expected to validate whether using contractive compressors are more efficient than using unbiased ones. Otherwise, maybe the authors can compare the full convergence complexity (instead of the asymptotic one only) to address the theoretical improvement.\n2. The numerical experiments are not persuasive enough. The compared baselines are Choco-SGD and BEER, which are in 2022 or earlier, and their convergence rate is clearly worse than SOTA as illustrated in Table 1. In contrast, CEDAS that seems closer to SOTA convergence rate is not compared. Maybe the authors can make the experimental results more solid by adding more baselines like CEDAS and DeepSqueeze.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "CyXBGH5ulc", "reviewer": "Reviewer_DZJC", "summary": "Compression has become a key technique in federated learning to address the primary bottleneck of communication efficiency. This paper introduces a new algorithm, MoTEF, designed for decentralized federated learning with communication compression. The distinctive features of MoTEF include integration with model compression, moment tracking and error feedback altogether.\n\nThe authors provide a convergence analysis showing that MoTEF achieves some of the best expected results, notably without requiring heterogeneity assumptions. They discuss convergence for general non-convex functions and for functions that satisfy the PL condition (a broader condition than convexity). Additionally, they present a moment-based variance reduction variant of MoTEF.\n\nTheoretical insights into the algorithm are explored through comparisons with existing bounds, as well as through numerical experiments.", "questions": "Can you elaborate which of the three trick (GT, moment, error feedback) helps remove the data heterogeneity of the paper?   \n\nCan you simplify the bounds in (11)? In particular, there seems to be a tradeoff on \\alpha among the second term, third term, fourth term. In other words, can you provide a unifying bounds that incorporates these three terms?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "It is impressive that the authors prove a convergence bound for such a complex algorithm without assuming a specific degree of data heterogeneity. Their other assumptions are also reasonable. Although the bound has a suboptimal dependence on \\rho, their experiments demonstrate that the algorithm’s sensitivity to \\rho can actually be much lower, offering valuable insights to the community.\n\nThe presentation is excellent, with comprehensive discussions that thoroughly compare their results to existing work.", "weaknesses": "More explanation to what Algorithm MoTEF actually does can improve the paper. From what is is written, it seems the algotihm just puts togther all the previous tricks into one place.  \n\nOne minor suggestion: while the authors say \"The codes to reproduce our synthetic experiment can be accessed here\", the URL is provided at the end of page 9.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "rD24gE8fGO", "reviewer": "Reviewer_TEjT", "summary": "The authors propose new algorithms for decentralized nonconvex optimization with heterogeneous functions, communication compression, and calls to stochastic gradients.", "questions": "Does it follow from Lemma 1 that in the conditions of Theorem 1, Phi^{t+1} <= Phi^t? This would imply that all quantities in (8) remain bounded (ideally, they would be proved to tend to zero).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "As far as I know, the state of the art as summarized in the paper and Appendix A is correctly presented. The contributions are important, as nonconvex decentralized optimization is a timely topic with a wide range of applications.", "weaknesses": "My main concern is the following. In Table 1, it is stated that convergence is established with respect to E[||nabla.f(x_out)||] for an appropriately chosen x_out, which as its name suggest should be constructed and output by the algorithm. However, the main result, Theorem 1, is established for x_out = bar{x}_t for a random t. The problem is that bar{x} is the average of the local variables x_i, which is not available! So you only prove one half of a valid convergence statement. The second half is that the method achieves a consensus, which in your case corresponds to Omega_3 converging to zero. Reasoning on bar{x} violates the conditions of decentralized optimization, where communication is assumed to be possible only through the network edges, and with compression.\n\nIs x_out = bar{x}_t used in the experiments? In that case this is clearly unfair to the other methods which do not use this unaccessible oracle.\n\nMinor comments on the state of the art:\n* The paper about LEAD by Liu et al. \"Linear convergent decentralized optimization with compression\" has been published at ICLR 2021.\n* The title \"Randcom: Random communication skipping method for decentralized stochastic optimization\" of the paper arXiv:2310.07983 has changed", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": {}}]

Author rebuttal:

Decision: Accept (Poster)