Tight analyses of first-order methods with error feedback
Authors: Daniel Berg Thomsen
Adrien Taylor
Aymeric Dieuleveut
Venue: NeurIPS 2025 poster ()
Keywords: distributed optimization
distributed learning
error feedback
EF
EF21
tight analysis
performance estimation
convex optimization
large-scale machine learning
Primary area: optimization

Abstract: Communication between agents often constitutes a major computational bottleneck in distributed learning. One of the most common mitigation strategies is to compress the information exchanged, thereby reducing communication overhead. To counteract the degradation in convergence associated with compressed communication, error feedback schemes---most notably EF and EF21---were introduced. In this work, we provide a tight analysis of both of these methods. Specifically, we find the Lyapunov function that yields the best possible convergence rate for each method---with matching lower bounds.  This principled approach yields sharp performance guarantees and enables a rigorous, apples-to-apples comparison between EF, EF21, and compressed gradient descent. Our analysis is carried out in the simplified single-agent setting, which allows for clean theoretical insights and fair comparison of the underlying mechanisms.

Tight analyses of first-order methods with error feedback
Daniel Berg Thomsen 1:2+
Adrien Taylor'
Aymeric Dieuleveut
'INII, D.I. Ecole Normale Supérieure, PSL Research University, 75005 Paris, France
CMAP, CNRS, École polytechnique, Institut Polytechnique de Paris, 120 Palaiseau, France
Abstract
Communication between agents often constitutes major computational bottleneck in distributed learning. One the most common mitigation strategies is to com- press the information exchanged, thereby reducing communication overhead. To counteract the degradation convergence associated with compressed communi- cation, error feedback schemes most notably EF and EF?1 EF?!_were introduced. this work, we provide a right analysis of both of these methods. Specifically, we find the Lyapunov function that yiclds the best possible convergence rate for each method wiit matching lower bounds. This principled approach yields sharp performance guarantees and enables rigorous, tween EF, EF21, and compressed gradient descent. Our analysis carried out the simplified single-agent setting, which allows for clean theoretical insights and fair comparison of the underlying mechanisms.
comparison be-
Remark: proof certificates
To consolidate and support our theoretical results, we complement each theoretical statement with analytical or numerical validation. Specifically, we provide certificates of correctness generated either with Computer Algebra System (CAS), using a WolframScript, for symbolic verification, using Performance Estimation Problems (PEP) for numerical validation. CAS enable verification of algebraic identities, while PEP annotations indicate numerical validation of complete statements. These certificates are highlighted the paper using CAS and (reP markers, which are direct links to the corresponding Jupyter notebook WolframSeript in our public GitHub repository.
Introduction
Over the past decade, distributed optimization has become cornerstone of large-scale machine learning. This shift driven by major increases in the size of models and training data, as well as increasing societal concerss about data ownership and privacy. Ultimately, solutions in which training is distributed across network of agents, each retaining its own local data, under the coordination of central server, have emerged one of the most natural and efficient solutions this problem [1, 2].
"Correspondence daniel. www.bbehraeeeeeeeeeeeeeeee "While these certificates not replace the mathematical proofs presented in paper, they serve an additional layer of transparency and error checking, analogous to unit tests software development. This practice provides reproducible, independently verifiable basis for our theoretical claims, thereby reducing the risk of oversights in complex derivations.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Formally, the goal is to solve the following minimization problem:
f(x) [(x)= (())=-_>m)
Σ M(x))
min
ZER
Classical methods such as distributed gradient descent and its stochastic variants achieve linear speedups in iteration complexity with respect to the number of agents, However, they often suffer from significant communication overhead, as gradients or model updates must be exchanged frequently over heetwwdth-liiieee channels [3-5]. As the scale of models keep increasing, this communication bottleneck has been identified early on as a critical limitation, prompting the development of methods aimed at reducing communication costs. Two main strategies are favored: scarcely communicating with the central server, known as local iterations [see e.g. 1, 6] and transmitting compressed updates. which aim to reduce the size of the exchanged information. Compression mechanisms can be applied to reduce communication either from agents to the server [3, 7-14] or from the server to the agents [15-23]. This paper focuses on methods using compression operators, which encompass variety of strategies, including selecting only a fraction of the weights to be transmitted (e.g., the top K coordinates [8]) or communicating low- cowpprecision updates via quantization [7].
Algorithm 1 Compressed gradient descent (CGD)
1: initialization: wo E TR:d 1] >
2: for k = 0, 0,1........ .N do
3: Agent i [ni] compresses (((x and communicates m = (.
4: Server updates Tb41 Ik 17 4 E. m
(4)
5: end for
Formally, a compression operator is a possibly random mapping C X - X, such that C(X) can be encoded (almost surely or on average) with a lower number of bits than X. The most natural algorithm leveraging communication compression with centralized server is the compressed gradient descent algorithm (CGD), which is described in Algorithm 1. The main idea is to perform distributed gradient step, with the compression operator C applied to the gradient of each agent before communication. Although this compression scheme reduces the communication cost, it comes at the expense of non-convergence in any practical setting [24].
To assess the general impact of compression schemes on the rate of convergence, one typically leverages the fact that these compressors all satisfy generic assumptions. These include unbiasedness, i... B[((x)] x for any x E X, together with relatively bounded variance, which states that B[][C(x) [²] < w||x||/ 2 for any x E X [7, 11, 25-27, 12, 28, 19, 20, 29-31], or contractive- nexs [32-34, 21, 24), defined as follows:
Assumption 1 (Contractive compression operator). The compression operator a stochastic operator such that, for some E [0, 1).
for all x E R", - [[Ix-c(x)1]] < <<|00]2
(2)
The standard way to improve CGD leverage the asymmetry of information: each agent has access to the exact gradient before compression and can therefore track the discrepancy between the exact gradient and the transmitted (compressed) message. This discrepancy can be stored and used as a correction term in subsequent iterations a principle that lies at the heart of error feedback techniques. The most basic mechanism used is known as classic error feedback (EF), where each agent stores the difference between the truc gradient and its compressed version locally, and incorporates this error into the next round of communication. This method, outlined in Algorithm 2, was first introduced in [3] and later analyzed in [32, 11, 10, 8, 35]. Notably, this method converges in many practical settings, effectively addressing the problem of non-convergence for CGD.
More recently, a variant of the classic error feedback mechanism, known as EFS1 was introduced by Richtárik et al. [14], and is presented in Algorithm Unlike classic error feedback, EF focuses on communicating a gradient estimate that is more robust to the variance observed in gradients received from different agents around the minimum of finite sum objectives. This method has since been extended in several directions [c.g. 36-38..

---

Algorithm 2 Classic error feedback (EF)
1: initialization: zo E IR 1) 0, co for i = I.....
2: for == 0,
NN do
3: Agent i E [n]] compresses
c + +1/VSi(( and communicates m = C(ek + +([[((zz))
4: Agent i [n]] updates c
ck + V f( C(ek v
(6)
5: Server updates IK+1 Jk E m
(8)
6: end for
Algorithm 3 Error Feedback 21 EF
1: initialization: 20 E R²; step size 17 > 0; df¹ = c(Vo(( for i = 1,... 1,..., n:;
2: for == 0, 1,2,..., N do
3: Server updates I - Ih 11 -1 (
4: Agent E [xx] compresses (zi((2211 ) and communicates mi := C(V C(V.
5: Agent i [n]] updates d dk m (x)
6: end for
Error feedback techniques widely regarded highly effective, and EF described "com- pression for free" as early as 2019 [10]. Despite that, and the abundant literature on the topic, the precise impact of error feedback techniques performance remains difficult assess. Com- parison is complicated by the diversity of settings under which methods are analyzed: different function classes (smooth, convex, or nonconvex), range of algorithmic enhancements (acceleration, adaptivity, variance reduction, etc.), and variety of performance measures (different Lyapunov functions) [23, 39, 38, 37, 40-42]. While some works provide insightful examples -e.g.....-................... Beznosikov et al. [24] show that classic error feedback effectively addresses the limitations of CGD in distributed settings- -aan others simply propose Lyapunov function and establish an upper bound without demonstrating its tightness. As a result, claims about "compression for free" are often based on comparisons between potentially loose guarantees, which may not reliably reflect real algorithmic performance. The length and complexity of the proofs involved typically make it difficult to ensure the tightness of the results, and most proofs are constructed in an ad hoc manner. Consequently, it is difficult to determine which methods are actually worst-case optimal based on upper bounds whose tightness is not always assured.
As result, even remarkably simple questions remain only partially answered:
What the optimal convergence rate that each method can attain? Given optimization setting, what method should we choose? How should each method be optimally tuned?
Our goal is provide definitive answers parts of these questions. In this paper, take complementary perspective to the existing literature and offer a tight, principled comparison of the three methods. Specifically, derive their optimal tuning, identify optimal Lyapunov function for each method, and compute the exact optimal convergence rate for any Lyapunov function within class of candidate Lyapunov functions.
To make this comparison sharp and transparent, we adopt a deliberately simple yet representative setup: we consider smooth and strongly convex functions in the single-agent setting (n 1). While simple, this regime is widely recognized as a crucial stepping stonc-not only for building intuition, but also as its theoretical contribution [e.g.. 32, 10]. The single-agent setting is also of independent interest: in the field sparsity-aware neural-netwond training. update methods have been shown correspond to feedback [43]. In this context, tightness means that identify the best possible Lyapunov function within a given class and compute the exact worst-case convergence rate over the class of problems considered.
Our methodology draws on the performance estimation framework [44, 45], which enables the numerical derivation of exact convergence rates for wide range of first-order methods. In particular,

---

recent advances [46, 47] demonstrate how to automatically search for optimal Lyapunov functions. While these approaches are primarily numerical, we build upon insights from their underlying proof structures [48] to derive new analytical results.
Contributions. This work makes the following contributions:
1. From a methodological perspective, this paper shows how to apply the performance estimation framework to algorithms from the federated learning literature that incorporate compression schemes. By leveraging this methodology- both analytically and numerically this work paves the way for a more precise and reliable understanding of federated and distributed learning methods.
2. This work provides tight analysis of EF and E and compare them with compressed gradient descent in the single-agent setting, on L-smooth, jı-strongly convex functions. particular, we give an analytical formula of the best possible contraction rate, by analyzing an optimal Lyapunov function within class candidate Lyарunov functions defined in Definition 1. Furthermore, we provide the optimal tuning for the step size in both those algorithms.
3. We demonstrate that those rates are achieved, proving that the analysis is tight.
4. We conclude that the complexities of EF and EF are perfectly identical this particular setting. Moreover, CGD outperforms both methods
in terms of the range of settings where converges and in terms of the optimal convergence rate achieved.
5. Finally, we contribute to the process of deriving simple Lyapunov functions for first-order methods, and extend known results for fixed-step methods to the setting of methods using compression.
Paper outline. The rest of the paper is organized as follows. In Section 2, we provide background on the relevant existing results for CGD, EF, and EF221 We also provide the necessary background on the techniques from the performance estimation literature needed to outline the methodology we use, as well as the definition of the classes of Lyapunov functions used. Section presents the main contribution of the paper: tight convergence guarantees for CGD, EF, and EF?1 along with matching lower bounds. Section details the methodology we use to derive the results, and provides references to the formal results required to justify this approach. It also contains a number of numerical results that illustrate the equivalence between FFF and EF21, and performance characteristies of the three methods. Section 5 summarizes the results of the paper and provides a discussion of the results in relation to the points brought up in the introductory section.
Notations:
We denote S the symmetric matrices, and denote 84 the set of positive semi definite matrices. For any two matrices A Se and B E gd, we denote A @ B the Kronecker product.
2
Backkround
In this section, we briefly overview relevant existing results from the field of distributed optimiza- tion, the necessary background on the performance estimation framework, provide the rest of the assumptions we will need, and specify the notion of Lyapunov functions used in this paper.
2.1 Theoretical results on CGD, EF, EF21
In the single agent case, we leverage the equivalence between compressed gradient descent (CGD), under Assumption 1 and the inexact gradient method with relatively bounded gradients. CGD corresponds to the particular case of Algorithm with n = 1, and relatively bounded gradients means that for any x, the oracle queried at point x outputs value g such that ||g ff(x) < V f())]2 Various notions of gradient approximation have been studied [49-51], and tight analysis for relatively bounded gradients was given in [52]. Specifically, authors have shown that the inexact gradient method then enjoys tight convergence guarantees for any step size 1) > O. with respect to the functional residual, Euclidean norm distance to the solution and gradient norm. However, CGD is known to diverge when applied using stochastic gradient oracles, and to non-smooth functions [10]. Interestingly, is also known to diverge in the multi- worker setting [24]. Studying CGD is important in its own right, because when the compression operator is chosen as the sign function, and the
algorithm is applied the stochastic setting (i.e., signSGD), there is a connection Adam both in the convex [53], and non-convex setting [54].

---

Convergence rates for EF have been established with strongly convex [32], quasi-convex and non- convex [10. 35] functions, and using stochastic gradients. Richtárik et al. [14] study EF in the multi-worker setting, with (potentially) randomized compression operators. They establish a O(k-!) convergence rate on Lipschitz smooth functions, and a linear rate under the additional assumption that the functions satisfy the Eojaasieiizz inequality. These results are obtained using a Lyapunov function; however, without tightness guarantees-neiinn neither for the choice of Lyapunov function, nor for the convergence rate itself. Extensions of EF have been proposed, including adaptations to stochastic gradients [23], and the introduction of momentum term to improve sample complexity in the stochastic setting [36].
2.2 Performance estimation
Performance estimation tools [55, 56, 45] enable obtain tight (i.c., exact worst-case) numerical guarantees on convergence rates for various choices of Lyapunov functions. To do so, the estimation of the worst-case rate is formulated as a semidefinite program (SDP), which is then solved numerically using standard solvers such as MOSEK [57]. The resulting numerical values approximate the exact worst-case rate of an algorithm over class of functions, and should not be confused with quantities that depend on specific data, initial points, or problem instances.
This framework has been made accessible through software packages in both Python [58] and Matlab [59], enabling researchers to easily apply these tools. Advanced performance estimation techniques based on the dual formulation of the aforementioned SDP have been developed within this framework to construct optimal Lyapunov functions for first-order methods [46, 47, 60]. Particularly relevant is the approach of [46], which formulates the search for quadratic Lyapunov functions as a feasibility problem with a candidate contraction rate. By performing bisection on this rate, the method identifies the smallest contraction rate for which valid Lyapunov function exists.
Another relevant line of work we leverage to discover the analytical form of the Lyapunov functions lies in the field of symbolic regression, which aims solve supervised learning tasks over the space of simple analytic expressions. Recent advances use genetic programming to search this space, and software packages have been developed in both Python and Julia [61].
2.3 Definitions & Notation
We have already introduced the notion of a contractive compression operator in Assumption 1. To position our contribution within the broader literature we now specify that our analysis is restricted to the setting of smooth, strongly convex functions:
Assumption 2. The function f is L-smooth, i.e., for all x, E Rd, we have
fly) < f(x) + (Vf(x), y 2) + L lly - 2012. 2
Assumption 3. The function f is p-strongly convex, for all x. y E IR,, we have
f(y) > f(x) (Vf(x), - x) + lly - 112 x1
We will use the notation F,,, to denote the set of smooth, strongly convex functions with parameters and L. We will denote x = L. the condition number. For any objective function f E FpLLL we denote r. arg min f its minimizer, and f- min f (x: its minimum value.
Lyapunov functions. We now formally define the class of Lyapunov functions under consideration.
We formally denote M : 1x x Id x F Rexd x Rd a first-order method acting on a set of functions F, an integer E N. Such method, given a function f E F, is applied to an initial state Eu E I and iterate In E Rd and generates a sequence h of states, and a sequence {xx ) of iterations. The states represent information summarizing the current point in the optimization trajectory that the algorithms may depend on beyond the current iterate- example, error-related quantities in error feedback algorithms. The integer é is thus typically small, from 0 to in general. The specific states used in this paper are all specified in Subsection 3.1.
Definition (Candidate I. Lyapunov function). A function V Rexdd x RRd - R. is called a candidate Lyapunov function for f if it satisfies the following conditions:
5

---

1. (Non-negativity) V(G,2; 2; > 0. for any Ç E Rexd R
2. (Zero fixed-poini V(S, 2;; 0 if and only if 2, and { E. for unique &. Rexd
(Meaningfullyy lower bounded) there exists a positive semidefinite matrix A E S and scalar > such that V(S, x; > (5 T (A & [a)(E - (.) a(f(()) -
and Tr(A) +
The lower bound in item of our definition requires some justification: it ensures that the Lyapunov function provides control over meaningful quantities in optimization, such as the distance to the fixed point, gradient norm, algorithm-dependent quantities and the functional residual.
The class of candidate Lyapunov functions is thus given by
Ve ((P.p) E S x R+ Tr(P) + p = p=13.
(3)
For any (P.p) E VE we denote V(Pp,) the Lyapunov functions of the form:
(erm(E f) = - T & La)(5 5.) + p((()))-
(4)
We seek candidate Lyapunov functions V P Exd x Rd x F - IR that satisfy the recurrence
V(E++1, #641: f) & ((EK f);
(5)
for some constant and for all O, uniformly over F. Finding the optimal Lyapunov function within a parameterized class, for a method M, then amounts to solving the following problem:
(E, V(P vo; (f1, M(Eo }.
p² (M)
min (P-p)
max SEF (60.20)
(6)
Note that we set & = 0 in order to have a guarantee that is valid for all x E Rd.
Main results
In this section, we provide answers to the questions stated in the introduction for setting. We begin by showing some numerical results on the performance of each method, and then provide the precise statements of all of our theoretical results.
3.1 Numerical performance of all methods
In order to compare EF and 2F with the performance CGD, we first need to specify the state-variables under consideration when analyzing each method. Those are given given by:
Tk (((ak) C(ex + v f(xw)) EN
TK vf(xx) ((nV)(
IK ( dp
CGD Sk
<EF
&
EF
(7)
where all variables are defined as in Algorithm 1, Algorithm 2 and Algorithm 3, respectively, Note that all numerical results this article are using deterministic compression operators.
We are now ready to present the numerical results on the performance of each method. Figure shows contour plots of the contraction factor for each method. That is. for fine grid of both the step size 77 in Algorithms 1 to 3, and the parameter in Assumption 1, we numerically compute the value of the best possible worst-case contraction rate terms of our class of candidate Lyapunov functions, over Fu,LL, as given by (6). A darker blue point indicates a stronger contraction p² (M) (i.e., better rate). A red point indicates that the method is non-convergent for that choice of (c, 7). We observe that, although the results are purely numerical at this stage, they indicate that EF and EFS1 exhibit identical performance in our setting. This numerical equivalence is supported by Table the maximum absolute difference between contraction factors for EF and ET is the order of 10-5 to 10-7 This first fact is a very surprising observation. Indeed while F.F and 2 are known to be identical in the very specific case of using deterministic positively homogeneous and additive

---

R
10
K
2
K
K
Absolute error
4.34c-07 6.02e-07
1.21e-06
Absolute error
1.14c-06 3.90c-07
5.11c-06
Table I:
Maximum absolute difference of con- traction factor for EF and EF computed over grid of [0.01, 0.99] and 1 E [0.01, 2 for 1, and varying μr.
Table Maximum absolute difference of con- traction factor for CGD when allowing any com- bination of terms in our Lyapunov function, com- pared the contraction achieved by the func- tional residual. Same grid as Table
Ltp
compression operator [14, see Section 4.2], EF and EF remain grounded in fundamentally different motivations at first sight: on the one hand, EF accounts for the errors introduced by the compression step, while the other hand, EF subtracts a control variate from the gradient prior to compression. Proving that the best possible convergence rate they can obtain, for any tuning c, 1). is similar (but achieved for a different Lyapunov function) was, the best of our knowledge, never established in the literature. thus constitutes a significant step towards better understanding their connections.
A second observation can be made from those plots: the region of non-convergence is by far larger for EF and EF than for CGD. In particular, there exist multiple tunings, for which incorporating any of the two types of error feedback, actually prevent convergence.
While given for single (μ, L) in Figure 1 and Table similar results hold for all values of (μ, L) that were tried numerically, and several examples are given in Appendix D, along with details of the numerical experiments, including the computation regions of non-oonvereence
Furthermore, we tune each algorithm by picking the optimal step size for each method. We compute the rate inf,, pa (,M,), for M {CGD, EF, EF?),, where M,, corresponds to the method with step size Results are shown in Appendix B for three values of K, namely 2, 4, and 10. In each setup, for every level of compression, CGD achieves rate which is strietly better than EF and EF21 In Appendix B.1, we also provide a symbolic certifiate this fact. These results challenge the prevailing intuition that error feedback ensures convergence comparable to that of uncompressed methods, and even demonstrate that in the single agent and deterministic gradient regime, error feedback is actually always detrimental convergence.
Finally, we note that the functional residual constitutes an optimal Lyapunov function for CGD, shown in Table 2. This result is not particularly surprising, given that tight analysis of the functional residual with the optimal step size was previously established for inexact gradient descent by De Klerk et al. [52]. That work also demonstrated the tightness of this rate?. For 2F Richtárik
2 Following same line of reasoning as our remark on the tightness of our Lyapunov functions in Section 5, we can then show that the functional residual is an optimal Lyapunov function for CGD.
0
CGD
EF
EF21
1.5
1.0
0.5
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
Figure 1: Single row of contour plots showing performance of CGD, EF, and EF as function of step size 7) and compression parameter c, with regions non-convergence marked in red. The regions of non-convergence were computed using PEPit by finding cycles of length 2.

---

et al. [14] proposed another Lyapunov function than the one used here. In Appendix D.5, Figure 12 we compare the complexities of an optimally tuned version of their Lyapunov function with the class- optimal Lyapunov function numerically. Further comparison of rates can be found in Appendix B. In Appendix B.2, we prove that our rate is strictly faster than the the aforementioned rate for FJF21
In the next two sections, we provide analytical results on EF and EF respectively.
3.2 Exact convergence rate and optimal tuning for EF
We begin by stating the main result of this section, which is tight rate of convergence for EF. Theorem 1. CAS
PEP
Consider running Algorithm 2, i.e., EF, with compression operator C satisfying Assumption 1 for some E [0, 1] on any function satisfying Assumptions and Let the step size be given by
17' n²= L (1++))
2
(ITVe)
(8)
Then, we have that
1" p'(EFrrr) = ve + (1 (L)
(9)
where
x= 1 (1- ( p) (1 VO 11)- 16 (I+Vo)2
Ve
(10)
A Lyapunov function achieving the rate in (9), with EEF defined in (7), given by
V(5 EF 22 f) = 1 xx 2(x x.) Te e+ (1+12) ||ell2 = =1|x x I. -A- - eel2
Ve |lell (11)
Finally, the step size in (8) is worst-case optimal for EF: V1j > O. we have p² (EF,,) > 0r (EF,,))
Importantly, (9) shows that the rate is tight; that is, there exist f E Fa,L and p) V2 for which the rate is exactly achieved. Since the lower bound also applies to any other performance measure in our state space, our performance measure optimal. This is formally demonstrated the proof provided in Appendix C.I. The proof was written using deterministic compressors, but the same guarantees hold under expectation with stochastic compressors as is explained in Appendix C.3.
For completeness-ann and to support both our theoretical results and the tightness of the numerical results obtained through performance estimation we provide additional figures comparing the empirically observed optimal step sizes for worst-case instances with our theoretical step size ni", across different values of e and μ/ L. These results are shown in Figure 11, located in Appendix D.4. The numerical and analytical values match up to numerical accuracy.
3.3
Exact convergence rate and optimal tuning for E.P21
We now state main result on the EF21 algorithm, which is also tight.
Theorem 2.
CAS
PEP
Consider ranning Algorithm 3 with compression operator satisfying Assumption 1 for some E [0, on any function satisfying Assumptions and Let the step size given by 11" in (8). Then,
0² ('EF21 n..) = >00==ppp0 p=FFF
(12)
A Lyapunov function achieving the rate in (12) is given by
V(GBF . f) == (1 + Ve) || 2g + = - -| ve- ||a||
(13)
Finally. the step size '7t is worst-case optimal for this algorithm.
Remark 1. The explicit rate for EF and EF21 can be written as
1 ("
[I-Ve+ (+=+'[I-=e
[
Va+ Ve16 (K - 1)2²
p p=
(14)
where iS = T./p. A detailed comparison between this and the existing rate for F. under the Lojasiewicz inequality [14] is provided in Appendix B.
8

---

The proof of this theorem is given in Appendix C.2 and assumes deterministic compressors, but the same guarantees hold under expectation with stochastic compressors, as explained in Appendix C.3.
This second theoretical result analytically confirms the surprising numerical observation from Subsec- tion 3.1, illustrated in Figure 1: EF and EF have the exact same optimal guarantee. Furthermore, the optimal step size is also the same, and can also be argued to be worst-case optimal in our setting using the same arguments as in Section 3.2. However, the optimal Lyapunov function is very different.
3.4 Tightness over multiple iterations and choice of state variables
A natural question arising from the above analysis concerns the tightness of the Lyapunov functions provided in Theorems and 2 over multiple steps. Specifically, for K > 2, we investigate whether the convergence rate of method M E EF, EF21, CGD can be improved by analyzing M the method run over K iterations, defined as follows:
1/K
M xK)) = M (Eo. xos 10: 1)) V(P.p) (En, (E0, z0;
Pk (M) =
min (Pi)ee
max fET (Ko.F))ER X
We provide numerical answer to that question in Appendix D.2 for all algorithms discussed in the paper, showing that the analysis of the single-state Lyapunov functions used in this work are tight even if we consider multiple iterations. To that end, we plot the worst-case contractions for multiple iterations computed using PEPit [58], on the optimal Lyapunov functions given by (11) and (13).
Lyapunov Tightness. To prove that the Lyapunov functions we in Theorems and are tight, one has to show that the rate of convergence for any other candidate Lyapunov function from our class is lower bounded by the rate we obtain. We consider a quadratic function, used in the latter sections of our proofs to prove tightness: asymptotic expressions for all the state-variables are the same, up to an veraaioonindeeendeent constant. Consequently, when computing ratios between any set of Lyapunov functions, these constants cancel out. The only thing remaining is the term that actually depends the iteration count, which exactly equal the rate given in Theorems and 2.
4 Methodology
We now present the methodology used to obtain the results in Section 3. The approach builds on the framework developed by [46]. We extend it to cover methods using deterministic compression operators under Assumption in Appendix A. Obtaining the proofs of Theorems I and 2 required combination of advanced performance estimation techniques (finding optimal Lyapunov functions), several tricks, well as symbolic computation and symbolic regression frameworks.
To solve problem (6), we begin by addressing the inner maximization problem for fixed contraction factor p. This amounts to checking the feasibility of a semidefinite program, detailed in Appendix A. We then apply bisection on p to identify the smallest admissible contraction factor. However, the Lyapunov function given is rarely unique, and most solutions obtained numerically vary significantly with problem parameters such as the compression factor e. To address this, we use rank minimiza- tion heuristies-specffeee specifically, the logdet heuristic [62]. This enables one to obtain unique set of structurally simpler, low-rank Lyapunov functions. Finally, we proceed by climinating redundant coefficients in the matrix P and the scalar p. to arrive at the concise forms presented in Section 3. At the end of this process, the Lyapunov function coefficients were found to be mutually dependent, reducing the problem to identifying closed-form expression for any one of them. To estimate such a coefficient, we applied symbolic regression using the PySR Python package [61]. This approach proved highly effective at finding simple yet optimal Lyapunov functions. To arrive at simple and readable proofs, we leverage the computer algebra system of Mathematica [63].
We wish to emphasize that the combined use of log-det heuristics, symbolic regression, and computer algebra system turned out to be highly effective at solving this problem, and we believe has broad applicability to other problems in machine learning.

---

Conclusion
In this paper, we provided tight analyses of EF and EF21 using Lyapunov functions, with guarantees on both the Lyapunov functions themselves and the convergence rates achieved. Notably, both algorithms exhibit the same convergence rate in our setting, and through a remark made in the discussion below, this gives us tight rates for any of the candidate Lyapunov functions we considered in our class. We also observed that their performance is strictly worse than that of compressed gradient descent-an outcome that, we believe, challenges the intuition of many in the field.
Our analysis is confined the single-agent setting, both interesting problem its own, and as source of intuition for the multi-agent case. CGD cannot serve as baseline in the multi-agent setting it fails to converge with more than one agent [24]. contrast, EF21 was specifically designed to improve convergence over EF in the multi-agent setting. Yet, its convergence rate in the single-agent case matches exactly that of EF. The findings of this paper raise two compelling questions:
Does the performance EF EF and EF²1 differ in the multi-agent setting? Are there more effective error compensation mechanisms yet be discovered?
We leave these questions for future work and conclude by emphasizing that the methodology used likely applicable to a broad range of problems in optimization for machine learning. We look forward to seeing it extended and applied in future research.
Acknowledgments and Disclosure of Funding
We would like thank Si Yi Meng, Jean-Baptiste Fest, Abel Douzal, and Lucas Versini for providing helpful feedback on an early draft of this paper. D. Berg Thomsen and A. Taylor are supported by the European Union (ERC grant CASPER 101 (62889). The work of A. Dieuleveut is partly SCAI, and Hi!Paris FLAG project, PEPR Redeem. The French government also partly funded this work under the management of Agence Nationale de la Recherche as part of the "France 2030" program, references ANR-23-IACL-0008 "PRIAI]RIE-PSAI", ANR-23-PEIA-005 (REDEEM project) and ANR-23-IACL-0005.
supported by W1R-19-CHIA-00002-01hhhe
10

---

References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- Efficient Learning of Deep Networks from Decentralized Data. In International Conference on Artificial Intelligence and Statistics (AISTATS), April 2017.
[2] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D Oliveiraa, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adria Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and Open Problems in Federated I Learning. arXiv: 1912.04977 [cs, stat], December 2019.
[3] 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 Annual Conference of the International Speech Communication Association, 2014.
[4] Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), 2014.
[5] Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In Annual Conference of the International Speech Communication Association, 2015.
[6] 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 on Machine Learning (ICML., 2020.
[7] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: coammunication-Efffcce SGD via Gradient Quantization and Encoding. Advances in Neural Information Processing Systems (NeurIPS), 30, 2017.
[8] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli. The Convergence of Sparsified Gradient Methods. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018
[9] K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik and. Distributed learning with compressed gradient differences. Optimization Methods and Software, 2024.
[10] 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 (ICML), 2019.
[11] Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization. In International Conference on Machine Learning (ICML), 2018.
[12] Samuel Horvath, Chen- 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.
[13) Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik. Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization. In International Conference on Machine Learning (ICML), 2020.
[14] Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. In Advances in Neural Information Processing Systems (NeurIPS), 2021.

---

[15] Ibrahim El Khalil Harrane. Rémi Flamary, and Cédric Richard. On reducing the communication cost of the diffusion Ims algorithm. IEEE Transactions on Signal and Information Processing over Networks, 5(1):100-112 2018.
[16] Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. DoubleSqueeze: Parallel Stochas- tic Gradient Descent with Double-past Error- certo--ommpesateed Compression. In International Conference on Machine Learning (ICML), 2019.
[17] Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan. A Double Residual Compression Algorithm for Efficient Distributed Learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[18] Shuai Zheng, Ziyue Huang, and James Kwok. Communication--lfiicii Distributed Blockwise Momentum SGD with Error-Feedback, In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[19] Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous settings for distributed federated learning with partial participation: tight convergence guarantees. arXiv:2006. 14529 [cs, stat), 2020.
[20] Constantin Philippenko and Aymeric Dieuleveut. Preserved central model for faster bidirectional compression in distributed settings. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[21] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtarik. Linearly Con- verging Error Compensated SGD. In Advances in Neural Information Processing Systems (NeurlPS), 2020.
[22] Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and Communication--ffiee Federated Learning From Non-ii.d. Data. IEEE Transactions on Neural Networks and Learning Systems, pages 3400-3413, 2019. ISSN 2162-2388. doi:
[23] Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback, October 2021.
arXiv:21 10.03294 [cs, math].
[24] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On Biased Compression for Distributed Learning. Journal of Machine Learning Research, 24(276):1-50, 2023.
[25] Sélim Chraibi, Ahmed Khaled, Dmitry Kovalev, Peter Richtárik, Adil Salim, and Martin Takáč, Distributed Fixed Point Methods with Compressed Iterates. a7X1v:1912.09925 [cs, math], December 2019.
[26] Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[27] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. FedPAQ: A Communication-Efiin Efficiien Federated Learning Method with Periodic Averaging and Quantization. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[28] Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtarik. Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time- Varein Networks. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[29] Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated Learning with Compression: Unified Analysis and Sharp Guarantees. In International Conference Artificial Intelligence and Statistics (AISTATS), 2021.
12

---

[30] Zhize Li and Peter Richtárik. CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[31] Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv: 06573 [cs, math], June 2018.
[32] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with Memory. In Advances in Neural Information Processing Systems (NeurIPS). 2018.
[33] Nikita Ivkin, Daniel Rothschild, Enayat Ullah, Vladimir Braverman, Ion Stoica, and Raman Arora. Communication--effciient Distributed SGD with Sketching. Advances in Neural Informa- fion Processing Systems (NeurIPS), 2019.
[34] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication. In International Conference on Machine Learning (ICML), 2019.
[35] Sebastian U Stich and Sai Pranceth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. Journal of Machine Learning Research, 21:1-36, 2020.
[36] Ilyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves crror feedback! Advances in Neural Information Processing Systems (NeurIPS), 2023.
[37] Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Com- pression. In International Conference Machine Learning (ICML), 2023.
[38] Dmitry Makarenko, Elnur Gasanov, Rustem Islamov, Abdurakhmon Sadiev, and Peter Richtárik. Adaptive Compression for Communication--ffiiiee Distributed Training. arXiv:2211.001 [cs), October 2022.
[39] Peter Richtarik, Igor Sokolov, Elnur Gasanov, Ilyas Fatkhullin, Zhize Li, and Eduard Gorbunov. 3PC: Three Point Compressors for Citmmunncaatio--fffiiiennn Distributed Training and a Better Theory for Lazy Aggregation. In International Conference on Machine Learning (ICML), 2022.
[40] 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. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[41] Yujun Wang, Lu Lin, and Jinghui Chen. Communication-Coppressse Adaptive Gradient Method for Distributed Nonconvex Optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
[42] Ron Dorfman, Shay Vargaftik, Yaniv Ben-Itzhak, and Kfir Yehuda Levy. DoCoFL: Downlink compression for cross-device federated learning. In International Conference on Machine Learning (ICML), 2023.
[43] Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. In International Conference on Learning Representations (ICLR), 2020.
[44] Yoel Drori. Contributions to the Complexity Analysis of Optimization A PhD thesis, Tel-Aviv University, 2014.
[45] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization. SIAM Journal Optimization, 2783):1283-1313 2017.
[46] Adrien Taylor, Bryan Van Scoy, and Laurent Lessard. Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees. In International Conference on Machine Learning (ICML) 2018
[47] Manu Upadhyaya, Sebastian Banert, Adrien B. Taylor, and Pontus Giselsson. Automated tight Lyapunov analysis for first-order methods. Mathematical Programming, 209(1):133-17) 2025.
13

---

[48] Baptiste Goujaud, Aymeric Dieuleveut, and Adrien Taylor. On Fundamental Proof Structures in First-Order Optimization. In Conference on Decision and Control (CDC). 2023.
[49] Alexandre d' Aspremont. Smooth Optimization with Approximate Gradient. SIAM Journal on Optimization, (113):117-11183 2008.
[50] Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2014.
[51] Mark Schmidt, Nicolas Roux, and Francis Bach. Convergence Rates of Inexact Proximal- Gradient Methods for Convex Optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2011.
[52] Etienne De Klerk, Francois Glineur, and Adrien Taylor. Worst-Cass Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation. SIAM Journal on Optimization, 303))2053-2082. 2020.
[53] Lukas Balles and Philipp Hennig. Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients. In International Conference on Machine Learning (ICML), 2018.
[54) Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed Optimisation for Non-Convex Problems. International Conference on Machine Learning (ICML), 2018.
[55] Yoel Drori and Mare Teboulle. Performance of first-order methods for smooth convex mini- mization: a novel approach. Mathematical Programming, 145(1):451-492, 2014.
[56] Adrien Taylor, Julien M. Hendrickx, and François Glineur. Smooth strongly convex interpo- lation and exact worst-case performance of first-order methods. Mathematical Programming, 16:(1-2):3773345, 2017.
[57] MOSEK ApS. MOSEK Optimizer API Python / 11.0.1, 2025. htthttss://docs. mosek. com/11. httpp/oooapiiieeee...eeeeeeeeeee hnml..
(58) Baptiste Goujaud, Céline Moucer, François Glineur, Julien M. Hendrickx, Adrien B. TTaylor, and Aymeric Dieuleveut. PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python. Mathematical Programming Computation, 16(3):337-367, 2024.
[59] Adrien B. Taylor, Julien M. Hendrickx, and François Glineur. Performance estimation toolbox (PESTO): automated worst-case analysis first-order optimization methods. In Conference on Decision and Control (CDC), 2017.
[60] Adrien Taylor and Francis Bach. Stochastic first-order methods: non-asymptotic and computer- aided analyses via potential functions. In Conference on Learning Theory (COLT), 2019.
[61] Miles Cranmer. Interpretable Machine Learning for Science with PySR and SymbolicRegres- sion.jl. arXiv:2305.00588 [physics), May 2023.
[62] Maryam Fazel, Haitham Hindi, and Stephen P. Boyd. Log-det heuristic for matrix rank minimization with applications Hankel and Fuclidean distance matrices. In American Control Conference (ACC), 2003.
[63] Wolfram Research, Inc. Mathematica, Version 14.2. URL wwtp://wwwwwwofr.....m com/ mathematical Champaign, II, 2024.
[64] Oran Gannot. frequency-domain analysis of inexact gradient methods. Programming, 194(1-2)995-10116 2022.
Mathematical
[65] Etienne De Klerk, François Glineur, and Adrien B Taylor. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters, 11:1185-1199, 2017.
[66] Baptiste Goujaud, Aymeric Dieuleveut, and Adrien Taylor. Counter-examples in first-order optimization: constructive approach. IEEE Control Systems Letters, 2023. (See arxiv 2303 10503 for complete version with appendices).
14

---

Organization of the appendix
A Feasibility problems with compressors
15
B Rate comparison
22
C Missing proofs
25
D Additional numerical results
29
Remarks on the importance of proof certificates
34
This appendix provides additional content and details complementing the paper. In particular, Appendix A details the general methodology used search for Lyapunov functions. The complete missing proofs for the main results of the paper are presented in Appendix C. Appendix D presents additional numerical results that informally motivate few choices made in the paper and provide numerical validation of our claims. Finally, Appendix E discusses our choice of annotating this article with proof certificates.
A Feasibility problems with compressors
This section presents the methodology used to search for Lyapunov functions. In nutshell, we formulate the Lyapunov search problem as quasi-convex optimization problem involving linear matrix incqualities. Those problems typically solved through the use of iterative procedure involving a binary search with semidefinite solvers-we use MOSEK [57] throughout. The main steps taken here be viewed generalization of the procedure proposed in [46] to first-order methods using compression, in particular Algorithms and 3. We also simplify few steps that are not needed for our purposes. We start by reviewing the technique simpler example in Appendix A.1 before detailing the more tricky formulations involving compression.
A.1 Feasibility problem for gradient descent
To introduce the concepts underlying the techniques used to construct Lyapunov functions for Algorithms and 3, we begin with the simpler case of gradient descent on smooth, strongly convex functions. That is, consider the algorithm:
V f(xo).
(GD,,)
The goal of this subsection is to review the steps used to compute p² (GNN,, as defined in (6), via bisection search in which each iteration involves verifying the feasibility of convex problem.
Our starting point is to consider the following state variable for GD:
Tk [((x))
S
=
(15)
and natural family of Lyapunov function candidates (which corresponds subset of (3)) of the form
.zif)) = (p vf(=)):f) = IH- xx [((xx))
GD Vp(5
(P Ia)
[[(xx)
(16)
Pu 12 + P22 V [x+=)]
++2 ): x.)),
where P gd is positive semidefinite and we require Tr(P) = 1. This latter requirement is without loss of generality due to a normalization argument, and added to avoid the trivial solution P 0.
The problem we aim to solve is that of finding the best Lyapunov function among a given set of sandidates-ssecificclll
Vp(#g, (f())) can be uniformly upper bounded by the smallest possible constant over all optimization problems in the considered family. In other words, we seek the Lyapunov candidate function that yields the smallest possible such that
the one for which the ratio Vp(21-Vf(r)
Vy(2i, V((x)): < Vp(ao, f)
(17)
15

---

is valid for all L-smooth p-strongly convex functions f R. + R (in any dimension d E N) and all possible 20: 21, x, IR compatible with f and ω 20 - fxo)) The problem can be phrased as finding
Vy(ai, vf(z1):f)
})
p² (GD,,) = min P=D
max AGN J #0.2VER"
(V(To. V((x)):
s.t. Tr(P) = 1, 21 - To 1/ ")V((20))
(18)
where > O is the step size. One can reformulate this problem directly using tools from the performance estimation literature [55, 56], but the resulting problem One way to address this is to reduce it to the problem of finding, for given contraction factor some Lyapunov function that achieves this p-if one exists. This problem, on the other hand, is convex, and we can simply perform bisection search on p to find the smallest possible contraction factor.
convex the variable p.
We now introduce some notation simplify the statement of finding such Lyapunov functions:
p (x11 01, To, Po: P) = (r 91: f) - ///rrr,, go: f).
(19)
We will arrive at a way of solving this problem by reasoning through two steps:
1. Step 1: verifying given Lyapunov function and rate convex problem.
2. Step 2: verifying rate p for the optimal candidate Lyapunov functions convex problem.
Step verifying a given Lyapunov function and rate as a convex problem. For fixed Lyapunov parameter P E V2 and a tentative rate 0, we can then state the problem of verifying given Lyapunov function as that of showing that the minimum value of the following non-positive:
sup /EFu.. #0,2. ER
0p(21, Vf(xi), P:
(20)
s.t. V
20 -
The constraint that is smooth strongly convex function is easily encoded using interpolation conditions [56]. This allows us to work with sampled points from f rather than the infinite dimensional F. L. We introduce the notation
1
1 7(e+ Jjj
Φij = ʃa Jj 93 (x, 2z))
11:
93112
9;)11 (21)
2L
2(1
p/L)
where the notation (x,, Gi. f() is used to denote sampled triplet from f. such that f(x;) = fi and fx,,) = 9: for all i E {0, 1, This lets us rephrase our problem
sup AEN
(o(#1,91,200 To, 9o: f)
T. 2o.9 90.91 ERd Jo.J FE
(22)
s.t.
> 0
Vi,j E 10, 77V
0o
9. 0
The above problem is not convex due to the interpolation constraints. To address this, we reformulate as a semidefinite program (SDP). Let G B B where B is the following (3 x d) matrix
F., Fo: 91),
fu - f.] f1 f.
and =
In other words, G > is the Gram matrix of the entries of B:
||:00 x=
(ga, xx)
(g) No x.m) (g1, go) 11 1
(go. zo I.)
|190 12
> 0.
(g), 3o r.)
(g1.9o)
16

---

We introduce convenient notation by defining basis (row) vectors in F.. 9: E R and f; E R² which allow us "select" specific elements in B and Specifically, we define them such that
2; 2. B
9. = Bgg fi f-
(23)
More precisely: I; = ci E R2: 9o C2
E R 01 C3 E . = 19u. T. = 0g E R
along with So = = E RR, f1 = ey E 22 I. = 0 E IR2. can conveniently rewrite the different
parts of problem (22) using the notation
|| x. 112 = B.B² B = Tr(x,
1 = 9. Bg, Tr(O. D.G),
(e, Fj n.) B3 BT] Tr Tr((:: o G))
where D: 2 Jj
[g 3 g:), and denotes the symmetric outer product. This notation allows us to express all relevant quantities in terms of traces involving symmetric matrices. We now reformulate the necessary terms to derive the desired semidefinite representation of the problem. Let us begin with
Vr(ro, [z(o): Pn FoG) P22 Tr(go 9nG) + 2P2 Tr((To ④ ())))
= T
where Ag
with A = and also define the matrices My for all ú,j E {0, 1] such that Øij m.yf + Tr
To go
Similarly, we can write Vp(II, Vf(=)):f==
T1
91
mij =f, -f Sj
My Oj (Ti- + 99 93) (0: 0j)
(24)
2(1 201- (a: - Bg [ 9n)) (x: - I (
This enables a convenient reformulation of (22) as verification of the following condition, which corresponds to solving standard semidefinite program:
> sup G=0
Tr(A, PAGG) [ATAAAAACO
f
(25)
s.t. Tr(M,
20
One immediate consequence is that the validity of given Lyapunov function Vp for a specified rate satisfying (17) equivalently, (20)-can be formulated as the convex problem (25).
Step verifying rate p for the optimal candidate Lyapunov functions convex problem. To derive convenient condition that formally guarantees the above problem is nonpositive, we consider its standard Lagrangian duals-which reduces verifying the existence of dual variables Aij 2 0 such that
inf Azy
0
s.t.
ATPA
PAo
Σ 1.E((,11.)
Maj >
(26)
Σ
Aeymiy= 0.
(JE(U,1,*}
The problem has finally reduced to showing that for a given matrix P, the small-sized problem (26) feasible.
Key idea: As this problem linear in P (when p is fixed), we can directly use to search for valid P that verifies the decrease condition in (5) for given p:
A PA pVd PA
Σ Mig x 0
feasible PzO. Au 20
Σ Aiymi = 1J
(GD-SDP)
Tr(P) 11
SStonn duality holds in this due the existence of Slater point; e.g., [56].
17

---

Conclusion. Problem (GD-SDP) is convex feasibility problem that encodes the existence of candidate Lyapunov function certifying a given rate p. By performing a bisection search over p. we can identify the smallest rate satisfied by some Lyapunov function in our class. This approach enables us to solve the problem numerically using a semidefinite solver.
A.2 Feasibility problem for EF
Using the same ideas as in Appendix A.I, this section states the feasibility problem we solve to identify Lyapunov functions for Algorithm 2. In short, this requires adapting the two steps presented in Appendix A.1 I to accommodate the compressed message. Practically speaking, Step must be adapted to slightly larger problem (with few more states both in the Gram matrix G and in the Lyapunov candidates to incorporate compression). Then, Step follows directly by the same reasoning before: the condition derived in Step reduces checking the feasibility of linear matrix inequality that is linear in (P.p). which in turn allows us to search for the Lyapunov function via binary search over p.
Recall that we defined our state space for EF (7) as
Vz(z) Cle V
6:
This space has dimension 4, and our normalized set of candidate Lyaрunov functions is given by
V4 (P..p) E $4 x IR+ Tr(P) + -
For any (P,p) E VA we thus consider (p) Lyapunov functions of the form:
V(P (5 EF f) = E5 <.P) ((P))(PP & (a)(E - + ((f(()))-)))))) f-).
(27)
where we impose Tr(P) + +p= = I, again, without loss of generality and to avoid the trivial solution
(P.p) = O. Similarly to (19), now define
EF d (SI 50
EF (P,p); f) = (5P EF
fziif) pV(( (50
zo: zo: f).
(28)
Again, we say that for (P.p) E V4, a Lyapunov function V((rp) satisfies rate p for the iterates of EF if we have that
0 > sup deN fET To.0. ER
<EF LF (EFF .50 (P.p):
(29)
s.t.
(I1, (.P) )- EF < :f)
vf(x))=1
Formally, we require the following lemma: Lemma (EF feasibility problem). Consider running Algorithm 2 with a deterministic compression operator satisfying Assumption I for some [0, 1] any function satisfying Assumptions 2 and 3. There exists a nonzero candidate Lyapunov function V(P.)) of the form defined in (27), satisfying a given rate p > 0, and only if the following problem is feasible:
0 = Avp(p) +
Σ
Mig
Σ v4 CFF
C.FFFF
(JE((.11.))
iE(O.1)
0 > Aep(p) +
Σ
Xiymaj
feasible
1.fE(0,1.))
(EF-SDP)
Pes",
O
PER,
20
0 0
1= T
where matrices (M.)). are defined as in (24), AVr(p), (p) given below in (33) and (34). Here 22 denotes coordinate-wise inequality in R².
given below in (36), and
Proof sketch. The proof decomposed into several steps that correspond to adapting the technical ingredients from Appendix A.I.
18

---

Basis vector encoding We begin by introducing notation analogously to (23) for EF. Define the following basis vectors F, Ib. Ca2 E R
3 e
9i e e==e,4 é, = e ie (0.1),
(30)
where e₁ the i-th basis vector in dimension Similarly, let R2 be defined by
f e iE {0,1,
(31)
where is the i-th basis vector in dimension 2.
The point of defining these vectors is the same it for GD. These vectors allow us "select" points from our Gram matrix (see (23)). This, in turn, allows us to express the interpolation conditions of our feasibility problem in clean manner.
also define row vectors that correspond to the fixed-point as:
J+ = g+ 0g: f. = 02
C
6. 0g
Finally, define method in terms of our basis vectors:
f To CO:
(32)
ēg vi00 Co.
Expressing (28) using basis vectors. terms of (28)
First, we encode the decrease in the linear and quadratic
1 F,
I1 F, 5
3o F, Go 9.
AVr(p)= =
91 9.
91 9.
9o 9.
P
(33)
C1 C,
č C.
Eo C.
Co C,
E1 E._
El &.
Eo E.
Eo E.
= (f) p.
P f+),
(34)
where p >> is the contraction factor to verified. Note that A AVp(p) E R8x8 and Aup(p) e IR?.
Using these objects, we have that:
oF (GFF cEF, (P.P): = ((AV)DO)GGE)) + (Arp(o))
(35)
where GEF (BEF) T BEF is the Gram matrix of vectors
BEF = [io, 1 (xo), V/(m)) + (VS(2o)). + + (()))
and PEF = (f(z)
Interpolation conditions The interpolation conditions that enforce f f F,,, are identical to those we define in (24), but using the new basis vectors we define specifically for EF. We do, however, need to introduce new interpolation condition to encode the fact that using contractive compressor. We do this for deterministic compression operators. Using our basis vectors, this corresponds to introducing the matrices
EEF- (ng. + ē. 2.) (ng: +ē, -a) -179 + T + E.),
(36)
for E {0.
Finally, following the same reasoning described in Step and Step 2 of Appendix A. and using the technical modifications we outlined here, we arrive at the feasibility problem described in the statement of the lemma.
D
19

---

A.3 Feasibility problem for EF21
As in the previous section, one can now adapt the same ideas in Appendix and Appendix A.2 to EF²! This section states the feasibility problem we solve to identify Lyapunov functions in this context.
Following a parallel line derivation, we begin by noting that the state space defined (7) for FF21 was
Sk
EF
f((+))
(37)
This space now has dimension 3, and normalized set of candidate Lyapunov functions is given by
V3 (P.p)) 5 x R Tr(P) p ==
For any (P.p) V3 we thus consider ((P.)) Lyapunov functions of the form:
Pp C x; f] (5
2F
( Ta)(EFF") -5. + ([[(x) f+).
(38)
where we once more require +rp = 1 without loss of generality and to avoid the trivial solution (P.p) O. Similarly, to (19) and (28), define here
EF
EE
cEFa 50
(P.p)::) = (EP BF .1iff)
(S
CEE Fo! f). (39)
Again, we say that for (P,p) E V3, a Lyapunov V(P.p) satisfies rate p for the iterates of E if we have that
0 >
sup deN FEF ER.
of
EF
(cEFa)
Su
eEFa
f)
(40)
s.t.
(I,, CEP21 Vf(x.) =0
EF
(zo,
ED cEP
if)
Formally, we prove the following lemma.
Lemma (EF21 feasibility problem). Consider running Algorithm 3 with a deterministic compres- sion operator satisfying Assumption 1 for some E 10 on any function satisfying Assumptions and There exists a nonzero candidate Lyapunov function (( of the form defined in (38), satisfying given rate p O, if and only following problem is feasible:
0 AVp(p)+
Σ
Mi + - - CEF
32 Aep(p)+ +
Σ
Arymas
feasible
(.EE(.11.))
(EF2)-SDP)
PE83.
P
PER,
2
v:30
= Tr(P) +P
where matrices (Me)) are defined as in Eq. (24), (C (o, given below in (44), and AVp(p), (pp(p) are given below in (45) and (46). Here 22 denotes coordinate inequality in R
Proof sketch. We begin by changing our basis vectors to
T; = - = T. 2; = cT4,, d, = T.. cT,
i {0.1}
(41)
where F.. Gs. C, d, R and f, R Similarly, we define the row vectors corresponding to the fixed-point as
F. = 0g ... = 0 C, 03. d. = 0 f. 0
(42)
20

---

We define our method using these basis vectors as
I 3o + 17 do.
(43)
dj = do + Co.
The only difference in the interpolation conditions that we are compressing a different quantity now, which encode using
CFF
ف - do εo) ( - dg -a) c0 do) (01 - do).
(44)
where we only need a single matrix because the compression operator acts on mixture of the current and next state.
Next, we encode the linear and quadratic terms in exactly the same way as did for EF, except with the state variables
31 E. 91
To
Iq Σ,
AVp(p) =
9.
P
Ø 9. di d.
9o 9.
P Go g.
(45)
d2
dg d,
dg
d.
(pp(p) p (ʃi Ia) p. (Jo - Here too, AVp(p) E 8x8 and (pp(p) E IR?
(46)
Finally, using Step and Step of Appendix A.1, we arrive at the feasibility problem described in the statement of the lemma.
21

---

B Rate comparison
In this section, compare the rate given in equation (14) with the convergence of CGD and the standard convergence rate of ET [14, see Theorem 2]. We show that CGD is strictly superior to EF/EF21 using a CAS certificate, that our then we visualize the gap in both cases in Figures 2 and 4.
strictly better than the existing rate for EF and
We also compare the "complexity" resulting from either method in Figures 3 and 5. In order to create a fair and interpretable comparison we used the following metric:
log PAA
(47)
log PB
The log-ratio can motivated by the following example: if PA = 0.99 and pg = 0.98, then the latter will require half the number of iterations of the former before V(EN, #N; < E.
B.1 Comparison between CGD and EF/EF21
We now compare the convergence rate when using the optimal step size between CGD and EF (equivalently, EF21 since the rate is the same). Note that the optimal rate for CGD is given by [64, 65]
KV - 1 PCGD
(48)
KK +
where KvE=
I+yr
when using step size [64]
2 JJGD (1- velu + (1 VE)L
(49)
The next statement has been verified using WolframSeript:
Certified using WolframSeript
CAS E
1 1- Vc)
R 1
PEF PCGD Ve+
1 ve+
ya+ vo)2 + Ve16
K K+
(k 1)a
> 0.
KV +
B.2
Comparison to Richtárik et al. [14]
The rate of [14] for EF21 under the Łojasiewicz inequality, and with the largest possible step size chosen, is given by
p' max 1 l-Ve 1 --
(1=vE)
1
(50)
2
the single-agent case. We begin by noting that to show that our rate is faster, we only have to show that it is smaller than one of the terms of equation (50).
22

---

Certified using WolframSeript
CAS &
Note that
p-pp=1 Ve- 1 Ve
(1+ + ve)
2/ (1 +6++)) (N 1)2
(I-Vet l+e+
(1 (1- (e) - 1)3
2(K 1)2
Writing this as single fraction, we see that the sign of this expression is the same as that of
A = (1 1)² 1)) V
where = / (N 15-11 1)2 + c(Kx 1>3 + 2/ (1 + =(6 + x)). Denote the coefficient front of R. as C(R), and note that is negative. As result, it just remains to make sure that the rest of the terms compensate for this term. Rewriting this as an inequality, and squaring to deal with A, our result follows from the inequality
- C(R) R2² - (C(R) R)² - 4(1 ((1-
where
F F= x0- 3x) + c(1 x)( 3k) + 2/c (-1+ (3+)
The factors other than F are clearly positive, and is increasing with respect to Setting to 0 shows that positive for all valid e.
1.00
0.75
9 0.50
0.25
Oytinel
x=
Raindak
4
Radnieft
10
0.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Figure 2: Line plot comparing the convergence rate of this paper (blue) with equation (50) (red) for various K.
Log Phuaikaa log,o
0.32
0.3
1.0
1.0
1.0
Figure 3: Line plot comparing the complexity of equation (50) with the rates of this paper for various K.
23

---

1.00
0.75
= 0.50
0.25
CGD
CGI
CGI
x-2
EF EF/EF2
4
EF/EF21
10
EF/EF21
0.000
0.75
1.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
Figure 4: Line plot comparing the convergence rate of this CGD (blue) with EF/EF21 (red) for various K.
Iog, loog, Pocab
0.9
0.91
0.8
0.7
0.67
0.0
1.0
Figure 5: Line plot comparing the complexity of 2F with CGD for various k.
24

---

C
Missing proofs
This section contains the proofs of Theorems I and 2. The proof's were obtained using by observing numerical results using the Lyapunov search procedure presented in Appendices A.2 and A.3. The resulting proofs are remarkably compact, and the main technical step consists of verifying an algebraic reformulation by hand. For ease of verification, we provide the reader with scripts written in Wolfram Language* that automatically performs those reformulations using computer algebra system.
C.1 Proof of Theorem
Theorem 1.
Consider running Algorithm 2, i.e., EF, with compression operator C satisfying Assumption 1 for some E [0, 1] on any function satisfying Assumptions 2, and Let the step size given by
2
(1-v
11t
L 1+
11)
(1+ Vc)
(8)
Then, we have that
p² (EF,,) = Ve + [1 + ve) ~
(9)
where
H)) (L-V (1+ ve) /L- 11)2 16L (I+V0?
(10)
L+H
A Lyapunov function achieving the rate in (9), with ęEr defined in (7), is given by
e+ (1+ (1++)) ||eell = || Is - -ell2 + Te /lelll (11)
V(g xi f) = - xx) Te
Finally, the step size in (8) is worst-case optimal for EF: Vn > 0, we have p² (EF,)) > (EFF,,,
Proof. We begin by proving the rate given in (9) for our Lyapunov function. Consider the following inequalities, and associated with each of them the assigned multiplier
12 = f((x)= - f. - vf(*x)
(Ix - x.) +
1 (f(x)))1
2L
/
100 I. v f((x)))' <0,
2(1 /1 L/L)
(2) FnLL = fo - ffxx)))) +
V (x=)) +
120 - vf(=n)] <0.
:>
2L
2(1 L)
L
Ic = |
12 =fflee [ <0,
where À is defined in (10), and
Certified using WolframSeript
CAS i
Summing these inequalities with their multipliers, plugging in the update rules for Tx+1 and ek+1, and using p to denote the contraction factor we got in (9), we can rewrite the resulting inequality as:
p. (N) > ((I441,441)) + a. |lex P-1 (In xx) + 2(VE 1) alI. [. 11)
9h 1x
(51)
where
= (0 Ve) (+
(52)
'Wolfram Language is the programming language used in Mathematica. The scripts be used verify rates without a paid license using Wolfram Engine. 'These multipliers correspond to closed forms for some of the variables of (EF-SDP) when the Lyapunov function is fixed as in the statement of the theorem.
25

---

The statement now follows from the simple inequality >> Ve. We now prove that the announced rate is tight. Consider the one-dimensional quadratic function
(x)
(53)
The proof strategy used here is to show that the contraction for our Lyapunov function asymptotically matches the convergence rate announced in Theorem 1. We begin by fully exploiting Assumption 1 and set
Ck C(ex + +z(((=))
(1 +1+ v (fV +e)).
(54)
We can now rewrite the update rule for TR+1 and TR42 to get an expression for eg and cx+1 respec- tively:
1 - (p + v 6k
26+1 + Ve'
1- nu + v
bk+2
1 VE
ok
ck+1
1 ++ VE
xk+1
1+
ve'
(55)
after which we use the update rule for ek+1 of Algorithm 2 to get second-order recurrence relation for the sequence {ax I
VeLi = Ik+2 (1 mp VE(L+ [[[1+Tp)) Ik+11
(56)
The solution to this recurrence relation is given by the roots of the characteristic equation, and after plugging in the initial conditions, we get
Tk = T (1 mp + vē(1 - 7/1) + (1 - 7/4 - Vc(1- + m/) + T)*
(57)
1
(1 nh + ve(1 m/0) - (1 TH
m-- - Ve(1 (1 + qnb) T)
T
where T = VAVE + (1 - mh + ve(1 + nn))a. Note that for
n ( (+=vV)
(58)
which is strictly larger than the step size given in (8), the above expression is dominated by the first term in the limit & -> 0o. If we plug in the resulting asymptotic expression for I& into the definition of eg, and plug the resulting points into our Lyapunov function we get
(IK+II Ck+1) k-000 1 (1 ny Ve(1 np) + T)2
((x ex)
4
(59)
which, after plugging in the step size given in (8), is exactly the convergence rate announced in Theorem 1. The fact that our Lyapunov function is tight now follows from the remark made in Section 3.4.
Finally, we prove that the step size given in (8) is the optimal step size for our Lyapunov function. Note that the contraction factor
p(1) == 1 mj Ve(1 m//) + T)
(60)
that becomes the dominant term in the limit + oo of (59) is strictly decreasing in v. This is immediate from inspecting the sign of the derivative of the expression with respect to ny:
dp(n) = p01 v (1- mp ve(1 + mp) + T)2
(61)
dn
2T
The rest of the proof now follows from instead considering the quadratic given by
fL(x) = T. 1
(62)
and repeating all the arguments stated above, except we instead consider step sizes
-e Ve (1 i
(
n
(63)
and show that the contraction for our Lyapunov function is strictly decreasing for these step sizes. The argument now follows from the fact that the contraction factor on both of these quadratics are the same for the step size given in (8).
D
26

---

C.2 Proof of Theorem 2
Theorem 2.
Consider running Algorithm 3 with compression operator satisfying Assumption 1 for some E [0, 1] on any function satisfying Assumptions 2, aad 3. Let the step size be given by 1f" in (8). Then,
p (EF21 n. =p" (EF,.).
(12)
A Lyapunov function achieving the rate in (12) is given by
V(SEFa) 3. f] = (1 + vc) | 2g + ||]] 11g - dII + vo. ||all
(13)
Finally, the step size 11' is worst-case optimal for this algorithm.
Proof. We begin by proving the rate given in (12) for our Lyapunov function. Consider the following inequalities, and associated with each of them the assigned multiplier:
7 Fp. = f(xx) - f(x++1)= ++++1 + [V - vf(xx)1
+ V)(()) (0o+1 (F xx))
2L
X
+ 2(1 - -1/T.) ||0x xk+1
1
V/(x+)))11 50,
FuLl = f(xx+1)) f(xx) + [V](xx)) - [[(+++1)11? + (T xx+11)
2L
x
+ 2(1 - / L)
μ
||
2/ 1 (V((x))) <
Te [V d2
- - d+ < 0,
where X' is defined as
== Ve
16L (1 - (1-v][(--)+ (1. (1+
(64)
(L++
and 1.
Certified using WolframSeript
CAS t
Summing these inequalities with their multipliers, plugging in the update rules for Tk+1 and 1 and using p denote the contraction factor got in (12), we rewrite the resulting inequality as:
p. Viggg,, > (1+x+1,d+11) I|da ( b)gh+1 (p + b)
(65)
where
A
1 1-
b= L- μ
(66)
1 vc)
and
Lfe
a c 2m vc) The statement now follows from plugging in the value of our multipliers and checking the sign. We now prove that the announced rate tight. Consider the one-dimensional quadratic function
(67)
L-
fx
(68)
The proof strategy used here is show that the contraction for Lyapunov function asymptotically matches the convergence rate announced in Theorem 2. We begin by fully exploiting Assumption and set
Ck = C( de) (1 Ve) (Vf(xe+1) dx)
(69)
27

---

We can now rewrite the update rule for 26++1 and Tk-2 to get an expression for dR and dx+1 respectively:
Ik Ik+1
Ik+1 2k+2
dR+1
(70)
7
"
after which the update rule for de+1 of Algorithm 3 to get second-order recurrence relation for the sequence {Ix )=
Vez 24+2 (1 7p ve(1 + mp)) 2x+1-
(71)
Note that this is the exact same recurrence relation as in (9), which means we can reuse the expression in (57) and the argument that follows. The proof now follows from the definition of our Lyapunov function in (13). The optimality of our Lyapunov function similarly follows from the same argument given in the remark made in Section 4.
Lastly, the proof of optimality of our step size follows directly from the same argument given proof of Theorem 1.
C.3 Extension to stochastic compressors
Note that all the results of Theorems and were proven using the deterministic version of Assump- tion 1. Any deterministic compressor satisfies that assumption, and our lower bounds thus remain valid in this case. show that the given rates are tight, we have to replace the inequalities Ic from the respective proofs with their stochastic counterparts:
I E [||4+11||]] <lle + f==(]= & $0,
IEF = E [ - d2 C(V - d+)l - V d 0.
Certified using WolframSeript
CAS i
For EF, we need to show the following:
p EV en) > EV(I)+1,e--1)
ex-1),
Certified using WolframSeript
CAS Ø
And for EF21 we need show the following:
p EV(ok, d4) EV(o++1,de11)
The same exact proof as used in the deterministic case holds for both due to the linearity of expectation. Wolfram Language scripts verifying this fact are available in the source code repository for this article.
28

---

D Additional numerical results
All subsections include details on how the corresponding results were computed. This section is organized as follows:
Appendix D.1 presents additional performance plots for all methods and explains how the plots in the main paper were generated.
Appendix D.2 provides illustrations demonstrating that our Lyapunov functions remain tight over multiple iterations.
Appendix D.3 includes additional tables further confirming the tightness of our Lyapunov functions.
Appendix D.4 shows plots illustrating the optimality of our step size.
Appendix D.5 numerically demonstrates that the type of Lyapunov function used in Richtárik et al. [14] achieves a worse rate of convergence than the one used in this work.
All experiments were run on a MacBook Pro with an M4 Max processor. While none of the experiments computationally demanding by modern standards, they be scaled by increasing the resolution of the 1) and grid to produce finer plots.
The source code for all the experiments is publically available in the following GitHub repository: http::/gggtuub.comDaniilll/ BanneelBrgThommee/errrooo herpee////rro--eeeeeaak-iiigigii
D.1 Performance plots
This section presents the worst-case performance of all methods studied in this work, plotted as function of the step size 1) and the compression parameter
All contour plots were evaluated over a grid with e E [0.01, 0.99), and r E [0.01, T. where μ4, is the smallest μr specified in the caption of each figure (except for Figure 7, where it is set to 0.1). Each axis was discretized with resolution of 200 points.
To generate each non-cyclic point, we used the following procedure:
1. For each method, we computed the optimal Lyapunov function (without additional con- straints) via bisection on the contraction factor p. up to a precision of 10
2. Using the resulting Lyapunov function, then computed the worst-case contraction factor using PEPit [58] and the MOSEK solver [57].
We adopt this two-step approach because the feasibility problems used to compute the Lyapunov functions suffer from numerical instability. By evaluating the contraction factor separately using PEPit, we ensure that the reported value is an upper bound on the true contraction factor up to solver tolerance.
To identify the area of non-convergence in the plots, we check whether a cycle exists for each pair of 7 and This is done by following the procedure outlined in Goujaud et al. [66]] compute the worst-case performance of the metric - || zoll² ll for CGD, -1|= æol | - coll² for EF, and -|r xo 2 ||d dol 2 for EF If this value falls below threshold (set to 10 10-3), conclude that a cycle is present. In our experiments, cycles of length were successfully identified for all methods, and these matched precisely with the regions of the contour plots where 1.
D.2 Multi-step Lyapunov analysis
In this section, we show that our simple Lyapunov functions achieve the claimed convergence rate over multiple iterations. Specifically, we use PEPit to compute the contraction factor achieved by the Lyapunov function after iterations and compare to the theoretical rate /² where / the single- step contraction factor. The exact match between these quantities in Figures 9 and 10 confirms that our single-step analysis accurately characterizes the worst-case performance over multiple iterations on these Lyapunov functions.
29

---

0.2
0.44
0.28
A: 10
1.5
1.0
0.5
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
Figure 6: Contour plot showing the performance of CGD function of step size v and compression parameter e, with regions of non-convergence marked in red. The regions of non-convergence were identified using PEPit by finding cycles of length 2. Each column corresponds to μ = 0.5, 0.25, 0.1, with L = 1.0 fixed across all plots.
A: 10
1.5
1.0
0.5
0.0
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
Figure 7: Contour plot showing the performance of EF as a function of step size y and compression parameter e, with regions of non-convergence marked in red. The regions of non-convergence were identified using PEPit by finding cycles of length 2. Each column corresponds to μ = 0.5, 0.25, 0.1, with L = 1.0 fixed across all plots. The optimal step size setting for a given is marked in blue.
D.3 Lyapunov function class tightness
In this section, we show that for various conditioning numbers our Lyapunov functions for EF and 2F are tight with respect to our class Lyapunov functions, when using optimal step sizes. We remark that our Lyapunov functions actually tight for many step size settings, but notably not step sizes which are larger than the optimal step size.
The tables report the maximum absolute difference in contraction factors between our Lyapunov function and the optimal one, over range of and 7) values specified in the captions. All contraction factors were computed using PEPit, and the procedure for the uncontrained Lyapunov functions is the one outlined in Appendix D. Points where either Lyapunov function yields contraction factor greater than were excluded from the computation of the maximum absolute difference.
K 2
K 10
Absolute error
3.70c-07
4. 4.83e-07 6.60c-07
Table 3: Maximum absolute difference in contraction factor for EF when comparing the general Lyapunov construuee using any combination of state terms specified in Subsection 3.1 3.1-to the simplified Lyapunov function defined in Theorem 1. The results computed over line with e E [0.01, 0.99) and with y set to the optimal step size for L. = 1, and f 0.5, 0.25, 0.1.
30

---

2.00
0068
01433
1.5
K 10
0.5
0.0
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
Figure 8: Contour plot showing the performance of EF function of step size and compression parameter e, with regions of non-convergence marked in red. The regions of non-convergence were identified using PEPit by finding cycles of length 2. Each column corresponds to f 0.5, 0.25, 0.1, with L = 1.0 fixed across all plots. The optimal step size setting for given is marked in blue.
PERS
PEPS
PEPS:
0.95
0.9
0.8
0.90
0.8
S 0.6-
0.85
0.7-
0.80
0.6
0.4
= 0.75
= 0.5
0.25
k:
Figure Multi-step Lyapunov analysis for EF, computed using PEPit. The blue line shows the contraction factor achieved by the Lyapunov function after k iterations, while the red dashed line represents the theoretical rate p*, where p is the single-step contraction factor. Each column corresponds different value of 0.75, 0.5, 0.25, with L = 1.0 and μ 0.1 fixed across all plots.
K =
2
K = 4
K == 10
Absolute error
2.77e-07 1.97e-06
1.65e-06
Table Maximum absolute difference in contraction factor for EF when comparing the general Lyapunov function-construucc using any combination of state terms specified in Subsection 3. the simplified Lyapunov function defined in Theorem 2. The results are computed over a line with [0.01, 0.99] and with 7) to the optimal step size for L 1, and μ 0.5, 0.25, 0.1.
D.4 Step size comparison
In this section, we compare the theoretically optimal step sizes we propose for our methods with empirically optimal step sizes determined through numerical experiments. optima, we evaluate grid of 1/ and values and select the step size that minimizes the contraction factor achieved by our simplified Lyapunov functions. The results of that experiment are found in Figure 11.
compute the empirical
31

---

0.95
0.9
0.8
0.90
0.84
0.6
0.85
0.7
0.80
0.6
0.4-
0.75
0.5
0.25
5
10
10
10
4:
Figure 10: Mteti-step Lyapunov analysis for EF computed using PEPit. The blue line shows the contraction factor achieved by the Lyapunov function after k iterations, while the red dashed line represents the theoretical rate p², where p is the single-step contraction factor. Each column corresponds to a different value of e 0.75, 0.5, 0.25, with L = 1.0 and μ 0.1 fixed across all plots.
1.5
1.00
0.1
0.25
0.5
1.0
1.0-
0.75
5
0.50
0.25
0.0-
0.0
0.00
11.3
1.0
0.3
1.0
0.0
11.5
1.0
<
0.3
0.3-
T.
0.2-
0.2-
0.1
0.1
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.15
= 10
0.15-
2 = 10
0.15
10
0.1
0.25
0.5
0.10-
0.10
0.05-
0.06
0.06
0.00-
0.00-
0.00
1.0
0.0
0.0
0.5
1.0
Figure 11: Empirically observed optimal step sizes (blue) in comparison with our setting (red, dashed) as function of for different values of ju and L.
D.5 Comparison of Lyapunov functions to previous work
In this subsection, we compare the convergence rates achieved with our I Lyapunov function compared to that of Richtárik et al. [14]. For reference, the Lyapunov function they use is the following:
V(EBF") . == f()) f-
!/ ld 21
(72)
where 0 : T- We ran experiment where we measured the best possible contraction factor p' resulting form this parameterization, and compared to the ones we achieve with the Lyapunov function defined in Theorem 2. In order to account for the possibility that there may be a better
32

---

weighting between the two terms of equation (72), we let that the weighting be free parameter in the Lyapumov analysis PEP.
The metric used is the complexity metric introduced in the beginning of Appendix B. The result of this comparison can be found in Figure 12.
log / log Ph
0.543
1,06
14.45
0.233
9.00
1045
0.30
1.5
2
k
10
1.0
0.5
0.0
0.25
0.50
0.75
0.25
0.50
0.75
0.25
0.50
0.75
Figure 12: Complexity ratio between the rate achieved by the freely weighted version of equation (72). and the Lyapunov function used in Theorem 2.
33

---

E Remarks on the importance of proof certificates
The paper and appendix provide checkae- certificates for the main claims in the paper. We include two such complementary certificate types:
CAS
Symbolic certificates (WolframSeript). Short WolframSeript snippets that verify algebraic
identities and intermediary equalities used within proofs. Any suitable Computer Algebra System (CAS) could be used for these purposes.
Numerical certificates (PEPs). Instances of the PEPs (as defined in the main text) that validate global inequalities and performance bounds by directly solving the corresponding optimization problems.
While the proofs resulting from PEP formulations are well suited to CAS for local verification of individual steps, we use both tools: WolframSeript checks algebraic steps, and PEPs validate the global statements.
The rationale behind the decision adding these proof certificates is the following:
Reviewing efficiency and literature consolidation. Submission volumes at large ML venues continue to grow, increasing reviewer workload and raising challenges in the community, acceptance of a paper does not necessarily guarantee that proofs have been thoroughly checked"
While machine-checkable certificates do not replace mathematical proofs, they may shift effort from re-deriving statements to verifying that appropriate checks were provided, which is typically easier. They also provide authors with early feedback on correctness before submission.
Incremental path to formalization. General-purpose proof assistants (e.g., Lean, Rocq) do not yet provide mathematical infrastructure needed to formalize many ML results. As an interim step, certify the parts that are currently amenable: symbolic steps via computer algebra and end-to-end statements via PEPs. This may enable a gradual transition toward fully formal proofs libraries mature.
Clarifying experimental intent. Ultimately, we also believe that this can serve to clarify the role of experiments the papers, that are not always described. Some experiments test hypotheses; while others function as theory unit tests. Declaring the latter explicitly (and supplying their certificates) helps readers understand how these checks support the claims.
Formalization in Lean Rocq is our ultimate standard for guaranteed, machine-checked certificate of validity. We consider this an ambition for future work and aim to explore it by gradually linking the symbolic components Lean (e.g., turning recurring identities into lemmas) and packaging numerical outputs as checkable witnesses.
'nttps://blog wtt.riis.cc/cattorr//OOO// confeeeree/c/ceeeeecee/
'The NeurIPS 2025 reviewer guidelines indicate specifically that the reviewer is not required to read the
paper's supplementary material https: http://ppw...toooooooo/////////e
34

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Every claim is proven in the paper, and we make the setting and assumptions clear in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
35

---

We discuss the fact that we are restricted to the single-agent setting in the discussion. We also make quite clear that we are working with deterministic compression operators and smooth strongly convex functions in the background section.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions and full theorem statements are in the paper, and the proofs are in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
36

---

Justification: Full details about how the plots were generated are given in the appendix. We also provide the code as part the submission for the reviewers, and intend on making open source afterwards.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code will be made open source after the review process. In the meantime, the reviewers will get access to the code an anonymized form.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
muuides/CodeSuuiiee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: for more details.
//nips. cttccc/ppuco http//ppllggguupee/eeeeeeeeeeeel gwwgguudd/e//eeeeo httpe//gg..eee/eeeuuueeeeeeeeee /ttp://eeuuimiisiooooooeeeoeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
37

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Necessary details understand the plots are given the captions. Details for how they were generated are given in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper does include experiments, but they are not random and so this question is not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
38

---

The experiments can be scaled arbitrarily to fine or course grid of points, and the time finish is highly dependent on this. Nevertheless, all the experiments were run on M4 Max.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /t///enurrp..// httttp////errpp...ppp///////eee/ hptpbbic//thiccsuuieeeeeeee..e
Answer: [Yes]
Justification:
The authors have not violated the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The paper only provides tight analysis of already existing methods. The only impact will have is on the community of researchers working in distributed optimization.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymmett of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
39

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No data models are released in this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Citations for the software packages PEPit and PySR are present in paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo///aaa.ee cam/dataeets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- ee-packaedd, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
The only new asset introduced is the code implementing the feasibility prob- lems themselves, and the utility functions surrounding them. The documentation for these are given in the form of instructions for reviewers to replicate our findings in the supplementary material, and in the comments of the code.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
40

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing or human subjects are involved in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No research with human subjects is involved in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
The paper does not use L.LMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy (https: / /nnuripss.... wcc/oonferences//// for what should or should not be described.
41


Reviews:
[{"review_id": "AXFfLkuszq", "reviewer": "Reviewer_xTH1", "summary": "This work applies performance estimation framework (PEP) via SDP reformulation to convergence analysis of popular federated learning algorithms (CGD, EF and EF21) using contractive compression. While the analysis is restricted to smooth, strongly convex, single node (agent) setup where EF and EF21 are not helpful (meaning that CGD already converges and achieves tight rate), the use of PEP framework delivers some interesting insights. First, two new Lyapunov functions are found for EF and EF21, and contraction rates is shown to be equivalent despite different Lyapunov functions. \n\nWhile I believe this work bring some useful insights for the study of compressed gradient methods, there are some formal inaccuracies in the Appendix and lack of explanation of some key steps. These issues summarized below are critical and have to be addressed in detail in the next revision before the paper is ready for publication. I am happy to increase my numerical rating if these concerns are addressed in the rebuttal.", "questions": "From analysis, CGD allows larger step-size of order $1/L$ than EF and EF21 which require $(1-\\sqrt{\\epsilon})/L$. This can be also seen from upper bounds and convergence analysis. Is there an intuitive explanation why this happens?", "limitations": "n/a", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper applies a general methodology of performance estimation problem to a relevant and modern machine learning problem. The analysis yields interesting conclusions about two most popular error feedback schemes reinforcing their equivalence. \n\n2. New tight Lyapunov functions are identified, which can potentially help to further improve the analysis of these algorithms in distributed settings and design even better algorithms. \n\n**Weaknesses:**\n\n1. Why interpolation conditions for the compression look as in equations (35,36) in supplementary material? This requires more detailed explanation as it is the key non-trivial extension of the prior work on PEP.\n\n2. Since I don't fully understand the point (could be due to poor explanation), it seems to me that the analysis does not actually cover the entire class of contractive compressors. I am afraid that it is restricted to linear contractive compressors such as the one shown in tightness analysis in equation (50). If that is the case, then such analysis is very limited and not particularly insightful. Specifically, EF21 is equivalent to heavy ball momentum (if restricted to linear compressors), which has already been analysed using such PEP framework, and for such linear compressors EF = EF21 as shown in (Richtarik et al 2021), thus most claims in the paper follow immediately. In fact, from the practical viewpoint, the most interesting contractive compressor is Top-$K$, but I am not sure this is covered in this framework. \n\n3. It is unclear why the resulting Lyapunov function for EF21 does not include the function value? I would expect it should since analysis in (Richtarik et al 2021) is conducted using the function value as the potential and is tight if I understand it correctly. \n\n\nTypos and Mistakes:\n\nIn equation (21), $\\nabla f(x_0)$ should be $f_0$.\n\nIn equation (22), it is unclear how to pick elements with $i = 1$ and $i = *$, because neither the gram matrix $G$ nor matrix $B$ contain elements with $i = 1$. \n\nIf I understand it correctly, the definition of large $C_{i,j}$ coefficients in line 591 can be simplified using a norm squared instead of inner products. \n\nOn line 595 there is likely a wrong pointer to equation (27) which wasn't discussed at this point yet. \n \nI assume it is just a typo, but coefficients $C_i$ in Lemma 1 should have a superscript EF. Same issue for analogous lemma for EF21. Moreover there is an issue with superscript in Lemma 2 in the SDP.", "was_revised": true, "final_justification": "My main concern was about the SDP formulation under contractive compressors and the potential limitation that the study is limited to linear compressors. The authors explained some analysis steps in more detail and corrected some mistakes that made it difficult to understand some parts of the analysis. I am now mostly convinced that the paper indeed works with a general deterministic contractive compressor, and therefore increase my decision to \"accept\".", "rebuttal": "We sincerely thank the reviewer for their detailed and thoughtful comments, particularly regarding the SDP formulation in the appendix. We appreciate the reviewer’s careful reading, as some highlighted questions will help significantly improve the clarity of the manuscript.\n\nWe first want to emphasize that the derivations and theoretical results presented in the main text remain correct and unaffected. In particular, it should be noted that the proofs of Theorems 1 and 2 do not rely on the SDP formulation and can be verified independently. We hope this reassures the reviewer regarding the validity of our results.\n\nBelow, we respond point by point to the reviewer’s remarks.\n\n>Why interpolation conditions for the compression look as in equations (35,36) in supplementary material? \n\nThank you for pointing this out. First, we acknowledge a clear typo in equation (36):\n$$\nC\\_i^{EF} = \\\\begin{bmatrix} \\\\bar{g}\\_i \\\\\\\\ \\\\bar{c}\\_i \\\\\\\\ \\\\mathbf{\\\\bar{c}}\\_i \\\\end{bmatrix}^\\\\top C\\_{EF} \\\\begin{bmatrix}\\\\bar{g}\\_i \\\\\\\\ \\\\bar{c}\\_i \\\\\\\\ \\\\mathbf{\\\\bar c}\\_i\\\\end{bmatrix}. \n$$\nThis should instead be\n$$\nC\\_i^{EF} = \\\\begin{bmatrix}\\\\bar{g}\\_i \\\\\\\\ \\\\bar{c}_i \\\\\\\\ \\\\mathbf{\\\\bar{e}}\\_i\\\\end{bmatrix}^\\\\top C\\_{EF} \\\\begin{bmatrix}\\\\bar{g}\\_i \\\\\\\\ \\\\bar{c}\\_i \\\\\\\\ \\\\mathbf{\\\\bar e}\\_i\\\\end{bmatrix}.\n$$\n\nWe apologize for this oversight, which may have made interpretation difficult.\n\nLet us now explain why we define equation 36 as we did. The interpolation condition, for any $i \\\\in \\\\{0, 1\\\\}$  can be written as \n$$\n||(\\eta g_i + e_i) - c_i|| ^2 \\leq \\epsilon ||\\eta g_i + e_i||^2,\n$$\nwhich is a direct discretization of Assumption 1 or equivalently,\n$$\n||(\\eta g_i + e_i) - c_i|| ^2 - \\epsilon ||\\eta g_i + e_i||^2 \\le 0.\n$$\n\nEquation 36 is simply a rephrasing of this condition, after expansion, in terms of the basis vectors we defined:\n$$\n\\\\begin{aligned}\n&||(\\\\eta g\\_i + e\\_i) - c\\_i|| ^2 - \\\\epsilon ||\\\\eta g\\_i + e\\_i||^2  \\\\\\\\\n&=||c\\_i||^2 + \\\\eta^2 ||g\\_i||^2 + ||e\\_i|| ^2 - 2\\\\eta \\\\langle g\\_i, c\\_i \\\\rangle -2 \\\\eta \\\\langle e\\_i, g\\_i \\\\rangle + 2 \\\\langle c\\_i , e\\_i \\\\rangle  - \\\\epsilon \\\\eta^2 || g\\_i||^2 - \\\\epsilon ||e\\_i||^2 -  2\\\\epsilon \\\\eta \\\\langle g\\_i, c\\_i \\\\rangle \\\\\\\\\n&= \\\\text{Tr}\\\\left(\\\\begin{bmatrix}g\\_i \\\\\\\\ c\\_i \\\\\\\\ e\\_i\\\\end{bmatrix}^\\\\top C\\^{EF} \\\\begin{bmatrix}g\\_i \\\\\\\\ c\\_i \\\\\\\\ e\\_i\\\\end{bmatrix}\\\\right).\n\\\\end{aligned}\n$$\nThis can be seen directly by matching the coefficients we now wrote down explicitly, to that of the matrix in equation (35). \nUltimately, $C_i^{EF}$ is defined such that the outer basis vectors are \"picking\" the contributions from the right vectors, and then assigning them the weights given in equation 35, i.e. s.t.:\n$$\n\\\\begin{aligned}\n \\\\text{Tr}\\\\left(\\\\begin{bmatrix}g\\_i \\\\\\\\ c\\_i \\\\\\\\ e\\_i\\\\end{bmatrix}^\\\\top C\\^{EF} \\\\begin{bmatrix}g\\_i \\\\\\\\ c\\_i \\\\\\\\ e\\_i\\\\end{bmatrix}\\\\right)\n\\\\end{aligned} = \\\\begin{aligned}\n \\\\text{Tr}\\\\left(  B^\\\\top C_i\\^{EF}  B\\\\right)\n\\\\end{aligned} \n$$\nFrom there on, the derivation follows step 1 and 2 from section A. The primal constraint  $\\\\text{Tr}\\\\left(  B^\\\\top C_i\\^{EF}  B\\\\right) = \\\\text{Tr}\\\\left( C_i\\^{EF}  G \\\\right) \\le 0 $ leads to the term $\\sum_{i \\in\\{0,1\\}} \\gamma_i \\cdot C_i^{E F}$ in eq. (EF-SDP) (following eq. (36)).\n\n\nWe will provide the details of this computation in the next version.\n\nAdditionally, we acknowledge that in the same subsection, we reused the notation $C_{ij}$, $c_{ij}$ (later referred to as $M_{ij}$ and $m_{ij}$) for the smoothness and strong convexity interpolation conditions. This overlaps with the notation used for $C_i^{EF}$ and $C_i^{EF21}$, and we understand this may have contributed to confusion. We sincerely apologize and have revised the appendix to improve the clarity and consistency of notation throughout.\n\n>Since I don't fully understand the point (could be due to poor explanation), it seems to me that the analysis does not actually cover the entire class of contractive compressors. I am afraid that it is restricted to linear contractive compressors such as the one shown in tightness analysis in equation (50).  [...]. In fact, from the practical viewpoint, the most interesting contractive compressor is Top-$K$, but I am not sure this is covered in this framework.\n\nWe hope the explanation provided above clarifies how Assumption 1 is exactly encoded in the SDP without restriction. To further reassure the reviewer, we emphasize that the analysis of convergence rates is entirely decoupled from the SDP—it directly invokes Assumption 1 in the proofs, and does not necessitate any linearity. The SDP was used only to design the Lyapunov function we use in our analysis.\n\nRegarding equation (50) specifically: it appears in the **lower-bound** construction, which is separate from the upper bound. We obtain this lower bound using a linear compressor given by eq. (50), on a specific function. It is sufficient to achieve the lower bound on this linear compressor to conclude, as it belongs to the more general set of compressors. The upper bound is obtained under the full generality of Assumption 1, and thus beyond linear contractiveness. \n\nThe Top-$K$ compressor is thus indeed included in our analysis.\n\n>It is unclear why the resulting Lyapunov function for EF21 does not include the function value? I would expect it should since analysis in (Richtarik et al 2021) is conducted using the function value as the potential and is tight if I understand it correctly.\n\nIt is indeed an interesting consequence of our analysis that the optimal Lyapunov function does not correspond to the ones in  the literature (even for EF!). This is actually one strength of our approach to be able to automatically and exactly derive the best possible Lyapunov functions. \n\nRegarding the analysis of (Richtarik et al 2021), there are a couple of differences on the assumption set. We are unsure about which exact tightness result you mention. Regardless, tightness results **for a given Lyapunov function** are very distinct from tightness results that say that **no** Lyapunov function can provide a better rate (and our result is tight in both senses). Getting results of the latter type typically requires using performance estimation techniques. It is thus not surprising that the use of these advanced tools enables us to find better Lyapunov functions.\n\nWe thank the reviewer for pointing out typos, which will be remedied in the next revision. We would just like to comment on the following:\n\n>If I understand it correctly, the definition of large $C_{i, j}$ coefficients in line 591 can be simplified using a norm squared instead of inner products.\n\nNote that the basis vectors are row vectors, expressions like $\\bar{g}_i^\\top \\bar{x}_j$ denote outer products (i.e. matrices), and not inner products (scalar). While we could reformulate these terms using a custom norm operator representing self-outer-products, we prefer to keep the current notation to avoid introducing new definitions that would require additional explanation. Instead, we have emphasized in the revised draft that the basis vectors are row vectors, to prevent further confusion.\n\n> From analysis, CGD allows larger step-size of order $1/L$ than EF and EF21 which require $(1-\\sqrt{\\epsilon})/L$. This can be also seen from upper bounds and convergence analysis. Is there an intuitive explanation why this happens?\n\nWe note that the optimal step size for CGD is given by [2]\n$$\n\\eta = \\frac{2}{(1 - \\sqrt{\\epsilon})\\mu + (1 + \\sqrt{\\epsilon}) L}.\n$$\nThe optimal rate for CGD is also given by [1, 2]\n$$\n\\left(\\frac{\\kappa_{\\sqrt{\\epsilon}} - 1}{\\kappa_{\\sqrt{\\epsilon}} + 1} \\right)^2,\n$$\nwhere $\\kappa_{\\sqrt{\\epsilon}} = \\frac{L (1 + \\sqrt \\epsilon)}{\\mu (1 - \\sqrt \\epsilon)}$ (note that we define the conditioning number inversely compared to [1]). An intuition for this is essentially that the uncertainty in the update direction is \"rescaling\" $L$ by adding \"$\\sqrt{\\epsilon}$ uncertainty\", and doing the converse operation for $\\mu$.\n\nAs far as our step size is concerned, it is given by\n$$\n\\eta = \\left(\\frac{2}{L + \\mu}\\right) \\left(\\frac{1 - \\sqrt{\\epsilon}}{1 + \\sqrt{\\epsilon}}\\right).\n$$\nThat is to say: in CGD, the \"rescaling\" is applied at the level of the smoothness and strong convexity constants, whereas the scaling for EF/EF21 is applied at the level of the step size.\n\n---\n\nWe hope our responses have clarified any misunderstandings and that you will consider revising your score accordingly. We would be happy to provide further clarification if needed.\n\n---\nReferences:\n- [1] E. De Klerk, F. Glineur, A. Taylor. _On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions_. Optimization Letters, 2016.\n- [2] O. Gannot. *A frequency-domain analysis of inexact gradient methods*. Mathematical programming, 2020."}, {"review_id": "QPFV3oTi9g", "reviewer": "Reviewer_f2XL", "summary": "In this work, the authors provide a tight analysis of both EF and EF21 methods. They identify the Lyapunov function that gives the best possible convergence rate for each method and, using computer-assisted techniques, establish matching lower bounds that confirm the optimality of these rates. This careful approach provides sharp performance guarantees and allows for a clear, direct comparison between EF, EF21, and Compressed Gradient Descent (CGD). The analysis is conducted in a simplified setting, focusing on the single node and deterministic case, which highlights the core algorithmic ideas and enables clean theoretical insights without the added complexity of other settings.", "questions": "Please check the weaknesses section.\n\nI think the paper is rigorous and clear, but the issues raised in the weaknesses section are important.", "limitations": "The results are obtained only in the single-node case and the deterministic setting.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well written, carefully structured, and easy to follow in most parts. The authors present their ideas clearly and maintain a logical flow throughout the paper, which makes it accessible to the reader.\n\nAll theorems, assumptions, and lemmas are clearly stated and supported by intuitive explanations. The theoretical sections are presented in a way that is both rigorous and understandable, which I find valuable.\n\nThe background section and the discussion of related work are thorough. The authors provide a solid overview of the existing literature and clearly explain how their work connects to and differs from previous studies.\n\nThe pseudocode is well presented and easy to interpret. It offers a clear description of the algorithms, making the proposed methods easier to understand and potentially easier to implement.\n\nFigures 1 and 2, as well as Tables 1 and 2, are well designed, clearly labeled, and well explained in the text. They effectively support the theoretical findings of the paper. I appreciate the clarity and care in the visual presentation.\n\nI briefly checked the theoretical results. They appear to be correct and rigorous, although I might have missed some minor details.\n\nOverall, the results seem to be sound and are well explained. The paper demonstrates careful work and contributes insights to the topic.\n\n\nWeaknesses:\n\nThe abstract is confusing and potentially misleading, as it does not mention that the results are obtained in the single-node setting.\n\nAssumption 1 is made for deterministic compressors, while in the EF21 paper by Richtárik, the contractive compression operator is defined for stochastic compressors in expectation. Is it possible to extend the current results to the class of stochastic contractive compressors?\n\nIn line 132, there might be a typo in the formula (though I am not certain). I believe it should be $\n\\Vert g - \\nabla f(x) \\Vert^2 \\leq \\epsilon \\Vert \\nabla f(x) \\Vert^2.\n$\n\nPlease clarify.\n\nThe main issue with the paper is its focus on the single-node regime. The core motivation for using gradient-type methods with compressed updates, such as EF, EF21, and CGD (Compressed Gradient Descent) is typically in the multi-node setting. It is unclear why it would be meaningful to consider these methods in the single-node setting, where compression is not useful. Could the authors clarify any potential benefits of using such methods in the single-node case?\n\nThe authors claim that studying the single-node setting can provide intuition. However, I find this potentially misleading. In the single-node setting, CGD can converge with an appropriate stepsize without any issues. In this scenario, EF and EF21 mechanisms seem redundant, since the standard CGD method can work without additional memory or algorithmic adjustments. On the other hand, in the multi-node setting, as the authors themselves mention, CGD may diverge regardless of the stepsize. This indicates that the two settings are fundamentally different. It is unclear how insights from the single-node case can reliably transfer to the multi-node case.\n\nAnother important point is that EF21 is typically analyzed in non-convex settings and also under the Polyak-Łojasiewicz (PL) condition. This gives EF21 a theoretical advantage in non-convex problems. The results provided in this paper focus on the strongly convex case and do not address the more interesting non-convex scenario. Showing that EF and EF21 perform identically in the strongly convex setting does not necessarily imply that the same will hold in the non-convex or multi-node case. In fact, theory currently favors EF21 in the non-convex regime.\n\nFinally, another limitation is that the analysis assumes full-gradient updates. Stochasticity is not considered, even though stochastic gradients are essential in practical applications. Therefore, it would be valuable to compare these methods in the stochastic case.", "was_revised": true, "final_justification": "Dear all, \n\nI appreciate the authors' responses and clarifications.\n\nMy main comments are as follows:\n\n1. I appreciate the authors for their tight analysis in the single-node setting with deterministic gradients under the strongly convex and Lipschitz smooth assumptions.\n\n2. While I acknowledge certain conceptual similarities, I do not see a strong connection between quantization-aware training and error-feedback methods in the single-node setting, as the former typically involves compression of models/iterates.\n\n3. I also appreciate the rigorous analysis and the use of carefully designed Lyapunov functions. However, I remain somewhat unconvinced that the insights derived in the single-node, deterministic setting can be directly generalized to more practical or broader scenarios.\n\n4. As previously noted, I find the single-node deterministic setting rather limited in scope. In my view, extending the analysis to the multi-node case would significantly enhance the impact and relevance of the work.\n\nBased on these points, I believe a borderline reject is an appropriate score for this paper.\n\nBest regards,\n\nReviewer", "rebuttal": "We sincerely thank the reviewer for their thoughtful and constructive feedback on our work. Below, we address each point in the order raised.\n\n> The abstract does not mention single-agent.\n\nWe agree that the final clause of the abstract is ambiguous. We will revise it to:  \n\"Our analysis is carried out in **the simplified single-agent setting**, which allows...\"\n\n> Assumption 1 is made for deterministic compressors, while in the EF21 paper by Richtárik, the contractive compression operator is defined for stochastic compressors in expectation. Is it possible to extend the current results to the class of stochastic contractive compressors?\n\nThis is a good question: the proofs indeed carry over directly to stochastic contractive compressors—one simply applies the expectation bound on the compressor and uses linearity of expectation in the Lyapunov analysis. We have prepared and will provide a WolframScript that verifies the resulting inequalities, and we will spell out the stochastic version of the assumption as well as the corresponding theorem statements in the next revision. We thank the reviewer for making this comment, which helps broaden the scope of the analysis.\n\n> Typo l.132\n\nWe thank the reviewer for noticing this typo. It will be fixed in the next draft.\n\n> The main issue with the paper is its focus on the single-node regime. The core motivation for using gradient-type methods with compressed updates, such as EF, EF21, and CGD (Compressed Gradient Descent), is typically in the multi-node setting. It is unclear why it would be meaningful to consider these methods in the single-node setting, where compression is not useful. Could the authors clarify any potential benefits of using such methods in the single-node case?\n\n> The authors claim that studying the single-node setting can provide intuition. However, I find this potentially misleading. In the single-node setting, CGD can converge with an appropriate step size without any issues. In this scenario, EF and EF21 mechanisms seem redundant, since the standard CGD method can work without additional memory or algorithmic adjustments. On the other hand, in the multi-node setting, as the authors themselves mention, CGD may diverge regardless of the step size. [...]\n\nWe appreciate this important question—this is a point we should have made clearer and will detail in the revised version. We fully acknowledge (and we stated in the submitted draft) that some behaviors will differ when moving from the single-agent to the multi-agent setting. Nevertheless, we believe there are strong arguments in favor of providing a tight analysis in the single-agent case as a first step:\n\n**1. Practical relevance beyond distributed optimization**\n\nWe would like to highlight the relevance of our work in the context of sparse/quantized neural-network training. BinaryConnect [1], which is one of the most popular algorithms for *quantization-aware training* of neural networks, combines gradient steps with quantization steps. Although not directly equivalent to CGD or EF, it is a natural example of a **single-agent** algorithm that combines quantization and GD. The adaptation of EF in the context of sparse neural networks leads to the work of Lin et al. [2], who perform sparse neural-network training by applying only sparse updates, which is equivalent to error feedback. The authors note this equivalence at the end of Section 3 (and are themselves among the active contributors to the field of error feedback, as they have co-authored [3-6]). \n\nGenerally speaking, the single-agent setting is thus relevant to the design of training methods for sparse or quantized neural networks—motivating the study of these algorithms even outside their typical distributed setting. \n\n- [1] M. Courbariaux, Y. Bengio, J-P. David. *BinaryConnect: Training Deep Neural Networks with binary weights during propagations*. Neurips 2015.\n- [2] T. Lin, S. Stich, L. Barba, D. Dmitriev, M. Jaggi. *Dynamic Model Pruning with Feedback*. ICLR, 2020.\n\n**2. Numerous key papers derive their analysis in the single-node case**\n\nWe respectfully disagree that error feedback is simply redundant in the single-agent setting. In fact, many of the foundational (and well-cited) works that analyze error feedback [see, among others, 3–5] place themselves specifically in that single-agent regime for the analysis. This is underlined in other papers; see, for example, Table 1 of [7].\nWe believe such sustained interest means that the community considers the single-agent case insights to be valuable.\n\n- [3] S. Stich, S.P. Karimireddy. *The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication.* JMLR, 2020.  \n- [4] A. Ajalloeian, S. Stich. *Analysis of SGD with biased gradient estimators.* , 2020.  \n- [5] S.P. Karimireddy, Q. Rebjock, S. Stich, M. Jaggi. *Error feedback fixes SignSGD and other gradient compression schemes*. ICML, 2019.\n- [6] S. Stich, J-B. Cordonnier, M. Jaggi. *Sparsified SGD with memory*. Neurips 2018.\n- [7] P. Richtárik, I. Sokolov, I. Fatkhullin. *EF21: A new, simpler, theoretically better, and practically faster error feedback*. Neurips, 2021.\n\n**3. Comparing EF, EF21, and CGD is far from straightforward even in the single-node case, and our analysis in the single-agent case already brings valuable insights:**\n\n- **First**, CGD does not consistently outperform EF or EF21 across all step sizes. The superiority of CGD only holds under optimal tuning. In fact, one of CGD’s key advantages is its ability to operate under significantly larger step sizes, which offers useful intuition for its behavior and performance trade-offs. We generated a figure (prior to the announcement disallowing new figures in the rebuttal process) that showcases, for any fixed $(\\eta, \\epsilon)$, the log-ratio of optimization complexities between CGD and EF: for instance, for $\\kappa=10$, depending on the step size, EF can be more than 100 times faster or 1000 times slower than CGD (in terms of number of steps required to achieve the same reduction in performance measure). We will add this figure to the paper.\n\n- **Second**, the equality of rates between EF and EF21 in this setting was, to the best of our knowledge, previously unknown. This equivalence can be revealed only by analysis using an optimal Lyapunov function, as the optimal rate is achieved for a very different Lyapunov function. For a fixed Lyapunov function, the rates of EF and EF21 are *not* the same—we will also provide an illustration of this fact.\n\nWe therefore believe that, although some behaviors will differ in the multi-agent case, the simplified setting considered in this work reveals non-trivial and meaningful insights. Providing a tight analysis under optimal step-size tuning allows us to offer a fair comparison between the methods and should act as a stepping stone for future work comparing these methods in the multi-agent, non-convex, or stochastic-gradient cases.\nNevertheless, we are happy to better highlight the differences to be expected in multi agent in a dedicated subsection.\n\n> Another important point is that EF21 is typically analyzed in non-convex settings and also under the Polyak-Łojasiewicz (PL) condition. [...] . Showing that EF and EF21 perform identically in the strongly convex setting does not necessarily imply that the same will hold in the non-convex or multi-node case. In fact, theory currently favors EF21 in the non-convex regime.\n\n> Finally, another limitation is that the analysis assumes full-gradient updates. Stochasticity is not considered, even though stochastic gradients are essential in practical applications. Therefore, it would be valuable to compare these methods in the stochastic case.\n\n- **Regarding extensions**: We agree that our work does not provide direct results under non-convex assumptions, nor does it use stochastic gradients. To avoid confusion, we have explicitly stated all of our assumptions in specific environments at the beginning of the paper, allowing readers to quickly verify the scope of our contributions. Extending our results to the non-convex setting and/or using stochastic gradients would be a very interesting contribution, but it would substantially change the scope of the current paper, which is already quite long. We consider either of those extensions to be exciting directions for future work in the field.\n\n- **Regarding non convexity**:\n\n  -- While a line of work has consisted in analyzing EF21 in non-convex settings [7–9], such analysis is not systematic; convexity assumptions are also common in the broader literature on distributed optimization, including [5, 6].\n\n  -- More importantly, results under weaker assumptions come with looser convergence guarantees, and we believe they do not always bring a better understanding of the methods: strong convexity allows us to show rates that are likely to be better characterizations of performance around local minima-which could be argued correspond better to training behavior ultimately observed in practice.\nMoreover, on the technical side, while extending our technique to PL condition is of great interest, we are unaware of tight _interpolation conditions_ for functions satisfying the PL condition. Providing them would on its own consitute a non-trivial research contribution. Overall, our choice is to focus on a setup powerful enough to provide a tight and fair comparison.\n\n---\nWe hope our clarifications help resolve the earlier concerns and would be grateful if you might reconsider the score. We’re glad to provide any further details you’d find useful.\n\n---\n- [8] I. Fatkhullin, I. Sokolov, E. Gorbunov, Z. Li, P. Richtárik. *EF21 with bells & whistles: practical algorithmic extensions of modern error feedback*. JMLR , 2025.  \n- [9] L. Condat, K. Yi, P. Richtárik. *EF-BV: A unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization*. Neurips, 2022."}, {"review_id": "BAA21CeiBe", "reviewer": "Reviewer_sQ6n", "summary": "The paper provides tight bounds for Compressed GD, EF, and EF21. It employs the performance estimation framework to find the optimal Lyapunov functions for EF and EF21. The paper demonstrates that CSG actually converges for the larger set of problem parameters compared with EF and EF21.", "questions": "Minor concerns:\n\nLine 188: redundant “and”\n\nLine 220: better to move the reference to the end of the phrase\n\nLine 237: naemly\n\nLine 565 is strange", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is very well-written and the main technique for finding optimal Lyapunov functions was very interesting.\n\nConcerns:\n\nThe paper only considers the exact-gradient case. Note that EF was largely motivated by the need of compressed GD to handle the stochastic noise (see [“Error Feedback Fixes SignSGD and other Gradient Compression Schemes”](https://arxiv.org/pdf/1901.09847), Section 3). Since the practical scenarios have stochastic noise, I question the significance of this work, in particular the conclusion “We also observed that their performance is strictly worse than that of compressed gradient descent – an outcome that, we believe, challenges the intuition of many in the field.”\n\nSection 3: what is the optimal convergence rate for CGD?\n\nIn Section 2.1, you don’t talk about EF. Also, please mention EF21 when using reference [14].", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their very positive comments on the execution of the paper, and for the ratings given. The typos found by the reviewer will be fixed in the next draft, and we thank them for pointing those out as well.\n\n>The paper only considers the exact-gradient case. Note that EF was largely motivated by the need of compressed GD to handle the stochastic noise (see [“Error Feedback Fixes SignSGD and other Gradient Compression Schemes”](https://arxiv.org/pdf/1901.09847), Section 3). Since the practical scenarios have stochastic noise, I question the significance of this work, in particular the conclusion “We also observed that their performance is strictly worse than that of compressed gradient descent – an outcome that, we believe, challenges the intuition of many in the field.”\n\nWe agree with the reviewer that it would be very interesting to see what the guarantees would look like with stochastic gradients. That being said, it would change the scope of the paper quite a bit. Deterministic gradients have been used in some landmark papers (e.g. [1]), or it is reported as a separate result  (e.g. [2]). We consider it to be a different problem that we would prefer to leave as an exciting direction for future work.\n\n>Section 3: what is the optimal convergence rate for CGD?\n\nWe recover the following optimal rate for CGD, that was also given by [3, 4]:\n$$\n\\left(\\frac{\\kappa_{\\sqrt{\\epsilon}} - 1}{\\kappa_{\\sqrt{\\epsilon}} + 1} \\right)^2,\n$$\nwhere $\\kappa_{\\sqrt{\\epsilon}} = \\frac{L (1 + \\sqrt \\epsilon)}{\\mu (1 - \\sqrt \\epsilon)}$ (note that we define the conditioning number inversely compared to [3]). \n\nThe line for CGD in Figure 2 was generated simply by discretizing over the interval $\\eta \\in (0, 2/(L+\\mu)]$, and manually selecting the step size that gave the best contraction. To reassure the reviewer: the plot was originally (before we knew the closed-form optimal step size for EF and EF21) using the same implementation, and simply looked like a discrete approximation of the smooth figure now present in the paper. We will update the plot to instead use the step size given in [4] directly in the next draft (while providing the reference and closed-form explicitly in the text).\n\n>In Section 2.1, you don’t talk about EF. Also, please mention EF21 when using reference [14].\n\nWe acknowledge that we should have discussed existing EF results and will incorporate this in the next draft.\nWe will likewise replace the generic reference with an explicit mention of EF21 accompanied by the Richtárik citation.\n\n---\n\nWe thank the reviewer again for their support and would happily participate in any further discussion if needed.\n\n---\n\n\nReferences:\n- [1] P. Richtárik, I. Sokolov, I. Fatkhullin. _EF21: A new, simpler, theoretically better, and practically faster error feedback_. Advances in Neural Information Processing Systems 34, 2021.\n- [2] K. Gruntkowska, A. Tyurin, P. Richtárik. _EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression_. International Conference on Learning Representations, 2020.\n- [3] E. De Klerk, F. Glineur, A. Taylor. _On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions_. Optimization Letters, 2016.\n- [4] O. Gannot. *A frequency-domain analysis of inexact gradient methods*. Mathematical programming, 2020."}, {"review_id": "imuLZ5WEMR", "reviewer": "Reviewer_z1Gw", "summary": "The paper provides a tight analysis of CGD, EF, and EF21 through the lens of the meta-optimization problem defined in equation (6). The authors detail the formulation of this meta-optimization problem, specify the set from which the Lyapunov function is selected, and explain the procedure used to construct the optimal Lyapunov function (i.e., how the meta-optimization problem is solved). The formal proofs of the convergences have been presented.", "questions": "1. How do the convergence rates obtained in this work compare to the classical results for EF and EF21?\n2. What's the primary challenge of analyzing the distributed setting?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The paper addresses a compelling research question and utilizes an interesting tool to tackle it.\n2. The theoretical analysis is rigorous, with carefully derived proofs.\n\nWeaknesses:\n1. The analysis is restricted to the single-client setting. This significantly limits the impact of the results, as some of the known challenges of CGD in the distributed setting, when $n > 1$, are not present in the $n=1$ case. In particular, as noted by the authors and shown in prior work \\[1, 2], CGD fails to converge in the distributed setting. Therefore, the phrasing in line 239  “These results challenge the prevailing intuition that error feedback ensures convergence comparable to that of uncompressed methods” is misleading: the lack of convergence is not a matter of intuition but a rigorously established fact. On the other hand, CGD converges without issue in the single-node case. Additionally, in the single-node case, error feedback appears unnecessary and overly complex.\n2. The paper lacks a clear rate comparison with classical results for EF [3] and EF21 [4]. In particular, Theorems 1 and 2 do not explicitly state the iteration complexity rates, and require additional manipulation to extract them.\n\nReferences:\n[1] Beznosikov et al, \"On Biased Compression for Distributed Learning\"\n\n[2] Karimireddy et al, \"Error Feedback Fixes SignSGD and other Gradient Compression Schemes\"\n\n[3] Stich et al, \"SGD with memory\"\n\n[4] Richtarik et al, \"EF21: Error Feedback 2021\"", "was_revised": true, "final_justification": "The main criticism of this paper concerns not the obtained results, but their relevance. While the analysis of the multi-node case is of utmost importance, the authors claim to have identified new properties in the single-node case, which appear to be relevant.", "rebuttal": "We sincerely thank the reviewer for their positive feedback and high ratings regarding the quality, clarity, and originality of our work. We also appreciate their familiarity with the relevant literature. Below, we respond to each of the reviewer’s comments and questions in detail.\n\n>The analysis is restricted to the single-client setting. This significantly limits the impact of the results, as some of the known challenges of CGD in the distributed setting, when n>1, are not present in the n=1 case. In particular, as noted by the authors and shown in prior work [...], CGD fails to converge in the distributed setting. \n\n> Additionally, in the single-node case, error feedback appears unnecessary and overly complex.\n\nWhile we all agree that the multi-agent case is of importance and shows nuances, we believe the single-agent case to be of significant interest, and do not fully agree with the claim that EF is \"unnecessary and overly complex\" in the single-agent setting.\n\n1. Many foundational works on error feedback [1–3] perform their analysis in the single-agent setting. E.g. Table 1 in [5] highlights this. It thus seems that the community does not disregard the importance of this regime for theoretical understanding.\n\n2. We believe our analysis does reveal meaningful distinctions: \n- CGD does not consistently outperform EF or EF21 across all step sizes. The superiority of CGD only holds under optimal tuning. In fact, one of CGD’s key advantages is its ability to operate using significantly larger step sizes, which offers useful intuition for its behavior and performance trade-offs. We generated a figure (prior to the announcement disallowing new figures in the rebuttal process) that showcases, for any fixed $(\\eta, \\epsilon)$, the log-ratio of optimization complexities between CGD and EF: for instance, for $\\kappa=10$, depending on the step size, EF can be more than 100 times faster or 1000 times slower than CGD (in terms of number of steps required to achieve the same reduction in performance measure). We will add this figure to the paper.\n\n- The equality of rates between EF and EF21 in this setting was, to the best of our knowledge, previously unknown. This equivalence can be revealed only by analysis using an optimal Lyapunov function, as the optimal rate is achieved for a very different Lyapunov function. For a fixed Lyapunov function, the rates of EF and EF21 are *not* the same—we will also provide an illustration of this fact.\n\n3. Third, there exist links to quantized-aware-training of deep neural networks, which we should have highlighted (and will add): \n\nBinaryConnect [6], which is one of the most popular algorithms for *quantization-aware training* of neural networks, combines gradient steps with quantization steps. Although not directly equivalent to CGD or EF, it is a natural example of a **single-agent** algorithm that combines quantization and GD. The adaptation of EF in the context of sparse neural networks leads to the work of Lin et al. [7], who perform sparse neural-network training by applying only sparse updates, which is equivalent to error feedback. The authors note this equivalence at the end of Section 3 (and are themselves among the active contributors to the field of error feedback, as they have co-authored [1-4]). \n\n**Generally speaking, the single-agent setting is thus relevant to the design of training methods for sparse or quantized neural networks**—motivating the study of these algorithms even outside their typical distributed setting. \n\n\n\n- [1] S. Stich, S.P. Karimireddy. *The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication.* JMLR, 2020.  \n- [2] A. Ajalloeian, S. Stich. *Analysis of SGD with biased gradient estimators.* , 2020.  \n- [3] S.P. Karimireddy, Q. Rebjock, S. Stich, M. Jaggi. *Error feedback fixes SignSGD and other gradient compression schemes*. ICML, 2019.\n- [4] S. Stich, J-B. Cordonnier, M. Jaggi. *Sparsified SGD with memory*. Neurips 2018.\n- [5] P. Richtárik, I. Sokolov, I. Fatkhullin. *EF21: A new, simpler, theoretically better, and practically faster error feedback*. Neurips, 2021.\n- [6] M. Courbariaux, Y. Bengio, J-P. David. *BinaryConnect: Training Deep Neural Networks with binary weights during propagations*. Neurips 2015.\n- [7] T. Lin, S. Stich, L. Barba, D. Dmitriev, M. Jaggi. *Dynamic Model Pruning with Feedback*. ICLR, 2020.\n\n\n> Therefore, the phrasing in line 239 “These results challenge the prevailing intuition that error feedback ensures convergence comparable to that of uncompressed methods” is misleading: the lack of convergence is not a matter of intuition but a rigorously established fact. On the other hand, CGD converges without issue in the single-node case. \n\nThere might a misunderstanding here: the claim we make in line 239 (and that echoes the way methods using error feedback are sometimes understood by the community) is that methods using error feedback achieve rates of convergence almost equivalent to the \"no-compression case\" (uncompressed methods), not to the \"CGD case\". What we show is that in the single agent deterministic case, they neither recover the performance of GD, nor that of CGD.  More precisely, CGD, which we consider to be the baseline method in the single-agent setting, is considerably slower than uncompressed methods, and as EF and EF21 underperform relative to the baseline method in the single-agent case, they are by-extension also not comparable to uncompressed methods. \n\nWe thus think the phrasing of line 239 is fair, but can amend it if the reviewer believes it's misleading. \n\n>The paper lacks a clear rate comparison with classical results for EF [3] and EF21 [4]. In particular, Theorems 1 and 2 do not explicitly state the iteration complexity rates, and require additional manipulation to extract them.\n\n>Q: How do the convergence rates obtained in this work compare to the classical results for EF and EF21?\n\nWe agree that our original presentation did not make rate comparison easy. We highlighted the dependence on the step-size and the optimal Lagrange multiplier, but the resulting expression is not immediately comparable to existing bounds. For completeness, we provide below the cleanest closed form we have derived to date for our rate:\n$$\n\\rho = \n\\sqrt{\\epsilon} + \\left(\\frac{1 - \\sqrt{\\epsilon}}{2}\\right) \\left(\\frac{\\kappa - 1}{\\kappa + 1}\\right)^2 \\left[1 - \\sqrt{\\epsilon} + \\sqrt{(1 + \\sqrt{\\epsilon})^2 + \\sqrt{\\epsilon} 16 \\frac{\\kappa}{(\\kappa - 1)^2}}\\right],\n$$\nwhere $\\kappa := L/\\mu$. Showing that this bound strictly improves upon other existing rates, such as the one under the PL-condition rate of [1], is straightforward (and natural: we have a tight rate under stricter assumptions); quantifying the margin analytically is less so, though feasible. We will therefore include the above parameterization as a remark in the revision, together with both an analytical discussion and a visual comparison against the PL-based rate.\n\n>Q: What's the primary challenge of analyzing the distributed setting?\n\nThis is a very good question. The main bottleneck in extending our approach to the multi-agent case is that the candidate Lyapunov function space grows quadratically (the Lyapunov functions may contain gradients, compressed messages from different functions, and error feedback terms, as well as crossed inner products); should the optimal function involve dense coefficient patterns, obtaining a closed-form via our approach requires substantial additional effort. \nOne approach in that direction, that we are currently investigating, is the use of symmetries to reduce the size of the problem.\n\n---\nWe thank the reviewer for their support and remain available for any further discussion.\n\n---"}]

Author rebuttal:

Meta-review: This paper provides a tight theoretical analysis of EF, EF21, and compressed gradient descent in the simplified single-node smooth and strongly convex setting. Using the performance estimation framework, the authors derive optimal Lyapunov functions and matching lower bounds, establishing sharp convergence guarantees. The results show that EF and EF21 achieve equivalent rates despite different Lyapunov structures, and they clarify the performance trade-offs with compressed gradient descent under different stepsize regimes.

The reviewers praised the clarity and rigor of the analysis and the novelty of the Lyapunov constructions. The main concern was scope, as the work is limited to the single-node deterministic case. The authors clarified the extension to stochastic compressors and added explicit rate formulas. While one reviewer remained skeptical about practical impact, others found the responses convincing, and the discussion shifted the balance toward acceptance.

In my view, the work makes a solid theoretical contribution. The optimal Lyapunov functions are insightful: for EF, the form aligns with earlier analyses but gives exact weighting, while for EF21 the analysis reveals a structure not considered before. Although the single-node focus is a limitation, the results provide useful clarity. For the final version, the authors should make the changes promised in the final remarks, especially clarifying the scope and adding the key references mentioned in the rebuttal, while using their discretion if some works are too distant.
Decision: Accept (poster)