GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity
Authors: Arto Maranjyan
Mher Safaryan
Peter Richtárik
Venue: Accepted by TMLR ()

Abstract: We study a class of distributed optimization algorithms that aim to alleviate high communication costs by allowing clients to perform multiple local gradient-type training steps before communication. In a recent breakthrough, Mishchenko et al. (2022) proved that local training, when properly executed, leads to provable communication acceleration, and this holds in the strongly convex regime without relying on any data similarity assumptions. However, their ProxSkip method requires all clients to take the same number of local training steps in each communication round. We propose a redesign of the ProxSkip method, allowing clients with ``less important'' data to get away with fewer local training steps without impacting the overall communication complexity of the method. In particular, we prove that our modified method, GradSkip, converges linearly under the same assumptions and has the same accelerated communication complexity, while the number of local gradient steps can be reduced relative to a local condition number. We further generalize our method by extending the randomness of probabilistic alternations to arbitrary unbiased compression operators and by considering a generic proximable regularizer. This generalization, which we call GradSkip+, recovers several related methods in the literature as special cases. Finally, we present an empirical study on carefully designed toy problems that confirm our theoretical claims.

Published in Transactions on Machine Learning Research (06/2025)
GradSkip: Conmunication-Acceleraeed Local Gradient Methods with Better Computational Complexity
Artavazd Maranjyan'
arto.manwiyan@@mmaal.comm
King Abdullah University of Science end Technology (KAUST)
Mher Safaryan
mobersse/arrynns@maall.com
King Abdullah University of Science end Technology (KAUST)
Peter Richtárik
yeler.richlarikkkkasstccco
King Abdullah University of Science and Technology (KAUST)
Reviewed on OpenReview: https: // openreview. net/ forum? id= FRF
Abstract
We study a class of distributed optimization algorithms that aim to alleviate high communi- cation costs by allowing clients to perform multiple local gradient-type training steps before communication. In a recent breakthrough, Mishchenko al. (2022) proved that local training, when properly exccuted, leads to provable communication accelcration, and this holds in the strongly convex regime without relying any data similarily assumptions. However, their ProxSkip method requires all clients to take the same number of local training steps in each communication round. We propose a redesign of the ProxSkip method, allowing clients with "less important" data to get away with fewer local training steps without impacting the overall communication complexity of the method. In particular, we prove that our modified method, GradSkip, converges linearly under the same assumptions and has the same accelerated communication complexity, while the number of local gradient steps can be reduced relative to local condition number. We further generalize our method by extending the randomness of probabilistic alternations to arbitrary unbiased compression operators and by considering a generic proximable regularizer. This generalization, which we call GradSkip+, recovers several related methods in the literature as special cases. Finally, we present an empirical study on carefully designed toy problems that confirm our theoretical claims.
1 Introduction
Federated Learning (FL) an emerging distributed machine learning paradigm where diverse data holders or clients (c.g., smartwatches, mobile devices, laptops, hospitals) collectively aim to train single machine learning model without revealing local data to each other the orchestrating central server (McMahan et al. 2017: Kairouz et al 2019 Wang 2021b. 'raining such models amounts to solving federated optimization problems of the form
n f(x) = n - (
min #ER
(1)
where d is the (typically large) mumber of parameters of the model Ed we aim to train, and is the (potentially large) total number of devices in the federated environment. We denote by fi(a) the loss or risk associated with the data D; stored on client i E [n] = (1, Formally, our goal is to minimize the overall loss/ /isk denoted by f(x).
Work done during an internship at KAUST, while being researcher at VerevaNN student Yerevan State University.
1

---

Published in Transactions on Machine Learning Research (06/2025)
Due to their efficiency, gradient-type methods with its numerous extensions DDuchi et al. 2011 Zeiler 2012
Ghadimi & Lan 2013 Kingma & Ba 2015 Schmidt et al. 2017 Qian et al. 2019 Gorbunov et al. 2020a is
by far the most dominant method for solving in practice.
The simplest implementation gradient descent in federated setup requires all workers i [n] in each time step 2 0 to
compute the local gradient Vz(())) at the current global model It,
update the current global model Ie using this gradient with step size >>
a = -
(2)
(iii) average the updated local models f to get the new global model
11+1
(3)
n
Challenges defining FL unique distributed training setup, necessitating training algorithm adjustments, include high communication costs, heterogeneous data distribution, and system heterogeneily across clients. Next, we discuss these challenges and potential algorithmic solutions.
1.1 Communication Costs
In federated oplimization, communication costs often become a primary bottleneck due to slow and unreliable wireless links between clients and the central server (McMahan et al. 2017). Eliminating the communication step (3) entirely would cause clients to train solcly on local data, leading to a poor model because of the limited local data.
A simple trick to reduce communication costs is perform the costly synchronization step 3 infrequently,
allowing multiple local gradient steps (2) in each communication round (Mangasarian 1995). This trick
appears in the celebrated FedAvg algorithm of McMahan al. (2016 2017) and its further variations
Haddadpourr & Mahdavi 2019 Li et al., 2019a Khaled et al.] 201 9a b Karimireddy et al. 2020 Horváth et al. 2022) under the name of local gradient methods. However, until very recently, theoretical guarantees on the convergence rates of local gradient methods were worse than the rate of classical gradient descent, which synchronizes after every gradient step.
In recent line of works (Mishchenko al. 2022 Malinovsky al. 2022 Condat & Richtárik 2022 Sadiev
et al. 2022), initiated by Mishchenko et al. (2022). , novel local gradient method, called ProxSkip, proposed which performs random number of local gradient steps before each communication (alternation between local training and synchronization is probabilistic) and guarantees strong communication acceleration properties. First, they reformulate the problem 1 into an equivalent regularized consensus problem of the form
min ERd
f((zz) + (1 mn) n
(4)
0,
if x
Un:
( In)
+00,
otherwise,
where communication between the clients and averaging local models Fi,..., En is encoded as taking the proximal step with respect to v i.c.,
prox ([x ... Fn = [T. T.... ......." T where T = Σ Tz.
1=1
With this reformulation, ProxSkip by Mishchenko step with small probability p 1/Ve, where is the condition number of the problem. Then method's 's key result.
(022) performs the proximal (equivalently averaging)
2

---

Published in Transactions on Machine Learning Research (06/2025)
for smooth, strongly convex setups is Okk 1/c) iteration complexity with O (v 1/c) communication rounds to achieve >> 0 accuracy. Follow-up works extend the method to variance-reduced gradient methods [Malinovsky et al. 2022), randomized application of proximal operator (Condat & Richtárik 2022), and accelerated primal-dual algorithms (Sadiev et al., 2022). Our work was inspired by the development this new generation of local gradient methods, also known as Local Training (I.T) methods, which we detail
shortly.
An orthogonal approach uses communication compression strategies on the transferred information. Informally, instead of communicating full precision models infrequently, might communicate compressed version of the local model in each iteration via an application of lossy compression operators. Such strategics include sparsification (Alistarh et al.) 2018 Wang et al. 2018 Mishchenko et al. 2020), quantization (Alistarh et al.)
2017 Sun et al. 2019 Wang et al. 2022). sketching (Hanzely et al. 2018
Safaryan et al, 2021 and low-rank
approximation Vogels et al. 2019).
Our work contributes the first approach to handling high communication costs that is less understood in theory and, at the same time, immensely popular in the practice of FL.
1.2 Statistical Heterogeneity
Due to the decentralized training data, distributions of local datasets can vary from client to client. This heterogeneity in data distributions poses an additional challenge since allowing multiple local steps would make the local models deviate from each other, issue widely known client drift. On the other hand, if training datasets are identical across the clients (commonly referred to homogeneous setup), the mentioned drifting issue disappears, and the training can be done without any communication whatsocver. Interpolating between these extremes, under some data similarity conditions (which are lypically expressed as gradient similarity conditions), multiple local gradient steps should be useful. In fact, initial theoretical guarantees of local gradient methods utilize such assumptions (Haddadpour Mahdavi 2019 Yu al. 2019
Li et al. 2019b: 2020).
In the fully heterogeneous setup, client drift reduction techniques were designed and analyzed to mitigate the adverse effect of local model deviations (Karimireddy et al. 2020 Gorbunov et al. 2021). A very close
analogy is variance reduction techniques called error feedback mechanisms for the compression noise added to lessen the number of bits required to transfer (Condat et al. 2022
1.3 System Heterogeneity
Lastly, system heterogeneity refers to the diversity of clients in terms of their computation capabilities or the amount of resources they are willing to use during the training. In a typical FL setup, all participating clients must perform the same amount of local gradient steps before each communication Consequently, a highly heterogeneous cluster of devices results in significant and unexpected delays due to slow clients or stragglers.
One approach addressing system heterogencity or dealing with slow clients client selection strategies (Wang & Joshi 2019 Reisizadeh et. al. 2020 Luo et. al.) 2021). Basically, client sampling can be organized that slow clients do not delay global synchronization, and clients with similar computational capabilities are sampled in each communication round.
Unlike the above strategy, we suggest clients take local steps based on their resources. We consider the full participation setup where clients decide how much local computation to perform before communication. Informally, slow clients do less local work than fast clients, and during the synchronization of locally trained models, the slowdown caused by the stragglers will be minimized see section 5.2
1.4 Local Training (LT) vs Accelerated Gradient Descent (AGD)
Nesterov's AGD method Nesterov (0044) matches the communication complexity our GradSkip algorithm. Its distributed implementation takes one local stop per round, suggesting LT methods might lag behind AGD. In contrast, almost all methods in production are based on local training, as evidenced by FL frameworks
like He et al. 2020 : Ro et. al. (2021): ) Beutel et al. 2022
3

---

Published in Transactions on Machine Learning Research (06/2025)
The preference for LT over AGD among practitioners stems from LT's advantages, especially in generalization and communication complexity. Both areas are closely tied with local training, becoming prominent in current research. LT's ability to enhance generalization remains under exploration in FL. Current studies link this improvement to personalization, meta-learning Hanzely et al. (2020) Hanzely & Richtárik (2021), and representation learning Collins et al. (2022). Practically, LT elfectively tackles nonconvex challenges
while AGD faces difficulty approximating stationary points of smooth nonconvex functions. Additionally, AGD is more sensitive the knowledge of the condition number than LT methods, which are versatile and work across wide range of numbers of local steps.
In statistically heterogencous cases, AGD often underperforms. Our experiments prove this by showing that when device condition numbers vary, AGD converges slower than GradSkip. Though our work does not primarily aim to directly compare AGD and LT, such comparative study, to our knowledge, remains a gap in current research and could offer valuable insights.
2
Summary of Contributions
Our key contributions are summarized below.
2.1
GradSkip: Efficient Gradient Skipping Algorithm
We propose GradSkip (Algorithm 1,, new local gradient-type method for distributed optimization that reduces both communication and computation. Our method extends the recently developed ProxSkip (Mishchenko et al. 2022), which first demonstrated communication acceleration via multiple local steps without data similarity assumptions. GradSkip not only inherits this accelerated communication complexity but also introduces a key improvement: it allows clients to terminate their local gradient computations independently, significantly improving computational efficiency.
The key technical novelty of the proposed algorithm is the construction of auxiliary shifts dat to handle gradient skipping for each client E [n]. GradSkip also maintains shifts hit initially introduced in ProxSkip to handle communication skipping across the clients. We prove that GradSkip converges linearly in strongly convex and smooth setup, has the same O log 1/c) accelerated communication complexity as ProxSkip, and requires clicnts to compute (in expectation) at most min { Ki, //max } local gradients in cach communication round (see Theorem 3.6), where K; is the condition number for client E [n]] and Kmax = max; Kü- Thus, for GradSkip, clients with cell-conditioned problems K2 < Vfmax perform much less local work achieve the same convergence rate of ProxSkip, which assumes /Kmma local steps average for all clients.
2.2 GradSkip+: General GradSkip Method
Next, we generalize the construction and the analysis of GradSkip by extending in two directions: handling optimization problems with arbitrary proximable regularizer and incorporating general randomization procedures using unbiased compression operators with custom variance bounds. This leads to our second method, GradSkip+ (see Algorithm 2 which recovers several methods in the literature special case, including the standard proximal gradient descent (ProxGD), ProxSkip [Mishchenko et al. 2022 RandProx-FB (Condat & Richtárik 2022) and GradSkip.
2.3 :R-GradSkip+:: Reducing the Variance of Stochastic Gradient Skipping
Finally, we proposc and analyze varianco-reduced extension (see Algorithm 3 in the Appendix) in the case when mini-batch stochastic gradients are implemented instead of full-batch gradients for local computations. Our VR-GradSkip+ method can be viewed as a successful combination of ProxSkip-VR method of Malinovsky ct al. (2022) and GradSkip providing computational efficiency through processing smaller batch of samples and probabilistically skipping stochastic gradient computations. We deferred the presentation of the part of our contribution in the appendix due to space limitations.
4

---

Published in Transactions on Machine Learning Research (06/2025)
3 GradSkip
In this section, we present our first algorithm, GradSkip, and discuss its benefits in detail. Later, we will generalize it, unifying several other methods as special cases. Recall that our (arget is to address three challenges in FL mentioned in the introductory part, which are
reduction in communication cost via infrequent synchronization of local models, (ii
statistical or data hetcrogeneity, and
iii
reduction in computational cost via limiting local gradient calls based on the local subproblem.
We now describe all the steps of the algorithm and how it handles these three cha challenges.
3.1
Algorithm Structure
For the sake of presentation, we describe the progress of the algorithm using two variables Ti,, fi,e for the local models and two variables hi,s h4,sh,, for the local gradient shifts. Essentially, want to maintain two variables for the local models since clients get synchronized infrequently. The shifts h are designed to reduce the client drift caused by the statistical heterogeneity. Finally, we introduce auxiliary shifts hú, to take care of the different number of local steps. The GradSkip method is formally presented in Algorithm |
A Algorithm GradSkip
1: Input:
stepsize > 0, synchronization probability probabilities > 0 controlling local steps, initial local iterates 1,, = In,0 E Rd, initial shifts h1,0..... hn,o E Rd, total mumber of iterations 2 1
2: for = 0, I.......7 T do server: Flip a coin 0, {0, 13 with Prob(0: = 1) =
Decide when skip communication
for all devices i [n] in parallel do Flip coin 7h, {0, with Prob(n,, 1) q
Decide when to skip gradient steps (sce Lemma 3.1 Update the local auxiliary shifts hag Update the local auxiliary iterate &is via shifted gradient step
h ni, + (1 Th, f((;;))
7:
f1,411 = Fi,t - -VV - hi,44)
if 0, = then
9:
F1,+ = Σド= (3,1111 - h
o Average shifted iterates, but only very rarely!
10:
else
11:
Fi,t+1 8.,,+1
Skip communication!
12: end if
13:
hi.r+1 = h + ((11011 22.+1)
Update the local shifts has
14: end for
15:
end for
As an initialization step, we choose probability p >> O to control communication rounds, probabilities qi > 0 for each client i E [n]] to control local gradient steps, and initial control variates (or shifts) hio E IRd to control client drift. Besides, we fix the stepsize 7 > and assume that all clients commence with the same local model, namely 21,0 = ... = In,0 E Rd. Then, each iteration of the method comprises two stages, the local stage and the communication stage, operating probabilistcally. Specifically, the probabilistic nature of these stages is the following. The local stage requires computation only with some predefined probability; otherwise, the stage is void. Similarly, the communication stage requires synchronization between all clients only with probability px otherwise, the stage is void. In the local stage (lines 5-7), all clients i E [n] in parallel update their local variables (81,41,h using values (Z h,,)) from previous iterate either by computing the local gradient (z.,)) or by just copying the previous values. Afterward, in the communication stage (lines 8-13), all clients in parallel update their local variables (ær,441, hi,41) from (ăr,41, ha,41) by either averaging across the clients copying previous values.
5

---

Published in Transactions on Machine Learning Research (06/2025)
3.2 Reduced Local Computation
Clearly, communication costs are reduced the averaging step occurs only when 0, = 1 with probability of our choice. However, it is not directly apparent how the computational costs are reduced during the local stage. Indced, both options 1/i, = and 7/, = 0 involve the expression V f(((zi)) as if local gradients need to be evaluated in every iteration. As we show in the following lemma, this is not the case.
Lemma 3.1 (Fake local steps; Proof Appendix C.I Suppose that Algorithm does not communicaaee for T 21 1 conseculive ilerales, i.e., 0₂ 0--1 client i [n] have Th.t 0. Then, regardless of the coin tosses [1,,++>}==1 client i does fake local steps without any gradient computation in 7 iterates. Formally, for all j = 1,2,..., + we have
0 O for some fixed I. 2 0. Besides, let for some
Petts = Ii,t+j = Fiitt.
hia4s = ha,e4s -4 V..
Let us reformulate the above lemma. During the local stage of GradSkip, when clients do not communicate with the server, jth client terminates its local gradient steps once the local coin tosses Thr Thus, smaller probability q: implies sooner coin toss Th, in expectation, hence, less amount of local computation for client i. Therefore, we can relax the computational requirements of clients by adjusting these probabilities qi and controlling the amount of local gradient computations.
Next, let us find out how the expected number of local gradient steps depends on probabilities and gi- Let O and H, be random variables representing the number of coin tosses (Bernoulli trials) until the first occurrence geomctric random variable with parameter p, and H; Geo(1 ys) are geometric random variables with parameter 1 qi for E [m). Notice that, within one communication round, 7th client performs min ( H,) number of local gradient computations, which is again geometric random variable with parameter formalized in the next lemma, the expected mumber of local gradient steps is E [min H = 1/(1-q(11p))
of 0- 1 and Th, = respoctively. Equivalently, θ Goo(p)
(1 (1-q))(( - p) = 1 41 - p). Therefore,
Lemma 3.2 (Expected number of local steps; Proof in Appendix C.2). The expected number of local gradient
computations in each commmunication round of GradSkip 1/(1 1/(11.(11 (1-r)) for all clients E [m].
Notice that, in the special case of q = for all i E [n), GradSkip recovers Scaffnew method of Mishchenko et al. (2022). However, we will show, and obtaining the same convergence rate as Scaffnew.
choose probabilities q smaller, reducing computational complexity
Remark 3.3 (System heterogeneity). From this discussion, we conclude that GradSkip can also address system device heterogencity. In particular, probabilities {4 can be assigned to clients in accordance with their local computational resources; slow clients with scarce compule power should get small 4i while faster clients with rich resources should get bigger I 1, see section 5.2
3.3
Convergence Theory
Now that we explained the structure and computational benefits of the algorithm, let us proceed to the theoretical guarantees. We consider the same strongly convex and smooth setup as considered by Mishhhenno ct al. )022) for the distributed case.
A Assumption 3.4. All functions f((x) are strongly convex with parameter μ >> and have Lipschitz continuous gradients with Lipschitz constants L, 0, i.., for all i [n]] and any x, y E Id we have
~ || v/12 (x. 2 || v|13.
where Dj (2. = fxxx) (
v) the Bregman divergence associated with fc- We present. Lyapunov-type analysis prove the convergence, which is very common approach for iterative algorithms, Consider the Lyapunov function
(Vi()), x
72 n
V =
0a.t - 12
h - hi
(5)
pa

---

Published in Transactions on Machine Learning Research (06/2025)
where Y 0 is the stepsize, 2, is the (necessary) unique minimizer of f(z) and h4 Vf((xx) is the optimal
gradient shift. As we show next, V decreases at a linear rate.
Theorem 3.5 (Proof in Appendix C.3
Let Assumption
3.4
hold. If the slepsize satisfies
pd
S min
L, 1 - (1 p2)
and probabilities are chosen so that 0 < p. q: 1, then the iterates of GradSkip (Algorithm) 7
satisfy
E [ S (1 Vo
(6)
for all t 2 1 with p = min fre, 1 Qman (1 (1-}²)} > 0. Let us comment on this result.
The first and immediate observation from the above result is that, with a proper stepsize choice, GradSkip converges lincarly for any choice of probabilitics p and q from (0. 1].
Furthermore, by choosing all probabilities q = we get the same rate of Scaffnew with p = minf7/44 p²} (see Theorem 3.6 (Mishchenko et al. 2022)). ). we further choose the largest admissible stepsize y 1/Lmax and the optimal synchronization probability p = 1/ we get (N log 1/4) iteration complexity, ((ytimax log 1/c) accelerated communication complexity with 1/p = //'max expected mumber of local steps in each communication round. Here, we used notation Kmax max; K2 where
K4 L// is the condition nunber for client i E [r]]
Finally, exploiting smaller probabilities qi, we can optimize computational complexity subject to the same communication complexity as Scaffnew. To do that, note that the largest possible stepsize that Theorem 3.5 allows is 7 = 1/trma as
D²
}
min L; (1- p2) S min
L
Luax
L
Hence, taking into account p THu the best iteration complexity from the rate 66 is O log 1/e), which can be obtained by choosing the probabilities appropriately as formalized in the following result.
Theorem 3.6 (Optimal parameter choices; Proof in Appendix C.5 Let Assumption 3.4 hold and choose probabilities
9:
1 and p /Kmax
Then, with the largest udmissible slepsize 7 1/ m/mmus GradSkip enjoys the following properlies:
(1) O (Kmax log 1/8) ileration complexity,
(it O (VFmax log 1/s) communication complezity,
(it) for each client i [n], the expected number of local gradient computations per communication round
is
1 (1 + / Frmax)
< min (Rigs y [/mma)
(7)
1- (1 p) + Vmaa
This result clearly quantifics the benefits of using smaller probabilities q. In particular, if the condition number Kt of client is smaller than /mmax, then within each communication round, it does only k; number of local gradient steps. However, for a client having the maximal condition number (namely, clients arg max, (sr)) the number of local gradient steps /limaxs which the same for Scaffnew. From this, we conclude that, terms of computational complexity, GradSkip is always better and can be O(n) times better than Scaffnew (Mishchenko al. 2022)

---

Published in Transactions on Machine Learning Research (06/2025)
4 GradSkip+
We extend GradSkip in two directions, leading to general GradSkip+ method. The first extension concerns the optimization problem formulation. As discussed, the distributed problem (1) with consensus constraints can be reformulated as regularized problem 4 in a lifted space, where the local variables ; are stacked into a single vector in gnd Following Mishchenko et al. 2022), we consider the lifted problem
Tn E Rd
min (xx + 1b(a),
#EB"
where (() smooth, strongly convex loss, and (xx) closod, proper, convex regularizer (soc require that the proximal operator of 1 single-valued function that be computed.
4
Wo
The second extension in GradSkip+ is the generalization of the randomization procedure of probabilistic alternations in GradSkip by allowing arbitrary unbiased compression operators with certain bounds on the variance. Let us formally define the class of compressors we will be working with.
Definition 4.1 (Unbiased Compressors). For any positive semidefinite matrix $ = 0, denote by ( the class of (possibly randomized) unbiased compression operators C: IRd - Rdd such that for all x E Rd we have
[C())]] I, [[[ 2) c())]
E
I |
The class (22) is generalization of commonly used class (w) of unbiased compressors with variance bound E ||(())]| I (1 + =||l=/ for some scalar w 2 0. Indeod, when the matrix Ω = wI, then ("I)) coincides with B (w). Furthermore, the following inclusion holds:
Lemma 4.2 (Proof in Appendix D.1. ( C Bd (1+AAmx (2))2 (1+Amin (R)) -1).
The purpose of this new variance bound with matrix parameter Ω is to introduce non-uniformity the level of compression across different directions. For example, in the reformulation 4 each client controls i/n portion of the directions and the level of compression. For example, consider compression operator
C: Rd + Rd defined as
Ez//p with probability Pj. with probability 1-P;.
C(x),
0,
for all coordinates j E [d] and for any E Rd, where Pj E (0,1) are given probabilities. Then, it is easy to
check that E (Z2) with diagonal matrix Ω = Diag(?/1- - 1) having diagonal entries 1/n, - 2 0.
With finer control over the compression operator, we can use the granular smoothness information the loss function via smoothness matrices (Qu & RRchtárik [
Definition 4.3 (Matrix Smoothness). differentiable function f: Rdd + R is called L-smooth with some symmetric and positive definite matrix L > 0
1 Dy v) s 11 1 Vx,y
(10)
where ||0|| == Væ Læ denotes the L-norm of æ.
The standard L-smoothness condition with scalar L > 0 is obtained as special case of (10 for matrices of the form L = LI, where is the identity matrix. The notion of matrix smoothness provides more information about the function than mere scalar smoothness. In particular, if f is L-smooth, then it also Amax (L)-smooth due to the relation L < Amax II)I. Smoothness matrices have been used the literature of randomized coordinate descent (Richtárik & Takáč 2016 Hanzely & Richtárik 2019b ab and distributed
optimization (Safaryan al. 2021 Wang et al.
2022
8

---

Published in Transactions on Machine Learning Research (06/2025)
Algorithm GradSkip+
1: Parameters: stepsize Y > 0, compressors C. E (w) and Cp E (2)))).
2: Input: initial iterate zy E R initial control variate hy E RR, number of iterations T 2
for = 0.!....,
do
h++1 = =v)(x+) (I 2 12- (V)()))
o Update the shift h via shifted compression o Update the iterate & via a shifted gradient step
5: ftt1 = =t - 7( f - hut1)
G. 1 Cu fi+1= - proxx (8141 -11
7(1 + w)ie+1))
Estimate the proximal gradient
+[++)
T++1 = Bz+1 Tht
Update the main iterate Update the main shift hy
8: h++1 = hi+1 + ((+x] (IL-1 - 2(41)
end for
4.1 Algorithm Description
Similar to GradSkip, we maintain two variables 2t, 2n for the model, and two variables h, hg for the gradient shifts in GradSkip+- Initial values To Rd and ho E RR be chosen arbitrarily. In each iteration, GradSkip+ first updates the auxiliary shift h4t1 using the previous shift he and gradient f((x)) (line 4). This shift h4f1 then used update the auxiliary iterale 24 via shifted gradient step (line 5). Then estimate the proximal gradient 9. (line 6) in order to update the main iterate 2++1 (line 7). Lastly, we complete the iteration by updating the main shift he (line 8). See Algorithm 2 for the formal steps.
4.2 Special Cases
GradSkip+ recovers several existing methods special cases, including ProxGD, ProxSkip, and RandProx-FB (Condat & Richtárik 2022
ProxGD. When Cu is the identity compressor (i.c., w = 0), then Algorithm 2 reduces to the ProxGD algorithu as
I++1 prox, - 7h441) prox, (x+ fx,))
for any choice Cn.
ProxSkip. Let Cn be the identity compressor (i.e., N -2=1 I) and Cu be the Bernoulli compressor C, with parameter (0, 1] (note that here = 1/p 1). In this case, h,41 = h, and
(a1+1 - -hh). with probability p, prox
Ft41
ii+11
with probability 1-p.
Thus, we recover the ProxSkip algorithm.
RandProx-FB. Let Cp the identity compressor and Cn = R E (w). Then, after the following change of notation:
de
h1 U1 9.
we
the method is equivalent to RandProx-FB (Condat Richtárik 2022 which a generalization of ProxSkip when additional smoothness information for the regularizer 1 knowl
GradSkip. Finally, we can specialize GradSkip+ to recover GradSkip. Consider the lifted space Bnd where add represents the concatenations of models æ1.... Fy E Rd from all clients. The central example of unbiased compression operator for that would be the probabilistic switching mechanism used in GradSkip, which is sometimes referred to as Bernoulli compressor: for any given p [0, 1], the compressor outputs
@ p
with probability p.
and (z)
0, with probability 1 1 p,
We do consider smooth regularizers as our primary example regularizer is the non-smooth consensus constraint,

---

Published in Transactions on Machine Learning Research (06/2025)
for any imput vector x E R'd GradSkip employs one Bernoulli compressor C. with parameter p (0. controlling communication rounds, and one Bernoulli compressor Ci with parameter qi (0, 1] for
qi each client to control local gradient steps. Therefore, choosing C. = Cnd and Cp = n x .. C in the lifted space Rnd, GradSkip+ reduces to GradSkip.
4.3 Convergence Theory
We now present the convergence theory for GradSkip+t for which we replace the scalar smoothness Assumption 3.4 by matrix smoothness.
Assumption 4.4 (Convexity and smoothness). We assume that the loss function f p-strongly convex with positive μ > 0 and L-smooth with positive definite matrix L > O.
Similar to analyze GradSkip+ using the Lyapunov function
V = || - 1= 21 + w) vf(x.)]1?
The next theorem shows the linear convergence result.
Theorem 4.5 (Proof in Appendix D.2 Let Assumption
4.4 hold, Cu E (w) and Cn E ( be the
compression operators, and
Ω + w(w 2) 92)
Then, if the slepsize 7 S Amax (LS)), the ilerates of GradSkip+ (Algoritlem
salisfy
E B S (1 min {y,, Vo.
(11)
where
(1
8 =
E 10, 1].
+ Amin (S2)
(1 w)2
First, we choose Cp to be the identity compression (i.c., Q 0). then GradSkip reduces to RandProx-FBB and we recover asymptotically the same rate with linear factor (1 min(y,, 1/(+w)3) (see Theorem of Condat] & Richtárik (2022)). If further choose Cu be the Bernoulli compression with parameter p E (0, 1], then 1/p and get the rate of ProxSkip.
To recover the rate in (60 for GradSkip, consider the lifted space Rnd and the reformulated problem with objective f(z) = 1 1== f(;)), where 2, E Rd and I = (zi,...,z.) .T) ) E Rnd, Since each fi is j-strongly convex, the function f is also j-strongly convex. Regarding the smoothness condition, we have L,I E Raxd smoothness matrices (e.g., scalar L-ssmoothness) for each fi, which implies that the overall loss function f has ( I, E BRndxnd as smoothness matrix.
Furthermore, choosing Bernoulli compression operators C. -ppd and Cn Cd.. Cd in the lifted space Rnd we get
gn
1 -1 and Ω Diag
1 -1)
p
It remains to plug all these expressions into Theorem and, hence, d=1 4max (1 p²).
4.5 and recover Theorem
3.6 Indeed, Amin(5)) = 1/amax
Finally, Theorem 1.5 gives the same stepsize bound
max (LΩ) = min { Li 1+ (1 (1+(1-a)) ( ( -))} min I ai (1 12)
p2
9.)
5 Experiments
To test the performance of GradSkip and illustrate theoretical results, we use the classical logistic regression problem.
10

---

Published in Transactions on Machine Learning Research (06/2025)
Pochh g 2001
Prcal
Ratio 2.574
227
Srazsip traandaaa
22"1
321
Commantattan rounds
Conmusser HAU1S)
Joro 16.39
kel
hrec theorsien
337
SredSip traamtcat
13
22
Needke
Cormunsdd HAR1
Rato 18.12
Frcaa pracc
A00
Frech choorstet
800
Dreciip breaeteat
324
2223 2003 5863 7022
Figure 1: The first column displays the condition numbers for devices. The second column presents convergence per communication round. The third column contrasts theoretical and practical gradient computation counts. The final column reveals the average gradient computations for devices with condition number K2. Notably, in GradSkip, the device with K₁ Kmaz performs gradient computations at rate comparable to all devices in ProxSkip.
221
327
AGD
FreeS theorsical
Greckip breckoal
2242"
33'
3559
127
Conmunccttor 1ouncs
Communsc mands
3,000
in prppect
1111
thsorsicat
DeeSkoo breckell
12"
Conmunccatoo rouncs
Communcccer munds
127
Prodoy
Praddop thaare
Duehbar lasehent
StedSip
2000 2003
1003
Figure 2: The columns in this figure represent the same as those in Figure
The loss function for this model has the following form:
m
log (1 exp (-bijaJz))) + A 11001
f(z)
where n is the number of clients, m is the number of data points per worker, aij Rd and by E ff11++1) are the data samples, and X is the regularization parameter.
11

---

Published in Transactions on Machine Learning Research (06/2025)
Experiments were conducted on artificially generated data and on the "australion" dataset from LibSVM library (Chang & Lin 2011p (see Section 5.1 All algorithms were run using their theoretically optimal hyperparameters (stepsize, probabilities). We compare GradSkip with ProxSkip and AGD, which have SOTA accelerated communication complexity. Comparisons between VR-GradSkip+ and ProxSkip-VR were omitted, as their computational complexity difference similar to that of GradSkip and ProxSkip.
For GradSkip, the expected local gradient computations per communication round are at most E min (Kig /mmx)) (see ( while for ProxSkip, it is Ry/Emax- Therefore, the gradient computation ratio of ProxSkip over GradSkip depends the number of devices with R4 VKmax. With & such devices, this ratio for ProxSkip over GradSkip converges to n/4: 2 as Emax 7 DC.
In our experiments, only one device has an ill-conditioned local problem (A: 1). To showcase I this convergence, we generate data to control the smoothness constants and set the regularization parameter 10 = μ. We run GradSkip and ProxSkip algorithms for 3000 communication rounds. Figure features n 20 devices, one with large L = Linaa, and others with L; Uni1orm(0.1,1) The second column illustrates similar convergence for GradSkip and ProxSkip. As we increment mmax row by row, the ratio converges to 20, while AGD's performance drops with increasing data heterogeneity. Figure 2 illustrates the growing ratio with more clients n, assigning one device L; Lmax = 10 and others L, ~ Uniform (0.1,, 1), showing the increase in n row by row.
5.1 Experiment on the "australian" Dataset
In line with our experiments on synthetic data (section 5), we conduct a parallel experiment using the "australian" dataset from the LibSVM library (Chang & Lin 2011 This involves applying the GradSkip and ProxSkip algorithms to the logistic regression problem, characterized by the same loss function used previously:
1 n Σ (xx =
1
log (1 + exp (-bsgaza)) + + lop.
We set the regularization parameter X = 10 We split the dataset equally into n 20 devices. In this case we get = devices with ill-conditioned local problems, so the gradient computation ratio of ProxSkip over GradSkip should be close to n/a 2.5. It can be seen in Figure
00.
Creetk
Prechppp la braccical Prockaa EProeet
305
80
204
Gradeds (ihoveecst
54:44
1:307
2305 Commurioo moIns
2000
3202
Communcction
Figure 3: The plots have the same meaning as in Figure
5.2 System Heterogeneity Case
Let T, represent the time required for client complete one local step. We consider T, be a random variable with the structure T, 7, + тІ- Here, т; is scalar representing the minimum time to finish one local step machine i, and л is random jitter (time delay) assumed to have an exponential distribution with scale parameter 3. Practically, the distribution of T; can be estimated.
Our objective is to determine values for that minimize the wall training time (excluding communication time) in GradSkip. The average expected time for local training before communication on client is:
T
(1(1
12

---

Published in Transactions on Machine Learning Research (06/2025)
given that, average, device performs
9: p)
local steps (see Lemma 3.2 To reduce waiting time, we initiate by setting = 1 for the fastest clients. For other clients, we set to make the average local training time before communication match with the fastest device. This condition can be mathematically expressed as:
E
[T] 9. - p)
E [T min
yiclding the value of qi
T P E main
9: max
1 P
To assess the effectiveness of our 4: selection strategy in GradSkip compared to ProxSkip, experiments with two lypes of delay distributions for Ty uniform and exponential. In the first case, Tj Uniform 1), and in the second, noise T ~ Exponential(33) with 8, Uniform(0, 1).
Exponential(1). To introduce variability in communication delays, we also added
The results, shown in Figure g demonstrate that GradSkip, with adaptively chosen dt achieves better performance than ProxSkip with a fixed under both delay models.
10a
GradSkip Uniform
ProxSkip Uniform
GradSkip Exponential
ProxSkip Exponential
10 10-1.
10-2
10 10-3
10
10-5
10000
20000
30000
40000
50000
60000
70000
80000
Time
Figure We used the "wba" dataset from the LibSVM library (Chang & Lin 2011). which has d 300 features. The number of clients is 153
2There particular for this choice, other than that "nice" number: 153 11+ 41+51
13

---

Published in Transactions on Machine Learning Research (06/2025)
Acknowledgments
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AL, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science.
References
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-lliiieee SGD via gradient quantization and encoding. In Advonces in Newral Information Processing Systems, pp. 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli. The convergence of sparsified gradient methods. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 5977-5987. Curran Associates, Inc., 2018.
Daniel J. Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Javier Fernandez-Marquee, Yan Gao, Lorenzo Sani, Kwing Hei Li, Titouan Parcollet, Pedro Porto Buarque de Gusmão, and Nicholas D. Lane. Flower: A friendly federated learning research framework, 2022.
Chih- Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1 27:27, 2011. Software available at ltttp://ww..cit cawe. edu. wtttt//winnnissstteee libsvm
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. FedAvg with Fine Tuning: Local Updates Lead to Representation Learning. arXiv preprint arXiv:2205.13692 2022.
Laurent Condat and Peter Richtárik. RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates. In ww..i:2207.18800 2022.
Laurent Condat, 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. arXic:2205.0; 08000 2022.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Journal of Machine Learning Reseorch, pp. 2121-2159, 2011.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. In SIAM Journal Optimization, volume 23(4), pp. 2341-2368, 2013.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory SGD: variance reduction, sampling, quantization and coordinate descent. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS). 2020a.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtarik. Linearly converging error com- pensated sgd. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 20889 20900. Curran Associates, Inc., 2020b. URL https pdf
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: unified theory and new efficient methods. The 24th International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5200-5209. PMLR, 09-15 15 Jun 2019. URL http:::tt https::/pproceedingg.ro mlr. prwss//97/ qian19b.ht.r htmll
14

---

Published in Transactions on Machine Learning Research (06/2025)
Michal Grudzieñ, Grigory Malinovsky, and Peter Richtárik. Can 5th generation local training methods support client sampling? Yes! 25th International Conference on Artificial Intelligence and Stalistics (AISTATS), 2023.
F. Haddadpour and M. Mahdavi. On the convergence of local descent methods in federated learning. Tn arXiv preprint arXi::1900.14 14425, 2019.
F. Hanzely, K. Mishchenko, and P. Richtárik. SEGA: variance reduction via gradient sketching. Advances in Neural Information Processing Systems 31, pages 2082-2093, 2018.
Filip Hanzely and Peter Richtárik. Accelcrated coordinate descent with arbitrary sampling and best rates for minibatches. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 304-312. PMLR, 16-18 Apr 2019a. URL http://proceediing mlr.
www.m.l...reeee.mmmemmmmmmmmmete prwpspesssssee.... wwwps//v9//aaaeeeeeeeeeee wwt/hhaaeelllaa.aa.. html
Filip Hanzely and Peter Richtárik. One method to rule them all: Variance reduction for data, parameters and many new methods. preprint arXiv:1905.112000 2019b.
Filip Hanzely and Peter Richtárik. Federated Learning of Mixture of Global and Local Models. arXiv preprint rrXt::2002005566, 2021.
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized federated learning, 2020.
Chaoyang He, Songze Li, Jinhyun So, Xiao Zeng, Mi Zhang, Hongyi Wang, Xiaoyang Wang, Praneeth Vepakomma, Abhishek Singh, Hang Qiu, Xinghua Zhu, Jianzong Wang, Li Shen, Peilin Zhao, Yan Kang, Yang Liu, Ramesh Raskar, Qiang Yang, Murali Annavaram, and Salman Avestimehr. Fedml: research library and benchmark for federated machine learning, 2020.
S. Horváth, M. Sanjabi, L. Xiao, P. Richtárik, and M. Rabbat. FedShuffle: Recipes for better use of local work in federated learning. In Xiv preprinl Xrv: 13169, 2022.
Peter Kairouz et al. Advances and open problems in federated learning. Foundations and TrendsBin Machine 210., 2019.
Learning,
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. In International Conference Machine Learning (ICML), 2020.
A. Khaled, K. Mishchenko, and P. Richtárik. First analysis of local gd on hetcrogencous data. In NewrIPS Workshop on Federaled Learning for Data Privacy and Confidentialily, pages 1 11, 2019a.
A. Khaled, K. Mishchenko, and P. Richtárik. Better communication complexity for local sgd. In NeurIPS Workshop on Federated Learning for Data Privacy and Confidentiality, pages 1-11, 2019b.
Diederik Kingmna and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations, 2015.
T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated optimization for heterogencous networks. In Proceedings of the 1st Adaptive Multitask Learning Workshop, 2019a.
X. Li, W. Yang, S. Wang, and Z. Zhang. Commuication-effcient local decentralized SGD methods. arXiv preprint ar Xrx::11910.00 09126, 2019b.
X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang. On the convergence of FedAvg non-IID data. International Conference on Learning Representations, 2020.
Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling In arXiv:2112.1 11256, 2021.
15

---

Published in Transactions on Machine Learning Research (06/2025)
Grigory Malinovsky, Kai Yi, and Peter Richtárik. Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning. In arXim:2207.04333, 2022.
O. Mangasarian. Parallel gradient distribution in unconstrained optimization. In SIAM Journal on Control and Oplimization, 33(6):1916-1998) 1925, 1995.
H Brendan McMahan, Fider Moore, Daniel Ramage, and Blaise Agūera y Arcas. Federated learning of deep networks using model averaging. In arXiv preprint urXic:1602.05629 05629, 2016.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Commuicctionn-cffciant learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Stalistics (AISTATS), 2017.
Konstantin Mishchenko, Filip Hanzely, and Peter Richtárik. 99% of worker-master communication in distributed optimization is not needed. In Jonas Peters and David Sontag (eds.), Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAT), volume 124 of Proceedings of Machine Learning Research, pp. 979 988. PMLR, 03 06 Aug 2020.
Konstantin Mishchenko, Grigory Malinovsky, Scbastian Stich, and Peter Richtárik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! 39th International Conference Machine Learning (ICMI.), 2022.
Yurii Nesterov. Introductory Lectures on Convez Optimization, volume 87 of Applied Optimization. Springer US, Boston, MA, 2004. ISBN 978-1-4613-4691-3 978-1-4419-8853-9.
doi: (0.1007/978-1-4419-88
Xun Qian, Peter Richtárik, Robert Mansel Gower, Alibek Sailanbayev, Nicolas Loizou, and Egor Shulgin. SGD with arbitrary sampling: General analysis and improved rates. In International Conference on Machine Learning, 2019.
Zheng Qu and Peter Richtárik. Coordinate descent with arbitrary sampling it: expected separable overap- proximation. Oplimization Methods and Sofbware, 31:858 884, 2016a. doi: 10.1080/10556788 0000//0556788..0 2000778882116666 2016. 0011..19900 1190361.
Zheng Qu and Peter Richtárik. Coordinate descent with arbitrary sampling algorithms and complexity. Oplimization Methods and Software, 31 11:8829-88 1829-857, 2016b.
Amirhossein Reisizadeh, Tsidoros Txiotis, Hamed Hassani, Aryan Mokhtari, and Ramtin Pedarsani. Straggler- Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Hetero- gencity In orXiv:2012. 14458, 2020.
Peter Richtárik and Martin Takáč. On optimal probabilitics in stochastic coordinate descent methods. Optim Lell, 10: 1233 1243, 2016. doi:
Jac Hun Ro, Ananda Theertha Suresh, and Ke Wu. Fedjax: Foderated lcarning simulation with jax, 2021.
Abdurakhmon Sadiev, Dmitry Kovalev, and Peter Richtárik. Communication Accelcration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox. In arXiv:2207.03957, 2022.
Mher Safaryan, Filip Hanzely, and Peter Richtárik. Smoothness matricos beat smoothnoss constants: Better communication compression techniques for distributed optimization. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. In Mathematical Programming, volume 162(1-2), pp. 83-112, 2017.
J. Sun, T. Chen, G. Giannakis, and Z. Yang. Commmicatiion-fffieee distributed learning via lazily aggregated quantized gradients. Advances in Newral Information Processing Systems, 32:3370 3380, 2019.
Thijs Vogels, Sai Pranceth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compres- sion for distributed optimization. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
16

---

Published in Transactions on Machine Learning Research (06/2025)
B. Wang, M. Safaryan, and P. Richtárik. Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-AAwr Quantization Techniques. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-cffctenn learning via atomic sparsification. In Advances in Neural Information Processing Systems, 2018.
Jianyu Wang and Gauri Joshi. Adaptive Communication Strategies to Achieve the Best Trade-off in Local-Updale SGD In arXic:1810.08313, 2019.
Jianyu Wang, et al. A field guide to federated optimization. arxiv preprinl arXiv:2107.06917, 2021.
H. Yu, R. Jin, and S. Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. International Conference Machine Learning (TCML), 2019.
Matthew D. Zeiler. ADADELTA: Au Adaplive Learning Rate Method. In ar Xio e-prints, or Xiv:1212.5700 2012.
17

---

Published in Transactions on Machine Learning Research (06/2025)
A Limitations and Future Work
In this part, we outlinc some limitations and future rescarch directions related to our work.
Similar to the previous works Malinovsky et al. (2022); Mishchenko et al. (2022) on local gradient methods with communication acceleration, our theory does not cover non-strongly convex non-
convex objective functions. So far, the communication acceleration property of local steps has been proven only for strongly convex setup.
Another key component for designing efficient distributed and federated learning algorithms is partial device participation. This extension seems rather tricky, and we leave this as future work. recent work by Grudkien et al. 2023) considers client sampling.
Finally, one can combine the local gradient methods with communication compression techniques to achieve even better communication complexity. Moreover, our proposed gradient skipping approach can be decoupled to address computational complexity, too.
B Extension to Stochastic Gradients with Variance Reduction: VR-GradSkip+
Recently developed ProxSkip-VR method (Malinovsky et al. 2022 reduces computational complexity by allowing computationally cheaper stochastic gradient estimators instead of full batch gradients. This approach of reducing computational complexity is blind to statistical heterogeneity and is entirely orthogonal to our approach of reducing computational complexity GradSkip. is natural to ask the following question.
Is it possible to combine these two methods (ProxSkip-VR and GradSkip) to achieve even better computational complexity?
We give an affirmative answer the question by developing our most general VR-GradSkip+ method.
B.1 Algorithm Description
We get VR-GradSkipt+ method from GradSkip- by replacing the gradient V.(x))) by an unbiased estimator
gt StochasticGradient(a..f
see Algorithm
Our next assumption, initially introduced by Gorbunov et al. (2020a), postulates several parametric inequalities charactorizing the bohavior and, ultimatcly, the quality of a gradient estimator. Similar assumptions appeared later (Gorbunov et al.] 2020b 2021
Assumption B.1. Let { be the iterales produced by VR-GradSkip++. We first assume unbiasedness of the stochastic gradients ge for all iterations 2 0, i.c.,
E [g x4] (x(x)).
Next, we assume that for some non-negative constants A, B, C, B, with B < 1, and non-negative sequence {otheu the following incqualities hold for all t t20 0:
E [lla
(z(x))
21]
s 2AD, x.) )+ + Bo, + C,
E
xz]
< (..,. + Bo, + Č.
Assumption B.1 covers a very large collection of gradient estimators, including an infinite variety of sub- campling/minibatee estimators, gradient sparsification and quantization estimators, and their combinations; see (Gorbunov et al. 2020a) for examples. VR estimators are characterized by Ö 0; most non- VR.
estimators by A= B = B = 0 and C C>0 0 (Gower et. al. 2019
18

---

Published in Transactions on Machine Learning Research (06/2025)
Algorithm V
1: Parameters: stepsize Y > 0, compressors C. E (w) and Cp E (2))...
2: Input: initial iterate zy E R initial control variate hy E Rd number of iterations T 2
for 0. .,.... T do
gt StochastieCrradien(zz:.
Construct an unbiased estimator of (ar) o Update the shift ht via shifted compression o Update the iterate i via shifted stochastic gradient step
5: h+11 = 9t (I+ -2 (9t- - hi)
6: 1++1 = It - 7(9t h(t1)
7: J. = *1+=) I Cw fitt1 - prox, (8141 - 7(1 + w)h++1)
Estimate the proximal gradient
I++1 fit1 7Út
Update the main iterate xy Update the main shift h
h++1 = he+1 + (T+w] (IC-1 2(+1)
10: end for
B.2 Convergence Theory
Consider the Lyapunov function:
V | x=12 72 2) hall2 + 2
where h. Vx..))
Theorem B.2 (Proof in Appendix B.4 Let Assumption 4-4 hold, and let gr be gradient estimator satisfying
Assumption B. Let Cu (w) and Cn E (B) be the compression operators. If B >> 0, choose any
W Amax (LS2)B
and 3 B Amax (LS2)B 0.
In case of B 0, set W = 0 and B = B. If the stepsize
A ANmax (LS2) WÁ
then the iterates of VR-GradSkip+ (Algorithm
satisfy
Amax (LΩ) WC min {yp, 8,8}
M $ (1 min 6r 3,) vo + 72
where
8=1- 1 1 Amin (S2) (1- (=(atwop)) á I+ 22)
(12)
B.3 Special Cases
GradSkip+ Consider the case when stochastic gradients are full batch gradients, i.e., = Vs(x)) for
all 2 Then Algorithm g reduces to GradSkip+
ProxSkip-VR. To recover ProxSkip-VR from VR-GradSkip+t, we need the same conditions we had for recovering ProxSkip from GradSkip+. That is, let Cn be the identity compressor (i.e., Ω = I) and C, be the Bernoulli compressor Cp with parameter p E (0, 1] (note that here w 1/p - 1). In this case, frea = 14 and
prox; v (Be41 3h1)
with probability p.
11t1,
with probability -
Thus, recover the ProxSkip-VR algorithm.
19

---

Published in Transactions on Machine Learning Research (06/2025)
B.4 Proof of Theorem B.2
Here, we start proving the convergence of Algorithm 3 by first proving some auxiliary lemmas. Let
Wy 2z
79h.
and
w. == I. fx.))
Lemma B.3 (Proof in Appendix
B.5.1
y 0 and Cw E (w), Cn E ( then
E. [V2+1 - ? 0+ I gc]
1 - wzll
+
72 +w) 119: - -1, 11 (I+4)
(1 + w)2
1
+
(1- w)}
7 + 114 - h. - 12-1
where the expectation is with respect to the randomness from Cu and Ca.
Next, we upper bound the first two terms.
Lemma B.4 (Proof in Appendix B.5.2). Denote δ2 = www + (T Then
E2 || [e w.ll]] + 1 (1 (1+
[1e. - h.1l - (1 7H)) 1|+0 x. x.11² 2 -2 (1 11-11-11 (1-7AdmaxLLi)) (Lf)) D)(
(1 (1+
72 Xmax (LS2) Bo:
+ 72 Amax (L52)C.
We are ready to prove the theorem. Proof of Theorem
B.
The proof is a direct combination of the two lemmas.
(1 7/0 ||:e - 1.112 - 27 (1 7.A (L.)) Dy Dy x+)
E 1 14t1]
x
72 Xmax (LS2) Box + 2 (LS2CC
(1+ 72
w) 11, h- 1(2+5))
W (2ĀD, (21, x.) + Bo, C)
(1 744 1|,e 11112 2- 27 7( (AAmmx (L5) + WA) (T
w(w + 2)
7 22 w) ||, 11
(1+ Amnn (1)) w)²
Amax (LS2) + B
722 >"Wo, + (
W
Next we choose the stepsize
Y AAmax (LΩ)) + WA
so that the term with Dy (Kte xx) is non-negative and can be suppressed for further steps. Let
w(w+2)
(1- (1- (1 + w)
E [0, 1],
(1 + Ami (w)) + 1)2
1 1 Amin (52)
B = B Amax (L
> 0,
W
20

---

Published in Transactions on Machine Learning Research (06/2025)
provided that W>
Amaze B and continue the above derivation 1-B
E [+++]]
max (1 n/4, 1 - 8, - 3) v (A (LS)C + WÕ)
min {7H4 6, (8) wr 72 (Amax (LS2)C WCC
S (1 - min 6,,,6,83) +1 vo + 72 Amax [L WŌ
min (np, 6,93
B.5
Proof of Auxiliary Lemmas
B.5.1
Proof of Lemma B.3
Lemma
B.3
Tf > and Cu E (u),,, Cn (S2), then
E, P141 ?"Wot+1 $ ||w, - well
+
(2 + w)² 11:: - -1, (I+ (
(1 w)2
1
72(1 w)2 11, - h, 1 s2)
(1 w)2
where the expectation is with respect to the randomness from Cus and Ca-
Proof. In order to simplify notation, let P(-) prox (1+x)(1+)))(); and
== 2 - 71 + w)eeti y == - --(--11-- + w)h
(13)
STEP 1 (Optimality conditions). Using the first-order optimality conditions for f + tb and using h, = (xx)), we obtain the following lixed-point identity for æx:
J. = ppppxxx (x+ -1 wh+
13
P(y)
(14)
STEP 2 (Recalling the steps of the method). Recall that the vectors r2+1 and h441 are in Algorithm 3 updated as follows:
Ø141 = 81+1 - 7r0- = 2.+1 I w
Cw (8++1 - P(x)),
(15)
and
h41 h4n+ +
7(1 + w) (1141 2241) h141
7(1 + w)2 Cw (#+41 P(x)).
(16)
STEP 3 (One-step expectation of the Lyapunov function). The expected value of the Lyapunov
function
V. = | 2=112 2 w) he1l WWo
(17)
21

---

Published in Transactions on Machine Learning Research (06/2025)
at time t + 1, with respect to the randomness of Cus is
F Pi+1 WWet1 [Ca.9:]
1
Cu (#141 P(a)) 2. 1|| /ca.90
Ex
1t
hett - 7(1 w)) Cw (8e41 P(x)) - he 1| Coa
+ Ee
71 + w)2
2_ (Cw (8c41 P(x)) x.)
= E.
12211 2.11?
It
(1+ [lC (8(41 P(x))) C
E2
(a + w)) llb441 - h. 12 24 (cw (8141 P(x)),,441 -ha)
(1 t] |C (Re+1 P())) CCa
2
< ||a411 11 + 1+ (P(x) - -1411 - [o) + 1+ P(()) 1111l?
+
| - h.ll²
2 (P(x) 7041,711 w - h.))
1+
1
+ +it (IP(a) - =11+1l1
= l6u41 - x=11? 1t (II(()) - a.1l -11211 2+11²)
+11(+
|l 1.l1?
1
(1P(z)) 2ct1 - 7(1 (he4) h.)l1² -2(1 w/² | - n. n11l1²)
I+
[1eet1 - 1.1 72 + +w)² lieets - 11- 12²)
1+
1
P(xx) - 2.11 + P(x) بيية + 7(1 + w)en - 11)))(²)
w
[1ee+] - x. 11 + + (1 + +w) | - h. 11²)
[tw)
(IP(()) - + - - -
1+w
STEP (Applying firm non-expansiveness) Applying firm non-expansiveness of prox operator P, this leads to the inequality
E2
M 21
Wo Cn. 9t]
1 T+ )
[1set1 - xx.12 + ~ + w)2
| - hr 111²)
1
+
1 || -vvl" y11
1
(18ce11 - 10112 + + w)2 |Peet - 1r 2)
19)
1 1+
1
[be41 7 w)ee+1 (x+ 7(1 + w)) 112
1 +
1 1+ )
1
[1āet1 - 121 + 7² (1 + w)² |iu442 - h- 11²
1
8041 - I. - 7(1 + w) ( h1 )1²
1
22

---

Published in Transactions on Machine Learning Research (06/2025)
STEP 5 (Simple algebra). Next, expand the squared norm and collect the terms, obtaining
Ex Wo+1 - Wo 9c]
1 1tw )
1
(102411xx.11 - x.1 -x,11 ( +1+ | - n1 121)
1
1
+ 1+ w || x.112 - (7( I,, he.1 - h.) + 7² (1 w)]l het1 - 11
|| x=112 - ( - F,,, h - --a + 72 + 3) hh+t1 - 1111
|| 2, - -7(be11 h2)l12 721lhet1 1211 + 7² (1 + w) h-11
= || x+ - -7h1111--110001 - h+)l12 + 1 +111+(11++))) (1-1+ (1+ 72 + w) fl 1211?
STEP 6 (Tower property). Applying the expectation with respect to the randomness of Ca and using the tower property, we get
Rg
1 W2t1
72 Wor+1 [t
F/z - 7(: h(+11) - T. - --( - -m.))² 19]]
E2
(1 1
1
(1+ w) [|1se- - (I -oo (g: - -he) - -hall² gt
+
+
(1 + w))
|00
Y (x+ ?11)11
+ (11 (1
(2 + (1(+w))TT) 2 [1see - h4 - (I+
(2) -2 (gr - he)ll? gt
(1 + w)? (1+))?
| - w=112 -w-ll
+
72(1 + w)² 119. h211?
(1+w)2
+(1- (1 + w)2
7 (1 + w)²
(2(9) - hr, hr - 91) (1) + 119t hell
1
w= +
(1+ )²(1 + w2)² 19: - 1=1 -1
+ 1 (1 + w
7 + #11+w2) (1142 hr 111111100)- -1lge h1 (11
1 -
1= -w-l""
+
(1+w)² 72(1 + w) |1:: - - 1
+ +(1- (1-7+ w)
1
72 + 1/: - -ha 11
B.5.2
Proof of Lemma B.4
Lemma B.4
Denote ñ I w(w + 2))2(1++ + 12)-1, Then
E2 We - wrll?] +
+(11- 1
(1 + ? [1.. - h- 12 -1100-11)1)
(1 + w)2
$ (1 - 7/1) |lore
1xx112 27 1 - 7 Ad (L7)) xx)) + Nexnnx (IS2 Bo,
2 Amaax (LS²)C.
23

---

Published in Transactions on Machine Learning Research (06/2025)
Proof. Expanding the first term and rearranging terms, we get
Es |wy - w.ll (1 (1- w)+ (1 (1+ |199 h, -h.li--ats))-1
(1
E, |1:20 I, (9 vf(x.))11? + +www 2) [190 V
|| - x.1l 27 (2, 2., vf(x)) vf(x,))
+ 2 |1gt vf(x.)) 12] www + 2) E |19. v.f(x))) (
( 7/44 || x. 112 27 D (8,, ).) + E |19. vf(x,))
S (1 (n44 || x. 122 DrD (T 2.x) + 722 X max (LS)) ||g - vsx
(1 7/44 || =.12
Amax (LS2) (2AD) Bo, + C) (1 7/4) || 1=12² - 27 (1 7 Amxx (ISI) (F( xx.) + 72 Amaxx (LS)) Boi
2 max (LΩ)CC
C Proofs for Section 3 (GradSkip)
C.1 Proof of Lemma 3.1
Lemma 3.1 Fake local steps). Suppose that Algorithm does not communicate for 1 consecutive iterates, i.e., 0₂ oet1 =... - =0 for some fixed t 2 O. Besides, let for some client i E [n] we have Th. = O. Then, regardless of the coin tosses {11,4+5]]-1> client does fake local steps without any gradient compulation in T ilerales. Formally, for all j = 1.2,..., T 1, we have
Pleti = Ti,t+ = Di,to
(18)
R4,44 hi,e4s h4g (x.a.).
Proof. The proof is rather straightforward and follows by following the corresponding lines the algorithm.
Note that The = 02 = 0 implies (see lines and Algorithm 1 that
ii,++1 = I1,411 Z4,1
(19)
h,,411= h4,1=11,411 har Vf((I,)))
(20)
which proves 18 then
when j
Consider the two possible cases for M1,441 coupled with 0,41 0. If m
1,
fi,442
31,41 - (VV(((),,411) hi,41))
19
T1,+1 (V.((( - h1.41)
Fi,+1
and
Rs,042 = h,,+1
h4, V.(()))))
In case of 78,41 = 0, we have
f.,t2 Fi,t+1
24

---

Published in Transactions on Machine Learning Research (06/2025)
and
h1.042 = V (z(,441)1)
19
V (=(i,))
19
hig
Hence, in both cases, get
01,42 2i,++1 Fi,t-
(21)
hu,42 h4 = Vf(2z)))).
(22)
It remains to combine
21
22
with the condition that 0c+1 = O, which implies
+ 2,,,, ha,42 hi,4+2-
Thus, we proved
18 when j = 2. The proof can be completed by applying induction on j.
C.2
Proof of Lemma 3.2
Lemma 3.2 [Expocted number of local steps). The expected number of local gradient computations in each commumicalion round of GradSkip is 1/11-a(1-p)) for all clients i [n].
Proof. As mentioned in the text preceding the lemma, the proof follows from the fact that for two geometric random variables θ ~ Geo(p) and H ~ Geo(g), their minimum min H is also a geometric random variable with parameter 1 (1 (1 - g). To see this, consider the corresponding Bernoulli trials with success probability p and q for each geometric random variable. Notice that the probability that both trials fail is (1 (1-p) -)). Hence, min , H} the number of joint trials of the two Bernoulli variables until one of them succeeds with probability (1 p) 1 q). Therefore, min(O, H} is also geometric random variable with success probability
(1 q)-
7
C.3 Proof of Theorem
3.5
Theorem
3.5
Let Assumption
3.4 hold. If the stepsize satisfies
p
f min
L, qi (1 p2)
and probabilities are chosen that 0 p. 9s 1, then the iterates of GradSkip (Algorithm) satisfy
E S (1 p)
for all 1/2 with p = min {T2,1 Imar (1 - p2) > 0.
We use the following two auxiliary lemmas to prove the theorem.
Denote E, [.] == [ Fiit," ... "a,,,,aa Fn,)] the conditional expectation with respect to the randomness of all local models Z1,t -. En,t at tth iterate.
Lemma C.1 (Proof in Appendix C.4.1 If > 0 and 0 S p.q: S 1, then
E2 [W41l] =
[0,, - wi,al (1 - 9:)) (1 p²) V V((r))) - h4,
+ (1 p²) 72 liie - hi,
where the expectation is laken over O, and Wa in Algorithm Next, upper bound the first two terms of the above equality by adjusting the stepsize.
25

---

Published in Transactions on Machine Learning Research (06/2025)
Lemma C.2 (Proof in Appendix C.4.2 If
p²
0 0c7 S min
9i (1 p2)
then
72 |0g 1 wi,,,1 + (1 (1-94 (-4)) (1-p²) p²) Vf(x)))) - hu, S (1 (1-rn)]laa, - -x,1 x.1?? +
p²
Proof of Theorem
3.5
The proof of the theorem is direct combination of the above lemmas.
E2 V +1] =
| Is - - (VSi(1)))) - -1,,,)1
72
+ (1 - -4:) (1 - p²)
V (xx,) -1,.-1?
y²
7²
+ di (1 - p²²) p
hist hi, 11?
"
72 I1 hi 112
Σ
7141 || - z=11 2 + qs (1- (p2)
p2
72 hige hi 112
(1 7/4) Σ
|| x=112 qmax (1- p²)
i=1
max { -H,, Imax (1-))) V/e
(1 min {aH,1 1 - qmax (1 - p²)}} }} M.
C.4 Proof of Auxiliary Lemmas
C.4.1 Proof of Lemma C.1
Lemma C.1
If and S p,4 $ 1, then
72
B2 [++1]]
| wi,el12 (1- (1 p²)
( - 11,=
p
72
di (1 11-)²) x²)
D2 Ilke 11,
where the expectation is taken over Og and Wha in Algorithm Proof. In order to simplify notation, denote
2 hh,44
2 hs.
2 = 2,1411
Yb == E,
(23)
p
p
F
T..
(24)
t=1
f=1
STEP (Recalling the steps of the method). Recall that
with probability p.
T4,41
(25)
Bitt1,
with probability p.
26

---

Published in Transactions on Machine Learning Research (06/2025)
and
hhat1+ + 2/0 - 2(4+1), with probability p. with probability - p.
hi4+1 STEP (One-step expectation w.r.t. the global coin toss 0²). The expected value of the Lyapunov function
(26)
h4,411
V. =
Fis Ix 1.112 +
higt 11,
(27)
p
al (1 + 1)th iterate with respect. to the coin uoss 0g is
E2 Mr+t 1
72 p²
Maaer 2( f.,411) ha. 1')
s x2,112 +
7
32
(1 p)
|| - 2.l12+
lllictts - heall?
p
i=1
24
| - y11
+ || - I; + 1/4 -z(())
22 - xx11? |
+ (1 p) Σ
pp Il - -hi,all?
i=1
xx112 + 22
1a 1:112 (1 p) Σ
pa lliuat2 -matll?
p
p [Ba.et1 Ther44
_
D xx
p
(1 pp) (187,111 - -xx1(² 2= +
22 - - ma..ll2) ]
pa
STEP 3 (Simple algebra). Next, we expand the squared norm and collect the terms, obtaining
E2 [W+z 17,,5.... Tn,e]
Σ p1 - =2.1 + p 2
|la - hi 27(21,411 x., hieei - h2.x)
pa
+ (1 p1-p) p) (1221411 - 12,1112
72
[h - 12,1112))
x2
72 [haeet - hi
|10,,011 - 10112-22(00.44 - Ie, Buse hin)) + 3
1
|| -x.- -x--7 - (hu.411-s..))) -7? -?/ecce 14, 1|
22
1he - -h,,
p
72 || ||a.ct -xa- (he.s11 hi..) )|² + (1=)
4 1hrst1 11,
STEP (One-step expectation w.r.t. local coin tosses nh.)). Applying the expectation with respect to (independent) coin tosses T)ū and using the tower property we get.
27

---

Published in Transactions on Machine Learning Research (06/2025)
Ee [+++]]
Σ qi - (V(((() - hos,e) xx - 7 (biit - -ha,,)l
72
+ (1 - n²)
p2 |/,,, - -ha--hhs 112)
(122he - Ixa - ( (V)())))) - hw,))l + - -1-) 2²
+ (1 qi)
l| [f((a)))) - ha..1
p²
9i || -1+ 7 (VSi(1))))) - h2,,)11 + (1- - y²)
xx+
2/2 |l,. 11.1113))
2²
p22
+ (1 - 4i)
|1022. - xx (VI( h1,))l + (1 - y²)
72
V ( - nesall)
p2
22
Σ ||:5,1 =x - (2 - h1l +(1 (1- (1) (1 - p²)
V ( 1.0--hap -1,,-12
pa
22 llbs,c 11.
+ q: (1 1-ps p²)
p2
- qi) (1 1²²) 72 Σ ||ws,e wi,el? + (1-
pz V [((r)))) - -1
22 + qi (1 p²)
pd l ner1l1
C.4.2
Proof of Lemma C.2
Lemma
C.2 If
p²
0< S min
Li - (1 p2)
then
72 [ h2, S (1 -11)]laaa - =x_1?.
|uie - w1, + (1 - 9i) (1 p²)
pa
Proof. After some algebraic transformations we get
|/00a -i, 112 + (1 (1- (:) (1 p"²) 22 1
v (xx,,) - -bs,.
= | I - (V.((zz,)) - h + (1 - qi) (1 - p²)
22
2
ff(2;))) - -h,,.
pz
= |R 11112 - 27 (Ii, Z., V (z(4))) - -ha,a)
+ +72 (f(((t.,) h1 12 + (1 - -;) (1 -p²) 7?
[ - 11,
y22
< (1 - (uo ||,5,, -xa12 2 Dy (1i
+g² (1 1+ (1 - (1- (1 - -p?) ,
(i(((z)))) - 11,
x2
p2 + +1 q:) (1 p²)
$ (1 - (44) ||, - 2.112 - Dy (2I,,)
(1-7h
12
S (1 (o4) ||ar,e - 1=12
28

---

Published in Transactions on Machine Learning Research (06/2025)
where we used the bound and the last inequality holds since
[Vi((1))) - hi,-11 S 2T, (11,
1 p²
7 5
T, 1 91 p2)
C.5 Proof of Theorem 3.6
Theorem 3.6 (Optimll parameter choices). Let Assumption 3.4 hold and choose probabilities
Ki
1 and p Fmax
Konax
Then, with the largest admissible stepsize "y 1/maax, GradSkip enjoys the following properties:
(i) O (Kmax log 4/e) iteration complenity,
(8) O (VKmmx log 1/s) communication complerity,
(tii) for each client [n], the expected number of local gradient computations per communication round
1 Ki(1 + /imax
I min {Kis v (imax)
1 qi(1 p)
K2 + Fmax
Proof. From the choice of q,
1 1-1/a 1/mmaxx
immediately imply qmax = 1. Furthermore, choosing the optimal
we get
Paaxx
P
Lap²
min
min
T,
p)-
Tiju
T.max
Now, if we plug these values back the rate
6 we get the best rate of ProxSkip as
- min {714, 1 Gman (1 - [ー-r))}] min
T.max p²
Temax
Kmax
This implies O (Kmax log !) total iteration complexity of the method. method enjoys O Fimax log !) accelerated commuication complexity.
Due to the choice p
/Bmax" the
We have two geometric random variables, θ ~ Gcom(p) and H, ~ Geom(1 - q:), for cach client describing local training. From the algorithm description, we see that the number of local steps for client min H:), which is still a Geometric random variable with parameter q.(1 p). Therefore, the expected number of local steps for client i is the inverse of that parameter, i.c., (1-pp If we plug in the values for p and qi we have
E min (0, H.))
- 9:(1 p)
1-1 /xa
Mmaax
1 1 1/ Manax
1 1-1/2
1/84 + 1/yFmoxx
/41///moxx
Kx(1 (1 + Vimaxx
I min (Kis Vimax)
+ Vmmax
where the last inoquality can be verified with simple algebraic steps.
29

---

Published in Transactions on Machine Learning Research (06/2025)
D Proofs for Section 4 (GradSkip+)
D.1 Proof of Lemma 4.2
Lemma 4.2
(1 Amax (22)
(22) C CB"
(1+ Amin (S2))
Proof.
The proof follows from the following simple inequalities:
| |1 S Amax (I+ 12) ||=||² = + Amin (52) |
III+ [[=))) Amin (I+ |c(x)]] (1 (1+ Amax (S)) [(((x))
D.2
Proof Theorem 4.5
Theorem
4.5 Let Assumption 4-4 hold, C. Bd (w) and Ca (S2) be the compression operators, and
= I + w(w 22)
Then, if the stepsize y S Amix (Lft), the iterates of GradSkip+ (Algorithm
satisfy
B S min {y,, Vo.
where
11 11- (1 + w)2
= + Amin (S2)
E [0.
Proof. Since GradSkip+ is special of VR-GradSkipt, Theorem 4.5 follows directly corollary of Theorem B.2 What remains is to verify that the gradient estimator satisfies the condition in Assumption B.1 and to identify the associated constants. The lemma below establishes this; the final step is to substitute these values into Theorem
B22
Lemma D.1. Let Assumplion 4-4 hold. Then for the gradienl eslimator 9t V((e),, Assumplion B.1 holds
with the following parameters:
1 B-0, 0. C 0,
Ā = 0, B B 0,
Č C= 0, = 0.
Proof. The proof is rather trivial and follows from the L-smoothness of f:
E |l.. vf(x,)) -] = [v.) vf(x.)) $2D)(2,,
30


Reviews:
[{"review_id": "XgBQTNGXBg", "reviewer": "Reviewer_bc2o", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Innovative Algorithm Design (GradSkip): The paper introduces GradSkip, an extension of the ProxSkip method by Mishchenko et al. (2022), which allows clients in federated learning (FL) to perform a variable number of local gradient steps based on their local data’s \"importance\" (condition number). This flexibility reduces computational complexity compared to ProxSkip, where all clients perform the same number of steps. tt maintains the accelerated communication complexity of ProxSkip (O(√κ_max log 1/ε)) while improving computational efficiency by allowing clients with well-conditioned problems (κ_i < √κ_max) to compute fewer local gradients (at most min(κ_i, √κ_max)).\n\n2. Generalization (GradSkip+): The authors generalize GradSkip into GradSkip+, incorporating arbitrary proximable regularizers and unbiased compression operators with custom variance bounds. This makes the method versatile, recovering several existing methods (e.g., ProxGD, ProxSkip, RandProx-FB, and GradSkip itself) as special cases.\n\n3. Variance Reduction (VR-GradSkip+): The paper proposes VR-GradSkip+, combining GradSkip with variance-reduced stochastic gradients (inspired by ProxSkip-VR). This reduces computational cost further by using mini-batch stochastic gradients instead of full-batch gradients, addressing both statistical heterogeneity and computational efficiency.\n\n4. Theoretical Guarantees: The authors provide rigorous convergence proofs under strongly convex and smooth assumptions, showing linear convergence rates. For GradSkip, they demonstrate O(κ_max log 1/ε) iteration complexity and O(√κ_max log 1/ε) communication complexity, matching ProxSkip’s communication efficiency while improving computation.\nTheorems (e.g., 3.6, 4.5, B.2) offer optimal parameter choices and quantify the computational savings, especially for heterogeneous systems.\n\nWeaknesses:\n\n1. Limited Scope of Convexity: A significant limitation, acknowledged in Section A, is that the theoretical guarantees apply only to strongly convex and smooth objectives. The communication acceleration property does not extend to non-strongly convex or nonconvex problems, limiting its applicability to many real-world machine learning tasks (e.g., deep learning).\n\n2. Lack of Partial Participation: The paper assumes full client participation and does not address partial device participation, a common scenario in FL where only a subset of clients is active per round. Extending GradSkip to client sampling is noted as future work, indicating an incomplete solution for practical FL systems.\n\n3. Theoretical Focus Over Empirical Validation: While the paper includes empirical studies, they are conducted on \"carefully designed toy problems\" rather than real-world datasets. This raises questions about how well GradSkip generalizes to complex, large-scale FL scenarios, a point not fully explored due to space constraints (e.g., VR-GradSkip+ details are in the appendix).\n\nComplexity of Implementation: The algorithms (GradSkip, GradSkip+, VR-GradSkip+) introduce additional parameters (e.g., probabilities p, q_i, compression operators) and auxiliary variables (e.g., shifts h_i,t, ĥ_i,t), increasing implementation complexity compared to simpler methods like FedAvg. This could hinder adoption in resource-constrained environments.\n\n4. Sensitivity to Parameter Tuning: Optimal performance relies on carefully chosen probabilities (e.g., q_i = (1 - 1/κ_i)/(1 - 1/κ_max), p = 1/√κ_max) and step sizes (e.g., γ = 1/L_max), which require knowledge of condition numbers (κ_i, κ_max). In practice, estimating these parameters accurately across heterogeneous clients may be challenging.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This proposes a redesign of the original ProxSkip method, allowing clients with ``less important'' data to get away with fewer local training steps without impacting the overall communication complexity of the method. The author prove that the modified method, GradSkip, converges linearly under the same assumptions and has the same accelerated communication complexity, while the number of local gradient steps can be reduced relative to a local condition number. The method is further generalized by extending the randomness of probabilistic alternations to arbitrary unbiased compression operators and by considering a generic proximable regularizer", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "please refer to the weaknesses.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CM3h0nR94c", "reviewer": "Reviewer_peWp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is extremely clearly written, the motivation is explained well, intuition is given for the algorithms, and the experiments are comprehensive. The proposed algorithms are simple to implement, and the theoretical guarantees are strong.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper develops new algorithms for distributed first-order optimization. When the different workers have different computational resources available, they use clever probabilistic and linear-algebraic ideas to optimize the loss function keeping low both the communication complexity and computational complexity.\n\nThey provide theoretical guarantees for their algorithms and show that their algorithms work well in practice as well, using both synthetic and real data.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Here are some minor suggestions to further improve the presentation.\n\n1. In Definition 4.3, define the notation $\\|\\|x-y\\|\\|_L$.\n\n2. In the caption of Figure 4, explain where the dataset *w6a* is coming from. Also, it's not clear why you have written 153 as a sum of factorials and as a sum of cubes. Wouldn't $n=153$ suffice?", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7DmCVVzeor", "reviewer": "Reviewer_wr9e", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written. The ideas are clearly explained. There are both theoretical guarantees and numerical experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a class of federated learning methods. It first proposes a new method called GradSkip -- an extension the existing ProxSkip method, which considers a regularized optimization problem and uses randomization. Then, the paper proposes a generalization of GradSkip by handling more general regularizers and allowing general randomization. Last, it presents a method with variance reduction. The convergence of each method is analyzed. Numerical experiments illustrate the performance of GradSkip compared with the original method, ProxSkip.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Nothing specific.", "broader_impact_concerns": "Nothing specific.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)