LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression
Authors: Laurent Condat
Arto Maranjyan
Peter Richtárik
Venue: ICLR 2025 Spotlight (2025)
Keywords: distributed optimization
local training
compression
communication-efficient algorithm
federated learning
Primary area: optimization

Abstract: In $D$istributed optimization and $L$earning, and even more in the modern framework of federated learning, communication, which is slow and costly, is critical. We introduce LoCoDL, a communication-efficient algorithm that leverages the two popular and effective techniques of $Lo$cal training, which reduces the communication frequency, and $Co$mpression, in which short bitstreams are sent instead of full-dimensional vectors of floats. LoCoDL works with a large class of unbiased compressors that includes widely-used sparsification and quantization methods. LoCoDL provably benefits from local training and compression and enjoys a doubly-accelerated communication complexity, with respect to the condition number of the functions and the model dimension, in the general heterogeneous regime with strongly convex functions. This is confirmed in practice, with LoCoDL outperforming existing algorithms.

Published as a conference paper at ICLR 2025
LoCoDL: COMMUNICATION-EFRIEES DISTRIBUTED LEARNING WITH LOCAL TRAINING AND COMPRESSION
Laurent Condat, Artavazd Maranjyan & Peter Richtárik
Computer Science Program, CEMSE Division
King Abdullah University of Science and Technology (KAUST) Thuwal, 23955-6900, Kingdom of Saudi Arabia & SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence
(SDAIA-KAUS) AI)
first. last lalasskkkuutee.mm edu. sa
ABSTRACT
In Distributed optimization and Learning, and even more in the modern framework of federated learning, communication, which is slow and costly, is critical. We introduce LoCoDL, a communication-eficienn algorithm that leverages the two popular and effective techniques of Local training, which reduces the communi- cation frequency, and Compression, in which short bitstreams are sent instead of full- dilenssinnii vectors of floats. LoCoDL works with large class of unbiased compressors that includes widely-used sparsification and quantization methods. LoCoDL provably benefits from local training and compression and enjoys a doubly- accelerated communication complexity, with respect to the condition number of the functions and the model dimension, the general heterogenous regime with strongly convex functions. This is confirmed in practice, with LoCoDL outperform- ing existing algorithms.
INTRODUCTION
Performing distributed computations is now pervasive in all areas of science. Notably, Federated Learning (FI.) consists in training machine learning models in distributed and collaborative way (Konečný et al. 2016a b. McMahan et al. 2017; Bonawitz et al., 2017). The key idea in this rapidly growing field is exploit the wealth of information stored on distant devices, such mobile phones or hospital workstations. The many challenges to face in FL include data privacy and robustmess to adversarial attacks, but communication-efftteee
is likely be the most critical (Kairouz et al.) 2021] Li et al., 2020al Wang et al.) 2021). Indeed, in contrast to the centralized setting in a datacenter, FL. the clients perform parallel computations but also communicate back and forth with distant orchestrating server. Communication typically takes place over the internet or cell phone network, and can be slow, costly, and unreliable. It is the main bottleneck that currently prevents large-scale deployment of FL in mass-market applications.
Two strategies reduce the communication burden have been popularized by the pressing needs of FL: 1) Local Training (LT),, which consists in reducing the communication frequency. That is, instead of communicating the output of every computation step involving (stochastic) gradient call, several such steps are performed between successive communication rounds. 2) Communication Compression (CC), which compressed information sent instead of full-dimensional vectors. We review the literature of LT and CC in Section 1.2
We propose a new randomized algorithm named LoCoDL, which features LT and unbiased CC for communication-efficieett FL and distributed optimization. It is variance-reduced (Hanzely & Richtárik 2019; Gorbunov et al. 2020a Gower et al. 2020), so that converges to an exact solution. It provably benefits from the two mechanisms of LT and CC: the communication complexity is doubly accelerated, with a better dependency on the condition number of the functions and on the dimension of the model.

---

Published as a conference paper at ICLR 2025
1.1 PROBLEM AND MOTIVATION
We study distributed optimization problems of the form
min Σ f((z) gax).
where d 2 1 is the model dimension and the functions ft R - R and g F R are smooth. We consider the server-client model in which n 2 clients do computations in parallel and communicate back and forth with server. The private function f; is owned by and stored on client i E [x]] = (1... (1.................... n.. Problem ① models empirical risk minimization, of utmost importance in
& Ben- Ben-David 2014). More generally, minimizing a sum of functions appears in virtually all areas of science and engineering. Our goal is to solve Problem (T) in communication-efficennn way, in the general heterogeneous setting in which the functions ft. as well as g. can be arbitrarily different: we do not make any assumption on their similarity whatsoever.
machine learning (Sra al.) 2011
We consider in this work the strongly convex setting, That is, the following holds:
Assumption 1.1 (strongly convex functions). The functions fa and are all T-smooth and j-strongly convex, for some 0 < μ S L Then we denote by 2* the solution of the strongly convex problem (T). which exists and is unique. We define the condition number K == &
Problem 1 can be viewed as the minimization of the average of the functions (Ji + g). which can be performed using calls to F(:+t)
Vs++ + Vg. We do not use this straightforward interpretation.
Instead, let illustrate the interest of having the additional function in @1 using 4 different
viewpoints. We stress that we can handle the case g = 0, as discussed in Section 3.1
Viewpoint I: regularization. The function g can be regularizer. For instance, if the functions fi are convex, adding g = ~1l 1|2 for a small μ > 0 makes the problem y-strongly convex.
Viewpoint 2: shared dataset. The function y can model the cost of a common dataset, or a piece thereof, that is known to all clients.
server-aided training. The function g can model the cost of core dataset, known only to the server, which makes calls to Vg. This setting has been investigated in several works, with the idea that using small auxiliary dataset representative of the global data distribution, the server can correct for the deviation induced by partial participation (Zhao et al.) 2018 Yang et al.] 2021 2024). We do not focus on this setting, because deal with the general heterogeneous setting in which y and the Si are not meant to be similar in any sense, and in our work y is handled by the clients, not by the server.
Viewpoint 3:
Viewpoint 4: a new mathematical and algorithmic principle. This is the idea that led to the construction of LoCoDL, and we detail it in Section
In LoCoDL, the clients make all gradient calls; that is, Client makes calls to Vf and Vg.
1.2 STATE OF THE ART
We review the latest developments on communication-effiiiee algorithms for distributed learning, making use of LT, CC, or both. Before that, we note that we should distinguish uplink, or clients-to- server, from downlink, or server-to-clients, communication. Uplink is usually slower than downlink communication, since the clients uploading different messages in parallel to the server is slower than the clients downloading the same message in parallel from the server. This can be due to cache memory and aggregation speed constraints of the server, well asymmetry of the service provider's systems or protocols used on the internet or cell phone network. In this work, we focus on the uplink communication complexity, which is often the bottleneck in practice. Indeed, the goal is to exploit parallelism to obtain better performance when n increases. Precisely, with LoCoDL, the uplink communication complexity decreases from O (d / log when is small to
A differentiable function f _ + IR is said to be L-soooth if V is L-Lipschitz continuous; that is. for every E Rd and y E Rd, f[) v.(y))l < T.Il yl (the norm is the Fuclidean norm throughout the paper). is said to be j-strongly convex if | convex.
2

---

Published as a conference paper at ICLR 2025
logge when is large, where the condition number is defined in Assumption 1.1
Corollary Many works have considered bidirectional compression, which consists in compressing the messages sent both ways (Gorbunov et al., 2020b] Philippenko & Dieuleveut] 2020; Liu et al. 2020; Philippeeko & Dieuleveut] 2021] Condat & Richtárik] 2022] Gruntkowska et al., 2023 Tyurin & Richtárik] 2023b) but to the best of our knowledge, this has no impact on the downlink complexity, which cannot be reduced further than O (dy log E ) just just because there is no parallelism to exploit in this direction. Thus, we focus our analysis on theoretical and algorithmic techniques to reduce the uplink communication complexity, which we call communication complexity in short, and we ignore downlink communication.
Communication Compression (CC) consists in applying some lossy scheme that compresses vectors into messages of small bit size, which are communicated. For instance, the well-known rand-k compressor selects & coordinates of the vector uniformly at random, for some k E [d] == (1, ......... d). I can be as small as 1, in which case the compression factor is d, which can be huge. Some compressors, such as r rand-k, are unbiased, whereas others are biased; we refer to Beznosikov et al.) (2020): : Albasyoni et al. (2020); Horváth et al. (2022): Condat et al. (2022b) for several examples and discussion of their properties. The introduction of DIANA by Mishchenko et al., (2019)
major milestone, as this algorithm converges linearly with the large class of unbiased compressors defined in Section 1.3 and also considered in LoCoDL. The communication complexity O(xx Oggslooge log of (
the basic Gradient Descent (GD) algorithm is reduced with DIANA to O (N + d) log c c-1) when n is large, see Table 2 DIANA was later extended in several ways (Horváth et al., [022] Gorbunov jet al., 2020aa Condat & Richtárik 2022). An accelerated version of DIANA called ADIANA based on Nesterov Accelerated GD has been proposed (Li et al. 2020b) and further analyzed in He et al. (2023); has the state-of-the-arr theoretical complexity.
Algorithms converging linearly with biased compressors have also been proposed, such as EF21 (Richtárik et al., 2021; Fatkhullin et al. 2021 Condat et al. 2022b). but the acceleration potential is less understood than with unbiased compressors. Algorithms with CC such as MARINA (Gorbunov) ct al. 2021) and DASHA (Tyurin & Richtárik 2023a) have been proposed for nonconvex optimization, but their analysis requires different approach and there is a gap in the achievable performance: their complexity depends on wa instead of w. with DIANA, where w characterizes the compression error vn variance, see 2). Therefore, we focus on the convex setting and leave the nonconvex study for future work.
Local Training (LT) is a simple but remarkably efficient idea: the clients perform multiple Gradient Descent (GD) steps, instead of only one, between successive communication rounds. The intuition behind is that this leads to the communication of richer information, so that the number of com- munication rounds to reach a given accuracy is reduced. We refer to Mishchenko et al.] (2022) for comprehensive review of LT-based algorithms, which include the popular FedAvg and Scaffold algorithms of McMaaan et al. (2017) and Karimireddy et al. (2020), respectively. |Mishchenko et al. (2022) made breakthrough by proposing Scaffnew, the first bT-ba variance-reduced algorithm that not only converges linearly to the exact solution in the strongly convex setting, but does so with accelerated communication complexity Old v log -1). In Scaffnew, communication can occur randomly after every iteration, but occurs only with a small probability p. Thus, there are in average p local steps between successive communication rounds. The optimal dependency on //c (Scaman et al. 2019) is obtained with p 1/VK. LoCoDL has the same probabilistic I.T' mechanism as Scaffnew but does not revert to when compression is disabled, because of the additional function g and tracking variables y and v. A different approach to LT was developed by (Sadiev et al.] (2022a) with the APDA-Inexact algorithm, and generalized to handle partial participation by Grudzien et al. (2023) with the 5GCS algorithm: in both algorithms, the local GD steps form an inner loop in order to compute a proximity operator inexactly.
Combining LT and CC while retaining their benefits is very challenging, In our strongly convex and heterogeneous setting, the methods Osparse-local SGD (Basu et al. 2020) and FedPAQ (Reisizadeh et al., 2020) do not converge linearly. FedCOMGATE features LT + CC and converges linearly (Haddadpour et al. 2021). but its complexity O (dx log e does not show any acceleration. We can mention that random reshuffling, a technique that can be seen as a type of LT, has been combined with CC in Sadiev et al. 2022b); Malinovsky & Richtárik| (2022). Recently, Condat et al. (2022a) managed to design a specific compression technique compatible with the LT mechanism of Scaffnew, leading to CompressedScaffnew. the first LT + CC algorithm exhibiting a accle-acceelerated complexity,
3

---

Published as a conference paper at ICLR 2025
namely ((VaV=++ AVR +d) 1og reported in Table However, CompressedScaffnew uses yn specifie linear compression scheme that requires shared randomness; that is, all clients have agree on random permutation of the columns of the global compression pattern. No other compressor can
be used, which notably rules out any type of quantization.
1.3 GENERAL CLASS OF UNBIASED RANDOM COMPRESSORS
For every 2 0, we define U(w) the of random compression operators C: Rd - Rd that unbiased, i.c. [x] 2, and satisfy, for every I E R
E [lI((=) =12 I w ||~11
In addition, given collection (c,) of compression operators in U(w) for some 2 0, in order to characterize their joint variance, we introduce the constant Way 2 0 such that, for every E R i [n]. we have
E
(c,())) m:))
Wav
72
The inequality 33 is not an additional assumption: it is satisfied with wav = w by convexity of the squared norm. But the convergence rate will depend Wav, which is typically much smaller than w. In particular, if the compressors Cj are mutually independent, the variance of their sum is the sum of their variances, and (3) is satisfied with Way
1.4 CHALLENGE AND CONTRIBUTIONS
This work addresses the following question: Can we combine LT and CC with any compressors in the generic class U(w) defined the previous section, and fully benefit from both techniques by obtaining Noubly-acceleree
communication complexity?
We answer this question in the affirmative. LoCoDL has the same probabilistic LT mechanism as Scaffnew and features CC with compressors in U(w) with arbitrarily large 2 0, with proved linear convergence under Assumption T.I. without further requirements. By choosing the communication probability and the variance appropriately, double acceleration is obtained. Thus, LoCoDL achieves the same theoretical complexity as CompressedScaffnew but allows for large class of compressors instead of the cumbersome permutation-bant -assd compressor of the latter. In particular, with compressors performing sparsification and quantization, LoCoDL outperforms existing algorithms, as we show by experiments Section 4 This is remarkable, since ADIANA, based on Nesterov acceleration and not LT. has an even better theoretical complexity when is larger than d, see Table but this is not reflected in practice: ADIANA clearly behind LoCoDL our experiments. Thus, our experiments indicate that LoCoDL sets new standards in terms of communication efficiency.
2 PROPOSED ALGORITHM LoCoDL
2.1 PRINCIPLE: DOUBLE LIFTING OF THE PROBLEM TO A CONSENSUS PROBLEM
In LoCoDL, every client stores and updates two local model estimates. They will all converge to the same solution x² of (T) This construction comes from two ideas.
Local steps with local models. algorithms making use of LT. such as FedAvg, Scaffold and Scaffnew, the clients store and update local model estimates r;, When communication occurs, an estimate their average formed by the server and broadcast to all clients. They all resume their computations with this new model estimate.
Compressing the difference between two estimates. To implement CC, a powerful idea to compress not the vectors themselves, but difference vectors that converge to zero. This way, the algorithm is variance-reducedd that is, the compression enror vanishes at convergence. The technique of compressing the difference between gradient vector and control variate is at the core of algorithms such as DIANA and EF21. Here, we want to compress differences between model estimates, not gradient estimates. That is, want Client i to compress the difference between z; and
4

---

Published as a conference paper at ICLR 2025
Table I: Communication complexity in number of communication rounds reach e-accuracy for linearly-converiing algorithms allowing for CC with independent compressors in U(w) for any w 2 0.
Since the compressors are independent, Way z. We provide the leading asymptotic factor and ignore log factors such as log c-!_ The state of the art highlighted in green.
Algorithm
Com. complexity in rounds
case (()
case w (n)
DIANA
+ ) +w w
K K+4
R.
EF21
(1 + W/
(1 + w)R
(1 + W)
5GCS-CC
1+ WH
W
VK kK
[1
w
K w
(1+v V +
Vn
ADIANA
1
11/4 +
3/1
Vk
1 1/4
VR +
(1+ VR
v
ADIANA
+ vn
VK + w
1 +
VK+
(1+vW)VR +
lower bound?
Vk +
1 Vn
VK+w
(1+/W)Vk+u
vn
LoCoDL
1 + 1+
VK (1+
(1+v/)
/ +
(1+)
This is the complexity derived in the original paper Li et (2020b).
This is the complexity derived by a refined analysis in the preprint He et al. (2023), where a matching lower bound is also derived.
Table 2: (Uplink) communication complexity number of reals to reach e-accuracy for linearly- converging algorithms allowing for CC, with an optimal choice of unbiased compressors. We provide the leading asymptotic factor and ignore log factors such as loge The state the art is highlighted in green.
Algorithm DIANA
complexity in reals case n- (dd)
(1 + d ))N +
d
b d dk
EF21
dR
5GCS-CC
Vd+ Va
VK + d
V Vk - d VTe +
ADIANA
1
VK + d
d
vT
CompressedScaffnew FedCOMGATE
Vd++ Vn
VK+ 1 d
Vn V - d
dk
dk
LoCoDL
(vd+
V +
d
V KK-d d
another model estimate that converges to the solution x² as well. We see the need of an additional model estimate that plays the role of an anchor for compression. This is the variable y common to all clients in LoCoDL, which compress x, and send these compressed differences to the server.
Combining the two ideas. Accordingly, equivalent reformulation of T is the consensus problem with n variables
min
Maxx)) + g(y) s.t. x1 Fn y- Σ 2=1
The primal-dual optimality conditions are T1
2r v. = Vf(())) u, Vi [n].
0 = Vgly) v, and 0 = + un + nw (dual feasibility), for some dual variables ,I,..., Uny introduced in LoCoDL, that always satisfy the dual feasibility condition.
2.2 DESCRIPTION OF LoCoDL
At every iteration, for every i [n]] in parallel, Client first constructs a prediction & of its updated local model estimate, using GD step with respect fs corrected by the dual variable uf. It also constructs prediction ÿ' of the updated model estimate, using a GD step with respect to g corrected by the dual variable v'. Since g is known by all clients, they all maintain and update identical copies of the variables y and
LoCoDL is randomized primal-dual algorithm, shown Algorithm |
5

---

Published as a conference paper at ICLR 2025
Algorithm LoCoDL
1: input: stepsizes 7 > 0, X > 0.p > 0: probability p E (0, 1]; variance factor w. O; local initial estimates 21 and v E IR_ such that : 2im1 uf + v 0.
In E Rd initial estimate v" E Rd, initial control variates w/. .... uf, E R
2: for = 0, 0. do
3: for = ...... n, at clients in parallel, do
4:
at = r (z + y
5:
y = y
Vgly") + 70" the clients store and update identical copies of y', v.,
6:
flip coin 0 E (0, 1) with Prob(0' = =
7:
ir = then
8:
di = ( D²)
9:
send di to the server
10:
at server: aggregate d' = Ej=1 dž and broadcast d' all clients
2n
11:
++1 = (1 p)at + plj'' +
12:
u, = u¹ + x1122
Px
(d d))
g = ij ppll
14:
vt+ = vt + 7[1+2w] d'
15: else
16:
xi ++1 = s/. ye+1 = 5/¹ u/ 1+1
== w/. r0 = v
end if
18:
end for
end for
If there is no communication, which is the case with probability 1 1 p. 2, and y are updated with these predicted estimates, and the dual variables u, and v are unchanged. If communication occurs, which is the case with probability p. the clients compress the differences of ÿ and send these compressed vectors to the server, which forms d' equal to one half of their average. Then the variables x; are updated using convex combination the local predicted estimates at and the global but noisy estimate j' + d'. is updated similarly. Finally, the dual variables are updated using the compressed differences minus their weighted average, that the dual feasibility condition remains satisfied. The model estimates z/. 2 y", jí all converge to x", so that their differences, as well as the compressed differences as a consequence of (2), converge zero. This is the key property that makes the algorithm variance-reduced We consider the following assumption.
Assumption 2.1 (class of compressors). In LoCoDL the compressors C are all in U(w) for some > O. Moreover, for every i E [n]. i' E [n], 2 0, t' > 0, C and Cj are independent t & 1' (c) and C₁2 the same iteration & need not be independent). We define Wav 2 0 such that for every 2 the collection ( satisfies (3)
Remark 2.2 (partial participation). LoCoDL allows for a form of partial participation if we set Indeed, in that case, at steps 11 and 13 of the algorithm, all local variables æ; as well the common variable y are overwritten by the same up-to-date model j' d'. So, it does not matter that for a non- non-participating client with df = 0, the & were not computed for the S t since its last participation, they are not used in the process. However, update its local copy of y at every iteration. This can be done when Vg is much cheaper to compute that V f., is the case with g -1 1|?. A non- non-participating client can be completely idle for certain period of time, but when it resumes participating, it should receive the last estimates of x, and from the server it lost synchronization.
non-participatinn client should still
CONVERGENCE AND COMPLEXITY OF LoCoDL
Theorem 3.1 (linear convergence of LoCoDL). Suppose that Assumptions [.1 and 2.1 hold. In LoCoDL, suppose that 0 < < 7. 2p (² Wav) x 2 For every i ' 0, define the Lyapunov

---

Published as a conference paper at ICLR 2025
function
n | 2²11² + +nlly' x* 201l²)
7(1 20d)
1
Vp'
1 uill²
+ +
+nllpt
v111
p²x
(4)
where Vy(a*) and u3 = Vi((x*). Then LoCoDL converges linearly; for every
2 0.
E E To where == max (1- -D) 1+ 2w
1²x
11.
(5)
In addition, for every E [m], (æi)ee and (y") (ee) converge to x², (u.)EεN converges to u,, and (v* LeeN converges v², almost surely.
We place ourselves in the conditions of Theorem 3.1 We observe that in D the larger x. the better,
so given P we should set X = 2p p²(1 (1 + War) Then, choosing to maximize x yields
x = 1 Way
(6)
We now study the complexity of LoCoDL with X and chosen as in (6) and - ( We remark that LoCoDL has the same rate 7 == max(1 7H, 7 1)² as mere distributed gradient descent, as long as p w and Wav are small enough to have 1+22 I 7². This is remarkable: communicating with low frequency and compressed vectors does not harm convergence at all, until some threshold.
p²x
The iteration complexity of LoCoDL to reach e-accuracy, i.e. IE[V*] evv0 is
o (K+ ((*+
(1 Wav (11 + w)
loge (gge-1
(7)
p²
By choosing
( Wav (1 + w)
p= min
(8)
16
the iteration complexity becomes O (1: + w01 + wav)) loge-! and the communication complexity in number of communication rounds is p times the iteration complexity, that is
o ((v(l + wav w) + w(1 + wnv)) log c
the compressors are mutually independent, way # and the communication complexity can be cquivalently written as
o ((l1+vo+ wh) Vk + w (1+ ()) loge logg:))
as shown in Table I
Let us consider the example of independent rand-k compressors, for some E [d]. We have 1. Therefore, the communication complexity in numbers reals is l times the complexity
d number of rounds; that is, ((((((t Vn Vi d d(1+ + m)) loge-1). We can now choose
to minimize this complexity: with k = [ it becomes (( (((va+ d
V d) loge loge as
shown in Table 2 Let state this result: Corollary 3.2. In the conditions of Theorem 3.
suppose in addition that the compressors C₁ are independent r rand-k compressors with k = Suppose that 7 = ( x= n-14d/k and
1) (1) d2
p min
(9)
nk²K
Then the uplink communication complexity in number reals of LoCoDL
0 ((vVavá
d/R
+ loge loge.))
(10)
vn
7

---

Published as a conference paper at ICLR 2025
60
Lobkl liied
20
10
100
0.53
6.5
650
033
3.08
1.25
1.0
1.75
2.00
8.0
0.35
0.57
675
3.0
1:25
1.0
3.75
Communicave
87
288
Figure 1: Comparison of several algorithms with several compressors on logistic regression with the "a5a' dataset from the LibSVM, which has d = 122 and 6,414 data points. We chose different values of n to illustrate the two regimes n and d, as discussed at the end of Section
This is the same complexity as CompressedScaffnew (Condat et al. 2022a). However, obtained with simple independent compressors, which is much more practical than the permutation-bant based compressors with shared randomness of CompressedScaffnew Moreover, this complexity can be obtained with other types of compressors, and further reduced, when reasoning number of bits and not only reals, by making use of quantization (Albasyoni et al. 2020), as we illustrate by experiments in the next section.
We can distinguish 2 regimes:
1. In the "large d small n" regime, i.e. O(d), the communication complexity of LoCoDL in (TO) becomes O ((2/ du/
d) loge-1). This is the state of the art, as reported in Table
2. In the "large n small d' regime, i.e. n = Rdd), the communication complexity of LoCoDL in IT) becomes ((VaVk + d) loge - If is even larger with n ((d)), ADIANA achieves the even better complexity O ((VR= + d) loge-)).
Yet, in the experiments other algorithms, including ADIANA, in all cases.
with different datasets and values of d, n, K, LoCoDL outperforms the
3.1 THE CASE g= 0
We have assumed the presence of function in Problem [ whose gradient called by all clients. In this section, show that
handle the where such function is not available. So. let us assume that we want to minimize - fú. with the functions fq satisfying Assumption 1.1 We now define the functions f. strongly convex, with L L - and µı = H. Moreover,
$ 11. and == $ 11.112. They all L-smooth and ji- equivalent to minimize 1 ">= fa or Σn J. + g. We can then apply LoCoDL to the latter problem. At Step 5, simply have y' ~V(() (1 7 y The rate in 5 applies with L and μ. replaced by and j., respectively. < 2ks the asymptotic complexities derived above also apply to this setting. Thus, the presence of y in Problem (1 is not restrictive all, as the only property of g that matters is that has the same amount of strong convexity as the fis.
Since
4 EXPERIMENTS
We evaluate the performance of proposed method LoCoDL and compare it with several other methods that also allow for CC and converge linearly to x². We also include GradSkip (Maranjyan al. 2022) and Scaffold (McMahan et al. 2017) in comparisons. We focus regularized
8

---

Published as a conference paper at ICLR 2025
logistic regression problem, which has the form ① with
m
f(()) =
E log eex x.) 1 ||x1|
(11)
and / | where n is the number of clients, m is the number of data points per client, ai,a E R and bi, E (-1,+1} are the data samples, and is the regularization parameter, set so that x 10 For all algorithms other than LoCoDL, for which there no function g. the functions f. in have a twice higher μr, so that the problem remains the same.
We considered several datasets from the LibSVM library (Chang Lin, 2011) (3-clause BSD license).
We show the results with the 'a5a'. 'diabetes', 'wla' datasets in Figures| 2 respectively. Other datasets are shown in the Appendix. We prepared each dataset by first shuffling it, then distributing equally among the clients (since in (TT) is an integer, the remaining datapoints were discarded). We used four different compression operators in the class U(w), for some w 2 0:
rand-k for some & [d], which communicates 32k + k <logg [d)] bits. Indeed, the k randomly chosen values are sent in the standard 32-bits IEEE floating point format, and their locations are encoded with k([lgg(d)) (d)] additional bits. We have = g
Natural Compression (Horváth et al. 2022). a form of quantization in which floats are encoded into 9 bits instead of 32 bits. We have
A combination of rand-k and Natural Compression, in which the & chosen values are encoded into 9 bits, which yields total of 9k A: [d) bits. We have w 9d 1.
The I Ii-selection compressor, defined as C(rr) sign(a; (aaee)]ll=//e ||x]] where j is chosen randomly in [d]. with the probability of choosing j' E [d] equal to [z.z" [=]||, and ej is the j-th standard unit basis
vector in R.. sign(1;) [=a]|| is sent 32- 22-bits float and the location of j is indicated with [log, (d)], so that this compressor communicates 32 + [d)] bits. Like with rand-l, we have w = d 1.
The compressors different clients are independent, so that way in
We can see that LoCoDL, when combined with rand-k and Natural Compression, converges faster than all other algorithms, with respect to the total number of communicated bits per client. We chose two different numbers n of clients, one with n < d and another one with n > 2d, since the compressor of CompressedScaffnew different in the two cases 2d and et al. 2022a). LoCoDL outperforms CompressedScaffnew in both cases. As expected, all methods exhibit faster convergence with larger n. Remarkably, ADIANA, which has the best theoretical complexity for large n, improves upon DIANA but is not competitive with the LT-based methods CompressedScaffnew 5GCS-CC, and LoCoDL. This illustrates the power of doubly methods based on a successful combination of LT and CC. In this class, our new proposed LoCoDL algorithm shines. For all algorithms, we used the theoretical parameter values given their available convergence results (Corollary 3.2 for LoCoDL). We tried to tune the parameter values, such as & in rand-k and the (average) number of local steps per round, but this only gave minor improvements. For instance, ADIANA in Figure I was a bit faster with the best value of k 20 than with k 30. Increasing the learning rate ? led to inconsistent results, with sometimes divergence.
2d (Condat
CONCLUSION
We have proposed LoCoDL, which combines probabilistic Local Training mechanism similar the one of Scaffnew and Communication Compression with a large class of unbiased compressors. This successful combination makes LoCoDL highly communication-efficieee complexity with respect to the model dimension d and the condition number of the functions. In practice, LoCoDL outperforms other algorithms, including ADIANA, which has an even better complexity in theory obtained from Nesterov acceleration and not Local Training. This again shows the relevance of the popular mechanism of Local Training, which has been widely adopted in Federated Learning. A venue for future work is to implement bidirectional compression (Liu et al. 2020; Philippenko & Dieuleveut 2 Dorfman et al. 2023). We will also investigate extensions of method with calls to stochastic gradient estimates, with or without variance reduction, well as partial participation. These two features have been proposed for Scaffnew in Malinovsy et al. (2022)
with doubly accelerated
and Condat et al. (2023), but they are challenging combine with generic compression.

---

Published as a conference paper at ICLR 2025
400
L00h lebet
20
10
30
10
20000
300060
150000
200383
250080
330303
357003
500000
50380
180030
350836
20300
350330
306068
300000
430003
(b) 12 37
23-1
23-4
250066 320300
bumber Communicaee 1hs
(c) 73
Figure 2: Comparison of several algorithms with several compressors on logistic regression with the 'diabetes' dataset from the LibSVM, which has d and 768 data points. We chose different values of n to illustrate the three regimes n < d, n > d, n > dh, as discussed at the end of Section
1.7
baten
10"
10
10m
10-
0.23
0.55 Los 125
610
0.25
033
1000
1.50
1.35
2032
87
619
Figure 3: Comparison of several algorithms with various compressors on logistic regression with the "wla" dataset from the LibSVM, which has d = 300 and 2,477 data points. We chose different values of n to illustrate the two regimes, n < d and n > d, as discussed the end of Section 3
We have studied the strongly convex setting, because analyzing how the linear convergence rate depends on d, provides valuable insights on the algorithmic mechanisms. It should be possible to derive sublinear convergence results in the general convex case, by studying the objective gap instead of the squared distance to the solution, as was done for CompressedScaffnew (Condat et al. 2022ah and TAMUNA (Condat et al. 2023). An analysis with nonconvex functions, however, would certainly require different proof techniques. In nonconvex settings, compression works well (Huang ct al. 2022 Chen et al. 2024). but the properties of local training with variance reduction are less
clear Yi al. 2024 Meinhardt et al. 2024).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence.
REFERENCES
A. Albasyoni, M. Safaryan, L. Condat, and P. Richtárik. Optimal gradient compression for distributed and federated learning. preprint arXiv:2010.03246, 2020.
D. Basu, D. Data, C. Karakus, and S. N. Diggavi. Dsparse-Local-SSe Distributed SGD With Quan- tization, Sparsification, and Local Computations. IEEE Journal Selected Areas in Information Theory, 1(1):217-226, 2020.
D. P. Bertsekas. Convex optimization algorithms. Athena Scientific, Belmont, MA, USA, 2015.
A. Beznosikov, S. Horváth, P. Richtárik, and M. Safaryan. On biased compression for distributed learning. preprint arXiv:2002.12410, 2020.
K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. Practical secure aggregation for the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
machine learning. In Proc. of
C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Trans- actions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available at http///ww.ccii..ng www.iii.nt..u..... www..ed..t/////.. wtt.://////.lliiiiibss.m.
Chen, Z. Li, and Chi. Escaping saddle points in heterogeneous federated learning via distributed SGD with communication compression. In Proc. Int. Conf. Artificial Intelligence and Statisties (AISTATS), pp. 2701-2709, 2024.
L. Condat and P. Richtárik. MURANA: A generic framework for stochastic variance-reduced optimization. In Proc. of the conference Mathematical and Scientific Machine Learning (MSML), PMLR 190, 2022.
L. Condat and P. Richtárik. RandProx: Primal-dual optimization algorithms with randomized proximal updates. Proc. of International Conference on Learning Representations (ICLR), 2023.
L. Condat, I. Agarsky, and P. Richtárik. Provably doubly accelerated federated learning: The first theoretically successful combination of local training and compressed communication. preprint arXiv:2210. 13277, 2022a.
L. Condat, K. Li, and P. Richtárik. EF-BV: A unified theory of eтror feedback and variance reduction mechanisms for biased and unbiased compression distributed optimization. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2022b.
L. Condat, I. Agarsky, G. Malinovsky, and P. Richtárik. TAMUNA: Doubly accelerated federated learning with local training, compression, and partial participation. preprint arXiv:2302.099: 0.08222222222 pre- sented the Int. Workshop Federated Learning in the Age of Foundation Models in Conjunction with NeurIPS 2023, 2023.
R. Dorfman, S. Vargaftik, Y. Ben-Itzhak, and K. Y. Levy. DoCoFL: Downlink compression for cross-device federated learning. In Proc. of Int. Conf. Machine Learning (ICML), 2023.
Fatkhullin, Sokolov, F. Gorbunov, Li, P. Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. preprint ar arXiv2211000222 2021.
E. Gorbunov, F. Hanzely, and P. Richtárik. A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In Proc. of 23rd Int. Conf. Artificial Intelligence and Statistics (AISTATS), PMLR 108, 2020a.
11

---

Published as a conference paper at ICLR 2025
E. Gorbunov, D. Kovalev, D. Makarenko, and P. Richtárik. Linearly converging error compensated SGD. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2020b.
E. Gorbunov, K. Burlachenko, Z. Li, and P. Richtárik. MARINA: Faster non-convex distributed learning with compression. In Proc. of 38th Int. Conf. Machine Learning (ICML), pp- 3788-378880 3798, 2021.
R. M. Gower, M. Schmidt, F. Bach, and P. Richtárik. Variance-reduced methods for machine learning. Proc. of the IEEE, 108(11))1988-1999 November 2020.
M. Grudzien, G. Malinovsky, and P. Richtárik. Can 5th Generation Local Training Methods Support Client Sampling? Yes! In Proc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), 2023.
K. Gruntkowska, A. Tyurin, and P. Richtárik. EF21-P and friends: Improved theoretical communica- tion complexity for distributed optimization with bidirectional compression. In Proc. of 40th Int. Conf. Machine Learning (ICML), 2023.
Haddadpour, M. M. Kamani, Mokhtari, and M. Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In Proc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), PMLR 130, pp. 2350-2358, 2021.
F. Hanzely and P. Richtárik. One method to rule them all: Variance reduction for data, parameters and many new methods. preprint arXiv: 1266, 2019.
Y. He, X. Huang, and K. Yuan. Unbiased compression saves communication in distributed optimiza- tion: When and how much? In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2023.
S. Horváth, C.-Y. Ho, L. Horváth, A. N. Sahu, M. Canini, and Richtárik. Natural compression for distributed deep learning. In Proc. of the conference Mathematical and Scientific Machine Learning (MSML), PMLR 190, 2022.
S. Horváth, D. Kovalev, K. Mishchenko, S. Stich, and P. Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. Optimization Methods and Software, 2022.
X. Huang, Y. Chen, W. Yin, and K. Yuan. Lower bounds and nearly optimal algorithmss in distributed learning with communication compression. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), pp. 18955-18969, 2022.
P. Kairouz et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2), 2021.
S. S. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. U. Stich, and A. T. Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. Proc. of 37th Int. Conf. Machine Learning (ICML), pp. 5132-5144 1143, 2020.
Konečny, H. B. McMahan, D. Ramage, and Richtárik. Federated optimization: distributed machine learning for on-device intelligence. 111.v21610.02577, 2016a.
Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016b. arXiv:1610.05492.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322 1998.
Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 3(37):50-60, 2020a.
Z. Li, D. Kovalev, X. Qian, and P. Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In Proc. of 37th Int. Conf. Machine Learning (ICML), volume PMLR 119, 2020b.
12

---

Published as a conference paper at ICLR 2025
Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan. A double residual compression algorithm for efficient distributed learning. In Proc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), PMLR 108, pp. 133-143, 2020.
G. Malinovsky and Richtárik. Federated random reshuffling with compression and variance reduction. preprint arXivarrXi::2205.000 2022.
G. Malinovsky, K. Yi, and P. Richtárik. Variance reduced ProxSkip: Algorithm, theory and application to federated learning. Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2022.
A. Maranjyan, M. Safaryan, and P. Richtárik. GradSkip: Communication-acceleraaaa local gradient methods with better computational complexity. preprint arXiv:2210.16400 2022.
H. B. McMahan, E. Moore, D. Ramage, Hampson, and Agüera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Proc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), PMLR 54, 2017.
G. Meinhardt, K. Yi, L. Condat, and P. Richtárik. Prune at the clients, not the server: Accelerated sparse training in federated learning, preprint urXiv:2405.20622 2024.
K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárík. Distributed learning with compressed gradient differences. arXiv: .09269, 2019.
K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtárik. ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally! Proc. of the 39th International Conference on Machine Leurning (ICML), July 2022.
C. Phillippenko and A. Dieuleveut. Artemis: tight convergence guarantees for bidirectional compres- sion in federated learning. preprint arXiv:2006. 14591, 2020.
C. Philippenko and A. Dieuleveut. Preserved central model for faster bidirectional compression in distributed settings. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2021.
A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani. FedPAQ: communication- efficient federated learning method with periodic averaging and quantization. In Proc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), pp. 2021-2031, 2020.
P. Richtárik, I. Sokolov, and I. Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. In Proc. of 35th Conf. Neural Information Processing Systems (NeurIPS), 2021.
A. Sadiev, D. Kovalev, and P. Richtárik. Communication acceleration of local gradient methods via an accelerated primal-dual algorithm with an inexact prox. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2022a.
A. Sadiev, G. Malinovsky, E. Gorbunov, I. Sokolov, A. Khaled, K. Burlachenko, and P. Richtárik. Federated optimization algorithms with random reshuffling and gradient compression. preprint arXiv:2206.070211 2022b.
K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié. Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, 20:1-31, 2019.
S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
S. Sra, S. Nowozin, and S. J. Wright. Optimization for Machine Learning. The MIT Press, 2011.
A. Tyurin and P. Richtárik. DASHA: Distributed nonconvex optimization with communication compression, optimal oracle complexity, and no client synchronization. In Proc. of International Conference on Learning Representations (ICIR), 2023a.
A. Tyurin and P. Richtárik. 2Direction: Theoretically faster distributed training with bidirectional communication compression. In Proc. of Conf. Neural Information Processing Systems (NeurIPS), 2023b.
13

---

Published as a conference paper at ICLR 2025
J. Wang et al. A field guide to federated optimization, preprint arXiv:2107.06917, 2021.
H. Yang, M. Fang, and J. Liu. Achieving linear speedup with partial worker participation in non-lll) federated learning. In Proc. of International Conference on Learning Representations (ICLR), 2021.
H. Yang, Qiu, P. Khanduri, M. Fang, and Liu. Understanding server-assisted federated learning in the presence of incomplete client participation. In Proc. of Int. Conf. Machine Learning (ICML), 2024.
K. Yi, G. Meinhardt, L. Condat, and Richtárik. FedComLoc: Communication--fficci distributed training of sparse and quantized models. preprint arXiv:2403.0990% 2024.
Y. Zhao, M. Li, L. Lai, N. Suda, D. Civin, and V. Chandra. Federated learning with non-iid data. preprint arXiv: 806.00582, 2018.
14

---

Published as a conference paper at ICLR 2025
Appendix
CONTENTS
Introduction
Problem and Motivation
State of the Art
2
General Class of Unbiased Random Compressors
..4
Challenge and Contributions
2
Proposed Algorithm LoCoDL
2.1
Principle: Double Lifting of the Problem Consensus Problem
2.2
Description of LoCoDL
3
Convergence and Complexity of LoCoDL
3.1
The Case g
4
Experiments
5
Conclusion
Proof of Theorem 3.1
15
Additional Experiments
19
A PROOF OF THEOREM 3.1
We define the Euclidean space X' Rdd and the product space X xn+1 endowed with the weighted inner product
Σ (oi, x n(y.)) Vx = (01, Fn. u), x' = (o/
(x, x
(12)
We define the copy operator 1 x X (xt (,,...,,,,0, x, E X and the linear operator
S X 17, with T
Σ i=1
xi + ny
(13)
2n
S is the orthogonal projector in X onto the consensus line (x X define the linear operator
21
In y). We also
W = Id-S: x (I,,..,,,. E X + (x) - En F, y F,Y- with T
In,
Σ
ny
2n
(14)
where Id denotes the identity. W is the orthogonal projector in X' onto the hyperplane (x E X Ii + ...... + H, + ny = 0}. which is orthogonal to the consensus line. As such, it is self-adjoint, positive semidefinite, its eigenvalues are (1,..., 1, 0), its kernel is the consensus line, and its spectral
15

---

Published as a conference paper at ICLR 2025
norm is 1. Also, W W. Note that we can write W in terms of the differences d, 2; y and
2n Di=1 dz
W : = (x1
Fn. v) - (d1 d,....d. dn d. d).
(15)
Since for every (I1, In. v) Wx = ..... 0) if and only if x1 = In y. we can reformulate the problem as
min ())
f(x)
s.t. Wx 0,
(16)
where f(x) == E (zx) + ng(y). Note that X, is L-smooth and p-strongly convex, and Vf(x) = (Vfi(z1),... Vg(v)).
Let f 2 O. We also introduce vector notations for the variables of the algorithm: x = (af,..., r y'), X = (#)..... H4 (¹), u' == (uf,..., uh v²), u ...,..., u 2² w' = x Vf(xx' w = x* - ~V((x*) where x* = 1x is the unique solution to (16). We also define  2m (2=n df nn²) and = 7(+22]]
Then we can write the iteration of LoCoDL
X = x - y Vf(x*) + yu' w + qu' flip coin 0 E {0. 1} with Prob(0' = 1) p 0' =1
d' = (#) 8 ",...,C,, C, - -)))
d' 2n 2i=1 d²
x(+1 = (1 - p) + pl( + +
(17)
ut+1 u' x(1d -d') -W-d
else
x111 = X¹
n1+1 = n'
end
We denote by F the o-algebra generated by the collection of X-valued random variables x", u .....,,"" x u'.
Since we suppose that Su and we have Swa d 0 in the update u, we have Su' 0 for every? t' 2 0.
If 0² 1, have
| +1
u²
12 ||u' u 1 2 + X2
d''l x - 2A/uu' - w'd)
W |d
x
= ||uu' u
|
+ X2
X2 [| 1 - 22(u' - u='d'))
x
because Su' = SS* = 0, so that (u' - Sd') 0.
The variance inequality satisfied by the compressors C, is equivalent to E [[(c(())1]] s (1
w) ||= so that
E ||d |F 0² =1 s (1 w) |||0-
- 10 12
Also,
E(d'
Fr 0² =1] x¹ - -1ÿ²
Thus,
u +1 - uul] 11112 |F(]
= (1 - p) ||u' -04-uu1 11 + pl || u² 11112= |F,00"= 00 =
< ||u' -
an'-u=ll'" 112 + p2 w) || 11j" 1
pA
|sa||| 1| | 0² =
2pA(uu' - uu, 8' - -17²)x
|luu (u'-u") 1|2 + +px2 (1 w) || - -10' 12 PA'E
Sd
2 x
|F 0'
00 =1]
-2pA/n' u², x²'x')xx
16

---

Published as a conference paper at ICLR 2025
Moreover, E ||sd' 11 |F 0 =1 2 [B[Sd' | |F, 0 = 1112x = ||S 10 and
||80 10 1xx = ||588* - 16'1lx + || x so that
B||lutt (a-4t-ull: | |r||
E
- |u' - 11211x + -A + w) ||8- - -10'lx - -22 1222|ssx* - -1001
ud'-u"ll"
- -2p)(u' - ='' x
= ||u uu'-u'll 11112x + +pX2 | 100 10 + +p2 | 2p2(u' -u",, x²,x)'xx. x.
From the Peter-Paul inequality ||a + B112 v 2||a|| + 22 for any and b, we have
||x -
181-10'11 10011i =
|| | - 8²1 = Σ [ - x²) - (0' - x²) 1
$ Σ (21 - x")l + 2 11 - 11)
Σ | - x + n 1100 - 1011?
n
2
2 1 1= 1|x = 2 |
(18)
Hence,
E |r(]
S |u' - 1011xx - pA - (ww+2w)|| || x - 22p((u' - -u", x²)x))x)
On the other hand,
E x +1 - x 11
1 F 0 00-1 = (1 1| - -x11
+ 2 || (55 + + - 1x11 1 1F =
+ +2p -p) (x' - xx', ( xx', + x Fr, 0 = 1]) -x')x
We have B(d
F-,0=1 1| = 2n Eイ= 2 - 1//0 = x² - "J" so that
1 10 + B F 0 1|) = 1F'= = SR.
In addition,
(8' (8'-x", 58x - -x*) x = =(** - x", S,( - xx))x x = =1|5(8* - x²
x",
Moreover,
E || + d)- - dd)-
-xy11x | 1F 1| || + B[d F 0 11) -x* 1x1
+E 1 1dd
E[d F 1))1l² | 1]
|S8
xx1 xx
+ 2nE ||
B[d
F 0 = 1|1l² |=
and, using 3
I8 d - LEd F 0- -1]11² F 0 = 1
Way
Σ
a 0012
<
4n
i=1
Way
|| x
2n
17

---

Published as a conference paper at ICLR 2025
where the second inequality follows from 18 Hence,
E ||x - x" x11
|
0
-0=11
1 - (1 - p)3 || - x 11x + p² 2|1sx* - -xx -x11xx + pa 11 l| 1
+ 2p - p) ||5(x* - -x0)
(1 - (1= || - -x'1 + &Pawar ||V*111
+ (2p - p²²) ||S - -xt)l
(1 - (1- ||x - -x11xx +p2wav || x
+ (2p /²) (1 x" *11xx - -||"
= || -x1111
xx1 11 - (2p p² -pp p2wwar) ||Wx*112
and
E || - 111 -x
|r²
= (1 p) |8 x' $12 + pl ||x -x11=x x111xx |F 0r =1]
S || x' 11x p22 p²(1 + wax)) 11 x'| |
Furthermore,
||xt -x x1 = || w w'
1 x + 72 |u' u²
1 + 27' -w", u² - u²)xx
wt w+
72 | u²
2 + 22 -x,, - u²)x
= w' w' 1 x 72
[ u²
1 + 27 ,u' =u')x,
which yields
E ||x +1 xx
[r 1 Iw' w' 1|
72 |u' u²
1 + 2 .u' ==)xx
p(2pp 0² (1 Wav)) |
1
x
Hence, with 2 7[++2]]'
x
r+ - x111xx |
71 2w)
E || -1= 11= |
u²
p² X
1 || |w' - -w* 1x ?
||u' u 112 + 2 uu - -u")x - _(p p² + wav)) | 1|
7
7(1 + 2w)
1/u1 u 112 + PX
| - -2(u² - -u*,
p²x
1 1|w² w'1 1 + 7(1 + 2w) (1
p²x
l/ue - -u- 1|x
p²x
1 2w
P -(2p - (1 + war) - x) ||
x
Therefore, assuming that 2p- pp²(1 + Wav)
X 2 0.
E 2 < || w -w x + (1
p²x
7(1+ 2w)
1u'
u 12
+ 2w
p2x
According to Condat & Richtárik (2023
Lemma 1),
|w w
x = [[(dd - >V))x* - -(Id - -VVV)***
S maax(1 - 714, - 1)² 1xx-
- x*1 x
Hence,
E E |F < max (1 (1-7w);;11-227
p2 + 2w
(19)
Using the tower rule, we can unroll the recursion in (19 to obtain the unconditional expectation of g+++
Using classical results on supermartingale convergence (Bertsekas 2015 Proposition A.4.5),
follows from (19 that T - 0 almost surely. Almost sure convergence of x' and u follows.
18

---

Published as a conference paper at ICLR 2025
600
10"
101
30000
10:000
Mimber Communtonne
2583E0
20000
258003
300000
50636
S03655
Communicatee
15300
260383
200066
333303
(b) 41
23-4
324
5300
bumber 5T Communicanee 1it
(c) 225
Figure 4: Comparison of several algorithms with various compressors logistic regression with the "australian" dataset from the LibSVM, which has d 14 and 690 data points. We chose different values of illustrate the three regimes: < d, n d. dL, as discussed at the end of Section 3
B ADDITIONAL EXPERIMENTS
The results with the 'australian' and 'covtype.binaat datasets from the LibSVM library, for the same logistic regression problem as in Section with = 10a. are shown in Figures and 5 Finally, we also run experiments on MNIST dataset (LeCun et al. 1998) Figure LoCoDL consistently outperforms the other algorithms in terms of communication efficiency.
In an additional experiment, we investigate how heterogeneity of the functions influences the conver- gence. We consider logistic regression as above, but with synthetic data sampled from the Dirichlet distribution parameter a. is small, the Dirichlet distribution becomes similar to the uniform distribution over the simplex, which corresponds to the heterogeneous case where there is no similar- ity between the data. If a is large, the samples of the Dirichlet distribution tend to be similar to each other and concentrated around the middle point (1/d.... 1/d) of the simplex. We set
100 and 10, and a single random sample is assigned to each client. The results are shown in Figure 7 for and 10. With these values of and d, ADIANA has better theoretical complexity than LoCoDL. However, in practice, we observe that LoCoDL again outperforms ADIANA. For both methods, joint sparsification and quantization with rand-1 and natural compression performs best. There is no significant difference depending on the value of a.
19

---

Published as a conference paper at ICLR 2025
10"
10
Mamber of Communicanes Bh:
Mimber of Communicated Bie
(a) 72
6
(b) 12 100
22-3
(c) 72 6, 000
Figure 5: comparison of LoCoDL and ADIANA using several compressors for logistic regression with the covtype.binary dataset from the LibSVM, which has d = 54 and 581,010 data points. We chose different values of illustrate the three regimes n < d, n >> n >> d², as discussed the end of Section
Rand-323
JCCOZi: Natural
LECO/L Rana-333 Naturai
10
AD Natural
60 Rand Momane
70 20A00
10
10
0.2
Number of Communicated Bits
1e7
Figure 6: Comparison of LoCoDL and ADIANA using several compressors for logistic regression.
The task was classifying 7s and 8s from the MNIST (LeCun et al. 1998) dataset, which consists of
d = 28 x 28 784 dimensions and 14,118 data points. We chose n = 6 (100x smaller than d).
20

---

Published as a conference paper at ICLR 2025
24
UOCLL Bing
COCAL Rert:
10
10m
38002
100068
150003
230000
200000
5ed6e
103000
150000
200026 250303
a=)
(b) 10
Figure 7: Comparison of LoCoDL and ADIANA with various compressors logistic regression (n 100, d = 10), with samples from the Dirichlet distribution of parameter with = on the left and a 10 on the right.
21


Reviews:
[{"review_id": "Ajb9hPzJWD", "reviewer": "Reviewer_1VVx", "summary": "This paper proposed the LoCoDL algorithm, which applies both communication compression and local updates in distributed training, and analyzed its complexity, showing that with suitable compression scheme the total communication complexity matches that of the accelerated compressed methods", "questions": "1. Can the authors please explain in more details and provide some intuitions on why does LoCoDL \"require\" a regularisation $g$ to work? I put \"require\" in quotes because, as explained in section 3.1, one can reduce the case with $g=0$ to some strongly convex $\\tilde g$. But such reduction highlights the fact that the algorithm, on its own, does need a strongly convex $g$, which seems quite mysterious to me. I think it would significantly improve my understanding of the technique if the authors can point out why/if LoCoDL, as is and without the reduction, would fail when $g=0$.\n\n2. Based on the choice of the Lyapunov function, it seems to me that the convergence of LoCoDL is characterised in terms of $\\frac{1}{n}\\sum\\lVert x_i^t-x^\\star\\rVert^2$. While ProxSkip's analysis also uses this convergence criteria, there the situation is slightly different since if the composite part can attain infinity then there is just no way to prove convergence in terms of the optimality gap when the prox step is skipped. But here the situation seems different, I wonder if it's possible to prove the convergence of LoCoDL in terms of the optimality gap, say, $f(\\bar x) + g(\\bar x)-f(x^\\star)-g(x^\\star)$ where $\\bar x$ is the average of the primal variable (or perhaps the average optimality gap of each clients)? If not, what's the difficulty here? I think some of the algorithms that the authors compare LoCoDL against do use optimality gap as the convergence criteria, so there might be some mismatch.\n\n3. The paper focuses on the strongly convex case. While the authors mentioned that non convex case might require significantly different techniques, I wonder what about the general convex case? It seems that LoCoDL would fail in that case (see also my question regarding $g$), but can the authors provide some insights in what would fail in the general convex case?\n\n4. I wonder if LoCoDL can handle stochastic gradients? It seems to me that the idea of compressing the difference between two estimates works well with full gradient computations, but might not work so well when there is noise (e.g. EF21 fail to converge beyond the variance of the noise and ProxSkip's original analysis cannot achieve linear speedup with the noise). Is it also the case here? Have the authors tried the stochastic case?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method, LoCoDL manages to combine both local updates and communication compression, and show that in the strongly convex regime, the method enjoys the communication-saving benefits of both techniques. LoCoDL combines ideas from ProxSkip and EF21 (and the likes) with primal-dual updates to achieve this impressive result.", "weaknesses": "see questions.", "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": "aRjpHsKiUX", "reviewer": "Reviewer_fCdQ", "summary": "This paper studies how to develop communication-efficient algorithms for centralized optimization problem by combining the idea of local training and communication compression, and proposes an algorithm called LoCoDL. LoCoDL is both validated theoretically through a nearly optimal convergence rate and via empirically by comparing with previous SOTA algorithms.", "questions": "1. It is a little bit strange that ADIANA performs worse than other baseline algorithms. Are the hyperparameters not sufficiently tuned?\n2. Since with communication compression only we can achieve the optimal theoretical convergence rate, how to illustrate the theoretical benefit of using \"local steps with local models\"?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Though the area of local training and communication compression has been explored by previous works, it may still be challenging to develop algorithms combining these ideas to achieve the theoretically optimal convergence rate. LoCoDL is shown to be optimal in cases where $n$ is smaller than the problem dimension $d$, which is often the case in real settings. Considering the assumptions used are standard, this result is believed to be strong enough.\n2. It is impressive that LoCoDL performs much better than ADIANA, which has been the SOTA algorithm in distributed deterministic convex optimization with communication compression, and enjoys an optimal convergence rate matching the convergence lower bound.", "weaknesses": "1. The theoretical results are not perfect. Since LoCoDL has a sub-optimal rate in the case where $n$ is larger than $d$, its unclear whether it is the algorithm or the analysis is sub-optimal. As ADIANA has already achieves the optimal rate, it should be better if the author discuss the challenges to achieve a same rate.\n2. It's not clear how LoCoDL is derived by combining the two ideas \"local steps with local models\" and \"compressing the difference of two estimates\". It is recommended that the authors discuss the motivation behind each algorithm line.", "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": "OM1WFUrBzB", "reviewer": "Reviewer_k7Jx", "summary": "This paper proposes LoCoDL, an algorithm for distributed optimization that incorporates both local training and communication compression. The design of LoCoDL uses a primal-dual approach and randomization, provably achieving double acceleration in strongly convex landscape with unbiased compression. Empirical advantages of LoCoDL are demonstrated from experiments.", "questions": "* Please consider a more comprehensive experimental evaluation.\n  * Since nonconvex landscape is not covered by theory, experiments on deep neural networks can be done to show its performance in handling nonconvex problems.\n  * The theory claims heterogeneous setting but experiments are done on a homogeneous distribution of dataset. Experiments with data heterogeneity can be conducted, as in previous related works like [1,2].\n* I suggest the authors provide more discussions on the primal-dual design. How does this help with your proof? What challenges will you encounter without this primal-dual approach?\n\n[1] Huang, X., Chen, Y., Yin, W., and Yuan, K. (2022). Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems, 35, 18955-18969.\n\n[2] Chen, S., Li, Z., and Chi, Y. (2024). Escaping Saddle Points in Heterogeneous Federated Learning via Distributed SGD with Communication Compression. In International Conference on Artificial Intelligence and Statistics (pp. 2701-2709). PMLR.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The design of LoCoDL shows novelty such as the introduction of primal-dual updates.\n* The convergence of LoCoDL with unbiased compression under strongly convex landscape is supported by rigorous theoretical analysis, provably showing a reduced communication overhead.\n* LoCoDL achieves empirical advantages in experiments on regularized logistic regression.\n* The presentation of the paper is well-organized and clear to follow.", "weaknesses": "* The theory of this paper has some limitation. For example, it assumes the usage of unbiased compression, which does not encompass some popular biased schemes such as Top-k compression. The proof also exploits strong convexity and nonconvex landscape poses a challenge.\n* Empirical evaluations are conducted only on regularized logistic regression with homogeneous distribution of local dataset. The experiments are not able to demonstrate the performance in heterogeneous settings (which is claimed by the theory) and nonconvex problems; also see Questions.", "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": "UF3mMEovbN", "reviewer": "Reviewer_ycJW", "summary": "The paper combines local update with compression to improve communication efficiency in distributed estimation.", "questions": "1. What is the intuition that make the proposed algorithm work compared to existing works that combines LT and CC?\n2. Is the rate obtained optimal?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Proves the proposed algorithm the accelerate communication complexity due to both components used.", "weaknesses": "Only demonstrate strongly convex case. Assuming g is smooth (exclude non-smooth penalty such as lasso, for example)", "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 (Spotlight)