Composite Optimization with Error Feedback: the Dual Averaging Approach
Authors: Yuan Gao
Anton Rodomanov
Jeremy Rack
Sebastian U Stich
Venue: ICLR 2026 Poster (2026)
Keywords: Composite Optimization
Distributed Optimization
Communication Compression
Error Feedback
Dual Averaging
Primary area: optimization

Abstract: Communication efficiency is a central challenge in distributed machine learning training, and message compression is a widely used solution. However, standard Error Feedback (EF) methods (Seide et al., 2014), though effective for smooth unconstrained optimization with compression (Karimireddy et al., 2019), fail in the broader and practically important setting of composite optimization, which captures, e.g., objectives consisting of a smooth loss combined with a non-smooth regularizer or constraints. The theoretical foundation and behavior of EF in the context of the general composite setting remain largely unexplored. In this work, we consider composite optimization with EF. We point out that the basic EF mechanism and its analysis no longer stand when a composite part is involved. We argue that this is because of a fundamental limitation in the method and its analysis technique. We propose a novel method that combines _Dual Averaging_ with EControl (Gao et al., 2024), a state-of-the-art variant of the EF mechanism, and achieves for the first time a strong convergence analysis for composite optimization with error feedback. Along with our new algorithm, we also provide a new and novel analysis template for inexact dual averaging method, which might be of independent interest. We also provide experimental results to complement our theoretical findings.

Published as a conference paper at ICLR 2026
COMPOSITE OPTIMIZATION WITH ERROR FEEDBACK: THE DUAL AVERAGING APPROACH
Yuan Gaot
Anton Rodomanov Jeremy Rack
Sebastian U. Stich"!
ABSTRACT
Communication efficiency is central challenge in distributed machine learning training, and message compression a widely used solution. However, standard Error Feedback (EF) methods (Seide et al. 2014), though effective for smooth unconstrained optimization with compression (Karimireddy et al. 2019), fail the broader and practically important setting of composite optimization, which captures, e.g. objectives consisting of a smooth loss combined with a non-smooth regularizer constraints. The theoretical foundation and behavior of EF in the context of the general composite setting remain largely unexplored. In this work, we consider composite optimization with EF. We point out that the basic EF mechanism and its analysis no longer stand when composite part is involved. We argue that this is because of a fundamental limitation in the method and its analysis technique. We propose novel method that combines Dual Averaging with EControl (Gao et al. 2024a), a state-of-the -tht variant of the EF mechanism, and achieves for the first time a convergence analysis for convex composite optimization with error feedback that matches the best-known results the uncomposite setting. Along with new algorithm, also provide a new and novel analysis template for inexact dual averaging method, which might be of independent interest. We also provide experimental results complement theoretical findings.
INTRODUCTION
Gradient methods, and in particular, distributed gradient methods, are the workhorse of modern Machine Learning. In this work, we consider a simple yet powerful extension of the basic optimization problem, namely, the composite optimization problem:
min [F(x) = f(x) + (x)). xEdomg
where f: Rdd -> IR is smooth and :: Rd - R U f+oo} is a composite part. The composite optimization problem is ubiquitous in machine learning, and it covers wide range of variants of the vanilla optimization problem, for example, regularized machine learning (Liu et al.) (015)), signal processing (Combettes & Pesquet 2010), and image processing (Luke, 2020). Since v can take on the value of infinity, it also naturally covers the constrained optimization problem.
The sizes of datasets and models in modern Machine Learning have been growing rapidly, leading unique challenges in the training process and the need for optimization algorithms tailored to these new settings. The distributed optimization paradigm has become necessity due the fact that one simply does not have the capacity to accumulate the entire dataset while training modern ML models. One of the most popular setups
distribute the data across multiple clients/workers, and coordinate the model update on one server. Many of the recent breakthrough models are trained in such a setup (Shoeybi al. 2019 Wang et al., 2020 Ramesh et al. 202T 2022).
One of the main bottlenecks in scaling up distributed training is the communication cost. Transmitting the full large model updates between clients and the server can be prohibitively expensive when performed naively (Seide et al. 22044 Strom 2015). One of the most popular practical remedy is
communication compression with contractive compression (Definition 2.2) (Lin et al. 20188 Sun et al.
CISPA Helmholtz Center for Information Security, Germany. 1 Universität des Saarlandes, Germany.
(yuan.gao gao, rodomanoy, michacl.rade rack, stich) @cispa.de

---

Published as a conference paper at ICLR 2026
2019:
Vogels et al.
2019). Contractive compressions potentially biased, and naive aggregation of
these biased compressed updates can lead to divergence (Beznosikov et al. 2020). In the classical setting when d 0, one of the most basic and popular families of methods that used to rectify this issue in practice is the Error Feedback (EF) mechanism (Seide et al. 2014 Stich et al. 2018 Vogels) et al. 2019 |Ramesh et al. 202T). Due to its vast practical importance, EF mechanism has attracted significant interests in the theory community as well, where many works, though restricted to di = O, have attempted theoretically explain the effectiveness of EF (Stich et al. 2018 Karimireddy et
2019; Stich & Karimireddy] (2200) or derive variants of EF that enjoy better theoretical properties than the original form (Fatkhullin al. 2023 Gao et al. 2024a)
However, in the composite setting, the situation becomes much more complex, and the theory is much less developed. Existing works the composite setting either impose some further restrictions on the objective (Islamov et al. 2025), cannot handle stochastic gradients (Condat et al. 2022), or have suboptimal rates (Qian et al.](2200)
The goal of our work is address the general composite setting for the EF mechanism. We develop novel algorithmic and analytical tools, and we are the first to obtain rates for EF in the convex composite setting that match the uncomposite counterpart. We achieve the
R202 ng²
Rivlo
CR 8c
82
convergence rate, matching the rates of state-of-the-art EF variants when vb 0.
1.1 THE CLASSIC EF AND VIRTUAL ITERATION
Assuming that và = 0, let recall the classic EF mechanism and the main tool that is used to analyze it, the virtual iteration framework (Mania et al. 2017). to understand its drawbacks. On a high level, consider update rule of the form x X ge where gr is some estimate of the true gradient g, f (x:). EF provides a way construct such an g: when the gradient information can only be communicated after being compressed by the compressor C. We can summarize the basic EF mechanism in the following (for simplicity, we consider the deterministic and single client setup in the introduction):
(I) The basic (and essentially the only) tool that people have been using to analyze it is the virtual iteration framework (Mania et al., (017). which has been the foundation of most of the theoretical works on EF since some of the first thcoretical papers on EF (Stich et al. 2018). We consider the virtual iterate x,, defined as:
& = g: - et
g: = C(o)), et-1 == e + gr g:.
x x; ct--
The key insight here is that e, == Ei ge ). i.e. the accumulation of all the gradient errors, and the virtual iterate takes the true gradients as the update, i.e. X,+1 = X, , gt. where again, g: = (x, This enables the analysis to use the virtual iterate as a proxy for the gradient descent trajectories.
However, the combination of EF with virtual iteration does not extend directly to the composite setting. If we still construct g, by Equation (I) but update via a proximal step
X x arg min hy [8: x - x.) + vxx)) + " =| x, 12
xédom
then the virtual iterate X; X, h,e, is difficult interpret, it may lic outside dom & and thus cannot serve as a feasible proxy.
To contrast, when ta the iterates satisfy
Σ gB -
Σ g+
e,
so X; is simply the cumulative sum of gradient estimates, and subtracting e, recovers the exact -radient trajectory. This additive structure is what makes the virtual iterate analysis effective.
2

---

Published as a conference paper at ICLR 2026
When d # however, the proximal step in 2 introduces distortions at each iteration. The iterates X; can no longer be expressed as a clean sum of past gradient estimates, while e, remains a sum of compression enrors. This structural mismatch is preciscly why the classical virtual-iterate argument breaks down in the composite case.
1.2 OUR STRATEGIES
Following discussions above, it is clear that the classical EF mechanism and the virtual iteration framework need to be modified in order to handle the composite setting. In particular, we need to restore the simple sum of gradient estimates in the iterates, that e₁ still be used to correct the accumulated deviations from the true gradients. This reminds us of the Dual Averaging framework, where the algorithm sums up all the past gradients and take one step from the initial point each step. In general, we consider the following update rule:
X
arg min
Σ ON (BK. (x)))
+ Vt |x xoll2 2
xEdomp
where ok. Yt > O are some properly chosen coefficients. In this way, the iterates x, are defined precisely by the (weighted) sum of all gradient estimates Σi aggk. We can therefore consider the (weighted) cumulative gradient error e; == Ex=
k=0 (gt gx) and use it to correct the deviations of X₁ from the true gradient trajectory, this time inside the proximal operator:
X1+1 = arg min xEdom
as ( x) + +xx)) - (ee, x)
||x xol1?
2
k=0
arg min xCdomp
an ((g x) xxx)) + It
xol12
turns out that this intuitive modification of EF and the virtual iteration framework is precisely what we need to address the composite setting.
2 PROBLEM FORMULATION AND ASSUMPTIONS
We consider the following distributed stochastic optimization problem:
F
min x
[(()) -((x) +(xx)
where f(x)
Σ f((x,,
where x E I are the parameters of model that we train. We assume this problem has solution which we denote by x". The objective function F is a composite objective with the smooth part f(x) = Σ fx(x) and the composite part 1/ IRd + IR U (+oc). và is simple proper closed convex function. We write domy Rd to be the set where v is finite. Each function is local loss function associated with local data set D; which can only be accessed by client i. There are in be accessed by the server.
total clients indexed by E (1, (1...., n). The composite part
Let us define the problem class that we consider in this paper. There are two types of agents this problem: the server and the clients. The server has access the proximal oracle for any g, Rd and 7 E R.,, defined as arg e (g x') + (x') + ||| x |' We assume that each client i can access only the function fi and only via the stochastic gradient oracle as follows:
Assumption 2.1. For any x e dome', g: (x. E") is stochastic gradient oracle for fi at x, where ç is the randomness used by the oracle. We assume that gi (x. is unbiased and has bounded variance:
(x. { [x(x),, Eeg [x 5 (f(()) o
We consider the distributed setting where communication from the client to the server is expensive, and need compress it to reduce the cost. By (contractive) compression, mean the following:
3

---

Published as a conference paper at ICLR 2026
Definition 2.2.
We say that a (possibly randomized) mapping C(:,)): R + R is contractive compression operator if for some constant < I 1 holds
F [[IC(s. () - -s S (1 -]||s||
Vs Rd
(5)
Here Ç is some possible randomness used by the compressor. For simplicity, we will often omit Ç in the notation when there no confusion.
In addition, we assume that the cost of communication from the server to each client is negli- gible (Karimireddy al. 2019; Richtárik et al., 2021: Gao et al., 2024a), while the client can communicate with the server through the following two types of channels:
Compressed channel: The client can send compressed vector C(x, () Rd to the server, where C is contractive compression operator (see Definition 2.2 The cost of sending one compressed vector is 1.
Uncompressed channel:
The client can send a vector g E IRd to the server without any compres-
sion. The cost of sending one uncompressed vector is m 2
When the compressor is the Top- K compressor (i.e. the client only sends the top K elements of the gradient), then the cost of sending one uncompressed vector in IR is at most d/ K. In general, given any 6-compression in the sense of Definition 2.2 we can combine at most O 3 log f compressed messages to recover an 8' o'-compression for any > (He et al. 2023
this sense, one can
typically approximate an uncompressed channel with compressed channel with an O additional multiplicative overhead. That is, we can typically think of m to be of the order }.
In this work, we are interested in minimizing the total (client server, uplink) communication cost of the algorithm (for each client). Suppose that throughout the algorithm, each client makes compressed communications and uncompressed communications to the server, then the total communication cost is a + mb. This is roughly proportionate to a + 5. We do not consider the communication cost from the server to the client (broadcast, downlink cost) since it typically much lower than the uplink cost, which is conventional in prior works (Karimireddy et al. 2019 Richtárik ct al. 2021 Gao et al. 2024a).
Let us now list the assumptions on the objective functions that make in the paper. First, make the standard assumption that f is convex.
Assumption 2.3. We assume that the function f and vi are convex, closed and proper over the convex domain domeh.
We note that we do not assume that each local function f, is convex. We also assume that f is L-smooth, which is standard in the literature (Stich et al. 2018 Karimireddy et al. 2019 Richtárik
ct al. 202T, Gao et al. 2024a)).
Assumption 2.4. We assume that the objective function f has I.-Lipschitz gradients, i.e. for all x,y dome), holds
| fxx) - f.((y)] < -||l-
(6)
We also assume the following smoothness condition for the local functions fi.
Assumption 2.5. We assume that there exists some f 0 such that for all x, E dom(w)) it holds
n V
f1 < -1
(7)
72
Remark 2.6. Note that this is weaker condition than what many existing works assume, c.g. (Richtárik et al. 2021] Li Richtárik] 202I), where they assume that all fi's are Lmor-smooth. In contrast, we only require that they are in some sense smooth average, which is strictly weaker.
We point out that by Jensen's inequality, we always have that L < E. In the analysis of our main method, Algorithm 2, we eventually only need Assumption 2.5 However, Assumption 2.4 is still important for the analysis of the inexact dual averaging framework that we propose, as does not presume any finite-sum structure of f.
4

---

Published as a conference paper at ICLR 2026
Algorithm 1 Inexact Dual Averaging
1: Input: Xy and {a,, Yt E RR+ too.....oo 7 is non-decreasing.
2: for 1= 0, l.... do
3: | Obtain g: = g: = g(x,, Ex). Ee is an independent copy of
4: Xx+1 = arg milly (x)x) = Ei o (x({(xx)) + (gi, x Xx) + xx(x)) - 211xx - xol1²
THE INEXACT DUAL AVERAGING METHOD
In this section, we take a step back from the distributed optimization problem with communication compression that we consider in the rest of the paper, and consider solving a general stochastic composite optimization problem of the form f* minxedome (F') = f(x) + (x)]. This perspective allows compressed communication. Here, we do not assume that f has finite-sum structure. We make Assumptions 2.3 and 2.4 for the objective in this section. We assume that we have access stochastic gradient oracle g gxx,E) satisfying Assumption below:
develop the core analytical tool that underpins our later analysis with
Assumption 3.1. For any x E domp, g(x. {) is stochastic gradient oracle for f at x. We assume that g(x, {) is unbiased and has bounded variance:
(x, c) = V fx)), Ee
S
(8)
We study the convergence of the general inexact dual averaging algorithm, as summarized in Algo- rithm [ for solving this problem. The algorithm gets some inexact gradient ge that approximates the stochastic gradient g: := g(x, Xr, Er) at each iteration. It uses these gradient estimates to perform dual averaging update, with stepsize parameters a, and ?/-- We assume that % non-decreasing.
We analyze the convergence of this method from the perspective of the virtual iterates, which are defined in Equation (9). We note that these virtual iterates are not explicitly computed or stored anywhere in the algorithm. However, since our convergence analysis will be given in terms of the suboptimality of convex combination of or random sample of the virtual iterates, an immediate question would be how to output such convex combination or random sample at the end of the algorithm without explicitly storing and computing the virtual iterates. We will addres this in Section 3.1
Let's write g:
Ek Ogge We define the following virtual iteration, with Xo Xo:
22 xx(x) = on (f(x)) + (Bx, x Xa) (x)) + 7t ||x xol12
- = arg min
xEdoms
2
k=O
(9)
arg min
x) (x(x) Σ
ak + Vt ||x ||x- xol13
xodomp
k=0
2
Now, we define the accumulative error of the compressions:
g+). -.)).
(10)
k=
We first show that the distance between the virtual iterate x, and the actual iterate x, is controlled by the accumulated error e;:
Lemma 3.2. For any 2 0, we have:
xx
x2
12
(11)
We simply write 7-1 No- Note that e, = 0. With this, we can give the main convergence theorem for the virtual iterafes:
5

---

Published as a conference paper at ICLR 2026
Theorem 3.3. Given Assumptions 3.1 any T 2 1, we have
2.3 and 2.4 and n--1 4a,L, then for any domb and
T
B (F(((()) - F(x))] + 7T-1
E
||x Xr|(7]
2
T-1 + +..
az (12) Σ
YT-1 x
xoll
E.
[ I +
2
t=0 T--1
1= x
In addition, we have the following upper bound on the distance between consecutive iterates:
T-1
+ 7--1 act
20h Ti +
(Bi-
Xx+1 - xi) s Fo V fx((x)
Σ
T-1
(Bepf - :.Pp+22) (13)
2 1=
1=0
where we write Be == -1-70-
P = |x, xoll?, = | x,12 and Fo F(xo) F*.
ae
Again, we note that Equation 12 deals with the virtual iterates. When vi O. typically we can bound the distance between [( (x+) and f(x,) simply by E |||e;]]]] This is, however, unclear when d * O. It is possible directly analyze the behavior of x2 without using the virtual iterates at all, but the analysis obtained that way will be weaker due to the presence of v (see Appendix [1 for a more detailed discussion, we further comment here that the techniques employed in Appendix [ can also be used to obtain analysis of the proximal method without dual averaging, albeit with similarly weak guarantees). It remains an open question whether it is possible to directly analyze x, without using the virtual iterates and still obtain a result as strong as Theorem 3.3
In addition, we also obtain an upper bound on the distance between X and x,, which will be useful later. Similar upper bounds the distance between consecutive iterates have been used in many existing works that applied the gradient difference compression strategics (Richtárik et al. 2021 Fatkhullin et al. 2023 Gao et al. 2024a), but these are typically upper bounding the individual distances. Due to the dual averaging strategies, our analysis here is significantly different, and we are only able upper bound the sum of the distances.
We point out that controlling the error || Vf((x)))' how constructed the approximate g., Therefore do not further analyze this term here, and discuss this term in more details when we present the analysis of our main algorithm in this work.
II? is method method-dependee dependent, that is, it depends on
3.1 A SAMPLING PROCEDURE FOR THE VIRTUAL ITERATES
Provided that the errors are sufficiently small, Theorem 3.3 allows to establish the convergence rate terms of AT IT- (F( F*), where x, are the virtual iterates rather than the real iterates X2 and we write A, E'=0 ag.
Therefore, after T' steps, we would like to return a randomly chosen point among {XI...., Xy} with the probabilities proportional de- This can be implemented follows: at each iteration t, we keep track of the accumulated true gradients g: Σ. agg, and update g to gr when = 1, and it remains unchanged when T; = 0. where 7 is a Bernoulli variable with probability Pr [T 1] A.4 This way, at step T 1, g is random sample from the set (o.).e .T-1) with probabilities proportional to at,, see Proposition E. Using g. we can easily compute a random sample xy from the set { as follows:
X7 = arg min
(g. x) + (xx)
a:
+
2r ||x 2
xoll2
xcdomp
We summarize this procedure in Algorithm
3 in Appendix As consequence, we have the following: Lemma 3.4. The outpul Xx from Algorithm is a random variable over the set (XIeetT), where &, defined in Equation 9 In particular, we have for any x E dom(v) (that are independent of {Ee, Ti Te)
1 T
E E L [F((T) F(x) =
Σ
o E
fr-1 [F(x+1)) - F(x)]
(14)
AT

---

Published as a conference paper at ICLR 2026
Algorithm 2 EControl with Dual Averaging
1: Input: Xo. 77, ej = 0, g- = (. Cb).
2: for t = 0, 1.... do
3:
Server:
4: Sample = 1 with prob.
1 and T, 0 otherwise. Send T to all clients. x41
5:
clients:
6:
gi [xi( (t) where şi is independent copy of e
g = --
7:
g' Bi if = otherwise g' remains.
8:
oj gi Bi-1 -,,,, A = C(6), G)
where Ç is independent copy of C².
9:
g: - 4 e/+1 e gi gi
10:
send A to the server
11:
server
12:
É: B
A
13:
Xt+1 arg minx (x) = (f(()) + (8., - xx) + xxx)) + - ||x - 13}
client: send g' to the server
15: server:
16: g = Н g
17: Xy = arg min (g. x) + (F + 1)x(x)) + 3/111xxx - xoll²} where T is the last t s.t. T₁ = 1.
4 EControl WITH DUAL AVERAGING
In this section, we apply the general framework discussed in Section 3 to the particular case of distributed optimization with communication compression. In such a setting, the stochastie gradient in is
Assumption js the average of the stochastic gradient each client i, which follows Assumption 2 Therefore, 0 a² where n is the number of clients. Now the gradient estimate & is the average of gi where each gi each client's estimate of its local gradient g: g(x,, {i), which can be communicated to the server using compressed communication channels.
The sampling procedure in Section 3.1 ge and g do not need to be maintained and communicated by the server throughout the algorithm; instead, we can simply ask the workers maintain their local g and g', using the same random bit (which costs bit of communication). At the end of the algorithm, we use one full communication round to collect the local g' and compute the output Xy. In total, the above procedure costs exactly round of full communication plus one extra bit in each of the T communication rounds.
can be easily implemented in such setting. The variables
Now, as the main focus of this section, we present a specific mechanism of generating the g. R gr- the EControl method (summarized in Algorithm in Appendix G), using mainly compressed communication channels. We assume that de = for all I. For simplicity, this section we also assume that % ry for all for some constant 7 > 0. In Appendix H present more advanced analysis of Algorithm 4 that handles variable %/- The variable stepsize analysis for EControl mechanism is unknown prior to this work due the complexity of 1) parameter in EControl and we have to employ a scaling/rescaling strategy in the analysis to handle it. We slightly modified the presentation from (Gao al. 2024a) to suit our setup better. We can put Algorithms together to get our final algorithm, EControl with Dual Averaging, summarized in Algorithm (see Appendix [ for more detailed walk-through of the algorithm). We highlight the EControl module with green color.
and 4
We note that the EControl mechanism was first proposed in (Gao et al. 2024a) and analyzed under the condition v = 0. In Appendix G we briefly discuss some intuitions behind the design of EControl. Here we present more systematic and hopefully cleaner analysis. We simply bound the sum of errors by the average of stochastic gradient differences. We note that the following upper bounds are entirely the consequences of the EControl mechanism, independent of the specific properties of the objectives and oracles.
7

---

Published as a conference paper at ICLR 2026
Lemma 4.1. Let 1
3v1-8(1 v1-8y then:
Σ |ell? 81(1 - -8) v1- 0) T-2
Ig 88+1 g/l?
26
(15)
T-1 Σ
36(1 - 5) vI 8)2
7-2
| gill
|8++1 g/l?.
82
Remark 4.2. We point out that in the analysis of the classical EF mechanism, upper bounding # - || relies on upper bounding : ビi (x,))l which leads to the data heterogeneity assumption, but more importantly. requires upper bounds on [Vxxx)] 1 in terms of the function residuals. When
0, this follows directly from the smoothness of f. However, in the composite setting, this is no longer possible unless Vx(x*) = O, which is not true in general. In contrast, EControl uses the gradient difference compression technique obtain a better handle on the errors and we only need to upper bound + > g gill which again can be done via Assumption 2.5 and Equation (13).
Next, we invoke the specific properties regarding the smooth objective f and the stochastic oracles, and apply Theorem 3.3 to get an upper bound on the sum of ||g/+1 - gill. and consequently, an upper bound on the sum of ||e|
Lemma 4.3. Given Assumptions we have:
2.
and
2.3
2.5
and let 11 1111-601+i- 72 24v then
T-1
806
E
gi
1=1
Fo + 7To2
(16)
9y
t=
1=1
Therefore, by Lemma 4.1
also have:
T-1
5760E 54hy
4536T
[
Fo +
(17)
84
t=
Finally, combining all of the pieces in Sections and guarantec of our final Algorithm 2
we can give the overall convergence
Theorem 4.4. Given Assumptions 2.3 to 2.5 and setting at 1,7r 7 1 3 3VI-0(1+v1-3 and
taking initial stochastic gradient step from x x/y if t/ # 0 and setting
24
To²
/// %
7 max
nRg
R &
then it lakes at most
T 16R30²
561R3 Vlo
96
ns2
82 Here, Ro = I|x - x
de
iterations of Algorithm to get E
In particular, this means that with three rounds of uncompressed communication (one for the initial stochastic gradient step, one communicating g-1 and one communicating g). and T rounds of compressed communications, Algorithm reaches the desired accuracy. Assuming that the cost of sending compressed vectors is 1 and sending uncompressed vectors is m, it costs at most
16R302 n222
561 RI 96
+mn,
82
de
in communications for Algorithm to get:
[
SC.
Remark 4.5. In the statement of Theorem 4.4 we let the algorithm take one initial exact stochastic gradient step in the composite setting. This comes from the fact that we need one gradient step the composite setting to upper bound Po by LRR (see Lemma C.3 This is satisfied automatically in the classical unconstrained setting. Without the extra initial step. the algorithm would still converge (with properly chosen step size), but the rate would additionally depend on Fo (though it would still be desirable ( se ) term). We refer to Appendix G for more details. We note that the rate in Theorem 4.4
matches the rate of EControl (Gao al. 2024ab in the basic uncomposite setting when &i = 0.
8

---

Published as a conference paper at ICLR 2026
3.0
todeo
3.0
2.5
Loss
Loss
2.0
2.0
1.5
1.5
10a
101 Iterations
10a
100
200
300
400
500
Iterations
(a) Achieving linear speedup. Performance of EControl with Dual Averaging with increasing number of clients n. We fix y to be 0.0001. The emror that the algorithm stabilizes around decreases as increases.
(b) Virtual Iterates vs Real Iterates. The perfor- mance of the virtual and real iterates of EControl with Dual Averaging. We see that the virtual iter- ates and real iterates perform similarly.
Figure I: Performance EControl with Dual Averaging on a synthetic regularized softmax objective.
5 EXPERIMENTS
In this section, we present some experimental results on a synthetic softmax objective with & regu- larization to complement our theoretical analysis. Details of the experimental setup (including data generation) and an additional experiment on the FaShionMNIST dataset are presented in Appendix B All our codes for the experiments can be found at this link
The
softmax
objective
with E1 regularization
is given as:
A| where l controls the smooth- ness, and set a 0.1. We set the regularization parameter À 0.1. We set the dimension = 200 and the total number of samples k = 2048. We simulate the stochastic gradient by adding Gaussian noise the gradients. We use Top-K compressor with K/a 0.1. For both of the following experiments, we set 0² 25.
mingeRd [(()) = μ log E exp
Linear speedup with n: one of the key characteristies of EF-style algorithms is that the leading (stochastic) term in its rate improves linearly with the number of clients n and is d-free. We prove that EControl with Dual Averaging does satisfy this quality-with the catch that the theory only applies to (the random sample of) virtual iterates. Here we verify this property experimentally for the real iterates directly. We fix small enough y to be 0.0001, and increase the number of clients n. The results are summarized in Figure Ta We see that the error that real iterates stabilize around decreases linearly with n, verifying the linear speedup for real iterates as well.
Virtual iterates real iterates: while we can do the sampling procedure to obtain convergence in terms of the virtual iterates, this is ultimately still somewhat clumsy in practice. The real iterates, on the other hand, do not enjoy convergence bounds that of the virtual and the real iterates. The results are summarized in Figure [b] We see that the virtual and real iterates perform almost identically in the suboptimality. This suggests that the real iterates might also be amenable to a strong theory; future work might explore refining our analytical template in Appendix to achieve this, construct lower bound examples demonstrate gap between the virtual and real iterates.
good. Here, compare the suboptimality
6 CONCLUSION
In this work, we addressed the open challenge of combining eттоr feedback with composite opti- mization. We showed that the classical virtual-iterate approach breaks down in this setting, as the composite update destroys the additive structure that underpins its analysis. To resolve this, we introduced the first framework that integrates error feedhack with dual averaging, which restores the summation structure and enables control of accumulated compression errors. Our analysis extends
https: httpss///tttnabbaooo//////a///op

---

Published as a conference paper at ICLR 2026
the theory of error feedback to the convex composite case and recovers the best-known results in the unconstrained setting when v = O.
Looking ahead, our inexact dual averaging analysis provides versatile template for problems where iterative updates are distorted by approximation, noise, or constraints. This opens up promising directions in domains such as safe reinforcement learning, constrained distributed optimization, and large-scale learning under resource limitations. An exciting avenue for future work is to connect our approach with recent efforts that aim to simplify error-feedback methods for practical use, potentially leading to more robust and scalable communication--ffiiiee algorithms.
REFERENCES
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Proceedings of Advances in Neural Information Processing Systems, 2018. 13
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression
for distributed learning. Journal on Machine Learning Research, 2020. 2 13
Patrick L. Combettes and lean-Christophe Pesquet. Proximal splitting methods in signal processing, 2010. 1
Laurent Condat, Kai Yi, and Peter Richtárik. EF-BV: unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization. Advances in Neural Information Processing Systems,
2022. 2 13
Jean-Baptiste Cordonnier. Convex optimization using sparsified stochastic gradient descent with memory. Technical report, 2018. 13
Ilyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves error feedback! arXiv preprint arXiv: 2305.15155. 2023. 13
Hyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. Journal of Machine Learning Research, 2025.
Yuan Gao, Rustem Islamov, and Sebastian U Stich. EControl: Fast distributed optimization with com- pression and error control. In The Twelfth International Conference on Learning Representations. 2024a.
6
13 20
Yuan Gao, Anton Rodomanov, and Sebastian U Stich. Non-convex stochastic composite optimization with polyak momentum. In Forty-first International Conference Machine Learning, 2024b. 19
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging еrror compensated SGD. In Proceedings of Advances in Neural Information Processing Systems, 2020. 13
Yutong Hc, Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and accelerated algorithms in distributed stochastic optimization with communication compression. arXiv preprint arXiv: 2305.07612, 2023.
Rustem Islamov, Yarden As, and llyas Fatkhullin. Safe-EF: Error feedback for non-smooth con- strained optimization. In Forty-second International Conference on Machine Learning, 2025. 2
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signSGD and other gradient compression schemes. In Proceedings of the 36th International Conference Machine Learning (ICML 2019), 2019.
13
Zhize Li and Peter Richtárik. CANITA: Faster rates for distributed convex optimization with
communication compression, 2021.
10

---

Published as a conference paper at ICLR 2026
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. International Conference on Learning Representations, 2018. T
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Pensky. Sparse convolu- tional neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2015.
D. Russell Luke. Proximal Methods for Image Processing, pp. 165- Springer International Publishing, Cham, 2020, ISBN 978-3-030-34413-9 doi: (0.1007/978-3-000-44// 3000000-4433-----01 6. URL 34413-2
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and
Michael I Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM
Journal on Optimization, 27(4):2202- 22029, 2017. 2
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint /0t1::/90/00000000 2019. 13
Mohammad Moshtaghifar, Anton Rodomanov, Daniil Vankov, and Sebastian U Stich. DADA: Dual averaging with distance adaptation. In OPT 2024: Optimization for Machine Learning, 2024. [4
Xun Qian, Hanze Dong, Peter Richtárik, and Tong Zhang. Error compensated proximal SGD and RDA. In Proc. 12th Annu. Workshop Optim. Mach. Learn., pp. 1-33, 2020. 13
Xun Qian, Hanze Dong, Peter Richtárik, and Tong Zhang. Error compensated loopless SVRG, Quartz, and SDCA for distributed optimization. arXiv preprint arXiv:2109.10049 2021a. 13
Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed SGD can accelerated. In Proceedings of Advances in Neural Information Processing Systems, 2021b. 13
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference Machine Learning, pp. 8821-8831 PMLR, 2021.
1
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. 2022.
Peter Richtárik, Igor Sokolov, and lyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. In Proceedings of Advances in Neural Information Processing Systems, 2021.
6 13
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. Proceedings of 15th annual conference of the international speech communication association. 2014.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick Le Gresley, Jared Casper, and Bryan Catan- zaro. Megatron-lm: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv: (tt0:::99900000000 08053, 2019.
Sebastian U. Stich. On communication compression for distributed optimization on heterogeneous data. arXiv preprint arXiv: 2009.02388, 2020. 13
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. Journal of Machine Learning Research, 2020.
Sebastian U Stich, Jean Saan-Bapistte Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In
Proceedings of Advances in Neural Information Processing Systems, 2018. 4
13
Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In Proceedings of Interspeech 2015, 2015.
11

---

Published as a conference paper at ICLR 2026
Haobo Sun, Yingxia Shao, Jiawei Jiang, Bin Cui, Kai Lei, Yu Xu, and Jiang Wang. Sparse gradient compression for distributed SGD. In International Conference on Database Systems for Advanced Applications, pp. 139-155. Springer, 2019. !
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems 32, 2019.
Meng Wang, Weijie Fu, Xiangnan He, Shijie Hao, and Xindong Wu. A survey on large-scale machine learning. IEEE Transactions on Knowledge and Data Engineering, 2020. [
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. In arXiv, 2017. 14
CONTENTS
1
Introduction
The Classic EF and Virtual Iteration
1.2 Our Strategies
2
Problem Formulation and Assumptions
3
The Inexact Dual Averaging Method
3.1 A Sampling Procedure for the Virtual Iterates
4
EControl with Dual Averaging
5
Experiments
6
Conclusion
Related Works on Error Feedback and Communication Compression
13
Additional Experiments and Details
14
B.1
Synthetic Softmax Objective
14
B.2 Regularized FashionMNIST Classification
14
Auxiliary Facts and Results
14
Analysis of Inexact Dual Averaging
16
Sampling Procedure for Virtual Iterates
19
Description of Full Algorithm
19
Analysis of the EControl Mechanism
20
H EControl with Variable Stepsize
24
12

---

Published as a conference paper at ICLR 2026
Analysis of the Real Iterates
28
A RELATED WORKS ON ERROR FEEDBACK AND COMMUNICATION COMPRESSION
In this section, we survey some of the most relevant works on EF. We note that while there's 's a rich body of literature on EF in the uncomposite setting, the extension to the composite setting less developed. [Stich et al. (018): Alistarh et al. (2018); Karimireddy et al. (2019) were among the first to explore the theoretical properties of the practical EF mechanism proposed by Seide ct al. (2014), but their analyses are restricted to the single-client setting. Under certain forms of bounded data heterogeneity assumption (e.g. bounded gradient, bounded gradient dissimilarity. or bounded local objective gap optimum), Cordonnier (2018); Allisarr et al.] (2018) (Stihh & Karimireddy (2020) extended the analysis to the more realistic multi-client settings. But these data heterogeneity assumptions are indeed very limiting factors. These theories were further refined in (Beznosikov
ct al.
2020 Stich 2020).
Another line of work parallel the classic EF variants is the gradient difference compression mech- anism. Mishchenko et al. (2019) added an additional unbiased compressor for gradient difference into the EF framework address the issue of data heterogeneity and obtained the DIANA algorithm. Another of follow-up works include Gorbunov et al. (2020); Stich (2020); Qian et al. (2021b), and culminated in the EF21 algorithm (Richtárik et al. 2021). The EF21 algorithm is the the first to fully support contractive compression in the full gradient regime. However, it is not compatible with stochastic gradients and leads to non-convergence up to the variance of the stochastic oracle. This was later addressed by adding momentum in (Fatkhullin et al., (023), or by more careful blend of EF and gradient difference compression in (Gao et al., 2024a). The latter work proposed the EControl mechanism, which is the basis of Algorithm in this paper.
All of the above focus on the uncomposite setting, and their extensions to the composite setting remain largely unexplored. Qian et al. (2020) considered a proximal variant of the EF mechanism, which they called CC-ProxXGD. However, their work considered the finite-sum stochastic setting, and their convergence rates have ( dependence on the compression quality, which is suboptimal compared to the state-of-the-art EF variants in the uncomposite setting. Perhaps more relevant to our work their EC-RDA algorithm, which is a dual averaging variant of the basic EF mechanism in the finite-sum setting. However, the analysis of EC-RDA relies on (in addition to smoothness) a number of bounded gradient assumptions on the objectives and the regularizers which we do not assume in our work, and their rates have a cubic dependence on which is even more undesirable. In (Qian et al. 2021a), the authors proposed and analyzed several variant-reduced EF algorithms in the composite setting, but these algorithms are designed for the finite-sum setting and are not applicable to our setting. In particular, their EC-LSVRG requires periodic access to full gradients. Their EC- Quartzz and EC-SDCA considers a more specific form of composite objectives and requires access to the first order information of the conjugates of the regularizers. More recently, Islamov et al. (2025) analyzed variant of EF, called Safe-EF. when v is indicator function of some convex set Q. Their analysis requires that the constraint set Q be described as an intersection of sublevel sets of functions, with first-order information of these functions available. Under this structural assumption, their method blends updates in the direction of both the objective and the constraint functions, enabling the virtual iterate to account for constraints. Sa also assumes that the stochastic gradients are bounded, which circumvents the issue of upper bounding || [x,
II in the smooth case.
Since Richtárik et al. (2021) first analyzed EF21 in the non- com-ootpo full gradient regime, there have been some attempts to extend EF21 to the composite setting. In particular, FFatkuulin et al. (2025) analyzed proximal version of EF21, but only in the nonconvex and full gradient regime. Condat et al. (2022) proposed the EF-BV algorithm, which (in addition to unifying EF21 with DIANA) extends the analysis of EF21 to the composite setting. But EF-BV's analysis is also restricted to the full gradient regime, and assumes either the PL or KL condition with strictly positive constants. It is unclear whether their analysis can be extended to the general convex setting even with full gradients. Recently, Islamov et al. (2025) extended the analysis of EF21 to the general convex composite setting, but noted that their analysis requires a bounded domain assumption, which we do not assume in our work.
13

---

Published as a conference paper at ICLR 2026
1.
Accuracy
0000
15.0
6.7
Plus wiit Klemein
Iterations
Iterations
Figure 2: Superior performance Comparison of the performance of EControl with Dual Averaging, proximal EF, and proximal EF21 on the FashionMNIST classification problem with & regularization. We use Top-K compression with 5 0.1. We see that EControl with Dual Averaging significantly outperforms the other methods.
B ADDITIONAL EXPERIMENTS AND DETAILS
In this section, we provide some additional experimental details for our experiments in Section and additional experiment on the PashionMNIST dataset.
B.1 SYNTHETIC SOFTMAX OBJECTIVE
We generate the data {a b randomly, following Moshtaghifar et al. (2024): we generate i.i.d. vectors å; whose entries are sampled from [-1, uniformly random. Each is generated the same way. This leads to a preliminary objective f. We then set a, == à f()) The resulting {a,, b gives us the desired objective with 0 being the minimizer.
For the experiment comparing the virtual and the real iterates, we perform a grid search for the stepsize parameters over E {0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001).
7
B.2 REGULARIZED FASHIONMNIST CLASSIFICATION
We consider logistic regression problem with & regularization the FashionMNIST dataset (Xiao et al. 2017). We set the regularization parameter À = 0.001. We compare the performance of EControl with Dual Averaging against the proximal EF and the proximal EF21 methods. Following our synthetic experiments, we choose to evaluate the performance of EControl with Dual Averaging directly with the real iterates. We split the FashionMNIST dataset into n 10 clients, and distribute half of the dataset randomly to each client, and assign the rest of the dataset according their labels, i.e. data with label is distributed client We use Top-K compressor with K/d = 0.1. We use batch size 64. We perform grid search for the stepsize parameters over E (0.1, 0.01, 0.001, 0.0001). The results are summarized Figure We see that EControl with Dual Averaging significantly outperforms the other methods. In additional, we note that EControl with Dual Averaging admits much larger stepsize than the other methods, which might explain its superior performance.
C AUXILIARY FACTS AND RESULTS
In this section we collect some auxiliary facts and results that are useful for the analysis of our algorithms. The first one is simple fact regarding the square of the norm of sum of vectors.
Fact C.I. For any 71....
:....:::77 YT, we have:
T
T
Σ
ST
1.
(18)
t=1
t=1
The next lemma upper bounds an exponentially weighted sum positive sequences:
Lemma C.2. Given sequence of non-negative values fas hee(T-I) and some other sequences {ur he(r-1) - If there exists 7 E (0, 1) such that the following holds:
04+1 & (1 -3)oz + Wt. 0g
0,
(19)
14

---

Published as a conference paper at ICLR 2026
then we have:
1 T
a2+1
1
Σ
(1
3)
u
Σ
ai+ -
Σ
u
(20)
3 k=0
32
Proof. Since og- 0, we have:
0++1 S =1 3) uu
(1
k=0
Squaring both sides, and applying Jensen's 's inequality, we have:
2 S St k=
(1- k uuk
(1
where St = -E= 3) It's easy check that S. S 3. and therefore we get the first part of
Equation 20 Now summing this from f t T, we get:
Σ
(1-
k=U
t=k
Note that Et= (1 -1-111---- B)** <
1 B. and therefore we get the second part of Equation (20).
Now show that one gradient step will lead to upper bound on the objective value.
Lemma C.3. Let f be convex and L-smooth, and X, E dom( and go satisfying Assumption 3.1
consider Xy defined as the following:
X =
arg min mrg
[f(x)) + (go, xo) + xxxx
+ To ||x xol22 2
then for any E domb and |ly - xol12 s R2, if we choose To max /20)
we have:
Ro V2
B[F(x)) -(y)) s LR
E B
- x111 s 2R
(21)
Proof.
f(xo) + (g, xy xo) + (xx))) + 70
| xxll 2 + 7o Ily x611
2
2
00
5s(xo) + ygo y - xo) + xyy) + |ly xo112
2
=s(x)) + (VI((x)))) y - xo) + xyy) + 2u lly - xo112 2 + (go - V[((o), -xo)
マ
<F(y) + - ly 30 (go vf(x)), y -xo)-
On the other hand, we have:
f(xx) + (go, xo) + (x6x)) + 70 xx11 xu xul + 7o Ily x6112
2
=f(xx) + (V)()))) x1= xo) + +xxx + (go V
(i(xn), X6 - xx) + 70 ||x - xol
+ 70
yly x6112
2
2
2/(x() + (go V (x(o), X xx) + 70 L
xol12 + 70 Ily x 11?
2
2F(x6) 7
1
go vf(x)) 2 70- - 2L
|x xol 12
70 lly x/ 11
Putting these together, we have:
20 lly x 2 70 2L
4 ||x
xx01
700 2
1go 2 (go0)++-8//02 - (oxoV((x)).
2
70
15

---

Published as a conference paper at ICLR 2026
Now by Assumption
3.1
take the expectation and get:
0²
E
vf(x)))l + (go y V-xo)
xo) 5
70
70
Therefore, assuming that 70 2L, we have:
0²
[[ F(y)] + 20
E
[ x611?1
20 n²
2
70
Now we pick 70 max (2L, V2a J. then we have:
R
[F((x) F(y)] - LR + Ra
V2
In addition, we have:
E [lly - T11 S R + +2700² 2R
D ANALYSIS OF INEXACT DUAL AVERAGING
In this section we give the missing proofs for the analysis of Algorithm 1 following notation:
We first introduce the
क = (x Φ = (x(+1),
the optimum of the virtual and real subproblems at
We now present the proof of Lemma 3.2
Lemma 3.2. For any 2 0, we have:
1
Xx xel1² S 2 1|e.11?
(II)
76-
Proof. By the definition of t,, 4, and Xx, we have:
x = arg min (o,(x) + (el+1,x)}
xVdom(v)
Therefore, have for any dom( ()):
L (x) + (er+1, 2 o (xx+1) + xe++1, + 711 ||x x++112
2
> के + (e.+1,x)) + 2
||x x1-1
Yt +
|xc+1 x
2
Now plug in the choice x = x,+1, we have:
(e++1, 8e41 Xx+1) 2 70 x| 11
Note that we have (er41, Xe+1 x < ||e X X++1ll. we get the desired result.
We now present the proof for Theorem
3.3
Theorem 3.3, Given Assumptions 3.1 2.3
and 2.4 and 7--1 2 La,L, then for any x E domp and
any T 2 have
E (F((4t))) - -Fxx)) + TT- E [||x
[|xx-xr11 xr
2
1=0
T-1 a
T-1 d
Yr-1
x X 2 + L
Σ
[|e
+
(12)
2
カ-1
In addition, we have the following upper bound on the distance between consecutive iterates:
T-1
+ 7-11 - a,L 2 + (g. v fx(x), x.+1 xi) < Fb +
Σ (Bip) - -Bppita) (13)
20:
1=0
1=0
where write Bg == 70-7011
p4 == ||x x
1012, = || xz and Fo F(xo) F².
as
16

---

Published as a conference paper at ICLR 2026
Proof. By the definition of X,, we have for any x E domeh:
px(x)) 2 : + 2 xx -x+1112
2
We also have:
fx(x)) ak (f(xx) + (Vf(x)), x xxx xxxx)) + Σ
Σ
a# (gk Vf(xx), x xx) + 71 "111x= xoll²
k=0
k=0
(1)
Fx) +
Σ a4 (gk vf(xx),x- xxb + I'' x xxll k=0
where in (i) we used the convexity of f. Note that the gradient noise gk V (xx)) independent of X2 for fixed x independent of the algorithm (in particular, for x*). Therefore, taking expectation on both sides:
E $
(x()
- Σ az F(x) + [|x -xol2
k=
Now by the definition of Xx, we have:
az (f + [x;((x;))..)))))))))>())) Xx+1 Xx) (X(+1))
+ a - vf(xx)), X1+1 - xz) + 7/t
7t-
[x,+1 - xoll
2
1 1 + M- | 1 11 + ael (e(f((x)
+ f x,+1 - x2) + (xx+1))
+ + [x(())) x,+1 - x,) + 7t- 7t-
X141 - xoll
2
(10)
0 1-1 + Yt-1
| -x + as (x(+1)
(X1+1)
7. || -x(l33)
L
2
2
+ 0 - [xx())), X++1 - xx+) + 7tt 7t-
|x xoll
2
(10)
1-11 2
7--
|x - =1 + ac [ (xx+1) - L1|3++11 x1,1 - L||se xxl1?)
+ ar ag( - (x((x)), Xx+1 - xx+) + 7/t 71-1
|x++1 xoll
2
(0)
Φ 7t-1 200L ||xc+11 - xxll + as ((x++)) - at T. x, 1|
2
+ agi vf(xi),
kx+11 -x,),
where in (ii) we used the strong convexity of e and in (iid) we used Assumption 2.4 In (iv) we used Young's 's inequality and in (w) we used that assumption that yt is non-decreasing. Note that the gradient noise g: V (x:) is independent of x, and X,, we have:
M-- 20,L
Ee, t Eo.......... E.......1111
2 Rg,
T+ i-1 +
1x+11 xx + a, F(x a. - x,11315. -c-1
2
+ a, Eg, lig - v - :o).6o..... 1r-
Φ 1-11 + 7- - 404
2 Eg
1x,11 - x2 + ai F - -:Ll/x - S(-1 -
4
0002
T-1
17

---

Published as a conference paper at ICLR 2026
Now rearranging and summing from f 0 to T - 1, and using the law of total expectation, get:
T
7t-1 4a, ||x1- - -xal1?
O0 B
Er-
F(X(+1) +
4
T-1
T-1 1
a
<
B
CT.... -1-1
47 T-
+ L
ag E Co....rr CT-1 [| - -x,13 +
7
t=0
t=
B
KT=1
YT-
2
E Eo...rr-1
kr-1
[|x- - xT xxx-X11'
T-1
0 g
L
Er-1 |||x: - x
M--
1=0
T
F()() + YT-1 ||x- - -xol1
E 1
-1-1
E
[||x - 11
2
2
T-1 2
0
L
0 E Ca.... Cr || - -xo111
+
g
7--1
1=0
Rearranging, we get the desired result.
Er.
ae (F(((()+1) F(x)) Nt-1 -4pL 4a,L
|x xxll2
PT-1
E Es.....5r1 [[|x - Xx 11
4
2
T-1
T-1
0,00
<
YT
|x xoll
a
||/ - x+11?|
+
2
7-1
1=0
1=
For Equation
13
by definition of X,+1, we have:
+ 'tt - ||x++1 - xool2
(x+1) + ae (f(e)) + (B. X(+1 x1) + xx((++1))
2
(v))
2 $ 1-1 +
701
|x+1 - -x, + ar (x(x)) + (8. Xe+1 xx) + 1/((xx++ + - |x++1 xoll?
2
+ 7-1
|x -x,l' 2|2 + (f (xx) + (Vf(x)), x++1 xx) + (g: Vf((x),, xx+1 xxi) + xx(x++1)
+ 7/1 7t1
|x - 1 2
2
(vái)
- + M-1 I.
|x++1 x + as (F(x(++) + (g. Vf(xx), -xi)) ----
X1+1 xull?
2
where in (vi) we used the strong convexity of t and in (i we used Assumption 2.4 Again by the definition of X1+1, have:
Φ + 7t | - x.11 1 (x()
(usit)
2
+ + at Fx::)
+ "t ---1
2 xx, xol12.
where in (vilt) we used the strong convexity of Φ.+1.
Putting these together, we have:
Vt + 7t-1 1.L
|x++1 x2l12 a: + (8: V[(x)), XL+1 - xx)) 7t 7
x - xol1
2
2
Sa,F(xi) +
- 7-1 Xr1 xol1.
18

---

Published as a conference paper at ICLR 2026
Now divide both sides by at and sum from t 0 T 1, we have:
T
Y) 76-1 a,L
|x+11 x2 (g: V[((x),x(+1 -x,) s ((xx))
xi)
(Bep 110--1)
20,
1=0
1=0
E SAMPLING PROCEDURE FOR VIRTUAL ITERATES
Algorithm 3 Sampling Procedure for Virtual Iterates
1: g. gn =
2:
for 0, 11..... do
3:
A, -5-00 0g
4:
Sample Ti = with prob. dt and fi = 0 otherwise. Aria Obtain g: gg g(,,, Ex)
5:
6:
= Bi--1 agg:
7:
g= if otherwise g remains.
8:
Update X++1
9:
XT arg minx (g. + (x)AA + x xol
where 7 is the last é such that T 1.
10:
A,
10=0 ai
In this section we prove the missing results for the sampling procedure for the virtual iterates in Section 3.1 We first summarize the procedure for clarity as Algorithm
Now simple proposition regarding the sampling procedure. This is folklore knowledge and the proof is taken directly from (Gao et al., 2024b).
Proposition E.1. Given stream of points {x+] in Rd and positive scalars {hx) we can maintain, at each step k 2 1, the random variable Xi(k), where t(k) is random index from (1....,k) chosen with prohabilities Pr(t(k) = i) requires only (d) memory and computation.
h. H. = 1......hh where H3 = Σ h4. This
Proof. We maintain the variables X E Rdd and H3 which are both initialized to 0 step Then, at each step & > update Hy. +- Ha-1 + hy and also, with probability Au. He we update
N X (or, with probability 1 hs. costs (d). Note that, for any i < k. the event
H. keep the old Xs = x)-1). The memory and computation x; happens iff was updated step and then not updated at each step j = + 1,..., Hence, for any < í S k, we have
h;
4:
(1
hg
h
H
hy
Pr(X, = =x) H
II j=i+1
H,
H
H₃
H
j=i+1
F DESCRIPTION OF FULL ALGORITHM
In this section, we describe Algorithm 2 in more details for clarity. The algorithm combines Algorithms and 3 Algorithm together.
At each iteration, the server samples bernoulli random variable to decide whether to update the g' vector, the cumulative gradient sample for all clients. The clients then proceed to compute their local stochastic gradient g/. and add it to their local cumulative gradient g). If 72 1, the client updates its cumulative gradient sample g' to g). otherwise it remains unchanged. Then the client make the EControl update, where it updates the local error e and the local gradient estimate g). The client then sends the compressed local gradient difference A the server. Now the server collects the gradient differences A from all clients and updates the global gradient estimate g and makes dual averaging update the primal variable X
19

---

Published as a conference paper at ICLR 2026
Finally, the server collects the cumulative gradient samples g' from all clients via full communication and computes g. The final output is then computed using so that it becomes a random sample of the virtual iterates (which are not explicitly computed and stored).
G ANALYSIS OF THE EControl MECHANISM
Algorithm 4 EControl
1: Input: Xo. 7), 6 0, 80 Vx((xo, Ct)-
2: for 0, I.... do
3: clients:
4:
g = gi Xx,, { & is independent copy of e
[x,,
5:
0; gi Bi - nei A = C(
6: g - Bi-1 A
7:
e1+1 e
+ gi g
8:
send A; to the server
9:
server
10:
A Σ A
11:
g: 81-1 A
In this section we present the missing proofs for the analysis of Algorithm For ease of understanding. we also summarize thet EControl mechanism Algorithm
The EControl mechanism is a blend of two different techniques. The first is the classical EF mechanism, which keeps track of the (local) compression errors ef and feedbacks them to compressor. The second is the gradient difference compression technique, which compresses the difference between the current gradient and the previous estimates. As was discussed in Gao et al. (2024a), directly mixing the two methods might lead to suboptimal dependence on the compression quality 5 in the convergence rate. The key innovation of EControl is to introduce a scaling factor the error feedback term. Note that the historical estimates g; also carries some information the error, and the error feedback term should be scaled down to balance the two sources of information. The specific choice of 1), we explain below, carefully chosen optimize the dependence in the final convergence rate.
Again, remind the readers that for now restrict ourselves to the setting where a and 7t 7 Please refer to Appendix H for more details on the case where is changing (and non-decreasing).
We first present an upper bound each sums of ||e and || gill2, both in terms of the sum of ||g - 1.ll..
Lemma 4.1. Let 3/1-6(1
51- then:
T
81(1 - -)) v1 5)1 T-2
5)1
Σ
|0
|g/ - gil??
25
1=
(15)
T
36(1 - 5)(1 + v1 8)3
T-2
|gg.1 gil..
82
1=0
Proof. By the definition of e/ have:
e = g g + = gi_ + A gi +ej
=A; - + n)e
Therefore, by triangular inequality, we have:
|etzaa|| || S (1 7)) || + |
الل1 < (1 le -
where in the last inequality we used the definition of the compressor. Now by Lemma
we get:
T
|
|
20

---

Published as a conference paper at ICLR 2026
Next note the following:
1/41 gi+1 gi -1
gi gi n(g) gi + e + 81+1 gi
= (1 + (g) gi) :1 + gi+1 gt
= (1 + (6 - A + nei) not + gi+1 g: = (1 + () - A + r + g gi.
Similar as before, we now apply triangular inequality and definition of the compressor and get:
| |1 _ (1 + 7) v1 5 || + 1 + +1ggi+1
gill-
Let's write 3 = 1 (1 + 7) 1 8 Now we apply Lemma C.2 again and Young's inequality, and
note that 6/ 0, we get:
2
|
2
Σ
(17 e|lll
+ |lg g/ll.).
32
Now we plug in the upper bound on the sum of ||el|| (and note that ej 0):
T-1
2(1
6) T-3
T-2
Σ |1 <
|0
g/ll.
B²
82
Rearranging, we have:
T-2
Σ t=
1101112 <
gil2²
82 2(1 5)11
11
t=0
Therefore, have:
2(1 8)
T-2
|e/l1 < 3212 2(1 8)17*
Σ
B1+1
g/ll
Next, we note the following:
g: = A (g) 81 v)ee)) + n,t
A 6: + nee.
Therefore, by Young's inequality, we have:
Σ Iigi --gill = 8) Σ 10211 + 2n² Σ |
8(1 5)
T-2
$ - 2(1 8)m?
Σ
g1+1
gil..
For the choice of 1) and we choose 3 2 8n. Since B = 1 v1 5(1 17), we have:
28
B
3/1 - 8(1 + v1 1 5)
3(1 + /1 8)
Putting this back, we get the desired results.
Lemma 4.3. Given Assumptions
2.1 and 2.3 to 2.5
and let 3/1-0(++v1-0) .2 24 then
we have:
T-1
80E
Σ
Fo + 7To2
(16)
9y
t=
1=1
Therefore, by Lemma
4.1
we also have;
T
5760
4536To2
<
Fo +
(17)
8ty
84
21

---

Published as a conference paper at ICLR 2026
Proof. For simplicity, let's write r ||xe+1
x1 By Assumptions 2.1 and 2.5
we have:
T-1
Σ
Bi+ - 8/ll9] - 26
Σ
R [ + 4To2.
n
t=
Therefore,
Σ
Σ
[lg
g(1 v
36(1 8)(1 + vI 6)2
T-2
gt+1 - g/l
82
7 i=1
1=0
1=0
720 (1 - 5) + vI 8)
T-2
144T - 5) + VT-
Σ
E
[r]]
+
82
82
(=0
288 T-2
576T
E
2
82
82
1=0
By Theorem 3.3
we have:
T-2
T-2
27
Σ
2
Σ
(g: Vx(xx),x(+1 x1) F(xo) F(XT).
11
Therefore, have:
T-1
T-1
18 [r [F((())) - F
E
[lls: (xx
27
1=0
1=0
T-1
2To²
$ [((o)) F(XT)] +
[|| - gr|1
+
7m
1=0
288
T-2
578T0²
E F(xo) F(x+)]+ +
E
[
82y
82
1=0
Now assuming that y 2 24 and rearranging, we have:
40
1285T
Σ 0=
E [ri]
v 9r
E [[((x)) - F(x+)]+
52n2
Therefore,
80E2
2570
||
gi1 <
- -((x)))
+ 4T
9y
82g2
Theorem 4.4. Given Assumptions 2.3 to 2.5
and setting a; = 1, = 7 1=
3/1- and
taking one initial stochastic gradient step from xo to xh if * 0 and setting
24
To²
////////
2 max
8
nRg
R
2//88
then it takes at most
T 16
n + 561R2 Vlo
96 2
82
de
iterations of Algorithm to get E ((XT) F S Here, Ro ||x0 x
In particular, this means that with three rounds of uncompressed communication (one for the initial stochastic gradient step, one communicating 8-1 and one communicating g), and T rounds of
22

---

Published as a conference paper at ICLR 2026
compressed communications, Algorithm 2 reaches the desired accuracy. Assuming that the cost of sending compressed vectors is 1 and sending uncompressed vectors is m, costs at most
16R
561 R61R
96v2ER
+ +m,
ng
828%/
de
in communications for Algorithm
to get.
[[((X)) - S'.
SE
Proof. For simplicity of notation, let's write Fi = F(x)) Fxx)).
By Lemma
4.3
and Theorem
3.3
we have, when 7 2 24/21
R
L
o²
E
[it1
Σ
E
[|]]]
+
T
2T
nn
t=0
t=0
1=1
R
5760 T,
4536T.02
0²
Fo 7884T
+
2T
7284
y
Now we choose Y max
24v2t
111 //
2T nR
217 r,
have:
6R
T
176R
1/4 8/2 F
R²/²
Ryo
21R
L' 2/5
+
+
T
8T
28T
2nT
4/88
Therefore, after:
T 8R00 2n
99R 99R2VLo
Lo
340R
111 1/
R
8/2
65
iterations of Algorithm we have:
T
E SE.
T
Note that this already gives us the desirable convergence rate. We can further simplify the above rates and remove the dependence on Fo by taking one additional stochastic gradient step initially to
get xy. By Lemma C.3 we have E [F(x)) F*] S LR
Reg and Ry = E || - x+1 2
22
Therefore if we start our algorithm at xg. then we have:
Rg T
5760 R
4073 Roo
4536lo² σ²
E [
<
T t=0
388T
338
7284
7/n.
Note that for the third term, we have the following due Young's inequality and the assumption that 24
7
2 Roo
4073 R& 27384T
4073l 2738TT
4073 Ro
6160² 2283
+
S
38TT
2738+T
Therefore, we have:
T E
77976- n2
2
0²
B[F-1]] <
T
T
384T
284
mm
1=
Now we pick:
24
To²
1//33/
= max
8
nR?
R 84/3
23

---

Published as a conference paper at ICLR 2026
and we have:
1
24v2
Roo
EE
[PP]
T
8T
ni
T3/8
Therefore, we need only:
16
96 2013
T
+
ne²
82
6z
iterations.
H EControl WITH VARIABLE STEPSIZE
Consider Theorem 3.3 when the stepsize 7t. is changing, we have to upper bound the sum of Jall This extra weight has to handled directly in the analysis.
7/-1
Lemma H.1. Let 1j
301-0(1+V-- we have:
le
81
5) + v1 - 8)
||8
gill
7--1
28
78
t=1
1=
(22)
gill 1|
36(1
8) + vI 8)
T-2
Igg
gf
|1
7082
78
Proof. By the definition of e we have:
e == g g e Bi- +
Aj gi + ej A -
-6, + (1 e)e
Therefore, by triangular inequality, we have:
|ل || $ (1 7) || + || |ل & (1 - nل|lا + v1 - -1-8 5|
where in the last inequality we used the definition of the compressor. Now divide both sides by 7/2 and noting that 7 7e-1. we have:
|
jej
v 1 - 6
I (1 11)
9--1
Now by Lemma C.2
we get:
le 2
1 8
|00112
172
72-1
Next we note the following:
8%
g gi ne
gi
gi n(g gi + e + gi+1 gi
i
+ (gi gi) n g gi
= + m) (5) A + ne)) ne
g g:
= =11+ + ()) - A + 2 + g gi. Similar as before, we now apply triangular inequality and definition of the compressor and get:
| || < (1 + /)v ||::|| + @| + ||Bi. -gill-
Again, we divide both sides by 7/ and note that 7/2 2 7
18
|
1 fl
|g
gill
< (1 + n)T 8
72_1
221
7
24

---

Published as a conference paper at ICLR 2026
Let's write 3 = (1+ v 8. Now we apply Lemma C.2 note that 6j 0, we get:
again and Young's 's inequality, and
18:12
2
|
|
Bill
3
kh-1
Now we plug in the upper bound on the sum of ||e||| (and note that cj 0):
1
2(1
8)n
T-3 3
2
T
66+1
88
76
8
7
32
Rearranging, we have:
18:1
2
||8
8ill
T--1
32
2(1
8'17
1=
78
Therefore, we have:
Σ
T |eeil?
2(1 - 6)
T
gi++
g/ll
<
7-1
B2, 2(1 8)y12
7
t=1
1=0
Next, we note the following:
gi A (gi
8:-1 mo0) + no
A 8% n
Therefore, by Young's inequality, we have:
T-1
|g -
T-1
10
T-1 1
|
& 2(1
8)
Σ
+ 21j
2
7t
1=
7t-1
1=1
8(1 8)
g
gi
3- 2(1 8)n7
For the choice of 17 and B, choose 3 = 2 - 8n.. Since B = 1 VI- 5(1 17), we have:
28
n 3V1 8(1 + v)
8
3(1 + V 8)
Putting this back, we get the desired results.
Lemma H.2. Given Assumptions
2.1 and
2.3 to
2.5
and 17
3/1-6(1+v1-8) 7
5
1366
we have:
1
gill
32
73988
T-1
(23)
7
10
==1
1=
Therefore, by Lemma 4.1
also have:
E
[[
21 Fo
226 p2
T-1
o²
(24)
00
3
00
2
Proof. For simplicity, let's write r ||x41
x11 2 By Assumptions
2.1 and 2.5
we have:
|2
T
402
28a
Σ
22
t=0
25

---

Published as a conference paper at ICLR 2026
Therefore,
gi
36(1 - 5)(1 + V1 - 8)2 T-2
[|8
gill
7882
π X
78
t=0
1=
(1
+ v1 8)2
T-2 Σ
EE
[r]]
144(1-
v1
0)²
T-1
0²
7062
7/
7082
78
t=0
288
T-
E
17]
576
T-1 0²
Σ
1/88
7
70
7
Recall the following from the proof of Theorem
3.3 (with at = 1):
+ π- L 1/ + F(X++1) + (8: VV(xx), xx)) + - 72-1
||x++1 xol12
2
2
=F(x)) + 7t - - 1|x - x0o12
2
Upper bounding (ge Vf(xi), x x - xi), and dividing both sides by ye and summing from t = 0
to T - 1, we have:
T- 1
Σ
7t- 2L
T
Fxx:) - F(x+1)
+ 2
T
Σ 0m
g:
T-1 Σ (Bipe - Bipet1)s
47
0
0
where
B/ = 7
Note that since yt is non-decreasing, we also have:
2%
Fxx:) F(X(+1)
F(xo) -F(x')
F(x1)-F(s) - -F(x")
F(xi) F(x")
F(x2) - F(xx)
7/
70
70
71
1=0
F(XT-1) - F(x*)
F(XT) - F(x*)
7/-1
97-1
F(xo) -F(x*) F(x1) - F((*)
F(x1) - Fx(x)
F(x2) - -x(x*
70
9/.
72
F(XT 1) 11- F((*)
F(XT) - -F(x*)
7--11
Fxxo) F'(x*)
Taking expectation on both sides, and applying Assumption 2.1
we have:
7t
2L 47
Fo T-1
g:
T
Sa²
Σ
T-1 (ppp - 3,P(1)..
i=1
t=
1=0
Now we use the assumption that 8 is non increasing and eliminate the last term. Further, we plug in the upper bound for the sum of g+
g
1l? we get:
h 2L
Fo
1152
T-2
2312 20
E
4
70
00
78
70
t=0
1=0
1=0
Suppose that 7/ 2 4L, then we have:
T-1
Σ
8Fg
92166
T-2 Σ
E
[r?]
18496
T-1
+
+
70
2000
2
0002
1=
If 70 2 1366. then we have:
5
T- 1 Σ
16F
36992
27
282
70
1=0
26

---

Published as a conference paper at ICLR 2026
Finally, we have:
E |1g
g
F2
73988
0²
70
7002
71
Therefore, by Lemma H.I
n
B
2
22
T-1
12-1
3
1000
Theorem H.3. Given Assumptions 2.3 to 2.5
and we set az = =1, 11 ==
and we take
3/1-0(1+v11-)
one initial stochastic gradient step from xo to x if # 0 and set
1368
2to²
6466
2t
+
V
nR
+
R
then it takes at most
288
66921./*R3
552ER
T ne²
+
8228/2
8E
iterations of Algorithm to get [X(T)) Se.
In particular, this means that with three rounds of uncompressed communication (one for the initial stochastic gradient step, one communicating g-1 and one communicating g). and T rounds of compressed communications, Algorithm S reaches the desired accuracy. Assuming that the cost of sending compressed vectors is 1 and sending uncompressed vectors is m, costs at most
T 288 6692L'/R88
5526RD
+
+ 3m,
ng²
82g
òe
in communications for Algorithm to get:
[F((x) - S S.
Proof. By Lemma H.2 and Theorem 3.3 and setting 17 3-1-6(++v1-8) and assuming that
To 2 1368 and that & non-increasing (this can be easily verified once we give the precise definitions of 7t),, we have:
σ²
Σ E
TT R2
TT-1
R
T
2T
2T
Ph1
n''
t=0
1=0
1=0
2
T-1
220 La²
TT-1
R
+
2T
8418T
8422T
n T
We consider the following stepsize:
1368
32L V2L
2to²
/
7t- =
R
nR
+
R R//3///
First we note that 7 dendeecra.,nng.. Further, it can be verified that with such choice of %. we have 86 7 is non-increasing in t.
2n
Noting that ET- d-p 2 1 - 1)P, then we have:
69ER3 87
16L 16LV
384L 1/3
R 2/3
3v2Roo
E [F <
T
8R./1
2//77//3
Vnf
1=0
27

---

Published as a conference paper at ICLR 2026
Therefore, after most:
288 T ne² 82g%/2
80199LVAR30
2762R2
dz
0R
iterations, we have E (xT]) E.
This is already desirable convergence rate, but we can also eliminate the term dependent on Fo. using one initial stochastic gradient step. By Lemma C.3
we have E [F(x) F+] s L
+ Reg
v2
and Ry := E [1x6
x
S 2 Therefore if we start our algorithm at x-- then we have:
T
2 R
2 Roo Dth8T
T-1 1 26
T-1
T Σ E F S
TT-1 2T
R
8478T
8478T
1
1=
For the third term, due to Young's incquality, we have:
25 Roo
25 R2
250
2 Roo
Roo
24160²
8 TT
8
+
8
8 8
8
Therefore, we have:
T YT-1
T- 26
2 202
T
E
[e41l
RD +
Σ
Σ
T
2T
8
8 8'agT
1ht-1
1=0
Now we pick:
7/- = 1368
21o
6/
+
+
8
nR
R2 8/////3
and after at most:
288 2
6692T.
RBo
552ENG
T
nE²
8//8/2
8E
iterations, we get
E [[F(xT) 5
S
I ANALYSIS OF THE REAL ITERATES
In this section, present analysis of the real iterates generated by Algorithm T which can be immediately combined with our analysis in Section 4 and give the convergence guarantee for Algorithm purely in terms of the real iterates X,. We note that this analysis does not rely on the virtual iterates X, at all, and is therefore also applicable to the basic proximal algorithm without dual averaging. We believe that this analysis might be of independent interest.
We first note that the guarantees for the real iterates is weaker than that of Theorem 3.3
Theorem 1.1. Given Assumptions 3.1 2.3 and 2.4 then for any X E domn, we have:
Σ
E a (F(xx+)) - + 7-1 L0,L
X xe|1?
< TT xx |x-xo| 12
Σ
E
||
22
+2 Σ
T-1
aio
4
---
1=0
1=1
1=0
(25)
Proof. By the definition of d., we have for any x E dom(())
(x) N क + ||x - x1+1 12
28

---

Published as a conference paper at ICLR 2026
We also have:
(x(())
Σ on (f(xx) + (Be, X2) + xxx)) + -/2 1111= xxol
km0
Σ on (f(xk) (Vf(x)), x xx) + xxxx) + Σ an (Ex V.((x)), x xx) + - 1|x xol1
(0)
ag
F(x) +
Σ au (g) V.((ss), x xx) + Ttt k=0
x xol13
2
k=0
where in (i) we used the convexity of f. Taking expectations on both sides, we get:
E [x) S
an F(x) + 20 ||x xol1?
k=0
Now by the definition of X(+1;
(x(+1) + ue (f(x)) + (g: X++1 - x1) + (xx++)) + - ||xe+1 - -xoll
6--
2
(10
2 Φ 1-1
1h-
Xt+1 x1112 + (xx()) + (8: xx-1 - -x.) + (x(++)))
2
-
7-
|x(+1 - xx1l' 1| + (xxi + (Vf(x;), x
x++1 - xx) + (xx+1)) + ar ag vf(x)),, Xx+1 -x,)
2
(06)
17-1 +
7-11
arb
|x++1 - xx 2 + a, (x++1) + ag) fx(x)),((+1 - -x,),
2
where in (ii) we used the I-strong convexity of + and in (iii) we used Assumption 2.4
Now rearranging and summing from t = to T - 1, we get:
T
+ 7-1 - a
E
ae (x(+1)
| - Xx 13
2
1=0
T-1
<E
Σ 1=0
E (a: - vf(x)), x1+1 - -x²)
T-1
SE 11
1T E ||| -xrl1?
Σ 1=U
a.E Kg. Vf(x()) xe+1 xx)
T-1
T-1
$
af Fxx) + Σ
a.E
[(g: Vf(()),, x- -x,0 + -T-1 [||x- - -xoll"
T-1
TT- 1
|||x - xr|
Σ
Kg. - Vf(x)) x1+1 - -xi)l
2
1=0
Rearranging, we get:
T Σ
E oel (xx((()1))FF6 + 7-1 - aeL
|x xol13
2
t=0
s, (1|x- -xull -E |||x x3. 112) + Σ
a (g. Vf((x),, x x(t1)].
1=0
29

---

Published as a conference paper at ICLR 2026
Note that by the definition of Ct, we have:
B Vs(x)),, x- Xx+1)
ee+1 - - X Xt+1)
|e+11, Xx+1) - (er, xi) + Xer, x1)
r=
(er,x ver,x-Xx -XX +
ets X1+1 -x,)
|er11
TT-1
x
Xr
211ee11
リ- x 11?)
-1
2
h--
8
Taking expectation on both sides, and noting that the noise g: and xg, we have:
V fxx) is independent both
Σ
a. (gg -f((xf(()x x(+1)l
t=
|
TT-
xx 11
2||e,11 12
T-1
2--1
xx+1 |1
T-1
0,00
+
+
-1
2
-t-1
4
7t-1
1=0
Now we put these together and get:
E a (F(xx+)) F(x)) + N 20,L
|x++1 xel1?
'r-1 |
22
Σ
IE [|ee
+2
T-1
af
Remark 1,2. Comparing Theorem 3.3 we note that the key difference here that the error in
B[[le_11%] The L multiplica- % tive difference here is crucial and allows the stepsize "t to control the errors much more effectively. Therefore, Theorem would lead to weaker convergence guarantee.
Equation 25 is Σズ= [1 while in Equation (12) is -
With this, we can now directly combine Theorem I.] with Lemma 4.3 to obtain the following convergence guarantee for Algorithm in terms of the real iterates x,. For simplicity, we use the fixed stepsizes " 7.
Theorem I.3, Given Assumptions
2.3 to 2.5 and we set a = 1. = 3/1-6(1+V1-8) and we set:
21v2e
326 F
1350
7 max
8% 3/3
Ro
then it takes at most:
T 72900R50²
48V2ER2
64((R)) 2/3 F 1/3
(26)
84g2
de
81/38
iterations of Algorithm
to get ETT (F(xx+1) F*) S.
Proof. We plug Equation
17
into Equation
25 and assume that 2 24v2r and get:
1
T
RR
1152062
907402
(F(x+1) - F*) <
+
Fo +
T
2T
84.2T
Jbyy
t=0
Now set
24v2t
326
F
1/8
135o
max
8
84/3
R
82 Ro
30

---

Published as a conference paper at ICLR 2026
and we have:
24v2ER
32( Fo!
135
T (F(((+1) F*) -
5T
8%
5
Therefore, takes at most:
T 72900R302
48 2
64((RR)%/E) 1/s
g4
òE
84/8
iterations of Algorithm to get:
(F(x++1) F*) SE
T
Remark 1.4. We emphasize that here we only achieved an O 5
convergence rate in the deter- ministic term, which worse than the O 1 rate achieved in Theorem 4.4 in terms 8. Perhaps 8r more importantly, in the stochastic case (o > 0), we only achieve a O rate, which does not improve linearly as increases and is not delta-free, unlike the rate in Theorem and Theorem H.3 is unclear whether this limitation is a fundamental property of the algorithm or an artifact of the analysis. We leave it for future work to resolve this question.
Remark I.S. We also briefly note that the restart strategy and a more careful analysis of the number of steps and parameter settings in each stage. This way we can remove the O ((54/a) term, and instead get a O 0'5 term overall. We will however have to assume that dome is bounded, and do Oloo }) number of restarts which requires one full communication at each stage. For simplicity, we omit the details here.
in Theorem 1.3 can be slightly improved using the
31


Reviews:
[{"review_id": "xQodJ6yn38", "reviewer": "Reviewer_bcYo", "summary": "The paper studies Error Feedback (EF) methods for distributed composite optimization problems.\nExisting EF analyses focus only on smooth (non-composite) settings, since the usual virtual-iterate technique used for EF fails when a non-smooth regularizer is present.\nThe authors address this issue by replacing standard gradient descent with a dual-averaging approach, which restores the additive structure needed for EF analysis.\nBy combining this idea with the EControl mechanism (a state-of-the-art EF variant), they obtain the first convergence guarantees for EF in the composite setting and achieve state-of-the-art iteration complexity.", "questions": "Is it possible to extend EF21 to the composite setting instead of EF? Did you try?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written and clearly organized.\n\n2. The motivation is intuitive: the authors reformulate the EF method using dual averaging, which restores the additive structure (gradients plus accumulated compression error) and enables virtual-iterate analysis in the composite case.\n\n3. The theoretical results are strong, with convergence rates matching the best-known results for the non-composite (smooth) setting.", "weaknesses": "1. It would be better if the paper provided more intuition about the **EControl** mechanism, since it plays a central role in the proposed method.  \n2. There are several typos and minor presentation issues:  \n   - Double $\\coloneqq$ in Algorithm 1.  \n   - $A_T$ and $\\tau_t$ are not defined.  \n   - $R_0$ is also not defined; it would be good to cite the work whose rate the paper matches in the non-composite case.  \n   - Several displayed equations are missing commas or periods at the end.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uuH3KPjx9j", "reviewer": "Reviewer_fp7G", "summary": "This paper presents a novel convergence analysis for distributed algorithms that incorporate error feedback mechanisms, referred to as **EControl**, to address **composite optimization problems**. The analysis is based on the **dual averaging framework**, which enables bounding the difference between the virtual and true iterates generated by the algorithms. This bound is a crucial step in demonstrating the advantages of error feedback, such as improved solution accuracy in algorithms using communication compression. \n\nThe paper establishes the convergence guarantees for distributed proximal algorithms using **EControl** under standard assumptions, including **Lipschitz smoothness** of the objective function and **unbiased**, **variance-bounded** stochastic gradients. Moreover, the **iteration complexity** of these algorithms for composite (constrained) optimization problems matches that of their unconstrained counterparts.\n\nFinally, empirical results validate the effectiveness of distributed proximal algorithms with **EControl**, showing that they achieve **linear speed-up** with respect to the number of participating agents.", "questions": "1. I believe Theorem 4.4 indicates that the iteration complexity of **EControl with Dual Averaging (Algorithm 2)** for composite problems matches that of the **vanilla EControl** method for quasi-convex unconstrained problems, as presented in *Gao et al. (2024a)*. Could the authors please verify this point? If confirmed, emphasizing this result would further strengthen the paper’s contribution by highlighting the efficiency of the proposed convergence analysis techniques.\n\n2. $m$ is not defined on Pages 2 and 4. Could the authors clarify what $m$ represents?\n\n3. On Page 6, the definition of $A_t$ is unclear. I assume it is given by $A_t = \\sum_{\\tau \\leq t} a_\\tau$. Please confirm or clarify this notation.\n\n4. In Section 5, the authors mention that “we simulate the stochastic gradient by adding Gaussian noise to the gradients.” What is the **standard deviation** of the Gaussian noise used in these experiments? This information is missing from the main text.\n\n5. **Assumption 2.5 vs. Assumption 3.1:**  The weaker condition in Assumption 2.5,  i.e. $\\mathbb{E}\\|\\| g_i(x;\\xi^i) - g_i(y;\\xi^i) \\|\\|^2 \\leq \\ell^2 \\|\\| x - y \\|\\|^2$,  seems potentially redundant with Assumption 3.1. Is it possible to remove Assumption 3.1 from the analysis, or are both required for specific parts of the proof?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper addresses an important gap in the study of **error-feedback algorithms** for distributed optimization by proposing novel analytical tools for handling **composite optimization problems** that involve the **proximal operator** under **communication constraints**. The authors effectively leverage the **dual averaging framework** to establish novel convergence analysis. In particular, Section 3 demonstrates how bounding the difference between the virtual and true iterates—a key aspect of analyzing error-feedback algorithms for unconstrained problems—can be extended to the composite setting.\n\nThe theoretical analysis is built upon standard and well-justified assumptions commonly used in gradient-based algorithms with communication compression, including:\n\n1. **Convexity and Lipschitz smoothness** of the objective function  \n2. **$\\alpha$-contractive** compression operators  \n3. **Unbiased** and **variance-bounded** stochastic gradients  \n\nExtensive literature on error feedback and communication compression, which is closely related to this paper, has been included in **Appendix A**. \n\nThe empirical evaluation is comprehensive. The proposed methods are tested on both synthetic data (softmax with $\\ell_1$-regularization) and real data (logistic regression with $\\ell_1$-regularization on FashionMNIST). Key findings include:\n- The proposed algorithms support a significantly **larger step size** compared to baseline methods, which likely contributes to its superior convergence behavior.  \n- The proposed algorithms exhibit **linear speed-up** with respect to the number of clients, confirming their scalability and efficiency in distributed settings.", "weaknesses": "Algorithm 2 requires access to $\\bar{g}$ in Line 16 to execute, which is **impractical**, even though full gradient communication occasionally occurs in Line 4. The key concern is that existing error-feedback methods for unconstrained problems—such as **EControl** and **EF21**—do **not** depend on periodic full gradient communication, making Algorithm 2 comparatively less communication-efficient.\n\nMoreover, the empirical results in this paper simulate stochastic gradients by adding Gaussian noise to the true gradients. A more realistic setup would be to construct the problems such that stochastic gradients are obtained through **minibatching** over the local training samples available to each client, rather than by artificially injecting noise. This modification would allow for evaluating the impact of minibatched training samples on the convergence behavior of the proposed algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1Y3AIWDRLT", "reviewer": "Reviewer_hvZz", "summary": "This paper studies distributed **composite** optimization, $\\min_x f(x)+\\psi(x)$ with smooth $f$ and (possibly) non-smooth/prox-friendly $\\psi$, under **compression with error feedback (EF)**. The authors combine **Dual Averaging (DA)** with **EControl** and analyze “virtual iterates,” claiming *“for the first time a strong convergence analysis for composite optimization with error feedback”* (Abstract; Sec. 1). They give an inexact-DA analysis template and experiments on synthetic $\\ell_1$-regularized softmax and FashionMNIST with Top-$k$ compression, comparing against proximal EF and proximal EF21.", "questions": "1. Please **restate** the novelty claim precisely: relative to EC-RDA (dual averaging) and EC-ProxSGD (OPT’20), what is mathematically new in your DA+EControl analysis (assumptions, iterates, rate form)? How does “strong convergence” differ from prior composite-EF rates? Could the authors please clarify their novelty claim in light of these specific prior works? Why were these methods not cited or compared against?\n2. Can you add **EC-ProxSGD/EC-RDA, EF-BV, and EC-LSVRG/Quartz/SDCA** as baselines—or explain incompatibilities?  \n3. Is there a **theoretical link** from virtual to **real** iterates beyond empirical similarity (Fig. 1b)? Can you deliver a bound for the real iterate under your stepsize choices? \n4.  The analysis of real iterates in Appendix I is much weaker than the analysis of virtual iterates, yet experiments suggest their performance is nearly identical. What is the fundamental analytical barrier preventing a tighter analysis for the real iterates? Is there a specific step in the proof (e.g., handling the proximal operator directly) where the analysis loses tightness?\n5.  Given that Qian et al. (2020) already analyzed an error-compensated RDA, could you elaborate on the specific contributions of your inexact dual averaging analysis template (Section 3)? Does it address limitations in the analysis of Qian et al. or offer a different perspective that enables the stronger (virtual iterate) result?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* **Clarity of Presentation:** The paper is well-written, logically structured, and easy to follow. The theoretical development is presented step-by-step, making the complex analysis accessible. The distinction between the real and virtual iterates, a key and often confusing point in EF literature, is handled with consistent clarity.\n- **Conceptual:** Clear identification that naïve EF analyses break in the composite case; DA is a natural vehicle to handle the prox term. (Sec. 3–4 table of contents suggests an organized build-up.) \n- **Analysis template:** An inexact-DA framework and a sampling scheme for virtual iterates (Secs. 3, 3.1) that could be reusable beyond EControl. \n- **Mechanistic clarity:** A separate technical section on EControl’s properties (App. G, H), and a discussion of real vs virtual iterates (App. I). \n- **Experiments** provide both synthetic composite and a FashionMNIST $\\ell_1$-regularized logistic example with Top-$k$ compression (δ=0.1), and include a *real vs virtual iterate* comparison. (Sec. 5; Fig. 1–2).", "weaknesses": "- **Overstated novelty (major):** The paper claims the first “strong convergence analysis for composite optimization with EF.” However, **composite EF** existed well before:\n  - EC-ProxSGD and **EC-RDA (dual averaging)** handle composite finite-sum with error compensation. (OPT 2020).   \n  - **EC-LSVRG/Quartz/SDCA** support composite settings with linear/convex guarantees (arXiv 2021).   \n  - **EF-BV** (NeurIPS 2022) treats composite objectives with an explicit proximal step within a unified EF/variance-reduction theory.   \n  - **Eco-FedSplit** (ICASSP 2022) integrates error-compensated compression with proximal FL splitting.   \n  - **EF21-Prox** makes EF21 applicable to composite problems and states convergence (JMLR/ArXiv 2021).\n  The manuscript must **qualify** its “first” claim (e.g., *first DA+EControl-based virtual-iterate rate under assumptions X, Y*), and clearly delineate what “strong” means vs prior composite-EF rates.\n\n[1] Qian, Xun, et al. \"Error compensated proximal SGD and RDA.\" _Proc. 12th Annu. Workshop Optim. Mach. Learn._. 2020.\n\n[2] Qian, Xun, et al. \"Error compensated loopless SVRG for distributed optimization.\" _Workshop on Optimization for Machine Learning_. 2020.\n\n[3] Qian, Xun, et al. \"Error compensated loopless svrg, quartz, and sdca for distributed optimization.\" _arXiv preprint arXiv:2109.10049_ (2021).\n\n[4] Condat, Laurent, Kai Yi, and Peter Richtárik. \"EF-BV: A unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization.\" _Advances in Neural Information Processing Systems_ 35 (2022): 17501-17514.\n\n[5] Khirirat, Sarit, Sindri Magnússon, and Mikael Johansson. \"Eco-fedsplit: Federated learning with error-compensated compression.\" _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022.\n\n[6] Fatkhullin, Ilyas, et al. \"EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback.\" _arXiv preprint arXiv:2110.03294_ (2021).\n\n\n- **Related-work coverage (major):** Sec. A emphasizes uncomposite EF and Safe-EF, but does **not** cite EC-ProxSGD/EC-RDA (OPT’20), EC-LSVRG/Quartz/SDCA (’21), EF-BV (NeurIPS’22), Eco-FedSplit (ICASSP’22). Add these and discuss differences in assumptions (e.g., convexity, finite-sum vs online), or the novelty claim is misleading.\n- **Baselines (major):** Experiments compare to “proximal EF” and “proximal EF21,” but **omit** EC-ProxSGD/EC-RDA, EF-BV, and EC-LSVRG/Quartz/SDCA—precisely the most relevant **composite+EF** competitors. Include these, or justify why not.\n- **Virtual vs real iterate gap:** Theory primarily addresses a sample of **virtual** iterates; experiments show similarity to **real** iterates on one setup. Provide bounds bridging real iterates (App. I) to the main claims, or broaden empirical validation.\n- **Scope/assumptions clarity:** Precisely state smoothness/convexity/stochastic-noise assumptions used to obtain the claimed “strong” rate, and contrast to prior composite-EF (e.g., whether rates are stationarity vs suboptimality, and dependence on $\\delta$, $n$, variance). The Abstract currently suggests generality that theorems may not cover. \n* **Gap Between Virtual and Real Iterate Guarantees:** The strong theoretical results, including linear speedup, are proven only for the *virtual iterates*. The analysis for the *real iterates* in Appendix I is substantially weaker, yielding a rate of $\\mathcal{O}(1/(\\delta^4 \\epsilon^2))$ that lacks linear speedup and has a much worse dependency on the compression parameter $\\delta$. The experiments show that real and virtual iterates perform similarly, which suggests the analysis for the real iterates is not tight. The proposed sampling procedure to recover the virtual iterate guarantee is impractical as it requires storing uncompressed cumulative gradients and an extra round of uncompressed communication, undermining the method's efficiency goals.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yeGByGMIwG", "reviewer": "Reviewer_nFER", "summary": "The work deals with reducing the communication in distributed optimization cost via compression, in the setting where there is an additional regularization term whose proximity operator is applied by the server.", "questions": "1) The $f_i$ can be non-convex? It seems that yes, but it is important to state it clearly.\n\n2) What is the real challenge in dealing with $\\Psi$? In algorithms such as EF21 or DIANA, dealing with $\\Psi$ is almost trivial, using nonexpansiveness of the prox. (Exploiting strong convexity of Psi to get linear convergence is less straightforward). This should be clearly explained as this is the main contribution of the work.\n\n3) Can you prove linear convergence if $f$ or $\\Psi$ is strongly convex?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Reducing the communication cost of distributed optimization is an important topic. Combining compression and stochastic gradients is not fully understood and this work is a step forward in this direction.", "weaknesses": "** I have the following concerns\n\n1)  \"In the convex regime, it is believed that the convergence of proximal EF21 critically relies on the bounded domain assumption, which we do not assume in our work\" This is not correct. There is no such restriction for EF21. The Islamov et al. paper is for non-smooth functions, which is a different setting.\n\n2) \"EF21, which is more closely related to gradient-difference compression methods\". I don't know why you claim that EF21 might not be really an EF method. The control variates are defined recursively, so they accumulates past compression errors. \n\n3) A refined analysis of EF21 in the composite case is in Condat et al. “EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization,” Neurips 2022\n\n4) It seems that the focus of the work is about dealing with stochastic gradient errors and linear speedup with respect to such errors (linear speedup with respect to compression errors with independent unbiased compressors is equally important but is not addressed).\n\n5) Explain why convexity is critical to the analysis. Convexity is a restrictive assumption. This is fine to me, but on the other hand in convex settings, Nesterov acceleration becomes available. So, there is an important gap between your guarantees and the convergence speed that can be obtained if $\\sigma\\rightarrow 0$ and $\\delta\\rightarrow 1$.\n\n** Typos and minor comments\n\n* Beznosikov et al: the reference is given twice.\n\n* Fatkhullin et al. 2021: published in Journal of Machine Learning Research, 26, 2025\n\n* Algorithm 1 line 4: :=:=\n\n* unlesss\n\n* There should be a period at the end of equations, e.g. 15, 16, 17", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "itL1erNhio", "reviewer": "Reviewer_Hh9y", "summary": "This paper addresses the failure of standard EF methods in composite optimization, where the objective includes a non-smooth component. The authors argue that the proximal step used in this setting disrupts the additive structure essential for traditional EF analysis. To resolve this, they propose a novel algorithm that combines Dual Averaging with a modern EF variant (EControl). This approach successfully restores the necessary structure, enabling the first strong convergence guarantees for composite optimization with communication compression.", "questions": "N/A", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Fills a gap in optimization theory by providing the theoretically-backed EF method for the general composite setting.\n\n- The use of Dual Averaging is a conceptually clean and logical solution that directly targets the structural issue at the core of the problem.", "weaknesses": "- The claims of the paper are not backed by strong experimental evidence. The experiments mentioned are not detailed enough to validate the practical advantages of the proposed method over existing techniques.\n\n- While the authors suggest their analysis provides a versatile template for other domains (e.g., safe reinforcement learning), the paper does not demonstrate these applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)